Mathematics behind RSA private and public keys

Public and private keys are used in asymmetric cryptographic systems to exchange data securely with out sharing a common secret key. Even though the mathematical concept behind each asymmetric cryptographic algorithm differs they all are based on one concept in which two different keys are used in encryption and decryption process. Out of these keys, encryption key is freely distributed (public key) while the other key (decryption key) remains a secret. Out of many asymmetric cryptographic algorithms we will have a look at the RSA algorithm.

In RSA, Private and public key pares are basically two prime numbers which satisfy certain mathematical conditions. In real life situations these two prime numbers need to be large enough to be practically used in a cryptographic system

RSA concept:

The basic steps in deriving key pairs are listed below.

1. Select/generate 2 prime numbers

Get two prime numbers p and q.

1. Calculate the modulus

Multiply to get number n

Modulus = n = p* q

2. determine φ(n)

Lets calculate φ(n) where φ(n) = (p-1)(q-1)

By applying Euler’s totient function we calculate φ(n), which is the number of positive integers less than n that are coprime with n .

3. Calculate the Encryption key(public exponent):

Let’s choose the encryption key (public key) e where e and φ (n) are coprime. Which means the greatest common denominator (gcd) of e and φ (n) is 1. I.e. the largest positive integer that divides both numbers without remainder is 1.

i.e: gcd(e , φ (n)) = 1

In here e should be greater than 1 and less than φ(n)

4. Calculate the decryption key (secret exponent):

Decryption key (Private key) d is derived by calculating the inverse of

e mod (φ(n)) using the extended Euclidian algorithm

d = e^-1 (mod (φ(n)))

In summery:

Public key is (n, e) where

gcd(e , φ(n)) = 1

and

φ(n) = (p-1)(q-1)

Private key is (n, d) where

d = e^-1 (mod (φ(n)))

Practical example:

How this algorithm is used to generate a private and public key pare is shown below by using two small prime numbers.

1. Select 2 prime numbers

Let’s select 2 prime numbers p and q where

p = 31

q = 17

2. Calculate the modulus

Modulus = n = 31 * 17 = 527

3. determine φ(n)

φ(n) = (p-1)*(q-1)

= (31-1)*(17-1)

=30 * 16

φ(n) = 480

4. Calculate the Encryption key:

Lets choose a value for e such that gcd(e , φ (n)) = 1

gcd(e , φ (n)) = 1

gcd(e , 480) = 1

Let’s choose e as 7

Lets ensure that gcd(7 , 480) is really 1

480 = 2⁵ x 3 x 5 x 1

7 = 7 x 1

Which assure us that gcd(7 , 480) = 1

5. Calculate the decryption key:

d = e^-1 (mod(φ (n)))

d = 7^-1 (mod480)

Let’s use a table to calculate the inverse of 7mod480 using extended Euclidean algorithm.

X_i = (X_i-2 - [X_i-1*q_i-2]) (mod b)

Where,

X₀ = 0 and X1 = 1

Step 0:	480 = 68(7) + 4	X0 = 0
Step 1:	7 = 1(4) + 3	X1 = 1
Step 2:	4 = 1(3) + 1	X2 = (0 – (1*68))mod480 = 412
Step 3:	3 = 3(1) + 0	X3 = (1 – (412*1))mod480 = 69
		X4 = (412 – (69*1))mod480 = 343

Thus d = X₄ = 343

Thus according to our chosen prime numbers p and q,

Public key e is (527, 7) and private key d is (527, 343)

In practise, to make modular exponentiation operation faster, e is chosen to be one of 3, 17 or 65537 values. This is to simplify the calculation of encryption, c = m^e mod n where c is cipher text and m is the unencrypted message.

The bit lengths of p and q should be equivalent to the half of the bit length of n where Modulus = n = p* q