密码学中数学困难问题

密码学中数学困难问题

1.大整数因数分解问题 Ⅰ）给定两个素数p,q,计算乘积p·q=n很容易； Ⅱ）给定大整数n，求n的素因素p,q使得n=p·q非常困难. 例1 p=20000000000000002559,q=80000000000000001239是两个安全素数，它们的乘积 n=p·q=160000000000000229500000000000003170601. 但要分解这个n非常困难.

2.离散对数问题 已知有限循环群G={g∧k∣k=0,1,2,…}及其生成元g和阶n=∣G∣. Ⅰ）给定整数a，计算元素g∧a=h很容易； Ⅱ）给定元素h，计算整数x，0≤x≤n,使得g∧x=h非常困难. 例2 p=12000000000000002559是一个安全素数，F_p=Z/pZ是一个有限域，F*_p=F_p{0}是一个乘法循环群，其生成元g=11. 给定整数a=2030428,可以快速计算 g∧a≡1134889584997235257（modp）. 但要求整数x，使得g∧x≡1134889584997235257非常困难.

3.椭圆曲线离散对数问题 已知有限域F_p上的椭圆曲线点群 E(F_p)={(x,y)∈F_p×F_p∣y²=x³+ax+b,a,b∈F_p}∪{O}， 点P=(x,y)的阶为一个大素数. Ⅰ）给定整数a，计算整数x，使得xP=(x_a,y_a)=Q很容易； Ⅱ）给定点Q，计算整数x，使得xP=Q非常困难. 例3 P=10823是一个素数，有限域F_p=Z/pZ上的椭圆曲线点群 E(F_p)={(x,y)∈F_p×F_p∣y²=x³+3x+7}∪{O}， ∣E(F_p)∣=100482=2·3·16747.E(F_p)的生成元为P_0=(1,8811).点P=6P_0=(62046,14962)的阶为素数16747. Ⅰ)给定a=1007，计算aP=(80726,17229)=Q很容易； Ⅱ）给定点Q=(80726,17229)，求整数x使得xP=Q很困难.

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。