이전 글까지 모두 대칭키 암호학(symmetric ciphers)에 관한 내용이었다.
뭐 고전적인 방법인 substitution과 permutation, block cipher의 DES, AES 그리고 다양한 모드들, stream cipher 등을 얘기한 것이다.
하지만 대칭키 암호학에서 해결하지 못한 문제점들이 있다.
이런 문제점들을 해결하기 위해 다른 방법을 시도했는데 바로 Asymmetric ciphers이고 그 중 공개키 암호학, public-key cryptography에 대해 알아보자.
Public-key Cryptography
등장 이유?
대칭키 암호화가 해결하지 못한 문제가 있다고 했는데 두 가지 문제가 있다.
대칭키 암호화의 문제점
-
Key distribution
- 안전하게 키를 가지고 있다면 대칭키 암호화가 분명 좋은 방법이지만 그 키는 어떻게 분배해서 서로 가지고 있을 것인가
-
Digital signatures
- 군 이외에도 암호학이 상용화되며 non-repudiation을 해결해야 했다.
참고로 전자서명은 non-repudiation 이외에도 authentication과 integrity 특성을 가질 수 있다.
그래서 이게 뭐냐
각자 public key와 private key를 가지고 있다.
public key는 누구나 알 수 있는 key이고, private key는 자신만 알고 있어야하는 key라 할 수 있다.
분명 각자 갖고 있다고 했다. Bob과 Alice가 서로 암호문 교환하려고 한다면 Bob은 Bob의 public key&private key를 가지고 있고, Alice는 Alice만의 public-key&private-key를 가지고 있어야 한다.
| Conventional Encryption | Public-Key Encryption | |
|---|---|---|
| 잘 동작하기 위해선 | 1. encryption과 decryption에 같은 key&알고리즘이 사용된다. 2. 송수신자가 동일한 key와 알고리즘을 공유해야한다. | 1. 한 쌍의 key를 가지고, 하나로는 encryption, 다른 하나로는 decryption한다. 2. 송수신자는 각각 매칭되는 key쌍을 가지고 있어야 한다. |
| 보안을 위해선 | 1. key는 비밀로 유지되야한다. 2. key만 비밀로 유지된다면 메시지 해석할 수 없어야한다. (암호 깨지지 않아야한다) 3. 알고리즘과 암호문 샘플을 알아도 key를 알 수는 없어야한다. | 1. 둘 중 하나의 key(Private key)는 비밀로 유지되어야한다. 2. Private key가 비밀로 유지되면 암호는 깨지지 않아야한다. 3.알고리즘과 암호문 샘플을 알아도 private key를 알 수 없어야 한다. |
그림으로 한번 보면 다음과 같다.
[출처] 위키피디아
엘리스가 밥에게 암호문을 보내고 싶다면 밥의 공개키로 잠근다. 공개키는 누구나 보고 사용할 수 있으니까.
그럼 밥은 자신만 가지고 있는 개인키로 암호문을 열어볼 수 있는 것이다.
그럼 전자서명은 어떻게 하는걸까?
[출처] 위키피디아
앨리스가 전자서명을 하는 상황이다. 엘리스가 전자서명을 해야하니 자신만 가지고 있는 개인키로 서명을 한다. 그래야 다른 누군가 자신이 엘리스마냥 서명을 할 수 없다. 엘리스의 개인키는 엘리스만 가지고 있으니까.
그럼 이 서명은 누구나 확인할 수 있다. 엘리스의 개인키로 잠갔으니 엘리스의 공유키로 누구나 서명을 확인할 수 있게 된다.
전자서명을 하고 이 전자서명을 잠글 수도 있다. 두 그림을 합치면 된다.
- 엘리스가 자신의 개인키로 서명
- 밥의 공개키로 암호화
- 전송 (엘리스가 밥에게)
- 밥은 자신의 개인키로 암호문을 복호화
- 엘리스의 공개키로 엘리스의 서명을 확인
어디다 써먹지? application
3군데에 써먹을 수 있다.
- Encryption/decryption
- Digital signature
- key exchange
어떤 알고리즘은 위의 3가지 애플리케이션 모두에 적합한 반면, 어떤 알고리즘들은 1~2군데만 사용할 수 있다.
대칭키 암호화에서 key를 안전하게 전달하기 위해 공개키 알고리즘을 사용할 수 있다. (Key exchange)
| Algorithm | Encrytpion/Decryption | Digital Signature | Key Exchange |
|---|---|---|---|
| RSA | O | O | O |
| Elliptic Curve | O | O | O |
| Diffie-Hellman | X | X | O |
| Elgamal | O | O | X |
| DSS | X | O | X |
RSA algorithm
RSA encryption/decryption
Euler totient function과 Euler's Theorem을 알고 있어야 이해할 수 있다.
그럼 대칭키 암호화는 이제 필요 없겠네?
그렇지 않다.
공유키 암호화는 대칭키 암호화에 비해 computing이 비싸다. 따라서 두 암호화 방식을 섞어 사용하는 경우가 많다.
그걸 Hybrid encryption이라고 하는데 아까 본 key exchange가 여기서 활용된다.
즉, 암호화의 전체적인 틀은 대칭키 암호화인데 여기서 서로 사용할 같은 키를 공유키 알고리즘을 사용해 교환한다.
Hybrid encryption에서는 암호문을 보낼 때 암호문 C 하나만 떡하니 보내는게 아니다.
보통 {,}를 보내는데 은 암호문, 는 암호화된 key를 나타낸다.
예: Alice가 Bob에게 메시지를 보낸다고 하자.
- Alice는 문서를 암호화할 key를 랜덤하게 생성한다.
- 그 key로 문서를 암호화한다. -> C1 생성
- 그 후, 해당 key를 Bob의 public key로 암호화한다. -> C2 생성
- 이렇게 생성된 {C1, C2}를 Bob에게 전송한다.
- Bob은 자신의 private key로 C2를 복호화해 key를 얻는다.
- 복호화한 key로 C1을 복호화해 plaintext를 얻는다.
RSA 서명
위에서 encryption과 다르게 생성할 때 자신의 개인키를 사용했다. 그리고 암호문을 보내는 것이 목적이 아니므로 원본 M을 서명과 함께 보낸다.
The Security of RSA
- Brute force(exchaustive key search)
- Mathematical attacks : p,q 소수 두개를 찾는 factoring 공격
- Chosen ciphertext attacks : RSA의
homomorphic특성 이용한 공격
- 그래서RSA-OAEP(Optimal Asymmetric Encryption Padding)를 사용 - Implementation attacks
- Side-channel attacks : timing attacks, power analysis attacks 등, 기기를 손상시키지않고 관찰하여 공격.
- Hardware fault-based attack : 기기를 손상시키며 공격
공개키 암호에 대한 오해
-
공개키 암호는 대칭 암호보다 안전하다? X
- 암호화 방식 자체가 달라서 그렇다고 얘기할 수 없다.
-
키의 길이가 같다면 공개키 암호와 대칭 암호의 안전성을 동일하다? X
- 대칭 암호가 더 안전하다.
-
공개키 암호는 대칭 암호를 완전히 대체할 수 있다? X
- 성능 자체는 대칭 암호가 훨씬 좋다. 그래서 보통 둘을 섞어서 사용하는 Hybrid 방식을 사용한다.
-
공개 키 암호화를 사용할 때 키 배포는 대칭 암호화를 위한 키 배포 센터와 관련된 번거로운 핸드쉐이킹과 비교할 때 사소하다? X
- 공개키 암호화를 이용한 키 분배에서도 상대방의 공개 키가 진짜 상대방 공개 키인지 확인하는 과정이 필요하다.
