暗号アルゴリズムの詳細評価
1. 評価対象暗号アルゴリズム
項番
1暗号アルゴリズム
MULTI-S01

分類
ストリーム暗号

暗号アルゴリズムの応募元
株式会社日立製作所

2. 評価項目・ 周期、線形複雑度、相互情報量
・ 統計的性質（1/0 等頻度性、連、一様性）
3. 評価方法及び評価結果
評価対象暗号アルゴリズムに対して、上記 6項目の評価を行なった。その際に共通な測定条件を次に示す。

秘密鍵

乱数列番号

K
Q

擬似乱数
生 成 器
A, B, S

測定条件と測定項目：
MULTI-S01 暗号はストリーム暗号であり、図１に示される手順で暗号化される。したがって、

冗長性

M

メッセージ
暗号R文

暗号化用
攪拌関数

C

擬似乱数生成器からの出力系列の乱数性と、メッセージ系列 M と冗長性 R を既知とした場合、

図 1．暗号化ブロック図つまりそれぞれの値を零としたときの暗号用攪拌関数の入出力における相関について評価を行なった。
擬似乱数生成器からの出力系列の乱数性：
・周期 ・線形複雑度 ・相関値 ・1/0 等頻度性 ・連 ・一様性
暗号用攪拌関数の入出力における相関性：
・擬似乱数生成器からの入力と暗号文としての出力との相関
・メッセージ系列と暗号文としての出力との相関
擬似乱数生成器の入力と対象とするメッセージのサイズ：
MULTI-S01 暗号の擬似乱数生成器への入力は秘密鍵 K (256 ビット)と乱数列番号 Q (256 ビット)であるので、擬似乱数生成器の乱数性評価は、まず K と Q を零とした評価データを取り、次に K と Qのそれぞれに一様乱数を用いて 100 回の試行を行なった。また、暗号対象のメッセージの長さを考慮して最大値を 10M として、他に 1K, 10K, 100K, 1M の長さで評価データを取っている。
K と Q を零とした評価データは、添付 Excel データの最上段 0 行（黄色）で与える。その下の段 1〜100 行を一様乱数を用いた 100 回の試行による評価データとする。ただし、連と周期の評価データは除く。

単位と擬似乱数生成器のレジスタの規格：評価を与える前に、仕様書中で定義される共通の単位を示す。
1 ワード ＝ 32 ビット

1 ステージ ＝ 8 ワード ＝ 256 ビット①. 周期
擬似乱数生成器から得られる乱数列の計算機シュミレーションによる周期の計測は時間的にブロック B
レジスタ bFeedback 関数

難しい為、仕様書をもとに理論的に考察する。
ブロック A

擬似乱数生成器は、2 つのレジスタ

非線型変換 ρa レジスタ： 17 ワード （ワード単位）

レジスタ ab レジスタ： 32 ステージ （ステージ単位）の組み合わせで構成され、pull モードと呼ばれ擬似乱数系列る定常状態では図 2 に示すようにデータの受け図 2．擬似乱数生成器ブロック図渡しが行なわれている。したがって、この擬似乱数生成器をブロック A とブロック B の独立な構成として、それぞれの周期 NA と NB を求める。

擬似乱数系列の相関値
12001000
擬似乱数系列相関値

8006004002000-2000200400600
系 列 長8001000

図 3．擬似乱数系列の自己相関値

ブロック A： a レジスタでは、1 ワードを単位として 17 段のレジスタが構成され、非線型変換ρによってその内容が更新されている。このとき、変換ρは 4 種類の変換γ, π, θ, σの合成関数として構成されているので、a レジスタ以外からの入力を零と仮定し、それぞれの変換による a レジスタの周期 Nγ,Nπ, Nθ, Nρ,を求めた[参考資料(周期)]。
• 変換γ ：γ (a i ) = a i ⊕ (a i +1 mod 17 or ( NOT a i + 2 mod 17 )) 0 ≤ i ≤ 17

初期値によって、2〜78812 の幅広い周期分布を持つ。

• 変換π ：π (a i ) = ROTL i(i +1)/2 mod 32 (a 7 i mod 17 ) 0 ≤ i ≤ 17

Nπ=1088 となる。
• 変換θ ：

θ (ai ) = ai ⊕ ai +1 mod 17 ⊕ ai + 4 mod 17 0 ≤ i ≤ 173〜6551 まで、幅広い周期分布を持つ。(ただし、ALL-0 のときは 1)• 変換σ ：σ (a0 ) = a 0 ⊕ 1σ (a i +1 ) = a i +1 ⊕ l i 0 ≤ i < 8σ (ai +9 ) = ai ⊕ bi16 0 ≤ i < 8

