Feige-Fiat-Shamir 识别协议 Java

Question

我正在尝试实现"应用密码学手册"一书中描述的Feige-Fiat-Shamir识别方案(第410页，第10.4.2节(。我有一个代码，但问题是有时它成功但有时它失败。任何人都可以帮助我找到此代码中的错误吗？谢谢。

    public static void main(String[] args) throws Exception {
    BigInteger p = BigInteger.probablePrime(16, new Random());
    BigInteger q = BigInteger.probablePrime(16, new Random());
    int k = 10;  // Receive k
    BigInteger trustedN = p.multiply(q);
    List<BigInteger> randomInts = new ArrayList<>();    //s1,s2...sk
    BitSet randomBits = new BitSet(k);  // b1,b2..bk
    List<BigInteger> listV = new ArrayList<>();
    Random rand = new Random();
    /*
    Choose k positive numbers less than trustedN.
    Choose k bits 0 or 1
     */
    for (int i = 0; i < k; i++) {
        // Generate random big ints less than trustedN
        randomInts.add(new BigInteger(trustedN.bitLength() + 1, rand).mod(trustedN));
        randomBits.set(i, rand.nextBoolean());
        // (-1)^bi
        BigInteger minus1pow = (((new BigInteger("-1")).pow(randomBits.get(i) ? 1 : 0))).mod(trustedN);
        // (s^2)^(-1)
        BigInteger randomIntPow = (randomInts.get(i).pow(2)).modInverse(trustedN);
        // vi = (-1)^bi * (s^2)^(-1)
        listV.add((minus1pow.multiply(randomIntPow)).mod(trustedN));
    }
    // Random r
    BigInteger randomR = new BigInteger(trustedN.bitLength() + 1, rand).mod(trustedN);
    // Random bit index
    int bitIndex = rand.nextInt(randomBits.length() + 1);
    // Calculate x
    BigInteger x = ((new BigInteger("-1")).pow(randomBits.get(bitIndex) ? 1 : 0).mod(trustedN)).multiply((randomR.pow(2)).mod(trustedN)).mod(trustedN);
    // Let pretend it was randomly selected vector (e1,e2,e3...)
    String eBits = "1100011010";

    BigInteger totalMultS = new BigInteger("1");
    for (int i = 0; i < k; i++) {
        totalMultS = totalMultS
                .multiply(randomInts.get(i).pow(eBits.charAt(i) == '1' ? 1 : 0));
    }
    totalMultS = totalMultS.mod(trustedN).multiply(randomR.mod(trustedN)).mod(trustedN);
    BigInteger y = totalMultS;

    BigInteger totalMultV = new BigInteger("1");
    for (int i = 0; i < k; i++) {
        totalMultV = totalMultV
                .multiply(listV.get(i).pow(eBits.charAt(i) == '1' ? 1 : 0));
    }
    totalMultV = totalMultV.mod(trustedN);
    BigInteger z = (y.pow(2).mod(trustedN)).multiply(totalMultV).mod(trustedN);

    if (z.toString().equals(x.toString())){
        System.out.println("SUCCESS");
    }
    else {
        System.out.println("FAIL");
        System.out.println("x: " + x.toString());
        System.out.println("z: " + z.toString());
    }

}

Answer 1

我已经找到了解决方案。问题出在最后一个条件下。请参阅代码：

    public static void main(String[] args) throws Exception {
    BigInteger p = BigInteger.probablePrime(4, new Random());
    BigInteger q = BigInteger.probablePrime(4, new Random());
    System.out.println("p: " + p.toString());
    System.out.println("q: " + q.toString());
    int k = 3;  // Receive k
    BigInteger trustedN = p.multiply(q);
    System.out.println("n: " + trustedN.toString());
    List<BigInteger> randomInts = new ArrayList<>();    //s1,s2...sk
    BitSet randomBits = new BitSet(k);  // b1,b2..bk
    List<BigInteger> listV = new ArrayList<>();
    Random rand = new Random();
    /*
    Choose k positive numbers less than trustedN.
    Choose k bits 0 or 1
     */
    System.out.print("random s: ");
    for (int i = 0; i < k; i++) {

        BigInteger si = new BigInteger(trustedN.bitLength() + 1, rand).mod(trustedN);
        while (si.gcd(trustedN).intValue() != 1){
            si = new BigInteger(trustedN.bitLength() + 1, rand).mod(trustedN);
        }
        // Generate random big ints less than trustedN
        randomInts.add(si);
        randomBits.set(i, rand.nextBoolean());
        // (-1)^bi
        System.out.print(randomInts.get(i) + " " + randomBits.get(i) + " ");
        BigInteger minus1pow = (((new BigInteger("-1")).pow(randomBits.get(i) ? 1 : 0)));
        // (s^2)^(-1)
        BigInteger randomIntPow = minus1pow.multiply(randomInts.get(i).pow(2)).modInverse(trustedN);
        // vi = (-1)^bi * (s^2)^(-1)//            listV.add((minus1pow.multiply(randomIntPow)).mod(trustedN));
        listV.add(randomIntPow);
    }
    System.out.print("nlist v: ");
    for (BigInteger bi:
         listV) {
        System.out.print(bi.toString() + " ");
    }
    System.out.println();
    // Random r
    BigInteger randomR = new BigInteger(trustedN.bitLength() + 1, rand).mod(trustedN);
    System.out.println("r: " + randomR.toString());
    // Random bit index
    int bitIndex = (int) (Math.random() * ( randomBits.length()  ));
    System.out.println("bitIndex: " + bitIndex + " bit value: " + randomBits.get(bitIndex));
    // Calculate x//        BigInteger x = ((new BigInteger("-1")).pow(randomBits.get(bitIndex) ? 1 : 0).mod(trustedN)).multiply((randomR.pow(2)).mod(trustedN)).mod(trustedN);
    BigInteger x = (((new BigInteger("-1")).pow(randomBits.get(bitIndex) ? 1 : 0)).multiply((randomR.pow(2)))).mod(trustedN);
    // Let pretend it was randomly selected vector (e1,e2,e3)
    String eBits = "100";

    BigInteger totalMultS = new BigInteger("1");
    for (int i = 0; i < k; i++) {
        totalMultS = totalMultS
                .multiply(randomInts.get(i).pow(eBits.charAt(i) == '1' ? 1 : 0));
    }
    BigInteger y = totalMultS.multiply(randomR.mod(trustedN)).mod(trustedN);
    System.out.println("y: " + y.toString());

    BigInteger totalMultV = new BigInteger("1");
    for (int i = 0; i < k; i++) {
        totalMultV = totalMultV
                .multiply(listV.get(i).pow(eBits.charAt(i) == '1' ? 1 : 0));
    }
    System.out.println("total mult v: " + totalMultV);

    if ((z.toString().equals(x.toString()) || z.toString().equals(x.negate().mod(trustedN).toString()))
            && !z.toString().equals("0")){
        System.out.println("SUCCESS");
    }
    else {
        System.out.println("FAIL");
        System.out.println("x: " + x.toString());
        System.out.println("z: " + z.toString());
    }
}