[SecureProgramming] ECDHE

Elliptical Curve Diffie-Hellman Ephemeral

• DHE과 ECDHE 모두 Key를 한번의 접속에만 사용하고 폐기합니다.
• 도청자가 Key를 알아냈다고 하더라도, 그것으로 풀 수 있는 Message는 한번의 접속에만 해당합니다.
• 계산식 => y^2 = x^3 + ax + b / 4a^3 + 27b^2 ≠ 0

 

[Step 01] 곡선 위의 임의의 점 P, Q를 선택합니다.
                    P( x(p), y(p) )     Q( x(q), y(q) )
[Step 02] P, Q를 지나는 직선이 곡선과 만나는 직선을 정의합니다.
                    y = sx + d
[Step 03] P, Q, R을 지나는 직선의 기울기를 구합니다.
                    s = ( y(q) - y(p) ) / ( x(q) - x(p) )

ex) y^2 = x^3 -2x + 4
      P(-2, 0)    Q(0, 2)
      y = sx + d
      s = 1
      y = x + d
      d = 2
      y = x + 2
      (x + 2)^2 = x^3 -2x + 4
       x^3 - x^2 -6x = 0 => x(r) = 3

 

[Step 04] x(r)을 이용하여 y(r)을 구해줍니다.
[Step 05] R( x(r), y(r) )을 x축 대칭이동 합니다.

ex) x(r) = 3 => R(3, 5)
      -R(3, -5)

 

[Step 05] 접선과 만나는 점인 R( x(r), y(r) )을 x축 대칭이동 합니다.
                    P (+) P = 2P
[Step 06] -R과 P를 지나는 직선이 타원곡선과 만나는 점을 선택합니다.
[Step 07] -R과 P를 지나는 직선이 곡선과 만나는 점을 x축 대칭이동 합니다.
                    P (+) -R = 2P (+) P = 3P

 

 

P, Q의 위치가 같은 경우 접선을 이용해 기울기를 알아내야 합니다.

            (1)
            y^2 = x^3 + ax + b
            y = sx + d
            2y(dy / dx) = 3x^2 + a -> dy / dx = (3x^2 + a) / 2y
            s = dy / dx = (3x^2 + a) / 2y

            (2)
            (sx + d)^2 = x^3 + ax + b
            x^3 - (s^2)(x^2) + (a - 2sd)x + (b - d^2) = 0

            (3)
            ( x - x(p) )( x - x(q) )( x - x(r) ) = 0
            x^3 - ( x(p) + x(q) + x(r) )x^2 + (x(p)x(q) + x(p)x(r) + x(q)x(r))x - x(p)x(q)x(r) = 0

            (4)
            x^3 - (s^2)(x^2) + (a - 2sd)x + (b - d^2) = 0
            x^3 - ( x(p) + x(q) + x(r) )x^2 + (x(p)x(q) + x(p)x(r) + x(q)x(r))x - x(p)x(q)x(r) = 0

            s^2 = ( x(p) + x(q) + x(r) )
            -x(r) = ( x(p) + x(q) - s^2 )

            (5)
            −y(r) = s(x(p) − x(r)) − y(p)

            (결론)
            P != Q => s = ( y(q) - y(p) ) / ( x(q) - x(p) )
            P = Q  => s = dy / dx = ( 3x(p)^2 + a ) / 2y(p)
            x(r) = s^2 - x(p) - x(q)
            -y(r) = s( x(p) - x(r) ) - y(p)

 

Finite Fields

• 타원곡선 방정식을 암호학에 응용하기 위해서는 자연수로 영역을 변경해야합니다.

        y^2 mod p = x^3 + ax + b mod p

        p = 17
        y^2 ≡ 5^3 + 2 × 5 + 2 = 137 (x = 5)
        y = sqrt(137)   11 < y < 12

        y^2 ≡ x^3 + 2x + 2 (mod 17)

        k     1      2      3      4       5        6      7       8      9       10
        kP (5, 1) (6, 3) (10, 6) (3, 1) (9, 16) (16, 13) (0, 6) (13, 7) (7, 6) (7, 11)
        k     11       12      13     14     15       16       17      18    19    20
        kP (13, 10) (0, 11) (16, 4) (9, 1) (3, 16) (10, 11) (6, 14) (5, 16)  O    (5, 1)

        => a = 2, b = 2, p = 17, G = (5, 1), n = 19, h = 1

* 개념
        [Step 01] 최초의 점인 G를 사용합니다
                    g = (5, 1)
        [Step 02] Alice와 Bob은 각각 자신의 비밀키를 선택합니다.
                    x(alice) = 3    x(bob) = 7
        [Step 03] Alice와 Bob은 각각 공개키를 생성하며 해당 키를 상대에게 전송합니다.
                    y(alice) = x(alice) ⊗ G = 3 ⊗ G = (10, 6)   y(bob) = x(bob) ⊗ G = 7 ⊗ G = (0, 6)
        [Step 04] Alice와 Bob은 상대방의 공개키와 자신의 개인 키를 이용하여 키를 획득합니다.
                    Key = y(bob) ⊗ x(alice) = (0, 6) ⊗ 3 = (6, 3)   Key = y(alice) ⊗ x(bob) = (10, 6) ⊗ 7 = (6, 3)


