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; }
Leave a Reply