-1

I need to do a very large calculation in a blind signature scheme to get a blinded token. I have tried this in java using the BigInteger class. I believe my current code is correct as it runs but ends up throwing an exception as the number would overflow the supported range.

The calculation I initially tried shown below.

BigInteger blindedToken = hashedToken.multiply(randomElementDecimal.pow(formattedValue.multiply(BigInteger.valueOf(3))));

This cannot work as BigInteger pow() must take an int value. Therefore, I used my own Helpers class to do this.

class Helpers { 
    public static BigInteger pow(BigInteger base, BigInteger exponent) {
          BigInteger result = BigInteger.ONE;
          while (exponent.signum() > 0) {
            if (exponent.testBit(0)) result = result.multiply(base);
            base = base.multiply(base);
            exponent = exponent.shiftRight(1);
          }
          return result;
        }
}

So the updated calculation looks like this.

BigInteger blindedToken = Helpers.pow(randomElementDecimal, formattedValue.multiply(BigInteger.valueOf(3)));
blindedToken = blindedToken.multiply(hashedToken);
System.out.println(blindedToken);

Which worked out as

Z = 941180828215645688530913292077221835722091184537123007963440625299702649269*1631434789^(222347888349073615524064151195238689903425040008399562092481278391150317944919*3)

Z = h(Tid)*R^(public exponent * formatting value)

I have since made the numbers shorted by changing the hashed values from the result of SHA-256 to SHA-1 but I am still facing issues.

It seems to run forever and I assume it will overflow because the calculation is so massive.

I was just wondering if there was another way around calculating this and storing the value. Or if this will be supported in another language like Python?

luk2302
  • 55,258
  • 23
  • 97
  • 137
lb-99
  • 33
  • 5
  • 1
    What runs forever, what is the actual java statement that runs forever, what is the input, what is the expected output? Provide a [mcve]! – luk2302 Feb 04 '21 at 18:48
  • How are you planning to output the answer? The number of digits in the answer is more than the number of atoms in the known universe. – Dawood ibn Kareem Feb 04 '21 at 19:19

2 Answers2

2

Yes, to the power of that kind of number is going to take a few billion years on any hardware.

Usually, with crypto, all of this needs to go modulo something, and therein lies the rub. x^y % z, with y being some ungodly number, but z being of reasonable size, CAN be done quickly, but not with Math.pow.

rzwitserloot
  • 85,357
  • 5
  • 51
  • 72
  • [link](https://drive.google.com/file/d/1LCpQnxVj5h3e6sxDXD3mprx9HgZ-5bWL/view?usp=sharing) The paper I was attempting to reproduce can be found here. I have attempted to follow the calculation correctly (I could be wrong). The later equations do involve some form of modulo so I do not imagine those to be an issue. It is just the initial blinding of the token. – lb-99 Feb 04 '21 at 19:38
  • See also last page of that linked paper - a modulo is definitely involved. Note that if you somehow find god and ask god to calculate that in reasonable time, the resulting number is a few GB large. – rzwitserloot Feb 04 '21 at 21:51
  • I see that modulo is involved _after_ the blinded token generation, but I do not believe it is in the equation I am attempting to reproduce to get Z. I guess it is a matter of trying to reduce the size of the elements forming said equation. @rzwitserloot – lb-99 Feb 05 '21 at 11:18
1

Since this is about Cryptography, your missing point is that you need a modulus. In cryptography, we mostly work on finite moduli. It seems that you are trying to RSA like blind signatures, therefore you need power on modulus.

Them, use the modPow of the BigInteger Class and available since JDK1.1. This uses the modular version of the square-and multiply technique, it has O(log n) complexity where n is the exponent. In each step, the intermediate values can be at most m^2.

modPow(BigInteger exponent, BigInteger m)

Returns a BigInteger whose value is (thisexponent mod m). (Unlike pow, this method permits negative exponents.)

kelalaka
  • 5,064
  • 5
  • 27
  • 44
  • I can indeed get this to run using the `modPow()` function. The only problem I am having is that the initial blinded token generation `(Z)` _does not_ use modulus. The future equations in the protocol _do_ use a modulus so I think this is the only issue here. [link](https://drive.google.com/file/d/1LCpQnxVj5h3e6sxDXD3mprx9HgZ-5bWL/view) – lb-99 Feb 05 '21 at 11:23
  • The target is known, so you can use the modpow. – kelalaka Feb 05 '21 at 11:27
  • Would you be able to clarify how that is achieved please? I just can't seem to figure out the correct method of doing that :) @kelalaka – lb-99 Feb 05 '21 at 15:44
  • It is the (4) equation. – kelalaka Feb 05 '21 at 15:46