Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Rabin Cryptosystem?
3.
Key Generation
4.
Encryption
5.
Decryption
6.
Full Implementation
7.
Security Evaluation
8.
Frequently Asked Questions
8.1.
How many plaintexts are generated during the Rabin scheme decryption?
8.2.
How does the Rabin cryptosystem encrypt the message?
8.3.
How does the Rabin cryptosystem work?
8.4.
What is the Rabin Cryptosystem?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is the Rabin Cryptosystem?

Author Rashi
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

What is the Rabin Cryptosystem?

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Key Generation

Key Generation for Rabin Cryptosystem

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

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.

m = "R" = 82 (R's ASCII value is 82)

    = 8210 = 10100102;

    = 1010010 10100102; → double extend

    = 1057810
 

  • Encrypt with the following formula:

c =  m2 mod n

c = 105782 mod 26549

c = 16598
 

  • Send C to the intended recipient.

Decryption

Decryption
  • Accept the sender's C.

c = 16598
 

x*p + y*q = 1

139x + 191y = 1
 

  • Using the following formula, compute r and s:

r = c(p+1)/4 mod p

s = c(q+1)/4 mod q

r = 16598(139+1)/4 mod 139 = 125

s = 16598(191+1)/4 mod 191 = 118
 

  • 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;
}


Output:

output

Security Evaluation

security evaluation

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:


You can refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning!

Previous article
Wiener’s Low Decryption Exponent Attack on RSA
Next article
What is Semantic Security of RSA?
Live masterclass