指数函数之特性（续） 15 本原元素举例：p=11,g=2,p(p-1)=φ(10)=4，即1,3,7,9 与p-1互素。若g=2为模p之本原元素，则 21=2,23=8,27=7,29=6,m0d11,均为模11之本原元素。 找到一个本原元素后可以容易找到所有本原元素，问题 是如何找到第一个本原元素。 3.交换性 指数函数满足交换性，因为： Ex(Ey(g))=Ex(gy)=(gY)x=gyx Ey(Ex(g))=Ey(g*)=(gx)y=gx ∴.Ex(Ey(g)=Ey(Ex(g) 2022/10/9 现代密码学理论与实践-08 17/70
2022/10/9 现代密码学理论与实践-08 17/70 指数函数之特性(续) 本原元素举例：p=11, g=2, φ(p-1)= φ(10)=4, 即1, 3, 7, 9 与p-1互素。若 g=2为模p之本原元素, 则 2 1=2, 23=8, 27=7, 29 =6, mod 11, 均为模11之本原元素。 找到一个本原元素后可以容易找到所有本原元素, 问题 是如何找到第一个本原元素。 3. 交换性 指数函数满足交换性, 因为: Ex(Ey(g))=Ex(gy )=(gy ) x=gyx Ey(Ex(g))=Ey(gx )=(gx ) y=gxy ∴ Ex(Ey(g))=Ey(Ex(g))
海连不 指数函数之特性（续） 1950 4.非对称性(Asymmetric Property) .Ex(-g)=(-g)x=(-1)g=(-1)xEx(g) '.若x为偶，则Ex(-g)=Ex(g) 若x为奇，则Ex(-g)=-Ex(g) 5.乘法性(Multiplicative Property) Ex(g1)Ex(g2)=g1×g2=(g1g2)x=Ex(g192) 甲 2022/10/9 现代密码学理论与实践-08 18/70
2022/10/9 现代密码学理论与实践-08 18/70 4. 非对称性(Asymmetric Property) ∵Ex(-g)=(-g)x=(-1)xg x=(-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 ) 指数函数之特性(续)
指数函数之特性（续） 15 6.乘法逆元素（乘法反元素）Multiplicative Inverse 若T为g之序，则对于所有x,0sx<T,Ex《g)=ET-x(g) g1为g的乘法逆元素 因为：Ex(g1)=g=1g-=gTgx=gTx=ETx(g) 这是一种求乘法逆元素的方法： 欲求g1时，由于g1=g1(这里X1) .T整除p-1, .'.g-1=gT-1=gp-1-1 gp-2 (mod p) gg-1modp=1,这是因为g*gT-x mod p=g"mod p=1 7.安全性 给定g∈G及y∈<Ex(g)>,求x使得y-Exg)=g×modp 为DLP问题。 2022/10/9 现代密码学理论与实践-08 19/70
2022/10/9 现代密码学理论与实践-08 19/70 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时, 由于g T-1=g-1 (这里x=1) ∵T整除p-1, ∴g -1=gT-1=gp-1-1 = g p-2 (mod p) g•g-1 mod p=1, 这是因为g xg T-x mod p=gT mod p=1 7. 安全性 给定g∈G及y∈<Ex(g)>, 求x使得y=Ex(g)=gx mod p 为DLP问题。 指数函数之特性(续)
指数函数之特性（续） 因海作术子 15 8.可逆性 若T为g∈G之序，x为在模T时的乘法逆元素，即 XX 1=1 mod T, Ex(Ex-1(g))=Ex-1(Ex(g))=gxx mod p=g mod p 这是因为Ex(g)满足交换性，所以Ex(Ex1(g)=Ex1(Ex(g)。 另一种证明方法： .x1x 1 mod T=kT+1 .'.Ex(Ex-1(g))=gxx1=gk+1=(g)kg=1kg=g mod p 这实际上是利用费马定理对RSA算法正确性的证明 2022/10/9 现代密码学理论与实践-08 20/70
2022/10/9 现代密码学理论与实践-08 20/70 8. 可逆性 若T为g∈G之序, x1为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算法正确性的证明 指数函数之特性(续)
快速指数运算法一平方再乘法 。快速指数运算法一平方再乘法(Square and multiply) 当x为n位时即X=(m-1,n-2,,1,o) Ex(g)=g=(.（1gn-1)2gn-2)2gn-3.…)2gx0 此算法共需要-1次平方及w(X)-1次乘法，平均而言 w(X)=n/2,x在二进制表示时有n/2个”0”及n/2个”1”。 因此，当x为n位时，平均需要1.5n-2个乘法（平方算 一次乘)。 甲A四两 2022/10/9 现代密码学理论与实践-08 21/70
2022/10/9 现代密码学理论与实践-08 21/70 快速指数运算法—平方再乘法 ⚫ 快速指数运算法—平方再乘法(Square and multiply) 当x为n位时即x=(xn-1 , xn-2 ,…,x1 , x0 ) Ex(g)=gx=(…(1•gxn-1) 2 •gxn-2) 2 •gxn-3…)2 •gx0 ⚫ 此算法共需要n-1次平方及w(x)-1次乘法, 平均而言 w(x)=n/2, x在二进制表示时有n/2个”0”及n/2个”1”。 因此，当x为n位时, 平均需要1.5n-2个乘法(平方算 一次乘)