一个数学问题，关于 RSA 里的 e 的问题。

[saranz]

关于 RSA 里，e 是怎么得出的问题。
B 站看了半天没看明白……
也没有一个视频说明的这个 e 怎么来的，搜了半天也没有结果。
咱这脑子真的不明白……
请各位数学大师傅给说说个明白呗。

p= 11, q= 19
φn= (11-1)(19-1)

e 取 7 。<== 这个 7 是怎么计算出来的，是随便取的一小于 φn 的质数，还是是经过什么过程计算出来的？

[adoal]

理论上随便选都可以。但是随便选的作为幂有可能会导致计算量太大。
PEM 建议用 3 ，X.509 建议用 65537 ，PKCS#1 建议用两者之一。

[tool2dx]

数学上无所谓，代码里要用到中国剩余定理，那就只能选特定的 e

[rabbbit]

随便选的
https://en.wikipedia.org/wiki/65,537

65537 is commonly used as a public exponent in the RSA cryptosystem. Because it is the Fermat number Fn = 22n + 1 with n = 4, the common shorthand is "F4" or "F4".[3] This value was used in RSA mainly for historical reasons; early raw RSA implementations (without proper padding) were vulnerable to very small exponents, while use of high exponents was computationally expensive with no advantage to security (assuming proper padding).[4]

[rabbbit]

随便选，条件是 1 < e < λ(n) 并且 e 和 λ(n) 互质

[saranz]

@rabbbit 就这个条件完全搞不明白…… 究竟是要计算出来还是随便找个小于 φn 的质数。


@tool2dx 中国剩余定理？

[rabbbit]

不懂，我以为就是随便选了个质数。
看看这里，也许有帮助。

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

e having a short bit-length and small Hamming weight results in more efficient encryption – the most commonly chosen value for e is 216 + 1 = 65537. The smallest (and fastest) possible value for e is 3, but such a small value for e has been shown to be less secure in some settings.

[rabbbit]

谁能讲讲这个 small Hamming weight 的作用？

[saranz]

@rabbbit 哎，不仅数学不会，English 还不懂，咱果然不适合研究这么深奥的学问。

看了半天，我的理解是，一个小于 φn 且是相对小的数。
但是不知道这是不是正确的理解。

[lDqe4OE6iOEUQNM7]

，
𝑝
=
11
p=11 和
𝑞
=
19
q=19 ，所以：

𝜙
(
𝑛
)
=
(
𝑝
−
1
)
(
𝑞
−
1
)
=
(
11
−
1
)
(
19
−
1
)
=
10
×
18
=
180
ϕ(n)=(p−1)(q−1)=(11−1)(19−1)=10×18=180

[lDqe4OE6iOEUQNM7]

p = 11;
q = 19;
n = p * q;
phiN = (p - 1) * (q - 1);
e = 7;
GCD[e, phiN]

[lDqe4OE6iOEUQNM7]

验证 7 和 180 互质性：
gcd(7,180)=1

[saranz]

@James2099 所以这个 7 究竟是怎么来的，是随便从小于 phiN 的质数里找一个呐，还是需要计算出来一个质数呐。

[marat1ren]

一般都先从 65537 ，如果 65537 不满足验证条件就从小的质数开始，比如 3 。

[pxiphx891]

可以看一下这一节： https://datatracker.ietf.org/doc/html/rfc8017#section-3.1

写的很清楚：「一个有效的 RSA 公钥中，RSA 模数 n 是 u 个不同奇素数 r_i 的乘积，i = 1, 2, ..., u ，此处 u >= 2 ，而 RSA 公钥指数 e 是一个介于 3 和 n - 1 之间的整数，满足 e 与λ(n)的最大公约数为 1 ，其中λ(n) = r_1 - 1, ..., r_u - 1 的最小公倍数。按照惯例，前两个素数 r_1 和 r_2 也可以分别表示为 p 和 q 。」

[jedrek]

@saranz
https://totct.com/article/modern-cryptography/

[234ygg]

e 随便取的，比 n 小 并且与φn 互素就行了。
这种算法实际上没啥用，教科书式算法，你会发现 p 和 q 的位数稍微大一点就因数分解不出了。
如果我没记错的话，p = random_prime(2^(k/2))，这里的 k 到 270 左右就很难解了