0

Here is my Paillier class:

public class Paillier {
    private static BigInteger Nv;
    private static BigInteger Nc;
    private static BigInteger b;
    private static BigInteger p;
    private static BigInteger q;
    private static BigInteger n;
    private static BigInteger nsquared;
    private static BigInteger lambda;
    private static BigInteger g;
    private static BigInteger mu;

    public Paillier(BigInteger cNv, BigInteger cNc, BigInteger cb, BigInteger cp, BigInteger cq) {
        this.Nv = cNv;
        this.Nc = cNc;
        this.b = cb;
        this.p = cp;
        this.q = cq;

        keyGeneration();
    }

    public static BigInteger getn() {
        return n;
    }

public static void keyGeneration() {
    n = p.multiply(q);
    nsquared = n.multiply(n);

    lambda = carmichaelFunction();

    g = new BigInteger("1578485334874745");
    BigInteger gModPow = LFunction(g.modPow(lambda, nsquared));

    mu = gModPow.modInverse(n);

    /**System.out.print("Encryption key: (" + n + ", " + g + ") \n");
     System.out.print("Decryption key: (" + lambda + ", " + mu + ") \n");**/
}

public static BigInteger carmichaelFunction() {
    BigInteger product = p.subtract(BigInteger.ONE).multiply(q.subtract(BigInteger.ONE));
    BigInteger lamb = product.divide(p.subtract(BigInteger.ONE).gcd(q.subtract(BigInteger.ONE)));

    return lamb;
}

public static BigInteger LFunction(BigInteger u) {
    BigInteger L = u.subtract(BigInteger.ONE).divide(n);

    return L;
}

public BigInteger encryption(int[] votes) {
    BigInteger m = BigInteger.ZERO;

    for (BigInteger i = BigInteger.ZERO; i.compareTo(Nc) == -1; i = i.add(BigInteger.ONE)) {
        if (votes[i.intValue()] == 1)
            m = m.add(b.pow(i.intValue()));
    }

    Log.d("MESSAGE","Message to be encrypted "+ m);
    Log.d("n ", n.toString());
    Log.d("nsquared ", nsquared.toString());

    BigInteger r = randomZStarN();
    Log.d("RandomZStarN ", r.toString());

    BigInteger gmi = g.pow(m.intValue());
    Log.d("gmi ", gmi.toString());
    BigInteger rin = r.pow(n.intValue());
    Log.d("rin ", rin.toString());
    BigInteger gMr = gmi.multiply(rin);
    Log.d("gMr ", gMr.toString());
    BigInteger c = gMr.mod(nsquared);
    Log.d("Ciphertext ", c.toString());

    return c;
}

public static BigInteger randomZStarN() {
    BigInteger r;

    do {
        r = new BigInteger(n.bitLength(), new Random());
    } while (r.compareTo(n) >= 0 || r.gcd(n).intValue() != 1);

    return r;
}
}

In the encryption method, the variable rin is not being calculated and logged and so are the variables after it. The Android application then stops responding. I am assuming it's because c is returning a null value.

The output is as follows and the log d doesn't display the value of rin:

01-15 11:03:22.593 3468-3468/com.example.oct30th D/MESSAGE: Message to be encrypted 1
01-15 11:03:22.593 3468-3468/com.example.oct30th D/n: 1291588321
01-15 11:03:22.593 3468-3468/com.example.oct30th D/nsquared: 1668200390943599041
01-15 11:03:22.594 3468-3468/com.example.oct30th D/RandomZStarN: 75325222
01-15 11:03:22.594 3468-3468/com.example.oct30th D/gmi: 1578485334874745

Can someone please help?

user8777308
  • 1
  • 5
  • It doesn't continue because `75325222.pow(1291588321)` takes forever to calculate. – Andreas Jan 15 '18 at 07:31
  • 3
    The result of that calculation is a number with more than 10 **billion** digits. Approx: `1.21e10173764252` – Andreas Jan 15 '18 at 07:44
  • @Andreas Any solution to this problem? – user8777308 Jan 15 '18 at 07:58
  • @user8777308: check your algorithm. It is very unlikely that such a huuuuge number is correct or required. It would make encryption almost impossible. – Rudy Velthuis Jan 15 '18 at 15:22
  • FWIW, on my system, `75325222.pow(1291588)` took approx. **19 seconds**. But `75325222.pow(12915880)` (10 x the exponent) took **527 seconds**. The numbers get larger and larger, which makes multiplying them slower and slower (even when they use Karatsuba or Toom-Cook algorithms). You can imagine that `75325222.pow(1291588321)` might take ages to complete and could also run out of memory, on many systems (the calculation requires several similarly large numbers to be in memory at the same time). – Rudy Velthuis Jan 15 '18 at 23:35
  • @RudyVelthuis What do you suggest since this calculation needs to be excuted with an Android app ? Thank you. – user8777308 Jan 16 '18 at 10:27
  • @user8777308: I already said what I would suggest:check your algorithm. It is very unlikely that it is correct, if it must calculate such huge values. Does it perhaps need modPow instead? That is **much** faster, as it keeps the values below the modulus, so no extremely big values have to be multiplied. – Rudy Velthuis Jan 16 '18 at 18:59

0 Answers0