RSA - Public Key Cryptosystem

RSA is an Public Key Cryptosystem which is used to transmit messages over the internet, it is based on the principle of factoring large prime numbers. RSA is named after its inventors, Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman, who created it at the Massachusetts Institute of Technology. This type of encryption is called Asymmetric cryptosystem, it is said so because the key for encryption and decryption are different. They are the public key pair and the private key pair. As their name name suggests , public key pair is available to everyone, while the private key pair is for the individuals own use and is kept a secret.

Now let us see the several steps used for encryption/decryption.

1. Key Generation
2. Key Distribution
3. Encryption/Decryption

Let us first define variables that will be repeatedly used:

1. p,q : Two very large primes
2. n : Modulus, n = p*q
3. e : Public key exponent
4. d : Private key exponent
5. M : Unpadded message
6. m : Padded message
7. c : Ciphertext
8. $\varphi(n)$: Euler's totient Function

Key Generation

1. Choose two distinct primes p and q. Both the primes must be chosen randomly and must be similar in magnitude. There should be a significant difference in the values of the primes otherwise it will become vulnerable to Fermat's Factorisation and we will see how and why is it so.
2. Compute $n = p*q$
3. Calculate the value of $\varphi(n) = (p-1)*(q-1)$ in this case.
4. Choose an integer $e$ such that $1 < e < \varphi(n)$ and $gcd(e, \varphi(n)) = 1$. $e$ is often selected small and to be in the form of ${2^2}^i+1$ (where i is a positive integer) also known as Fermat Numbers, because it makes exponentiation more efficient. This makes it vulnerable to some attacks in some situations and we will see how we can prevent them.
5. Compute $d$ as $d = e^{-1} mod \varphi(n)$
6. The pair $(e, n)$ is known as public key and $(d, n)$ is known as private key.

Key Distribution

Let us use an example to understand this,Suppose Alice wishes to send Bob a secret message, but the message will fall into the wrong hands if sent unsecured. Both Alice and Bob have a variety of padlocks, but they don't own the same ones, meaning that their keys cannot open the other's locks. In cryptographical terms, 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, but not necessarily secret, route. Alice's private key $(d)$ is never distributed. Reliable channel → The keys are sent without any alterations in their values.

Encryption

After Bob receives Alice's public key, he does the following operations: 1. Convert the message into integer form

1. Computes ciphertext $c = m^e \bmod{n}$

2. Now you have the ciphertext c ready to transmit using a reliable channel

Decryption

After receiving the ciphertext c from Bob, Alice computes the following to get back the message:

1. Computes $m = c^d \bmod{n}$ . How this provides us the message we will see in the next section.

2. Convert the integer plaintext to the normal form.

Proof of decryption using Euler's Theorem

Read about Euler's Theorem here. Now we have:

$c = M^e \bmod n$

$c^d \bmod n = M^{ed} \bmod n$

Since we have from Euler's theorem that: $a^{\varphi(n)} \equiv 1 \bmod{n}$,

We also know that, $ed \equiv 1 \bmod{\varphi (n)}$

We can convert this equation into: $ed = 1 + h{\varphi (n)}$

Using this we can now write

${\displaystyle m^{ed}=m^{1 + h\varphi (n)} = m(m^{\varphi (n)})^{h}\equiv m(1)^{h}\equiv m{\bmod {n}}}$

PyCrypto

PyCrypto is a python module which will help you to implement most of the encryptions including RSA. Now the first step is to install the module, you can do this by the

pip install pycrypto

Now let us see how to import these modules in python

>>> from Crypto.PublicKey import RSA
>>> from Crypto.Util.number import *

While doing RSA, the basic things you would have is the Modulus n and the public key exponent e. Usually n and e are given in numerical form but sometimes, they may also given in the form of key files, these file end with the extension dot pem (.pem) or dot der (.der), but its mostly .pem

Now for converting this file into numerical form with which we can operate can be done by this module first go to the directory where the file is present.

>>> f=open('PublicKey.pem').read()
>>> n=RSA.importKey(f).n
>>> e=RSA.importKey(f).e

Now the next thing that would be useful for you is inverse, Lets consider that you have found p and q from which you calculated the euler totient function ${\varphi (n)}$ . Now you need to find the private key exponent d by finding the modular inverse of e to ${\varphi (n)}$ , this can be accomplished by the function named inverse in the PyCrypto Module.

>>> n = p*q
>>> phin = (p-1)*(q-1)
>>> d = inverse(e,phin)
>>> plaintext = pow(ciphertext,d,n)

Now another set of useful functions are long_to_bytes and bytes_to_long . Usually you have the message in numerical form, to convert this into readable ascii form, you can use the function named long_to_bytes and to convert a ascii message into numerical form is bytes_to_long .

>>> bytes_to_long('RSA is cool')
99525075000367028712206188L
>>> long_to_bytes(99525075000367028712206188L)
'RSA is cool'

Now another module which will help you with the math is gmpy2. But that is not quite important.