[email protected]
参照
RSA 算法的加密原理是什么? - 童凌的回答 - 知乎 RSA 算法的加密原理是什么? - 知乎
来自 <RSA 算法的加密原理是什么? - 知乎>
问题1: 什么是欧拉函数
对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目(因此φ(1)=1)
来自 <欧拉函数 - 国内版 Bing>
问题1.1 什么是互质
互质是公约数只有1的两个整数
来自 <什么是互质 - 国内版 Bing>
认知1.2 φ(n)=(p-1)(q-1) 当 n = p x q 且 p 和 q 是不同素数时
问题1.3 什么这样的等式能够成立
问题2: 什么是求模反
其中
为 k * φ(n) +1
d记作e 的模反
问题3: 为什么 求得大整数的质分解 能够 破解RSA的加密密文
原因是需要求得欧拉函数 这是在破解方不知道 fi(n)本体 和 p,q时的
推导 n 的欧拉函数的方式
欧拉函数φ(n)的计算及欧拉定理 - 知乎 (zhihu.com)
在计算定理中 首先得求出这个数的质分解
才能进行后面的步骤
事实上这样的求解并不是行不通的 而是非常慢
在线的一个工具可以求得70位长的整数的质分解
但是当这个位数上百位甚至达到736位时那个计算量就是巨大而难以承受的了
分解质因数工具 - 整数分解最多为70位 (numberempire.com)
问题4: 公钥和私钥是怎么产生的
Pu = (e, n), Pr = (d, n)
问题4.1
这么看来e和d不是对称的吗 因为如果 1 < d < fi(n) 那么 e不就相当于相对d膜反 了吗
问题5: 公钥是怎么加解密的 私钥又是如何加解密的
加密过程 其实对公私钥来说都是一样的 密文C的<钥值Key> 次方 模一个 n
解密过程则有赖于一个定理 密文C的<tK(另一个钥匙)>次方恒等于上式右项
那这样的话就能加解密了
问题5.1 公钥加密私钥解 私钥加密公钥解 那么公钥加密公钥能解吗
不行的 因为公钥之间并不一定是膜反的
问题6: 私钥是如何产生公钥的
答案是还是这个式子 但是事实上还需要知道 fi(n)
也就是说从某种意义上来说 fi(n)是私钥持有方必须知道的信息
(私钥持有方手里有初始公钥 因而随时都能产生fi(n) )
更或者说 公钥本来就是公开的信息 所以私钥持有方可以默认知道公钥
默认知道公钥的话就一定能产生fi(n)
但是私钥是秘密信息 是无法被其它使用方获取的
所以其它使用方无从通过如此的方式来产生公钥的
问题7 既然找不出 私钥 那能不能直接硬猜呢
答案是可以的 但是你也不知道你猜的正不正确 而且超大的数量级的前提下
这样的猜也是很费劲的