实施不可否认签名方案：随机 e1 和 e2 未能在验证协议中计算正确的 d

Question

首先检查不可否认的签名方案验证算法。

因为第一步告诉我们选择两个随机的 x1 和 x2。

但是验证算法有时有效，有时失败，这取决于两个随机数。（算法在 java 中正确实施）。

对于同一个输入，如果我们运行算法多次，有时签名匹配，有时不匹配，最后比较失败。

请帮助我。我被困在这里（缺乏数学）。

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

实施不可否认签名方案：随机 e1 和 e2 未能在验证协议中计算正确的 d

Implementing Undeniable Signature Scheme : random e1 and e2 failed to compute correct d in verify protocol

signature