9.5椭圆曲线公钥体制 1.椭圆曲线 定义951:设p是一个大于3的素数,在 zp上的椭圆曲线y2=x3+ax+b由一个基 于同余式y2=x3+ax+ b modp的解集(x, y)∈Zp*zp和一个称为无穷远点的特定 点O组成,这里的a,b∈Zp是二个满足 4a+27b≡0modp的常数
9.5椭圆曲线公钥体制 1．椭圆曲线 ◼ 定义9.5.1：设p是一个大于3的素数，在 Zp上的椭圆曲线y 2=x3+ax+b 由一个基 于同余式y 2=x3+ax+b modp的解集（x， y）∈Zp*Zp和一个称为无穷远点的特定 点O组成，这里的a,b∈ Zp是二个满足 4a+27b≡0 modp 的常数
椭圆曲线上的运算 设P=(X11)∈EQ=(X2,y2)∈E,若 1=x2且y1=y2,那么P+Q=O;否则 P+Q=(x3y3),这里的x3=2-×1×2y3=A (x1-x3)y1 y2-y如果P≠Q 3=x2x 3x,2+ 如果P=Q
椭圆曲线上的运算 ◼ 设P=(x1,y1) ∈E, Q=(x2,y2) ∈ E, 若 x1=x2且y1=-y2 ,那么 P+Q=O;否则 P+Q=(x3,y3) ,这里的x3=λ 2 -x1-x2,y3=λ (x1-x3)-y1. x3= = + − − P Q y x a Q x x y y 如果 如果 1 2 1 2 1 2 1 2 3 P
2.椭圆曲线密码体制 定理95.1( Hasse定理):如果E是定义在 域GF(q)上的椭圆曲线,N是E上的点(Xy) ∈GF(q)的数目,则 N-(q+1)2√q
2．椭圆曲线密码体制 定理9.5.1（Hasse定理）：如果E是定义在 域GF(q)上的椭圆曲线，N是E上的点(x,y) ∈GF(q)的数目，则 | N − (q +1) | 2 q
系统参数;设E是一个定义在Z。(P>3的素数)上的椭圆曲线,令a∈E,则由a 生成的子群H满足其上的离散对数问题是难处理的,选取a,计算β=a,则 私有密钥:a, 公开密钥:a,β,p 加密算法:对于明文x随机选取正整数k∈Zp1, ek(xk)=(y1y2),其中y1a,y2x+kB。 解密算法: dk yu y2y2-ay ELGamal密码体制的椭圆曲线形式
系统参数；设 E 是一个定义在 Z p (P>3 的素数)上的椭圆曲线，令 E，则由 生成的子群 H 满足其上的离散对数问题是难处理的，选取 a，计算 =a ，则 私有密钥：a, 公开密钥： ， ，p。 加密算法：对于明文x,随机选取正整数kZ p−1 , e 1 k (x,k)=(y1 ,y 2 ), 其中y1 =k ， y 2 =x+k 。 解密算法： d 2 k (y1 ,y 2 )=y 2 -ay1 ELGamal密码体制的椭圆曲线形式
隋圆曲线密码体制有如下的一些特点 1.在安全性相当的前提下,可使用较短的密钥 ■2椭圆曲线密码体制是建立在一个不同于大整数分解及素 域乘法群离散对数问题的数学难题之上 3椭圆曲线资源丰富,同一个有限域上存在着大量不同的 椭圆曲线,这为安全性增加了额外的保证。 ■4.在执行速度方面椭圆曲线密码体制较对应的离散对数 体制要快,且在签名和解密方面较RSA快,但在签名验证 和加密方面较RSA慢. ■5.椭圆曲线密码体制的安全性分析成果并不丰硕.也许这 可视为椭圆曲线密码体制具有高强度的一种证据,因此,大 多数密码学家对这种密码体制的前景持乐观态度
椭圆曲线密码体制有如下的一些特点 ： ◼ 1.在安全性相当的前提下, 可使用较短的密钥. ◼ 2.椭圆曲线密码体制是建立在一个不同于大整数分解及素 域乘法群离散对数问题的数学难题之上. ◼ 3 椭圆曲线资源丰富, 同一个有限域上存在着大量不同的 椭圆曲线, 这为安全性增加了额外的保证。 ◼ 4. 在执行速度方面,椭圆曲线密码体制较对应的离散对数 体制要快, 且在签名和解密方面较RSA 快, 但在签名验证 和加密方面较RSA 慢. ◼ 5．椭圆曲线密码体制的安全性分析成果并不丰硕. 也许这 可视为椭圆曲线密码体制具有高强度的一种证据,因此, 大 多数密码学家对这种密码体制的前景持乐观态度
96其他公开密钥密码体制 9.6 gOldwasser. Mica概率公开密钥 密码系统
9.6其他公开密钥密码体制 9.6.1GoldwasserMicali概率公开密钥 密码系统
系统参数:A随机选取两个大的强素数pq,计算n=p,随机选取数y且满足 J(y, n)=1 J(y,)(y, q)=-1,l 公开密钥:yn 私有密钥:pq 加密算法:若B想给A传送明文m,m表示成二进制形式,即m=m1,m2mA)∈F 对于m;(0≤i≤k),任意选取x,∈[n11 当m,=1时,B计算 当m,=0时,B计算C1=x2modn 则密文为E(m)=(C1C,C) 解密算法:A收到B传来的密文(C1C2…Ck)后,对每一个C1(0≤i≤k,计算JC1p) 和J(C1)。 当JC1P)=JC1=1,则m;为 当JC1P)=J(C1)=1,则m为 (m1,m22…,mk)即为明文m Goldwasser- Micali概率公开密钥密码系统
系统参数：A 随机选取两个大的强素数 p,q，计算 n=pq, 随 机选取数 y 且满足 J(y,n)=1 ,J(y,p)=J(y,q)=-1 ,则 公开密钥：y,n。 私有密钥：p,q。 加密算法：若 B 想给 A 传送明文 m，m 表示成二进制形式，即 m=(m1 ,m 2 ,…,m k )F k 2 ， 对于 mi （0 i k）,任意选取 x i [1,n-1]， 当 mi =1 时，B 计算 Ci = yx 2 i mod n。 当 mi =0 时，B 计算 Ci = x 2 i mod n。 则密文为 E(m)=(C1 ,C 2 ,…,C k )。 解密算法：A 收到B 传来的密文 (C1 ,C 2 ,…,C k )后，对每一个 C（i 0 i k），计算J(Ci ,p) 和 J(Ci ,q)。 当 J(Ci ,p)= J(Ci ,q)=-1, 则 m i 为=1 当 J(Ci ,p)= J(Ci ,q)=1, 则 mi 为=0 (m1 ,m 2 ,…,m k )即为明文 m。 Goldwasser-Micali概率公开密钥密码系统
Goldwasser-Mica概率公开密钥密码系统 的安全性分析与讨论 对于玫击者来说,当他截获到密文 (C1,C2,…,Ck)时,他能求出]Ci,n),但当 mi=0,JCin)=J(×2n)=1,当m=1, J(y×2n)=J(yn)]x2,n)=1,攻击者无法获 得其它的任何信息,而对A来说,因为他 拥有私有密钥p和q,可求出JCp), J(Ciq),从而得到明文 ■从传输效率来看,由于明文对应至[1,n-1] 之间,故其效率为,|为n的长度。效率 非常差
Goldwasser-Micali概率公开密钥密码系统 的安全性分析与讨论 ◼ 对于攻击者来说，当他截获到密文 (C1,C2,…,Ck)时，他能求出J(Ci,n) ，但当 mi=0，J(Ci,n)= J(xi2 ,n)=1，当mi=1, J(yxi2 ,n)= J(y,n)J(xi2 ,n)=1,攻击者无法获 得其它的任何信息，而对A来说，因为他 拥有私有密钥p和q ，可求出J(Ci,p)， J(Ci,q) , 从而得到明文。 ◼ 从传输效率来看，由于明文对应至[1,n-1] 之间，故其效率为，|n|为n的长度。效率 非常差
962 Merkle-Hellman背包公 钥密码体制 系统参数:A任选一个超递增序列T=(t1t2…n),整数WN满足N>∑t且 ged(W,N)=1 将递增序列T转化成为伪随机序列G=(g1g2…gn),这里的g,(i=12,n满足 gi=t, 公开密钥:G 私有密钥:TN,W 加密算法:对于待加密消息m=(m1m2xmn)∈F2,B想将之传给A,B先找出A的公开密 钥G,则密文为v=∑m.g, 解密算法:收到密文V后,计算 V=w-=∑mtWw-=∑ m, t, modN 由于T是超递增序列,利用超递增序列算法就可算出明文m
9.6.2Merkle-Hellman背包公 钥密码体制 系统参数：A 任选一个超递增序列 T=(t 1 ,t 2 ,…,t n ) ，整数 W,N 满足 N>= n i i t 1 且 gcd(W,N)=1 将递增序列 T 转化成为伪随机序列 G=(g1 ,g 2 ,…,g n ) ，这里的 g i (i=1,2,…,n)满足 g i =t i W modN, 公开密钥： G， 私有密钥：T,N,W。 加密算法：对于待加密消息 m=(m1 ,m 2 ,…,m n )F n 2 ,B 想将之传给 A，B 先找出 A 的公开密 钥 G，则密文为 V== n i i i m g 1 。 解密算法：收到密文 V 后，计算 V ' =VW −1 == n i i i m t 1 WW −1 == n i i i m t 1 modN 由于 T 是超递增序列，利用超递增序列算法就可算出明文 m
963有限自动机公开密钥密码 体制 ■此类体制是基于分解两个有限自动机的 合成也是困难的而构造的,尤其是当其 中的一个或两个为非线性时,难度就会 更大
9.6.3有限自动机公开密钥密码 体制 ◼ 此类体制是基于分解两个有限自动机的 合成也是困难的而构造的，尤其是当其 中的一个或两个为非线性时，难度就会 更大