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

Sorting million records with minimum memory

I encountered this problem of sorting a million records of same size on a unix box. My unix box is often overloaded with lot of processes, so I had to do it with a less amount of user and process memory. As usual, the time for implementation is quite less. So following is the method I adopted:

1. Read the input file which the complete input values, each line has one big number. Basically, each line is a big integer representation of a certain AES output value. Big Integer is created with the open source GMP library.
2. Read the first 4 digits and append the line to a file named based on the first 4 digits. For instance, if the the line is 8923523345012545454646,
It is written out to a file called 8923.ref. Any other number starting with the same 4 digits will be appended to the same file.
3. Repeat this process until every line is processed. This might created utmost 10K files. I wrote this code in C, so to make the file writing fast, a character array of large size is used to minimize the number of file writes.
4. Sort each and every file using any sorting method. If the items are of fixed size, sort utility in unix can be used.
5. You are only left with a cat operation of all files in the ascending order to a single file now.

This may not be a very efficient way, but very quick and flexible and requires very less memory. Choosing the file name based on n first digits should be done by analysing the input data. You may want to reduce or increase the number of digits based on the input data you have.

Start

Hi,This blog is for all the IT professionals around the world who has a passion for programming. I would like to keep posting about the technical tips that I have which might somebody else in this world. After all, programming is more about searching.Sorry, I haven't introduced me yet, I am a humble software professional based in Hyderabad, India. I like to dream about better design and ideas. Hope this blog would be of some help to people. Please feel free to contribute.