實現不可否認簽名方案：隨機e1和e2在驗證協議中未能計算出正確的d

Question

首先檢查不可否認的簽名方案驗證算法。

比在那裏有第一步告訴選擇兩個隨機x1和x2。

但驗證算法有時會有效，有時會失敗，這取決於兩個隨機數。 （算法在java中正確實現）。

對於相同的輸入，如果我們運行算法多次，有時候它的簽名是匹配的，有時候不是，最後的比較失敗。

Plz幫助我。我被困在這裏（缺乏數學）。

Answer 1

其實這是一個簽名方案，在紙上它令人困惑，但現在我已經找出解決方案。

解決方案代碼是：讓我知道你是否需要我解釋這段代碼。

import java.lang.*; 
import java.util.*; 
import java.math.*; 
import java.security.MessageDigest; 
import java.nio.file.*; 
import java.io.*; 
import java.security.*; 

class UndeniableSignature { 

    int Q;   // prime 
    int P;   // prime of form P = 2Q + 1 
    BigInteger G; // Generator of Z*P 
    int D;   // private key belongs to [2 ... Q-1] 
    BigInteger Y; // G^D (mod P) 
    int invD;  // D^-1 (mod Q) 
    Random rand = new SecureRandom(); // uniform random generator 

    public int[] extendedEuclidean(int a, int b) { 
     if(b==0) { 
      int[] arr=new int[3]; 
      arr[0] = a; 
      arr[1] = 1; 
      arr[2] = 0; 
      return arr; 
     } 
     int[] subResult = extendedEuclidean(b,a%b); 
     int[] arr=new int[3]; 
     arr[0] = subResult[0]; 
     arr[1] = subResult[2]; 
     arr[2] = subResult[1] - (a/b) * subResult[2]; 
     return arr; 
    } 

    public int secureRandom(int max) { 
     return rand.nextInt(max); 
    } 

    public BigInteger getGenerator(BigInteger p, BigInteger q){ 
     BigInteger generator = BigInteger.ZERO; 
     BigInteger exp = p.subtract(BigInteger.ONE).divide(q); 
     for(int i=2;i<p.intValue()-1;i++) { 
      generator = BigInteger.valueOf(i); 
      generator = generator.modPow(exp, p); 
      if(!generator.equals(BigInteger.ONE)) return generator; 
     } 
     // do { 
     // generator = BigInteger.valueOf(this.secureRandom(p.intValue())); 
     // generator = generator.modPow(exp, p); 
     // } while(generator.equals(BigInteger.ONE)); 
     return generator; 

     // BigInteger generator = BigInteger.ZERO; 
     // for(long i = 2; i < p.intValue()-1; i++) 
     // { 
     //  generator = BigInteger.valueOf(i); 
     //  if(generator.modPow(BigInteger.valueOf(2), p).equals(BigInteger.ONE)) continue; 
     //  if(generator.modPow(q, p).equals(BigInteger.ONE)) continue; 
     //  else return generator; 
     // } 
     // return generator; 
    } 

    public String readMessageFile(String filename) { 
     try { 
      return new String(Files.readAllBytes(Paths.get(filename))); 
     } catch(Exception ex) { 
      System.out.println("ERR: Can't read file."); 
     } 
     return null; 
    } 

    public int[] readSignatureFile(String filename) { 
     InputStream is=null; 
     DataInputStream dis=null; 
     try { 
      is = new FileInputStream(filename); 
      dis = new DataInputStream(is); 
      ArrayList intList = new ArrayList(); 
      int count = 0; 
      while(dis.available()>0) { 
       intList.add(dis.readInt()); 
      } 
      int[] data = new int[intList.size()]; 
      for(int i=0;i<data.length;i++) { 
       data[i] = (int)intList.get(i); 
      } 
      dis.close(); 
      is.close(); 
      return data; 
     } catch(Exception ex) { 
      System.out.println("ERR: Can't read file."); 
     } 
     return null; 
    } 

    public static void writeSignatureFile(String filename, int[] contents) { 
     FileOutputStream fos=null; 
     DataOutputStream dos=null; 
     try { 
      fos = new FileOutputStream(filename); 
      dos = new DataOutputStream(fos); 
      for(int i=0;i<contents.length;i++) { 
       dos.writeInt(contents[i]); 
      } 
      dos.flush(); 
      dos.close(); 
      fos.close(); 
     } catch(Exception ex) { 
      System.out.println("ERR: Can't write to file."); 
     } 
    } 

