[Help in Formula implementation] Why am I getting a float value when a integer value is expected?

I'm trying to implement the Paillier cryptosystem in Matlab using the key generation guidance available here: https://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation, but the problem is that with any combination of prime numbers I try, I get a float gMu required for the private key.

The first step is:

> Choose two large prime numbers p and q

Just for a starting point I chose ``p = 17 and q = 19``.

> Compute n=p*q and

Which I achieved in Matlab using:

    n = p*q;
    lambda = lcm((p - 1), (q - 1));

This gives me "n = 323" and "lambda = 144"

> Third step:

Select random integer g

I read that "g = n + 1" satisfies all the required conditions so I went with that, which gives me a "g = 324".

> Fourth step is to compute mu using:

where

I achieved this using:

    a = (powermod(g, lambda, n*n) - 1) / n;

    gMu = mod(inv(a),n);

So at this stage, the public key is supposed to be "(n,g) = (323,324)" and the private key would be "(lambda,mu)" which in my case comes to "(144,0.0069)".

Why am I getting a float value of "gMu" whereas all the implementations I have seen online provide a integer value of private keys.

Where am I getting this wrong?

Answer 1

[John D'Errico]

p = 17;
q = 19;
n = p*q;
lambda = lcm((p - 1), (q - 1));
g = n+1;
a = (powermod(g, lambda, n*n) - 1) / n;

a
a =
   144

    whos a
    Name      Size            Bytes  Class     Attributes
    a         1x1                 8  double

Fine, up to that point. Not sure where you found a powermod code. You might have found one in my VPI toolbox, which does that computation, and will work on regular integers too. Regardless, that is the correct result up to this point.

But now I had to laugh. You need to think about what you are doing, rather than just write down formulas and expect them to have a chance of working.

What is inv(a)?

inv(a)
ans =
    0.0069444

a is a real number. What is the inverse of a real number, in this case, the number 144? That would be

1/144
ans =
    0.0069444

which is what inv will return for scalar input.

Perhaps what you really needed to compute was a modular inverse? That is, the modular inverse of a with respect to a modulus n, is the number ainv, such that

mod(a*ainv,n) = 1

Of course, when a is a real number, the inverse of a, in the field of real numbers is the number such that

a*ainv = 1

Clearly, that is given by (for a~=0)

ainv = 1/a

But that is not available when you are talking about the field of numbers modulo some integer n. And how did you create a? a is a double precision number. As far as MATLAB is concerned, a is just a number, a real number.

If n is not prime, then not all numbers a will have a modular inverse. But for a=144, and n=323, we can find

ainv = 83;

As a test, we can verify that claim:

mod(a*ainv,n)
ans =
     1

It is also pretty easy to show that no value for ainv exists, such that either 17 or 19 can have an inverse modulo 323. In fact, since the prime factors of 323 are 17 and 19, all numbers which are integer multiples of either 17 or 19 will fail to have a modular inverse in this case. The general rule would be that only integers relatively coprime with n would have a modular inverse mod n.

There are several ways you can compute such a modular inverse (multiplicative inverse). I'd suggest the extended Euclidean algorithm as a good solution.

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

If you indeed are using my vpi toolbox, you might find minv to be of value, as it does the work for you. Though, I wonder if I should have just put it into powermod, as Mathematica seems to have done? Oh well, another round tuit.

[Faraz]

Many thanks for the detailed answer.

I was not aware of your vpi toolbox but have started using it now and the minv function as well. The encryption works as expected now. Thanks