RSA暗号
『暗号技術のすべて』の第4章を参考にしました。 初めての具体的な公開鍵暗号であるRSA暗号について書いていきます。
RSA暗号とは
数学的基礎知識
- GCD(x,y)：xとyの最大公約数（GCD(x,y)=1のとき、xとyは互いに素である）
mod：モジュロ演算 → a=b mod m：aとbは法mで合同
法mとは、mで割った余りのこと。
（例）法7のもとでは、3と10は合同（3÷7=0...3，10÷7=1...3）
- フェルマーの小定理
- 中国人剰余定理
アルゴリズム
鍵生成、暗号化、復号の3つのアルゴリズムに分けられます。
鍵生成アルゴリズム
入力：k，出力：公開鍵pk，秘密鍵sk
- kビットの素数p, qをランダムで生成する。 ここで、p, ｑは十分大きな素数でなければならない（pqが簡単に素因数分解されない）。
- N = pqを計算し，φ(N) = (p - 1)(q - 1)とする。
- GCD(φ(N), e) = 1となるようなe（1 < e < φ(N)）をランダムに選ぶ。
- ed = 1 mod φ(N)を満たすようなd(> 0)を計算する。
- pk=(N, e)，sk=dとして出力する。
暗号化アルゴリズム
入力：平文m, pk、出力：暗号文c
c=me mod N
を計算し、出力する。
復号アルゴリズム
入力：暗号文c, pk, sk、出力：平文m
m=cd mod N
を計算し、出力する。
正当性の検証
ed = 1 mod φ(N)（鍵生成アルゴリズムステップ4）より、 ある整数k(≧ 0)に対してed = kφ(N) + 1となる。よって、m'は以下のように展開できる。
m' = cd = (me)d = med = mkφ(N)+1 = mkφ(N)・m
ここでmとNが互いに素かどうかで場合分けする。
(1) GCD(m,N) = 1のとき
オイラーの定理より、次のように変形できる。
m' = mkφ(N)・m = 1k・m = m mod N
(2) GCD(m,N) ≠ 1のとき
N = pqより、GCD(m, N) = p or qとなる。
(i) GCD(m,N) = pのとき
法Nではなく、法p, qで考え、出力をa, bとする。 mはpの倍数であるため、a = 0となる。 また、qは素数かつGCD(m,q)=1（互いに素）より、フェルマーの小定理を用いてb = mとなる。
a = m' = med = 0ed = 0 modｐ
b = m' = med = mk(p-1)(q-1)+1 = m・(mq-1)k(p-1) = m・1k(p-1) = m mod q
中国人剰余定理より、px+qy=1となるx, yを用いて、m'は以下のように計算できる。
m' = aqy + bpx mod pq
= 0・py + m・px mod N
= mpx mod N
= m(1 - py) mod N
= m - mpy mod N
= m mod N（mはpの倍数なので、mqはNの倍数）
(ii) GCD(m,N) = qのとき
(i)と同様に算出できる。
正当性の検証のまとめ
(1), (2)より、m'= m mod Nとなるので、正当性が成り立つ。
RSA暗号の安全性
RSA暗号は、「公開鍵がわかっても、秘密鍵を求めることが困難である」ことを安全性の根拠としています（公開情報から秘密の情報が漏洩したらダメですよね）。素因数分解は困難であるので、Nを知っていても効率的にp, qを求めることは出来ません。したがって、(p - 1)(q - 1)も効率的に求めることが出来ないので、秘密鍵dも効率的に求めることが出来ません。
RSA問題、RSA仮定とは
素因数分解問題とRSA問題
[問題]
素因数分解問題が解けると、RSA問題が効率的に解けてしまうことを証明せよ。
[証明]
整数Nを素因数分解するアルゴリズムAが存在したと仮定します。 つまり、アルゴリズムAとは、入力がNに対して、出力がp, qとなるブラックボックスのアルゴリズムです。
このAを用いて、RSA問題を解くアルゴリズムBを構成できれば、問題の関係性を証明できたことになります。アルゴリズムBは、入力p, qから鍵生成アルゴリズムと同様にdを計算できます。dが計算できたので、cd mod Nより、mを求めることが出来ました。
よって、素因数分解問題が解ければ、RSA問題が解けることがわかりました。一方、RSA問題が解けても、素因数分解問題が解けるかはわかっていないので，RSA仮定は、「素因数分解問題が困難」という仮定よりも強いことになります。
[結論]
感想
参考文献にはこのような記述があります。
実は、「素因数分解が難しい」ならば「ＲＳＡ暗号の解読も難しい」という関係には完全な証明がされているわけではありません。真正面からＲＳＡ暗号を解読しようとすれば素因数分解を行う必要があり、それが「素因数分解が難しければＲＳＡ暗号の解読も難しいだろう」という根拠になっているだけなのです。つまり、現在のところ素因数分解は困難ですが、その素因数分解をせずにＲＳＡ暗号を解読できる抜け道が、もしかしたら存在するかもしれないのです。
こういう未知なものにロマンを感じざるを得ない...