    public void keyGeneration() { 
     System.out.println("UNDENIABLE SIGNATURE SCHEME"); 
     System.out.println("- KEY GENERATION"); 
     System.out.print("\tEnter prime P (such that P=2Q+1) : "); 
     this.P = new Scanner(System.in).nextInt(); 
     this.Q = (this.P - 1)/2; 
     System.out.println("\tPrime Q is "+this.Q+"."); 
     this.G = this.getGenerator(BigInteger.valueOf(this.P),BigInteger.valueOf(this.Q)); 
     System.out.println("\tGenerator G of group Z*("+this.P+") is "+this.G+"."); 
     System.out.print("\tEnter private key D (belongs to Z*P) :"); 
     this.D = new Scanner(System.in).nextInt(); 
     while(this.D <= 0 || this.D >= this.P) { 
      System.out.println("\tInvalid private key selected, please try again."); 
      System.out.print("\tEnter private key D (belongs to Z*P) :"); 
      this.D = new Scanner(System.in).nextInt(); 
     } 
     this.Y = this.G.modPow(BigInteger.valueOf(this.D), BigInteger.valueOf(this.P)); 
     System.out.println("\tG^D(mod P) = "+this.Y+"."); 
     System.out.println("\tPublic Key [P, G, Y] is ["+this.P+", "+this.G+", "+this.Y+"]."); 
     System.out.println("\tPrivate Key [D] is ["+this.D+"]."); 
     int[] g = this.extendedEuclidean(this.D, this.Q); 
     this.invD = g[1]; 
     if(this.invD < 0) { 
      this.invD = this.Q - Math.abs(this.invD); 
      System.out.println("\tInverse was negative."); 
     } 
     System.out.println("\tInverse of D (mod Q) is "+this.invD+"."); 
    } 

    public void messageSigning(String message) { 
     int[] signatureBytes = new int[message.length()]; 
     for(int i=0;i<message.length();i++) { 
      BigInteger m = BigInteger.valueOf((int)message.charAt(i));//this.H(message.charAt(i)+""); 
      BigInteger s = m.pow(this.D).mod(BigInteger.valueOf(this.P)); 
      signatureBytes[i] = s.intValue(); 
      // System.out.println("\tchar:"+message.charAt(i)+", m:"+m+", s:"+s+", S:"+signatureBytes[i]); 
     } 
     System.out.print("\tEnter signature filename : "); 
     String signatureFilename = new Scanner(System.in).nextLine(); 
     this.writeSignatureFile(signatureFilename, signatureBytes); 
     System.out.println("\tSignature is successfully generated."); 
    } 

    // see the condition proof for w=W for solution of problem 

    public boolean signatureVerification(String message, int[] signature) { 

     for(int i=0;i<message.length();i++) { 

      // rand=new Random(); 
      // int x1 = this.secureRandom(this.Q-1); 
      // while(x1<=1) x1 = this.secureRandom(this.Q-1); 
      // int x2 = this.secureRandom(this.Q-1); 
      // while(x2<=1) x2 = this.secureRandom(this.Q-1); 

      int x1 = 38, x2 = 397; 

      BigInteger S = BigInteger.valueOf(signature[i]); 

      BigInteger s = S.pow(x1); 
      BigInteger y = this.Y.pow(x2); 
      BigInteger z = s.multiply(y).mod(BigInteger.valueOf(this.P)); 

      BigInteger w = signerChallengeForVerification(z); 

      BigInteger M = BigInteger.valueOf((int)message.charAt(i));//this.H(message.charAt(i)+""); 
      BigInteger m = M.pow(x1); 
      BigInteger g = this.G.pow(x2); 
      BigInteger mg = m.multiply(g); 
      BigInteger W = mg.mod(BigInteger.valueOf(this.P)); 
      // System.out.println("\ti:"+i+", char:"+message.charAt(i)+", m:"+M+", s:"+S); 
      // System.out.println("\t\tz:"+z+", w:"+w+" , W:"+W); 
      if(!w.equals(W)) { 
       return false; 
      } 
     } 

     return true; 

    } 

