Presentation is loading. Please wait.

Presentation is loading. Please wait.

第十章 数字签名与认证协议 1 EIGamal签名方案

Similar presentations


Presentation on theme: "第十章 数字签名与认证协议 1 EIGamal签名方案"— Presentation transcript:

1 第十章 数字签名与认证协议 1 EIGamal签名方案
第十章 数字签名与认证协议 1 EIGamal签名方案 该方案是特别为签名的目的而设计的。1985年提出,很大程度上为Diffe-Hellman密钥交换算法的推广和变形。这个方案的改进已被美国NIST(国家标准和技术研究所)采纳作为数字签名标准。 方案:P为素数,FP中的离散对数问题是难处理的。取本原元Fp*,消息集合M=Fp*,签名集合A=Fp*Zp-1,定义K={(p,,a,)| = a(modp)},值p,和是公开的,a是保密的。 对K=( p,,a,)和一个(秘密)随机数k Zp-1*,对消息x

2 M进行签名: SigK(x,k)=(,), 其中,=k(modp), =(x-  )k-1(modp-1) 对x, Fp*和Zp-1,验证签名定义为 Ver(x, ,)=真(true)x(modp) 对EIGamal签名方案安全性的讨论: 若Oscar在不知道a的情况下企图伪造一个给定消息x的签名: Sigoscar(x,k)=(,) (1)Oscar先选定一个,然后企图找,这样,他就必须解一个关于未知数的方程: x(modp) 这个方程是一个已知无可行解法的难处理问题!

3 (2)Oscar先选定一个 ,使其满足: x(modp),于是,
log(-x)=?,这自然是难处理的问题! (3)若两者, 都被 Oscar首先选定,然后企图解出一个随机消息x,使得x(modp),于是Oscar利用这种方式也不能伪造随机消息的签名。 (4) Oscar同时选择, 和x来伪造签名问题: 假设i和j是整数,0<=I<=p-2,0<=j<=p-2,且(j,p-1)=1,先完成下列计算: ij(modp) -j-1(modp-1) x=-ij-1(modp-1) (其中j-1是用模p-1来计算的)

4 可以证实(, )是一个消息x的有效签名:
例子:假设p=467,=2和=132,它们为Bob公开的签名方案中的参数。Oscar利用这些参数伪造对一随机信息x的签名: 选择i=99和j=179,那么j-1(modp-1)=151,计算出下列的x,, :

5 那么(117,41)是消息331的一个有效签名。验证: 因此,这个伪造的签名有效! (5)其他类型的伪造签名: Oscar依据Bob已签名的消息来做伪签名。假设(, ) 是一个消息x的有效签名,那么Oscar可以用此来伪签其它 消息: 设h,i,j为整数,0<=h,i,j<=p-2且 ,计算

6 然后可验证出 (其中 是模p-1算出) 因此 , 为假消息 的一个有效签名 讨论两个问题:
因此 , 为假消息 的一个有效签名 讨论两个问题: (1)用EIGamal方案计算一个签名时,使用的随机数k为什么不能泄露? (2)若Bob用相同的值来签名不同的两份消息,Oscar能否攻破这个体制?

7 2 数字签名标准 公布于1994年5月19日的联邦记录上,并于1994年12月1日采纳为标准DSS。DSS为EIGamal签名方案的改进。
2 数字签名标准 公布于1994年5月19日的联邦记录上,并于1994年12月1日采纳为标准DSS。DSS为EIGamal签名方案的改进。 DSS:p为512bit的素数,q为160比特的素数,且q|p-1, Fp*,且为模p的q次单位根。消息集合P=Fp*,签名集合A=FqFq,定义K={(p,,a,)| = a(modp)},值p,q,和是公开的,a是保密的。 取xP,对K=( p,q,,a,)和一个(秘密)随机数k (1<=k<=q-1) ,定义 SigK(x,k)=(,), 其中,=k(modp)(modq), =(x+  )k-1(modq) 对xFp*和,Fq来说,按下述计算来验证签名的真伪:

8 注:1*.DSS的使用涉及到Smart卡的使用,要求短的签名。DSS以一个巧妙的方法修改了EIGamal方案,使得签名160bits消息产生一个320bit的签名,但是计算使用了512比特的模p.
2*.要求 在整个签名算法中,如果计算了一个值 ,程序自动拒绝,并且产生一个新的随机值计算新的签名,事实上, 的发生概率大约为2-160.

