from 公開鍵暗号

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が近い数だと、解読することができてしまう

参考

『現代暗号の基礎数理』 7章