Ch9:Public-key crptography and RSA

오늘은 공개키 암호 중에서도 가장 유명한 RSA에 대해 자세히 알아봅시다.

 

Private-key 

전통적인 암호학은 single key를 사용합니다. 암호화,복호화에 모두 하나의 키를 사용하는 겁니다. 만약 이 키가 공개될 경우 비밀성이 깨지게 됩니다. 

 

 

 

Key distribution problem 

 

A B C 와 통신을 위해서는 

(A,B) 둘만의 비밀키가 존재해야하고 

(B,C),(A,C) 각각 둘만의 비밀키가 존재해야합니다. 

그니깐 키를 완전히 분배해야합니다. 

제 3자의 둘만이 아는 키를 어떻게 분배할지가 문제점이 됩니다. 

 

 

Public-key 

두개의 키가 사용됩니다. 하나는 공개키고 하나는 비밀키입니다. 

asymmetric(비대칭)인데 이는 암호화할때와 복호화할때 쓰는 키가 다르다는 말입니다. 

 

특징

- 계산하기 어려운 문제

- 숫자가 많이 큼

- 성능이 안 좋음

 

public-key : 수신자의 공개키를 이용해 메세지 암호화(수신자만이 개인키로 풀 수 있게) , 성명 검증(상대방이 비밀키로 암호화하고 공개키로 복호화해서 확인)

 

private-key : 성명 생성, 메세지 복호화

 

다음과 같은 방식으로 진행이 됩니다. 

1. 상대방의 공개키로 메세지를 암호화합니다. 

2. 이 암호화한 메세지를 상대방에게 보냅니다. 

3. 상대방은 본인의 개인키로 암호화된 메세지를 복호화합니다. 

 

이게 비대칭키의 암호시스템입니다.

 

다음 그림으로 요약할 수 있습니다. 

 

암호화된 메세지를 얻는 법 : 수신자의 공개키로 암호화

원래의 메세지를 얻는 법 : 수신자의 비밀키로 복호화

---

공개키 암호의 목적, 활용

 

- key distribution (key exchange)

- digital signatures

 

다음은 어디에 어떤 알고리즘을 쓸 수 있는가 입니다. 

 

Algorithm	Encryption/Decryption	Digital Signature	Key Exchange
RSA	Yes	Yes	Yes
Elliptic Curve	Yes	Yes	Yes
Diffie-Hellman (분배를 하는 목적으로 만듦)	No	No	Yes
DSS (Digital Signature Standard)	No	Yes	No

 

 

공개키 암호가 기본적으로 가져야하는 특성

- computationally infeasible : 공개키가 공개되어도 비밀키를 찾기가 어렵습니다. 그리고 계산이 어려워야한다는 의미입니다.

 

 

---

Public Key Crytography - trapdoor one-way function 

 

공개키 암호의 또 다른 특성에 대해 알아보겠습니다. 바로 'trapdoor one-way function' 인데요

one-way Function 은 A -> B는 쉽습니다. 하지만 B -> A는 알기 어렵다는 의미입니다. 

간단한 예시를 들어보겠습니다. 함수가 A + B라고 했을때 A = 3, B= 5 면 답은 8이죠. 하지만 결과가 8이야! 라고 하면 이게 (1,7)일지 (2,6)일지 알기가 힘듭니다.(불가능은 아닙니다.) 이런 걸 one-way function 이라고 합니다. 

 

그럼 trapdoor one-way function 은 뭘까요? 위와 같이 'A->B 는 쉽고 B->A 는 어렵지만 C를 알면 쉬워진다.' 라는 겁니다. 어떤 요소가 있으면 알기 쉬워진다라는 의미인데요. 공개키 암호에서는 이 C 가 무엇인지 살펴보겠습니다.

 

 

예제1. 

n 이 클때 n = p x q 는 one way function 입니다. p, q를 알면 n는 그냥 곱셈에서 알면 됩니다. 하지만 n을 안다고 p,q를 알기 어렵습니다. 이게 factorization problem 입니다. (소인수분해 문제) 

 

예제2. 

n이 클때 y = x^k mod n 은 trapdoor one-way function 입니다. x, k, n 이 주어지면 당연히 y를 계산하기 쉽습니다. 하지만 y, k, n이 주어지만 x를 계산하기 어렵습니다. 이게 discrete logarithm problem 입니다. 

그러나 만약 우리가 trapdoor 인 k' 를 안다면 풀 수가 있습니다. k x k' = 1 mod 파이 n 

우리가 k'를 안다면 y^k' -> x^k ^ k' => x 이렇게 x를 쉽게 알아낼 수 있습니다. 이런 걸 trapdoor one-way function 이라고 합니다. 

---

서명 생성

다음은 서명을 생성하는 방법입니다. 수신자의 신원(?)을 확인을 위해 발송자가 자신의 비밀키로 서명을 암호화하고 수신자는 발신자의 공개키를 통해서 복호화하여 검증합니다. 

 

 

RSA 에 관한 내용입니다. 

https://com24everyday.tistory.com/112

RSA