公钥密码体制又称公开密钥密码体系, 公钥密码体制是现代密码学的最重要的发明和进展, 在 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∣y2=x3+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∣y2=x3+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 日.
公钥密码的三大数学问题
原文: https://blog.51cto.com/13520299/2608125
来源: http://www.bubuko.com/infodetail-3720872.html