RSA, part 1: generating private and public keys

Hi there. It's first part about RSA algorithm with using c++, I'll provide information and code about generating public and private keys. Let's get started. RSA is public key cryptosystem which widely used for transfering data. It was descovered in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman. RSA creates public key with using two large prime numbers and auxiliary value. The idea of all public key cryptosystems is simple:

If we know x, then to calculate f(x) must be easy, if we know f(x), then calculate x must be really hard(no effecient way to do this). Similar property has modular exponentiation.

We've got c, m, e, n and d values. Let's take a look on first expression. We've got c, m, e and n values: m stands for text which we want to encrypt, c stands for decrtypted text. It's obvious that c depends on values e and n. So, (e, n) pair is public key.

Take a look on second expression. We've got new value d: d is value with using wich we got m(decrypted text). So, (e, d) pair is private key.

Prime values kept in secret. Any message can be encrypted with using public key, but can be decrypted by someone who knows private key. For now is no efficient way to decrypte message without knowing a private key.

Operation

RSA algorithm involves 4 steps: generation, distribution, encryption and decryption.

Key generation

Here it's necessary to make a reservation about my implementation. It's quite obvious that numbers better be big, it's popular to use 1024 bit length, for this need to use libraries for big numbers (such as GMP for c++). I don't use it. Later maybe I'll post article about RSA code with using GMP library.

Now let's be more specific about generating values and all details.

1. Choose 2 distinct prime numbers p and q in a random way. What we do is just generate 2 random numbers and chech if they're prime, if not - generate again. if you got any questions about is_prime function then visit this topic on StackOverFlow.

// should be compiled with c++17
#include <ctime>
#include <iostream>

#define u unsigned

// primarity test for numbers
bool is_prime(u int num){
    if (num != 2){
        if (num < 2 || num % 2 == 0) 
            return false; 
        for (int i = 3; i * i <= num; i += 2){ 
            if (num % i == 0) 
                return false; 
        }
    }
    return true; 
} 

std::pair<int, int> generate_prime_numbers(u int low_lim, u int upper_lim){ 
    // u means unsigned, I defined this above
    u int first_num = 0; 
    u int second_num = 0; 
    do { 
        first_num = low_lim + (rand() % upper_lim); 
        second_num = low_lim + (rand() % upper_lim);  
    } while (!is_prime(first_num) || !is_prime(second_num)); 
     
    return std::make_pair(first_num, second_num); 
} 

2. Compute n = p * q

// I use long long type because n probably is a big number 
long long n = p * q;

3. Calculate Euler's phi function(Euler's totient function). Function counts positive integers that a relatively prime to given n. Other words, this function counts numbers with gcd(great common devider, НОД рус.) 1 with n.

Why n has beed choosen exactly like this. We can get private d value with public e value. With p and q values is not a problem to calculate phi function, but in public key is n value. So, if we want to calculate phi(n) we need to solve factorization problem(there is no effecient way to do this).

4. Find e value: e value have to comply these conditions.

u int find_coprime(u int phi_res){ 
    u int e = 2; 
    while (e < phi_res){ 
        u int gcd_res = gcd(e, phi_res); 
        if (gcd_res == 1) 
            return e; 
        e++; 
    }     
    return e; 
} 

5. Find d value

u int calculate_d(u int phi_res, u int e){ 
    u int k = 1; 
    u int d = 0; 
     
    while ((((k * phi_res) + 1) % e) != 0) 
        k++; 
    d = ((k * phi_res) + 1) / e; 
     
    return d; 
} 

Main function

int main(){ 
    srand(time(0)); 
    // from 1k to 10k 
    auto [p, q] = generate_prime_numbers(1000, 10000); 
    long long n = p * q; 
    u int phi_res = phi(p, q); 
    u int e = find_coprime(phi_res); 
    u int d = calculate_d(phi_res, e); 
     
    std::cout << "(" << e << ", " << n << ") — public key" << std::endl; 
    std::cout << "(" << e << ", " << d << ") — private key"; 
    /* 
    (e, n) pair stands for public key, could be published anywhere 
    (e, d) pair stands for private key and keeps in secret 
    */ 
     
    return 0; 
}

Next article'll defenitely be 2 part about RSA.

Full code on GitHub: https://github.com/rastr-0/teletype_source_files/tree/main/rsa_generating_keys

See ya soon

@rastr