RSA

RSA는 공개 키 암호 알고리즘의 하나로써 암호화뿐만 아니라 디지털 서명에 사용할 수도 있다

RSA는 세 사람의 개발자 이름, Ron Rivest, Adi Shamir, Leonard Adleman의 각각 첫글자를 따서 붙여졌다.

 

 

RSA에 의한 암호화

RSA에서는 평문, 키, 암호문 모두 숫자이다.

 

<암호화 식>

암호문 =  (평문)^E mod N (RSA 암호화)

<복호화 식>

평문 =  (암호문)^D mod N (RSA 복호화)

 

공개 키 (E, N)

개인 키 (D, N)

 

위의 식을 풀기 위해서는 E, D, N을 알아야 한다. 순서는 다음과 같다.

 

(1) N을 구한다

(2) L을 구한다 (L은 키 쌍을 생성할 때만 등장하는 수이다.)

(3) E를 구한다

(4) D를 구한다

 

 

 

예를 들어 p = 17, q = 19를 골라서 계산을 해보자.

 

(1) N을 구한다.

우선 큰 소수 2개(p, q)를 준비한다.

N = p x q

 

예1)

N = 17 x 19

    = 323

 

 

(2) L을 구한다

L은 암호화나 복호화에 등장하지 않는 수이다.(키 쌍을 생성할 때만 등장)

L = LCM(p-1, q-1)

 

예2)

L = LCM(16, 18)

   = 144

 

 

(3) E를 구한다.

1 < E < L 후보 군중에

gcd(E, L) = 1 를 만족하는지 조사한다. 이 때 유클리드 호제법을 이용.

E와 L의 최대공약수가 1이라는 의미는 E와 L이 서로소라는 것이다.

여기까지 E와 N을 구했기 때문에 공개 키의 키쌍이 만들어졌다.

 

예3)

gcd(E, 144) = 1  (144보다 작은 144와 서로소인 수들은 5, 7, 11, 13, 17, ... 등이 있다.)

E = 5로 선택

 

(4) D를 구한다.

1 < D < L

(E x D ) mod L = 1

위의 조건을 충족시키는 수 D를 찾아내면 E와 N으로 암호화한 암호문을 D와 N으로 복호화 할 수 있게 된다.

(E x D) mod L = 1 을 충족한다는 것은  E와 L이 서로소라는 것을 의미한다.

 

예4)

(5 x D) mod 144 = 1

D = 29

 

.

.

.

 

공개 키

(E, N) = (5, 323)

개인 키

(D, N) = (29, 323)

 

 

평문 '123' 을 암호화 한다고 하면

123^5 mod 323 = 225

'225'가 암호문이 되고

암호문 '225'를 복호화 한다면

225^29 mod 323 = 123

'123'이 평문이 된다.

 

 

 

 

 

<RSA에 대한 공격>

 

1. 암호해독자는 암호문으로부터 평문을 구할 수 있을까?

암호 해독자는 암호문, E, N을 알고 있기 때문에

암호문 =  (평문)^E mod N (RSA 암호화) 식을 이용하여 평문을 구할 수 있을 것 같다.

하지만 mod N 때문에 평문을 구하는 것은 이산대수를 구한다는 것으로 귀결되기 때문에

암호문을 해독하는 것은 매우 어려운 문제가 된다.
(이산대수를 구하는 빠른 방법을 아직 알지 못한다.)

 

2. 전사공격

'D'를 알면 암호문을 복호화 할 수 있다. 그렇기 때문에 D의 후보근을 모두 시도해서 복호화하는 전사공격을 시도할 수 있다.

통상 RSA에서의 p와 q의 비트는 512비트 이상을 N은 1024비트 이상을 이용한다. D를 찾아내기 위해서는 1024비트 이상의 전사공격이 필요하기 때문에 이 비트 길이의 전사공격에 의해D를 찾아내는 것은 매우 어렵다.

 

3. E와 N으로부터 D 구하기

암호해독자는 D를 모르지만 공개키인E와 N은 알고 있다. 키 쌍을 생성할때 D는 E로부터 계산해서 얻어내기 때문에 암호해독자도 D를 생성해낼 수 있을 것처럼 보인다. 하지만 불가능하다 이유는 다음의 식에서 알 수 있다.

(E x D) mod L = 1

위의 관계식에서 사용된 L은 lcm(p-1, q-1)이므로 E로부터 D를 구할 때는 p와 q를 알아야한다.
하지만 암호해독자는 p와 q를 알지 못하기 때문에 D를 구할 수 없는 것이다.

 

여기에서 중요한 포인트는 p와 q이다.

소수p와 q를 절대로 암호해독자가 알게 해서는 안된다는 점이다!

만약 암호해독자가 p와 q를 알게 된다면 암호해독자가 개인키를 알게될 것이다.

 

p와 q를 절대로 암호해독자가 알게 해서는 안되지만 N = p x q 라는 관계식이 존재하며 N은 공개되어 있는 수이다.

암호해독자는 N이라는 숫자를 소인수분해하여 소수인 p와 q를 추측해낼 수 있다.

N이 작은 수라면 N을 소인수분해하여 p와 q를 찾아내는 건 비교적 쉬울 수는 있으나 N이 엄청나게 큰 수라면

그  큰 수를 소인수분해 하는 것은 현실적으로 불가능하다.

 

 

4.중간자 공격

중간자공격이란 RSA암호를 직접 해독하는 것은 아니고 송/수신자 사이에 들어가서 송신자에게는 수신자인 것처럼 수신자에게는 송신자인 것처럼 행세하는 공격 방법이다.

 

 

 

 

공개 키 암호로 키 배송문제가 해결됐다고 생각될 수도 있으나 중간자공격을 막아야 할 필요가 있다.

그러기 위해서는 입수한 공개 키가 정말로 유효한 공개 키인지를 인증하는 수단이 필요해지는데

이때 사용하는 것이 공개 키 인증서이다.

 

공개 키 인증서는 추후에 공부하도록 하자.

 

 

 

 

 

 

<참고 : 히로시 유키 - 알기 쉬운 정보보호개론>