公钥密码的三大数学问题

wyj777

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

ds252673381

那么请问楼主，目前国内哪家的加密芯片性价比较高呢

dzdjkf

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

旋转の木偶

凌科家的加密芯片可以根据客户需要进行定义算法吗？

paultoday

旋转の木偶 发表于 2021-1-29 17:54
凌科家的加密芯片可以根据客户需要进行定义算法吗？

当然，技术针对客户需求一对一支持

11199124

这么深奥的文章，对于小白来说完全看不明白，太专业了

苍茫的天涯是

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

wyj777

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

小二来碗孟婆汤

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