RSA Algorithm - Program in C

RSA is one of the first practical public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, theencryption key is public and differs from the decryption key which is kept secret. In RSA, this asymmetry is based on the practical difficulty of factoring the product of two large prime numbers, the factoring problem. RSA is made of the initial letters of the surnames ofRon Rivest, Adi Shamir and Leonard Adleman, who first publicly described the algorithm in 1977. 

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

Key generation

RSA involves a public key and a private key. The public key can be known by everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted in a reasonable amount of time using the private key. The keys for the RSA algorithm are generated the following way:

1. Choose two distinct prime numbers p and q.
   • For security purposes, the integers p and q should be chosen at random, and should be of similar bit-length. Prime integers can be efficiently found using a primality test.
2. Compute n = pq.
   • n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
3. Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function. This value is kept private.
4. Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are coprime.
   • e is released as the public key exponent.
   • e having a short bit-length and small Hamming weight results in more efficient encryption – most commonly 2¹⁶ + 1 = 65,537. However, much smaller values of e (such as 3) have been shown to be less secure in some settings.^[5]
5. Determine d as d ≡ e⁻¹ (mod φ(n)); i.e., d is the modular multiplicative inverse of e (modulo φ(n)).

• This is more clearly stated as: solve for d given d⋅e ≡ 1 (mod φ(n))
• This is often computed using the extended Euclidean algorithm. Using the pseudocode in the Modular integers section, inputs a and n correspond to e and φ(n), respectively.
• d is kept as the private key exponent.

The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d, which must be kept secret. p, q, and φ(n) must also be kept secret because they can be used to calculate d.

Encryption

Alice transmits her public key (n, e) to Bob and keeps the private key d secret. Bob then wishes to send message M to Alice.

He first turns M into an integer m, such that 0 ≤ m < n by using an agreed-upon reversible protocol known as a padding scheme. He then computes the ciphertext c corresponding to

This can be done efficiently, even for 500-bit numbers, using Modular exponentiation. Bob then transmits c to Alice.

Note that at least nine values of m will yield a ciphertext c equal to m,^{[note 1]}

Decryption[edit]

Alice can recover m from c by using her private key exponent d via computing

Given m, she can recover the original message M by reversing the padding scheme.

(In practice, there are more efficient methods of calculating c^d using the precomputed values below.)

A worked example[edit]

Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but one can also use OpenSSL to generate and examine a real keypair.

1. Choose two distinct prime numbers, such as

    and 

2. Compute n = pq giving

   

3. Compute the totient of the product as φ(n) = (p − 1)(q − 1) giving

   

4. Choose any number 1 < e < 3120 that is coprime to 3120. Choosing a prime number for e leaves us only to check that e is not a divisor of 3120.

   Let 

5. Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding,

   

   Worked example for the modular multiplicative inverse:

   

   

The public key is (n = 3233, e = 17). For a padded plaintext message m, the encryption function is

The private key is (d = 2753). For an encrypted ciphertext c, the decryption function is

For instance, in order to encrypt m = 65, we calculate

To decrypt c = 2790, we calculate

Both of these calculations can be computed efficiently using the square-and-multiply algorithm for modular exponentiation. In real-life situations the primes selected would be much larger; in our example it would be trivial to factor n, 3233 (obtained from the freely available public key) back to the primes p and q. Given e, also from the public key, we could then compute d and so acquire the private key.

/*
    Sample test case 1 :
        Choose p = 3 and q = 11
        Compute n = p * q = 3 * 11 = 33
        Compute φ(n) = (p - 1) * (q - 1) = 2 * 10 = 20
        Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 7
        Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 3 [(3 * 7) % 20 = 1]
        Public key is (e, n) => (7, 33)
        Private key is (d, n) => (3, 33)
        The encryption of m = 2 is c = 27 % 33 = 29
        The decryption of c = 29 is m = 293 % 33 = 2
        
    Sample test case 2 :
        Choose p = 61 and q = 53
        Compute n = p * q = 61 * 53 = 3233
        Compute φ(n) = (p - 1) * (q - 1) = 60 * 52 = 3120
        Choose e such that 1 < e < φ(n) and e and n are coprime. Let e = 17
        Compute a value for d such that (d * e) % φ(n) = 1. One solution is d = 2753 [(2753 * 17) % 20 = 1]
        Public key is (e, n) => (17, 3233)
        Private key is (d, n) => (2753, 3233)
        The encryption of m = 65 is c = 2790
        The decryption of c = 2790 is m = 65
*/
#include<stdio.h>
/*
    Exponentiation by squaring
        http://en.wikipedia.org/wiki/Exponentiation_by_squaring
*/
long long int power(long long int a,long long int b,long long int mod)
{
    long long int t;
    if(b==0)
        return 1;
    else if(b==1)
        return a;
    t=power(a,b/2,mod);
    if(b%2==0)
        return (t*t)%mod;
    else
        return (((t*t)%mod)*a)%mod;
}

/*
    Euler's theorem may be used to compute modular inverse:
    According to Euler's theorem, if a is coprime to m, that is, gcd(a, m) = 1, then
        
        inverse of a = power(a,m-2) % m 
        
    but for Euler's m must be prime.
        and our mod will never be prime.
            because mod is phi(n) = (p-1)*(q-1) ... so this is never prime.
    so we cant apply Eulers Theorem to find multiplicative inverse of e
*/
/*
long long int modularMultiplicativeInverse_Euler(long long int e,long long int mod)
{
    return power(e,mod-2,mod);
}
*/
/*
long long int modularMultiplicativeInverse_ExtendedEuclideantheorem(long long int e,long long int mod)
{
    
}
*/
long long int modularMultiplicativeInverse_BruteForce(long long int e,long long int mod)
{
    long long int i;
    for(i=1;i<mod;i++)
        if((e*i)%mod==1)
            return i;
}
long long int encrypt(long long int m,long long int e,long long int n)
{
    return power(m,e,n);
}
long long int decrypt(long long int c,long long int d,long long int n)
{
    return power(c,d,n);
}
int main()
{
 long long int p,q,n,phin,d,e,m,c;
 // p and q should be prime numbers of similar bit length.
 printf("Enter the value of p and q (p and q should be primes of similar bit length) :\n");
 scanf("%lld%lld",&p,&q);
 n=p*q;
 phin=(p-1)*(q-1);

 printf("Enter an integer e such that 1 < e < %lld, and gcd(e,%lld)=1 : ",phin,phin);
 scanf("%lld",&e);

 printf("NOTE : %lld,%lld is your public key.\n",e,n);
 // e is called the public key exponent
 
 d=modularMultiplicativeInverse_BruteForce(e,phin);
 printf("NOTE : %lld,%lld is your private key.\n",d,n);
 // d is called the private key exponent
    
    printf("\nEnter the number to be encrypted : ");
    scanf("%lld",&m);
    c=encrypt(m,e,n); // sending the message to be encrypted and the public key.
    printf("the encrypted message is : %lld\n",c);
    
    printf("\nEnter the number to be decrypted : ");
    scanf("%lld",&c);
    m=decrypt(c,d,n); // sending the cipher message to be decrypted and the private key.
    printf("the decrypted message is : %lld\n",m);
 return 0;
}