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實施

回答

相關問題