(정수론/파이썬) RSA 암호화 및 복호화 함수

# RAS 암호화와 복호화
# 연습문제 18.5
# 암호를 풀 때 p와 q의 값을 넣어줘야 함.

import math
from number_util import *   # 정수론 함수들 모아놓은 것

# 암호책: 문자를 숫자로 바꾼다. 원래의 것에 공백과 문장부호 추가
cipher_book = {'A':11, 'B':12, 'C':13, 'D':14, 'E': 15, 'F':16, 'G':17, 'H':18, 'I':19, 'J':20, 
              'K':21, 'L': 22, 'M':23, 'N':24, 'O':25, 'P':26, 'Q':27, 'R':28, 'S':29, 'T':30,
              'U':31, 'V':32, 'W':33, 'X':34, 'Y':35, 'Z':36, ' ':37, '.':38, ',':39, "'":40, '!':41, '~':42}

# key:value 인 암호북으로 value: key 암호북을 새로 생성
cipher_book2 = {}
for key, value in cipher_book.items():
  cipher_book2[value] = key

#print(cipher_book2)
def RSA_incode(msg, m, k):
  msg = msg.upper() # 대문자로 바꾼다

  len_m = len(str(m))  # 9
  len_ = len_m - 1   # 8

  new_msg = "" # 메시지를 숫자로 바꾼 문자열
  # 문자를 숫자로 변환
  for c in msg:   #'TOBEORNOTTOBE'
    new_msg += str(cipher_book[c])

  #print(new_msg)  # "30251215252824253030251215"
  len_new_msg = len(new_msg)  # 26
  howmany = math.ceil(len_new_msg / (len_m - 1))  # 배열을 쪼갠 갯수 round(26/(9-1))+1 = round(3.25)+1 = 4

  div_new_msg = []
  for i in range(howmany): # 0~3
    if i == howmany - 1:  # 마지막이라면
      div_new_msg.append(int(new_msg[i*len_:]))
    else:
      div_new_msg.append(int(new_msg[i*len_:i*len_+len_]))

  #print(div_new_msg)  #[30251215, 25282425, 30302512, 15]

  ciphered_list = []
  for i in range(howmany): # 0~3
    #ciphered = div_new_msg[i] ** k % m  # 단순한 계산 방식. 수가 클 경우 시간이 많이 걸림.
    ciphered = my_successiveSquaring(div_new_msg[i], k, m)
    ciphered_list.append(ciphered)

  return ciphered_list # [149419241, 62721998, 118084566, 40481382]


# 암호 풀기
def RSA_decode(ciphered_list, m, k, p, q):
  # 1. phi_m 을 구한다. 소수 p와 q값을 알고 있기에 쉽게 구함
  phi_m = (p-1)*(q-1)

  # 2. k*u - phi_m*v = 1    1차 방정식을 푼다
  u, _ = linear_equation(k, phi_m)

  # 3. b^u (mod m) = x    : 연속제곱법으로 구한다
  answers = ""
  for ciphered in ciphered_list:
    answer = my_successiveSquaring(ciphered, u, m)  # 어떤 숫자
    answers += str(answer)

  #print("---------", answers) # '30251215252824253030251215'
  count = len(answers) // 2
  restored = ""   # 복원된 암호문 저장

  for i in range(count):
    tmp = int(answers[i*2:i*2+2])
    #print(i, tmp)
    restored += cipher_book2[tmp]

  return restored  # 복원된 암호문



msg = "To be or not to be"
p, q = 12553, 13007
m = p * q
k = 79921
lst = RSA_incode(msg, m, k)
print(msg)
print(lst)

restored = RSA_decode(lst, m, k, p, q)
print(restored)
print("----------")

# 암호 풀기: '친절한 수론 길라잡이' 제18장 127쪽 
lst = [145387828, 47164891, 152020614, 27279275, 35356191]
restored = RSA_decode(lst, m, k, p, q)
print(restored)
print("----------")

# 암호 풀기: '친절한 수론 길라잡이' 연습문제 18.1
m = 7081
k = 1789
phi_m = euler_phi2(m)

lst = [5192, 2604, 4222]
restored = RSA_decode(lst, m, k, 73, 97)
print(restored)
print("----------")

lst = [5272281348, 21089283929, 3117723025, 26844144908, 22890519533,
26945939925, 27395704341, 2253724391, 1481682985, 2163791130,
13583590307, 5838404872, 12165330281, 28372578777, 7536755222]

p = 187963
q = 163841
m = p*q
k = 48611

restored = RSA_decode(lst, m, k, p, q)
print(restored)
print("----------")


p = 27999999697
q = 27999999749
m = p*q  # 
k = 48611

msg = "I loved her. I didn't know that at that time. Now I regret so much."
ciphered_lst = RSA_incode(msg, m, k)
print(ciphered_lst)

word = RSA_decode(ciphered_lst, m, k, p, q)
print(word)

To be or not to be
[124051554, 123619784, 123420070, 44442925, 132143181]
TO BE OR NOT TO BE
----------
THOMPSONISINTROUBLE
----------
FERMAT
----------
MATHEMATICSISTHEQUEENOFSCIENCEANDNUMBERTHEORYISTHEQUEENOFMATHEMATICSKFGAUSS
----------
[668558382795708096991, 228096689983973528058, 329379656476946401863, 237383652483450007605, 116916970404156835769, 555511501219436113333, 577896737264214619388]
I LOVED HER. I DIDN'T KNOW THAT AT THAT TIME. NOW I REGRET 
SO MUCH.
PS C:\Users\m