██████╗ ███████╗ █████╗ 
    ██╔══██╗██╔════╝██╔══██╗
    ██████╔╝███████╗███████║
    ██╔══██╗╚════██║██╔══██║
    ██║  ██║███████║██║  ██║
    ╚═╝  ╚═╝╚══════╝╚═╝  ╚═╝

About RSA

By Tony Josi

(refer)

RSA Implementation in C++

RSA (Rivest–Shamir–Adleman)) is one of the commonly used asymmetric cryptography algorithm .

Operation

The RSA algorithm involves four steps: key generation, key distribution, encryption, and decryption.

RSA Proof of correctness

Before establishing the proof of correctness, there are two theorems that are essential in undertstanding it:

  1. Fermat's little theorem
  2. Chinese remainder theorem

Fermat's little theorem

Fermat's little theorem states that if p is a prime number, then for any integer a, the number a^p − a is an integer multiple of p.

fermats

Chinese remainder theorem

In number theory, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

If the remainders are same then:

Theorem: If, x = y (mod p) & x = y (mod q) with p and q coprime. Then x = y (mod pq).

Proof: 


    x = y (mod p)
    
    x = y + kp
    x - y = kp
    
    p divides (x - y)
    
    Similarly,
    
    x = y (mod q)
    x = y + kq
    x - y = kq
    
    q divides (x - y)
    
    => kp = kq = x - y
    
    kq = x - y
    
    Muliply with p on both sides,
    
    kpq = (x - y)p
    
    Take mod pq,
    
    0 = (x - y)p mod pq
    
    => 0 = (x - y) mod pq
    
    => x = y mod pq
    
    The same can be arrived from kp = x - y .

RSA Proof

We need to prove that,

rsa --------------- (1)

where m can be any integer, p and q are distinct prime numbers and e and d are positive integers satisfying,

rsa --------------- (2).

According to the Chinese remainder theorem (CRT) equation (1) is valid if,

rsa --------------- (3) and

rsa --------------- (4) are valid.

From equation (2)

rsa --------------- (5)

where u and v are some integers, because ed - 1 is a multiple of the lcm of (p-1, q-1), and lcm of (p-1, q-1) will be u(p - 1) = v(q - 1).

Equation (3) can be written as,

rsa --------------- (6),

which in turn can be written as

rsa --------------- (7),

which can be further reduced using the Fermats Little theorem to,

rsa --------------- (8),

which is valid.

Similarly equation (4) can be written as,

rsa --------------- (9),

which in turn can be written as

rsa --------------- (10),

which can be further reduced using the Fermats Little theorem to,

rsa --------------- (11),

which is also valid.

Hence as both equation (3) and (4) are valid, according to CRT equation 1 is valid. Hence correctness of RSA is proved.

RSA optimizing the decryption algorithm

The textbook RSA decryption algorithm is as follows:

rsa --------------- (12),

where c is the cipher text, d is the private/decryption key, m is the original message. But as c, d, and pq will be very large the decryption process will take long time to execute.

To optimize the calculation of equation 12, by using the CRT we can reduce it to,

rsa --------------- (13)

which can be further reduced to

rsa --------------- (14)

by using the Fermats Little theorem.

RSA Sample Implementation wrt. above discussion

(refer big-int library)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
/** 
 *  @file   rsa.cc
 *  @brief  Soruce file for the RSA library
 *
 *  This file contains the implementation of the RSA library
 *
 *  @author         Tony Josi   https://github.com/tony-josi/rsa
 *  @copyright      Copyright (C) 2021 Tony Josi
 *  @bug            No known bugs.
 */

#include <stdexcept>
#include <stdint.h>

#include "big_int.hpp"

class rsa {

private:
    size_t          bit_size;
    bi::big_int     p;
    bi::big_int     q;
    bi::big_int     p_minus_1;
    bi::big_int     q_minus_1;
    bi::big_int     pq;
    bi::big_int     p_minus_1q_minus_1;
    bi::big_int     e;
    bi::big_int     d;
    bi::big_int     smaller_prime;
    bi::big_int     reduced_d;

public:

    /*  bit_size                                ==> RSA bitsize
        miller_rabin_rounds                     ==> Maximum number of Rabin Miller iterations to be done 
                                                    on the candidate random number to check its a prime    
        max_number_of_threads_for_miller_rabin  ==> Maximum number of threads to use while finding random
                                                    prime numbers. -1 means use maximum possible number of 
                                                    threads [std::thread::hardware_concurrency()].
    */
    rsa(size_t bit_size, int miller_rabin_rounds = 20, int max_number_of_threads_for_miller_rabin = -1);

    int             rsa_encrypt(bi::big_int &plain, bi::big_int &cipher);
    int             rsa_decrypt_textbook_method(bi::big_int &cipher, bi::big_int &decipher);
    int             rsa_decrypt(bi::big_int &cipher, bi::big_int &decipher);
    bi::big_int     get_public_key(); 
    bi::big_int     get_private_key(); 
    bi::big_int     get_modulus();

};

constexpr uint32_t DEFAULT_32_BIT_PUBLIC_KEY = 0x10001;

