10.23 Pohlig-He|man离散对数密 Pohlig- Hellman scheme,其安全性基于DHP问题 加密:C= Me mod p 解密:M=Cd=(Me) d mod P 这里, ed modφp(P)=1,φ(P)为模P的欧拉商数,即在(1 2,…P-1)中所有与P互素的数的个数。P为大素数,显然, P(P)=P-1 因为P是素数,q(P)容易获得,因此e和d都需要保密、 P=11,q(P)=10,d=7, 则e=d-1=inv(7,10)=3 假定M=5,则 C= Me mod p= 53 mod 11=4 M=Cd mod p= 47 mod 11=5 ad Can futer Science Technolog fy@ustc.edu.cn 现代密码学理论与实践 16/59
mfy@ustc.edu.cn 现代密码学理论与实践 16/59 Pohlig-Hellman Scheme，其安全性基于DHP问题 加密：C = Me mod P 解密：M = Cd = (Me ) d mod P 这里，ed mod φ(P) = 1，φ(P)为模P的欧拉商数，即在 (1, 2, ..., P-1)中所有与P互素的数的个数。 P为大素数，显然， φ(P)=P-1。 因为P是素数，φ(P)容易获得，因此e和d都需要保密。 P = 11，φ(P) = 10，d = 7， 则e = d-1 = inv(7, 10) = 3。 假定M = 5，则 C = Me mod P = 53 mod 11 = 4 M = Cd mod P = 47 mod 11 = 5
1024楚于DHP的概率密码系统 假设A和B互相通信,共享大素数p,本原元素α, 0≤m≤p-1 加密: A选择k∈[0,p-1],k的作用其实即为A的临时密钥 ( Ephemeral Key),A访问公共区域找到B的公开密钥YB axB mod p,计算: K=(Y) k mod p,即K=(×B) mod p a mod p (ak实质上就是A的临时公钥) C2=mk mod p (AB共享K,与 diffie-Helman密钥交换协议本质上相同) 密文即为(C1,C2) 解密: B首先恢复K:K=c1 XB mod p=∝ :kxB mod p 然后恢复m:m=c2/ K mod Pc2 K mod p fy@ustc.edu.cn 现代密码学理论与实践 17/59
mfy@ustc.edu.cn 现代密码学理论与实践 17/59 假设A和B互相通信，共享大素数p，本原元素α， 0≤m≤p-1 加密： ◦ A选择k∈[0, p-1], k的作用其实即为A的临时密钥 （Ephemeral Key）, A访问公共区域找到B的公开密钥YB = αxB mod p, 计算： K = (YB ) k mod p, 即K = (αxB) k mod p c1 = αk mod p （α k 实质上就是A的临时公钥 ） c2 = mK mod p （A,B共享K，与diffie-Helman 密钥交换协议本质上相同） 密文即为 (c1, c2) 解密： ◦ B首先恢复K：K = c1 xB mod P = αkxB mod p ◦ 然后恢复m：m = c2/K mod P = c2K-1 mod p
ElGamal Cryptosystem 这里特别注意,k不能重复使用,如果 (1)C1.1=∝ x mod p C2.1=m,k mod p (2)c1.2=∝ k mod p 2,2 m2K mod p 得:m1/m2=C2,/C22modp.如果m1已知,m2即可 算出。 丶 EIGamal密码体制是概率密码体制,同样的明文每次加 密得到不同的密文,因为每次随机选择k。 EIGamal密码体制加密效率是50%,因为密文大小是明 文的两倍。 EIGamal密码体制的破译难度同Difⅰe-Hel|maη的方 法,即基于DLP,离散对数问题,最快的算法需要 T=exp(n(p)nn(p)1/2)次运算。 amver s clevice /echvolage fy@ustc.edu.cn 现代密码学理论与实践 18/59
mfy@ustc.edu.cn 现代密码学理论与实践 18/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)次运算
EIGamal Cryptosystem 例:P=17,Q=3 B m从A发送到B,A选择k=7. 求:密文(C1,C2)并解密 加密:YA= OxA mod P=32mod17=9 B XB mod p=35 mod 17=5 K=(YBk mod P= 57 mod 17=10 C,=ak mod p=37 mod 17=11 mK mod p= 10x1l mod 17=8 所以,密文C=(C1,C2)=(11,8) 解密:K=C1× B mod p=115mod17=10 c2=mk mod p= 10m mod 17=8 m= C2/K mod p= c2K- mod P KK-1modP=1,即10K1mod17=1,得K-1 所以,明文m=C2K-1modP=8×12mod17=11 fy@ustc.edu.cn 现代密码学理论与实践 19/59
mfy@ustc.edu.cn 现代密码学理论与实践 19/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