6 离散对数与数字签名

现代密码学概论7/29/202610:56AM1主讲人：潘森杉第6讲离散对数与数字签名Merkle的背包(knapsack)问题0-1背包问题：给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程

S=∑aixi

的二进制向量X=(x1,…,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题用于公钥密码学做法方法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题易解的背包问题——超递增背包满足下列条件的背包 ai>∑aj(j=1,…,i-1)这样的背包也被称为简单背包求解从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到最小的ai例如背包序列{2,3,6,13,27,52}求解70的背包结果为{2,3,13,52}所以，密文70对应的明文为110101转换背包简单背包用作私钥如何产生相应的公钥——转换做法：选择一个整数m>∑ai(i=1,…,n)然后选择一个与m互素的整数w，然后

ai’=wai(modm)(i=1,…,n)这里的ai’是伪随机分布的这样得到的背包是非超递增背包基于背包问题的公钥密码系统

——MH公钥算法加密将明文分为长度为n的块X=(x1,…,xn)然后用公钥A’=(a1’,…,an’)，将明文变为密文S

S=E(X)=∑ai’xi解密先计算S’=w-1Smodm再求解简单背包问题S’=∑aixi背包密码系统的意义是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷Diffie-Hellman密钥交换协议公钥用于密钥交换的一个显著的优点就是通信双方可以在无需安全信道的基础上进行密钥协商。Diffie和Hellman对Alice:对Bob:有限域Fp,p为素数，p-1的完全分解是知道的g为Fp*的生成元，[1,p)中每个元素都可以表示为gx(modp)注意到，这样双方计算得到的值是相同的。——为什么？例题的答案：执行Diffie-Hellman密钥交换协议应注意的问题共同的输入p应该是一个素数，或者素数的幂，满足p-1有足够大的因子p`，大于2160Alice和Bob应该验证ga和gb不等于1，这个验证将保证gab是Fpp`阶子群的一个元素。在通信结束后，应该立即删除a和b的值，这样将会拥有前向保密性质。共同输入g不必是Fp*的生成元,但应该是Fp*中一个高阶子群的生成元Diffie-Hellman密钥交换Alice和Bob确定两个大素数p和q，

这两个数不必保密，因此Alice和Bob可以用不安全信道确定这两个数。设p＝11，q＝72. Alice选择另一个大的随机数r₁，并计算：。设r₁＝3，则A＝73mod11＝23. Alice将A发送给Bob。4. Bob选择另一个大的随机数r₂，并计算：设r2＝6，则B＝76mod11＝45. Bob将B发送给Alice。6. Alice计算密钥：k₁＝43mod11＝97. Bob计算密钥:k2＝26mod11＝9中间人攻击

——处于A、B通信中间的主动攻击者能够利用协议的消息以达到成功的攻击中间人攻击图示类似的，Malice可以伪装成Bob，并同Alice协商另一个密钥gam，然后在两人之间转发“保密”通信。攻击存在的原因：没有进行消息源的认证服务。Diffie-Hellman密钥交换的攻击replay攻击中间人攻击图示ABK=rxyEABK=rxzEK=ryzDiffie-Hellman问题和离散对数问题原理：因为离散对数问题是困难的，所以DHC问题是单向的。ElGamal密码体制问题

离散对数

实例：乘法群(G,·)，一个n阶元素

∈G，∈<

>

问题：找到唯一整数a，1≤a≤n-1满足：

a=

整数a记为log

，称为

的离散对数。性质：求解离散对数(可能)是困难的，指数运算可以应用平方-乘算法有效计算，即：指数运算是单向函数。TaherElGamal密码体制

Zp*上的ElGamal公钥密码体制素数p，使得(Zp*,·)上的离散对数问题是难处理的，令∈Zp*是一个本原元令P=Zp*,C=Zp*×Zp*,定义K={(p,

,a,):

≡

a

(modp)}p,

,是公钥，a是私钥。对K=(p,

,a,),及一个(秘密)随机数k∈Zp-1,定义eK(x,k)=(y1,y2)其中：y1=

k

modpy2=x

k

modp对y1,y2∈Zp*，定义dK(y1,y2)=y2(y1a)

-1modp注：x通过乘以

k伪装，产生y2，

k也作为密文的一部分传送，Alice随机选k，Bob知道a，可从

k计算出

k(=

ak=(

k)a)，用y2除以

k去伪装，得到x.例：p=2579，

=2为Zp*本原元令a=765，=2756mod2579=949Alice:x=1299,随机选择k=853y1=2853mod2579y2=1299×949853mod2579=2396发送密文y=(y1，y2)=(435,2396)给BobBob收到密文y=(435,2396)

x=2396×(435765)-1mod2579=1299如果Oscar可计算a=log

，则ElGamal密码体制不安全。一般地，p至少取300位十进制数，p-1具有至少一个较大的素因子。离散对数问题的算法乘法群(G,·),

∈G，ord(

)=n，给定∈<

>,找出唯一的指数a=log

，使得a=

假定计算G中两元素乘积需常数（O(1)）时间通过O(n)时间和O(1)存储空间穷举搜索计算，2，…，直到发现=

a预计算所有可能的值i，并对(i,

i

)以第二个坐标排序列表。给定，对存储的列表执行一个二分查找，直到找到a使得a=

(需O(n)时间与计算的n个幂，O(nlogn)时间对n个元素排序，近似为O(n)，二分查找时间为O(logn)，忽略对数因子项，得：用O(1)时间，O(n)步预计算和O(n)存储空间)Shanks算法算法

SHANKS(G,n,,)m←[n1/2]+1forj←0tom-1

do

计算mj

对m个(j,

mj)关于第二个坐标排序，得到列表L1fori←0tom-1

do

计算-i对m个(i,

-i)关于第二个坐标排序，得到列表L2找(j,y)∈L1和(i,y)∈L2log

←(mj+i)modn由(j,y)∈L1和(i,y)∈L2，得

mj=y=

-i

mj+i=

log

=mj+i,0≤i,j≤m-1运行时间O(m)，存储空间O(m)，是一个时间-存储折中算法O(m)O(mlogm)O(m)O(m)O(mlogm)Pollard

离散对数算法划分G=S1∪S2∪S3,元素个数大致相同。定义f:<

>×Zn×Zn→<

>×Zn×Zn如果gcd(b2i-bi,n)=1,c=(ai-a2i)(b2i-bi)-1modn算法

Pollard

离散对数算法(G,n,,)proceduref(x,a,b)ifx∈S1

thenf←(x,a,(b+1)modn)

elseifx∈S2

thenf←(x2,2amodn,2bmodn)

elsef←(x,(a+1)modn,b)return(f)main定义划分G=S1∪S2∪S3(x,a,b)←f(1,0,0)(x’,a’,b’)←f(x,a,b)whilex≠x’

do(x,a,b)←f(x,a,b)(x’,a’,b’)←f(x’,a’,b’)(x’,a’,b’)←f(x’,a’,b’)ifgcd(b’-b,n)≠1

thenreturn(“failure”)

elsereturn(“(a-a’)(b’-b)-1modn”)gcd(b’-b,n)=d>1c(b’-b)≡a-a’(modn)有d个解，假如d不是很大，可直接算出d个解并检验哪个是正确的期望在O(n1/2)次迭代计算离散对数Pohlig-Hellman算法=a,a=log

，

的阶为n=∏pici,计算出每个i对应的amodpic，然后用CRT计算出amodnn≡0(modqc),n≠0(modqc+1),q素数，求x=amodqc

记x=a0+a1q+…+ac-1qc-1,a=x+sqc1.计算a0：

n/q=a0n/q计算r=n/q,r2,…,直到某个i≤q-1:ri=n/q,则a0=i2.c=1,则x=a0;c>1,确定a0，a1，…，ac-1记

0=，算法

Pohlig-Hellmen(G,n,,,q.c)j←0

j←whilej≤c-1

do←

找到满足=in/q的i

aj←i

j+1←j←j+1return(a0,a1,…,ac-1)算法计算复杂度为O(c·q1/2)指数演算法Zp*,因子基B={p1,p2,…,pb}计算这b个素数的离散对数；利用这些离散对数，计算所要求的离散对数。c稍大于b(如c=b+10),构造c个模p的同余方程：给定b个未知量log

pi的c个同余方程，希望存在模p-1下的唯一解，于是可得因子基元素的离散对数。随机取x,计算

xmodp，确定是否xmodp的所有因子在B中。利用LasVegas随机算法计算:选随机数s,1≤s≤p-1,计算r=

smodp试图在B上分解r，如果成功，得同余方程例：p=10007,=5为本原元，作为模p的离散对数的基取B={2,3,5,7},log55=1x=4063:54063mod10007=42=2×3×7

log52+log53+log57≡4063(mod10006)x=5136:55136mod10007=54=2×33

log52+3log53+log57≡5136(mod10006)x=9865:59865mod10007=189=33×7

3log53+log57≡9865(mod10006)log52=6578,log53=6109,log57=1301求log59451:

随机取s=77369541×57736mod10007=8400=24×3×52×7在B上完全分解log59451=4log52+log53+2log55+log57-7736mod10006=6057预计算O(e(1+O(1))(lnplnlnp)^1/2),计算O(e(1/2+O(1))(lnplnlnp)^1/2)公钥加密的实用性LOGO公钥加密的实用性LOGO公钥加密的实用性LOGOLOGO公钥加密的实用性LOGO公钥加密的实用性LOGORSA编码RSA解码数字签名数字签名的实用性纸质签名的缺点民间借贷纠纷案件：甲方说，这是张“借条”；乙方说，自己只在纸上留了个名字和电话号码，其余是对方写的。法院判决，乙方败诉。1.不要轻易在空白纸上签名，如确有需要签名，务必在签名旁边注明用途。2.借条内容由借款人自行书写。3.借条出具后由借款人保留一份复印件，并要求出借人在复印件上签字。4.交易记录有迹可循。LOGO“定金”and“订金”定金：是指合同当事人未来确保合同履行，依据法律规定或者当事人双方约定，由当事人一方在在合同订立时或者订立后履行前，按照合同标的额的一定比例（≤总房款的20%