RSA 암호화 파이썬 코딩 - 2018.11.25

--2018.11.25년도에 작성되었던 글을 옮겨왔습니다--

 

학교에서 보안수업을 듣는데 얼마전에

RSA 암호화를 파이썬으로 직접 코딩해보고 간단하게 예시를 통해

암호화 과정을 설명하라는 과제가 나왔습니다.

​

RSA 암호화는 암호화 하는데 사용하는 키와 복호화하는데 사용하는 키가

서로 다른 비대칭 암호화 방식이라 합니다.

​

즉 공개키로 암호화한 문서는 공개키로 복호화 할 수 없고, 대신

개인키로만 복호화 가능한 암호화 방식입니다.

​

먼저 암호화 과정에서 쓰이는 알고리즘들을 정의해 보았습니다.

​

def encrypt(pk, text):

key, n = pk

cipher = [(ord(char) ** key) % n for char in text]

return cipher

​

(암호화(encrypt) 정의)

보내려는 문자의 아스키코드인 ord(char) [char 은 text에 있는 하나의 문자]

에 key 번 만큼 제곱한 다음 n으로 나눈 나머지로 암호화 합니다.

​

def decrypt(pk, text):

key, n = pk

plain = [chr((char ** key) % n) for char in text]

return ''.join(plain)

​

(복호화(decrypt) 정의)

받은 암호문을 암호화 과정과 유사한 계산으로 복호화 합니다.

def gcd(a, b):

while b!=0:

a, b = b, a%b

return a

(공개키를 구하는데 사용하는 유클리드 호제법 (최대공약수 구하기))

​

def public_key(tot):

e=2

while e<totient and gcd(e, totient)!=1:

e += 1

return e

(공개키, totient 는 오일러 피 함수로 구한 수 입니다.)

​

def private_key(e, tot):

k=1

while (e*k)%tot != 1 or k == e:

k+=1

return k

(개인키)

​

-암호화할 문장을 입력합니다. (대충)

m = "I am major in computer science and I like listening to information security class“

-두 개의 소수 p, q를 정합니다.

p = 277, q = 53

​

-두 키의 계수가 되는 n = p*q를 구합니다.

n = p*q

print("두 키의 계수=",str(p),"*",str(q),"=",str(n))

​

-오일러 피함수가 되는 (p-1)*(q-1)을 구합니다. k = φ(n)

totient = (p-1)*(q-1)

print("오일러 피함수 K( (p-1)*(q-1) ) =",str(totient))

​

-공개키 e를 구합니다.

e = public_key(totient)

print("공개키(n, e):("+str(n)+","+str(e)+")")

​

-개인키 d를 구합니다.

d = private_key(e, totient)

print("개인키(n, d):("+str(n)+","+str(d)+")")

​

-공개키 e와 계수 n = p*q 를 이용해 암호화 합니다.

encrypted_msg = encrypt((e,n), m)

print('Encrypted Message:', encrypted_msg)

​

(print 결과)

Encrypted Message: [11626, 8347, 12289, 8352, 8347, 8352, 12289, 10441, 8690, 14324, 8347, 5723, 13638, 8347, 3810, 8690, 8352, 6769, 7086, 14564, 1963, 14324, 8347, 14635, 3810, 5723, 1963, 13638, 3810, 1963, 8347, 12289, 13638, 7488, 8347, 11626, 8347, 7452, 5723, 9276, 1963, 8347, 7452, 5723, 14635, 14564, 1963, 13638, 5723, 13638, 6541, 8347, 14564, 8690, 8347, 5723, 13638, 6025, 8690, 14324, 8352, 12289, 14564, 5723, 8690, 13638, 8347, 14635, 1963, 3810, 7086, 14324, 5723, 14564, 2747, 8347, 3810, 7452, 12289, 14635, 14635]

​

-개인키 d와 계수 n을 이용해 복호화 합니다.

decrypt((d,n),encrypted_msg)

print('Decrypted Message:', decrypt((d,n),encrypted_msg))

​

(print 결과)

Decrypted Message: I am major in computer science and I like listening to information security class

​

RSA 암호화는 원리는 그렇게 어렵지 않은것 같긴 했지만

파이썬으로 코딩하는게 쉽지가 않았습니다;;

파이썬은 공부한 적이 거의 없어서 구글링을 많이 했습니다.

​

역시 구글링만한 게 없는것 같아요

​

(https://wkdtjsgur100.github.io/RSA-algorithm/) - 참고

RSA 알고리즘 개념 및 구현(python)

RSA 알고리즘이란?

wkdtjsgur100.github.io

* 작성한 코드에는 오타가 끼어 있을 수도 있습니다. 그대로 따라 작성하더라도 오류가 날수 있어요