Text Encryption Using RSA

Text Encryption Using RSA

The RSA cryptosystem is a public-key cryptosystem that offers encryption. Ronald Rivest, Adi Shamir, and Leonard Adleman developed the RSA system in 1977; RSA stands for the first letter in each of its inventors’ last names.

The RSA algorithm works as follows: take two large primes, p and q, and compute their product n = p*q; n is called the modulus. Choose a number, e, less than n and relatively prime to (p-1)*(q-1), which means e and (p - 1)(q - 1) have no common factors except 1. Find another number d such that (e*d - 1) is divisible by (p - 1)*(q - 1). The values e and d are called the public and private exponents, respectively. The public key is the pair (n, e); the private key is (n, d). The factors p and q may be destroyed or kept with the private key.

It is currently difficult to obtain the private key d from the public key (n, e). However if one could factor n into p and q, then one could obtain the private key d. Thus the security of the RSA system is based on the assumption that factoring is difficult. The discovery of an easy method of factoring would ‘‘break’’ RSA.

Encryption

Suppose Alice wants to send a message m to Bob. Alice creates the cipher text c by exponentiating:

c = m^e mod n, where e and n are Bob’s public key. She sends c to Bob. To decrypt, Bob also exponentiates: m = c^d mod n; the relationship between e and d ensures that Bob correctly recovers m. Since only Bob knows d, only Bob can decrypt this message. (text is taken from RSA Security)

C Source Code

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#include<math.h>

#define Asal_Adet 168

short Asal[168] = {  2, 3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
                   67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,
                   139,149,151,157,163,167,173,179,181,191,193,197,199,
                   211,223,227,229,233,239,241,251,257,263,269,271,277,
                   281,283,293,307,311,313,317,331,337,347,349,353,359,
                   367,373,379,383,389,397,401,409,419,421,431,433,439,
                   443,449,457,461,463,467,479,487,491,499,503,509,521,
                   523,541,547,557,563,569,571,577,587,593,599,601,607,
                   613,617,619,631,641,643,647,653,659,661,673,677,683,
                   691,701,709,719,727,733,739,743,751,757,761,769,773,
                   787,797,809,811,821,823,827,829,839,853,857,859,863,
                   877,881,883,887,907,911,919,929,937,941,947,953,967,
                   971,977,983,991,997 };

long filesize(FILE* stream) {
   long curpos, length;
   curpos = ftell(stream);
   fseek(stream, 0L, SEEK_END);
   length = ftell(stream);
   fseek(stream, curpos, SEEK_SET);
   return length;
}

// This clever algorithm finds the invers
unsigned long get_invers(unsigned long a, unsigned long n)
{
     long k=0;
     float x=0.5, y=0.0;

     while((x-y) != 0.0)
     {
                 k++;
                 x = (1+(float)n*k)/(float)a;
                 y=(long)x;
     }

     return (unsigned long)x;
}

unsigned long get_encrypted_data(unsigned int c, unsigned long e, unsigned long n)
{
  long w, say1=e, k;
  w = 1;
  while (say1 >= 1)
   {
     k = say1 % 2;
     say1 = say1 >> 1;  // division by 2
     if (k > 0)
       w = ( w * k * c ) % n;
     c = (c * c) % n;
   }
  while (w <= 0 )
    w = w + n;
  return w;
}

unsigned long get_decrypted_data(unsigned int c, unsigned long d, unsigned long n)
{
  unsigned long w1, say2=d, k;
  w1 = 1;
  while( say2 >= 1)
   {
     k = say2 % 2;
     say2 = say2 >> 1; // division by 2
     if( k > 0)
       w1 = ( w1 * k * c ) % n;
     c = (c*c) % n;
   }
  while (w1 <= 0 )
    w1 = w1 + n;
return w1;
}

int Encrypt( unsigned long e,
                                    unsigned long p,
                                    unsigned long q,
                                    char data_o[],
                                    unsigned char data_e[],
                                    unsigned long s)
{
  unsigned long i, n;
  unsigned char ch;

// encrypt
  n = p * q;
  for(i=0;i<s;i++)
   {
      ch = data_o[i];
              ch = (char)get_encrypted_data(ch, e, n);
      data_e[i] = ch;
   }
// decrypt

  return 0;
}

int Decrypt( unsigned long e,
                                    unsigned long p,
                                    unsigned long q,
                                    unsigned char data_e[],
                                    unsigned char data_b[],
                                    unsigned long s)
{
  unsigned long i, n, fi, m, d;
  unsigned char ch;

//  decrypt
  n = p * q;
  m = fi = (p-1) * (q-1);
  d = get_invers(e, m);
  for(i=0;i<s;i++)
   {
      ch = data_e[i];
              ch = (char)get_decrypted_data(ch, d, n);
      data_b[i] = ch;
   }
// decrypt

  return 0;
}

void main(void)
{

      unsigned long i, s, e, p, q;
      char data_o[256]={0};
      unsigned char data_e[256]={0}, data_b[256]={0};

      printf("input e: ");scanf("%ld", &e);
      printf("input p: ");scanf("%ld", &p);
      printf("input q: ");scanf("%ld", &q);
      printf("input string: ");scanf("%s", data_o);
      s = strlen(data_o);

      Encrypt(e, p, q, data_o, data_e, s);
      printf("Encrypted data: ");
      for(i=0;i<s;i++)
                  printf("%ld ", data_e[i]);

      Decrypt(e, p, q, data_e, data_b, s);
      printf("\nDecrypted data: ");
      printf("%s\n", data_b);
}

Sample Execution

input e: 23

input p: 11

input q: 23

input string: bilgisayar_muhendisligi

Encrypted data: 98 128 223 218 128 92 212 121 212 229 233 109 2 81 239 110 100 128 92 223 128 218 128

Decrypted data: bilgisayar_muhendisligi