[Python] RSA 암호화 알고리즘

RSA 암호화 알고리즘이란? 

- 대표적인 비대칭키(공개키) 알고리즘 

RSA는 두개의 키를 사용하는데, 모두에게 공개되는 공개키와 공개하지 않는 비밀키(개인키)가 있다.

공개키를 사용해서 암호화하고, 비밀키를 사용해서 복호화한다.

이 과정이 전자상거래(공인인증서)이다.

 

 

RSA 암호화 알고리즘의 원리와 과정을 프로그래밍 해봤다.

#두개의 소수 선언
p = 991
q = 997

#두 소수의 계수
n = p * q

#오일러의 피 함수 구하기
totient = (p - 1) * (q - 1)

#유클리드 호제법 사용해 최대공약수 구하기
def gcd(a, b):
    while b!= 0:
        a, b = b, a % b
    return a

#1 < e < totient, gcd(e, totient)가 1인 e를 구하기
# e는 공개키
def getPublicKey(tot):
    e=2
    while e < tot and gcd(e, tot)!= 1:
        e += 1
    return e

# ed를 (p - 1) * (q - 1)로 나눈 나머지가 1이 아니거나 d가 e이면 d의 값을 1씩 증가시킨다. 
# 위의 조건을 만족시키지 않을때, d값을 반환
def getPrivateKey(e, tot):
    d = 1
    while (e * d) % tot != 1 or d == e:
        d += 1
    return d

#암호화
def encrypt(pk, plaintext):
    key, n = pk
    
    # c = m^e % n 
    cipher = [(ord(char) ** key) % n for char in plaintext] #ord() : 문자를 인자로 받아 해당하는 유니코드 정수 값을 반환

    return cipher

#복호화
def decrypt(pk, ciphertext):
    key, n = pk
  
    # m = (c*d)%n
    plain = [chr((char ** key) % n) for char in ciphertext] #chr() : 정수를 인자로 받아 해당하는 유니코드 문자 값을 반환

    return ''.join(plain)

m = str(input("암호화 할 문자를 입력하세요:"))

e = getPublicKey(totient)

d = getPrivateKey(e, totient)

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

print("암호화 된 문자 : ", ''.join(map(lambda x: str(x), encryptMsg)))

print("복호화 한 문자 : ", decrypt((d,n), encryptMsg))

주의사항

- 개인 키의 길이가 긴 것을 사용해야한다.

길이가 길 수록 수학적 공격(소인수 분해)으로 부터 안전하다.

 

- 복호화 될 때에 소요되는 시간이 드러나지 않도록 해야 한다.

소요 시간으로 키의 길이를 추측할 수 있다.