為 RSA 演算法生成解密密鑰ed = 1 mod T的公式是使用公式生成 T 的地方(p-1)(q-1)。p 和 q 是兩個不相同的素數。e 是加密密鑰。所以按照公式，如果我想ed = 1 mod T在 C 程式中實作代碼塊應該是
d = (1%T)/e;
但是，我發現大多數編碼網站（編碼網站）都d*e = 1 k * T用于生成解密密鑰。
我不明白他們從哪里得到的k？
uj5u.com熱心網友回復：
模乘逆可以用擴展的歐幾里得演算法求得。
這是一個簡單的演示實作。加密實作通常需要擴展精度算術。
#include <stdio.h>
#include <stdlib.h>
// Return the multiplicative inverse of e modulo t.
static int invert(int e, int t)
{
/* We will work with equations in the form:
x = d*e s*t
where e and t are fixed, and x, d, and s change as we go along.
Initially, we know these two equations:
t = 0*e 1*t.
e = 1*e 0*t.
We will use the Euclidean algorithm to reduce the left side to the
greatest common divisor of t and e. If they are relatively prime,
this eventually produces an equation with 1 on the left side, giving
us:
1 = d*e s*t
and then d is the multiplicative inverse of e since d*e is congruent to
1 modulo t.
*/
// Now we start with our first values of x, d, and s:
int x0 = t, d0 = 0, s0 = 1;
int x1 = e, d1 = 1, s1 = 0;
// Then we iteratively reduce the equations.
while (1)
{
/* Find the largest q such that we can subtract q*x1 from x0 without
getting a negative result.
*/
int q = x0/x1;
/* Subtract the equation x1 = d1*e s1*t from the equation
x0 = d0*e s0*t.
*/
int x2 = x0 - q*x1;
int d2 = d0 - q*d1;
int s2 = s0 - q*s1;
/* If we found the inverse, return it.
We could return d2 directly; it is mathematically correct.
However, if it is negative, the positive equivalent might be
preferred, so we return that.
*/
if (x2 == 1)
return d2 < 0 ? d2 t : d2;
if (x2 == 0)
{
fprintf(stderr, "Error, %d is not relatively prime to %d.\n", e, t);
exit(EXIT_FAILURE);
}
/* Slide equation 1 to equation 0 and equation 2 to equation 1 so we
can work on a new one.
*/
x0 = x1; x1 = x2;
d0 = d1; d1 = d2;
s0 = s1; s1 = s2;
}
}
int main(void)
{
int e = 3, t = 3127, d = invert(e, t);
printf("The multiplicative inverse of %d modulo %d is %d.\n", e, t, d);
}
輸出：
3 模 3127 的乘法逆元是 2085。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/452782.html
上一篇：洗掉字串和符號