公钥密码的三大数学问题

李阿淇

公钥密码的三大数学问题 [复制链接]

 

公钥密码体制又称公开密钥密码体系，公钥密码体制是现代密码学的最重要的发明和进展，在1976年，Whitfield Diffie和Martin Hellman发表了“New directions in cryptography”这篇划时代的文章奠定了公钥密码系统的基础。公钥密码体制根据其所依据的难题一般分为三类：大素数分解问题类、离散对数问题类、椭圆曲线类。

 

1：大数因子分解

具体说明：

Ⅰ）给定两个素数p,q,计算乘积p·q=n很容易；

Ⅱ）给定大整数n，求n的素因素p,q使得n=p·q非常困难.

      大数因子分解是国际数学界几百年来尚未解决的难题，也是现代密码学中公开密钥RSA算法密码体制建立的基础。《大数因子分解的合数模式特性》从RSA算法存在的不动点中发现了素数因子的分布与特性以及它们之间的连接机制，据此将大数因子分解问题转化为在两个含有素数因子的数之间求公因子问题，将最困难的大数因子分解问题转化为一系列算法的初等数学问题，这无疑是研究大数因子分解的重要成果与进展。

2：离散对数

已知有限循环群G={g∧k∣k=0,1,2,...}及其生成元g和阶n=∣G∣.

Ⅰ）给定整数a，计算元素g∧a=h很容易；

Ⅱ）给定元素h，计算整数x，0≤x≤n,使得g∧x=h非常困难，其难度与RSA中因子分解素数之积的难度有相同的数量级。

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很困难.

综上，理解数学原理可能比较烧脑，但是作为应用者来说，我们其实不需要完全掌握原理，我们只需要记住一点最重要的，即公钥密钥体系中，私钥的安全是最重要的，如果运行环境中没有相应的安全机制保护私钥，就必须使用加密芯片来存储私钥，包括私钥运算也要在加密芯片中执行，否则私钥泄露，整个安全体系就被攻破了。

 

参考资料：

《简明信息安全数学基础》，陈恭亮，高等教育出版社，2011年1月1日。

okhxyyo

谢谢分享~~所学都还给老师了的我~~

freebsder

有点难。。。看不懂

dzgc42673

国内做推广的那几家产品都不错，我们公司都测评过，凌科家的算法移植技术还是比较出众的，可以试试

额气氛如果全国

rsa算法在什么地方用的多啊，没接触过呢

EC1018

实际项目中的登陆认证、web api接口调用、支付接口调用等场合经常涉及到：md5、sh、 rsa等算法。各大银行接口中经常使用MD5算法对调用接口参数进行签名防篡改

陌小凯

楼主讲的太好了，学习了。

李阿淇

如果放在服务器上面就不需要保护私钥了

dzgc42673

支持sop8及QFN32等相关封装

额气氛如果全国

是不是可以理解为私钥的安全性取决于硬件载体的安全性

EC1018

我心痛了 发表于 2021-2-2 08:27 除了使用加密芯片来保护私钥，有没有其他的方案来存储这个私钥那？

理论上来说，破解RSA密码的问题就是从已知的e和n的数值，想办法求出d的数值，这样就可以得到私钥来破解密文。

李阿淇

有啊，它家芯片挺多的，工业级、民用级