RSA 공개 키 암호방식

우선 RSA라는게 공개 키 알고리즘의 하나인데

 

RSA 이름은 어떻게 만들어졌냐 하면??

 

• 개발자 3명의 이름
• Ron Rivest, Adi Shamir, Leonard Adleman의 이니셜(Rivest- Shamir-Adleman)

 

호랑이는 가죽을 남기고 사람은 이름을 남긴다라는 말이 언제나 맞는 것같다.

 

 

 

암호화 방법과 복호화 방법은 정말 간단하다.

 

 

??  뭐야?? 이렇게 간단해?? 라고 생각하면

맞긴 한데... 뒤에서 설명하겠다.

 

 

---

우선 RSA 암호의 구성을 살펴보자

 

공개키로 암호화 하고 개인키로 복호화 하는 방식이다 그렇지??

 

 

 

 

 

---

 

 

그렇다면 공개키, 개인키 등 암호에 필요한 숫자들을 어떻게 구하는지 알아봐야겠지??

 

키를 만드는 순서는 이렇다.

 

1) N을 구한다
2) L을 구한다
(L은 키 쌍을 생성할 때만 등장하는 수이다)
3) E를 구한다
4) D를 구한다

 

 

1)

큰 소수를 2개 준비( p와 q)
 N = p × q (p, q는 소수)

 

 

2)

L 은 RSA의 암호화나 복호화에 사용안한다. ( 잠깐 만드는거다)
키 쌍을 만들 때 임시로 사용
L = lcm(p-1, q-1) 
(L은 p-1 과 q-1의 최소공배수)

 

3)

다음 두 식을 만족하는 수 E를 하나 찾아낸다
1 < E < L
gcd(E, L) = 1 (E와 L은 서로 소)

 

4)

다음 두 식을 만족하는 수 E를 하나 찾아낸다
 1 < D < L
 E × D mod L = 1

 

간단하지???

---

그렇지만 정말 암호화를 하고싶다거나... 복호화를 해야해서 계산을 해야한다면..?

 

우선 소수 p,q를 선택하고 평문M 을 선택해보자

 

p = 11, q = 13, M = 23으로 정해보자

 

암호화 해보고 복호화 해보겠다.

 

 

글씨,,, 못쓰는거 아는데

천재는 선택이고 악필은 필수자나 ㅎㅎ

 

 

 

저기 잘보면 왜 23^7을 나눠서 했냐면... 엄청 크잖아.. 손으로 계산 못한다ㅠㅠㅠ

 

23^43도 그렇다.. 그래서 나눠서 계산했다.

 

 

그렇다. 계산이 무지하게 어렵다..

 

---

?? 그렇다면 RSA 암호방식은 지수 승이 너무 커서 그것으로 보안성을 유지하느냐??

 

아니죠 어떻게 방어하는지 알아보자

 

 

 

1. 직접 접근

 

직접 접근으로 암호문을 평문으로 바꾸고 싶다면

이산 대수 문제를 풀어야하는데 
현재까지 아직 이산 대수를 구하는 빠른 방법을 알지 못해서 이 방법은 거의 불가능에 가까운.. 방식

 

 

 

2. 전사공격

 

물론 전사공격이라고,, 키가 될 수 있는 후보들을 다 넣어서 계산하는 방식이 있지만

 

D의 후보가 되는 수를 순서대로 모두 시도해서 복호 화 해본다
** D의 비트 수가 크면 클수록 어려워진다
** 비트 수가 충분히 크면 전사공격으로 수 D를 찾아내는 것은 현실적으로는 불가능
** RSA에서는 p와 q의 비트 수로서 512 비트 이상을 사용
** N은 1024 비트 이상을 이용
**E나 D는 N과 같은 정도의 크기로 할 수 있으므로 D를 찾으려면 1024 비트 이상의 전사공격이 필요

사실 영원한 암호란 것은 없지만 지금 성능으로는 전사공격으로 죽을 때 까지해도 못찾기 때문에... 

 

 

3. E와 N으로 D 구하기

 

N = p × q라는 관계식을 공격자는 알고 있고 N은 공개되어 있다

 

++N으로부터 p와 q를 구할 수는 없는 것일까????
p와 q는 소수이기 때문에 N으로부터 p와 q를 구한다는 것은 자연수 N을 소인수분해하는 것

 

큰 수를 고속으로 소인수분해 할 수 있는 방법이 발견되면 RSA를 깰 수 있지만 현재 큰 수의 소인수분해를 고속으로 행
하는 방법은 아직 발견되지 않아서 정말 힘든 작업이 될 것이다.

 

** 소인수분해를 간단히 수행하는 방법이 존재하는 지의 여부도 아직 모른다

++소수란 아직 풀리지 않은 수수께끼들이 많아서.. 암호에 자주 이용하는 이유기도 하다.

 

 

4. p,q 추측하기

 

p와 q는 의사난수 생성기로 생성하기 때문에 의사난수 생성기의 품질이 나쁘면 p와 q를 암호 해독자가 추측할 수 있다
그래서 난수 생성기가 강력하게 해서 암호 해독자가 추측할 수 없도록 해야한다.

 

 

5. 중간자공격

 

사실 암호 알고리즘을 직접 푸는 것보다 여기가 제일 어렵다.

RSA를 해독하는 게 아니니까 너무 좋다 ㅎㅎ 기밀성을 침해하는 공격이다. 

 

공격자 맬로리가 송신자와 수신자 사이에서 송신자에 대해서는 수신자처럼

수신자에 대해서는 송신자처럼 행세하는 공격

 

어떤 식으로 공격을 할까 살펴보자

 

색으로 잘 구분하자

 

1) 앨리스는 밥의 공개 키 요청

2) 맬로리는, 앨리스의 요청을 도청

3) 밥은 자신의 공개 키를 앨리스에게 전 송

4) 맬로리는 밥의 이 메일이 앨리스에게 도달하지 못하도록 하고, 밥의 공개 키를 보존

5) 맬로리는 자신의 공개 키를 밥의 공개키라고 속여서 앨리스에게 전송

6) 앨리스는 자신의 메시지를 밥의 공개 키(착각하고 있음)로 암호화

 

7) 앨리스는 암호화한 메시지를 밥에게 전송

8) 맬로리는 앨리스의 암호 메일을 갈취해서 자신의 개인키로 복호화하고 평문을 확보

9) 맬로리는 앨리스 행세를 하며 위조 메일(을 만들고 위의 단계 (4)에서 보존해 둔 밥의 공개키를 써서 이 위조 메일을 암호화하여 밥에게 전송

10)밥은 받은 암호 메일을 자신의 개인 키로 복호화하고 메일( P’)을 읽게 된다

 

 

그렇다 중간자 빼면 보안성이 높은 알고리즘 RSA에 대해서 알아봤다.