[컴퓨터 보안] Public Key Cryptography(공개키 암호) and RSA

Public-Key Cryptosystems의 원칙들

• 공개키 암호는 대칭 암호가 해결하지 못한 두 가지 문제점을 풀기 위해 시도된 암호이다. 
  • Key distribution:
    • key를 어떻게 안전하게 전달
  • Digital signature (Nonrepudiation):
    • 누가 보낸 메시지인지 확인할 수 있음을 보장

 

 

Public-Key Cryptosystems

• 대칭키 암호에서는 하나의 key를 공유해서 사용하는 것과 달리 공개키 암호에서는 public key와 private key 두 개의 key가 존재한다.
• public key는 말 그대로 공개된 키이며, private key는 자신만 알고 있는 key이다.
• 용도에 따라 다음과 같이 작동한다.
• 상황 1. Bob이 Alice한테 암호문을 보내려고 한다.
  • 목적: 암호화 및 복호화

Bob은 공개되어 있는 Alice의 public key로 plaintext를 암호화하여 Alice에게 보낸다. 

Alice는 보유 중인 본인의 private key로 해당 암호문을 복호화하여 plaintext를 얻어낸다.

여기서 public key와 Encryption/Decryption algorithm은 공격자가 알 수 있다.

• 상황 2. Bob이 Alice한테 계약서 보내려고 함.
  • 목적: 서명 생성 및 확인 (Nonrepudiation을 위해)

Bob은 자신의 private key를 이용해 plaintext를 암호화하여 Alice한테 보낸다.

Alice는 Bob의 public key를 이용해 암호문을 복호화하여 plaintext를 얻어낸다.

제대로 된 plaintext가 출력되었다는 것은 Bob이 보낸 계약서가 맞음을 확인할 수 있다.

또한 데이터가 중간에 변조되지 않았음을 보장할 수 있으므로 Integrity(무결성) 또한 확인할 수 있다.

즉, 이 경우(전자서명) Integrity, Authentication, Nonrepudiation을 모두 해결할 수 있다. 

 

 

 

Conventional Encryption vs Public-Key Encryption

	Conventional Encryption	Public-Key Encryption
작동을 위해 필요한 것	1. 같은 key와 알고리즘을 사용하여 encryption/decryption한다. 2. 송수신자가 동일한 key와 알고리즘을 공유한다.	1. 한 쌍의 key를 가지고, 하나로는 encryption, 다른 하나로는 decryption한다. 2. 송수신자는 각각 매칭되는 key쌍을 나눠가진다.
보안을 위해 필요한 것	1. key는 비밀로 유지되야한다. 2. key만 비밀로 유지된다면 메시지 해석할 수 없어야한다. (암호 깨지지 않아야한다) 3. 알고리즘과 암호문 샘플을 알아도 key를 알 수는 없어야한다.	1. 둘 중 하나의 key(Private key)는 비밀로 유지되어야한다. 2. Private key가 비밀로 유지되면 암호는 깨지지 않아야한다. 3.알고리즘과 암호문 샘플을 알아도 private key를 알 수 없어야 한다.

 

 

공개키 암호: 인증(Authentication)과 기밀성(Confidentiality)

• 상황: Alice가 Bob한테 메시지를 보낸다고 하자.
• 암호문(Z) 생성: plaintext -> Alice의 private key로 암호화(인증을 위해) -> Bob의 public key로 암호화 (기밀성을 위해)

• 즉, 암호문(Z)은 다음과 같이 암호화되어 있다. 
• 이를 해독하기 위해서는 겉부터 복호화한다.

 

 

Applications for Public-Key Cryptosystems

• 공개키 암호 시스템의 용도 3가지
  • Encryption/Decryption
    • 송신자는 수신자의 public key로 메시지를 암호화한다.
  • Digital Signature
    • 송신자는 자신의 private key로 메시지에 서명한다.
  • Key exchange
    • 양측이 협력하여 세션 키를 교환한다.
• 어떤 알고리즘은 위의 3가지 애플리케이션 모두에 적합한 반면, 어떤 알고리즘들은 1~2개만 사용할 수 있다.
• 대칭키에서 key를 안전하게 전달하기 위해 공개키를 사용할 수 있다. (Key exchange)

