📝 공개키 암호 - RSA

공개키 암호는 대칭키 암호의 취약점을 해결하고자 한 노력의 결과로 탄생하였다.
그렇기에 비대칭키 암호로도 불리며, 대칭키 암호와 다르게 암호화와 복호화에 사용하는
암호키가 서로 다르다.

공개키 암호는 한 쌍의 키가 존재하며, 하나는 특정 사람만 가지는 개인키,
다른 하나는 누구나 가질 수 있는 공개키로 이루어져있다.

대칭키 암호의 취약점인 키 전달에 대한 문제를 해결하였으나, 암호화, 복호화를 위해
복잡한 수학연산을 수행하기 때문에 대칭키 암호에 비해 속도가 느리다는 단점이 있다.

현재는 용량이 큰 정보는 대칭키로 암호화하고, 암호화에 사용된 대칭키는
다시 공개키로 암호화하여 대상에게 전달하는 하이브리드 암호화 방법이 일반적이다.

이 글에서는 대표적인 공개키 암호인 RSA에 대해 알아보겠다.

---

📌공개키 암호의 원리

원리

대부분의 공개키 암호는 정보가 부족한 상황에서 매우 어려워지는 수학문제를 바탕으로
만들어진다. "매우 큰 수의 소인수분해", "이산로그방정식의 해 구하기" 등이 있다.

소수 a, b 가 있다. 우리는 이 두 수의 곱을 쉽게 구할 수 있고 이를 c라 하자.

c = a x b

여기서 a와 b는 비밀로 유지되는 소수 값(개인키) 이고
c는 누구나 볼 수 있는 공개키의 일부다.

c를 공개한다고 하더라도 a와 b를 구하는 것은 c가 a 또는 b (큰 소수)로 나누어 떨어지는
모든 경우의 수를 확인해야 구할 수 있다.

수가 커질수록 연산시간은 기하급수적으로 늘어나며, 현재 컴퓨터 기술로는 몇백만년,
혹은 그 이상이 걸리므로 사실상 해독이 불가능하다고 볼 수 있다.

암호화와 복호화

그렇다면 암호화와 복호화는 어떻게 이루어질까?
이는 정보를 a로 암호화 할 경우 c에 의해서만 복호화 가능하고,
정보를 c로 암호화하면 a에 의해서만 복호화 되도록 특별한 수식을 사용한다.
자세한 예시는 아래의 RSA 암호에서 다룬다.

공개키 암호화와 공개키 서명

A와 B가 있는 상황에서 A는 B의 공개키로 정보를 암호화하고 B에게 전달한다.
B는 자신의 개인키로 복호화하여 정보를 확인한다.
이는 B의 공개키로 암호화 했기 때문에 B의 개인키로만 복호화 가능하다.

반대로, B가 자신의 개인키로 어떤 정보를 암호화하고 A에게 전달할 때에는
A는 자신이 가지고 있는 B의 공개키를 가지고 복호화할 수 있다.
만약에 B의 공개키로 복호화 되지 않으면 이 정보는 B가 보낸 정보가 아닌 것이다.

이와 같이 어떤 사람이 자신의 개인키로 암호화하고 이를 다른 사람이 공개키로 복호화 하여,
전달 받은 정보가 특정 사람이 보냈다는 것을 확신할 수 있게 하는 것을 공개키 서명이라고 한다.

공개키 기반 구조 (PKI)

그렇다면 특정 사람의 개인키와 공개키는 어떻게 생성할 것이며,
어떻게 배포할 것이고, 어떻게 관리할 것인가?

공격자는 중간에서 위조된 공개키를 배포하고, 본인이 위조한 개인키로 서명한 문서를
사용자에게 보내도 사용자는 위조된 공개키로 문서를 인증하므로 위조 사실을 알 수 없다.

이를 해결하기 위해 디지털 인증서를 도입하게 되었고, 이를 활용하는 소프트웨어, 하드웨어,
정책, 제도, 사용자 등을 총칭하여 공개키 기반 구조 라고 한다.

---

📌RSA (Rivest, Shamir and Adleman)

개발자의 이름을 따서 만든 RSA 암호는 국제기구의 암호 표준일 뿐만 아니라
산업표준으로도 권장할 정도로 강력한 보안을 제공한다.

RSA는 소인수 분해 문제의 어려움에 기반한 연산을 제공하여
공개키가 제공되어도 이를 개인키로 역산시키기 어려운 점을 이용하였다.