    public boolean disavowalProtocol(String message, int[] signature) { 

     int x1 = 38, x2 = 397; 
     BigInteger response1 = BigInteger.ZERO; 
     BigInteger response2 = BigInteger.ZERO; 
     // verification 1 
     for(int i=0;i<message.length();i++) { 

      BigInteger S = BigInteger.valueOf(signature[i]); 

      BigInteger s = S.pow(x1); 
      BigInteger y = this.Y.pow(x2); 
      BigInteger z = s.multiply(y).mod(BigInteger.valueOf(this.P)); 

      BigInteger w = signerChallengeForVerification(z); 

      BigInteger M = BigInteger.valueOf((int)message.charAt(i));//this.H(message.charAt(i)+""); 
      BigInteger m = M.pow(x1); 
      BigInteger g = this.G.pow(x2); 
      BigInteger mg = m.multiply(g); 
      BigInteger W = mg.mod(BigInteger.valueOf(this.P)); 
      // System.out.println("\ti:"+i+", char:"+message.charAt(i)+", m:"+M+", s:"+S); 
      // System.out.println("\t\tz:"+z+", w:"+w+" , W:"+W); 
      if(!w.equals(W)) { 
       response1 = w; 
       break; 
      } 

     } 

     if(response1.equals(BigInteger.ZERO)) { 
      return false; // signature is not forgery bcoz signature is matched 
     } 

     // verification 2 
     for(int i=0;i<message.length();i++) { 

      BigInteger S = BigInteger.valueOf(signature[i]); 

      BigInteger s = S.pow(x1); 
      BigInteger y = this.Y.pow(x2); 
      BigInteger z = s.multiply(y).mod(BigInteger.valueOf(this.P)); 

      BigInteger w = signerChallengeForVerification(z); 

      BigInteger M = BigInteger.valueOf((int)message.charAt(i));//this.H(message.charAt(i)+""); 
      BigInteger m = M.pow(x1); 
      BigInteger g = this.G.pow(x2); 
      BigInteger mg = m.multiply(g); 
      BigInteger W = mg.mod(BigInteger.valueOf(this.P)); 
      // System.out.println("\ti:"+i+", char:"+message.charAt(i)+", m:"+M+", s:"+S); 
      // System.out.println("\t\tz:"+z+", w:"+w+" , W:"+W); 
      if(!w.equals(W)) { 
       response2 = w; 
       break; 
      } 

     } 

     if(response2.equals(BigInteger.ZERO)) { 
      return false; // signature is not forgery bcoz signature is matched 
     } 

     // forgery validation now it comes here only when one of above validation is failed 

     BigInteger A = response1.divide(this.G.pow(x2)).pow(x1).mod(BigInteger.valueOf(this.P)); 
     BigInteger B = response2.divide(this.G.pow(x1)).pow(x2).mod(BigInteger.valueOf(this.P)); 

     return A.equals(B); // signature is forgery if A == B 
    } 

    public BigInteger signerChallengeForVerification(BigInteger z) { 
     // System.out.println("\tchallange: "+z+", invD:"+this.invD+", d:"+(z.pow(this.invD).mod(BigInteger.valueOf(this.P)))); 
     return z.pow(this.invD).mod(BigInteger.valueOf(this.P)); 
    } 

} 

class Program { 

    public static void main(String[] args) { 
     String msgFilename, signatureFilename, message; 
     UndeniableSignature scheme = new UndeniableSignature(); 
     scheme.keyGeneration(); 
     int choice = 0; 
     do { 
      System.out.println(); 
      System.out.println("- OPERATIONS"); 
      System.out.println("\t1. Sign message"); 
      System.out.println("\t2. Verify signature"); 
      System.out.println("\t3. Disavowal protocal"); 
      System.out.println("\t4. Exit"); 
      System.out.print("\tChoice : "); 
      choice = new Scanner(System.in).nextInt(); 
      System.out.println(); 
      switch(choice) { 
       case 1: 
        System.out.println("- MESSAGE SIGNING"); 
        System.out.print("\tEnter message filename : "); 
        msgFilename = new Scanner(System.in).nextLine(); 
        message = new String(scheme.readMessageFile(msgFilename)); 
        scheme.messageSigning(message); 
       break; 
       case 2: 
        System.out.println("- SIGNATURE VERIFICATION"); 
        System.out.print("\tEnter message filename : "); 
        msgFilename = new Scanner(System.in).nextLine(); 
        System.out.print("\tEnter signature filename : "); 
        signatureFilename = new Scanner(System.in).nextLine(); 
        message = scheme.readMessageFile(msgFilename); 
        int[] signatureBytes = scheme.readSignatureFile(signatureFilename); 
        if(scheme.signatureVerification(message, signatureBytes)) { 
         System.out.println("\tSignature IS valid."); 
        } else { 
         System.out.println("\tSignature is NOT valid."); 
        } 
       break; 
       case 3: 
        System.out.println("- DISAVOWAL VERIFICATION"); 
        System.out.print("\tEnter message filename : "); 
        msgFilename = new Scanner(System.in).nextLine(); 
        System.out.print("\tEnter signature filename : "); 
        signatureFilename = new Scanner(System.in).nextLine(); 
        message = scheme.readMessageFile(msgFilename); 
        signatureBytes = scheme.readSignatureFile(signatureFilename); 
        if(scheme.disavowalProtocol(message, signatureBytes)) { 
         System.out.println("\tSignature IS forgery."); 
        } else { 
         System.out.println("\tSignature is NOT forgery."); 
        } 
       break; 
       case 4: 
        System.out.println("- BYE BYE"); 
       break; 
      } 
     } while(choice!=4); 
    } 

} 

感謝：d