Photo by Jacqui Brown
秋山です。Pythonエンジニアです。
みなさんは公開鍵暗号という暗号方式を知っていますか？
エンジニアの方なら知っているかと思いますが、プログラミングを始めたばかりの初心者の方だと、「聞いたことある気がするけど…何？」という感じかと思います。
そこで今回は、Pythonを使って実際に公開鍵暗号を実装してみる方法について書きたいと思います。
公開鍵・秘密鍵について
公開鍵暗号方式は、暗号化、また復号するときの「鍵」に、一対となっている公開鍵と秘密鍵を使います。公開鍵と秘密鍵を生成するのは、秘密鍵を持っている人です。
たとえば、霧島京子さんが公開鍵と秘密鍵を作りました。公開鍵はその名の通り公開してOKなものなので、公開します。
↓霧島京子さん
Picture by ITエンジニアを目指す女子高生たちの学園ライフ4コマ漫画『ぱいじょ！』
緑川つばめさんは、霧島さんが公開した公開鍵を使って、秘密のメッセージを暗号化して、霧島さんに送りました。
↓緑川つばめさん
Picture by ITエンジニアを目指す女子高生たちの学園ライフ4コマ漫画『ぱいじょ！』
この秘密のメッセージを復号して解読するには、秘密鍵が必要です。緑川さんが送ったメッセージは、秘密鍵を持っている霧島さんにしか解読できないので、秘密のやりとりができる…というわけです。
また、霧島さんが「このPCは2019年1月1日に霧島が買ったもの」というメッセージを秘密鍵で暗号化して、PC内に記入しました。そこに六村リオさんが現れて「いや、このPCは私のものです」と言ってきたとします。このPCが霧島さんのものであると証明するにはどうすればよいでしょうか。
↓霧島京子さんと六村リオさん
Picture by ITエンジニアを目指す女子高生たちの学園ライフ4コマ漫画『ぱいじょ！』
霧島さんが秘密鍵で暗号化したメッセージを、今度は霧島さんの公開鍵で復号すると「このパソコンは2019年1月1日に霧島が買ったもの」というメッセージを出現させることができます。霧島さんが公開している公開鍵で復号できるメッセージは、対応する秘密鍵を持っている霧島さんにしか作れないので、霧島さんが書き込んだものであるという証拠になります。
…っていうのが公開鍵と秘密鍵のざっくりしたイメージです。実際に、Pythonを使って実装していってみましょう。
暗号化に使う数字の話
※今回は、典型的な公開鍵暗号方式であるRSA暗号方式（RSA暗号）を使います。（公開鍵の暗号方式にもいろいろ種類があるのですが、RSA暗号方式はとりあえずメジャーな暗号方式です）
コーディングの前に、暗号化に使う数字について説明します。
- 大きな素数 p, q
- N = (p - 1 と q - 1 の最小公倍数)
- 公開鍵 public は、 2 から N の整数の範囲内で、 N の最大公約数 が 1 となる数字
- 秘密鍵 secret は、 2 から N の整数の範囲内で、 public とかけて N で 割った余りが 1 となる数字
RSA暗号では、これらの数字を使って暗号化と復号をおこないます。
pとqそれぞれは非公開ですが、p * q は公開鍵 として暗号化と復号に利用されます。
実際に公開鍵 を使って暗号化するときは
- 暗号化したい数値を public 乗し p * q で割った余り
暗号化されたものを復号するときは
- 暗号化された数値を private 乗し p * q で割った余り
という計算をします。
このとき気をつけたいのが、 p * q で割った余りが暗号文・復号文の数値より大きくなるのはNGということです。割った余りを使っているので当然ですが…。
pとqが十分に大きければ特に問題ないですが、テストのときなどに小さい数で試すときは注意してください。
Pythonを使って公開鍵 を実装してみる
実際にコードを書いて実装してみましょう。
まず、最小公倍数を求める lcm 関数と最大公約数を求める gcd 関数を作り、 p = 13、 q = 41 としたときの鍵の生成をしてみましょう。
これで pと q、そして最小公倍数を求める関数を使って N の値が決まりました。
続けて、公開鍵 public と、最大公約数を求める関数を使って秘密鍵 secret も作ってみましょう。
これで、公開鍵(public と p * q)、秘密鍵(privateとp * q)のセットが完成しました。
このとき、公開鍵はあくまで public と p*q で、pとqそれぞれの値はわからないというのがRSA暗号のポイントになります。
533は、13と41の素数に素因数分解できますが、手計算だとなかなか大変な作業ですね。（コンピューターなら全探索が一瞬で終わりますが）実際に使われる素数はもっと巨大になるので、探索するのも困難です。
次に、暗号化と復号もしてみましょう。
このようにすれば、 "paiza" という秘密のメッセージを、秘密鍵 を持つ人のみにこっそり伝えることができます。
署名の部分は、逆に「 paiza 2019 / 6 / 21」といったメッセージを暗号化し、元の文章とセットで公開鍵を知っている人たちに配ります。公開鍵を知っている人たちは、そのメッセージを公開鍵を使って暗号文から平文に復号できます。暗号文を作れるのは、秘密鍵を持っている人だけ（漏えいしていなければですが）なので、誰が作ったメッセージなのかわかりますね。
このように、public と privateを入れ替えるだけで、公開鍵と秘密鍵を逆にした暗号化と復号ができます。
暗号の脆弱性について
暗号が意図せず解読されてしまう場合もあります。大きな数の素因数分解も高速でできちゃうコンピュータを使われたら、533なんてすぐに13と41に素因数分解できてしまいます。
前述の通り
- 秘密鍵 secret は、 2 から N の整数の範囲内で、 public とかけて N で 割った余りが 1 となる数字
ですから、Nは p-1, q-1の最小公倍数なので、 N はわかっちゃいますね。12と40の最小公倍数は120です。
publicは 7 なので
(2 * 7) % 120 (3 * 7) % 120 ... (103 * 7) % 120 == 1 ←103が秘密鍵 private ！
といった具合で判明してしまいます。
このようなセキュリティにおける攻撃手段についてはいろいろありまして、"paiza" みたいな小さな平文の場合なんかは容易に暗号文から平文に解読されてしまいます。そのため、実際に実装されるときは、関係のない数値などを混ぜて平文を長くするなどといった措置がとられたりしています。
まとめ
こんな感じで、Pythonを使って公開鍵と秘密鍵を作ってみることができます。
プログラミングに入門はしているけど、暗号化とかセキュリティとかについては勉強してないな〜って人や、暗号化に興味がある人はぜひやってみてください。
これまでにもPythonに関する記事や機械学習に関する記事をいろいろ書いているので、気になった人はぜひ見てみてください。
paiza.hatenablog.com
paiza.hatenablog.com
「公開鍵どころかプログラミング初心者なので、まずはPythonの書き方を学びたい！」という方は、プログラミングが動画で学べる「paizaラーニング」の「Python入門編」（全編無料）から始めてみてください。
途中で出てきた画像の漫画はこちら
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
