RSA 알고리즘 뚫기 [Python]

도입 - RSA의 등장 배경

RSA란 1977년 리베스트(R), 샤미르(S), 애들먼(A) 이 개발한 공개키 암호 알고리즘이다. 공개키 암호란 암호를 만들거나 푸는데 사용하는 "키" 의 일부를 공개하는 방법이다.

간단히 좀더 자세하게 설명해보겠다. 먼저 가장 간단한 암호체계를 소개한다. 알파벳을 몇개씩 밀어서 암호를 만드는 방법(카이사르 암호)은 들어본 적, 혹은 간단히 떠올려본 적 있을것이다. "good" 이라는 단어에서 알파벳을 하나씩 뒤로 밀면 "hppe"가 된다. 이 암호 체계의 본 상황에서는 "한"칸씩 알파벳을 밀었기에 키 k=1이라고 할 수 있다. 알파벳을 A부터 Z까지 0~25에 대응시킨다면 평문 P를 암호문 C로 바꾸는 상황(암호화), 암호문 C를 평문 P로 바꾸는 상황(복호화) 는 아래와 같은 식으로 나타낼 수 있다.

$$ C = P+1 \ mod \ 26 $$ $$ P = C-1 \ mod \ 26 $$

$$ k=1 $$

위와 같은 식은 카이사르 암호의 암호화-복호화 식이다. 키는 k 하나만 존재하고, 이는 암호화 할 때, 복호화할 때 모두 필요하다는 것을 알 수 있다. 따라서 카이사르 암호를 통해 비밀리에 정보를 주고받으려면, 우선적으로 서로 키 k를 공유해야한다. 이때, 키를 공유하는 과정에서 탈취당할 수 있고, 변조당할 수도 있으며 물리적으로 주고받지 않는 이상 전산상의 보안문제도 항상 존재한다. 따라서 비밀리에 키를 공유할 필요가 없는 암호체계인 공개키 암호체계의 개념이 제시되었다.

RSA의 개념

RSA는 키를 생성하기 위해 총 3개의 정수 N, E, D가 필요하다. 먼저 큰 소수 두개 p, q를 정하고, 이를 바탕으로 일련의 복잡한 과정(여기서는 다루지 않는다. 아래 코드엔 포함되어있다)을 거쳐 생성된 세개의 수는 공개키인 (E, N) 그리고 개인키인 (D, N)을 이루게 된다. 공개키를 통해 암호화가, 개인키를 통해 복호화가 가능하다. 따라서 수신자는 개인키를 공개해선 안되고 본인만 안전하게 보관하여야한다. 키를 배송할 필요도 없다. 평문 P와 암호문 C에 대해 RSA의 암호화, 복호화의 식은 다음과 같다. 아래 식이 성립하도록 수학적 과정으로 키를 생성하는 것이다.

$$ C = P^E \ mod \ N $$

$$ P = C^D \ mod \ N $$

공개키로부터 개인키를 얻는것은 매우 어려워서, RSA의 안정성이 보장된다.

RSA를 통한 암호화, 복호화 구현해보기.

지금부터는 문자가 아닌 숫자를 암호화한다고 생각하면 편할 것 같다. 문자를 숫자로 변환하는 함수는 따로 구현되어있고 암,복호화 함수는 숫자만을 다룬다.

코드 0. 필요한 라이브러리

아래의 네 라이브러리를 사용한다.

import math
import random
import time
import numpy as np

코드 1. 문자열-숫자리스트 변환

def str2int(ss):
    ss = list(ss)
    ii = []
    for s in ss:
        if s == ' ':
            ii.append(32)
            continue
        ii.append(ord(s)-ord('a'))
    return ii

def int2str(ii):
    ii = list(ii)
    ss = []
    for i in ii:
        if i==32:
            ss.append(' ')
            continue
        ss.append(chr(i+ord('a')))
    ss = ''.join(ss)
    return ss

위 코드는 문자열을 숫자 리스트로, 숫자 리스트를 문자로 변환하는 코드이다. 공백은 아스키코드인 32로 예외처리하였다. A부터 Z까지 0에서 25로 변환하였다.
다음으로 RSA의 키를 생성해보겠다. 먼저 두 소수 p, q는 다음과 같이 적당히 큰 메르센소수로 정하였다.