Algorithm	Encryption/Decryption	Digital Signature	Key Exchange
RSA	Yes	Yes	Yes
Elliptic Curve	Yes	Yes	Yes
Diffie-Hellman	No	No	Yes
DSS	No	Yes	No

 

 

RSA(Rivest-Shamir-Adleman) 알고리즘

• -> 공개키 암호에서 일반적으로 사용되는 접근
• Bit sequence를 정수로 취급해서 연산한다.
  • 즉, 어떤 n에 대해 plaintext와 ciphertext를 0~(n-1) 사이의 정수로 표현한다.

• Public-Key = {e, n}
• Private-Key = {d, n}

 

 

 

긴 길이의 메시지는 어떻게 처리할까?

• 메시지를 여러 블락으로 나누고, 각각 public/private key 만들어서 전송하려남? Nope!
• 보통 Hybrid encryption 방식을 이용한다.
  • 대칭 키 암호 방식을 이용하되, key를 공개키 암호를 이용하여 공유한다.
• 작동 방식
  • 암호 메시지를 보낼때 {C1, C2} 두 개를 보낸다.
    • C1: 암호화된 문서
    • C2: 암호화된 Key
      • C2 = $K^e$ mod n
  • 예: Alice가 Bob에게 메시지를 보낸다고 하자.
    1. Alice는 문서를 암호화할 key를 랜덤하게 생성한다.
    2. 그 key로 문서를 암호화한다. -> C1 생성
    3. 그 후, 해당 key를 Bob의 public key로 암호화한다. -> C2 생성
    4. 이렇게 생성된 {C1, C2}를 Bob에게 전송한다.
    5. Bob은 자신의 private key로 C2를 복호화해 key를 얻는다.
    6. 복호화한 key로 C1을 복호화해 plaintext를 얻는다.
• 왜 이렇게 하나요?
  • 메시지가 길어지면, 메시지를 여러 개의 블락으로 나눠야 하고, 암호화 알고리즘을 여러 번 거쳐야 한다.
  • 이때, 공개키 암호 알고리즘은 성능이 안 좋기 때문에 느리다.
  • 그래서 빠른 대칭키 암호로 많은 양을 암호화시켜 속도를 향상하고, 
  • 대신 대칭 키 암호에는 안전하게 key를 공유하는데 안전성 문제가 있을 수 있으므로, 공개키 암호를 사용해 안전성을 높였다.

 

 

RSA 서명

• 상황: Alice가 Bob에게 계약서를 보낸다고 하자.
  • Signature(S) = $M^d$ mod n
  • Alice의 private key = {d, n}
  • Alice의 public key = {e, n}
• Alice는 Bob에게 {M, S} 쌍을 보낸다. -> {메시지, 서명}
• Bob은 계약서를 받고 서명(S)을 Alice의 public key를 이용해 복호화해본다 -> M = $S^e$ mod n
• 이 작업을 통해 Integrity, Authentication, Nonrepudiation을 모두 보장할 수 있다.

 

 

Modular 연산에서 exponentiation

• RSA는 moular에 대해 정수 제곱하는 연산을 많이 한다.
• 아래의 modular 특성을 이용해 효과적으로 계산해보자.
  • [(a mod n) x (b mod n)] mod n = (a x b) mod n
• 예: $7^{1000110000}$을 구해보자

지수를 이진수로 표현한다.

즉, $7^1$에 제곱한 것을 $7^{10}$로 표현할 수 있다.

예를 들어, $7^{10001}$은 ($7^{100}$의 제곱)x7이다.

 

 

 

 

공개키 암호에 대한 오해

• 공개키 암호는 대칭 암호보다 안전하다? Nope
  
  • 암호화 방식 자체가 달라서 그렇다고 얘기할 수 없다.
• 공개키 암호는 대칭 암호를 완전히 대체할 수 있다? Nope
  • 성능 자체는 대칭 암호가 훨씬 좋다. 그래서 보통 둘을 섞어서 사용하는 Hybrid 방식을 사용한다.
• 대칭 암호의 키 공유 문제를 해결하기 위해 나온게 공개키 암호이다. 그렇다면 공개키 암호는 키 공유 문제가 전혀 없는가? Nope
  • 상대적으로 나은 것이지, 그 문제가 근본적으로 해결된 것은 아니다.
  • 대칭 암호는 기밀성이 보장된 상태, 공개키 암호는 무결성과 인증이 보장된 상태로 키 분배해야한다. 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]