Sunday, February 21, 2010

Homomorphic Encryption feature of RSA algorithm

RSA algorithm is homomorphic in mulitiplication. What do you mean by that? Well we all know that RSA is a reversible encryption algorithm which is widely used, especially with ssh. It is a bit slow encryption algorithm as the logic is based on two probable prime number calculations. Let me give a flow of how RSA works:
PlainText ->Key-> Encryption
Now, the encrypted text is what being transmitted across. Decryption is done as follows:
Encryption->Key->Decryption
There is public and private keys for RSA. I am not going in detail about it, but I can share the source code I used to prove that RSA is homomorphic in multiplication.
Homomorphic property of RSA states that if you multiply the encrypted value by n and decrypt with the same key, you will get the result as original value * n.

For example, if the plain text is 10 and if you multiply the encrypted text with 2 and then decrypt, you will get 20.
There is a catch here: A mere multiplication will not work. The multiplication should be done with the encrypted value of n.
ie, Let us take plain text as x
E(x) denotes the encrypted value of x
D(x) denotes the decrypted value of x.

Then,

D ( E(x) * E(n) ) = x*n

But D ( E(x) * n ) != x * n

Here is the source code for your reference:

import java.math.BigInteger;
import java.security.SecureRandom;
   

public class RSAHomomorphic {
  private final static BigInteger one = new BigInteger("1");
  private final static SecureRandom random = new SecureRandom();

  private BigInteger privateKey;
  private BigInteger publicKey;
  private BigInteger modulus;

  // generate an N-bit (roughly) public and private key
  RSAHomomorphic(int N) {
  BigInteger p = BigInteger.probablePrime(N/2, random);
  BigInteger q = BigInteger.probablePrime(N/2, random);
  BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));

  modulus = p.multiply(q);  
  publicKey = new BigInteger("65537"); // common value in practice = 2^16 + 1
  privateKey = publicKey.modInverse(phi);
  }


  BigInteger encrypt(BigInteger message) {
  return message.modPow(publicKey, modulus);
  }

  BigInteger decrypt(BigInteger encrypted) {
  return encrypted.modPow(privateKey, modulus);
  }

  public String toString() {
  String s = "";
  s += "public = " + publicKey + "\n";
  s += "private = " + privateKey + "\n";
  s += "modulus = " + modulus;
  return s;
  }
 
  public static void main(String[] args) {
 
  RSAHomomorphic key = new RSAHomomorphic(100);
  System.out.println(key);
 
  BigInteger x1 = new BigInteger("100");
  BigInteger x2 = new BigInteger("2");

  BigInteger enc_x1 = key.encrypt(x1);
  BigInteger enc_x2 = key.encrypt(x2);
  BigInteger dec_x1 = key.decrypt(enc_x1);
  BigInteger dec_x2 = key.decrypt(enc_x2);
   
 
  BigInteger homomorphic = enc_x1.multiply(enc_x2);
  BigInteger dec_h = key.decrypt(homomorphic);
   
  System.out.println("x1 = " + x1);
  System.out.println("x2 = " + x2);
   
  System.out.println("E ( x1 ) = " + enc_x1);
  System.out.println("E ( x2 ) = " + enc_x2);
  System.out.println("E ( x1 ) * E ( x2 ) = " + homomorphic);
  System.out.println("D ( E ( x1 ) * E ( x2 ) ) = " + dec_h);
  }
}

The output would be as:

$ java RSAHomomorphic 
public = 65537
private = 237497666793168261168967449473
modulus = 895820695748138208858686014249
x1 = 100
x2 = 2
E ( x1 ) = 867737439426455424754448444175
E ( x2 ) = 274813293643034418407848031465
E ( x1 ) * E ( x2 ) = 238465783746157286286789717700937490114748844108605695966375
D ( E ( x1 ) * E ( x2 ) ) = 200


6 comments:

  1. Hi I want to apply this source code on a data file (image, word file, video ...) and not integers. How can I do?

    ReplyDelete
    Replies
    1. Hii yosra i do have the same query...if u got any way to do it so...please help me in doing it...thank u...\

      Delete
  2. what are other algorithm support homomorphism

    ReplyDelete
  3. hello, i need help. I am applying this to protect a delegated computation. How do i go about it.
    Thanks

    ReplyDelete
  4. Hi I want to apply this source code on a data file (image, word file, video ...) and not integers. How can I do?

    ReplyDelete