RSA algorithm in C

The RSA algorithm was invented by Ronald L. Rivest, Adi Shamir, and Leonard Adleman in 1977 and released into the public domain on September 6, 2000.

This an example of how a public and private key is used in the encryption process. (Photo credit: Wikipedia)

Public-key systems–or asymmetric cryptography–use two different keys with a mathematical relationship to each other. Their protection relies on the premise that knowing one key will not help you figure out the other. The RSA algorithm uses the fact that it’s easy to multiply two large prime numbers together and get a product. But you can’t take that product and reasonably guess the two original numbers, or guess one of the original primes if only the other is known. The public key and private keys are carefully generated using the RSA algorithm; they can be used to encrypt information or sign it.

 Key generation
1) Pick two large prime numbers p and q, p != q;
2) Calculate n = p × q;
3) Calculate ø (n) = (p − 1)(q − 1);
4) Pick e, so that gcd(e, ø (n)) = 1, 1 < e <  ø (n);
5) Calculate d, so that d · e mod ø (n) = 1, i.e., d is the multiplicative inverse of e in mod  ø (n);
6) Get public key as KU = {e, n};
7) Get private key as KR = {d, n}.

Encryption
For plaintext block P < n, its ciphertext C = P^e (mod n).
Decryption
For ciphertext block C, its plaintext is P = C^d (mod n).

/* C program for the Implementation Of RSA Algorithm Encrypt the text data and Decrypt the same */
#include<stdio.h>
#include<conio.h>
int phi,M,n,e,d,C,FLAG;
int check()
{
int i;
for(i=3;e%i==0 && phi%i==0;i+2)
{
FLAG = 1;
return;
}
FLAG = 0;
}
void encrypt()
{
int i;
C = 1;
for(i=0;i< e;i++)
C=C*M%n;
C = C%n;
printf(“\n\tEncrypted keyword : %d”,C);
}
void decrypt()
{
int i;
M = 1;
for(i=0;i< d;i++)
M=M*C%n;
M = M%n;
printf(“\n\tDecrypted keyword : %d”,M);
}
void main()
{
int p,q,s;
clrscr();
printf(“Enter Two Relatively Prime Numbers\t: “);
scanf(“%d%d”,&p,&q);
n = p*q;
phi=(p-1)*(q-1);
printf(“\n\tF(n) phi value\t= %d”,phi);
do
{
printf(“\n\nEnter e which is prime number and less than phi \t: “,n);
scanf(“%d”,&e);
check();
}while(FLAG==1);
d = 1;
do
{
s = (d*e)%phi;
d++;
}while(s!=1);
d = d-1;
printf(“\n\tPublic Key\t: {%d,%d}”,e,n);
printf(“\n\tPrivate Key\t: {%d,%d}”,d,n);
printf(“\n\nEnter The Plain Text\t: “);
scanf(“%d”,&M);
encrypt();
printf(“\n\nEnter the Cipher text\t: “);
scanf(“%d”,&C);
decrypt();
getch();
}

Overview

Key Generation Generate two large prime numbers, p and q Let n = pq Let m = (p-1)(q-1) Choose a small number e, coprime to m Find d, such that de % m = 1 Publish e and n as the public key. Keep d and n as the secret key.	Encryption C = Pe % n
	Decryption P = Cd % n
	x % y means the remainder of x divided by y

The reasons why this algorithm works are discussed in the mathematics section. Its security comes from the computational difficulty of factoring large numbers. To be secure, very large numbers must be used for p and q - 100 decimal digits at the very least.
I'll now go through a simple worked example.

Key Generation

1) Generate two large prime numbers, p and q

To make the example easy to follow I am going to use small numbers, but this is not secure. To find random primes, we start at a random number and go up ascending odd numbers until we find a prime. Lets have:

p = 7
q = 19

2) Let n = pq

n = 7 * 19
  = 133

3) Let m = (p - 1)(q - 1)

m = (7 - 1)(19 - 1)
  = 6 * 18
  = 108

4) Choose a small number, e coprime to m

e coprime to m, means that the largest number that can exactly divide both e and m (their greatest common divisor, or GCD) is 1. Euclid's algorithm is used to find the GCD of two numbers, but the details are omitted here.

e = 2 => GCD(e, 108) = 2 (no)
e = 3 => GCD(e, 108) = 3 (no)
e = 4 => GCD(e, 108) = 4 (no)
e = 5 => GCD(e, 108) = 1 (yes!)

5) Find d, such that de % m = 1

This is equivalent to finding d which satisfies de = 1 + nm where n is any integer. We can rewrite this as d = (1 + nm) / e. Now we work through values of n until an integer solution for e is found:

n = 0 => d = 1 / 5 (no)
n = 1 => d = 109 / 5 (no)
n = 2 => d = 217 / 5 (no)
n = 3 => d = 325 / 5
           = 65 (yes!)

To do this with big numbers, a more sophisticated algorithm called extended Euclid must be used.

Public Key n = 133 e = 5

Secret Key n = 133 d = 65

Communication

Encryption

The message must be a number less than the smaller of p and q. However, at this point we don't know p or q, so in practice a lower bound on p and q must be published. This can be somewhat below their true value and so isn't a major security concern. For this example, lets use the message "6".

C = P^e % n
  = 6⁵ % 133
  = 7776 % 133
  = 62

Decryption

This works very much like encryption, but involves a larger exponentiation, which is broken down into several steps.

