[Cryptography] About Asymmetric Key and RSA, ECC

• 비대칭키 암호의 기본 개념
• Asymmetric Key (비대칭 키) 암호
• 활용 메커니즘
• 𖤐 대칭 키 암호와 비대칭 키 암호의 차이
• RSA 암호화 방식의 원리와 적용
• RSA
• 개념
• RSA 키 생성과 복호화 과정
• 생성 알고리즘
• RSA 정확성 증명과 예시
• ECC (Elliptic Curve Cryptosystem)
• 타원 곡선 암호 시스템의 특징
• 타원 곡선 상의 덧셈 연산
• GF($p$)상의 타원 곡선

비대칭키 암호의 기본 개념

Asymmetric Key (비대칭 키) 암호

비밀 키와 공개 키를 한 쌍으로 암호 키로 사용하여 암호화 >

활용 메커니즘

• 비밀 메시지 : A의 공개키로 암호화한 암호는 A의 비밀 키로 복호화
• 전자 서명 : A의 비밀 키로 암호화한 암호는 A가 암호화 했다고 증명 가능

𖤐 대칭 키 암호와 비대칭 키 암호의 차이

RSA 암호화 방식의 원리와 적용

RSA

가장 널리 쓰는 공개 키 알고리즘 중 하나로 전자서명이 가능한 최초의 공개 키 알고리즘으로 알려져 있습니다.

개념

• Public Key : e, n

  ✓ Plain Text의 크기는 n을 넘을 수 없으며 n은 1024 bits 이상의 수 입니다.

• Private Key : d

• $C = P^e mod n$

• $P = C^d mod n$

RSA 키 생성과 복호화 과정

생성 알고리즘

1. 512비트 이상의 큰 소수 p, q를 선택

⤷ p ≠ q

2. n = p × q

⤷ n은 1024비트 이상의 수가 됩니다.

3. φ⒩ = ( p - 1) × ( q - 1 )

4. φ⒩ 와 서로소인 e를 선택

⤷ 1 < e < φ⒩

• 생성된 Public Key : e, n
• 생성된 Private Key : d = e⁻¹ mod φ⒩ ⇒ 확장 유클리드 알고리즘 사용

RSA 정확성 증명과 예시

• 전송한 PlainText($P$)가 전송받은 CipherText($C$)를 복호화 한 PlainText($P_1$)과 같다는 걸 증명하는 과정입니다.

$P^1 = C^d  mod n = (P^e mod n)^d = P^{ed} mod n$

• $ed = k × φ⒩ + 1$

• $P^1 = P^{ed} mod n= P^{k × φ⒩ + 1} mod n$

• $P^1 = P^{k × φ⒩ + 1} mod n = P mod n$

  ⇒ ✏️ φ⒩ 오일러의 정리 마지막 부분 참고하시면 됩니다.

ECC (Elliptic Curve Cryptosystem)

타원 곡선 암호 시스템으로 유한체상의 타원곡선 이론에 기반한 공개키 암호입니다.

타원 곡선 암호 시스템의 특징

• RSA의 키는 보통 1024bits 이상이지만 ECC는 256bit 이상의 크기를 갖으며 상대적으로 짧은 키의 길이로 같은 보안 수준을 제공할 수 있습니다.

• 실수 상의 타원곡선에서는 모든 근이 실근일 경우, 좌표의 수평선과 곡선이 3점에서 교차합니다.

$y^2 = x^3 + ax + b$ 그래프

타원 곡선 상의 덧셈 연산

타원곡선 상에서 두 점($P$,$Q$)을 정한 후 두 점을 지나가는 직선이 타원 곡선과 만나는 3번째 교점을 $x$축 기준으로 대칭되는 점을 $R$로 정의하여 계산하는 것을 기초한다

$P$ = ($x_1$, $y_1$) , Q = ($x_2$, $y_2$) $R$ = $P + Q$

✏️ $R$ = ($x_3$, $y_3$) 계산 방법

• $a$ . $P ≠ Q$

  $m$(기울기) = $(y_2 - y_1) / (x_2 - x_1)$ > $x_3 = m^2 - x_1 - x_2$ > $y_3 = m(x_1 - x_3) - y_1$

• $b$ . $P = Q$

  $m$(기울기) = $(3x_1^2 + a) / (2y_1)$ > $x_3 = m^2 - x_1 - x_2$ > $y_3 = m(x_1 - x_3) - y_1$

GF($p$)상의 타원 곡선

GF는 Galois Field, 유한체를 의미하며 $p$는 Prime Number 즉 소수를 의미합니다.

Modulo $p$를 이용한 타원곡선 특징

• $x$의 값은 0~ $p$-1 사이에 존재합니다.

• 덧셈연산은 덧셈 결과를 mod $p$연산 합니다.

• 역원은 $(x,y)$ 기준 $(x, -y)$이며 여기서 $-y$는 $y$의 덧셈에 대한 역원입니다.

  ⤷$p$가 13일때 $(1,4)$의 역원은 $(1,-4)$이며 즉 $(1,9)$

Reference

• 해시넷-타원 곡선 암호