[암호학] 공개키 암호 알고리즘 (RSA, ElGamal 등)

---

공개키 암호 알고리즘

1. Knapsack 암호
2. RSA 암호
3. ElGamal 암호
4. 타원곡선 암호
5. OAEP

---

RSA 암호

암호, 전자 서명 등에 사용
큰 수의 소인수분해가 어렵다는 문제에 기반한 암호

n은 다른 사람에게 공개

p, q는 공개하지 않음 → n을 알아도 p, q를 구하기 어려움

                                  → p, q를 모르기 때문에 파이(n)을 모름 

                                  → 비밀키 d도 모름

 

암호화 알고리즘

e와 n은 공개키

복호 알고리즘

d는 비밀키

정리

RSA 암호의 안전성

공개키 e, n

개인키 d를 획득하기 위한 절차

→ n을 소인수 분해 하여 p, q 구하기

→ 파이(n) 계산

→ d 계산

: 큰 수 n을 소인수 분해하는 문제 NP-complete 문제, 매우 어려움

 

* e가 작을 경우 안전하지 않을 수 있음

 

---

ElGamal 암호

유한체 상에서의 이산대수문제의 어려움에 기반한 암호

이산대수 문제

g, y를 알고 있어도 x를 구하기 어려움. NP-complete 문제

소인수분해 문제보다 어렵다고함

 

키 생성

비밀키 x

암호화 알고리즘

M은 평문
p - 1 과 서로소인 난수 k 선택

a, b를 각각 따로 구해야하며, a와 b가 암호문임

 

복호 알고리즘

 

ElGamal 암호의 안전성

어려운 이산대수문제는 안전한 ElGamal 암호의 필요조건

이산대수문제가 해결되면 ElGamal 암호도 깨질 것임

 

---

기타 공개키 암호 

기존에 있던 RSA와 같은 암호를 사용하여 구현한 암호, 새로운 암호의 형태는 아님

1. 타원 곡선 암호 ECC

          : 기존의 공개키 암호를 유한체 상의 타원곡선을 이용하여 구현

          : RSA와 같은 정도의 안전성을 보다 작은 키의 크기, 메모리로 구현 가능

2. OAEP

         : 완강성을 가지는 암호

         : 랜덤 함수를 이용한 효율적인 암호 구성

 

---

PKCS

공개키 암호의 사용을 활성화하기 위해 개발
표준화 과정