P = C^d % n
  = 62⁶⁵ % 133
  = 62 * 62⁶⁴ % 133
  = 62 * (62²)³² % 133
  = 62 * 3844³² % 133
  = 62 * (3844 % 133)³² % 133
  = 62 * 120³² % 133

We now repeat the sequence of operations that reduced 62⁶⁵ to 120³² to reduce the exponent down to 1.

  = 62 * 36¹⁶ % 133
  = 62 * 99⁸ % 133
  = 62 * 92⁴ % 133
  = 62 * 85² % 133
  = 62 * 43 % 133
  = 2666 % 133
  = 6

And that matches the plaintext we put in at the beginning, so the algorithm worked!
at another example 
 RSA Encryption

• Public Key Encryption
  
• A Worked Example of RSA Encryption

PUBLIC KEY ENCRYPTION

• RSA encryption is the modern standard for sending secure information.
• RSA is based on the modular arithmetic of primes.
In the mid 1970s, three MIT researchers, Ron Rivest, Adi Shamir, and Leonard Adleman, discovered a new method of encryption that relies on the properties of primes and modular arithmetic. This system, RSA (initials of the discoverers), has remained secure for over 20 years, although countless people have attempted to breach it. In 1982, Rivest, Shamir, and Adleman founded RSA Security, a company that would go on to provide the standard in data encryption used worldwide on the Internet.
RSA encryption relies not on one key, as in our previous Caesar cipher examples, but on two. One of these keys is made public, and the other is kept private. If you wish someone to send you an encrypted message, you simply tell them your public key, and they can then encrypt their message so that only you can read it. They do not need to know your private key for this system to work. Here is a brief, and somewhat simplified, description of the process.
As we have seen throughout this unit, multiplying two primes together is easy to do, but factoring a large number into primes is a nightmarish trial-and-error scenario if the number has only two large primes as factors. This property of primes provides the basis of the RSA encryption scheme.
In general, to encrypt a message using the RSA method, we choose two large primes, p and q, and multiply them to produce a number N. The number N will be the modulus of our system and will be made public. This is fine; because p and q are both large and prime, their product, N, will be practically impossible to factor and can be confidently made public knowledge. We will now use p and q to make our public and private keys.
To make our keys, we first subtract 1 from both p and q and then multiply the results: (p-1)(q-1) = T. At this point, we will choose our public key, which can be any number less than T that shares no factors with it. This public key is what we referred to in the previous section as e. To construct our private key, we need to identify a number, d, such that when it is multiplied by e, the public key, it is congruent to 1 mod T. In other words, the following congruence must hold:
d × e ≡ 1 mod T
Now, if we want someone to send us a message that only we can read, we tell them the modulus, N, and the encryption key, e. They then convert their message from letters to a series of number strings, or "words," just as we have been doing in previous sections of this text. We must be careful that none of the words are larger than the modulus, which would result in some words being indecipherable. Let's say this word is the number M. The encrypter raises each word to the "e^th" power, mod N. This new word, let's call it C, is now encrypted and can be sent to us. In mathematical terms, we have:
C ≡ Me mod N
We receive the coded number C. To decrypt it, all we have to do is raise it to the "d^th" power, mod N. This works because C^d ≡ (M^e)^d mod N, and Rivest, Shamir, and Adleman were able to show that M^ed ≡ M mod N. Recall that we chose e and d such that, d times e triple equal 1 mod T (d × e = 1 mod T), so there is some mathematics hidden in this statement! Thus, our private key, known
only to us, undoes the encryption of the public key. Anyone who knows e and N can send us a message that only we, because we know d, can decrypt. To get a better idea, let's look at an example.

A WORKED EXAMPLE OF RSA ENCRYPTION

Real RSA encryption uses very large numbers, which would be very difficult— not to mention less than illuminating—to use here. In this example, we'll use smaller numbers that are not at all realistic but that illustrate how the method works.
First, let's choose the primes that form the foundation of our scheme, p and q:
p = 17 and q = 19
By multiplying p and q, we get our modulus, N:
N = 17 × 19 = 323
Now, we find T by subtracting 1 from both p and q and multiplying:
T = (p-1) × (q-1) = (16) × (18) = 288
Next, we can select the encryption key, the public key, e, so that it has no common factors with 288. Let's let e = 11.
To find the decryption key, d, we need a number that, multiplied by e, gives a product that is congruent to 1 mod 288. Expressed mathematically, we need to find a number d such that:
11 × d = 1 + n(288)
Using trial and error, we find that 131 works because 11 × 131 = 1 + 5(288).
So, our public key is N = 323 and e = 11.
The private key is d = 131.
If someone wants to send us the message "ABC" securely, using this scheme, we tell them N and e. They first convert "ABC" to "123" and then do the following arithmetic:
123^e = (123)¹¹ mod 323 = 81
The sender could then send the message, "81," over a public line of communication with confidence.
To decrypt the code, "81," we can use N and d as follows:
81^d = (81)¹³¹ mod 323 = 123
The message "81" becomes "123" after decryption, which we can then easily convert to "ABC," which was the intended message.
Notice that in order to break this scheme, a hacker would have to find the two numbers that when multiplied together yield 323. The square root of 323 is a little less than 18, so they would have to try a maximum of 7 divisors before they would be guaranteed to break the modulus into the original primes that were used to find the public and private keys. Using a computer, this would not be difficult, so real RSA encryption uses numbers that are sufficiently large so that even the fastest computers would take longer than a human lifespan to factor them. It is upon this foundation, the difficulty of factoring products of two large prime numbers, that modern data encryption rests.