RSA (Rivest, shamir, adelman)

0. RSA 정리

위의 증명에서 사용한 오일러 법칙은 다음과 같다.

1. 수치로 계산해보는 RSA encryption

1) 문제 풀이 

2) 문제풀이 계산과정

2. 중국인 나머지 정리(CRT : Chinese Remainder Theorem)을 사용한 복호화

이 결과는 mod n에서 계산하는 것 보다 mod p 와 mod q계산이 더 효율적임을 보여준다.

이를 이해할려면 중국인 나머지 정리부터 이해해야 한다.

3. RSA 공격

1) Chosen Ciphertext Attack

2) small e with the same small message and different

3) circular encryption attack

적긴 했지만...사실 이해가 안간다.

4) OAEP (optimal Asymmetric Enryption)

이전의 RSA는 Chosen Ciphertext Attack에 취약했다. 이 때 메세지 m을 조금만 변형 시키면 안전하게 암호화를 할 수 있다. 식이 어려워 보일지 모르나 그림을 보면 쉽게 이해할 수 있다.

이렇게 기본 메시지를 s || t 로 바꾸어 준다.

m = s xor G(H(s) xor t) 로 볼 수 있다.

결국 메시지를 암호화 하기전에 조금의 연산을 거친 뒤 암호화를 하게 되면 공격이 매우 힘들어지는 효과를 얻을 수 있다.

4. RSA 파라미터(parameter)

그렇다면 보안성이 높은 RSA 키를 생성하기 위해선 어떤 조건이 성립해야할까?

다음과 같은 조건이 성립하면 안전한 키를 생성했다고 한다.

1) p와 q를 선택할 때는 2^n -1 을 선택하는 것이 좋다.

2) p와 q의 크기는 비슷해야 한다.

3) p-1 와 q-1 는 많은 소수를 가져야 한다.

4) p-1와 q-1의 최대공약수는 매우 작아야 한다.

그리고 2p-1이 소수인 수를 safe prime이라고 한다.

5. 메시지가 n보다 길 때?

메시지가 길면 이를 블록화해야하는데 이는 매우 어렵다.

따라서 하이브리드 방식을 통해 암호화를 진행한다.

1) c1 = 우선 키를 가지고 RSA를 만든다. 

2) c2 = 그 키를 가지고 암호화를 한다.

3) 전송시 c1과 c2를 함께 전송한다.

4) 상대방은 c1을 복호화하여 키를 획득하고 이 키로 c2를 복호화하면 메시지를 볼 수있다.

6.RSA 서명

RSA는 공개키를 사용해 메시지를 암호화하는 용도 외에

개인키를 사용해 자신임을 인증하는 방식으로도 사용할 수 있다.

이때 해쉬함수가 필요하다. 이 해쉬함수는 이전에 설명한 3가지 조건이 다 성립해야 한다.

자신이 보내려는 메시지를 서명하려고할 때 

1) H(m) : 우선 메시지를 해쉬화한다.

2) S : 해쉬화 한 메시지를 RSA 개인키를 사용해 암호화한다.

3) (m, S) : 메시지와 암호화된 메시지를 함께 전달한다.

4) S^e = H(m) : RSA 공개키를 사용해 암호화된 메시지를 복호화한다.

5) H(m) : 기본 메시지를 해쉬함수를 사용해 해쉬값을 알아낸다.

6) H(m) =? S^e : 복호화한 값과 해쉬값이 일치하면 인증이 성공됨을 의미한다.