RSA (cryptosystem)

RSA is one of the first public-key (asymmetric) cryptosystems and is widely used for secure data transmission. RSA stands for Rivest-Shamir-Adleman, initial letters of the surnames of its creators. This asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the “factoring problem”. Here’s how key generation works: 1. Choose two distinct prime numbers, p, and q. 2. Compute n = p * q. n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length. 3. Compute λ(n) = least_common_multiple(p − 1, q − 1). This value is private. 4. Choose an integer e such that 1 < e < λ(n), e and λ(n) are coprime. 5. Determine d from d * e ≡ 1 (mod λ(n)).

e is released as the public key exponent.

d is kept as the private key exponent.

Key pair
public key: (e, n)
private key: (d, n)

Currently, the standard sizes for RSA keys are as follows:
512 bits – Low-strength key
1024 bits – Medium-strength key
2048 bits – High-strength key
4096 bits – Very high-strength key

Suppose that Bob wants to send information to Alice. If they decide to use RSA, Bob must know Alice’s public key to encrypt the message and Alice must use her private key to decrypt the message. To enable Bob to send his encrypted messages, Alice transmits her public key (n, e) to Bob via a reliable (not necessarily secret) channel. Alice’s private key (d) is never distributed.

Let’s try to generate very simple key pair: 1. p = 61 and q = 53 2. n = 61 * 53 = 3233 3. λ(n) = lcm(p-1, q-1) = lcm(60, 52) = 780 4. e = 17 (1 < e < λ(n), e and λ(n) are coprime) 5. d = 413 (d * e mod λ(n) = 1) public key: (n = 3233, e = 17) private key: (n = 3233, d = 413) We generated the key pair. We need the public key (n, e) to encrypt plaintext. Let’s assign plaintext to m and the ciphertext to c; then ciphertext will be: c = m ^ e mod n For example, if our plaintext m = 65, then: c(m) = 65 ^ 17 mod 3233 = 2790 To decrypt the ciphertext with the private key (n, d), we should use this: m(c) = c ^ d mod n = 2790 ^ 413 mod 3233 = 65

The following code will generate a simple key pair, encrypt the plaintext, and decrypt.

#include <iostream>
#include <ctime>
#include <cstdlib>

typedef  unsigned int  uint;

constexpr uint gCD(uint a, uint b)
{
    if (b == 0)
        return a;
    else
        return gCD(b, a%b);
}


const uint extEuclid(uint  x, uint  y, int * d, int * k)
{
    uint  sa = 1, ta = 0, sb = 0, tb = 1, q, tempA, tempB;
    int  a = x, b = y;
    while (b > 0)
    {
        q = a / b;
        tempA = a; a = b; b = tempA - q * b;
        tempA = sa; tempB = ta; sa = sb; ta = tb;
        sb = tempA - q * sb; tb = tempB - q * tb;
    }
    *d = sa; *k = ta;
    return a;
}

//function counts (base^exp)%rem in O(ld(n)) time
uint fastExp(int base, int exp, uint rem)
{
    while (base < 0)
        base += rem;
    //if the exponent is negative we should set the
    //modular multiplicative inverse of base to base and exp = -exp
    //e.g. we have to count 2^(-123)%3=(2^-1%3)^123%3=-1^123%3
    //because -1 is modular multiplicative inverse of 2 with 2*(-1)%3=1
    if (exp < 0)
    {
        int temp = 0;
        extEuclid(base, rem, &base, &temp);
        return fastExp(base, -1 * exp, rem);
    }
    uint res = 1;
    base = base % rem;
    while (exp > 0)
    {
        if (exp&1)
            res = (res*base) % rem;
        exp = exp >> 1; 
        base = (base*base) % rem;
    }
    return res;
}

 const uint prepareKey(int& e, int&d)
 {
     using namespace std;
     //First we have to choose two different prime numbers p and q
     uint p = 67, q = 193;
     //now we count N = p*q
     uint rem = p * q;
     //now we count euler = (p-1)(q-1)
     uint euler = (p - 1)*(q - 1);     
     //after that we count the public key e,
     //with 1<e<euler and GCD(e,euler) = 1
     uint pubKey;
     do {
         pubKey = rand() % (euler - 1) + 1;
     } while (gCD(pubKey, euler) != 1);
     e = pubKey;
     //now we count private key d, with (e*d) % euler = 1,
     //using extended euclidian algorithm
     int privKey, k;
     extEuclid(pubKey, euler, &privKey, &k);
     d = privKey;
     return rem;
 }

 const uint encrypt(uint mes, int pub_key, uint rem)
 {
     return fastExp(mes, pub_key, rem);
 }

 const uint decrypt(uint mes, int priv_key, uint rem)
 {
     return fastExp(mes, priv_key, rem);
 }


int main()
{
    srand(time(NULL));    
    int pubKey = 0, privKey = pubKey, rem;
    rem = prepareKey(pubKey, privKey);
    uint mes = rand() % rem, encMes = encrypt(mes, pubKey, rem);
    std::cout << "The message is equal to: " << mes << std::endl;
    std::cout <<"The message after encryption with public key is equal to: "<< encMes << std::endl;
    std::cout << "The message after decryption with private key is equal to: ";
    std::cout << decrypt(encMes, privKey, rem) << std::endl;
    return 0;
}