Matlab taking forever to give a simple result - something that java does in seconds

I am trying to do encryption in Matlab using Paillier, I found online implementation in Java, since I know matlab and am very bad at java. I implemented that code in matlab. I want to know if matlab very bad at this or is my implementation wrong?

I'm having performance issues with matlab using large prime numbers. I am using vpi for all my inputs and it is still taking hours.

I'm encrypting a number using Paillier encryption, using:

n = p*q;
cipherText = mod(g^pixel_value*random_number^n,n^2);

This works and I can decrypt the result as well using small prime numbers such as p = 43 and q = 47. But for this to be effective I have to use large prime numbers, so I tried with p = 41983 and q = 42013, and random_number = 743. I am unable to get a result for that above calculation.

It has been over 2 hours and its still busy processing for a pixel_value = vpi(10).

Whereas on the other hand in Java, my p and q are of 512 bits each and I get the encryption and decryption done within seconds. Here is the code in java for encryption:

public BigInteger Encryption(BigInteger m) {
BigInteger r = new BigInteger(bitLength, new Random());
return g.modPow(m, nsquare).multiply(r.modPow(n, nsquare)).mod(nsquare);

using the following p and q respectively:

97397929462509430948085750131928345276271739093186875584416638279790842581747
90403725479134903380301300689889714727885388292269807925961915682035739163693

Answer 1

[John D'Errico]

Your implementation is just plain silly. Sorry, but it is. You used modpow when you computed it with java. But when you tried to do it in MATLAB (using vpi), what did you do?

Why would you compute it this way:

p = vpi(41983);
q = vpi(42013);
n = p*q
random_number = 743;

cipherText = mod(g^pixel_value*random_number^n,n^2);

Hmm. You don't tell me what is g, or pixel_value. But I don't need to know. Think about what you did!

n =
    1763831779

Do you now compute 743^1763831779? Why in the name of god and little green apples would you do that? You knew you had to use modpow before! Do you have any clue as to how many digits that number has?

log10(743)*1763831779
ans =
        5063941306.86442

Something like 5 BILLION decimal digits. Are you serious? And then you multiplied it by g^pixel_value, which I lack. And only then did you bother to compute the mod. Again, this is why powermod tools exist. They allow you to do a mod computation of a power, without EVER computing the large number explicitly.

powermod(random_number,n,n^2)
ans =
    2161172753976661333

Next, you need to recognize one basic identity:

mod(A*B,m) = mod(mod(A,m)*mod(B,m),m)

Of course, that applies to any powermod computation too. So you can use powermod twice. That is, apply powermod to g^pixelvalue (at least, if that number will be large.) THEN use mod on the product.

If you will work with large integers, you need to learn how to work with large integer tools. Never just unthinkingly apply brute force, unless you want it to take forever. I suppose that might be the goal of some people.

[Faraz]

Hi, Thanks for the great answer again.

I clearly dont know how to handle large integers, I am just getting into encryption and I am implementing the equations in matlab as they are written from wikipedia. Also that java implementation is not mine, I just found it online for comparison sake.

mod(A*B,m) = mod(mod(A,m)*mod(B,m),m)

This is very helpful, thanks. The calculation that took hours was done in an instant using the above form. Is there anywhere where I can read more on how to deal with large integers?