RSA 암호화 알고리즘 분석

RSA 알고리즘이란?

현대 컴퓨터 시스템 및 다른 전자기기에서 데이터를 암호화/복호화할 때 사용.

두 개의 다른 key를 사용하는 비대칭(asymmetric) 암호학 알고리즘이다. 

 

유클리드 알고리즘(유클리드 호제법)

1. a,b 두 수가 주어짐.(a>b)
2. b가 0이면 a를 리턴함.
3. a가 b로 나눠 떨어지지 않으면 a를 b로, b를 a에서 b로 나눈 나머지를 대입하고 1번으로 돌아감.
a = b
b = a%b
위 코드를
temp = a%b
a = b
b = temp
이런 식으로도 쓸 수 있다.

유클리드 알고리즘을 이용해 38, 10의 최대공약수 구하기
38%10 = 8
a= 10, b= 8 (a에는 b, b에는 a%b 대입)
다시 나눈다.
10%8 = 2
a= 8, b=2
8%2= 0
최대공약수는 2가 된다.

gcd함수 구현 안하고도 math 라이브러리에서 gcd import해서 사용할 수 있다.

 

오일러 피 함수(Euler's totient function)

1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수.

 

φ(9) = 6 

1~9까지의 자연수 중 9와 최대공약수가 1인 수(서로소인 수)는  1, 2, 4, 5, 7, 8

RSA 알고리즘의 구현

매우 큰 소수 p와 q를 선택.

n = pq, k = φ(n)을 구한 후

e*d = 1+k에서 e와 d를 구한다.

 

n과 e(공개키)는 public으로 공개되고, d는 개인키이다. 

0<m<n인 정수 m으로 표현되는 메시지는 계산에 의해서 암호화된다.

암호화

C = m^e mod n

복호화

t = c^d mod n 
#복호화된 메시지 t = 오리지널 메시지 m

RSA 알고리즘 7단계

1. 두개의 소수 p, q 정하기(너무 작으면 제대로 암/복호화가 이루어지지 않는다.)

 

2. 두 키의 계수인 n=p*q를 구한다.

 

3. 오일러의 피 함수 = (p-1)(q-1)

 

4. 1<e<totient, gcd(e, totient) = 1인 e를 구한다.  -> e는 공개키이다.

 

5. e*d % totient == 1이 되는 d를 구한다. -> d는 개인키이다.

 

6. 암호화된 메시지 c= m^e%n을 구한다. 

m = 메시지 각각의 단일 문자를 아스키 코드로 변환한 값.

 

7. m = c^d%n을 이용 복호화된 메시지 구하기

 

 

공개키, 개인키 만들기
1. 두 소수 p(=11), q(=13)를 준비한다.
두 소수의 곱은 공개키(2개) 중 하나가 된다.

2. phi = (p-1)(q-1)= 10*12=120을 구한다.

3. phi = (p-1)(q-1)와 서로소인 정수 e(ecryption, =7)를 준비한다.
-> 120과 서로소인 정수
또한 1< e<phi 여야 한다.
e는 공개키가 된다.
보통 1의 비트가 2개인 3(11)이나 65537 같은 소수를 쓴다.

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는 개인키이므로 숨겨둔다.

#서로소를 따지려면 최대공약수 함수가 필요하다.

from math import gcd

import math

p = 991
q = 997  #서로 다른 두 소수

n = p*q # 두 소수의 계수
tot = (p-1)*(q-1) #오일러 피함수

def gcd(a, b): #최대공약수 구하기
    while b!=0:
        temp = a%b
        a = b
        b = temp
    return a

 
def find_e(tot): #공개키 구하기
    e = 2
    for i in range(2,tot):
        if gcd(tot, i) == 1:
            e = i
            break
    return e

def find_d(tot, e): #개인키 구하기
    d = 3
    for i in range(tot//e, tot):
        if e*i%tot == 1:
            d = i
            break
    return d



 

def enc(pk, plaintext): #암호화 
    key, n = pk 

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

    

def dec(pk, ciphertext): #복호화
    key, n = pk

    plain = [chr((char**key)%n)for char in ciphertext]
    return ''.join(plain)




e = find_e(tot) #공개키 구하는 함수에 위에서 구한 오일러 피함수 대입
d = find_d(tot, e) # 인자로 오일러 피함수와 공개키 대입

m = str(input("암호화할 문장 입력:")) #평문입력받기

encrypted = enc((e,n), m) #암호문
print("암호문 : ", ''.join(map(lambda x: str(x), encrypted))) #암호문 출력
decrypted = dec((d,n), encrypted) #복호문
print("복호문 : ", decrypted) #복호문 출력