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

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

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

e 取 7 。<== 这个 7 是怎么计算出来的,是随便取的一小于 φn 的质数,还是是经过什么过程计算出来的?
1982 次点击
所在节点    数学
16 条回复
adoal
186 天前
理论上随便选都可以。但是随便选的作为幂有可能会导致计算量太大。
PEM 建议用 3 ,X.509 建议用 65537 ,PKCS#1 建议用两者之一。
tool2dx
186 天前
数学上无所谓,代码里要用到中国剩余定理,那就只能选特定的 e
rabbbit
185 天前
随便选的
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
185 天前
随便选,条件是 1 < e < λ(n) 并且 e 和 λ(n) 互质
saranz
185 天前
@rabbbit 就这个条件完全搞不明白…… 究竟是要计算出来还是随便找个小于 φn 的质数。


@tool2dx 中国剩余定理?
rabbbit
185 天前
不懂,我以为就是随便选了个质数。
看看这里,也许有帮助。

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
185 天前
谁能讲讲这个 small Hamming weight 的作用?
saranz
185 天前
@rabbbit 哎,不仅数学不会,English 还不懂,咱果然不适合研究这么深奥的学问。

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

𝑝
=
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
185 天前
p = 11;
q = 19;
n = p * q;
phiN = (p - 1) * (q - 1);
e = 7;
GCD[e, phiN]
lDqe4OE6iOEUQNM7
185 天前
验证 7 和 180 互质性:
gcd(7,180)=1
saranz
185 天前
@James2099 所以这个 7 究竟是怎么来的,是随便从小于 phiN 的质数里找一个呐,还是需要计算出来一个质数呐。
marat1ren
185 天前
一般都先从 65537 ,如果 65537 不满足验证条件就从小的质数开始,比如 3 。
pxiphx891
185 天前
可以看一下这一节: 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
185 天前
234ygg
180 天前
e 随便取的,比 n 小 并且与φn 互素就行了。
这种算法实际上没啥用,教科书式算法,你会发现 p 和 q 的位数稍微大一点就因数分解不出了。
如果我没记错的话,p = random_prime(2^(k/2)),这里的 k 到 270 左右就很难解了

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/1042052

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX