Implementation of Rabin Cryptosystem in Java

Hello Learners, today We are going to learn about Rabin Cryptosystem and implement it in Java language.

Rabin Cryptosystem is a public-key cryptosystem discovered by Michael Rabin. It uses key encryption for communicating between two medium senders and receivers.

It is like a security system it can produce every text with some numbers any of the combinations of four inputs. If our o/p is ciphertext we need extra complexity in the decryption front to find which is the exact text.

Algorithm for this problem

Generation of Text

we need to consider two prime numbers such as a1 and b1 where a1 not equals to b1 but let’s consider a1 and b1 is near about 3 mod 4.

for example, we can say, a1=139 and b1=191.

now result = a1*b1 where the result is denoted as the public key and  a1 and b1 are the private key.

Encrypted Text

• We have our public key result and now convert the text or message into their respective ASCII values.
• after converting into binary then change the value back with its decimal formal such as here decimal.
• Enter the value in the formula, code = decimal mod result
• Send the code value to the recipient after encoding the code.

Decrypted Text

•    Accept our code from the sender.
• with the help of extended euclidean GCD algo find the a2 and b2 in that form where the addition of a1 * a2 and b1*b2 is 1.
• Put the values in the formulae, receiver = code * (a + 1) / 4 mod a1 and for sender it is ame but with b.
• Now it is the time for calculating the values. where
• A = ( a1.a2.receiver + b1.b2.sender ) mod a1 and B is as same as A but with substraction in the middle and mod by b1.
• So up to now, we have four roots as decimal1 = A ,decimal2 = -A, decimal3 = B ,decimal4 = -B
• Now, Convert them to binary and divide them all in half.
• Converting the value into binary and cut them in halves. For those where right and left part are same keep that binary part and turn into decimal. Finally, after doing this technique we can get our correct message from the sender.

Code

Below is our Java code for implementation of Rabin Cryptosystem:

package CodeSpeedy;

import java.math.BigInteger; 
import java.nio.charset.Charset; 
import java.security.SecureRandom; 
import java.util.Random; 

class CryptographyClassic { 
  private static Random random = new SecureRandom(); 
  private static BigInteger second = BigInteger.valueOf(2); 
  private static BigInteger third = BigInteger.valueOf(3); 
  private static BigInteger fourth = BigInteger.valueOf(4); 

  public static BigInteger[] generateKey(int Bitlength) 
  { 
    BigInteger p1 = blumPrime(Bitlength / 2); 
    BigInteger q1 = blumPrime(Bitlength / 2); 
    BigInteger n = p1.multiply(q1); 
    return new BigInteger[] { n, p1, q1 }; 
  } 

  public static BigInteger encrypt(BigInteger m, 
                  BigInteger n) 
  { 
    return m.modPow(second, n); 
  } 

  public static BigInteger[] decrypt(BigInteger c, 
                  BigInteger p, 
                  BigInteger q) 
  { 
    BigInteger n = p.multiply(q); 
    BigInteger p1 = c.modPow(p 
                  .add(BigInteger.ONE) 
                  .divide(fourth), 
                p); 
    BigInteger p2 = p.subtract(p1); 
    BigInteger q1 = c.modPow(q 
                  .add(BigInteger.ONE) 
                  .divide(fourth), 
                q); 
    BigInteger q2 = q.subtract(q1); 

    BigInteger[] ext = Gcd(p, q); 
    BigInteger yp = ext[1]; 
    BigInteger yq = ext[2]; 

    BigInteger d1 = yp.multiply(p) 
              .multiply(q1) 
              .add(yq.multiply(q) 
                  .multiply(p1)) 
              .mod(n); 
    BigInteger d2 = yp.multiply(p) 
              .multiply(q2) 
              .add(yq.multiply(q) 
                  .multiply(p1)) 
              .mod(n); 
    BigInteger d3 = yp.multiply(p) 
              .multiply(q1) 
              .add(yq.multiply(q) 
                  .multiply(p2)) 
              .mod(n); 
    BigInteger d4 = yp.multiply(p) 
              .multiply(q2) 
              .add(yq.multiply(q) 
                  .multiply(p2)) 
              .mod(n); 

    return new BigInteger[] { d1, d2, d3, d4 }; 
  } 

  public static BigInteger[] Gcd(BigInteger a, BigInteger b) 
  { 
    BigInteger s = BigInteger.ZERO; 
    BigInteger olds = BigInteger.ONE; 
    BigInteger t = BigInteger.ONE; 
    BigInteger oldt = BigInteger.ZERO; 
    BigInteger r = b; 
    BigInteger oldr = a; 
    while (!r.equals(BigInteger.ZERO)) { 
      BigInteger q = oldr.divide(r); 
      BigInteger tr = r; 
      r = oldr.subtract(q.multiply(r)); 
      oldr = tr; 

      BigInteger ts = s; 
      s = olds.subtract(q.multiply(s)); 
      olds = ts; 

      BigInteger tt = t; 
      t = oldt.subtract(q.multiply(t)); 
      oldt = tt; 
    } 
    return new BigInteger[] { oldr, olds, oldt }; 
  } 

  public static BigInteger blumPrime(int bitLength) 
  { 
    BigInteger p; 
    do { 
      p = BigInteger.probablePrime(bitLength, random); 
    } while (!p.mod(fourth).equals(third)); 
    return p; 
  } 
} 
public class RabinCryptoSystem { 
  public static void main(String[] args) 
  { 
    BigInteger[] form = CryptographyClassic.generateKey(512); 
    BigInteger n = form[0]; 
    BigInteger p = form[1]; 
    BigInteger q = form[2]; 
    String finalMessage = null; 
    int i = 1; 
    String s = "Hi Learners ,Welcome to Codespeedy!"; 

    System.out.println("Message sent by sender is  : " + s); 

    BigInteger m 
      = new BigInteger( 
        s.getBytes( 
          Charset.forName("ascii"))); 
    BigInteger c = CryptographyClassic.encrypt(m, n); 

    System.out.println("Encrypted Message is  : " + c); 

    BigInteger[] m2 = CryptographyClassic.decrypt(c, p, q); 
    for (BigInteger b : m2) { 
      String dec = new String( 
        b.toByteArray(), 
        Charset.forName("ascii")); 
      if (dec.equals(s)) { 
        finalMessage = dec; 
      } 
      i++; 
    } 
    System.out.println( 
      "Message received by The Receiver is  : "
      + finalMessage); 
  } 
} 

 

Output :

Message sent by sender is  : Hi Leaners , Welcome to Codespeedy!
Encrypted Message is  : 1444859695420650621464775939815486931953053159161778005014850020303292629817991635679919811652273086812472851363820741721835334113421175829726383437857383
Message received by The Receiver is  : Hi Leaners , Welcome to Codespeedy!