Feige菲亚特Shamir实施

我正在Java中实施Fiege Fiat Shamir身份识别方案，并且我非常确定这是数学方面的好方法。（我已经检查了许多次）但它永远不会起作用（当检查被调用时，即使用应该工作的数字调用它几乎总是错误的）。我已经在没有序列的情况下使用它（k的值为1），但现在它不起作用。帮帮我！Feige菲亚特Shamir实施

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)); 
} 

}

来源

2015-04-22 Haskelier

第一个问题是在makeY整数溢出和检查：在这两个功能的“结果”很可能溢出，因为你首先建立产品和减少模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;

（I也被去除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; 
}

有了这些小的更正，我设法让您的代码运行。希望它有帮助...

来源

2015-06-26 15:45:45 ash

Feige菲亚特Shamir实施

回答

相关问题