ウィーナーの攻撃

暗号学者マイケル・J・ウィーナーにちなんで名付けられたウィーナー攻撃は、 RSA暗号に対する暗号攻撃の一種です。この攻撃は、連分数表現を用いて、 dが小さい 場合に秘密鍵dを暴露します。

RSAの背景

架空の人物、アリスとボブは、安全に通信したい人々です。具体的には、アリスはボブに、ボブだけが読めるメッセージを送りたいと考えています。まずボブは 2 つの秘密の素数pとqを選択します。次に、RSA係数N = pqを計算します。この RSA 係数は、暗号化指数eとともに公開されます。N とeは公開鍵ペア( e、N )を形成します。この情報を公開することで、誰でもボブへのメッセージを暗号化できます。復号化指数d はed ≡ 1 (mod λ ( N ))を満たします。ここで、λ ( N ) はカーマイケル関数を表しますが、オイラーのトーシェント関数φ ( N ) が使用されることもあります (注: これは乗法群( Z ‍ /‍ NZ ) ^×の順序であり、必ずしも巡回群ではありません)。暗号化指数eとλ ( N ) も互いに素でなければならないため、モジュラー逆が存在する。Nの因数分解と秘密鍵dは秘密に保持されるため、ボブだけがメッセージを復号できる。秘密鍵ペアを( d , N )と表記する。メッセージMの暗号化はC ≡ M ^e (mod N )で与えられ、暗号文Cの復号はC ^d ≡ ( M ^e ) ^d ≡ M ^ed ≡ M (mod N )で与えられる（オイラーの定理を使用）。

ユークリッドの互除法を用いると、 Nの因数分解が分かれば秘密鍵dを効率的に復元できる。秘密鍵dが分かれば、 Nの法を効率的に因数分解できる。^{[ 1 ]}

小さな秘密鍵

RSA暗号システムにおいて、ボブはRSA復号性能を向上させるために、大きな乱数ではなく小さな値のdを使用する傾向があるかもしれません。しかし、ウィーナーの攻撃は、 dに小さな値を選択すると、攻撃者がすべての秘密情報を復元できる、つまりRSAシステムを破ることができる安全でないシステムになることを示しています。この破綻は、 dが小さな値であるときに成立するウィーナーの定理に基づいています。ウィーナーは、 d < ⁠のときに攻撃者がdを効率的に見つけることができることを証明しました。1/3⁠北^1/4 . ^{[ 2 ]}

Wiener氏の論文では、彼の攻撃に対する高速な復号を可能にするいくつかの対策も提示されています。具体的には、以下の2つの手法が説明されています。

大きな公開鍵の選択：e をe ′に置き換えます。ここで、e ′ = e + k ⋅ λ ( N ) （ kの大きさ）です。e ′ が十分に大きい場合、つまりe ′ > N ^{3/2 の}場合、 dがどれだけ小さくてもウィーナー攻撃は適用できません。

中国剰余定理を使う：d _p ≡ d (mod ( p − 1))とd _q ≡ d (mod ( q − 1))が両方とも小さいが、 d自体は小さくなるようにd を選択すると、 Cの高速復号化は次のように実行できます。

1. まずM _p ≡ C ^{d _p} (mod p )とM _q ≡ C ^{d _q} (mod q )を計算します。
2. 中国剰余定理を使用して 、 M ≡ M _p (mod p )およびM ≡ M _q (mod q )を満たす0 ≤ M < Nの一意の値を計算します。 Mの結果は、必要に応じてM ≡ C ^d (mod N )を満たします。重要な点は、 d mod λ ( N )の値が大きくなる可能性があるため、ここではウィーナー攻撃は適用されないことです。

攻撃の仕組み

ご了承ください

${\displaystyle \lambda (N)=\operatorname {lcm} (p-1,q-1)={\frac {(p-1)(q-1)}{G}}={\frac {\varphi (N)}{G}}}$

ここでG = gcd( p − 1, q − 1)。

ed ≡ 1 ( mod λ ( N ) )なので、

${\displaystyle ed=K\times \lambda (N)+1}$

${\displaystyle ed={\frac {K}{G}}(p-1)(q-1)+1}$

k = ⁠の定義K/gcd( K , G )⁠およびg = ⁠G/gcd( K , G )⁠、これを上記に代入すると次のようになります。

${\displaystyle ed={\frac {k}{g}}(p-1)(q-1)+1}$ 。

dpqで割ると:

${\displaystyle {\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )}$ 、 どこ。${\displaystyle \delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}}$

だから、⁠e/pq⁠は⁠よりわずかに小さいけ/dg⁠、前者は完全に公開情報で構成されています。しかし、確認と推測の手段は依然として必要です。

簡単な代数演算と恒等式を用いることで、推測の正確さを確認することができる。^{[ 1 ]}

ウィーナーの定理

N = pqとし、q < p < 2 qとする。d < ⁠1/3⁠ N ^1/4。

ed≡1 (modλ ( N ) )の⟨N , e⟩が与えられると、攻撃者はdを効率的に回復できる。^{[ 2 ] [ 3 ]}

例

公開鍵が⟨ N , e ⟩ = ⟨90581, 17993⟩であると仮定する。攻撃はd を決定する必要がある。ウィーナーの定理と連分数を用いてd を近似するために、まず⁠の連分数展開を求める。e/北⁠。このアルゴリズムは分数を最小の項で求めることに注意してください。

${\displaystyle {\frac {e}{N}}={\frac {17993}{90581}}={\cfrac {1}{5+{\cfrac {1}{29+\dots +{\cfrac {1}{3}}}}}}=\left[0,5,29,4,1,3,2,4,3\right]}$

