RSAを手計算する課題とてもかったるかったので実装した。[python]
このブログは提出したものの改良版です。個人情報や講義に支障がない範囲での公開としていますので至らない部分もあるかもしれないです。軽量版でお送りします。
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
問題文
RSA暗号の数値例を作成しなさい。
２つの素数は、いずれも10進数2桁とする。なお、10進数2桁の素数には、11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 がある。
これらから自由に選択しなさい。選んだ素数に対して、暗号化と復号化に必要なパラメータの導出過程を示しなさい。平文M=127を暗号化する過程を示しなさい。
上記で得られた暗号文を復号する過程を示し、元の平文が得られることを確認しなさい。計算には、電卓やPCを利用すればよいが、計算の過程が分かるように、適宜、途中の計算結果を示すこと。なお、PCを利用する場合、通常の整数演算を利用し、多倍長整数演算は使わないこと。
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
解答
とてもとても手計算などではやってられないと感じましたので一般化する意味も込めて当該内容のスクリプトを記述しました。pythonで書きました。プログラムで書くとレポートは数学の手計算をする手間がゼロになってコードの解説を添えることで完成になるという斬新な感じに仕上がりました。
import math
from math import gcd
""" ここでは引数に与えた最小公倍数を求める """
def lcm(p,q):
return (p * q) // gcd(p, q)
def generate_keys(p, q):
N = p * q
P = lcm(p-1, q-1)
for i in range(2, P):
if gcd(i, P) == 1:
E = i
break
for i in range(2, P):
if (E * i) % P == 1:
D = i
break
""" 公開鍵=public_keyを使って平文=plain_textを暗号化する """
def encrypt(plain_text, public_key):
E, N = public_key
plain_integers = [ord(char) for char in plain_text]
encrypted_integers = [pow(i, E, N) for i in plain_integers]
encrypted_text = ''.join(chr(i) for i in encrypted_integers)
return encrypted_text
""" 秘密鍵=private_keyを使って暗号文=encrypted_textを復号する """
def decrypt (encrypted_text, private_key):
D, N = private_key
encrypted_integers = [ord(char) for char in encrypted_text]
decrypted_intergers = [pow(i, D, N) for i in encrypted_integers]
decrypted_text = ''.join(chr(i) for i in decrypted_intergers)
return decrypted_text
def unitetext(encrypted_text):
""" ここから下がmain関数 """
if __name__ == '__main__':
public_key, private_key = generate_keys(17, 29)
plain_text = '127'
encrypted_text = encrypt(plain_text, public_key)
decrypted_text = decrypt(encrypted_text, private_key)
print(f"""
公開鍵: {private_key}
平文:【{plain_text}】
暗号文:【{unitetext(encrypted_text)}】
復号後の平文:【{decrypted_text}】
"""[1:-1])
計算をするのでmathモジュールをインポートしてきました。gcdに関してはmathの中に提供されていたのですがlcmに関しては見つからなかったので自ら関数定義してやって作りました。p*q=gcd(p,q)*lcm(p,q)が自明に成り立つことから式変形したやったものを条件式に入れてやることでできますね。整数をリターンしてやるだけできわめて簡単に実装できました。//は切り捨て剰余演算子で除算結果にmath.floor(x)つまり x 以下の最大の整数（Integral値）を返します。
次のブロックでは2つの素数から公開鍵と秘密鍵を生成する関数を示しています。レジュメのアルゴリズムを素直に実装しています。返り値は公開鍵と秘密鍵のタプル型で、それぞれの鍵は 2 つの整数のタプル型で表現しました。
encrypt
公開鍵を用いて平文を暗号化しています。文字列plain_textを整数値であるE,Nを使って計算したいので文字列をリスト変換してやります。その部分がord(char)の部分です。1 文字の Unicode 文字を表す文字列に対し、その文字の Unicode コードポイントを表す整数を返します。pow(base,exp,mod)では base の exp 乗に対する mod の剰余を返します。 powはそういう組み込み関数です。これは暗号化に際しては必ず必要な部分です。plain_text＾E mod N の適用を意味しています。最後にchr()関数でUnicodeのコードポイントが整数である文字を表す文字列を返してやります。変換したものを連結して文字列生成をしています。
decrypt
秘密鍵を使って暗号文を復号して平文に戻しています。基本的には暗号化したときと同じ作用を与えてやるだけです。
ここからはおまけです。すべての場合において暗号化したものの文字がどのような形式になるのかの予測がつかないことからprint()での予期せぬエラーの回避を目的にunitetextという関数を作っています。つまり”書式の強制的な統合化”を意味しています。
今回、問題文の中に与えられていた2つの素数は17と29を選びましたのでmainのgenerate_keys(p,q)のp,qにその二つを与えてやりました。plain_textすなわち問題文の平文M=127を設置しました。暗号文は平文を公開鍵で暗号化してやったものです。復号文は暗号文を秘密鍵で復号化してやったものです。最後はそれぞれ関数定義してやったものを一気にprintf引き出してやりました。
できていることが確認されました。平文を暗号化して復号することもきちんとできいます。 授業に参加している皆さんは自分が選んだ数値の部分を変えて遊んでみると提出した課題があっているのかどうかの確認ができます。なので遊んでみると楽しいかもしれないです。
注、このブログでの回答は最終版ではなく簡易版なので今後追加していく可能性があります。
*1:E, N),(D, N
