[SecureProgramming] DigitalSignSignature

* Elliptical Curve Digital Signature Algorithm

[Step01] 임의의 Eliptic Curve를 선택합니다.
[Step02] 임의의 자연수 d를 비밀키로 선택합니다. (Elliptic Curve의 차수 (n)보다 작아야합니다.)
[Step03] 비밀키와 Generator Point (G)를 곱해 공개키 Q Point를 생성합니다.
[Step04] Elliptic Curve의 차수 (n)보다 작은 임의의 자연수 K를 선택합니다. (Elliptic Curve의 차수 (n)보다 작아야합니다.)
[Step05] kG를 계산해 나온 좌표의 x 좌표를 n으로 나눈 나머지를 r이라고 합니다.
[Step06] 서명할 메시지를 자연수로 m이라고 가정합니다.
[Step07] Hash를 수행한 메시지 <라고 합니다. (메시지에 Hash를 수행해 Bit의 수가 차수의 Bit수를 넘지 않게합니다.) 

[Step081 k-l(x+ rd) mod n을 구해 이를 s라고 합니다.
[Step09] r 또는 5가 0이라면 다시 K를 생성하고 아니면 (r, s)이 서명값이 됩니다.

* 증명
    u = zs^-1 mod n
    v = rs-1 mod n
    P = uG + vQ = uG + vdG      → Q = dG
    = (u + vd)G
    =（zs^-1 + rs^-1d)G
    = ( z+ rd )s^(-1)G
    = (z + rd)(k^-1(z+ rd))^(-1)G
    =（ z + rd ）（ z + rd）^(-1)(k^-1)^(-1)G
    = kG
    P(x) = r mod n인 경우 Signature가 유효합니다

 

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Random;

import static java.lang.Math.max;

public class ECDSA {

    private ECPoint G;
    private BigInteger n;
    private int nOfBit;

    public ECDSA(ECPoint g, BigInteger n) {
        G = g;
        this.n = n;
        this.nOfBit = n.bitLength();
    }

    public BigInteger modInverse(BigInteger value) {
        // mod n에 대한 나머지 역원을 구한다.
        return value.modInverse(n);
    }

    public String hash(String text) {
        MessageDigest md = null;
        try {
            md = MessageDigest.getInstance("SHA-256");
            md.update(text.getBytes());
            return bytesToHex(md.digest());
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        return null;
    }

    private String bytesToHex(byte[] bytes) {
        StringBuilder builder = new StringBuilder();
        for (byte b : bytes) {
            builder.append(String.format("%02x", b));
        }
        return builder.toString();
    }

    public Point sign(BigInteger m, BigInteger d) {
        int mBit = m.bitLength();
        BigInteger z = m.shiftRight(max(mBit - nOfBit, 0));
        System.out.println("mBit: " + mBit);
        System.out.println("Shift Right: " + max(mBit - nOfBit, 0));
        BigInteger k, s, r;
        ECPoint P;
        do {
            do {
                k = BigInteger.probablePrime(32, new Random());
                P = G.multiplyOperation(k);
                r = P.getX().mod(n);
            } while (r.equals(BigInteger.ZERO));
            s = modInverse(k).multiply(r.multiply(d).add(z));
            s = s.mod(n);
        } while (s.equals(BigInteger.ZERO));
        return new Point(r, s);
    }

    public boolean verify(BigInteger m, Point sig, ECPoint Q) {
        BigInteger r = sig.getX();
        BigInteger s = sig.getY();
        if (r.compareTo(BigInteger.ONE) < 0 || r.compareTo(n) >= 0
            || s.compareTo(BigInteger.ONE) < 0 || s.compareTo(n) >= 0) {
            return false;
        }
        int mBit = m.bitLength();
        BigInteger z = m.shiftRight(max(mBit - nOfBit, 0));
        BigInteger u1 = m.multiply(modInverse(s)).mod(n);
        BigInteger u2 = r.multiply(modInverse(s)).mod(n);
        ECPoint P = G.multiplyOperation(u1).addOperation(Q.multiplyOperation(u2));
        if (P.getY().equals(G.getField().getP())) {
            System.out.println("P is O");
            return false;
        }
        return P.getX().subtract(r).mod(n).equals(BigInteger.ZERO);
    }

    @Override
    public String toString() {
        return "ECDSA{" +
            "G=" + G +
            ", n=" + n +
            ", nOfBit=" + nOfBit +
            '}';
    }

    public int mul(int num1, int num2){
        return num1*num2;
    }
}

 

import java.math.BigInteger;

public class Point {

    private BigInteger x;
    private BigInteger y;

    public Point(BigInteger x, BigInteger y) {
        this.x = x;
        this.y = y;
    }

    public BigInteger getX() {
        return x;
    }

    public BigInteger getY() {
        return y;
    }

    @Override
    public String toString() {
        return "Point{" +
            "x=" + x +
            ", y=" + y +
            '}';
    }
}

 

import java.math.BigInteger;
import java.util.Random;

public class DigitalSignTest {

    private static final String a = "FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC".replace(
        " ", "");
    private static final String b = "5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B".replace(
        " ", "");
    private static final String p = "FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF".replace(
        " ", "");
    private static final String gX = "6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296".replace(
        " ", "");
    private static final String gY = "4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5".replace(
        " ", "");
    private static final String n = "FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551".replace(
        " ", "");

    public static void main(String[] args) {
        System.out.println("[Step01] Elliptic Curve를 선택합니다.");
        EllipticCurve ellipticCurve = new EllipticCurve(new BigInteger(a, 16), new BigInteger(b, 16), new BigInteger(p, 16));
        System.out.println(ellipticCurve);
        System.out.println("===================================================================================================================================================================================================================================================================");

        System.out.println("[Step02] 임의의 자연수 d를 비밀키로 선택합니다.");
        BigInteger d = BigInteger.probablePrime(32, new Random());
        System.out.println("[Private Key] d: " + d);
        System.out.println("===================================================================================================================================================================================================================================================================");

        System.out.println("[Step03] 비밀키 d와 Generator Point (G)를 곱해 공개키 Q를 생성합니다.");
        ECPoint G = new ECPoint(new BigInteger(gX, 16), new BigInteger(gY, 16), ellipticCurve);
        ECPoint Q = G.multiplyOperation(d);
        System.out.println("[Generator Point] G: " + G);
        System.out.println("[Public Key] Q = dG = " + Q);
        System.out.println("===================================================================================================================================================================================================================================================================");

        System.out.println("ECDSA");
        ECDSA ecdsa = new ECDSA(G, new BigInteger(n, 16));
        System.out.println(ecdsa);
        System.out.println("===================================================================================================================================================================================================================================================================");

        System.out.println("[Step07] Hash를 수행한 메시지를 z라고 합니다.");
        String message = "Hello";
        String z = ecdsa.hash(message);
        System.out.println("[Message] m: " + message);
        System.out.println("[Hash Message] z: " + z);
        System.out.println("===================================================================================================================================================================================================================================================================");

        System.out.println("[Step07] 서명을 수행합니다.");
        Point sign = ecdsa.sign(new BigInteger(z, 16), d);
        System.out.println("[Signature] " + sign);
        System.out.println("r: " + sign.getX());
        System.out.println("s: " + sign.getY());
        System.out.println("===================================================================================================================================================================================================================================================================");

        boolean verify = ecdsa.verify(new BigInteger(z, 16), sign, Q);
        System.out.println("[Verify]");
        System.out.println(verify);
    }
}

 

 

https://github.com/l2yujw/SecureProgramming/tree/main/digital_sign_signature