* Secp256k1
        p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
        a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
        b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
        G = (79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798,
        483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8)
        n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
        h = 01

 

 

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class ECPoint {

    private BigInteger x;
    private BigInteger y;
    private EllipticCurve field;

    public ECPoint(BigInteger x, BigInteger y, EllipticCurve field) {
        this.x = x;
        this.y = y;
        this.field = field;
    }

    public ECPoint(int x, int y, EllipticCurve field) {
        this.x = BigInteger.valueOf(x);
        this.y = BigInteger.valueOf(y);
        this.field = field;
    }

    public boolean allPointSame(ECPoint r) {
        return getX().equals(r.getX()) && getY().equals(r.getY());
    }

    public ECPoint addOperation(ECPoint r) {
        if (r.getY().equals(field.getP())) {
            // System.out.println("P + O = P\n");
            return this;
        }
        if (this.getY().equals(field.getP())) {
            // System.out.println("O + P = P\n");
            return r;
        }
        BigInteger S;
        if (allPointSame(r)) {
            // [Case] P = Q
            if (this.getY().equals(BigInteger.ZERO)) {
                // [Wrong] return new ECPoint(getY(), field.getP(), field);
                return new ECPoint(getX(), field.getP(), field);
            }
            BigInteger modInverseResult = field.modInverse(BigInteger.valueOf(2).multiply(getY()));
            S = BigInteger.valueOf(3).multiply(getX().pow(2)).add(field.getA())
                .multiply(modInverseResult).mod(field.getP());
        } else {
            // [Case] P != Q
            if (this.getX().equals(r.getX())) {
                return new ECPoint(getX(), field.getP(), field);
            }
            BigInteger modInverseResult = field.modInverse(r.getX().subtract(getX()));
            S = r.getY().subtract(getY()).multiply(modInverseResult).mod(field.getP());
        }
        BigInteger newX = S.pow(2).subtract(getX()).subtract(r.getX()).mod(field.getP());
        BigInteger newY = S.multiply(getX().subtract(newX)).subtract(getY()).mod(field.getP());
        return new ECPoint(newX, newY, field);
    }


    public ECPoint slowMultiplyOperation(BigInteger i) {
        ECPoint newPoint = this;
        for (BigInteger bi = i; bi.compareTo(BigInteger.ONE) > 0;
            bi = bi.subtract(BigInteger.ONE)) {
            newPoint = addOperation(newPoint);
        }
        return newPoint;
    }

    public ECPoint multiplyOperation(BigInteger k) {
        List<Integer> bitInfo = new ArrayList<Integer>();
        for (int i = 0; i < k.bitLength(); i++) {
            if (k.testBit(i)) {
                bitInfo.add(1);
            } else {
                bitInfo.add(0);
            }
        }
        ECPoint X = this;
        ECPoint R = new ECPoint(BigInteger.ZERO, field.getP(), field);
        for (Integer bit : bitInfo) {
            if (bit == 1) {
                R = R.addOperation(X);
            }
            X = X.addOperation(X);
        }
        return R;
    }

    public BigInteger getX() {
        return x;
    }

    public void setX(BigInteger x) {
        this.x = x;
    }

    public BigInteger getY() {
        return y;
    }

    public void setY(BigInteger y) {
        this.y = y;
    }

    public EllipticCurve getField() {
        return field;
    }

    public void setField(EllipticCurve field) {
        this.field = field;
    }

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

 

 

import java.math.BigInteger;

public class EllipticCurve {

    private BigInteger a;
    private BigInteger b;
    private BigInteger p;

    public EllipticCurve(BigInteger a, BigInteger b, BigInteger p) {
        this.a = a;
        this.b = b;
        this.p = p;
    }

    public EllipticCurve(int a, int b, int p) {
        this.a = BigInteger.valueOf(a);
        this.b = BigInteger.valueOf(b);
        this.p = BigInteger.valueOf(p);
    }

    public BigInteger modInverse(BigInteger value) {
        return value.modInverse(p);
    }

    public BigInteger getA() {
        return a;
    }

    public void setA(BigInteger a) {
        this.a = a;
    }

    public BigInteger getB() {
        return b;
    }

    public void setB(BigInteger b) {
        this.b = b;
    }

    public BigInteger getP() {
        return p;
    }

    public void setP(BigInteger p) {
        this.p = p;
    }

    @Override
    public String toString() {
        return "EllipticCurve{" +
            "a=" + a +
            ", b=" + b +
            ", p=" + p +
            '}';
    }
}

 

 

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

public class ECDHETest {

    public static void main(String[] args) {
        System.out.println("[Basic Test]");
        sampleTest();
        System.out.println("[Secp256k1 Test]");
        Secp256k1Test();
        System.out.println("[secp256r1 Test]");
        Secp256r1Test();
    }

    public static void sampleTest() {
        long beforeTime = System.currentTimeMillis();
        EllipticCurve field = new EllipticCurve(2, 2, 17);
        ECPoint G = new ECPoint(5, 1, field);

        BigInteger privateA = BigInteger.valueOf(117);
        BigInteger privateB = BigInteger.valueOf(7);

        System.out.println("[Alice Private Key]");
        System.out.println(privateA);
        System.out.println("[Bob Private Key]");
        System.out.println(privateB);
        System.out.println();

        ECPoint xA = G.multiplyOperation(privateA);
        ECPoint xB = G.multiplyOperation(privateB);

        System.out.println("[Alice Public Key]");
        System.out.println(xA);
        System.out.println("[Bob Public Key]");
        System.out.println(xB);
        System.out.println();

        ECPoint keyA = xB.multiplyOperation(privateA);
        ECPoint keyB = xA.multiplyOperation(privateB);

        System.out.println("[Alice Key]");
        System.out.println(keyA);
        System.out.println("[Bob Key]");
        System.out.println(keyB);
        System.out.println();

        long afterTime = System.currentTimeMillis();
        System.out.println("Operating Time: " + (afterTime - beforeTime) + "ms");
        System.out.println();
    }

    public static void Secp256k1Test() {
        long beforeTime = System.currentTimeMillis();
        String pStr = "FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F".replaceAll(
            " ", "");
        BigInteger p = new BigInteger(pStr, 16);
        String aStr = "00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000".replaceAll(
            " ", "");
        BigInteger a = new BigInteger(aStr, 16);
        String bStr = "00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007".replaceAll(
            " ", "");
        BigInteger b = new BigInteger(bStr, 16);
        String gXStr = "79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798".replaceAll(
            " ", "");
        BigInteger gX = new BigInteger(gXStr, 16);
        String gYStr = "483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8".replaceAll(
            " ", "");
        BigInteger gY = new BigInteger(gYStr, 16);

        EllipticCurve field = new EllipticCurve(a, b, p);
        ECPoint G = new ECPoint(gX, gY, field);

        BigInteger privateA = BigInteger.probablePrime(256, new Random());
        BigInteger privateB = BigInteger.probablePrime(256, new Random());

        System.out.println("[Alice Private Key]");
        System.out.println(privateA);
        System.out.println("[Bob Private Key]");
        System.out.println(privateB);
        System.out.println();

        ECPoint xA = G.multiplyOperation(privateA);
        ECPoint xB = G.multiplyOperation(privateB);

        System.out.println("[Alice Public Key]");
        System.out.println(xA);
        System.out.println("[Bob Public Key]");
        System.out.println(xB);
        System.out.println();

        ECPoint keyA = xB.multiplyOperation(privateA);
        ECPoint keyB = xA.multiplyOperation(privateB);

        System.out.println("[Alice Key]");
        System.out.println(keyA);
        System.out.println("[Bob Key]");
        System.out.println(keyB);
        System.out.println();

        long afterTime = System.currentTimeMillis();
        System.out.println("Total Operating Time: " + (afterTime - beforeTime) + "ms");
        System.out.println();
    }

    public static void Secp256r1Test() {
        long beforeTime = System.currentTimeMillis();
        String pStr = "FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF".replaceAll(
            " ", "");
        BigInteger p = new BigInteger(pStr, 16);
        String aStr = "FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC".replaceAll(
            " ", "");
        BigInteger a = new BigInteger(aStr, 16);
        String bStr = "5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B".replaceAll(
            " ", "");
        BigInteger b = new BigInteger(bStr, 16);
        String gXStr = "6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296".replaceAll(
            " ", "");
        BigInteger gX = new BigInteger(gXStr, 16);
        String gYStr = "4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51F5".replaceAll(
            " ", "");
        BigInteger gY = new BigInteger(gYStr, 16);

        EllipticCurve field = new EllipticCurve(a, b, p);
        ECPoint G = new ECPoint(gX, gY, field);

        BigInteger privateA = BigInteger.probablePrime(256, new Random());
        BigInteger privateB = BigInteger.probablePrime(256, new Random());

        System.out.println("[Alice Private Key]");
        System.out.println(privateA);
        System.out.println("[Bob Private Key]");
        System.out.println(privateB);
        System.out.println();

        ECPoint xA = G.multiplyOperation(privateA);
        ECPoint xB = G.multiplyOperation(privateB);

        System.out.println("[Alice Public Key]");
        System.out.println(xA);
        System.out.println("[Bob Public Key]");
        System.out.println(xB);
        System.out.println();

        ECPoint keyA = xB.multiplyOperation(privateA);
        ECPoint keyB = xA.multiplyOperation(privateB);

        System.out.println("[Alice Key]");
        System.out.println(keyA);
        System.out.println("[Bob Key]");
        System.out.println(keyB);
        System.out.println();

        long afterTime = System.currentTimeMillis();
        System.out.println("Total Operating Time: " + (afterTime - beforeTime) + "ms");
        System.out.println();
    }
}

 

 

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