指数函数之特性(续) 本原元素举例:p=11,g=2,中(p-1)=中(10)=4,即1,3,7,9与 p-1互素。若g=2为模p之本原元素,则 21=2,23=8,27=7,29mod11=6均为模11之本原元素。找到 个本原元素后可以容易找到所有本原元素,问题是如何找到第 个本原元素。 算法如下: P1.利用素性验证算法,生成一个大素数q; P2.令p=q*2+1; P3.利用素性验证算法,验证p是否是素数,如果否,则跳 转到P1; P4.生成一个随机数g,1<g<p-1; P5.验证g2modp和 gq mod p都不等于1,否则跳转到 P4 cP6.g是大素数p的本原根。 ash mfy@ustc.edu.cn 现代密码学理论与实践 18/81
mfy@ustc.edu.cn 现代密码学理论与实践 18/81 本原元素举例：p=11, g=2, φ(p-1)= φ(10)=4, 即1, 3, 7, 9与 p-1互素。若 g=2为模p之本原元素, 则 21=2, 23=8, 27=7, 29 mod 11=6均为模11之本原元素。找到 一个本原元素后可以容易找到所有本原元素, 问题是如何找到第一 个本原元素。 算法如下： ◦ P1. 利用素性验证算法，生成一个大素数q； P2. 令 p = q * 2 + 1； P3. 利用素性验证算法，验证 p 是否是素数，如果否，则跳 转到P1； P4. 生成一个随机数 g，1 < g < p - 1； P5. 验证 g2 mod p 和 gq mod p 都不等于 1，否则跳转到 P4； P6. g 是大素数 p 的本原根
指数函数之特性(续) 3.交换性 指数函数满足交换性,因为 Ex(ey(g)=Ex(g)=(gy)x=gyx y(Ex(g)=Ey(gx)=(gx)Y=g x(E√g) ))=Ey(Ex(g)) 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 19/81
mfy@ustc.edu.cn 现代密码学理论与实践 19/81 3. 交换性 指数函数满足交换性, 因为: Ex(Ey(g))=Ex(gy )=(gy ) x=gyx Ey(Ex(g))=Ey(gx)=(gx) y=gxy ∴ Ex(Ey(g))=Ey(Ex(g))
指数函数之特性(续) 4.非对称性( Asymmetric property) Ex(-g)=(-g)x=(-1)xgx=(-1)XEx(g) 若X为偶,则E(-g)=Ex(g) 若X为奇,则E(-g)=-Ex(g) 5.乘法性( Multiplicative property) Ex(g)Ex(g2)=g, x=(g1g2)x=Ex(,g2) 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 20/81
mfy@ustc.edu.cn 现代密码学理论与实践 20/81 4. 非对称性(Asymmetric Property) ∵Ex(-g)=(-g)x=(-1)xgx=(-1)xEx(g) ∴若x为偶，则Ex(-g)= Ex(g) 若x为奇，则Ex(-g)= -Ex(g) 5. 乘法性(Multiplicative Property) Ex(g1 )Ex(g2 )=g1 xg2 x=(g1g2 ) x=Ex(g1g2 )
指数函数之特性(续) 6.乘法逆元素 Multiplicative inverse 若T为g之序,则对于所有x,0≤X<T,Ex(g-)=Erx(g g-1.g的乘法逆元素 因为:Ex gx=g·g x-QT-X g ET-x(g 这是一种求乘法逆元素的方法,欲求g-时,由于g g-1(这里x= T整除p-1, g-l=g-1=gp-1-1= gp-2(mod p) g·g1modp=1,这是因为 gxg -x mod p= g mod p 7.安全性 、053Cy(Ex(q)>,求熄得y=E()9mod 0(0 ash mfy@ustc.edu.cn 现代密码学理论与实践 21/81
mfy@ustc.edu.cn 现代密码学理论与实践 21/81 6. 乘法逆元素Multiplicative Inverse 若T为g之序, 则对于所有x, 0≤x<T, Ex(g-1)=ET-X (g) g-1为g的乘法逆元素. 因为：Ex(g-1)=g-x=1•g-x= gT•g-x=gT-x= ET-x (g) 这是一种求乘法逆元素的方法, 欲求g-1时, 由于gT- 1=g-1 (这里x=1) ∵T整除p-1, ∴g-1=gT-1=gp-1-1 = gp-2 (mod p) g•g-1 mod p=1, 这是因为gxgT-x mod p=gT mod p=1 7. 安全性 给定g∈G及y∈<Ex(g)>, 求x使得y=Ex(g)=gx mod p为DLP问题
指数函数之特性(续) 8.可逆性 若T为g∈G之序,x1为x在模T时的乘法逆元素,即 XxI=1 mod t RIEx(Ex-1(g)=Ex-1(Ex(g))=gxx- mod p=g mod p 这是因为Ex(g)满足交换性,所以Ex(Ex1(g)=Ex (Exg) 另一种证明方法: x-x=1 modT=kT+ Ex(Ex-1(g)=gxx-I=gkT+1=(g)kg=1kg=g mod p 这实际上是利用费马定理对RSA算法正确性的证明 ter Science& Technologs ash mfy@ustc.edu.cn 现代密码学理论与实践 22/81
mfy@ustc.edu.cn 现代密码学理论与实践 22/81 8. 可逆性 若T为g∈G之序, x-1为x在模T时的乘法逆元素, 即 xx-1=1 mod T, 则Ex(Ex-1(g)) = Ex-1(Ex(g))=gxx-1 mod p = g mod p 这是因为Ex(g)满足交换性, 所以 Ex(Ex-1(g))=Ex- 1(Ex(g))。 另一种证明方法： ∵ x-1x = 1 mod T = kT+1 ∴Ex(Ex-1(g))=gxx-1=gkT+1=(gT) k•g=1kg=g mod p 这实际上是利用费马定理对RSA算法正确性的证明