C中生成解密密钥的RSA算法

Question

生成RSA算法解密密钥的公式为ed = 1 mod T，其中T是使用公式(p-1)(q-1)生成的。 p和q是两个不相同的素数。 e 是加密密钥。所以根据公式，如果我想在 C 程序中实现 ed = 1 mod T，代码块应该是

 d = (1%T)/e;

但是，我发现大多数编码网站(coding website)使用d*e = 1 + k * T生成解密密钥。

我不明白他们从哪里得到的 k?

Answer 1

模乘逆可以用extended Euclidean algorithm找到。

这是一个简单的演示实现。加密实现通常需要 extended-precision 算术。

#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);
}

输出：

The multiplicative inverse of 3 modulo 3127 is 2085.

C中生成解密密钥的RSA算法

RSA algorithm for generating decryption key in C

c

for-loop

if-statement

rsa