9 3*. DSS是一个产生签名比验证签名快得多的方案,验证签名太慢!
4*. Smart卡的应用!!Smart卡有有限的处理能力,但是能与计算机进行通信。人们企图设计一种让Smart卡仅作小量运算的签名方案。该方案必须完成签名、验证签名两部分,而且方便安全。 用DSS签名的例子: 假设取q=101,p=78*9+1=7879,3为F7879的一个本原 元,所以能取=378(mod7879)=170为模p的q次单位根。 假设a=75,那么a(mod7879)=4567.现在, 假设Bob想签 名一个消息x=1234,且他选择了随机值k=50,可算得 k-1(mod101)=99,签名算出: =(17050(mod7879)(mod101) =2518(mod101)=94

10 =( *94)99(mod101)=97 签名为(1234,94,97)。 验证: -1=97-1(mod101)=25 , e1=1234*25(mod101)=45,e2=94*25(mod101)=27 (17045*456727(mod7879))(mod101)=2518(mod101)=94 因此,该签名是有效的。

11 3 一次签名 任何单向函数都可用来构造一次签名方案。该签名对一个消息来说,唯一对应着一个确定的签名。这样的签名可验证任意多次。
3 一次签名 任何单向函数都可用来构造一次签名方案。该签名对一个消息来说,唯一对应着一个确定的签名。这样的签名可验证任意多次。 Lamport方案: 设k为一个正整数,P={0,1}K,设f:YZ是一个单向函数,签名集合A=YK,对于1<=i<=k, j=0,1来说,yijY可随机地选择。选后,可算得 Zij=f(yij) <=i<=k,j=0,1 密钥K由2k个y值和2k个Z值组成,y值保密而Z值公开.消息x=x1x2….xk(kbit串)。对于K=(yij,Zij|1<=i<=k,j=0,1)

12 定义 其中,yixi=ai,f(ai)=Zixi 验证: 注:1*. 待签名的消息为一个二进制 元组,每一个都单独签名.这个特征决定了 “一次签名” 2*.验证是简单的检查:签名结果的每一个元素是相应公开钥元素的愿象. 例子:取单向函数f(x)=x(modp),设p=7879(素数),3为F7879的本原元,定义f(x)=3x(mod7879) 假设Bob想签名3比特消息,他选择了6个(秘密的)随机数:

13 y10=5831,y11=735,y20=803,y21=2467,y30=4285,y31=6449 在f的作用下计算y的像: z10=2009,z11=3810,z20=4672,z21=4721,z30=268,z31=5732 将这些Z值公开。现在Bob打算签名消息x=(1,1,0),那么对的签名为(y11,y21,y30)=(735,2467,4285). 验证签名: 3735(mod7879)=3810 32467(mod7879)=4721 34285(mod7879)=268 因此,该签名有效。 注:该方案,仅能用于签一个消息!一次,无法伪造。

14 4 不可否认的签名 (Chaum和Van Antwerprn 1989年提出)
该签名的特征是:验证签名者必须与签名者合作。验证签名是通过询问------应答协议来完成。这个协议可防止签名者Bob否认他以前做的签名。 一个不可否认的签名方案有三个部分组成: 签名算法、验证协议、否认协议 设p=2q+1是一个素数,它满足q为素数,且Fp中的对数问题是难解的。 ,且阶为q,取1<=a<=q-1,定义 , G表示阶为q的FP*的子群。易见G=<>,(事实上G由模p的二次剩余组成) 设P=A=G,且定义K={(p,,a,)| = a(modp)},值p,和是公开的,a是保密的。

15 对K=(p,,a,)和消息xG,定义y=SigK(x)=xa(modp)
易见y G 。按如下协议完成验证: (1).Alice 随机选择 (2)Alice计算 , 且将C送给Bob. (3)Bob计算 , 且d将送给Alice. (4)Alice接受y作为一个有效签名,当且仅当 对上述这个签名方案,要证明以下两点: 1)Alice将回接受按如上方案的有效签名 2)Bob几乎不可否认经Alice 验证过的自己的签名。 证明(1):(alice接受Bob的签名)。下面计算的所有指数都已做到模q约简.

16 代入上式得 刚好与协议(4)相符,故Alice接受Bob的签名。对于(2) Bob几乎不可否认经Alice验证过的自己的签名。相当于证 明下述定 理。 定理1:若 ,那么Alice以概率1/(q-1)接受y作 为x的有效签名. 证明: Bob对x做了签名y(=xa)给Alice后。Bob接受了Alice的 一个询问 ,这个询问对应于q-1个有序对 (e1,e2)。( 原因是 一旦固定,e2=f(e1)。然而, Bob不知Alice选择了哪一对(e1,e2)来构造出C。

17 如果 ,那么Bob能做的任何可能回答 , 刚好与q-1个可能的有序对(e1,e2)中的一个相对应。 由 G=<>, 所以对C,d,x,y来说,可设 C=  i,d= j,x= k,y=  l,i,j,k,l , 考虑同余式: 写出关于 的指数表示: 等价于下述方程组:

18 既然假设 而 y=2l,xa=(k)a=  ak,所以lak,
相当于说上述方程的系数行列式: 知该方程组仅有唯一一组解。 即对每一个dG, 对于q-1个可能的有序对中(e1,e2),刚好 有一个是正确的回答,Bob给Alice的一个回答d,将被验证 的概率刚好为1/(q-1)。定理得证!

19 下面讨论否认协议: 目的:(1)Bob能使Alice相信一个无效的签名是伪造的. (2)Bob签名有效,而导致Alice判决错误的概率为小概率事件。 否认协议:(y?=xa)暂视为对的签名 1)Alice 随机选取 2)Alice计算 且将送给Bob, 3)Bob计算 ,且将他回送Alice 4)Alice验证 5)Alice再随机选取 6)Alice计算 ,且将他送给Bob 7)Bob计算 ,且将他回送给Alice 8)Alice验证

20 9)Alice推出 y是伪造的 定理2:如果 yxa(modp) ,且Alice和Bob都遵守否认协议,那么 证明:注意, , 而 又 ,从而有 进一步有

21 类似地,按如上方式推出 证毕。 注:我们不能假设遵守了否认协议,他可以想方设法构造d,D,来达到否认自己签过名的目的。然而,只要Alice严格遵守协议,Bob是无法否认的。可证。 定理3,假设yxa(modp) 且Alice遵守否认协议,如果 那么 成立的概率为1-1/(q-1)。


Download ppt "第十章 数字签名与认证协议 1 EIGamal签名方案"

Similar presentations


Ads by Google