a レジスタ以外からの入力なので、無視する。
ブロック B： b レジスタは、1 ステージを単位としたレジスタで構成され、フィードバック値のシフト・ローテーションで長周期化を行なっている。このとき、シフト・ローテーションを除く部分のフィードバッ
ク関数は次式となり、長周期の擬似乱数生成する。

x 32 + x 25 + 1 = ( x 2 + x + 1)( x 30 + x 29 + x 27 + x 26 + x 24 + x 22 + x 21 + x 19 + x 18+ x 16 + x 15 + x 13 + x 12 + x 10 + x 9 + x 7 + x 6 + x 4 + x 2 + x + 1)
また、シフト・ローテーションの周期は 4 である。
以上、複数の関数の組み合わせで生成されるため、擬似乱数の周期については非常に予測し難い。
また、数千回の自己相関評価では、周期 220 よりも小さな相関は確認されていない。
②. 線形複雑度
線形複雑度は、擬似乱数系列の予測し難さ・解読し難さの評価尺度であるが、その値だけでは評価として不十分である。したがって、ここでは周期に対する線形複雑度の他に Profile についても測定を行なった。Profile による評価は、線形複雑度の増加の回数として評価している。ここで、線形複雑度は、解読し難さの面から、系列長に対して 1/4 の割合で増加することが望ましいとされている。
評価結果については、参考資料(線形複雑度)に示す。評価は、Length： 生成された系列長
LC： 長さ Length の擬似乱数系列の線形複雑度（系列長を 1 として規格化した値）
No. of Steps： 長さ Length の擬似乱数系列 Profile で、線形複雑度が増加した回数（系列長を 1 として規格化した値）として示す（Profile の様子を図 4 に示す）。

LC および No. of Steps の評価結果より、Multi-S01 で用いられる擬似乱数生成器は、線形複雑度の評価において理想的な結果が得られた。今回、時間的制約もあり、M バイト単位のメッセージに対する擬似乱数生成器評価は行なってないが、周期が M バイトを超えることを考慮すると、M バイト単位の線形複雑度による評価が極端に悪くなることは予想し難い。

Profile (線形複雑度)
600

線形複雑度

500
400300200100
擬似乱数系列0020040060080010001200系 列 長
図 4．擬似乱数系列の Profile③. 相互情報量
暗号化処理のデータ攪拌武において、メッセージ M と冗長性 R を零として、擬似乱数生成器から出力される 2 元系列と暗号文 C の 2 進数表現による相関から得られる相互情報量を評価データとして参考資料（相互情報量）に示す。また、一様乱数を用いて得られたメッセージ M と暗号分 C との相互相関値(相関区間：N=1000)としても参考資料（相互相関）で与えている。相関結果については、各位相の相互相関値からの平均・分散・最小値・最大値で与える。
相互情報量および相互相関値の評価結果から、相互情報量は 1 に近い値を取るので一致するビットと一致しないものが等頻度となり、暗号結果からの擬似乱数系列の予測は難しい。また、相互相関値も低くいことからも、同じ事が言える。
④. 統計的性質（1/0 等頻度性）
擬似乱数生成器から出力される系列を 2 進数で表現したとき、0 と 1 の出現回数を平均と分散で与える。ただし、系列長を 1 として規格化した値とする。

1/0 等頻度性の評価結果は、参考資料（1/0 等頻度性）から 1 と 0 とが、ほぼ等頻度で出現することが分かる。
⑤. 統計的性質（連）100 回の試行により、擬似乱数系列の連の分布を平均で与える（参考資料（連））。

評価結果より、最も長い連(長さ L)の出現回数を１として、長さ L-1 の連の出現回数は 2、長さ L-iの連の出現回数はほぼ 2i となっており、理想的な結果が得られた。
⑥. 統計的性質（一様性）
一様性の評価は、擬似乱数系列からの出力系列を 2i 進数(i=1,2,3,4)表現として、その出現分布により評価した。ただし、系列長を 1 として規格化した値とする。評価結果は、参考資料(1/0 等頻度性、一様性(2^2)、一様性(2^3)、一様性(2^4))で与える。
評価結果から、1/0 等頻度性の評価を含め、2i 進数(i=1,2,3,4)表現における出現分布から一様性が高いことが分かる。
4. まとめ
評価時間制約から、擬似乱数生成器で出力される系列の周期については、評価の点で不十分な面もあるが。評価対象暗号アルゴリズム MULTI-S01 の安全性については、非常に高い結果が得られた。