java - 飞哥菲亚特沙米尔实现

Question

我正在用 Java 实现 Fiege Fiat Shamir 识别方案，而且我很确定它在数学方面很好。 (我已经检查了很多次)但它从来没有用过(当调用检查时，它几乎总是错误的，即使用应该有效的数字调用也是如此)。之前我已经让它在没有序列的情况下工作，(k 值为 1)，但现在它不起作用。帮助!

public class ZKPTimeTrials {

public static int gcd(int p, int q) {
    if (q == 0) return p;
    else return gcd(q, p % q);
}

public static int randomR(int min, int max) {
    Random randgen = new Random();
    return randgen.nextInt((max - min) + 1) + min;
}

public static int getRandomCoprime(int n) {
    int result = n;
    while (gcd(n, result) != 1) {
        result = randomR(2, n-1);
    }
    return result;
}

public static int[] makeSi(int k, int n) {
    int[] result = new int[k];
    for(int i = 0; i < result.length; i++) {
        result[i] = getRandomCoprime(n);
    } 
    return result;
}


public static int[] makeVi(int[] si, int n) {
    int[] result = new int[si.length];
    for(int i = 0; i < result.length; i++) {
        result[i] = (si[i] * si[i]) % n;
    } 
    return result;
}

public static int[] makeEi(int k) {
    int[] result = new int[k];
    for(int i = 0; i < k; i++) {
        result[i] = randomR(0, 1);
    }
    return result;
}

public static int makeY(int r, int[] ei, int[] si, int n) {
    int result = r;
    for(int i = 0; i < si.length; i++) {
        result *= (int) Math.pow(si[i], ei[i]);
    }
    return result % n;
}

public static boolean check(int n, int x, int y, int[] ei, int[] vi) {
    int signBit = ZKPTimeTrials.randomR(0, 1);
    if(signBit == 0) {
        signBit = -1;
    }
    int shouldY = x * signBit;
    for(int i = 0; i < vi.length; i++) {
        shouldY *= (int) Math.pow(vi[i], ei[i]);
    }
    return ((y * y) % n) == shouldY % n;
}

public static void main(String args[]) {
    int n = 71 * 7;
    int t = 50;
    int k = 10;
    int[] si = makeSi(k, n);
    int[] vi = makeVi(si, n);

    int r = randomR(2, n-1);
    int ei[] = makeEi(k);
    int s = randomR(0, 1);
    if(s == 0) {
        s = -1;
    }
    int x = (s * r * r) % n;
    int y = makeY(r, ei, si, n);
    for(int i = 0; i < si.length; i++) System.out.print(ei[i] + " ");
    System.out.println();
    for(int i = 0; i < si.length; i++) System.out.print(si[i] + " ");
    System.out.println(check(n, x, y, ei, vi));
}

}

Answer 1

第一个问题是 makeY 中的整数溢出并检查:在这两个函数中，'result' 很可能溢出，因为您先构建产品，然后再减少模 n。尝试在每次乘法后减少 mod n 以保持“结果”较小。

比如在makeY中，写:

int result = r % n;
for (int i = 0; i < si.length; i++) {
    if (ei[i] == 1)
        result = (result * si[i]) % n;
}
return result;

(我还删除了 Math.pow() 以使其更具可读性和效率，但这不是错误。)

第二个问题是检查函数的逻辑:不需要 signBit 变量，但您应该检查 y*y 是否等于 shouldY 或 -shouldY。

public static boolean check(int n, int x, int y, int[] ei, int[] vi) {
    int shouldY = x % n;
    for (int i = 0; i < vi.length; i++) {
        if (ei[i] == 1)
            shouldY = (shouldY * vi[i]) % n;
    }
    return (y*y - shouldY) % n == 0 || (y*y + shouldY) % n == 0;
}

通过这些小的更正，我设法让您的代码运行起来。希望对您有所帮助...