p = 2**13-1
q = 2**17-1 #Mersenne prime numbers

이제 아래는 키를 생성하고 출력하는 코드이다. 또한 encRSA, decRSA는 입력받은 정수형 리스트의 각 값을 RSA로 암호화 및 복호화하는 함수이다.

start = time.time()

N = p*q
L = math.lcm(p-1,q-1)

E = L//2#적당한 아무 수 생성
while(math.gcd(E,L) != 1):
    E = random.randint(1,L)

D = L//2
while((E * D)%L != 1):
    D = random.randint(1,L)

def encRSA(a):
    for i in range(len(a)):
        a[i] = pow(a[i],E,N)
    return a

def decRSA(x):
    for i in range(len(x)):
        x[i] = pow(x[i],D,N)
    return x

end = time.time()

print(f"RSA Key generating time : {end - start}")

print(f"Public Key (E, N) : ( {E} , {N} )")
print(f"Private Key (D, N) : ( {D} , {N} )")

다음은 사용 예제이다. 평문 hello를 숫자형 리스트, 그를 암호화한것, 다시 복호화한 것을 출력하는데, 암호화 후 복호화 한 것이 평문과 같음을 볼 수 있을 것이다.

a = 'hello'

print(str2int(a))
enc = encRSA(str2int(a))
print(enc)
dec = decRSA(enc)
print(dec)

핵심 - RSA를 뚫어보자 !!

위 코드는 int형 범위 이내의 작은 정수를 사용하였지만 실제 RSA는 p,q의 곱이 2^2048 정도인 RSA-2048정도는 사용한다. 이를 뚫는 것은 매우 어렵지만 위에서 쓴 작은 RSA는 가능하다. RSA에 대해 가장 많이 알려진 공격방법은 소인수분해 공격이다. 공개키중 하나인 N은 RSA를 생성할 때 사용한 두 소수 p,q의 곱이다. p,q는 공개되면 이를 통해 공격자가 키를 생성해 개인키까지 알아낼 수 있다. 따라서 N을 소인수분해하여 p,q를 얻는 것이다. 또 다른 방법은 D값을 추정하는 것이 있다. 먼저 D값을 임의의 자연수로 추정한다. 임의의 평문을 암호화 후 추정하는 D값으로 복호화하였을 때 평문과 같다면 추정한 D 값이 찾으려는 D값과 같을 것이다. (수학적으로 정확한지는 모르겠다.) 이를 통해 개인키를 모두 알아낼 수 있다. 먼저 D에 대한 공격의 코드부터 소개한다.

D에 대한 공격

1부터 D값을 순차적으로 추정해가며 올바른지 확인한다.

start = time.time()
stkRSA = 3

print(stkRSA)
enc = pow(stkRSA,E,N)
print(enc)

atkD = 1
while True:
    dec = pow(enc,atkD,N)
    if stkRSA == dec:
        break
    atkD += 1

end = time.time()
print(f"\nSingle Key attacking time : {end - start}  (by brute force attack on D)\n")

print(f"Founded private key D is {atkD}")
print(f"Real D is {D}")

위 코드를 이용해 D값을 찾는 데, 나는 37초 가량 걸렸다.

N 소인수분해 공격

p 값을 1부터 순차탐색하고 (무조건적으로 제곱근 N까지만 탐색하긴 하지만) 소인수분해가 되는지 확인한다.
위의 D에 대한 공격보다 훨씬 짧은 시간이 걸렸다.

start = time.time()

atkP = 2
while True:
    if N % atkP == 0:
        break;
    else :
        atkP += 1
atkQ = N // atkP

end = time.time()

print(f"\nSingle Key attacking time : {end - start}  (by prime factorization attack on N)\n")

print(f"Founded generating prime numbers (p,q) is {atkP,atkQ}")
print(f"Real P,Q is ( {p}, {q} )")

결론

RSA를 실습해보고싶지만 코드가 없는 사람들에게 이 글이 많은 도움이 되었길 바란다. 혹시 작동이 안되는 부분, 오류가 있다면 알려주세요!