[python] RSA (Rivest, Shamir and Adleman) 알고리즘

RSA 암호 알고리즘은 대표적인 공개키 알고리즘 중 하나로

소인수 분해의 어려움을 이용한 방식을 사용하고 있다.

 

사용자는 각각 공개키와 개인키를 갖고 있다

메시지를 보낼때는 송신자가 수신자의 공개키로 암호화 한 후 전송하면

수신자는 수신자의 개인키로 복호화한다.

 

RSA 암호 알고리즘의 암호화, 복호화 공식

<RSA 공개키, 개인키 구하기>

1. 먼저 2개의 소수(p, q)를 선택합니다.

2.  n 을 구합니다 n = p * q

3.  φ(n)을 구합니다 φ(n) = (p-1)(q-1)

4.  1 < e < φ(n) 을 만족하는 φ(n)과 서로소인 자연수 e를 구합니다

5. e mod φ(n) = 1 을 만족하는 d를 구합니다

여기서 공개키는 (n, e) 쌍이 되고, 개인키는 d 가 됩니다.

 

<소스코드>

# RSA 암호화 프로그램
def encipher(p, n, pk):
    c = ''
    i = 0
    while i < len(p):
        m = ''
        for j in range(4):
            m += p[i+j]
        i += 4
        a = int(m)
        t = a
        for k in range(pk):
            b = t % n
            t = a * b
        if b < 10:
            c += '000' + str(b)
        elif b < 100:
            c += '00' + str(b)
        elif b < 1000:
            c += '0' + str(b)
        else:
            c += str(b)

    return c

def encode(p):
    m = ''
    for i in range(len(p)):
        a = ord(p[i])
        if a == 32: a = 64
        a -= 64
        if a == 0:
            m += '00'
        elif a < 10:
            m += '0' + str(a)
        else:
            m += str(a)

    return m

def decipher(c, n, s):
    p = ''
    i = 0
    while i < len(c):
        m = ''
        for j in range(4):
            m += c[i+j]
        i += 4
        a = int(m)
        t = a
        for k in range(s):
            b = t % n
            t = a * b

        if b < 100:
            p += '00' + str(b)
        elif b < 1000:
            p += '0' + str(b)
        else:
            p += str(b)

    return p


plainText = 'SAVE PRIVATE RYAN '
N = 3713
S = 97
P = 37
plainMessage = encode(plainText)
print('평 문 : ', plainMessage)
cipherMessage = encipher(plainMessage, N, P)
print('암호문 : ', cipherMessage)
print('복호문 : ', decipher(cipherMessage, N, S))

 

 

* 공부하며 정리한 내용이라 틀린 부분이 있을 수 있습니다. 

틀린 부분이 있으면 말씀해주세요!