rsa::rsa(size_t bit_size_arg, int miller_rabin_rounds, int max_number_of_threads_for_miller_rabin) {

    int ret_val = 0;
    
    if (bit_size_arg < 64 || bit_size_arg % 2 != 0) {
        throw std::invalid_argument("Invalid bit size for RSA, must be greater than or equal to 64 and even");
    }
    bit_size_arg /= 2;
    bit_size = bit_size_arg;
    
    /* Create 2 random primes with RSA bitsize bits. */
    int pq_comp_res;
    do {
        ret_val += p.big_int_get_random_unsigned_prime_rabin_miller_threaded(static_cast<int>(bit_size_arg), \
        miller_rabin_rounds, max_number_of_threads_for_miller_rabin);
        ret_val += q.big_int_get_random_unsigned_prime_rabin_miller_threaded(static_cast<int>(bit_size_arg), \
        miller_rabin_rounds, max_number_of_threads_for_miller_rabin);
    } while((pq_comp_res = p.big_int_unsigned_compare(q)) == 0); /* Continue until we have distinct primes p, q. */

    ret_val += p.big_int_multiply(q, pq);

    bi::big_int bi_1;
    ret_val += bi_1.big_int_from_base_type(1, false);

    /* Calculate p-1 and q-1 */
    ret_val += p.big_int_unsigned_sub(bi_1, p_minus_1);
    ret_val += q.big_int_unsigned_sub(bi_1, q_minus_1);
    ret_val += p_minus_1.big_int_multiply(q_minus_1, p_minus_1q_minus_1);

    /* Initialise public key, [uses DEFAULT_32_BIT_PUBLIC_KEY as the default public key, hence the minimum 64 bits key size restrictions.] */
    ret_val += e.big_int_from_base_type(DEFAULT_32_BIT_PUBLIC_KEY, false);

    if (e.big_int_unsigned_compare(p_minus_1q_minus_1) >= 0) {
        throw std::invalid_argument("Error initializing RSA");
    }

    /* Calculate the private key as the modular inverse of the 
       public key in (p-1)(q-1). */
    ret_val += e.big_int_modular_inverse_extended_euclidean_algorithm(p_minus_1q_minus_1, d);

    /* Store the smaller prime among p & q and private key modulo smaller prime
       for faster/efficient decryption. [Fermat's Little theorem]. */
    if (pq_comp_res > 0) {
        smaller_prime = q;
        ret_val += d.big_int_modulus(q_minus_1, reduced_d);
    } else {
        smaller_prime = p;
        ret_val += d.big_int_modulus(p_minus_1, reduced_d);
    }

    /* Throw if error. */
    if (ret_val != 0) {
        throw std::invalid_argument("Error initializing RSA");
    }

}

bi::big_int rsa::get_private_key() {
    return d;
}

bi::big_int rsa::get_public_key() {
    return e;
}

bi::big_int rsa::get_modulus() {
    return pq;
}

int rsa::rsa_encrypt(bi::big_int &plain, bi::big_int &cipher) {

    if (plain.big_int_get_num_of_bits() > bit_size) {
        throw std::invalid_argument("Plain text too long");
    }

    /* c  = m ^ e mod pq = m ^ e mod p = m ^ e mod q     [Chinese remainder theorem].
        refer ==> https://tony-josi.github.io/Articles/RSA_Proof/rsa_proof.html */
    return plain.big_int_fast_modular_exponentiation(e, smaller_prime, cipher);
}

int rsa::rsa_decrypt_textbook_method(bi::big_int &cipher, bi::big_int &decipher) {

    if (cipher.big_int_get_num_of_bits() > bit_size) {
        throw std::invalid_argument("Cipher text too long");
    }

    /* m  = c ^ d mod pq = c ^ d mod p = c ^ d mod q     [Chinese remainder theorem].
        refer ==> https://tony-josi.github.io/Articles/RSA_Proof/rsa_proof.html */
    return cipher.big_int_fast_modular_exponentiation(d, smaller_prime, decipher);
}

int rsa::rsa_decrypt(bi::big_int &cipher, bi::big_int &decipher) {

    if (cipher.big_int_get_num_of_bits() > bit_size) {
        throw std::invalid_argument("Cipher text too long");
    }

    /* Refer ==> RSA optimizing the decryption algorithm
       from https://tony-josi.github.io/Articles/RSA_Proof/rsa_proof.html */

    int ret_val = 0;
    bi::big_int reduced_cipher_text;
    ret_val += cipher.big_int_modulus(smaller_prime, reduced_cipher_text);

    ret_val += reduced_cipher_text.big_int_fast_modular_exponentiation(reduced_d, smaller_prime, decipher);
    return ret_val;

}

Sample Output [RSA 1024]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
PUB: 10001                                                                                              

PRIV: 399FE73E6ABDBF9CBCFD1FA5D30019B3F979DC607ED7104E9222B9947DB168CE48B46C395B7E3F4EC7C39206D1D7010F952C48723EA59EAC79364AF34708068632DE4D7B3C30621EAF58A655928BE6AD697D7E1ED2422B5927F5AC6FEB9C54AE02E800530096DE856835493D71A8F09456D91A76279BC3476A276871902C2BB5                                                                                                  

MOD: 568B6823BA364D9B222F0ABF4D20A3D1A02F9FC145199142A11D9B622F48B81D6F85A0E9C515E194F9F41FF3A1E9262A61AD837DA3A5C19A84EAF21F7DE009496EC9137A638C6F2A871FA630051995FA7B42DF8CE0B4D72D54BC95DD8AEB88E24FC8B74E2ABB9E2082AE37C1CC3EE3023CB385C1513C9B84DC1CCCC9266E03F9                                                                                                   

PLAIN: CAFEBABE                                                                                                         

CIPHER: 7900F505EF6217AAFF1ACB7562BCCA9FB93414C196F9DB0B338F26400F1A014F232BD3531C9D278D382E70D2B6ADB5FD07E23B12246A7087EFF848ECEC829B9B                                                                                                        

DECIPHER: CAFEBABE                                                                                                      

DECIPHER TB: CAFEBABE

Source code HTML generated using hilite.me