じゃあぼくも雑にRSA暗号実装してみた
つくったやつ
画像にある pubが公開鍵です。公開するときに使います。
画像にあるsecは秘密鍵です。ふつうは公開しないけど、この記事では説明用に公開しています。
しくみの概要
RSA暗号は、素因数分解がとてもむずかしいこと（人類が解くにはとても時間がかかるという意味）を利用して、
「なに人類？ 数が素因数の分解をさせてくれない？ 人類、それは無理矢理引き離そうとするからだよ。逆にかんがえるんだ。『暗号につかっちゃってもいいさ』と考えるんだ」
というやつです。TRIZの13番目のルール 'The Other Way Round' （逆にせよ）みたいなノリです。
ざっくりとしたしくみ
まず文字列は数値に変換できます。たとえば文字コードを使えば変換できます。逆もそうで数値も文字列に変換できます。
たとえば、ASCIIコードで a は 0x61です。つまり0x61という16進数で扱うことができます。なので、これ以降は文字列を数値と考えることにします。数値にすると全部数値として扱えて計算しやすいからです。
ここで、平文をP（文字列を数値にかえたやつ）、暗号化済みのやつをC（これも数値になっている）、暗号化に使う公開鍵その1（数値）をe、暗号化に使う公開鍵その2（数値）をM、復号に使う秘密鍵（数値）をdというふうに考えます。Mは、暗号化でも復号でもどちらでも使います。そして次のような式を使います。
encrypt（暗号化）
decrypt（復号）
PとかCとかeとかdとかMはなんかそういう慣習があるみたいです。何の略語かは知らないですが、ぼくの頭の中では password / encrypt / decrypt / committed / modularみたいな印象です。たぶん正しくないので知っている人いたら教えてほしいです。
Mが、素数と素数をかけあわせて作った数です。たとえば5183みたいな感じです（この5183自体は71と73をかけた素数です）。ただし、実際はもっとはちゃめちゃに大きな数を使います。素因数分解はすごくむずかしくて（スパコンで数万年とかギャグみたいな時間かかってしまう）、もともと何と何をかけるのかあらかじめ知っていないと簡単には素因数分解できないということが証明されているみたいです。すごい！
「この
ちなみにmodは合同式です。
eとMは公開鍵ということでみんなに公開します。dだけ自分で持っておきます。
dはどういうやつかというと、↓の式（encryptとdecryptを合わせたやつ）のようになるような値です。
簡単そうな式なので、eとMがわかっていれば、なんだかいつかPが求めれそうな気がしますけど、「それが全然できそうで全然できない！」というのがミソのようです。
ところで、暗号を作りたい人はM（素数と素数をかけたやつ）のもとになるやつがわかっているので、先にd（秘密鍵）を求めてしまいます。
秘密鍵の作り方ですが、素人のぼくが適当に言ってもかえって混乱をきたすと思います。詳しくは調べてもらうのがいちばんいいと思います。
具体的には「オイラーの定理 → 一時不定方程式の整数解を求める → 拡張ユークリッドの互除法を使う」の3コンボで求まるみたいです。な、なんだ……か……かんたんだな！！競プロをやっていなかったら即死だった…
まあなんやかんやで、秘密鍵が求まります。
実装
暗号鍵と秘密鍵の生成メソッドの実装
じゃあ実装していきます。Mは、素数2つを掛け算して求めます。
e（暗号鍵その1）は、 φ(M)と互いに素であるような数にします。急にφとか言い出して意味わからないと思いますが、たぶんここまで読んでいる人は気になりすぎて勝手にオイラーの定理とかフェルマーの小定理とか調べていて、すでに知っていて証明もしていると思うので説明を雑にしていきます。互いに素も知っているはずです。
eの互いに素のやつってどうやって求めるのかよくわからんし、適当に65537(素数)を置いています。
↓適当に置いていい理由はここで説明されてました。
（※ 本当にぼくはいろいろと適当なので真似しないでください）
あとはその eを使って、拡張ユークリッド互除法をしかけます。拡張ユークリッド互除法の気持ちは、「いったん海の底まで潜ったあと、『ここに宝あったわ〜〜』『えぇ！？そこにあったの〜！？』っていうのを伝言ゲームみたいなノリで繰り返すイメージ」です。まあ再帰です。
そういうわけでd(秘密鍵）ができます。
eとdとMが求まって嬉しいです。
暗号化メソッドと復号メソッドの実装
こんな感じです。public_keyとかには、{eの値}_{Mの値}または{dの値}_{Mの値}が来ます。
この関数では nって書いてありますが、Mのことです。ややこしくてすみません。
何乗とかをしているだけになっています。
def encrypt(mes, public_key):
e, n = map(int, public_key.split('_'))
return (mes ** e) % n
def decrypt(mes, secret_key):
d, n = map(int, secret_key.split('_'))
return (mes ** d) % n
数値を文字に変えたり、文字を数値に変える
これはなんでもいいんですが、今回の実装ではASCII限定にしてみました。
くわしくはこの下にソースをはったのでそれを見てほしいです。
Caveat!
たぶん2文字しか暗号化できません。あとめっちゃ重いです。実用的に使えるようにするのは大変そうです。実用化してくれた天才たちのおかげで今の世の中が成り立っているんだなというのを実感しました。
今はRSA暗号の進化系である楕円曲線暗号を使っているらしいです。かっこいいですね。名前がかっこいい。
ちなみにこの記事だけではRSA暗号はよくわからないと思います。
バグってたらすいません。テストはあまりしてないです。
ソース
python3で動きます。
import sys
def generate_key(p, q):
n = p * q
phi = (p - 1) * (q - 1)
def extgcd(a, b):
if b == 0:
return a, 1, 0
d, y, x = extgcd(b, a % b)
y -= (a // b) * x
return d, x, y
def create_secret_key(pub, phi):
d, x, y = extgcd(phi, pub)
y = y % phi
return y
e = 65537
return str(e) + '_' + str(n), str(create_secret_key(e, phi)) + '_' + str(n)
def encrypt(mes, public_key):
e, n = map(int, public_key.split('_'))
return (mes ** e) % n
def decrypt(mes, secret_key):
d, n = map(int, secret_key.split('_'))
return (mes ** d) % n
if __name__ == '__main__':
if sys.argv[1] == 'generate':
p = int(sys.argv[2])
q = int(sys.argv[3])
keys = generate_key(p, q)
print('---------pub---------')
print(keys[0])
print('---------sec---------')
print(keys[1])
elif sys.argv[1] == 'encrypt':
pub = sys.argv[2]
mes = sys.argv[3]
fom = ''.join(['{0:>02s}'.format(hex(ord(x)).replace('0x', '')) for x in mes])
fom = int('0x' + fom, 16)
print(hex(encrypt(fom, pub)))
elif sys.argv[1] == 'decrypt':
sec = sys.argv[2]
mes = int(sys.argv[3], 16)
fom = decrypt(mes, sec)
fom = hex(fom).replace('0x', '')
fom = '0' + fom if len(fom) % 2 != 0 else fom
dec = ''
for i in range(0, len(fom), 2):
dec += chr(int('0x' + str(fom[i]) + str(fom[i+1]), 16))
print(dec)
else:
raise Exception
リファレンス
Discussion