目的
RSA暗号の細かい理論などは全部すっ飛ばして、とりあえず何となくの動きだけ理解しようといった記事になります。
RSA暗号の原理
RSA暗号では二つの大きな素数$p, q$に加え$(p-1)(q-1)$と互いに素な正整数$e$を用いる。
暗号化
まず初めに、暗号化を行うための鍵(公開鍵)を作成する。公開鍵は$n$と$e$の二つであり$n$は以下のように求められる。
n = pq
次に、公開鍵$e$, $n$を用いて暗号化を行う。$n$より小さい正の整数$M$を送ることを考えると、暗号化された文$M'$は以下のように表される。
M' ≡ M^e (mod n)
つまり、$M^e$を$n$で割った余りが$M'$となる。これで、RSA暗号を用いて文章を暗号化することができた。
復号
次に復号を行っていく。まず初めに、復号を行うための鍵(秘密鍵)を作成する。秘密鍵は以下のように表される。
ed≡1 (mod (p-1)(q-1)) を満たす正の整数
つまり、$(p-1)(q-1)$で$e×d$を割ったときに余りが1になるような$d$が秘密鍵となる。
この秘密鍵を用いて暗号化された文$M'$を復号すると以下のようになる。
M ≡ (M')^e (mod n)
これで、暗号文をもとの文に復号することができた。
RSA暗号では、暗号化する際には$n$を使用し、復号する際には$(p-1)(q-1)$を用いる。$(p-1)(q-1)$を求めるためには$n$を素因数分解する必要があり、この素因数分解が現実的な時間内で行うには困難であり、これを安全性の根拠としている。
実装
まず初めに、暗号で用いる素数$p, q, e$を定める。今回は$p=2^{521}-1$, $q=2^{607}-1$, $e=65537$とする。これらを用いて、公開鍵と秘密鍵を求める。
公開鍵
e
n = pq
秘密鍵
ed≡1 (mod (p-1)(q-1)) を満たす正の整数
p = 2**521-1
q = 2**607-1
e = 65537 #公開鍵1
n = p*q #公開鍵2
X = 1
phi_n = (p-1)*(q-1)
while ((phi_n*X + 1)%e != 0):
X += 1
d = ((phi_n*X + 1)//e) #秘密鍵
$d$の計算について、$(p-1)(q-1)$で$ed$を割ったときに余りが1になるような$d$とは$\frac{ed}{(p-1)(q-1)} = X あまり1$ と置き換えることができる。(Xは正整数)
これを整理すると、以下のように表される。
ed = X(p-1)(q-1) + 1
d = \frac{X(p-1)(q-1) + 1}{e}
次に、暗号化の部分を実装していく
M' ≡ M^e (mod n)
cleartext = 'この文を暗号化するよ！'
M = int(cleartext.encode('utf-8').hex(), 16) #文字列を数字に変換
M_dash = pow(M, e, n) #暗号化処理
print(f"M' = {M_dash}")
M' = 2892841978445552746552837068720977153947099046131513535902823000007771738034045526718176991547726996682473804152587900965801173342085402689879720830643090816942047842310966699951841816001310762118138504126990135972666327576985699629144337598585098611928957102657956612360733923445833594736631303539301347543121853275516833807034728752160735
こんな感じで、しっかりと文章が暗号化されている。
次に、復号の実装を行う
M ≡ (M')^e (mod n)
M = pow(M_dash, d, n) #復号
#数字から文字列に変換
hexM = hex(M)[2:]
decM = [int(hexM[i:i+2], 16) for i in range(0, len(hexM), 2)]
sentence = bytes(decM).decode('utf-8')
print(sentence)
M' = 2892841978445552746552837068720977153947099046131513535902823000007771738034045526718176991547726996682473804152587900965801173342085402689879720830643090816942047842310966699951841816001310762118138504126990135972666327576985699629144337598585098611928957102657956612360733923445833594736631303539301347543121853275516833807034728752160735
この文を暗号化するよ！
元の文章に復号することができた。
ソースコード
p = 2**521-1
q = 2**607-1
e = 65537 #公開鍵1
n = p*q #公開鍵2
X = 1
phi_n = (p-1)*(q-1)
while ((phi_n*X + 1)%e != 0):
X += 1
d = ((phi_n*X + 1)//e) #秘密鍵
cleartext = 'この文を暗号化するよ！'
M = int(cleartext.encode('utf-8').hex(), 16) #文字列を数字に変換
M_dash = pow(M, e, n) #暗号化処理
print(f"M' = {M_dash}")
M = pow(M_dash, d, n) #復号
#数字から文字列に変換
hexM = hex(M)[2:]
decM = [int(hexM[i:i+2], 16) for i in range(0, len(hexM), 2)]
sentence = bytes(decM).decode('utf-8')
print(sentence)
まとめ
RSA暗号の詳しい証明部分についてはすべて割愛しましたが、「なんとなくこんなことをしてるんだな～」といった雰囲気をつかんでいただけたら幸いです。
参考文献
この記事は以下の情報を参考にして執筆しました。