書記が数学やるだけ#891 RSA暗号の安全性

RSA暗号の攻撃法を中心に見ていく。

問題

説明

RSA暗号方式は1977年に発明され、その名称は発明者であるロナルド・リベスト（Ronald Rivest）、アディ・シャミア（Adi Shamir）、レオナルド・エーデルマン（Leonard Adleman）の頭文字を組み合わせたものである。

計算例：

セキュリティパラメータが 1024 の場合、n は 1024 ビットという非常に大きな整数となり、秘密指数 d も n とほぼ同程度の桁数を持つ。このとき

$$a=b^d \mod n$$

を計算するには、バイナリ法（繰り返し自乗法）と呼ばれるアルゴリズムを用いることで、1024ビット同士の剰余乗算をおよそ 1500 回程度繰り返すだけで実現できる。

RSA暗号は、特定の条件下では脆弱性を示す場合が多数存在する。例えば、公開指数 e が小さすぎる場合（Low Public Exponent Attack）、秘密鍵 d が小さすぎる場合（Wiener Attack）、あるいは同じ平文を同じ Nで異なる公開指数 e により暗号化した場合（共通法攻撃）などが挙げられる。

解答

RSA暗号の正当性を示す際には、平文 m が n の約数であるかどうかによって場合分けを行う。m が n の約数でない場合は、式を変形したうえでオイラーの定理を用いて正当性を示すことができる。

m が n の約数である場合は、m^ed に対して中国剰余定理を適用することで正当性を示すことができる。

同じ平文 m を同一の公開モジュラス N に対して、複数の異なる公開指数 e1 ,e2 ,… で暗号化した暗号文を攻撃者が入手すると、中国剰余定理を利用して元の平文 m を求められる可能性がある（共通法攻撃）。

公開指数 e が非常に小さい値（例えば 3 や 5）に設定されていると、暗号文 c が m^e<n の場合に、剰余演算を行わず平文 m を直接求められてしまう可能性がある（Low Public Exponent Attack）。

秘密鍵 d が小さい場合、攻撃者は公開鍵 (N,e) から連分数展開を用いて d を効率的に復元することができる（Wiener’s Attack）。

近似分数の性質について：

本記事のもくじはこちら：