⁠の連分数展開によれば、e/北⁠、すべての収束⁠け/d⁠は次のとおりです。

${\displaystyle {\frac {k}{d}}=0,{\frac {1}{5}},{\frac {29}{146}},{\frac {117}{589}},{\frac {146}{735}},{\frac {555}{2794}},{\frac {1256}{6323}},{\frac {5579}{28086}},{\frac {17993}{90581}}}$

最初の収束はNの因数分解を生じないことが確認できます。しかし、収束は1/5⁠利回り

${\displaystyle \varphi (N)={\frac {ed-1}{k}}={\frac {17993\times 5-1}{1}}=89964}$

さて、この方程式を解くと

${\displaystyle x^{2}-\left(\left(N-\varphi (N)\right)+1\right)x+N=0}$

${\displaystyle x^{2}-\left(\left(90581-89964\right)+1\right)x+90581=0}$

${\displaystyle x^{2}-618x+90581=0}$

すると、 x = 379; 239となる根が見つかる。したがって、因数分解が見つかった。

${\displaystyle N=90581=379\times 239=p\times q}$ 。

係数N = 90581の場合、ウィーナーの定理は次の場合に成り立つ ことに注意する。

${\displaystyle d<{\frac {N^{1/4}}{3}}\approx 5.7828}$ 。

ウィーナーの定理の証明

証明は連分数を用いた近似に基づいている。^{[ 2 ]}

ed = 1 (mod λ ( N ))なので、 ed − kλ ( N ) = 1となるk が存在する。したがって、

${\displaystyle \left|{\frac {e}{\lambda (N)}}-{\frac {k}{d}}\right\vert ={\frac {1}{d\lambda (N)}}}$ 。

G = gcd( p − 1, q − 1)とします。λ ( N ) の代わりにφ ( N )を使用すると、証明はG = 1に置き換えられ、φ ( N ) はλ ( N ) に置き換えられることに注意してください。

次に⁠を掛けて1/G⁠、

${\displaystyle \left|{\frac {e}{\varphi (N)}}-{\frac {k}{Gd}}\right\vert ={\frac {1}{d\varphi (N)}}}$

したがって、⁠け/神様⁠ は⁠の近似値ですe/φ ( N )⁠ 。攻撃者はφ ( N )を知らないが、N を使って近似値を求める可能性がある。実際、 φ ( N ) = N − p − q + 1かつp + q − 1 < 3 √ Nなので、以下の式が成り立つ。

${\displaystyle \left\vert p+q-1\right\vert <3{\sqrt {N}}}$

${\displaystyle \left\vert N-\varphi (N)\right\vert <3{\sqrt {N}}}$

φ ( N )の代わりにNを使用すると次のようになります。

${\displaystyle {\begin{aligned}\left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert &=\left\vert {\frac {edG-kN}{NGd}}\right\vert \\&=\left\vert {\frac {edG-k\varphi (N)-kN+k\varphi (N)}{NGd}}\right\vert \\&=\left\vert {\frac {1-k(N-\varphi (N))}{NGd}}\right\vert \\&<\left\vert {\frac {-k(N-\varphi (N))}{NGd}}\right\vert (\ because 0<|N-\varphi (N)|)\\&<\left\vert {\frac {3k{\sqrt {N}}}{NGd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}Gd}}\leq {\frac {3k}{d{\sqrt {N}}}}\end{aligned}}}$

ここで、kλ ( N ) = ed − 1 < ed なので、kλ ( N ) < ed となります。e < λ ( N )なので、kλ ( N ) < ed < λ ( N ) dとなり、以下の式が得られます。

${\displaystyle k\lambda (N)<\lambda (N)d}$

${\displaystyle k<d}$

k < dかつd < ⁠なので1/3⁠ N ^1/4 . したがって次式が得られます。

（1）${\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert <{\frac {1}{dN^{\frac {1}{4}}}}}$

d < ⁠​1/3⁠ N ^1/4、 2 d < 3 d、そして2 d < 3 d < N ^1/4の場合、次の式が得られます。

${\displaystyle 2d<N^{1/4}}$ なので（2）${\displaystyle {\frac {1}{2d}}>{\frac {1}{N^{1/4}}}}$

（１）と（２）から、

${\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{Gd}}\right\vert <{\frac {3k}{d{\sqrt {N}}}}}{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2}}}}$

もし| x − ⁠1つの/b⁠ | < ⁠1/2 b ²⁠、そして⁠1つの/b⁠はxの収束なので、⁠け/神様⁠ は⁠の収束の中に現れるe/北⁠。したがって、アルゴリズムは最終的に⁠を見つけることになります。け/神様⁠。

参考文献

1. L. Render, Elaine (2007). WienerのShort Secret Exponentsへの攻撃.
2. ボネ、ダン. 「RSA暗号システムへの20年間の攻撃」（PDF） .アメリカ数学会報. 46 (2): 203– 213.
3. Wiener, Michael J. (1990). 「短いRSA秘密指数の暗号解析」. IEEE Transactions on Information Theory . 36 (3). IEEE : 553– 558. Bibcode : 1990ITIT...36..553W . doi : 10.1109/18.54902 .

さらに読む

• コッパースミス、ドン (1996). 低指数RSAと関連メッセージ. シュプリンガー・フェアラーク・ベルリン・ハイデルベルク.

• Dujella, Andrej (2004). 「連分数と小さな秘密指数を持つRSA」arXiv : cs/0402052 .
• Wiener 攻撃の Python 実装。
• R. スティンソン、ダグラス (2002).暗号理論と実践(第2版). CRC Press Company. pp.  200– 204. ISBN 1-58488-206-9。