- RSAの仕組みを学習して、その仕組みを使った簡単なツールを作成しました
- RSAの仕組みはQuizKnockの動画で学習しました
- 動画内の問題を解くことで、RSAの仕組みについて感覚的に理解できる内容になっています
- 問題をコーディングで解きました(Pythonを使用)
- 応用として、RSAの仕組みを使ったエンコード・デコードツールを作成しました
- 注意
- 作成したエンコード・デコードツールは全然実用的ではありません
- あくまで学習のためのコードであることをご留意ください
Quizknockの動画で学習
- 問題の詳細・RSAの解説については、QuizKnock様の動画を是非ご覧ください
問題1：0101→AA、0102→ABと変換する場合、23011819→？
コード(問題1)
# input
key_num = "23011819"
def number_to_alphabet(key_num):
# アルファベットのリストを定義(index番号0~25がA~Zに対応)
alphabet = [
"A", "B", "C", "D", "E", "F", "G",
"H", "I", "J", "K", "L", "M", "N",
"O", "P", "Q", "R", "S", "T", "U",
"V", "W", "X", "Y", "Z"
]
# 数字の数をチェック(奇数の場合は頭に0を付与)
if len(key_num) % 2 != 0:
key_num = key_num.zfill(len(key_num)+1)
# 2文字ずつ切り取る→アルファベットに変換→リストに格納
key_word_char = []
for char_num in range(0, len(key_num), 2):
slice_start = char_num
slice_end = slice_start + 2
char_slice = key_num[slice_start:slice_end]
append_char = alphabet[int(char_slice)-1]
key_word_char.append(append_char)
# リストに格納した文字を結合
key_word = "".join(key_word_char)
return key_word
if __name__ == "__main__":
key_word = number_to_alphabet(key_num)
print(key_word)
実行結果
WARSコード(問題1)の解説
- アルファベットのリストを定義
- index番号+1(1~26)がA~Zに対応している
- 数字の桁数を確認
- A~I(01~09)が最初の文字の場合、奇数桁になる
- 後程2桁ずつ切り出す処理をしたいので、奇数桁の場合は頭に0を付け足す(
zfill) - ↑の処理をするため、最初の入力は文字列にしている
- 2桁ずつ取り出し、アルファベットに変換→リストに格納
- スライスで2桁ずつ取り出す
- 取り出した2桁がアルファベットに対応しているので、リストのindex番号として指定(
alphabet[番号-1]) - リストのindex番号は0~のため、取り出した番号-1にする
- リストのアルファベットを結合(
join)して単語に→回答(WARZ)
問題2：p=37、q=71、e=79であるとき、暗号文「904」を解読せよ
コード(問題2)
import part1
# input
p = 37
q = 71
e = 79
c = 904
def calc_message(p, q, e, c):
n = p * q
phi = (p-1)*(q-1)
# m(p-1)(q-1)≡-1(mod e)を満たすmを求める
num = 1
while True:
target_num = e * num - 1
if target_num % phi == 0:
m = target_num // phi
print("search complete.")
break
num = num + 1
print("m = ", m)
# mからdを計算
d = (m * (p-1) * (q-1) + 1) // e
print("d = ", d)
# C,d,nからMを計算
M = pow(int(c), int(d), int(n))
print("M = ", M)
return M
if __name__ == "__main__":
M = calc_message(p, q, e, c)
# アルファベットに変換(問題1のアルファベット変換関数を利用)
word_M = part1.number_to_alphabet(str(M))
print(word_M)実行結果
m = 10
d = 319
M = 1526
OZコード(問題2)の解説
- $m(p-1)(q-1) \equiv -1 \pmod e$ を満たす$m$を求める ※後述
- 求めたmからdを計算
- 暗号文C、d、n(=pq)からMを計算
- M(数字)をアルファベットに変換し、元の文を求める
- 問題1で作成した関数
number_to_alphabetを使用
- 問題1で作成した関数
$m(p-1)(q-1) \equiv -1 \pmod e$ を満たす$m$を求める
- m(p-1)(q-1)をeで割った余りがe-1になるmを探す
- mを1~探すと時間がかかるため、式を変形して工夫する
$m(p-1)(q-1) \equiv -1 \pmod e \Leftrightarrow m(p-1)(q-1) \equiv e-1 \pmod e$ を別の形で書くと
$m(p-1)(q-1) = ex + e - 1$ ($x$は任意の自然数)
$\Leftrightarrow m(p-1)(q-1) = ex' - 1$ ($x' = x + 1$)
-
この式を満たす自然数$m$がある時、$m = \frac{ex'-1}{(p-1)(q-1)}$ と計算できる
- $x'$を1~順番に確認する
- $(p-1)(q-1)$で割り切れた時の$m$を計算
-
※後程出てきますが、この方法も効率が良くなく、大きい数字になった時に計算量が多いため、ツール作成時には別の方法を採用しています
問題3：p×q=177773となる、pとqを求めよ
コード(問題3)
import math
# input
target_num = 177773
def calc_pq(n):
# 2~target_numの平方数までに必ず約数が1つある
num_limit = int(math.sqrt(n))
# target_numの平方数までの素数を計算→リスト
list_prime_num = calc_prime_num(num_limit)
# 素数リストから該当の約数を探す
for num in list_prime_num:
if n % num == 0:
p = num
break
q = n // p
return p, q
# エラトステネスのふるい
def calc_prime_num(input_num):
# 上限の平方数まで確認すればOK
loop_limit = input_num ** 0.5
# 上限数のTrueリストを生成、indexを数で管理する
list_sieve = [True] * (input_num + 1)
# 0、1は素数ではないためFalse
list_sieve[0] = False
list_sieve[1] = False
# 2~上限の平方数までを確認
target_num = 2
while target_num < loop_limit:
# 素数(=True)の場合 → 倍数をFalseに
if list_sieve[target_num]:
for num in range(target_num*target_num, len(list_sieve), target_num):
list_sieve[num] = False
target_num = target_num + 1
# Trueで残った数のみリストで出力
list_prime_num = [index for index, flag in enumerate(list_sieve) if flag == True]
return list_prime_num
if __name__ == "__main__":
p, q = calc_pq(target_num)
print("p=", p)
print("q=", q)実行結果
p= 389
q= 457コード(問題3)の解説
- 177773の平方数を計算
- 約数は必ずその数の平方数までに存在する
- 今回は$\sqrt{177773} = 421.631 \cdots$までに約数がある
- 計算した値までの素数を計算→リストに格納
- 素数計算にはエラトステネスのふるいを使用
- 素数計算の解説は下記にて解説しているので、良ければご覧ください
- 【Python】素数計算プログラム
- 素数リストから177773の約数を探す
- リストを順番に確認、割り切れたら約数
- 今回は2つの素数の積と分かっているため、一つ見つけたらその数で割って確定
エンコード・デコードツール
- 応用として、RSAの仕組みを使ってエンコード(文字を数字に変換)・デコード(数字を文字に変換)するツールを作ってみました
コード
エンコードツール
import math
import random
import func
# input
message = "test"
def str_to_num(message):
# アルファベット(大文字・小文字)・記号のリストを定義
strings_list = func.make_str_list()
# 1文字ずつ数字(2桁)に変換
message_num_list = []
for ch in message:
char_num = str(strings_list.index(ch)).zfill(2)
message_num_list.append(char_num)
message_num = "".join(message_num_list)
return message_num
def calc_pqe(M):
# Mを暗号化できる素数p, qを計算する
M_sqrt = math.sqrt(int(M))
# Mの桁数までの素数を計算
loop_limit = 1 * pow(10, len(str(int(M_sqrt))))
list_prime_num = func.calc_prime_num(loop_limit)
# Mの平方数~計算した上限までの素数リストからランダムに2つ取り出す->p, q
candidate_pq = [num for num in list_prime_num if num > M_sqrt]
p, q = random.sample(candidate_pq, 2)
# nを計算
n = p * q
# (p-1)(q-1)と互いに素となるeを計算
e = (p-1)*(q-1)-1
return p, q, n, e
def calc_C(M, n, e):
C = pow(int(M), e, n)
return C
if __name__ == "__main__":
# inputの文字を数字に変換
M = str_to_num(message)
# Mを暗号化できる各値を計算
p, q, n, e = calc_pqe(M)
# 暗号文Cを計算
C = calc_C(M, n, e)
# C, e, n(素数p、qの積)を渡す
print("n =", n)
print("e =", e)
print("C =", C)実行結果
n = 32859391
e = 32847911
C = 16854072デコードツール
import math
import func
# input
n = 32859391
e = 32847911
C = 16854072
# nからp, qを計算
def calc_pq(n):
num_limit = int(math.sqrt(n))
list_prime_num = func.calc_prime_num(num_limit)
for num in list_prime_num:
if n % num == 0:
p = num
break
q = n // p
return p, q
# Mを計算
def calc_M(p, q, n, e, C):
if n != p * q:
print("error")
return None
# mを計算(dの計算に必要)
phi_n = (p-1)*(q-1)
inverse_phi = pow(phi_n, -1, e)
m = ((e-1)*inverse_phi) % e
# dを計算
d = (m*(p-1)*(q-1) + 1) // e
# d, C, nからMを計算
M = pow(C, d, n)
return M
# Mから元のメッセージを復元
def num_to_str(M):
M = str(M)
# アルファベット・記号のリストを定義
strings_list = func.make_str_list()
# 桁数が奇数の時、頭に0を付けて偶数にする
if len(M) % 2 != 0:
M = M.zfill(len(M)+1)
# 2桁ずつ切り出して文字に変換->リスト
message_list = []
for char_num in range(0, len(M), 2):
char_slice = M[char_num:char_num+2]
char = strings_list[int(char_slice)]
message_list.append(char)
# リストを結合してメッセージに
message = "".join(message_list)
return message
if __name__ == "__main__":
# nからp, qを計算
p, q = calc_pq(n)
# Mを計算
M = calc_M(p, q, n, e, C)
# Mから元のメッセージを復元
message = num_to_str(M)
print("message = ", message)実行結果
message = testエンコード・デコード共通関数
def make_str_list():
strings_list = [
" ",
"a", "b", "c", "d", "e", "f", "g",
"h", "i", "j", "k", "l", "m", "n",
"o", "p", "q", "r", "s", "t", "u",
"v", "w", "x", "y", "z",
"A", "B", "C", "D", "E", "F", "G",
"H", "I", "J", "K", "L", "M", "N",
"O", "P", "Q", "R", "S", "T", "U",
"V", "W", "X", "Y", "Z",
"-", "'", "!", "?", "."
]
return strings_list
def calc_prime_num(input_num):
# 上限の平方数まで確認すればOK
loop_limit = input_num ** 0.5
# 上限数のTrueリストを生成、indexを数で管理する
list_sieve = [True] * (input_num + 1)
# 0、1は素数ではないためFalse
list_sieve[0] = False
list_sieve[1] = False
# 2~上限の平方数までを確認
target_num = 2
while target_num < loop_limit:
# 素数(=True)の場合 → 倍数をFalseに
if list_sieve[target_num]:
for num in range(target_num*target_num, len(list_sieve), target_num):
list_sieve[num] = False
target_num = target_num + 1
# Trueで残った数のみリストで出力
list_prime_num = [index for index, flag in enumerate(list_sieve) if flag == True]
return list_prime_numコード(エンコード・デコード)解説
エンコード
- 文字を数字Mに変換
- 文字のリストを定義
- 1文字ずつ2桁の数字に変換→リストに
- リストを結合して一つの数字に
- ※今回は半角スペース,
A~Z,a~z,-'!?,.をインデックス番号に対応させた(文字コードを使用するのが一般的) - ※通常は文字を分割して暗号化します
- Mを暗号化できる素数p, qを計算
- Mを暗号化するためにはp×qがMより大きい必要がある
- Mの平方数以上の素数を求め、そこからランダムに2つ取り出す→p, q
- エラトステネスのふるいを使用
- eを計算
- (p-1)(q-1)(オイラー関数)と互いに素な自然数eを計算
- 今回は(p-1)(q-1)-1とした
- 暗号文Cを計算
- $C \equiv M^e \pmod n$
デコード
- 流れはQuizKnockの問題とおおよそ同じになる
- 問題3の流れで、nを素数p, qに分解
- 問題2の流れでp, q, CからMを計算
- $M \equiv C^d \pmod n$
- M計算途中のmの計算のみ、QuizKnockの問題のコードから変更した(後述)
- 文字に変換する
mの計算の効率化
- dの計算に使用するmの計算
- $m(p-1)(q-1) \equiv e-1 \pmod e$を満たす最小の自然数m
- 問題2のコードで採用した方法だと、以下のようなコードになる
phi = (p-1)(q-1)
num_x = 1
while True:
target_num = e * num_x - 1
if target_num % phi == 0:
m = target_num // phi
break
num_x = num_x + 1
- 上記方法は求めたいものは計算できるが、値が大きい時の計算量が大きくなり、結果が返ってこなくなった
- そのため、直接mを求める方法を採用した
- ※求めたいものはこの方法で計算できていますが、以下の説明が正しいかちょっと自信が無いです(^_^;)
$m(p-1)(q-1) \equiv e-1 \pmod e$を変形すると、
$m \equiv (e-1){{(p-1)(q-1)}}^{-1} \pmod e$ となる
-
${{(p-1)(q-1)}}^{-1}$は${(p-1)(q-1)}$の逆元
- 等式の逆数を合同式に拡張したイメージのものです
- そのため、通常の逆数$\frac{1}{(p-1)(q-1)}$とは異なります
-
ここから${{(p-1)(q-1)}}^{-1}$を計算すればmは
powで計算できる- ${{(p-1)(q-1)}}^{-1}$の計算も
powで計算可能 pow(a, -1, c)→ $ax \equiv 1 \pmod c$のxを計算する
- ${{(p-1)(q-1)}}^{-1}$の計算も
終わりに
- 1月に投稿したRSA暗号：復号化の仕組みからRSA暗号の仕組みについて、いろいろと勉強しました
- 軽い興味から始めたものだったのですが、最終的に関連記事を総合すると、25000字を超える大ボリュームとなりました(^_^;)
- 計算量を気にしないと上手く処理できない箇所があったり、少しの工夫で処理がグッと早くなる箇所があったりと、とても勉強になりました
参考
- サマーウォーズの暗号、ガチで解けるかやってみた【RSA暗号】
- RSA暗号の解説(あなたのためのプログラミング)
RSA暗号 | あなたのためのプログラミング公開鍵暗号とはkf74.utcode.net - RSA暗号の解説(中部大学)
RSA暗号edu.isc.chubu.ac.jp - RSA暗号の解説(東京工芸大学)
http://www.cs.t-kougei.ac.jp/nsim/study/RSAT/RSA1.pdf
関連リンク
- RSA暗号：復号化の仕組み
- 【Python】素数計算プログラム
コメント