-
파이썬, RSA 암호화Python/파이썬 자료구조 알고리듬 2020. 10. 26. 03:06반응형더보기
대칭키 암호화
일반적으로 암호라고 하면 떠올리는 방식입니다.
암호문을 생성할 때, 복원할 때 같은 키를 사용합니다.
난수표나 시저 암호도 대칭키 암호화죠.장점은 단순하기 때문에 빠르다는 것.
단점은 빠르다는 것 외에는 모두 다입니다.
보내는 사람 받는 사람이 같은 키를 가지고 있기 때문에
분실에 취약하다는 점이 있습니다.
2명이 가지고 있으면 사고 날 확률도 2배...대칭키는 비밀을 유지하기 위해서 개인별 암호가 필요합니다.
(여러 명의 스파이에게서 보고를 받을 때...
스파이마다 암호가 달라야 스파이 사이에도 비밀이 유지됩니다.)암호 관리가 힘듭니다.
문서에 대한 인증이 필요할 때 공인 인증 기관이 필요합니다.
이런 단점을 극복하고자 공개키 암호화가 나왔습니다.
공개키 암호화
수학적인 쌍을 이루는 두 개의 키를 공개키, 개인키로 나눠서
'공개키로 암호화'한 데이터를 '개인키로 복원'하는 겁니다.
암호화하는 키와 복원하는 키가 다릅니다. @,.@단점은 느리다는 것이겠죠?
그 외에는 전부 장점입니다.
공개키는 분실해도 되고,
하나의 공개키로 여러 명이 쓰더라도
공개키만 가지고는 서로의 메시지를 볼 수 없기 때문에 안전합니다.문서의 작성자가 개인키를 가지고 문서를 암호화한 뒤
공개키와 암호화된 문서를 공개합니다.
받은 사람은 공개키로 암호화된 문서를 복호 합니다.
문서가 정상적으로 복원이 되면,
위조되지 않았음을 알 수 있습니다.대표적인 공개키 암호화인 RSA 알고리듬을 간략히 알아보겠습니다.
공개키, 개인키 만들기
1. 두 소수 p(=11), q(=13)를 준비합니다.
두 소수의 곱은 공개키 (2개) 중 하나가 됩니다.
두 소수는 계산하기 어려울 정도로 커야 합니다만...
쉽게 쉽게...
2. phi = (p-1)(q-1) = 10*12 = 120을 구합니다.
3. phi = (p-1)(q-1)와 서로소인 정수 e(encryption, =7)를 준비합니다.
또한 1 < e < phi 여야 합니다.
e는 공개키가 됩니다.
공개키는 어차피 공개할 것이라 선택이 비교적 자유롭습니다.
보통 1의 비트가 2개인, 3(11)이나 65537(10000000000000001) 같은 소수를 씁니다.
4. ed(=7*d)를 phi=120으로 나눈 나머지가 1이 되도록 하는 d(decryption, =103)를 찾습니다.
또한 1 < d < phi 여야 합니다. d는 개인키가 됩니다.
e가 (p-1)(q-1)과 서로소가 아니면 이를 만족하는 d는 존재하지 않습니다.
5. N=pq(=143)를 계산한 후, 공개 키인 N과 e(=7)를 공개합니다.
d는 개인키이며 숨겨둡니다.
p, q, (p-1)(q-1) 등은 보안에 문제를 일으킬 뿐입니다.
모두 파기합니다.
출처: 나무위키 https://namu.wiki/w/RSA%20%EC%95%94%ED%98%B8%ED%99%94암호화 및 복호화
원본 메시지를 m,
암호화된 메시지를 M,
e, n은 공개키,
d는 개인키라고 할 때.암호화는 M = m ** e % n
복호화는 m = M ** d % n입니다.파이썬의 REPL에서 계산해 봅시다.
6을 암호화하면 85
85를 복호화하면 6이 나옵니다.>>> 6 ** 7 % 143 85 >>> 85 ** 103 % 143 6어떻게 돌아가는 지 코딩할 수 있을 정도는 알 것 같습니다.
수학적으로 이해하기 위해서는 다음 글을 참고하시면 될 것 같습니다.
https://tramamte.github.io/2018/07/25/rsa/이제 코딩해 봅시다.
먼저 서로 다른 2개의 소수를 고릅니다.
from random import randint def is_prime(n): if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True def find_primes(start, end): prime1 = prime2 = 0 while not is_prime(prime1): prime1 = randint(start, end - 1) while not is_prime(prime2): prime2 = randint(start, end - 1) return prime1, prime2phi를 구하고, 서로소인 e를 준비합니다.
서로소란 최대 공약수가 1이라는 뜻이니까
유클리드 호제법을 이용합시다.math.gcd를 이용할 수도 있습니다만...def gcd(a, b): while b: a, b = b, a % b return a def find_e(phi): e = None for i in range(2, phi): if gcd(phi, i) == 1: e = i break return e개인키인 d를 찾습니다.
def find_d(phi, e): d = None for i in range(phi // e, phi): if e * i % phi == 1: d = i break return d암호화 및 복호화는 하나의 함수로 가능한데...
가독성을 위해 나눴습니다.주석으로 처리할 것을 함수명으로 처리하면
가독성이 좋아진다고... 어디서 봤습니다... ^^제곱을 반복하면 숫자가 너무 커지고, 연산은 느려집니다.
이를 방지하기 위해 중간중간 % 처리합니다.def get_mod(message, exp, n): result = message for i in range(1, exp): result = (result * message) % n return result def encrypt(message, e, n): return get_mod(message, e, n) def decrypt(message, d, n): return get_mod(message, d, n)전체 코드입니다.
# RSA TEST 2020-10-05 from random import randint def is_prime(n): if n < 2: return False for i in range(2, int(n ** 0.5) + 1): if n % i == 0: return False return True def find_primes(start, end): prime1 = prime2 = 0 while not is_prime(prime1): prime1 = randint(start, end - 1) while not is_prime(prime2): prime2 = randint(start, end - 1) return prime1, prime2 def gcd(a, b): while b: a, b = b, a % b return a def find_e(phi): e = None for i in range(2, phi): if gcd(phi, i) == 1: e = i break return e def find_d(phi, e): d = None for i in range(phi // e, phi): if e * i % phi == 1: d = i break return d def generate_keys(): n, e, d = 0, None, None while e is None or d is None: prime1, prime2 = find_primes(1000, 10000) n = prime1 * prime2 phi = (prime1 - 1) * (prime2 - 1) e = find_e(phi) d = find_d(phi, e) return n, e, d def get_mod(message, exp, n): result = message for i in range(1, exp): result = (result * message) % n return result def encrypt(message, e, n): return get_mod(message, e, n) def decrypt(message, d, n): return get_mod(message, d, n) def main(): # message: int = int(input('암호화할 숫자를 입력하세요:')) message: int = 6 n, e, d = generate_keys() print('공개키:', n, e, '개인키:', d) encrypted = encrypt(message, e, n) print('암호화된 숫자:', encrypted) decrypted = decrypt(encrypted, d, n) print('복호화된 숫자:', decrypted) if __name__ == '__main__': main()공개키: 30431903 5 개인키: 18251957 암호화된 숫자: 17293413 키 제작부터 암호화까지 걸린 시간: 4.022498369216919 복호화된 숫자: 5555 복호화에 걸린 시간: 5.229518413543701비밀키를 찾는데 걸리는 시간을 측정해 보았습니다.
def find_secret_key(n): sieve = [True for _ in range(n)] sieve[0] = sieve[1] = False primes = [] for i in range(2, n): if sieve[i]: primes.append(i) for j in range(i * 2, n, i): sieve[j] = False for i in range(len(primes) - 1): for j in range(i + 1, len(primes)): if primes[i] * primes[j] == n: return primes[i] * primes[j] print(find_secret_key(30431903))파이썬(cpython) 3.8에서는 180초 정도 걸립니다.
Working Time [find_secret_key]: 176.46851658821106 30431903파이파이(pypy) 3.7에서는 다음과 같습니다.
Working Time [find_secret_key]: 37.28349709510803 30431903암호체계는 비밀에 부쳐질 필요가 없어야만 하며, 적의 손에 떨어지더라도 문제가 없어야 한다.
(암호 알고리듬의 은닉에 암호 체계의 안전을 의존해서는 안된다.
암호 알고리듬이 공개되더라도, 비밀 키만 잘 숨겨 두면, 비밀은 유지될 수 있어야 한다. )
케르크호프스의 원리(Kerckhoffs's principle)PyCryptodome
실제 프로젝트에서는 외부 모듈로 암호화를 구현하면 됩니다.
검색을 해보면 PyCrypto 모듈에 대한 언급이 많습니다.
하지만 PyCrypto는 2012년에 업데이트가 중단되었고,MS 윈도 환경에서는 설치가 잘 안됩니다.(Visual Studio용 Build Tools이 설치되어 있다면..... 잘 됩니다.)PyCrypto보다는 PyCryptodome을 사용하는 게 편한 것 같습니다.
PyCryptodome은 PyCrypto의 fork입니다.문서화도 잘 되어 있습니다. @,.@
https://pycryptodome.readthedocs.ioPyCrypto의 마지막 공식 버전인 (2.6.1) 보다 몇 가지 향상이 있다고 합니다.
(세월이 얼마나 지났....)
윈도에서는 PyCryptodomex를 쓰라는 말도 있으나, PyCryptodome도 잘 설치되었습니다.
PyCrypto와 PyCryptodome을 동시에 설치하진 말랍니다.PyCryptodome은 대부분 pure 파이썬으로 작성되었고,
속도에 치명적인 영향을 주는 부분만 C 언어로 작성되었다고 합니다.공식 홈페이지의 예제입니다.
개인 키와 공개 키를 만듭니다.
from Crypto.PublicKey import RSA key = RSA.generate(2048) private_key = key.export_key() file_out = open("private.pem", "wb") file_out.write(private_key) file_out.close() public_key = key.publickey().export_key() file_out = open("receiver.pem", "wb") file_out.write(public_key) file_out.close()암호화합니다.
from Crypto.Cipher import AES, PKCS1_OAEP from Crypto.PublicKey import RSA from Crypto.Random import get_random_bytes data = "I met aliens in UFO. Here is the map.".encode("utf-8") file_out = open("encrypted_data.bin", "wb") recipient_key = RSA.import_key(open("receiver.pem").read()) session_key = get_random_bytes(16) # Encrypt the session key with the public RSA key cipher_rsa = PKCS1_OAEP.new(recipient_key) enc_session_key = cipher_rsa.encrypt(session_key) # Encrypt the data with the AES session key cipher_aes = AES.new(session_key, AES.MODE_EAX) ciphertext, tag = cipher_aes.encrypt_and_digest(data) [file_out.write(x) for x in (enc_session_key, cipher_aes.nonce, tag, ciphertext)] file_out.close()복호화합니다.
from Crypto.Cipher import AES, PKCS1_OAEP from Crypto.PublicKey import RSA file_in = open("encrypted_data.bin", "rb") private_key = RSA.import_key(open("private.pem").read()) enc_session_key, nonce, tag, ciphertext = \ [file_in.read(x) for x in (private_key.size_in_bytes(), 16, 16, -1)] # Decrypt the session key with the private RSA key cipher_rsa = PKCS1_OAEP.new(private_key) session_key = cipher_rsa.decrypt(enc_session_key) # Decrypt the data with the AES session key cipher_aes = AES.new(session_key, AES.MODE_EAX, nonce) data = cipher_aes.decrypt_and_verify(ciphertext, tag) print(data.decode("utf-8"))PyCryptodome에서 RSA와 관련된 부분입니다.
https://www.pycryptodome.org/en/latest/src/public_key/rsa.html#
https://pycryptodome.readthedocs.io/en/latest/src/examples.html#generate-an-rsa-key반응형