密码学之 | RSA 算法之 private public key

liuzhengyuan

本文章只在 FishC 和我的博客发出！

RSA 算法理念

（from geek for geek）The idea of RSA is based on the fact that it is difficult to factorize a large integer. The public key consists of two numbers where one number is multiplication of two large prime numbers. And private key is also derived from the same two prime numbers. So if somebody can factorize the large number, the private key is compromised. Therefore encryption strength totally lies on the key size and if we double or triple the key size, the strength of encryption increases exponentially. RSA keys can be typically 1024 or 2048 bits long, but experts believe that 1024 bit keys could be broken in the near future. But till now it seems to be an infeasible task.

翻译：
RSA 的理念是利用了分解大整数的困难性。public key 是由两个数字组成的（其中一个是两个素数的公倍数）。Private key 是由同样的两个素数派生而来的。所以，如果有人能把大的那个数给因数分解了，那么 private key 也暴毙了。所以这个东东的破解难度完全依赖于数字的长度。。。（不想翻译了）

实现

确定 public key

选像个素数（P = 53 and Q = 59）

那么 public key 的第一个数就是 n = P * Q = 3127

然后第二个数（e）：先定 e 为 3

第二个数（e）必须要：
    整数
    不能是 n 的因数
    1 < e < Φ(n)

顺便说一下

Φ(n)是一个与 n 互素的小于 n 的非负数整数，换言之 0 >= Φ(n) > n。且 Φ(1) = 1
参考：3.8 The Euler Phi Function (whitman.edu)

确定 private key

其中 Φ(n) = (P-1)(Q-1)

目前 Φ(n) = 3016

private key (d) = (k*Φ(n) + 1) / e（暂定 k = 2）

所以目前：Public Key (n = 3127 和 e = 3) 以及 Private Key(d = 2011)

---

(之后的不弄了，麻了 )

liuzhengyuan

？ 有回帖奖励的竟然没人

liuzhengyuan

20 鱼币啊，没人？

python爱好者.

liuzhengyuan 发表于 2022-8-5 02:19
20 鱼币啊，没人？

我才是因为赠送的鱼币太少了的缘故

李天豪

感谢大佬

李天豪

liuzhengyuan

python爱好者. 发表于 2022-8-5 04:50
我才是因为赠送的鱼币太少了的缘故

不，是因为我发的版块没人

青出于蓝

Ireset

Passepartout

xuzitong

这个我知道一点，看到过文章说，未来量子计算机对破解RSA有奇效。

xuzitong

俺想挣鱼币买一点课后习题给我小弟做，技术是有滴，版主能不能帮我出出主意，挣了币咱一起分？

kerln888

邪泱

tommyyu

ZzzxzzZ

豆嘉木

zns12345

托纳利的朋友

不狂

啊！！！