타원 곡선 암호화

Elliptic Curve Cryptography

1. 순서 $q$를 가지는 (
   덧셈적
   ) 순환 그룹 $G$를 선택한다.
2. $G$에서 생성자 $P$를 선택한다.
3. $Z_q^*$에서 임의의 정수 $x$를 선택한 후 $Q = xP$를 계산한다.
4. 공개 키 $pk = (q, P, Q)$, 개인 키 $sk = x$를 반환한다.

1. $Z_q^*$에서 임의의 $k$를 선택한다.
2. $r = kP \pmod{q}$와 $s = k^{-1}(H(M) + xr) \pmod{q}$를 계산한다.
3. 서명 $\sigma = (M, r, s)$를 반환한다.

1. $w = s^{-1} \pmod{q}$를 계산한다.
2. $u_1 = H(M)w \pmod{q}$와 $u_2 = rw \pmod{q}$를 계산한다.
3. $v = u_1P + u_2Q \pmod{q}$를 계산한다.
4. $v \stackrel{?}{=} r \pmod{q}$를 확인한다. 이 조건이 성립하면 1을 반환하고, 그렇지 않으면 0을 반환한다.

1. (안전한)덧셈 그룹을 어떻게 생성할 것인가
2. 모듈러 연산을 어떻게 처리할 것인가

Weierstrass 형태의 방정식 해 집합

1. $E: Y^2 = X^3 -3X+3$
   
2. $E: Y^2 = X^3 -6X+5$
   

필드 $\mathbb{F}_p$는 덧셈, 곱셈 뺄셈, 그리고 0이 아닌 요소들에 대한 나눗셈이 가능한 수학적 구조이다.

또한 결합 법칙, 교환 법칙, 분배 법칙이 성립한다.

• 결합 법칙: $(a+b)+c = a+(b+c)$, $(ab)c = a(bc)$
• 교환 법칙: $a+b = b+a$, $ab = ba$
• 분배 법칙: $a(b+c) = ab+ac$

• $\mathbb{F}_{13} = \{0, 1, 2, \cdots, 12\}$
• $X = 0; Y^2 = 8 \rightarrow \mathbb{F}_{13}$에 $Y$가 존재하지 않음
• $X = 1; Y^2 = 12 \rightarrow 5^2 \equiv 12 \pmod{13}, 8^2 \equiv 12 \pmod{13} \;\text{in}\; \mathbb{F}_{13}$

• $Y^2 = X^3 + AX + B$와 $Y = sX + t$의 교점 찾기
  1. $(sX + t)^2 = X^3 + AX + B$
  2. $s^2X^2 + 2st + t^2 = X^3 + AX + B$
  3. $X^3 - s^2X^2 + (A-2st)X + (B-t^2) = 0$
• 세 근 $x_1, x_2, x_3$의 합은 $s^2$이다.
  $x_1 + x_2 + x_3 = s^2 \Rightarrow \underline{x_3 = s^2 - x_1 - x_2}$
• $P = (x_1, y_1)$와 $-R = (x_3, -y_3)$은 $Y = sX + t$위에 있다.
  $y_1 = sx_1 + t \Rightarrow t = y_1 - sx_1$
  $-y_3 = sx_3 + t = sx_3 + (y_1 - sx_1) s(x_3 - x_1) + y_1$
  $\Rightarrow \underline{y_3 = s(x_1 - x_3) - y_1}$

• $Y^2 = X^3 + AX + B$와 $Y = sX + t$의 교점 찾기(
  덧셈 정리
  와 동일)
• 점 $P$에서 접선의 기울기 계산하려면 $Y^2 = X^3 + AX + B$의
  도함수
  를 이용한다.
  $2Y \frac{dY}{dX} = 3X^2 + A \Rightarrow \frac{dY}{dX} = \frac{3X^2 + A}{2Y}$
  $\therefore \underline{s = \frac{3x_1^2 + A}{2y_1}}$
• $P = (x_1, y_1)$와 $-R = (x_3, -y_3)$은 $Y = sX + t$위에 있다.(
  덧셈 정리
  와 동일)

• 곱셈 $\rightarrow$ 덧셈 (ex: $2P = P + P$)
• 거듭제곱 $\rightarrow$ 두 배 연산 (ex: $2^kP = 2^{k-1}P + 2^{k-1}P$)

R = O, T = P 
for i from 0 to l-1 do
	if x_i = 1 then
		R = R + T
	T = 2T
end for
return R

• 짧은 파라미터 크기
• $Z_p^*$의 부분군 $\mathbb{G}$에서 정의된 DLP(이산 로그 문제) 해결
  • $p$가 크지 않다면 가장 좋은 공격은 숫자 체 방법
  • $q$가 크지 않다면 가장 좋은 공격은 Pollard Rho 방법
• 타원 곡선 위에서 정의된 DLP를 해결하기 위한 최선의 알고리즘은 Pollard Rho 방법

1. 타원 곡선 $E$를 사용하여 다음을 선택한다.
   • 모듈러스 $p$
   • 타원 곡선 계수 $a$와 $b$
   • 소수 차수 $q$의 순환 그룹을 생성하는 점 $P$ (생성자)
2. $Z_q^*$에서 임의의 정수 $x$를 선택한 후 $Q = xP$를 계산한다.
3. 공개 키 $pk = (p, a, b, q, P, Q)$, 개인 키 $sk = x$를 반환한다.

1. $Z_q^*$에서 임의의 $k$를 선택한다.
2. $R = kP$를 계산한 후 $r = x_R$(점 $R$의 $x$ 좌표)를 둔다.
3. $s = k^{-1}(H(M) + xr) \pmod{q}$를 계산한다.
4. 서명 $\sigma = (M, (r, s))$를 반환한다.

1. $w = s^{-1} \pmod{q}$를 계산한다.
2. $u_1 = H(M)w \pmod{q}$와 $u_2 = rw \pmod{q}$를 계산한다.
3. $R = u_1P + u_2Q$를 계산한다.
4. $r \stackrel{?}{=} x_R \pmod{q}$를 확인한다. 이 조건이 성립하면 1을 반환하고, 그렇지 않으면 0을 반환한다.

1. 타원 곡선 $E$를 사용하여 다음을 선택한다.
   • 모듈러스 $p$
   • 타원 곡선 계수 $a$와 $b$
   • 소수 차수 $q$의 순환 그룹을 생성하는 점 $G$ (생성자)
2. $Z_q^*$에서 임의의 정수 $x$를 선택한 후 $X = xG$를 계산한다.
3. 공개 키 $pk = (p, a, b, q, G, X)$, 개인 키 $sk = x$를 반환한다.

1. $Z_q^*$에서 임의의 원소 $r$를 선택한다.
2. $C_1 = rG$, $C_2 = M + rX$를 계산한다.
3. 암호문 $C = (C_1, C_2)$를 반환한다.

1. $M = C_2 - xC_1$를 계산한다.($= M + rX - x(rG) = M + rX - rX$)
2. 평문 $M$을 반환한다.