(파이썬/정수론) RSA 암호 풀기와 예제

# RAS 암호 풀기와 예제 '친절한 수론 길라잡이' 제18장 본문
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}

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

print(cipher_book2)

msg = "To be or not to be"
msg = msg.upper().replace(' ', "")  # 대문자로 바꾼 뒤, 공백을 제거한다 "TOBEORNOTTOBE"

p, q = 12553, 13007
m = p * q
k = 79921
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 = round(len_new_msg / (len_m - 1)) + 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]

# div_new_msg[0] ^ 79921 (mod 163276871) = ?
# div_new_msg[1] ^ 79921 (mod 163276871) = ?
# div_new_msg[2] ^ 79921 (mod 163276871) = ?
# div_new_msg[3] ^ 79921 (mod 163276871) = ?

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)

print(ciphered_list) # [149419241, 62721998, 118084566, 40481382]

### 암호 풀기
# 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):
  restored += cipher_book2[int(answers[i*2:i*2+2])]

print(restored)  # 복원된 암호문


# '친절한 수론 길라잡이' 제18장 127쪽
#################################### 암호 풀기
ciphered_list = [145387828, 47164891, 152020614, 27279275, 35356191]

# x ^ k = b (mod m) : then x = ?
# x ^ 79921 = 145387828 (mod 163276871)
# x ^ 79921 = 47164891 (mod 163276871)
# x ^ 79921 = 152020614 (mod 163276871)
# x ^ 79921 = 27279275 (mod 163276871)
# x ^ 79921 = 35356191 (mod 163276871)

# 1. phi_m(m)을 구한다
phi_m = (p-1)*(q-1)  # 163251312

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

# 3. 연속제곱법으로 푼다.
# b^u (mod m)

answers = ""
for ciphered in ciphered_list:
  answer = my_successiveSquaring(ciphered, u, m)  #[30182523, 26292524, 19291924, 30282531, 122215]
  answers += str(answer)

print(answers) # '30182523262925241929192430282531122215'

# 해독된 숫자를 문장으로 바꾼다.
count = len(answers) // 2
restored = ""   # 복원된 암호문

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

print(restored)

실행:

{11: 'A', 12: 'B', 13: 'C', 14: 'D', 15: 'E', 16: 'F', 17: 
'G', 18: 'H', 19: 'I', 20: 'J', 21: 'K', 22: 'L', 23: 'M', 
24: 'N', 25: 'O', 26: 'P', 27: 'Q', 28: 'R', 29: 'S', 30: 'T', 31: 'U', 32: 'V', 33: 'W', 34: 'X', 35: 'Y', 36: 'Z'}  
30251215252824253030251215
[30251215, 25282425, 30302512, 15]
[149419241, 62721998, 118084566, 40481382]
--------- 30251215252824253030251215
TOBEORNOTTOBE
30182523262925241929192430282531122215
THOMPSONISINTROUBLE