(57)【要約】  本発明は、T-functionはデータの下位から上位へしか波及しないため、データに差分を与えても差分を与えたビット位置より下位ビットには差分が伝播せず、T-functionを利用したストリーム暗号は差分を利用して解読される可能性があるという問題を解決することを目的とする。非線形変換手段１１（T-function）でデータを更新した後に、転置手段（１３）でビット転置を行う処理を追加し、これによって、差分が上位ビットから下位ビットに波及する効果が期待できる（図１）。
2008117804.tif 000002
【特許請求の範囲】
【請求項１】
ストリーム暗号に用いられる擬似乱数生成装置であって、
少なくとも１つの内部状態と、
前記内部状態に保存されている数値データを更新する非線形変換手段と、
前記非線形変換手段で更新された数値データに対して、予め定められたルールに基づいてビット転置を行う転置手段と、
を備えたことを特徴とする擬似乱数生成装置。
【請求項２】
前記内部状態の更新が、
擬似乱数列の出力ごとに、
擬似乱数列の出力よりも多く、
擬似乱数列の出力よりも少なく、
のうちのいずれか１つにしたがって行われる、
ことを特徴とする請求項１に記載の擬似乱数生成装置。
【請求項３】
前記ビット転置のルール付けを、予め定められたテーブルの値に従って変更する、
ことを特徴とする請求項１又は２記載の擬似乱数生成装置。
【請求項４】
請求項１乃至３のいずれか一に記載の擬似乱数生成装置で用いられる擬似乱数列を生成する擬似乱数列生成装置。
【請求項５】
ストリーム暗号に用いられる擬似乱数を生成するプログラムであって、
少なくとも１つの内部状態に保存されている数値データを更新する非線形変換処理と、
更新された数値データに対して、予め定められたルールに基づいて、ビット転置を施す転置処理と、
をコンピュータに実行させるプログラム。
【請求項６】
前記内部状態の更新が、
擬似乱数列の出力ごとに、
擬似乱数列の出力よりも多く、
擬似乱数列の出力よりも少なく、
のうちのいずれか１つにしたがって行われる、
ことを特徴とする請求項５に記載のプログラム。
【請求項７】
前記ビット転置のルール付けを、予め定められたテーブルの値に従って変更する処理を含む、ことを特徴とする請求項５又は６記載のプログラム。
【請求項８】
請求項５乃至７のいずれか一に記載のプログラムを記録したコンピュータが読みとり可能な記録媒体。
【請求項９】
ストリーム暗号に用いられる擬似乱数を生成する方法であって、
少なくとも１つの内部状態に保存されている数値データを更新する非線形変換工程と、
更新された数値データに対して、予め定められたルールに基づいて、ビット転置を施す転置工程と、
を含むことを特徴とする擬似乱数生成方法。
【請求項１０】
前記内部状態の更新が、
擬似乱数列の出力ごとに、
擬似乱数列の出力よりも多く、
擬似乱数列の出力よりも少なく、
のうちのいずれか１つにしたがって行われる、
ことを特徴とする請求項９に記載の擬似乱数生成方法。
【請求項１１】
前記ビット転置のルール付けを、予め定められたテーブルの値に従って変更する、
ことを特徴とする請求項９又は１０記載の擬似乱数生成方法。
【請求項１２】
所定ビット幅のデータを保持するレジスタを複数備え、
前記複数のレジスタに保持されている複数のデータを入力して非線形変換を行う非線形変換手段と、
前記非線形変換手段で変換された複数のデータを入力し、各データを上位、下位ビットに分割し、一のデータの上位ビットが別のデータの下位ビットに配置されるようなビット転置を行う転置手段と、
前記非線形変換手段と前記転置手段との間に配設され、前記非線形変換手段から出力される複数のデータを、前記転置手段に供給するか、又は前記複数のレジスタへ戻す選択を行うセレクタと、
を備え、
前記転置手段から出力される、ビット転置された複数のデータは、前記複数のレジスタに戻されて保持される、擬似乱数生成装置。
【請求項１３】
前記非線形変換手段が、マルチワードＴ−ファンクション（ｍｕｌｔｉ  ｗｏｒｄ  Ｔ−ｆｕｎｃｔｉｏｎ）である、請求項１２記載の擬似乱数生成装置。
【請求項１４】
第１、第２のレジスタと、
前記第１、第２のレジスタから第１、第２のデータを入力し、  請求項１２又は１３記載の擬似乱数生成装置の前記非線形変換手段又は前記転置手段から出力される複数のデータとともに、非線形変換を行う、別の非線形変換手段と、
を備え、
前記別の非線形変換手段から出力されるデータにて前記第１、第２のレジスタが更新されるとともに、前記データの一方は、鍵ストリームとして出力される、鍵ストリーム生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本願は、先の日本特許出願２００７−０８１７５５号（２００７年３月２７日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は、データの通信や蓄積の際にデータを秘匿するための暗号装置に関し、特に高速な暗号化ができるストリーム暗号および暗号用の乱数生成に適用して好適な装置、プログラム、方法に関する。
【背景技術】
【０００２】
＜ストリーム暗号の概要説明＞
データを秘匿するための手法として共通鍵暗号方式があり、ブロック暗号とストリーム暗号に大別することができる。【０００３】
典型的なストリーム暗号は、擬似乱数系列（鍵ストリーム）を生成する擬似乱数生成部（鍵ストリーム生成部）と、擬似乱数系列と平文を結合する結合部からなる。【０００４】
秘密鍵、もしくは秘密鍵と初期ベクトルをシードとして、擬似乱数系列を生成し、その擬似乱数系列を平文と排他的論理和して（結合部）、暗号文を生成する。【０００５】
復号する場合は、暗号化で使用したシードから擬似乱数系列を生成し、暗号文に排他的論理和して平文を得る。【０００６】
つまり、平文をＰ、暗号文をＣ、擬似乱数系列をＲ、排他的論理和を表す記号を（＋）とすると、
P (+) R = C
C (+) R = P
の関係となる。【０００７】
＜ストリーム暗号の安全性＞
ストリーム暗号は生成した擬似乱数系列を排他的論理和など簡単な処理で作用させることが多い。そのため、ストリーム暗号の安全性は、生成する擬似乱数系列の安全性に依存する。【０００８】
一般的に、ストリーム暗号に用いられる擬似乱数系列の性質としては、予測不可能性、統計的一様性、無相関性、長周期性、非線形性などが挙げられる。【０００９】
“真の乱数”は、周期がなく完全に無相関である。真の乱数は、サイコロを振ったり、自然現象を利用して生成するなどの方法で生成することができる。つまり、生成される擬似乱数系列が上記の性質を満たすならば、そのストリーム暗号は安全であるといえる。【００１０】
逆に、生成される擬似乱数系列が真の乱数と区別できるような情報を見つけることができれば、そのストリーム暗号は何がしかの安全性が低下していると考えられる。【００１１】
＜ストリーム暗号の安全性評価手法の一例＞
前述のような考え方に基づいて、ストリーム暗号の安全性を評価する手法がある。【００１２】
出力された暗号文や擬似乱数が、真の乱数と区別がつくことを示す暗号の攻撃手法を、Distinguishing Attackとよぶ。【００１３】
真の乱数との区別は、出力された暗号文や擬似乱数が、統計的な偏りや特徴を持っていることが示せれば、区別できたと判断する。【００１４】
Distinguishing Attackでは、このような偏りや特徴を示す手段を、Distinguisherと呼び、このような偏りや特徴を示す手段を発見したり作成したりすることを、Distinguisher を構成すると言う。【００１５】
Distinguisherが構成できるならば、Distinguishing Attackが適用できることになる。【００１６】
ある暗号に、Distinguishing Attackが適用できるならば、その暗号は平文または鍵や内部の情報を漏らしている可能性があることから、安全な暗号であるとはいえない。【００１７】
従って、Distinguishing Attackが適用できる暗号に修正を加え、Distinguishing Attackが適用出来なくなれば、暗号の安全性が向上したといえる。【００１８】
＜ストリーム暗号の具体例＞
ストリーム暗号の具体例としてMir-1がある。Mir-1は２００５年、Maximovによって提案され、eSTREAMに応募されたストリーム暗号である。【００１９】
Mir-1は、T-functionと呼ばれる関数で内部状態を更新し、その更新されたデータを時刻毎の鍵として利用し、秘密鍵依存でエントリが変化するＳ−ｂｏｘによる攪拌を利用して鍵ストリームを生成するストリーム暗号である。【００２０】
T-functionとは、2002年、KlimovとShamirが以下の論文（非特許文献２）で提案した暗号学的な基礎関数である。【００２１】
T-functionは、その内部状態を連結したデータが最長周期を持ちながら、最下位ビット以外は１次の線形関係式が成り立つというような代数的特性を持たない。【００２２】
また古くから、最長周期を保証できる処理として、線形フィードバックシフトレジスタ（LFSR）が知られている。LFSRによって更新されるデータは、全てのビットが1次の線形関係を持つという代数的特性がある。【００２３】
LFSRのもつ代数的特性を利用すると、内部データを連立方程式で表現し、その連立方程式を解くことで内部データを求める攻撃（Algebraic Attack）を適用できる可能性がある。【００２４】
よって、T-functionはストリーム暗号におけるLFSRの代わりとなる部品として期待されている。【００２５】
しかし、それ以降、T-functionを用いたストリーム暗号はいくつか提案されているが、いずれも、T-functionの特性を利用した解析によって、暗号としての安全性が十分でないことが報告されている。【００２６】
Mir-1は、将来主流となるであろう64ビットプロセッサで、高速かつ小メモリでの実装が可能となるよう考慮し、T-functionとS-boxを基本構造としたアルゴリズムを選択している。【００２７】
Mir-1では、LFSRの代わりに、T-functionを用いていることから、代数的攻撃への耐性が向上することが期待できる。【００２８】
＜発明が対象とする攻撃手法の要点＞
Mir-1は連続する３時刻分の出力データを用いて構成されるDistinguisherが真の乱数系列で構成されるDistinguisherと比べて高い確率で成立する。【００２９】
このDistinguisherにより、約2の10乗のデータ量で真の乱数系列と区別可能となる。【００３０】
＜攻撃手法の例示のための、Mir-1アルゴリズムの説明＞
Mir-1アルゴリズムを説明するにあたり、変数の表記や定義について説明する。【００３１】
ビット単位の排他的論理和、論理積、論理和をそれぞれ(+) 、&、｜と表記する。【００３２】
2の64乗を法とする加算、乗算をそれぞれ＋、・と表記する。【００３３】
1ワード（64ビット）の変数Xのtビット左ローテイトシフトを
X <<< t、または
ROLt(X)
と表記する。【００３４】
ワードXのバイト単位、ビット単位をそれぞれ以下のように定義する。ただし、‖はデータの連結を意味している。【００３５】
X = X.byte7 ‖ X.byte6 ‖ … ‖ X.byte0 = X.bit63 ‖ X.bit62 ‖ … ‖ X.bit0【００３６】
またワードXの第Mビットから第NビットまでをX[M,N]と定義する。上記の表現を用いると、
X[M,N] = X.bitN ‖ X.bit(N-1) ‖ … ‖ X.bit(M)
となる。【００３７】
Mir-1は、秘密鍵KEYが128ビット、初期ベクトルIVが64ビットであり、それぞれ以下のように表記する。【００３８】
KEY = k.byte15 ‖ k.byte14 ‖ … ‖ k.byte0
IV = IV.byte7 ‖ IV.byte6 ‖ … ‖ IV.byte0【００３９】
Mir-1の鍵ストリーム生成処理について説明する。【００４０】
Mir-1の鍵ストリーム生成処理は大きく、
Loop State Update（“LS Update”という）と
Automata State Update（“AS Update”という）
の２つのパートに分かれている。【００４１】
図５に、Mir-1のLS Updateのアルゴリズムを示す。図５に示すように、LS Updateは64ビットのレジスタxi（0≦i≦3）を４つ持ち、multi-word T-functionによってレジスタxiをそれぞれ更新する。【００４２】
LS Updateの出力256ビット（x0‖x1‖x2‖x3）は最長周期2の256乗が保証されている。【００４３】
図６に、Mir-1のAS Updateのアルゴリズムを示す。AS Updateは、64ビットのレジスタA、Bの２つを持ち、更新関数３１を用いて、A’、B’を計算する。A’、B’は、そのままA、Bとなる。【００４４】
このとき用いられるLS Updateからのレジスタ値は、それぞれ、(x0, x1, x2, x3)の上位3２ビットを連結した６４ビットデータであり、それぞれのワードを、
( x(i+2)[32,63] ‖ xi[32,63] )（i=0,1）
と表記する。【００４５】
以降、
x20 = ( x2[32,63]‖x0[32,63] )、
x31 = ( x3[32,63]‖x1[32,63] )
で表現する。【００４６】
Mir-1の鍵ストリーム生成処理では、時刻ごとに、LS UpdateとAS Updateを実行し、AS Updateで計算された64ビットのB'を鍵ストリームzとして出力する。【００４７】
次にMir-1の初期化処理について説明する。初期処理は鍵ストリーム生成処理に先立って行われる。【００４８】
Mir-1の初期処理は大きく分けて、Key Setupと、IV Setupの2つのパートに分かれている。【００４９】
図７に、Mir-1のKey Setupのアルゴリズムを示す。Key Setupでは、128ビットの秘密鍵を用いてレジスタxi（i = 0〜3）、およびレジスタA、Bを初期化する。ここで、C0、C1は、図５に示す定数である。【００５０】
Key Setupでは、最初に「secret S-box」と呼ばれる秘密鍵の値に応じて変化するS-boxを以下の式(1)で生成する。【００５１】
ここで、SR[・]は、AES (Advanced Encryption Standard) で使用されているS-boxを意味しており、i=0, … , 255までのエントリについてそれぞれ計算する。【００５２】
S-box[i] = SR[… SR[SR[i (+) k.byte0] (+) k.byte1] (+) … (+) k.byte15]                            ・・・  (1)【００５３】
図８に、Mir-1のIV Setupのアルゴリズムを示す。IV Setupは、64ビットの初期ベクトルを用いて、Key Setupで初期化されたレジスタxi（0≦i≦3）、およびレジスタA、Bを更新する。【００５４】
＜発明が対象とするMir-1攻撃手法 Distinguishing Attackの説明＞
Distinguishing Attackを適用するにあたり、Mir-1のIV Setupと、LS Updateにおいて成り立つ性質について説明する。ただし、Key Setupは、Distinguishing Attackには影響しない。【００５５】
まず、IV Setupの構造的性質について説明する。【００５６】
図８に示すように、IV Setupでは、64ビットのIVを、8ビットずつ8つ（IV.byte0〜IV.byte7）に分割し、それぞれを、secret S-boxで置換したデータを各レジスタに排他的論理和する。【００５７】
ここで、各バイトが同じ値のIVa = (a‖a‖ … ‖a)を与える場合を考える。【００５８】
排他的論理和の性質として、同じ値を排他的論理和すると結果は0になるので、結果的に、IV Setupで排他的論理和されるデータは、図９のようになる。図９は、IV Setupの性質を説明する図であり、IV Setupに、全バイト同じ値のIVが与えられた時に、各ワードによって全バイト同じデータが排他的論理和されるまたはIVの影響を受けないなどの問題が生じることを示す図である。【００５９】
図９に示すように、ステップ２では、レジスタ（x0, x1, x2, x3）はIVの影響を受けない。【００６０】
またステップ１、３でも、各レジスタxi.byte4（i=0〜3）,A.byte0, A.byte4, B.byte0, B.byte4に排他的論理和されるデータは全てS[a]という同じデータとなる。【００６１】
Secret S-boxのエントリは、秘密鍵依存のため未知であるが、全てのレジスタに同じ値が排他的論理和されることがわかる。【００６２】
次に、LS Updateの性質を説明する。【００６３】
Multi-word T-functionは、各ワードの第nビットは全ワードの第0〜nビットの影響しか受けない。【００６４】
ブロック暗号に対する差分解析のように、LS Update開始時のレジスタxi（i=0〜3）に排他的論理和の差分（「差分」と略記される）Δiを与えたとき、差分Δiの第0〜nビットが全てゼロ（差分がない）の場合、レジスタxiの第0〜nビットの差分は、LS Updateの実行回数によらず常にゼロ、つまり差分が発生しない。【００６５】
これは、LS Update（T-function）で行われる演算の影響が上位桁にしか波及しないためである。【００６６】
図９に示すとおり、LS Updateでは全バイトが同じ値のIVaを与えたとき、レジスタxi（i = 0〜3）の第0〜31ビットはIVの影響を受けない。【００６７】
よって、秘密鍵が固定の間（Key Setupの結果が同じ）は、全バイト同じ値という条件でIVaを変化させても、LS Updateの実行回数によらず、レジスタxiの第0〜31ビットには差分が生じない。【００６８】
＜選択IVを用いた差分攻撃＞
上記２つの性質を利用した解析方法を説明する。【００６９】
まず攻撃の条件として以下の３つが成り立つものとする。
・攻撃の間、秘密鍵は固定であるものとする。
・IVは攻撃者が自由に選択可能であるものとする。
・攻撃者は鍵ストリームを自由に入手可能であるものとする。【００７０】
まずIV Setupにおいて、全バイトが同じ値である【００７１】
Iva = (a‖a‖ … ‖a)
と、
IVb = (b‖b‖ … ‖b)
のペアで初期処理を行う。【００７２】
IVaを与えたときのレジスタをxai、
IVbを与えたときのレジスタをxbi
とすると、IVSetupの構造的性質から、xaiとxbi（i = 0〜3）の下位32ビットの差分はゼロとなる。【００７３】
xai[0,31] = xbi[0,31]  (i=0〜3)                 ・・・  (2)【００７４】
また図９のステップ１のように、レジスタxi.byte4にはそれぞれS[a]、S[b]が排他的論理和されるため、次式(3ａ)、(3b)のようになる（ただし、演算子(+)は排他的論理和を表す）。【００７５】
xai.byte4 = xi.byte4 (+) S[a]   (i=0〜3)       ・・・  （3a）【００７６】
xbi.byte4 = xi.byte4 (+) S[b]   (i=0〜3)        ・・・  (3b)【００７７】
このとき、secret S-boxのエントリは不明であるが、
S[a] & 0x1 = S[b] & 0x1 ・・・                  ・・・  (4)
を満たす場合、各レジスタxaiのビット32とxbiの第32ビットは以下の関係(5)を満たす。【００７８】
xai.bit32 = xbi.bit32  (i=0〜3)                ・・・  (5)【００７９】
よって、IV Setupにおいて、全バイトが同じ値であるIVaとIVbを与えたとき、式(4)の条件を満たしていれば、式(2)と式(5)より以下の式(6)を満たす。【００８０】
xai[0,32] = xbi[0,32]  (i=0〜3)                ・・・  (6)【００８１】
つまり、IVaとIVbで更新されるレジスタxiの下位33ビットの関係はそれぞれ差分がゼロとなる。【００８２】
LS Updateの性質からIV Setupおよび鍵ストリーム生成処理において、LS Updateの実行回数によらず式(4)の関係は必ず維持される。【００８３】
次に、式(4)の条件を満たしているという仮定の元、鍵ストリーム生成処理について考える。【００８４】
図１０は、AS Updateの更新について３時刻分の状態遷移を示した図である。【００８５】
時刻tにおけるデータXをX^(t)と表現する。【００８６】
AS Updateでは、2の64乗を法とする加算を用いているが、最下位ビットのみを解読に利用することによって排他的論理和に置き換えて考えることができる。【００８７】
図１１は、最下位ビットのみを考慮し、連続する３時刻の鍵ストリームを利用してDistinguisherを構成することを説明するための図であり、最下位ビットのみを考慮し、図１０における2の64乗を法とする加算を排他的論理和に置き換えた図である。【００８８】
次にdistinguisherの構成方法について説明する。【００８９】
IVaおよびIVbから生成される鍵ストリームをza、zbとする。【００９０】
また、IVaおよびIVbを与えたときのLS Updateから挿入されるデータを（xa20, xa31）、（xb20, xb31）とする。【００９１】
このとき、時刻tのsecret S-box出力ポジション（図１１の81）において最下位ビットに関する式を立てると、次式(7a)、(7b)のようになる。【００９２】
{ ROL29(za^(t-1)) (+) za^(t) (+) xa31^(t-1) (+) xa20^(t) (+) za^(t+1) }.bit0 = S[za^(t)].bit0                    ・・・  (7a)【００９３】
{ ROL29(zb^(t-1)) (+) zb^(t) (+) xb31^(t-1) (+) xb20^(t) (+) zb^(t+1) }.bit0 
= S[zb^(t)].bit0                  ・・・  (7b)【００９４】
ここで、式(5)より、以下の関係(8)、(9)を満たしている。【００９５】
xa20^(t).bit0 = xb20^(t).bit0            ・・・  (8)【００９６】
xa31^(t-1).bit0 = xb31^(t-1).bit0        ・・・  (9)【００９７】
またIVaおよびIVbから生成される鍵ストリームにおいて、
za^(t).byte0 = zb^(t).byte0             ・・・  (10)
を満たす時刻tを選択したとき、secret S-boxのエントリは不明であっても、入力が同じためsecret S-boxの出力も同じとなり以下の関係を満たす。【００９８】
S[za^(t)] = S[zb^(t)]                  ・・・  (11)【００９９】
よって、式(8)〜式(11)を考慮すると、以下の関係式(12)が成り立つ。【０１００】
{ ROL29(za^(t-1) (+) zb^(t-1)) (+) za^(t+1) (+) zb^(t+1) }.bit0 = 0                                   ・・・  (12)【０１０１】
まとめると、任意に与えたIVaとIVbのペアにおいて式(4)を満たしているとき、式(10)が成り立つ時刻tにおいて、式(12)が常に成り立つ。【０１０２】
次に、式(12)がDistinguisherとして利用できることを説明する。【０１０３】
＜Distinguisherが成り立つ確率と必要なデータ量＞
ここでは、Distinguisherとして利用する式(12)の成立確率について説明する。【０１０４】
もしMir-1の出力する鍵ストリームが真の乱数系列であれば、Distinguisherである式(12)が成り立つ確率は1/2となる。【０１０５】
以降では異なるIVによって更新される内部状態、および鍵ストリームは独立であり一様に分布する、という仮定のもと議論を進める。【０１０６】
まず式(10)を満たす確率は、2の-8乗となる。ただし、鍵ストリームは攻撃者にとって既知の値となるため選択可能であり、常に式(10)を満たすことが可能である。【０１０７】
次に、式(4)を満たす確率は、ランダムに選択されたsecret S-boxエントリの最下位ビットが一致する確率であり1/2となる。【０１０８】
ここで式(4)を満たさない時、式(12)が成り立つ確率を理想的に1/2と仮定すると、Mir-1の出力系列において式(12)が成り立つ確率Pdは、
Pd = 1×1/2 + 1/2(1-1/2)
= 1/2(1+1/2)                              ・・・  (13)
となる。【０１０９】
よって真の乱数系列における確率1/2と比べて大きくなる。【０１１０】
次に、式(12)をdistinguisherとしたとき、Mir-1の出力系列と真の乱数系列を区別するために必要なデータ量を検討する。【０１１１】
非特許文献３（I. Mantin, and A. Shamir: "A Practical Attack on Broadcast RC4,"Fast Software Encryption, FSE 2001, LNCS 2355, pp.152-164,Springer-Verlag, 2001.）によると、2つの分布を区別するのに必要なデータ量は以下のようになることが示されている。【０１１２】
確率pで発生する事象分布Xと、確率p(q+1)で発生する事象分布Yにおいて、あるイベントeが生じる時、無視できない成功確率でXとYを区別するには、O(1/(p・qの2乗))のサンプルが必要である。【０１１３】
ただし、上記の定理はpが十分小さいとき成り立つ定理である。【０１１４】
非特許文献４（S. Paul, B. Preneel, and G. Sekar: "Distinguishing Attacks on the Stream Cipher Py,"eSTREAM, the ECRYPT Stream Cipher Project, Report 2005/081, 2005.）には、p=1/2のときには、2つの分布を区別するのに必要なデータ量は以下のようになることが示されている。【０１１５】
確率p = 1/2で発生する事象分布Xと、確率1/2(q+1)で発生する事象分布Yにおいて、あるイベントeが生じる時、無視できない成功確率でXとYを区別するには、O(1/(qの2乗))のサンプルが必要である。【０１１６】
先に述べたDistinguisherを使用した解読におけるイベントeは、式(12)が成り立つ事象であり、乱数におけるイベントeの分布をX、Mir-1の出力系列におけるイベントeの分布をYとみなすことができる。【０１１７】
よって、p=1/2、q=1/2と考えることができるため、解読に必要なデータ量はO(2の2乗)となる。【０１１８】
ここで、式(10)を満たす鍵ストリームを選択することを考慮に入れると、解読に必要なデータ量Tは、
T = 2の8乗 × O(2の2乗)
= O(2の10乗)                      ・・・  (14)
となる。【０１１９】
よって、選択IV攻撃を適用することで、理論的に、約2の10乗ワードの鍵ストリームを利用するとMir-1の出力系列と真の乱数列との区別が可能である。【０１２０】
【非特許文献１】A. Maximov,"A New Stream Cipher "Mir-1,"ECRYPT Stream Cipher Project, Report 2005/017, 2005.
【非特許文献２】A. Klimov, and A. Shamir,"A New Class of Invertible Mappings,"CHES'02, LNCS 2523, pp.470-480, Springer Verlag, 2002.
【非特許文献３】I. Mantin, and A. Shamir: "A Practical Attack on Broadcast RC4,"Fast Software Encryption, FSE 2001, LNCS 2355, pp.152-164,Springer-Verlag, 2001.
【非特許文献４】S. Paul, B. Preneel, and G. Sekar: "Distinguishing Attacks on the Stream Cipher Py,"eSTREAM, the ECRYPT Stream Cipher Project, Report 2005/081, 2005.
【発明の開示】
【発明が解決しようとする課題】
【０１２１】
以上の非特許文献１〜４の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下に本発明による関連技術の分析を与える。
Mir-1の出力系列は、式(12)をDistinguisherとしたときの攻撃手法によって鍵ストリームが高い確率で真の乱数列との区別が可能であり、このため安全性が低い、という課題がある。【０１２２】
したがって、本発明の目的は、例えばMir-1等のストリーム暗号におけるDistinguisherの構成を困難にし、かつMir-1がもつ速度性能の低下をきたさない暗号装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【０１２３】
本願で開示される発明は、前記課題を解決するため、概略以下の構成とされる。【０１２４】
本発明は、ストリーム暗号に用いられる擬似乱数生成装置であって、１個以上の内部状態を有し、前記内部状態に保存されている数値データを更新する非線形変換手段と、前記非線形変換手段で更新された数値データに対して、予め定められたルールに基づいてビット転置を行う転置手段と、を備えている。【０１２５】
本発明において、内部状態の更新は、擬似乱数列の出力ごとに行われる。あるいは、内部状態の更新は、擬似乱数列の出力よりも多く行われる。あるいは、内部状態の更新は、擬似乱数列の出力よりも少なく行われる。【０１２６】
本発明において、前記ビット転置のルール付けを、予め定められたテーブルの値に従って変更する。
【発明の効果】
【０１２７】
本発明によれば、例えばMir-1等のストリーム暗号におけるDistinguisherの構成を困難にするとともに、速度性能の低下をきたすことはない。
【図面の簡単な説明】
【０１２８】
【図１】本発明の一実施形態の手順を示すフローチャートである。
【図２】本発明の一実施例の構成を示す図である。
【図３】本発明の一実施例における転置手段の一例を示す図である。
【図４】本発明の一実施例の動作の一例を示す図である。
【図５】Mir-1 LS Updateのアルゴリズムを示す図である。
【図６】Mir-1 AS Updateのアルゴリズムを示す図である。
【図７】Mir-1 Key Setupのアルゴリズムを示す図である。
【図８】Mir-1 IV Setupのアルゴリズムを示す図である。
【図９】IV Setupの性質を説明する図である。
【図１０】連続した３時刻分のAS Updateの状態遷移を示す図である。
【図１１】Distinguisherの構成を示す図である。
【符号の説明】
【０１２９】
１１  内部状態
１２  非線形変換手段
１３  転置手段
３１  更新関数
８１  S-box出力ポジション
９０、９４、９０１、９０２、９０３、９０４、９４１、９４２  内部状態
９１、９５  非線形変換手段
９２  セレクタ
９３、９３１、９３２、９３３、９３４  転置手段
９６、９７  処理  
１１１  Key  Setup
１１２  セレクタ切替
１１３  IV  Setup
１１４  セレクタ切替
１１５  鍵ストリーム生成処理
９２１〜９２８  セレクタ出力
【発明を実施するための最良の形態】
【０１３０】
図１は、本発明の一実施形態の構成を示す図である。本発明は、「選択ＩＶを用いた差分攻撃」を適用できなくするものである。具体的には、IV Setupにおいて、内部状態１１を、T-functionである非線形変換手段１２で更新したあとに、あるルールに基づいたビット転置を行う転置手段１３を有する。【０１３１】
本実施形態においては、このような転置手段１３を用いることによって、T-functionにおける第ｎビットは、第０〜ｎビットの影響しか受けない、という性質を消すことができる。【０１３２】
つまり、内部状態の各ワードの第ｎビットは、全ワードの第ｎビットよりも上位のビットからの影響を受けるため、「選択ＩＶを用いた差分攻撃」が実質的に適用出来なくなる。【０１３３】
よって、本発明により、従来のＭｉｒ−１の出力系列が高い確率で真の乱数列との区別が可能であり安全性が低いという課題を解決できる。【０１３４】
図２は、図１に示した本発明の一具体例（実施例）の構成を示す図である。図２に示すように、本実施例は、内部状態９０、９４、非線形変換手段９１、９５、セレクタ９２、転置手段９３を有する。内部状態９０は４つの内部状態（レジスタ）９０１〜９０４を有する。転置手段９３は、４つの転置手段９３１〜９３４を有する。セレクタ９２は、非線形変換手段９１からの４つの出力データを、内部状態９０１〜９０４又は転置手段９３１〜９３４に供給する。内部状態９４は２つの内部状態（レジスタ）９４１〜９４２を有する。【０１３５】
内部状態９０に保持されている数値データを、非線形変換手段９１に入力して非線形変換を行う。【０１３６】
非線形変換手段９１は、例えばmulti-word T-function（図５参照）に相当する。【０１３７】
非線形変換手段９１から出力されたデータは、セレクタ９２によって処理が制御される。【０１３８】
セレクタ出力９２１、９２３、９２５、９２７が選択されているとき、データは内部状態９０に戻され、保持される。【０１３９】
セレクタ出力９２２、９２４、９２６、９２８が選択されているとき、データは、転置手段９３に入力される。【０１４０】
本実施例において、転置手段９３は、図３に示したビット転置処理を行う。すなわち、６４ビットの各データを、上位８ビットと下位５６ビットに分割し、上位８ビットが別のワードの下位８ビットに配置されるようなビット転置を行う。【０１４１】
例えばx0の場合、
x0の上位8ビット（x0[56,63]）がx1の下位8ビットに、
x0の下位56ビット（x0[0,55]）がx0の上位56ビットに
配置されるように、ビット転置を行う。【０１４２】
ビット転置処理されたデータは、内部状態９０に戻されて保持される。【０１４３】
一方、内部状態９４１、９４２に保持されているデータは、非線形変換手段９５に入力され、非線形変換手段９１又は転置手段９３から出力されたデータと共に、非線形変換される（図６の更新関数３１の処理に対応）。【０１４４】
非線形変換手段９５で変換されたデータは、内部状態９４１、９４２に戻され、保持される。このとき、内部状態９４２に戻されるデータを、鍵ストリームとして出力する。【０１４５】
前述した従来の手法は、Mir-1の初期処理（LS UpdateとIV Setup）の性質を利用した手法である。本実施例では、鍵ストリームを生成する処理（AS Update）には、この従来手法に変更を施さない。【０１４６】
以下では、初期処理に、本発明を適用した一具体例について、図４を参照して説明する。【０１４７】
Key Setupステップ１１１は、図７に示したMir-1のKey Setupから変更はない。ここで、図２との対応は、x0〜x3が内部状態９０、A、Bが内部状態９４となる。【０１４８】
図２の９６の処理が、LS Update、９７の処理は、AS Updateに対応する。このとき、セレクタ９２は、転置処理９３を行わないようにセットされる（セレクタ切替１１２）。【０１４９】
図２において、非線形変換手段９１は図５に対応し、転置手段９３は図３に対応し、非線形変換手段９５は図６に対応する。【０１５０】
以上の処理で、秘密鍵を入力として、内部状態の更新を行う。このとき、鍵ストリームは出力しない。【０１５１】
次に、IV Setupステップ１１３では、ＩＶの挿入方法を、図８から、次式(15)のように変更する。【０１５２】
x0 = x0 (+) S[IV]x1
= x1 (+) S[ROL16(IV)]x2 
= x2 (+) S[ROL32(IV)]x3 
= x3 (+) S[ROL48(IV)]
・・・  (15)【０１５３】
S[X]はデータXをバイト単位でS-box参照する。【０１５４】
つまり
S[X] = S-box[X.byte7]‖S-box[X.byte6]‖…‖S-box[X.byte0]
・・・  (16)
を意味している。【０１５５】
ＩＶの挿入後、セレクタ９２は、転置処理９３を行うようにセットされ、図２の処理を２回行う。このとき、鍵ストリームは出力しない。【０１５６】
そして、セレクタ９２は、再度、転置処理９３を行わないようセットされ（セレクタ切替１１４）、鍵ストリーム生成処理１１５に移行する。【０１５７】
鍵ストリーム生成処理１１５では、必要な鍵ストリームが得られるまで、図２の処理を繰り返し行う。【０１５８】
図４に示した実施例により、得られる作用効果を以下に説明する。【０１５９】
まず、IV Setupステップ１１３の変更により、全バイト同じ値となるIVを与えたとしても、内部状態の各ワードに必ず差分が入る、つまり入力差分を打ち消すようなIVを与えることが出来ない。【０１６０】
また、図２の転置手段９３によって、内部状態に入る差分のバイト位置も、１６ビットずつずれるため、処理９６によって、下位側のバイトからの差分攪拌効果が期待できる。【０１６１】
また、この変更を行ったとしても、８ビット単位でのＳ−ｂｏｘの参照回数および排他的論理和の実行回数に変更が無いため、処理速度の劣化はない。【０１６２】
また、６４ビットプロセッサをターゲットとした暗号アルゴリズムであることを考えると、排他的論理和は６４ビット変数のまま実行できるため、処理速度の向上が期待できる。【０１６３】
次に、転置手段９３の追加により、全バイト同じ値となるような選択ＩＶを与えたとしても、内部状態９０のバイト４に挿入された差分が非線形変換手段９１の処理によって上位側に波及し、その差分効果が転置手段９３よって下位側および隣のワードに波及する。【０１６４】
よって、全バイト同じ値となるような選択IVを与えたとしても、内部状態９０の更新において確率1で差分ゼロが伝播することは発生しない。【０１６５】
また図３の処理は、２の256乗→2の256乗の全単射な写像であり、IV Setupの終了直後の値としてＩＶのパタン２の６４乗のバリエーションが保証できる。【０１６６】
これにより、T-functionの最長周期を保証するという特徴も鍵ストリーム生成処理においては影響しない。ただし、実装性の観点で処理速度が若干劣化するが、６４ビットプロセッサをターゲットとした暗号アルゴリズムであることを考えれば、それほど大きな劣化はないと考えられる。【０１６７】
以上詳細に説明したように、本発明によれば、データの通信や蓄積の際にデータを秘匿するための安全性の高い暗号装置を得ることができる。かつ元来の暗号が有していた速度性能の低下をきたさない暗号装置の提供も可能となる。【０１６８】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
以上本発明を上記実施例に即して説明したが、本発明は、上記実施例にのみ限定されるものではなく、本願特許請求の範囲の各請求項の発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。
【図１】
2008117804.tif 000003
【図２】
2008117804.tif 000004
【図３】
2008117804.tif 000005
【図４】
2008117804.tif 000006
【図５】
2008117804.tif 000007
【図６】
2008117804.tif 000008
【図７】
2008117804.tif 000009
【図８】
2008117804.tif 000010
【図９】
2008117804.tif 000011
【図１０】
2008117804.tif 000012
【図１１】
2008117804.tif 000013
【手続補正書】
【提出日】平成20年12月2日(2008.12.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ストリーム暗号に用いられる擬似乱数生成装置であって、
少なくとも１つの内部状態と、
前記内部状態に保存されている数値データを更新する非線形変換手段と、
前記非線形変換手段で更新された数値データに対して、予め定められたルールに基づいてビット転置のみを行う転置手段と、
を備えたことを特徴とする擬似乱数生成装置。
【請求項２】
前記内部状態の更新が、擬似乱数列の出力よりも多く行われる、ことを特徴とする請求項１に記載の擬似乱数生成装置。
【請求項３】
（削除）
【請求項４】
（削除）
【請求項５】
ストリーム暗号に用いられる擬似乱数を生成するプログラムであって、
少なくとも１つの内部状態に保存されている数値データを更新する非線形変換処理と、
更新された数値データに対して、予め定められたルールに基づいて、ビット転置のみを施す転置処理と、
をコンピュータに実行させるプログラム。
【請求項６】
前記内部状態の更新が、擬似乱数列の出力よりも多く行われる、ことを特徴とする請求項５に記載のプログラム。
【請求項７】
（削除）
【請求項８】
請求項５又は６に記載のプログラムを記録したコンピュータが読みとり可能な記録媒体。
【請求項９】
ストリーム暗号に用いられる擬似乱数を生成する方法であって、
少なくとも１つの内部状態に保存されている数値データを更新する非線形変換工程と、
更新された数値データに対して、予め定められたルールに基づいて、ビット転置のみを施す転置工程と、
を含むことを特徴とする擬似乱数生成方法。
【請求項１０】
前記内部状態の更新が、擬似乱数列の出力よりも多く行われる、ことを特徴とする擬似乱数生成方法。
【請求項１１】
（削除）
【請求項１２】
所定ビット幅のデータを保持するレジスタを複数備え、
前記複数のレジスタに保持されている複数のデータを入力して非線形変換を行う非線形変換手段と、
前記非線形変換手段で変換された複数のデータを入力し、各データを上位、下位ビットに分割し、一のデータの上位ビットが別のデータの下位ビットに配置されるようなビット転置を行う転置手段と、
前記非線形変換手段と前記転置手段との間に配設され、前記非線形変換手段から出力される複数のデータを、前記転置手段に供給するか、又は前記複数のレジスタへ戻す選択を行うセレクタと、
を備え、
前記転置手段から出力される、ビット転置された複数のデータは、前記複数のレジスタに戻されて保持される、擬似乱数生成装置。
【請求項１３】
前記非線形変換手段が、マルチワードＴ−ファンクション（ｍｕｌｔｉ  ｗｏｒｄ  Ｔ−ｆｕｎｃｔｉｏｎ）である、請求項１２記載の擬似乱数生成装置。
【請求項１４】
第１、第２のレジスタと、
前記第１、第２のレジスタから第１、第２のデータを入力し、
請求項１２又は１３記載の擬似乱数生成装置の前記非線形変換手段又は前記転置手段から出力される複数のデータとともに、非線形変換を行う、別の非線形変換手段と、
を備え、
前記別の非線形変換手段から出力されるデータにて前記第１、第２のレジスタが更新されるとともに、前記データの一方は、鍵ストリームとして出力される、鍵ストリーム生成装置。
【請求項１５】
所定ビット幅のデータを保持するレジスタを複数備えたコンピュータに、前記複数のレジスタに保持されている複数のデータを入力して非線形変換を行う非線形変換処理と、
前記非線形変換処理で変換された複数のデータを入力し、各データを上位、下位ビットに分割し、一のデータの上位ビットが別のデータの下位ビットに配置されるようなビット転置を行う転置処理であって、前記ビット転置された複数のデータは前記複数のレジスタに戻されて保持される転置処理と、
前記非線形変換処理と前記転置処理との間に配設され、前記非線形変換処理から出力される複数のデータを、前記転置処理に供給するか、又は前記複数のレジスタへ戻す選択を行う選択処理と、
を実行させるプログラム。
【請求項１６】
前記非線形変換処理が、マルチワードＴ−ファンクション（ｍｕｌｔｉ  ｗｏｒｄ  Ｔ−ｆｕｎｃｔｉｏｎ）である、請求項１５記載の擬似乱数生成プログラム。
【請求項１７】
第１、第２のレジスタを備えたコンピュータに、
前記第１、第２のレジスタから第１、第２のデータを入力し、請求項１５又は１６記載のプログラムの前記非線形変換処理又は前記転置処理から出力される複数のデータとともに、非線形変換を行う、別の非線形変換処理と、
前記別の非線形変換処理から出力されるデータにて前記第１、第２のレジスタを更新するとともに、前記データの一方を、鍵ストリームとして出力する処理を実行させる鍵ストリーム生成プログラム。
【請求項１８】
請求項１５乃至１７のいずれか一に記載のプログラムを記録したコンピュータが読みとり可能な記録媒体。
【請求項１９】
所定ビット幅のデータを保持する複数のレジスタに保持されている複数のデータを入力して非線形変換を行う非線形変換工程と、
前記非線形変換工程で変換された複数のデータを入力し、各データを上位、下位ビットに分割し、一のデータの上位ビットが別のデータの下位ビットに配置されるようなビット転置を行う転置工程と、
前記非線形変換工程と前記転置工程との間に配設され、前記非線形変換工程から出力される複数のデータを、前記転置工程に供給するか、又は前記複数のレジスタへ戻す選択を行う選択工程と、
を含み、前記転置工程から出力される、ビット転置された複数のデータが、前記複数のレジスタに戻されて保持される、ことを特徴とする擬似乱数生成方法。
【請求項２０】
前記非線形変換工程が、マルチワードＴ−ファンクション（ｍｕｌｔｉ  ｗｏｒｄ  Ｔ−ｆｕｎｃｔｉｏｎ）である、請求項１９記載の擬似乱数生成方法。
【請求項２１】
第１、第２のレジスタから第１、第２のデータを入力し、請求項１９又は２０記載の擬似乱数生成方法の前記非線形変換工程又は前記転置工程から出力される複数のデータとともに、非線形変換を行う、別の非線形変換工程を有し、
前記別の非線形変換工程から出力されるデータにて前記第１、第２のレジスタが更新されるとともに、前記データの一方は、鍵ストリームとして出力される、鍵ストリーム生成方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
部状態を有し、前記内部状態に保存されている数値データを更新する非線形変換手段と、前記非線形変換手段で更新された数値データに対して、予め定められたルールに基づいてビット転置のみを行う転置手段と、を備えている。
［０１２５］
本発明において、内部状態の更新は、擬似乱数列の出力よりも多く行われる。
［０１２６］
本発明において、前記ビット転置のルール付けを、予め定められたテーブルの値に従って変更する。
発明の効果
［０１２７］
本発明によれば、例えばＭｉｒ−１等のストリーム暗号におけるＤｉｓｔｉｎｇｕｉｓｈｅｒの構成を困難にするとともに、速度性能の低下をきたすことはない。
図面の簡単な説明
［０１２８］
［図１］本発明の一実施形態の手順を示すフローチャートである。
［図２］本発明の一実施例の構成を示す図である。
［図３］本発明の一実施例における転置手段の一例を示す図である。
［図４］本発明の一実施例の動作の一例を示す図である。
［図５］Ｍｉｒ−１  ＬＳ  Ｕｐｄａｔｅのアルゴリズムを示す図である。
［図６］Ｍｉｒ−１  ＡＳ  Ｕｐｄａｔｅのアルゴリズムを示す図である。
［図７］Ｍｉｒ−１  Ｋｅｙ  Ｓｅｔｕｐのアルゴリズムを示す図である。
［図８］Ｍｉｒ−１  ＩＶ  Ｓｅｔｕｐのアルゴリズムを示す図である。
［図９］ＩＶ  Ｓｅｔｕｐの性質を説明する図である。
［図１０］連続した３時刻分のＡＳ  Ｕｐｄａｔｅの状態遷移を示す図である。
［図１１］Ｄｉｓｔｉｎｇｕｉｓｈｅｒの構成を示す図である。
符号の説明
［０１２９］
１１  内部状態
１２  非線形変換手段
１３  転置手段
３１  更新関数
【国際調査報告】
2008117804.tif 000014
2008117804.tif 000015
2008117804.tif 000016
2008117804.tif 000017
2008117804.tif 000018