三大数学难题

在信息安全领域应用广泛的三大数学难题

No1. 大整数因素分解问题Permalink

• 已知两个大素数 p,q，求 N=pq 很容易。
• 已知N为两个大素数的积，求 p 和 q 非常困难。

典型应用: RSA

No2. 离散对数问题Permalink

已知有限循环群 G=<g>={gk|k=0,1,2,⋯} 及其生成元 g 和阶 n=|G|。

• 给定整数 a，求 ga=h 很容易。
• 给定元素 h，求整数 x,0≤x≤n ，使得 gx=h 非常困难。

典型应用：Diffie-Hellman

No3. 椭圆曲线离散对数问题Permalink

已知有限域 Fp 上的椭圆曲线群 ‘E(Fp)={(x,y)|∈Fp×Fp,y2=x3+ax+b,a,b∈Fp}∪{O}‘ 及点 P=(x,y) 的阶为一个大素数。

• 已知 a ，求点 aP=(xa,ya)=Q 很容易。
• 已知点 Q，求整数 x，使得 xP=Q 非常困难。

可见密码学很多都是在和大素数打交道。

详见：信息安全数学基础