1
adoal 170 天前
理论上随便选都可以。但是随便选的作为幂有可能会导致计算量太大。
PEM 建议用 3 ,X.509 建议用 65537 ,PKCS#1 建议用两者之一。 |
2
tool2dx 170 天前 via Android
数学上无所谓,代码里要用到中国剩余定理,那就只能选特定的 e
|
3
rabbbit 170 天前
随便选的
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] |
4
rabbbit 170 天前
随便选,条件是 1 < e < λ(n) 并且 e 和 λ(n) 互质
|
6
rabbbit 170 天前
不懂,我以为就是随便选了个质数。
看看这里,也许有帮助。 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. |
7
rabbbit 170 天前
谁能讲讲这个 small Hamming weight 的作用?
|
8
saranz OP |
9
lDqe4OE6iOEUQNM7 170 天前
,
𝑝 = 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 |
10
lDqe4OE6iOEUQNM7 170 天前
p = 11;
q = 19; n = p * q; phiN = (p - 1) * (q - 1); e = 7; GCD[e, phiN] |
11
lDqe4OE6iOEUQNM7 170 天前
验证 7 和 180 互质性:
gcd(7,180)=1 |
13
marat1ren 170 天前 via iPhone
一般都先从 65537 ,如果 65537 不满足验证条件就从小的质数开始,比如 3 。
|
14
pxiphx891 170 天前
可以看一下这一节: 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 。」 |
15
jedrek 170 天前 via Android
|
16
234ygg 164 天前 1
e 随便取的,比 n 小 并且与φn 互素就行了。
这种算法实际上没啥用,教科书式算法,你会发现 p 和 q 的位数稍微大一点就因数分解不出了。 如果我没记错的话,p = random_prime(2^(k/2)),这里的 k 到 270 左右就很难解了 |