e * d ≡ 1 (mod (p-1) * (q-1))
时间: 2024-05-24 12:15:34 浏览: 18
这是一个RSA加密算法中的公式,其中e和d是加密密钥和解密密钥,p和q是两个大质数。这个公式是用来计算d的值的,使得e和d满足条件:e * d ≡ 1 (mod (p-1) * (q-1))。这个条件的意思是,e和d必须是模(p-1)*(q-1)的乘法逆元素,这样才能保证加密和解密的正确性。在RSA加密算法中,首先选择两个大质数p和q,然后计算它们的乘积n=p*q,再选择一个整数e作为加密密钥,使得e和(p-1)*(q-1)互质。然后根据上述公式计算出d作为解密密钥。最后,将n和e公开,而将d保密,这样就可以用公开的n和e进行加密,用保密的d进行解密。
相关问题
素数p = 7,q = 17. n = p*q = 119 φ(n) = (p - 1) * (q - 1) = 96 e = 11 e * d ≡ 1 mod φ(n) 计算d
根据公式:e * d ≡ 1 mod φ(n),可以转化为 e * d = 1 + k * φ(n)(k为任意整数)。
我们先求出 k 的值:
e * d ≡ 1 mod φ(n)
11 * d ≡ 1 mod 96
可以通过扩展欧几里得算法求出 11 和 96 的最大公约数,以及对应的 Bézout 系数 x 和 y:
gcd(11, 96) = 1,x = 35,y = -4
因为 x 和 y 中有负数,所以我们将它们转换成对应的正数:
x = x + k * φ(n),y = y - k * e
35 + 96k > 0,-4 - 11k > 0,解得 0 ≤ k < 4,因此 k 可以取 0、1、2 或 3。
当 k = 0 时,x = 35,y = -4,此时 e * d = 1 + k * φ(n) = 1,d = 1 / e = 1 / 11。
当 k = 1 时,x = 131,y = -15,此时 e * d = 1 + k * φ(n) = 97,d = 97 / 11 = 8 余 9。
当 k = 2 时,x = 227,y = -26,此时 e * d = 1 + k * φ(n) = 193,d = 193 / 11 = 17 余 6。
当 k = 3 时,x = 323,y = -37,此时 e * d = 1 + k * φ(n) = 289,d = 289 / 11 = 26 余 3。
因此,d 的取值可能是 1、8、6 或 3,其中 1 是不合适的,因为它不满足 d 与 e 互质的条件。所以,在这个例子中,可以选择 d = 8 或 d = 6。
已知p=199 q=397 e=179 计算d
首先,我们需要计算n = p * q = 79,003。然后,我们可以使用扩展欧几里得算法来计算d,满足 e*d ≡ 1 (mod (p-1)*(q-1))。
首先,计算φ(n) = (p-1)*(q-1) = 78,808。
然后,我们需要找到整数x和y,满足 e*x + φ(n)*y = 1。通过扩展欧几里得算法,我们可以得到:
φ(n) = 78,808
e = 179
r1 = φ(n) % e = 223
r2 = e % r1 = 44
t1 = φ(n) // e = 440
t2 = e // r2 = 4
r3 = t1 - t2 * r1 = 429
r4 = r1 - r2 * r3 = 19
t3 = t2 - t1 * r2 = -173
t4 = r2 - r3 * r4 = 5
r5 = r3 - r4 * t3 = 6
r6 = r4 - r5 * t4 = -26
t5 = t3 - t4 * r5 = 878
t6 = t4 - t5 * r6 = -437
因为我们需要d是正整数,所以我们可以加上φ(n)的倍数,直到得到一个正整数d:
d = t6 + k * φ(n) = -437 + k * 78,808
其中,k是一个任意整数。
我们可以选择k = 1,这样d = 78,371。因此,d = 78,371。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)