こんにちは，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) = (1) – (2) * 2
…(4) = (2) – (3)
…(5) = (3) – (4) * 2
を計算して， が得られる．
|
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)
を解くことを考える．ただし， と
は互いに素であるため，右辺は
となっている．
上式において，モジュロ を取ると，
となるが，これは
と整理できる．よって，(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 です．お楽しみに．