C RSA密钥生成程序

Question

我正在努力磨练自己的C技能以及更好地理解RSA，所以我自己尝试制作自己的发电机。我已经生成了两个基本素数p和q，计算出值o =（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: %d\nq: %d\nn: %d\no: %d\ne: %d\nd: %d\n", 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。

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