网站社区的建设,信阳市住房和城乡建设厅网站,北京注册公司地址新规定,济南网站制作运营算法简介 RSA是一种非对称加密方式。发送者把明文通过公钥加密后发送出去#xff0c;接受者把密文通过私钥解密得到明文。 算法过程 生成公钥和私钥 选取两个质数p和q#xff0c;np*q。n的长度就是密钥长度。φ(n)(p-1)*(q-1)φ(n)为n的欧拉函数。找到1-φ(n)间与φ(n)互质的… 算法简介 RSA是一种非对称加密方式。发送者把明文通过公钥加密后发送出去接受者把密文通过私钥解密得到明文。 算法过程 生成公钥和私钥 选取两个质数p和qnp*q。n的长度就是密钥长度。φ(n)(p-1)*(q-1)φ(n)为n的欧拉函数。找到1-φ(n)间与φ(n)互质的一个数 e,将n和e封装成公钥。d*e ≡ 1mod φ(n)将n和d封装成私钥。 加密过程 假设明文为X密文 YX^e mod N 解密过程 X Y^d mod N 算法的可靠性 上述加解密过程一共涉及6个数字 n p q φ(n) e d 公钥 n e 私钥 n d。算法的可靠性即在已知 n和e的情况下能否推出d。 ed ≡ 1mod φ(n) 只有知道e和φ(n) 才能得出dφ(n)(p-1)*(q-1) 只有知道p和q才能得出φ(n) np*q 只有将n因数分解 才能得到p和q 算法可靠性在于n因数分解由于大数的因数分解是指数级别复杂程度所以保证了加密算法的可靠性。 由RSA算法中大数因数分解复杂程度的延伸 大数分解因数为何困难 分解因数是把合数分解为非平凡解非平凡解排除1和本身的质因数。 常规的因数分解 就是判断这个数能否被某一个质数整除即 a%b0。 求余的过程其实是用到了除法。除数较小的情况下求余不是难事。但是当除数很大时类似高精度除以高精度除法的效率就不那么高了。 个人认为计算机在处理大数的除法效率问题导致了大数分解因数困难。 计算机是如何处理除法运算 计算机的四则运算 传统的数学思维里并不能直接用在计算机的四则运算中例如加法132942传统思维直接对位相加有进位再加上进位。这种思维对应计算机的处理就要用到异或运算与运算和左移运算。 13 的二进制 0000 1101 29 的二进制 0001 1101异或运算 处理01的情况 0000 1101 ⊕ 0001 1101 0001 0000 ①与运算处理11的情况有1代表需要进位 0000 1101 0001 1101 0000 1101 左移运算非全0就需要左移 0000 1101 1 0001 1010 ②用 ①、②重复异或运算、与运算、左移运算0001 0000 ⊕ 0001 1010 0000 1010 ③ 0001 0000 0001 1010 0001 0000 0001 0000 1 0010 0000 ④处理 ③ ④0000 1010 ⊕ 0010 0000 0010 1010 ⑤ 0000 1010 0010 0000 0000 0000 ⑥因为⑥结果全为0所以 ⑤ 就是最终答案。 ⑤ 转为10进制即2^52^32^1 328242。 计算机除法结论 减法就是用补码参与加法运算乘法就是多个加法运算本次讨论的除法就是不断地减法操作。所以大数的除法就涉及到不断地异或、与、左移运算导致运算复杂程度升高。 本文由 mdnice 多平台发布
