- Published on
About Asymmetric Key and RSA, ECC
- Authors
- Name
- 이민기
- Github
- @mingi3442
- 비대칭키 암호의 기본 개념
- Asymmetric Key (비대칭 키) 암호
- 활용 메커니즘
- 𖤐 대칭 키 암호와 비대칭 키 암호의 차이
- RSA 암호화 방식의 원리와 적용
- RSA
- 개념
- RSA 키 생성과 복호화 과정
- 생성 알고리즘
- RSA 정확성 증명과 예시
- ECC (Elliptic Curve Cryptosystem)
- 타원 곡선 암호 시스템의 특징
- 타원 곡선 상의 덧셈 연산
- GF($p$)상의 타원 곡선
- Reference
비대칭키 암호의 기본 개념
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
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()가 전송받은 CipherText()를 복호화 한 PlainText()과 같다는 걸 증명하는 과정입니다.
⇒ ✏️ φ⒩ 오일러의 정리 마지막 부분 참고하시면 됩니다.
ECC (Elliptic Curve Cryptosystem)
타원 곡선 암호 시스템으로 유한체상의 타원곡선 이론에 기반한 공개키 암호입니다.
타원 곡선 암호 시스템의 특징
RSA의 키는 보통 1024bits 이상이지만 ECC는 256bit 이상의 크기를 갖으며 상대적으로 짧은 키의 길이로 같은 보안 수준을 제공할 수 있습니다.
실수 상의 타원곡선에서는 모든 근이 실근일 경우, 좌표의 수평선과 곡선이 3점에서 교차합니다.
그래프
타원 곡선 상의 덧셈 연산
타원곡선 상에서 두 점(,)을 정한 후 두 점을 지나가는 직선이 타원 곡선과 만나는 3번째 교점을 축 기준으로 대칭되는 점을 로 정의하여 계산하는 것을 기초한다
= (, ) , Q = (, ) =
✏️ = (, ) 계산 방법
- .
(기울기) = > >
- .
(기울기) = > >
)상의 타원 곡선
GF(GF는 Galois Field, 유한체를 의미하며 는 Prime Number 즉 소수를 의미합니다.
Modulo 를 이용한 타원곡선 특징
의 값은 0~ -1 사이에 존재합니다.
덧셈연산은 덧셈 결과를 mod 연산 합니다.
역원은 기준 이며 여기서 는 의 덧셈에 대한 역원입니다.
⤷가 13일때 의 역원은 이며 즉