java - Feige Fiat Shamir实现

我正在用java实现fiege-fiat-shamir身份验证方案，我很确定它在数学上是很好的。（我检查过很多次）但它永远都不起作用（当调用check时，它几乎总是错误的，即使使用应该起作用的数字调用时也是如此）。我以前让它在没有序列的情况下工作，（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));
}

}

最佳答案

第一个问题是makeY和check中的整数溢出：在这两个函数中，“result”很可能溢出，因为您首先构建产品，然后减少模n每次乘法后尽量减少mod n，以保持“result”较小。
例如，在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（），使其更具可读性和效率，但这不是一个错误。）
第二个问题是check函数的逻辑：不需要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;
}

通过这些小小的修正，我成功地让你的代码运行起来。希望有帮助…

关于java - Feige Fiat Shamir实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29809025/