C RSA密钥生成程序

Question

我正在努力磨练我的C技能以及更好地理解RSA，所以我自己尝试制作自己的生成器。我已经生成了两个底数，p和q，计算出0 = (p-1) * (q-1)的值。这些工作正常。接下来的步骤是我遇到问题的地方。我很接近，但我似乎找不到正确的方法来计算1 mod r值的加密和解密因子。任何帮助生成这将是了不起的。(或者只是自己写代码，我可以从中学习)另外，如果有任何其他问题，请告诉我!

下面是我的代码:

#include<stdio.h>
#include<time.h>
#include"../hdr/test.h"    //fake header just to satisfy my makefile
//Receives: number that was generated in main
//Returns: 1 for false, 0 for true
//Purpose: checks if the numbers is prime and returns 1 or 0
int isPrime(int number) 
{
    if (number <= 1) 
        return 0;
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0) 
            return 0;
    }
    return 1;
}
/*Receives: an integer ((p-1) * (q-1))
  Returns: integer (e)
  Purpose: Generates the relatively prime number to ((p-1) * (q-1))*/
int gen_E(int o)
{
    puts("Generating E...");
    int e;
    do {e = rand() % o;} while (GCD(e, o) != 1);
    return e;
}
/*Receives: integer E and O from the main
  Returns: newly calculated integer D
  Purpose: Generates D for the private key*/
int gen_D(int e, int o)
{
puts("Generating D...");
int e = a;
int o = b;
int phin, d;
for (phin = 1; phin < o; phin ++)
    for (d = 1; d < 998001; d ++)
        if ((e * d) == (o * phin) + 1) return d;
}
/*Receives: integer E and O from main
  Returns: greatest common divisor's remainder
  Purpose: Calculate if the two numbers share a divisor.*/    
int GCD(int e, int o)
{
    int c;
    while (e != 0) {
        c = e; e = o%e; o = c;
    }
    return o;
}
int main()
{
    puts("Generating Prime P...");
    srand(time(NULL));
    int p = rand() % 1000;
    while (isPrime(p) != 1) {
        p = rand() % 1000;
    }
    puts("Generating Prime Q...");
    int q = rand() % 1000;
    while (isPrime(q) != 1) {
        q = rand() % 1000;
    }
    int n = p * q;
    int o = (p - 1) * (q - 1);
    int e = gen_E(o);
    int d = gen_D(e, o);
    printf("p: %dnq: %dnn: %dno: %dne: %dnd: %dn", p, q, n, o, e, d);
    printf("KU = {%d, %d}n", e, n);
    printf("KR = {%d, %d}n", d, n);
}

Answer 1

您将需要一个函数来计算两个数的GCD(最大公约数)。之后，选择随机e，使GCD(e,o) == 1。

当然，在实践中可能比这更复杂，但对于家庭作业来说，这是可以的。