RSA暗号方式をpythonで実装してみる
琉球大学工学科知能情報コースAdventCalender2018の8日目の記事です。 こんにちは、kagariです！ 私自身2回目の記事でAdvent Calendarに登録するなんて思ってもみませんでしたw 記事の内容を「RSA暗号方式をpythonで実装する」って決めた理由としては、最近授業で習ったからというだけの理由です。 何か至らない点があっても暖かい目で見守ってくださいm(__)m RSA暗号方式ってなに？ RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。(wikiより) うん、完全に理解した(多分) 要するに素数を使った暗号方式だね! 今回はこれをpythonで実装していく アルゴリズム 鍵の生成 まずは公開鍵の生成を行う。 2つの素数をp,qとし、n=p×qとm=(p-1)×(q-1) を求める。 さらに、nとmとが互いに素である数$e$を定める。 この(e,n)が公開鍵である。 次に、秘密鍵の生成を行う。 ed mod ((p-1)(q-1)) = 1となるようなdを見つける。 このdが秘密鍵である。 公開鍵と秘密鍵を生成したらp,qは用済みなのでしっかり破棄しましょう。 暗号化と複合 暗号化 平文(M)を暗号化すると、暗号文(C)は C=M^e mod nとなる。 これで暗号化を行う。 複合 複合は、暗号文(C)を以下のようにして平文(M)にすることができる。 M=C^d mod n これで複合を行う。 実際に実装していく 早速、どうやってpとqを生成すればいいかわからないという問題にぶつかった。 が、今回は全然セキュリティとかは考えていないので、手打ちにすることにする() 使用するライブラリはmathだけ! import math とりあえず、公開鍵と秘密鍵を生成する関数を作ってみる。 まずは公開鍵から def get_public_number(p, q): n = p*q # mと互いに素な数eを見つける m = (p-1)*(q-1) e = 2 while math.gcd(m, e) != 1: e += 1 return e, n 次に、秘密鍵を生成する関数を用意...