まずは RSA 署名の復習から。 p, q を k/2 ビットの素数、 N = p×q を k ビットの合成数として、公開鍵を (N, e)、秘密鍵を (d, p, q) とおきます。このとき、メッセージ m に対する RSA 署名は s = u(m)d mod N によって生成されます。また、メッセージ m に対する署名 s の検証は se と u(m) が mod N で等しいかをチェックします。ここで u(m) はパディングと呼ばれる関数で、暗号の教科書では u(m) = m として説明されることが多いのですが、安全性に問題があるため、現実にはもう少し複雑な関数が使用されます。
さて、本題の Desmedt-Odlyzko による偽造法 (DO 偽造法) ですが、攻撃の最終目標は偽造署名を算出することです。前提として、攻撃者はメッセージを選択できることと、署名オラクルを利用できることを仮定します。具体的には、攻撃者は最終的に
| s* = D×s1e1×s2e2×...×sLeL mod N |
|
という関係式から偽造署名 s* を算出するので、攻撃者は係数 D と指数 e1, e2, ..., eL を求めれば十分です。ここで s1, s2, ..., sL はメッセージ m1, m2, ..., mL に対応する(同じ秘密鍵のもとでの)署名です。係数 D と指数 e1, e2, ..., eL を求めるには、メッセージに関する関係式
| u(m*) = De×u(m1)e1×u(m2)e2×...×u(mL)eL mod N |
|
を利用します。つまり DO 偽造法の目標は、この関係式を満たす係数 D と指数 e1, e2, ..., eL を求めることです。
上の関係式を求めるために、DO 偽造法は u(m) の素因数分解を利用します。その方法を説明する前に、素因数分解関係の記号を定義しておきましょう。 L 個の素数を小さい順にならべて得られる集合を PrimeL とかき、その要素を p1=2, p2=3, ..., pL=B とおきます。ある自然数が B 以下の素数のべき積として素因数分解できるとき、その自然数は B-smooth であると言います。例えば 15 は 3 と 5 の積として素因数分解できますので、15 は 5-smooth です。
DO 偽造法は、 u(m) が B-smooth となるようなメッセージ m を L+1 個以上収集します。得られたメッセージとその素因数分解を
と表し、 u(mi) の素因数分解に登場する指数から得られる L 次元ベクトル
| Vi = (v(i,1), v(i,2), ..., v(i,L)) |
|
を考えます。このベクトルは L+1 個ありますので、高い確率で線形従属となり、あるベクトル Vt を他のベクトルの線形結合として
| Vt = e ×V0 + b1 ×V1 + b2 ×V2 + ... + bL ×VL |
|
と表すことができます。ここで V0 = (v(0,1), v(0,2), ..., v(0,L)) は定数ベクトル b1, b2, ..., bL は e 未満の整数係数となります (線形結合の計算手順の説明はここでは省略しますが、
以下の数値例から理解できると思いますが)。
このとき、
とおくことで、偽造署名
| st* = D ×s1b1 ×s2b2 ×... ×sLbL mod N |
|
が得られます。
うーん、数式だらけで全然わかりませんね ^^; とりあえず押さえておきたいのは、 DO 偽造法はメッセージ u(m) が素因数分解できることを利用している点です。単純な RSA 署名であれば u(m) = m となっていますので、 u(m) が素因数分解できるようなメッセージを収集することは簡単です。しかし u(m) がもっと複雑な場合 (u(m) のビット長が大きな場合)、その素因数分解は困難となり、 DO 偽造法も適用できなくなってしまいます。 ISO/IEC 9796-2 (Scheme 1) は u(m) が k-1 ビットとなるように設計されているので、 DO 偽造法は適用できないのです。 これが DO 偽造法の特徴でもあり限界でもあります。
最後に DO 偽造法の処理内容を数値例を用いて説明していきます。以下では u(m)=SHA16(m) (SHA16 は出力長が 16 ビットのハッシュ関数で、具体的には SHA-1 の下位 16 ビットを用います)、e=3、L=7 (つまり PrimeL = {2,3,5,7,11,13,17=B}) とします。初めの処理は、u(mi) が B-smooth となるようなメッセージ mi を L+1 個以上収集することです。 m=1,2,... と変化させていくと、以下の 8 個のメッセージを得ることができます:
次に、これら 8 個の素因数分解から線形結合を求めるために、次のような行列を考えます。この行列の各行は上の素因数分解の各行の指数を並べたものです。また右側には、どの行とどの行を足し合わせたかを記録するために、単位行列を並べておきます。
次に各成分を mod e します。
以下、Gauss 消去によって線形結合を求めていきます。まず、5 行目をピポットにして 1 列目を消去します。
次に、3 行目をピポットにして 2 列目を消去します。
次に、1 行目をピ・- ットにして 3 列目を消去します。
次に、2 行目をピポットにして 4 列目を消去します。
次に、4 行目をピ・- ットにして 5 列目を消去します。
次に、7 行目をピポットにして 6 列目を消去します。
最後に、8 行目をピポットにして 7 列目を消去します。
このとき、6 行目の成分が全て 0 になっていますので、線形結合
| 0 = 1 ×V1 + 2 ×V2 + 0 ×V3 + 0 ×V4 + 0 ×V5 + 1 ×V6 + 2 ×V7 + 1 ×V8 mod e |
|
つまり
| V6 = -1 ×V1 - 2 ×V2 - 2 ×V7 - 1 ×V8 mod e |
|
が得られます。よって、各ベクトルの成分ごとに比較することで、整数上の線形結合
| V6 = e ×V0 + 2 ×V1 + 1 ×V2 + 1 ×V7 + 2 ×V8 |
|
が得られます。ここで V0=(-6,-3,0,-1,-1,-1,-1,-1) となります。
以上より、
|
|
|
| 2-6 ×3-3 ×7-1 ×11-1 ×13-1 ×17-1 |
|
|
|
| De ×u(m1)2 ×u(m2)1 ×u(m7)1 ×u(m8)2 |
|
|
|
|
という関係式が得られます。ここまでの計算に N や d の値を用いていないことに注意して下さい。
最後は偽造署名の算出です。公開鍵 N=281467359833221 と s1=992405412287, s2=108524445318, s7=912311723672, s8=362819320988 が得られたとすると、偽造署名
| s6* = D ×s12 ×s21 ×s71 ×s82 mod N = 815606114320 |
|
が算出できます。実際、(s6*)e mod N = 11900 = u(m6) となり、偽造署名の正当性が検証できます。偽造には秘密鍵を一切用いていないことに注意して下さい。
次回は DO 偽造法を改良した Coron-Naccache-Stern 偽造法を説明したいと思います。
【関連ブログ記事】
コメント