RSA Algorithm(Encryption and Decryption) implementation in C

RSA algorithm is mainly a public key encryption technique used widely in network communication like in Virtual Private Networks (VPNs) for securing sensitive data, particularly when being sent over an insecure network such as the Internet.

RSA algorithm was first described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology.

In cryptosystem, system needs to make sure that nobody, except the intended recipient, deciphers the message, the people involved had to strive to keep the key secret. In public key encryption technique, a key is split into two keys and they are called as public and private keys. Public key is advertised to the world and private key is kept secret. It is not possible to generate private key using the public key. So, someone who knows the public key cannot decrypt a message after it has been encrypted using the public key.


Working with a public-key encryption system has mainly three steps:

1.Key generation:

Whoever wants to receive secret messages creates a public key (which is published) and a private key (kept secret). The keys are generated in a way that conceals their construction and makes it 'difficult' to find the private key by only knowing the public key.The keys for the RSA algorithm are generated as follows
1) Pick two large prime numbers p and q, p != q;
2) Calculate n = p × q<the product n is used as modulus for both public and private key>;
3) Calculate ø (n) = (p − 1)(q − 1) <where ø is Euler’s Totient function>;
4) Pick e, so that gcd(e, ø (n)) = 1, 1 < e <  ø (n) <where e is public key>;
5) Calculate d, so that d · e mod ø (n) = 1, i.e., d is the multiplicative inverse of e in mod  ø (n) <where d is private key>;
6) Get public key as KU = {e, n};
7) Get private key as KR = {d, n}.

2.Encryption:

A secret message to any person can be encrypted by his/her public key (that could be officially listed like phone numbers).
For plaintext block P < n, its ciphertext C = P^e (mod n).

3.Decryption:

Only the person being addressed can easily decrypt the secret message using the private key.
For ciphertext block C, its plaintext is P = C^d (mod n).

Example

Key Generation:
1. Select primes: p=17 & q=11
2. Compute n = p*q =17×11=187
3. Compute ø(n)=(p–1).(q-1) =16×10=160
4. Select e: gcd(e,160) =1; choose e=7
5. Determine d: de=1 mod 160 and d < 160 Value is d=23 since 23×7=161= 10×160+1
6. Publish public key KU= {7,187}
7. Keep secret private key KR= {23,17,11}
8. sample RSA encryption/decryption is:
9. given message M = 88 (nb. 88<187)

Encryption:
10. C = 887 mod 187 = 11

Decryption:
11. M = 1123 mod 187 = 88

Implementing RSA algorithm in C Program

 The given program will Encrypt and Decrypt a message using RSA Algorithm.



Output will be