89 lines
2.0 KiB
C++
89 lines
2.0 KiB
C++
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include "rsa.h"
|
|
#include "prng.h"
|
|
|
|
/*
|
|
* We will generate the public and private RSA key
|
|
*/
|
|
void generateKeys(unsigned long *e, unsigned long *d, unsigned long *n){
|
|
unsigned long p = prng();
|
|
unsigned long q = prng();
|
|
unsigned long phi = 0;
|
|
|
|
// Check if p and q are different
|
|
if (p == q)
|
|
q ^= q << 2;
|
|
|
|
// Check if p and q are prime numbers
|
|
if (isPrimeNumber(p) != 0)
|
|
prime_number_finder(&p);
|
|
|
|
if (isPrimeNumber(q) != 0)
|
|
prime_number_finder(&q);
|
|
|
|
// Calculate n
|
|
*n = p * q;
|
|
|
|
// We're going to calcule the Euler's totient
|
|
phi = (p - 1)*(q - 1);
|
|
|
|
/* We will calculate e for the public key */
|
|
generatePublicKey(phi, e);
|
|
|
|
/* We will calcuate d for the private key */
|
|
generatePrivateKey(d, phi, e);
|
|
}
|
|
/*
|
|
* This function will identify all the divider of the variable a
|
|
* with the Euclidean algorithm
|
|
*/
|
|
static int gcd(unsigned long a, unsigned long b){
|
|
if (b == 0)
|
|
return a;
|
|
return gcd(b, a%b);
|
|
}
|
|
/*
|
|
* This function will check if te variable e is a prime number
|
|
* is not, we increment the value to 1 and continue until is a prime number
|
|
*/
|
|
static void prime_number_finder(unsigned long *p){
|
|
while(isPrimeNumber(*p) != 0)
|
|
*p += 1;
|
|
}
|
|
/*
|
|
* Check if the number specified is a prime number
|
|
*/
|
|
static int isPrimeNumber(unsigned long x){
|
|
for (int i = 2; i < x; i++){
|
|
if (x % i == 0)
|
|
return 1;
|
|
}
|
|
return 0;
|
|
}
|
|
/*
|
|
* Generate the public key and need to be coprime with phi(n)
|
|
*/
|
|
static unsigned long generatePublicKey(unsigned long phi, unsigned long *e){
|
|
// Generate e
|
|
*e = prng();
|
|
|
|
while ((gcd(phi, *e)) != 1)
|
|
*e += 1;
|
|
|
|
return *e;
|
|
}
|
|
/*
|
|
* We generate tne private key with the modular inverse of phi(n)
|
|
*/
|
|
static unsigned long generatePrivateKey(unsigned long *d, unsigned long phi, unsigned long *e){
|
|
for (int i = 0; i <= phi; i++){
|
|
if ((i * (*e)) % phi == 1){
|
|
*d = i;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return *d;
|
|
}
|