RSA暗号
1978年
(時代的に)コンピュータがあることが前提
公開鍵暗号方式
鍵生成
大きな素数$ p, q\;(p\ne q)と$ N=pqを用意する
$ \gcd((p-1)(q-1), e)=1となる$ eをランダムに選ぶ
この$ eは$ (p-1)(q-1)より小さくて$ (p-1)(q-1)と互いに素なら何でもいい
なんで$ (p-1)(q-1)より小さくないといけない？
適当に小さめな素数を決めればだいたい行ける。11とか
でも小さすぎたら弱くなるんかな
オイラー関数を用いて$ \varphi(N)=(p-1)(q-1)とおく $ ed \equiv 1 \pmod {\varphi(N)}を満たす整数$ dを、拡張ユークリッドの互除法を用いて求める 拡張ユークリッド互除法を用いると、$ xe+y\varphi(N)=1が得られる
入力は、$ e,\varphi(N)
出力が$ 1,x,y
つまり、上の式より自明だが1は出力で得られる
なので、この$ xこそが欲しかった$ dに当たる
$ yは使わない
$ dを得るために拡張ユークリッド互除法を使ってる
公開鍵
$ N, e
秘密鍵
$ d
暗号化した人だけが知っているものは
$ p,q,d
暗号化
$ C \equiv M^e \pmod N
$ M: 平文
$ C: 暗号文
相手に送るやつ
複合
$ C^d\equiv M \pmod N
解法
$ C^d \equiv (M^e)^d \equiv M^{1+m\varphi(N)} = (M^{\varphi(N)})^m \cdot M \equiv M \pmod N
成り立っている式
$ C\equiv M^eは暗号化時にそう置いている
$ ed\equiv1\pmod{p-1}
$ pが素数なら、$ a^{p-1}\equiv 1\pmod p
より、両辺を$ x乗し、両辺に$ aをかけると以下が成り立つ
$ a^{1+x(p-1)}\equiv a\pmod p\;(\forall{x}\in \mathbb{Z})
↑これを$ p,qに対して使うと任意の整数$ xに対し以下が成り立つことがわかる
$ a^{1+x(p-1)(q-1)}\equiv a\pmod {pq}
この式を解法の3,4項目で使っている
安全性
公開鍵$ N,eから、秘密鍵$ dがバレてはいけない
$ Nが素因数分解されてしまったら$ N=(p-1)(q-1)より$ p,qがバレる
そうすると$ ed\equiv 1\pmod {(p-1)(q-1)}より秘密鍵$ dがバレる
Haskell
使用する2つの素数$ p,$ qが近い数だと、解読することができてしまう
参考