Do you think IIT Guwahati certified course can help you in your career?
Introduction
We share almost every aspect of our lives online and conduct susceptible transactions daily. In this environment, both individuals and businesses require strong security measures. Thus, comes cryptography in this scenario. It is a method for securing information and communications using codes so that only those who need the information can understand and process it.
Also, for more security, we use Asymmetric cryptography. Asymmetric encryption employs two separate but related keys. The Public Key is used for encryption here, while the Private Key is used for the decryption. The Private Key is meant to be private, as the name implies, so only the authenticated person receiving can decrypt the data. One such Asymmetric Cryptography technique involves Rabin Cryptosystem, which will be discussed in this article.
What is the Rabin Cryptosystem?
The Rabin cryptosystem is an asymmetric cryptographic method invented by Michael Rabin. The difficulty of factorization is related to the security of the Rabin cryptosystem. It has the advantage over the others in that the problem it banks on has proven to be difficult as integer factorization. It also has the disadvantage that any of the four possible inputs can generate each Rabin function output. If each output is a ciphertext, decryption requires additional complexity to determine which of the four possible inputs was the true plaintext.
Key Generation
The Rabin system, like all asymmetric cryptosystems, employs both a public and a private key. The public key is required for later encoding and can be published, whereas the private key can only be possessed by the message's recipient.
The exact key-generation procedure is as follows:
Select two large distinct prime numbers p and q, such that p ☰ 3 mod 4, and q ☰ 3 mod 4(ex: p=139 and q=191).
Calculate n = p*q.
n = 139*191
= 26549
Then n represents the public key, and the pair (p, q) represents the private key. Only the public key n is required to encrypt a message. The factors p and q of n are required to decrypt a ciphertext.
Encryption
Only the public key n is used for encryption, yielding a ciphertext from the plaintext. A message M can be encrypted by first converting it to a number m < n using a reversible mapping, and then computing c=m2 mod n, c is the cipher text.
Algorithm:
Obtain the public key n.
n=26549
Convert the message's value to ASCII. Then convert it to binary, multiply it by itself, and convert the binary value back to decimal m.
Now, use the following formula to compute X and Y:
X = ( x*p*r + b*q*s ) mod p
Y = ( y*p*r – b*q*s ) mod q
X = 11*139*118 = 180422
Y = -8 *191*125 = -191000
The four roots are as follows: m1=X, m2=-X, m3=Y, and m4=-Y.
Now, Convert all of them to binary and divide them in half.
Determine which half of the left and right halves are the same. Keep one half of that binary and convert it to decimal m. Obtain the ASCII character corresponding to the decimal value m. The resulting character conveys the message sent by the sender.
Full Implementation
C++ code for Rabin Cryptosystem:
#include<bits/stdc++.h>
using namespace std;
int encryption(int m, int n);
int decryption(int c, int p, int q);
int mod(int k, int b, int m);
int modulo (int a, int b);
vector<int> extendedEuclid(int a, int b);
/* private key pair(p,q) of the form 3 mod 4 */
int p = 151, q = 43;
/* public key n */
int n = p * q;
int main()
{
/* vector for storing the encrypted message */
vector<int>e;
/* vector for storing the decrypted message */
vector<int>d;
string message ="Welcome to Coding Ninjas!";
cout << "Plain text: " << message << endl;
int len = strlen(message.c_str());
cout << "Encrypted text: ";
for(int i = 0; i <= len; i++)
{
e.push_back(encryption(message[i], n));
cout << e[i];
}
cout << endl;
for(int i = 0; i < len; i++)
{
d.push_back(decryption(e[i], p, q));
}
cout << "Decrypted text: ";
for(int i=0;i<d.size();i++)
cout << char(d[i]);
cout << endl;
return 0;
}
int encryption(int m, int n)
{
/* c = (m^2) mod n */
int c = (m * m)%n;
return c;
}
/* chinese remainder theorem implementation */
int mod(int k, int b, int m)
{
int i=0;
int a=1;
vector<int> v;
while(k>0){
v.push_back(k%2);
k=(k-v[i])/2;
i++;
}
for(int j=0; j<i; j++){
if(v[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;
}
/* Extended Eucledian Algorithm */
vector<int> extendedEuclid(int a, int b)
{
if (b>a) {
int temp=a; a=b; b=temp;
}
int i=0;
int j=1;
int x=1;
int y=0;
while (b!=0) {
int q= a/b;
int temp1= a%b;
a=b;
b=temp1;
int temp2 = i;
i=x-q*i;
x = temp2;
int temp3 = j;
j = y-q*j;
y=temp3;
}
vector<int>arr(3);
arr[0] = x;
arr[1] = y;
arr[2] = 1;
return arr;
}
int decryption(int c, int p, int q)
{
int r = mod((p+1)/4, c, p);
int s = mod((q+1)/4, c, q);
vector<int> arr = extendedEuclid(p, q);
int rootp = arr[0]*p*s;
int rootq = arr[1]*q*r;
double r1 = modulo((rootp+rootq), n);
if( r1 < 128)
return r1;
int negative_r = n - r1;
if (negative_r < 128)
return negative_r;
int s1 = modulo((rootp-rootq), n);
if( s1 < 128)
return s1;
int negative_s = n - s1;
return negative_s;
}
You can also try this code with Online C++ Compiler
Any algorithm that finds one of the possible plaintexts for each Rabin-encrypted ciphertext can be utilized to factor the modulus n. As a result, Rabin decryption for arbitrary plaintext is at least as difficult as that of the integer factorization problem, which has not been proven for RSA. It is widely assumed that there is no polynomial-time factoring algorithm, which implies that there isn't any effective approach for decrypting a random Rabin-encrypted value in the absence of the private key (p, q).
Because the encryption process is deterministic, the Rabin cryptosystem does not provide indistinguishability against chosen plaintext attacks. Given a ciphertext and an applicant message, an adversary can easily determine whether the ciphertext encodes the applicant message by checking whether encrypting the applicant message yields the given ciphertext.
Frequently Asked Questions
How many plaintexts are generated during the Rabin scheme decryption?
Decryption yields three false results in addition to the correct one, necessitating guessing the correct result.
How does the Rabin cryptosystem encrypt the message?
After obtaining the public key n, convert the message to an ASCII value. Then convert it to binary, multiply it by itself, and convert the binary value back to decimal m. Encrypt now using the formula: C = m^2 mod n. Send C to the intended recipient.
How does the Rabin cryptosystem work?
We choose two prime numbers using the Rabin public key (p and q). If possible, p≡q≡3(mod4) makes the decryption process easier. We begin by determining n=p*q, where n is the public key and p and q are the private keys. We encrypt with n and decrypt with p and q of n factors.
What is the Rabin Cryptosystem?
The Rabin cryptosystem is an asymmetric cryptographic method invented by Michael Rabin. The difficulty of factorization is related to the security of the Rabin cryptosystem. It has the advantage over the others in that the problem it banks on has proven to be difficult as integer factorization.
Conclusion
In this blog, we have learned about the Rabin Cryptosystem and the various steps involved in this cryptosystem. We went through the key generation, encryption, and decryption along with the examples and then full implementation of the Rabin cryptosystem in C++. Recommended Readings:
568+ registered 
