少海冷不 Diffie-Hellman Example 15 Users Alice Bob who wish to swap keys Agree on prime p=353 and a =3 ● Select random secret keys: ●Acho0 ses XA=97, ●Bch00 ses XB=233 ·Compute public keys: ● ya=397m0d353=40 (Alice) 233 yB=363 m0d353=248 (Bob) Compute shared session key as: -2 97 m0d353=160 (Alice) 233 m0d353=160 (Bob) 道置道品 2022/10/9 现代密码学理论与实践-10 17/59
2022/10/9 现代密码学理论与实践-10 17/59 Diffie-Hellman Example ⚫ Users Alice & Bob who wish to swap keys ⚫ Agree on prime p=353 and α =3 ⚫ Select random secret keys: ⚫ A chooses xA=97, ⚫ B chooses xB=233 ⚫ Compute public keys: ⚫ yA=3 97 mod 353 = 40 (Alice) ⚫ yB=3 233 mod 353 = 248 (Bob) ⚫ Compute shared session key as: KAB= yB xA mod 353 = 24897 mod 353 = 160 (Alice) KAB= yA xB mod 353 = 40233 mod 353 = 160 (Bob)
作亲衣大 10.2.2 Diffie-Hellman密钥交换协议 1950 。本协议不能抵抗中间人攻击 User A User B Generate random XA<q; Calculate YA=aKA mod g YA Generate random XB<q; Calculate YB YB=aAB mod g; Calculate Calculate K=(Y)Bmod g K=(YB)XA mod g 2022. Figure 10.8 Diffie-Hellman Key Exchange 18/59
2022/10/9 现代密码学理论与实践-10 18/59 10.2.2 Diffie-Hellman密钥交换协议 ⚫ 本协议不能抵抗中间人攻击
基于DLP的概率密码系统 车k 15 ElGamal Cryptosystem ●1 假设A和B互相通信，共享大素数p,本原元素a, 0≤m≤p-1 。加密： ● A选择k∈[O,p-1],k的作用其实即为XA,A访问公共区域找到 B的公开密钥YB=axe mod p,计算： K=(YB)k mod p,EK=axek mod p C1=ak mod p C2=mK mod p 密文即为(C1,C2) ● 解密： ·B首先恢复K:K=C1阳modP=ak8modp 然后恢复m:m=c2/Kmod P=c2K1modp 兰道道■显 2022/10/9 现代密码学理论与实践-10 19/59
2022/10/9 现代密码学理论与实践-10 19/59 ⚫ 假设A和B互相通信，共享大素数p，本原元素α， 0≤m≤p-1 ⚫ 加密： ⚫ A选择k∈[0, p-1], k的作用其实即为xA, A访问公共区域找到 B的公开密钥YB = αxB mod p, 计算： K = (YB) k mod p, 即K = αxBk mod p c1 = αk mod p c2 = mK mod p 密文即为 (c1 , c2 ) ⚫ 解密： ⚫ B首先恢复K：K = c1 xB mod P = αkxB mod p ⚫ 然后恢复m：m = c2 /K mod P = c2K-1 mod p 基于DLP的概率密码系统 ElGamal Cryptosystem
ElGamal Cryptosystem 这里特别注意，k不能重复使用，如果 (1)C1.1 =ak mod p C2.1=miK mod p (2）c1.2=akm0dp C2.2 m2K mod 得：m1lm2=c2,/c2.2modp.如果m1已知，m2即可算出。 EIGamal密码体制是概率密码体制，同样的明文每次加 密得到不同的密文，因为每次随机选择k。 EIGamal密码体制加密效率是50%，因为密文大小是明 文的两倍。 EIGamal密码体制的破译难度同Diffie-Hellman的方法， 即基于DLP，离散对数问题，最快的算法需要 T=exp(In(p)lnln(p)12)次运算 2022/10/9 现代密码学理论与实践-10 20/59
2022/10/9 现代密码学理论与实践-10 20/59 这里特别注意，k不能重复使用，如果 (1) c1,1 =α k mod p c2,1 = m1K mod p (2) c1,2 = αk mod p c2,2 = m2K mod p 得：m1 /m2 = c2,1/c2,2 mod p. 如果m1已知，m2即可算出。 ⚫ ElGamal密码体制是概率密码体制，同样的明文每次加 密得到不同的密文, 因为每次随机选择k。 ⚫ ElGamal密码体制加密效率是50%，因为密文大小是明 文的两倍。 ⚫ ElGamal密码体制的破译难度同Diffie-Hellman的方法, 即基于DLP，离散对数问题，最快的算法需要 T=exp((ln(p)lnln(p)1/2)次运算。 ElGamal Cryptosystem
车学 ElGamal Cryptosystem 15 例：P=17,a=3,X4=2,3=5,m=11, 从A发送到B,A选择k=7. 求：密文(C1,c2)并解密 加密：Ya=axA mod P=32mod17=9 YB=axB mod P=35 mod 17=5 K=(YB)k mod P=57 mod 17=10 C1=ak mod P 37 mod 17 =11 C2=mK mod P=10x11 mod 17=8 所以，密文C=(C1,c2)=(11,8) 解密：K=c18m0dP=115m0d17=10 C2=mK mod P 10m mod 17=8 m C2/K mod P=C2K-1 mod P KK-1m0dP=1,即10K1m0d17=1,得K1=12 所以，明文m=c2K1m0dP=8x12mod17=11 姓道 2022/10/9 现代密码学理论与实践-10 21/59
2022/10/9 现代密码学理论与实践-10 21/59 例：P = 17, α= 3, xA = 2, xB = 5, m = 11, m 从A发送到B, A选择k = 7. 求：密文(c1 , c2 )并解密 加密：YA = αxA mod P = 32 mod 17 = 9 YB = αxB mod P = 35 mod 17 = 5 K = (YB) k mod P = 57 mod 17 = 10 c1 = αk mod P = 37 mod 17 = 11 c2 = mK mod P = 10x11 mod 17 = 8 所以，密文C = (c1 , c2 ) = (11, 8) 解密：K = c1 xB mod P = 115 mod 17 = 10 c2 = mK mod P = 10m mod 17 = 8 m = c2 /K mod P = c2K-1 mod P K K-1 mod P = 1，即10 K-1 mod 17 = 1，得K-1 = 12 所以，明文m = c2K-1 mod P = 8x12 mod 17 = 11 ElGamal Cryptosystem