7. Public Key Cryptography - Eliptic curve

사용 변수

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

• (a, b) = curve모양을 결정하는 상수
• p = prime num
• G = generator. base point.
• n = order of point G

그래프 내 G 계산 방법

맨 처음엔 doubling을 사용해야한다.

n=151처럼 큰 경우는? -> double and add algorithm

encrypt & decrypt

사용 변수

• private key ($d_A$) : n보다 작은 랜덤 정수
• public key ($Q_A$) : scalar point multiplication 을 사용해 G를 계산한 결과
  $Q_A=d_A*G$
  

Encryption
1. temporary public key R 생성

• 랜덤정수 r 선택
• R = r * G 계산
• S(secret shared point) = r * $Q_A$

2. data encrypt

• C = S X M
• generating H(M)

3. Trasmission

• (R, C, H(M)) 보냄

Decryption
1. 받는것

• R, C = S X M , H(M)

2. decrypt

• S 계산하기
  $d_A*R=d_A*r*G=r*(d_A*G)=r*Q_A=S$

Example

ECC vs RSA

• ECC는 RSA 보다 적은 key size로 같은 수준의 보안 레벨을 achieve
• ECC는 based on discrtete logarithm -> much more difficult to challenge.
• ECC 는 Quantum computer사용하여 discrete logarithm을 빠르게 계산할 수 있는 경우, Easier to break than RSA 🥲