Elliptic Curve Cryptography

1. 곱셈 표기(Multiplicative Notation)

- Generator g는 Zp*같은 곱셈 그룹에서 사용하는 생성자

- 곱셈 연산 사용: g⋅h

- Exponentiation 연산: g^x = g⋅g⋯⋅g (x번 곱하기)

 

 

2. 덧셈 표기(Additive Notation)

- Generator P는 타원곡선 위의 기준점

- 타원곡선 위의 점 덧셈: P+Q

- Scalar Multiplication: xP = P+P+⋯+P (x번 더하기)

 

 

3. DSA with Additive Notation

- Key Generation: 

  1) 차수가 q인 덧셈 사이클릭 그룹 G 생성

  2) 그룹 G에서 생성자 P 선택

  3) 비밀키 x∈Zq* 선택, 공개키는 Q = xP

  4) 공개키: (q,P,Q), 비밀키: x

 

- Sign:

  1) k∈Zq*​ 무작위 선택

  2) r = kP mod q (??)

  3) s = (H(M) + x⋅r​)⋅k^−1 mod q

  4) 서명 결과: σ = (M, (r,s))

 

- Verify:

  1) w = s^−1 mod  q

  2) u1​ = w⋅H(M) mod q

  3) u2 ​= w⋅r ​mod q

  4) ν = u1​P + u2​Q mod q (??)

  5) v = r mod q (??) 가 성립하는지 확인

 

- 어떻게 안전한 additive group을 생성할까?

- How to handle three(??) parts?

 

 

4. Elliptic Curve(타원 곡선)

Weierstrass 정규형

- A, B는 곡선을 정의하는 상수

- 타원 곡선 위의 점은 이 방정식을 만족하는 (X, Y) 쌍으로 구성됨

타원곡선이 되기 위한 조건

 

- 추가된 점 O는 타원 곡선의 덧셈 연산에서 항등원 역할

타원 곡선의 예시 그림

 

 

5. Elliptic Curve over Finite Field(유한체 위의 타원곡선)

- Field : 덧셈, 뺄셈, 곱셈, 나눗셈에 대해 닫혀있고 결합법칙, 교환법칙, 분배법칙을 만족하는 수의 집합

- 실수나 복소수는 필드지만 정수는 필드가 아님 -> 4/3같은 나눗셈이 결과를 벗어남

- p가 소수일 때 Zp는 필드

- GF(p^n) : p^n개의 원소를 가지는 필드. 다항식 Zp[X]를 다항식 P(X)로 나눠서 만듬

 

- 유한체 Fp 위의 타원 곡선은 E: Y^2 = X^3 + AX + B (mod p)를 만족하는 (X,Y)의 집합

- A,B ∈ Fp​, 즉 0부터 p−1 사이의 값

접 집합(O는 덧셈 항등원)

 

 

6. Addition on Elliptic Curve Points

- 타원곡선 위의 두 점 P = (x1, y1), Q = (x2, y2)를 더한 점 R = P + Q = (x3, y3)은 다음처럼 계산됨 :

기울기 s

두 점이 다를 때의 덧셈 공식

- 위 그림에서 P, Q를 잇는 직선과 곡선이 교차하는 세 번째 점(-R)을 찾고, 그 점을 x축에 대칭 이동한 점이 R = P + Q가 됨

- 직선의 방적식을 Y = sX + t로 설정하여 수학적 증명 가능

 

 

7. Doubling on Elliptic Curve Points

- 곡선 위의 점 P = (x1, y1)에 대해 2P = R = (x3, y3)을 구하기

공식

 

- 그림으로 이해해보자면 타원 곡선과 접선이 생김

- 여기서도 접선을 Y = sX + t로 설정

- 수학적 증명을 사용할 때는 미분해서 시작(접선이기 때문에)

 

 

8. Scalar Multiplication on Elliptic Curve Points

- ECC에서 xP는 점 P를 x번 더하는 연산

- 곱셈은 반복 덧셈, 제곱은 doubling 연산 사용

- Right-to-Left Algorithm 사용 가능

- ECC의 장점 : 같은 수준의 보안을 더 작은 키로 제공 가능

- DLP는 p가 작거나 q가 작으면 여러 공격법이 존재

- 하지만 ECC에서의 유일한 공격은 Pollard’s rho algorithm

 

 

9. ECDSA(타원곡선 기반 서명 알고리즘)

- 입력 요소 :

  1) 타원곡선 E : Y^2 = X^3 + aX + b  mod p

  2) P는 곡선 위에 있는 generator point, q는 점 P가 생성하는 사이클릭 군의 차수

 

- Key Generation :

  1) 비밀키 x ∈ {1,...,q−1} 선택 

  2) 공개키 Q = xP 계산

  3) 비밀키 = x, 공개키 = (p,a,b,q,P,Q)

 

- Sign : 

  1) 무작위 값 k ∈ {1,...,q−1} 선택

  2) R = kP 계산 → R = (xR,yR)

  3) r = xR ​mod q (x좌표를 q로 나눈 값)

  4) 해시값 H(M)을 사용하여: s = (H(M) + x⋅r)⋅k^−1  mod  q

  5) 서명 결과 σ = (r,s)

 

- Verify :

  1) w = s^−1  mod q 계산

  2) u1​ = w⋅H(M)  mod q 계산

  3) u2 ​= w⋅r  mod q 계산

  4) R = u1​P + u2​Q 계산

  5) xR​ mod q = r 만족하면 서명 유효

 

 

10. Elliptic Curve ElGamal 암호화 방식

- Key Generation : 

  1) 타원곡선 E, 소수 p, 계수 a,b 생성점 G 사용

  2) 비밀키 x ∈ {1,...,q−1} 선택

  3) 공개키 X = xG

  4) 비밀키 = x, 공개키 = (p,a,b,q,G,X)

 

- Encryption : 메시지 M은 타원곡선 위의 점이어야 함

  1) 무작위 r ∈ {1,...,q−1} 선택

  2) C1​ = rG 계산

  3) C2​ = M + rX

  4) 암호문 C = (C1,C2) -> r이 매번 달라지므로 확률적 암호화

 

- Decryption : 

  1) 비밀키 x 이용해서 xC1 = xrG = rX 계산

  2) M = C2 ​− xC1 ​= M + rX − rX = M