Logo
Published on

About Asymmetric Key and RSA, ECC

Authors

비대칭키 암호의 기본 개념

Asymmetric Key (비대칭 키) 암호

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

활용 메커니즘

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

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

대칭 키비대칭 키
개념 및 키 구성 차이같은 키를 두 사람이 공유공개 키는 공개되어 있지만 개인의 비밀 키는 공개하지 않음
암호화 방식C = Ek(P)C = f(PublicKey, P)
복호화 방식P = Dk(C)P = g(PrivateKey, C)
알고리즘의 실행 시간빠르다상대적으로 느리다
활용길이가 긴 메시지를 암호화짧은 데이터 암호화, 전자서명, 인증 등

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

RSA

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

개념

  • Public Key : e, n

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

  • Private Key : d

  • C=PemodnC = P^e mod n

  • P=CdmodnP = C^d mod n


RSA 키 생성과 복호화 과정

생성 알고리즘

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

pq

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(PP)가 전송받은 CipherText(CC)를 복호화 한 PlainText(P1P_1)과 같다는 걸 증명하는 과정입니다.

P1=Cdmodn=(Pemodn)d=PedmodnP^1 = C^d  mod n = (P^e mod n)^d = P^{ed} mod n

  • ed=k×φ+1ed = k × φ⒩ + 1

  • P1=Pedmodn=Pk×φ+1modnP^1 = P^{ed} mod n= P^{k × φ⒩ + 1} mod n

  • P1=Pk×φ+1modn=PmodnP^1 = P^{k × φ⒩ + 1} mod n = P mod n

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


ECC (Elliptic Curve Cryptosystem)

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

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

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

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

y2=x3+ax+by^2 = x^3 + ax + b 그래프

타원 곡선 상의 덧셈 연산

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

PP = (x1x_1, y1y_1) , Q = (x2x_2, y2y_2) RR = P+QP + Q

✏️ RR = (x3x_3, y3y_3) 계산 방법

  • aa . PQP ≠ Q

    mm(기울기) = (y2y1)/(x2x1)(y_2 - y_1) / (x_2 - x_1) > x3=m2x1x2x_3 = m^2 - x_1 - x_2 > y3=m(x1x3)y1y_3 = m(x_1 - x_3) - y_1

  • bb . P=QP = Q

    mm(기울기) = (3x12+a)/(2y1)(3x_1^2 + a) / (2y_1) > x3=m2x1x2x_3 = m^2 - x_1 - x_2 > y3=m(x1x3)y1y_3 = m(x_1 - x_3) - y_1

GF(pp)상의 타원 곡선

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

Modulo pp를 이용한 타원곡선 특징

  • xx의 값은 0~ pp-1 사이에 존재합니다.

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

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

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


Reference