zntsbkhhhhhh

公钥密码的三大数学问题

0
阅读(306) 评论(24)


     公钥密码体制又称公开密钥密码体系,公钥密码体制是现代密码学的最重要的发明和进展,在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日。


  1. RSA的安全性还是有保障的,期待楼主能介绍下应用方案。理论太复杂了


  2. 的确是这样的,据我了解他们家加密芯片的研发费用每年都是投入几百万的,而且有十几年研发芯片的根基,实力还是很雄厚的


  3. 有啊,它家芯片挺多的,工业级、民用级

  4. 市面上国内做的好的芯片我知道一家,叫凌科芯安,楼上好像也提到他家,加密芯片口碑不错,有专业的技术一对一服务,他家专做加密芯片的创新度也是非常快的。

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

  6. 文章结尾提到若无相应的安全机制保护私钥,就必须使用加密芯片来存储私钥,请问市面上那么多芯片如何挑选一款安全性较高的加密芯片?


  7. 这芯片挺智能啊!有成熟的产品了吗?

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


  9. 除了使用加密芯片来保护私钥,有没有其他的方案来存储这个私钥那?

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

  11. 那破解rsa就是破解大素数n,岂不是无解?

  12. 支持sop8及QFN32等相关封装

  13. 加密芯片支持各种大小的封装吗?

  14. 请问还有比公钥密码算法更安全的算法吗?


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