RSA暗号
素数生成
暗号として機能する素数の大きさは$2^{512}$ や $2^{1024}$ 程度のオーダーでなければいけない。素数定理より、ある数$n$が素数である確率は約$1/\log n$である。例えば$n=2^{512}$で2.8%、$n=2^{1024}$で1.4%となる。500回乱数を生成すれば99.65%で素数を見つけられる。
素数判定のアルゴリズムは多くあるがここではMiller-Rabin素数判定法を紹介する。
Solovay-Strassen素数判定法
与えられた数nが素数かどうかを計算時間$O(k\log n)$で誤り率$2^{-k}$以下で判定するアルゴリズムです。
Miller–Rabin素数判定法
与えられた数nが素数かどうかを計算時間 $O(k\log^3 n)$ で誤り率$4^{-k}$以下で判定するアルゴリズムです。
nが素数のとき、$n-1$を2で割れるだけ割った数をdとして$n-1 = 2^sd$と書ける。フェルマーの小定理より$a≠0 \pmod n$のとき
\begin{align}
a^{n-1} &= a^{2^sd} ≡ 1 \quad \pmod n\\
a^{2^sd}-1 &= (a^d-1)(a^d+1)(a^{2d}+1)(a^{4d}+1)\cdots(a^{2^{s-1}d}+1)\\
&≡ 0 \quad \pmod n\\
\end{align}
これより次の2式のどちらかが成り立つ。
\begin{align}
\left\{
\begin{array}{ll}
a^d &≡ 1 \quad \pmod n\\
a^{2^rd} &≡ -1 \qquad \pmod n \qquad (\exists r \in \mathbb{Z}, 0\leq r\leq s-1)
\end{array}
\right.
\end{align}
この対偶をとると、あるaをとってきて次の2式をどちらも満たすとき
\begin{align}
\left\{
\begin{array}{ll}
a^d &≢ 1 \quad \pmod n\\
a^{2^rd} &≢ -1 \qquad \pmod n \qquad (\forall r \in \mathbb{Z}, 0\leq r\leq s-1)
\end{array}
\right.
\end{align}
nは合成数であると言える。
これを用い、次のステップを実行することで確率的な素数判定ができる。
- $1\leq a \leq n-1$でaの値をランダムにとってくる。
- 上の条件を満たしたらcompositeと返す。
- 満たさなければprobably primeと返す。
これを繰り返すことで判定の精度が高まる。この処理をMiller–Rabin素数判定法という。実行時間は$O(k\log^3 n)$、FFTベースの乗算で$Õ(k\log^2 n)$となる。
具体例を考えてみよう。判定時にprobably primeを返した時p compositeを返した時cとする。
$n = 25$ (合成数)のとき
$n-1 = 24 = 2^3 \times 3$ より $s = 3,\ d = 3$ となる。
| a | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $a^3 \bmod 25$ | 1 | 8 | 2 | 14 | 0 | 16 | 18 | 12 | 4 | 0 | 6 | 3 | 22 | 19 | 0 | 21 | 13 | 7 | 9 | 0 | 11 | 23 | 17 | 24 |
| $a^6 \bmod 25$ | 1 | 14 | 4 | 21 | 0 | 6 | 24 | 19 | 16 | 0 | 11 | 9 | 9 | 11 | 0 | 16 | 19 | 24 | 6 | 0 | 21 | 4 | 14 | 1 |
| $a^{12} \bmod 25$ | 1 | 21 | 16 | 16 | 0 | 11 | 1 | 11 | 6 | 0 | 21 | 6 | 6 | 21 | 0 | 6 | 11 | 1 | 11 | 0 | 16 | 16 | 21 | 1 |
| 判定 | p | c | c | c | c | c | p | c | c | c | c | c | c | c | c | c | c | p | c | c | c | c | c | p |
$n = 17$ (素数)のとき
$n-1 = 16 = 2^4 \times 1$ より $s = 4 ,\ d = 1$ となる。
| a | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| $a \bmod 17$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| $a^2 \bmod 17$ | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 | 13 | 15 | 2 | 8 | 16 | 9 | 4 | 1 |
| $a^4 \bmod 17$ | 1 | 16 | 13 | 1 | 13 | 4 | 4 | 16 | 16 | 4 | 4 | 13 | 1 | 13 | 16 | 1 |
| $a^8 \bmod 17$ | 1 | 1 | 16 | 1 | 16 | 16 | 16 | 1 | 1 | 16 | 16 | 16 | 1 | 16 | 1 | 1 |
| 判定 | p | p | p | p | p | p | p | p | p | p | p | p | p | p | p | p |
かなりの正確で判定できることがわかるだろう。
正確性について
まず、フェルマーの小定理よりnが奇素数ならば常にprobably primeと返す。
ここで示したいことはnが9以上の合成数のときprobably primeと返すようなaの数をP(n)として$P(n)\leq\phi(n)/4$が成り立つことである。。
P(n) \subseteq S(n)\\
|P(n)| \leq |S(n)| \leq \phi(n)/4\\
\begin{align*}
\overline{\mathcal{S}}(n) &= \{a \bmod{n} \mid a^{2^{\nu(n)-1}m}\equiv \pm 1 \pmod{n} \}
\end{align*}
k回試行すれば誤り率は$4^{-k}$以下となる。10回で99.9999046%成功する。
RSA暗号の方法
フェルマーの小定理より素数$ p, q\ $を用いて$ m, n = pq\ $が互いに素のとき次が成り立つ。
m^{(p - 1)(q - 1)} ≡ 1 \pmod n
$ \phi(n) = (p - 1)(q - 1)\ $とおくと、肩の数は$\phi(n)$を法として次のような計算ができる。
\begin{align}
c &≡ m^e \pmod n \\
d &≡ e^{-1} \pmod {\phi(n)} \\
c^d &≡ m^{ed} ≡ m \pmod n
\end{align}
ここで$n, e$を知っていても素数$p, q(\approx 2^{512})$を知らないとき$c$から$m$を求めることは難しい。これを用いた暗号をRSA暗号(Rivest-Shamir-Adleman)と呼ぶ。
具体的には次の手順で通信する。
- AliceがBobに公開鍵$n, e$を渡す
- Bobは公開鍵を用いて平文を暗号化
- BobからAliceへ暗号文を送る
- Aliceは秘密鍵$p, q$を用いて復号化して平文を得る
これで送っている最中に盗聴されても平文の内容は秘密鍵がなければ解読できず、安全な通信ができる。
またこれは一方向通信であるが、逆も同様に行えば双方向通信が実現する。
RSA暗号の解読方法
このスライドを元に解説を書く
それぞれの方法を具体的に解説する。
その1 公開鍵 n のビット数（鍵長）が小さくてはいけない (Pollard-rho 素因数分解法)
公開鍵 $n$ のビット数が小さいと素因数分解されて秘密鍵 $p, q$ を求められてしまう。素因数分解を行うアルゴリズムは多くあり、近年は一般数体篩法お手軽で高速なアルゴリズム、Pollard-rho法を解説する。RSA暗号以外にも楕円曲線暗号にも効く。
その3 近い値の素数を用いてはいけない (Fermat's method)
p, qが近いと中心から順に調べることで素数の組を見つけられる。
\begin{align}
n &= (x + d)(x - d) \\
&= x^2 - d^2 \\
&= (\lceil\sqrt n\rceil + k)^2 - d^2 \\
d^2 &= (\lceil\sqrt n\rceil + k)^2 - n
\end{align}
より$ (\lceil\sqrt n\rceil + k)^2 - n\ $についてkを増やしていき、計算結果が平方数となったとき$p, q$が求まる。
このままだと$O(\sqrt n)$付近しか探索できないが近似比が与えられていればその近辺を探索できる。
\begin{align}
\frac{a}{b} &\approx \frac{p}{q} \\
aq &\approx bp \\
aq \times bp &= abn
\end{align}
より$abn$に対しFermat's methodを適用することで$p, q$が求まる。
その6 eの値が小さすぎてはいけない (Low Public Exponent Attack)
$e = 3$くらいなら$m^e < n$となり$m$を求められることがある。
\begin{align}
c &≡ m^e \pmod n \\
c &= m^e \\
m &= \sqrt[e] c
\end{align}
累乗根はニュートン法と呼ばれる近似法を用いると高速に求められる。
\begin{align}
f(x) &= x^e - c \\
0 &= f'(x_n)(x_n - x_{n+1}) + f(x_n) \\
x_{n+1} &= x_n + \frac{f(x_n)}{f'(x_n)} \\
m &= x_N & (\exists N \in \mathbb{N})
\end{align}
その7 eの値が大きすぎてはいけない (Wiener's Attack)
eが大きい$(\approx N)$と秘密鍵$d = e^{-1}$が小さくなりdを求められる。次のようにユークリッドの互除法を用いて連分数展開し、適当な場所で打ち切って再構成することで近似分数を作ることが出来る。
\begin{align}
ed &≡ 1 \pmod{\phi(n)} \\
ed &= k(n - p - q + 1) + 1 \\
\frac{e}{n} &= \frac{k}{d}(1-\delta) &\delta = \frac{p + q - 1 - \frac{1}{k}}{n} \approx \frac{1}{2^{512}} \\
\frac{e}{n} &\approx q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\dots \cfrac{}{q_{m-1} + \cfrac{1}{q_m}}}}} = \frac{k}{d} \\
\end{align}
\begin{align}
r_{-2} &= n \\
r_{-1} &= e \\
r_{i-2} \div r_{i-1} &= q_{i} \cdots r_{i} \\
\\k_{-2} &= 0 &d_{-2} &= 1 \\
k_{-1} &= 1 &d_{-1} &= 0 \\
k_i &= q_i k_{i−1} + k_{i−2} &d_i &= q_i d_{i−1}+d_{i−2} \\
\end{align}
$k_i, d_i$の計算をどこで打ち切るかは2次方程式の判別式を用いて判定する。
\begin{align}
x^2 - (p + q)x + pq &= (x - p)(x - q) = 0 \\
p + q &= n - \frac{ed - 1}{k} + 1 \in \mathbb{N} \\
pq &= n \\
D &= (p + q)^2 - 4n \geq 0 \\
\end{align}
その8 同一の平文を異なるeで暗号化した暗号文を与えてはいけない (Common Modulus Attack)
\begin{align}
c_1 &≡ m^{e_1} \pmod n \\
c_2 &≡ m^{e_2} \pmod n \\
\end{align}
$e_1, e_2$について$gcd(e_1, e_2) = g$のとき拡張ユークリッドの互除法を用いることで次を満たす$s_1, s_2$を計算できる。
\begin{align}
s_1e_1 + s_2e_2 &= g \\
c_1^{s_1} c_2^{s_2} = m^{s_1e_1 + s_2e_2} &= m^g \pmod n \\
\end{align}
これによって$e_1, e_2$が互いに素のとき、または$g$が小さいならばLow Public Exponent Attackを用いて$m$を求められる。
その9 同一の平文を異なるnで暗号化した暗号文を与えてはいけない (Håstad's Broadcast Attack)
$n_1, ..., n_e$が互いに素ならば中国剰余定理を用いて$m$を求められる。garnerのアルゴリズムを用いて$m^e$を計算する。
https://www.creativ.xyz/ect-gcd-crt-garner-927/
\begin{align}
c_1 &≡ m^e \pmod{n_1} \\
c_2 &≡ m^e \pmod{n_2} \\
\vdots \\
c_e &≡ m^e \pmod{n_e} \\
c &≡ m^e \pmod{n_1n_2\cdots n_e} \\
c &= m^e \\
\end{align}
その10 任意の暗号文を復号した結果の偶奇(下位1bit)を知られてはいけない (LSB Decryption Oracle Attack)
その11 上位ビットが共通する二つの平文に対する暗号文を知られてはいけない (Franklin-Reiter Related Message Attack)
その12 素数pの上位ビットまたは下位ビットが知られてはいけない (Coppersmith's Attack)
Coppersmithの定理
Nを法とした$f \in \mathbb{Z}[x]$を満たす次数dのモニック多項式があり、$X + N^{\frac{1}{d}} - \epsilon (1/d > \epsilon)$
その13 秘密鍵dの下位ビットが知られてはいけない (Partial Key Exposure Attack)
その14 平文mの上位ビットまたは下位ビットが知られてはいけない (Coppersmith's Attack)
RSA-CRT Fault Attack
RSA-CRTにバグがあることで攻撃、復号時に中国剰余定理(CRT)
Coppersmith's Short Pad Attack
離散対数問題(DLP: Discrete Logarithm Problem)
g^x = y \pmod n
xからyを求めるのは簡単だがyからxを求めるのは難しいという非対称性を用いて暗号を作る。楕円暗号はこれを用いる。
xからyを求める方法
バイナリ法に比べサイドチャネル攻撃に強いモンゴメリ冪乗法(Montgomery Powering Ladder)
ビルドイン関数 powはバイナリ法
pycryptodomeはモンゴメリ
yからxを求める方法
Baby-step Giant-step
平方分割してにぶたん
Pohlig–Hellman algorithm
オイラーの定理で剰余とって中国剰余定理
楕円曲線暗号
楕円曲線暗号の方法
x_1 = x_2, y_1 = −y_2, P + Q = O \\
λ = \frac{y_2 - y_1}{x_2 - x_1} \\
x3 = λ2 − x1 − x2, y3 = λ(x1 −x3) − y1 \\
P + Q = (λ^2 − x_1 − x_2, λ(x_1 − x_3) − y_1) \\
λ = \frac{3x_1^2 + a}{2y_1} \\
2P = \\