Rabin Cryptosystem Implementation in C++

Rabin Cryptosystem is an asymmetric cryptography algorithm that is based on quadratic congruence. This cryptography technique involves a private key pair(p,q) and a public key n. This n is called ‘Blum Integer’ and the plain text x should always be:  1 < x < n. Its security like the RSA algorithm is determined by integer factorization (i.e. the decomposition of a composite integer into a product of smaller integers). The Rabin Cryptosystem has been mathematically proven to be computationally secure against a brute-force attack as long as the attacker is unable to get the correct factors.

Pre-requisites for implementing Rabin Cryptosystem in C++

In order to understand this cryptography technique one should know the following algorithms:

1. Extended Euclid Algorithm

2. Chinese Remainder Theorem

Basic knowledge of vectors/arrays is a must.

Key Generation in Rabin Cryptosystem:

Two prime numbers p and q form the private key pair, such that:

p≅3 (mod 4)

q≅3 (mod 4)

p q

n = p*q is the public key.

Encryption of the plain text :

The encrypter function takes two parameters, the plain text ‘m’ and the public key ‘n’.

It returns an integer value c, where c is the ciphertext.

The formula is c = (m2) mod n

```int encrypter(int m, int n)
{
int c = (m * m)%n;    // c = (m^2) mod n
return c;
}
```

Utility functions used : Rabin Cryptosystem

```int modulo (int a, int b)
{
return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b;
}

vector<int> Extended_Euclid(int a, int b)

{
if (b>a) {
int temp=a; a=b; b=temp;
}
int x=0;
int y=1;
int lastx=1;
int lasty=0;

while (b!=0) {

int q= a/b;
int temp1= a%b;
a=b;
b=temp1;
int temp2 = x;
x=lastx-q*x;
lastx = temp2;
int temp3 = y;
y = lasty-q*y;
lasty=temp3;

}

vector<int>arr(3);
arr[0] = lastx;
arr[1] = lasty;
arr[2] = 1;
return arr;
}
```

Decryption in the Rabin Cryptosystem in C++

Take the ciphertext c from the user and the private key pair (p,q).

Calculate mp and mq using the following formulae:

mp = C(p+1)/4 mod p
mq = C(q+1)/4 mod q

Find out a and b using the Extended Euclid Algorithm (a.p + b.q = 1)

Since the Rabin Cryptosystem is based on quadratic congruence there will be 4 possible roots after decryption.

r1,r2,r3,r4

Calculate root values rootp and rootq as follows:

int rootp = a*p*mq;
int rootq = b*q*mp;

calculate r = modulo((rootp+rootq), n);

calculate s = modulo((rootp-rootq),n);

Now, r1 = r

r2 = n – r

r3 = s

r4 = n-s

Convert the ascii value to text and Out of these 4 roots, one will be the plain text.

Below is the C++ implementation of the Rabin cryptosystem:

```#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int p = 151, q = 43; //private key pair(p,q) of the form 3 mod 4

int n = p * q;        //public key n

int encrypter(int m, int n)
{
int c = (m * m)%n;    // c = (m^2) mod n
return c;
}

int mod(int k, int b, int m) //chinese remainder theorem implementation
{
int i=0;
int a=1;
vector<int> t;
while(k>0){
t.push_back(k%2);
k=(k-t[i])/2;
i++;
}
for(int j=0; j<i; j++){
if(t[j]==1){
a=(a*b)%m;
b=(b*b)%m;
} else{
b=(b*b)%m;
}
}
return a;
}

int modulo (int a, int b)
{
return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b;
}

vector<int> Extended_Euclid(int a, int b)
{
if (b>a) {
int temp=a; a=b; b=temp;
}
int x=0;
int y=1;
int lastx=1;
int lasty=0;
while (b!=0) {
int q= a/b;
int temp1= a%b;
a=b;
b=temp1;
int temp2 = x;
x=lastx-q*x;
lastx = temp2;
int temp3 = y;
y = lasty-q*y;
lasty=temp3;
}
vector<int>arr(3);
arr[0] = lastx;
arr[1] = lasty;
arr[2] = 1;
return arr;
}

int decrypter(int c, int p, int q)
{
int mp = mod((p+1)/4, c, p);
int mq = mod((q+1)/4, c, q);

vector<int> arr = Extended_Euclid(p, q);
int rootp = arr[0]*p*mq;
int rootq = arr[1]*q*mp;
double r = modulo((rootp+rootq), n);
if( r < 128)
return r;
int negative_r = n - r;
if (negative_r < 128)
return negative_r;
int s = modulo((rootp-rootq), n);
if( s < 128)
return s;
int negative_s = n - s;
return negative_s;

}

int main()
{
vector<int>e; //vector to store the encrypted message
vector<int>d; //vector to store the decrypted message
string message ="CodeSpeedy is Cool!";
cout << "Plain text: " << message << endl;
int len = strlen(message.c_str());

cout << "Encrypted text: ";
for(int i = 0; i <= len; i++)
{
e.push_back(encrypter(message[i], n));
cout << e[i];
}

cout << endl;

for(int i = 0; i < len; i++)
{
d.push_back(decrypter(e[i], p, q));
}
cout << "Decrypted text: ";
for(int i=0;i<d.size();i++)
cout << char(d[i]);

cout << endl;
return 0;
}
```