RSA 암호화에서:
공개키는 (e, C) - e는 공개지수, $C = a * b$
개인키는 (d, C) - d는 개인지수, $C = a * b$

데이터를 M이라고 하고 암호문을 E라고 할때,
암호화는 공개키를 사용: $E = M^c mod C$(공개키의 e와 C만 사용, a와 b는 공개되지 않음)
복호화는 개인키를 사용: $M = E^d mod C$ (개인키의 d와 C가 필요, a와 b는 공개되지 않음)

위의 e 와 d는 특별하게 계산된 값으로 다음 성질을 만족한다.
$M = (M^e)^d mod C = M^{e \cdot d}modC$
이 성질을 통해 공개키로 암호화한 정보를 개인키로 복호화 할 수 있다.

RSA 암호화에서는 2048비트 크기의 소수를 사용한다.
2048비트 = 약 $10^617$ 크기의 숫자

이 크기의 소수는 가능한 숫자 범위 중 약 $1/ln(x)$ 비율로 존재하며
2048비트 범위에 존재하는 소수의 개수는 약 $10^{615}$ 개 라고 할 수 있다.

이를 $N = p * q$ 로 구성된 RSA 키에서 p 와 q 를 구하기 위해 가능한 조합의 수는
$10^{306} * 10^{306} = 10^{612}$ 로, 현재 컴퓨터로는 탐색이 불가능에 가까운 수준이다.

RSA를 이용하여 암호화, 복호화를 수행한 코드는 다음과 같다.

from Crypto.Cipher import PKCS1_OAEP
from Crypto.PublicKey import RSA


def rsa_enc(msg):
    # 1024비트 개인키 생성
    private_key = RSA.generate(1024)
    # 개인키에 대응하는 공개키를 얻는다다
    public_key = private_key.publickey()
    # 공개키 암호 표준(PKCS#1), 암호화 전 패딩 추가
    cipher = PKCS1_OAEP.new(public_key)
    encdata = cipher.encrypt(msg)
    print(encdata)

    cipher = PKCS1_OAEP.new(private_key)
    decdata = cipher.decrypt(encdata)
    print(decdata)


def main():
    msg = "samsjang loves python"
    rsa_enc(msg.encode("utf-8"))


main()

위 코드는 암호화와 복호화가 잘 작동하나, 프로그램이 종료되면 생성한 개인키와 공개키가
사라져 버린다. 공개키는 잃어버려도 개인키만 있으면 언제든 가지고 올 수 있으니
개인키를 잘 저장하면 된다.

아래는 개인키와 공개키를 파일로 저장하여 보관하는 방법이다.

from Crypto.PublicKey import RSA

def createPEM() :
	private_key = RSA.generate(1024)
    h = open('privatekey.pem', 'wb+')
    h.write(private_key.exportKey('PEM'))
    h.close()
    
    public_key = private_key.publickey()
    h = open('publickey.pem', 'wb+')
    h.write(public_key.exportKey('PEM'))
    h.close()

createPEM()

이를 실행하여 생성된 개인키와 공개키 파일을 이용하여 RSA 서명을 구현하면 다음과 같다.

from Crypto.Signature import pkcs1_15
from Crypto.PublicKey import RSA
from Crypto.Hash import SHA256 as SHA


def readPEM(pemfile):
    h = open(pemfile, "r")
    key = RSA.importKey(h.read())
    h.close()
    return key


# 개인키로 서명한 후 상대방에게 보내는 과정
def rsa_sign(msg):
    private_key = readPEM("privatekey.pem")
    public_key = private_key.publickey()
    h = SHA.new(msg)
    signature = pkcs1_15.new(private_key).sign(h)
    return public_key, signature


# 공개키를 이용하여 서명을 확인하는 과정
def rsa_verify(msg, public_key, signature):
    h = SHA.new(msg)

    try:
        pkcs1_15.new(public_key).verify(h, signature)
        print("Authentic")
    except Exception as e:
        print(e)
        print("Not Authentic")


def main():
    # 서명을 확인하는 쪽에서는 확인해야 할 msg를 이미 알고있고,
    # 개인키에 대응되는 공개키를 가지고 있다고 가정한다.
    msg = "My name is samsjang"
    public_key, signature = rsa_sign(msg.encode("utf-8"))
    rsa_verify(msg.encode("utf-8"), public_key, signature)


main()

---