こんにちは，yaitaimo です．
この記事は CAMPHOR- Advent Calendar 2015 の3日目の記事です.
RSA 公開鍵暗号は，一度触れて見たがよくわからなかった，という人も居るのでは無いでしょうか．今回はそんな皆さんのために，数学的に一番簡単な筋をたどって，一連の流れを説明したいと思います．
納得感を持って読み終わっていただけたら幸いです．
Python 3 を使います．
1. RSA 公開鍵暗号とは
公開鍵暗号は，暗号化と復号に同じ鍵を用いる共通鍵暗号と違い，世界に公開する公開鍵と自分しか知らない秘密鍵の2つの鍵を用いる．
この2つの鍵は，
- 公開鍵で暗号化したものは，秘密鍵でしか復号できない
- 秘密鍵で暗号化したものは，公開鍵でしか復号できない
という性質を持っている．
これをうまく利用することで，秘密情報の伝達や認証を行うことが出来る．
今回はこの内の秘密情報の伝達を取り上げて実装を行う．
秘密情報の伝達
- BさんがAさんにある機密データを受け取りたい場合は，Aさんの公開鍵を使ってそのデータを暗号化してからAさんに送る．
- Aさんは秘密鍵を使ってそれを復号し，データを手に入れる．
RSA暗号は上記の公開鍵を具体的に実現したもので，桁数が大きい合成数の素因数分解が困難であることを安全性の根拠としたものである．
2. 必要な数学の知識と実装
最大公約数（ユークリッドの互除法）
「2つの正の整数に共通な約数のうち最大のもの」
例えば 
を計算して，
|
1 2 3 4 |
def gcd(a, b): while b: a, b = b, a % b return a |
最小公倍数
「2つの正の整数の共通な倍数のうち最小のもの」
例えば 
を計算して，
|
1 2 |
def lcm(x, y): return x * y // gcd(x, y) |
拡張ユークリッドの互除法
「
を計算して，
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
def ex_euclid(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return c0, a0, b0 |
モジュロ演算
また，
3. RSA暗号の実装
3.1 ユーザの鍵生成
- 2素数
を定め，
を計算する．
に対して，
と互いに素で
を生成し，
を満たす
を求める．
を定め， 
を計算する．
に対して， 
を満たす 以上より，公開鍵 
例：
ここで，拡張ユークリッドの互除法を利用して，
を解くことを考える．ただし，
上式において，モジュロ
となるが，これは
と整理できる．よって，(b)を解くことで，
ただし，拡張ユークリッドの互除法では負数が出力されることもあるため，
このようにして，
|
1 2 3 4 5 6 |
p, q = 7, 11 n = p * q e = 13 λ = lcm(p-1, q-1) c, a, b = ex_euclid(e, λ) d = a % λ |
3.2 暗号化
平文 
例：
|
1 2 |
m = 15 c = pow(m, e, n) |
3.3 復号
暗号文 
例：
|
1 |
m1 = pow(c, d, n) |
4. おわりに
さくっと書いてきましたが，内容については理解してもらえたでしょうか．
興味が出てきた人は，RSAについて調べてみてください．
高速化・効率化するさまざまな手法があるので興味深いです．
明日は ryota-ka です．お楽しみに．
初めまして、情報処理の勉強をしている者です。
ＲＳＡの解説、とても興味深くかったです！
これからも色々と学ばせて下さい！
よろしくお願いいたします。
師子乃さん
yaitaimo です．コメントは励みになるので，とてもありがたいです！
こちらこそ，どうぞよろしくお願いいたします．
ピンバック: PythonでRSA暗号 | IT技術情報局