Miyaji Laboratory

RC4は多くの商用アプリケーションや標準プロトコルで使用されている．そこで，RC4の解読法を研究することにより，RC4 の安全性を評価することを本研究の目的とする．網代らは，PRGAの初期内部状態が2 bytes のみ異なる内部状態を作り出す秘密鍵のペア（擬似等価鍵）が存在する時，出力を観測することによりPRGAの初期内部状態の一部をランダムより高い確率で推定できるという脆弱性が発見した．さらに，松井は擬似等価鍵の存在を理論的に示した．これらより，ある秘密鍵のペアを使っていた場合，出力を観測することにより，PRGAの初期内部状態の一部が推測できるという脆弱性が発見された．PRGAの初期内部状態が全て推測できた時，RC4の出力が導出できるため，平文との排他的論理和により暗号文が解読されてしまう．本研究では，解読に使える秘密鍵のペアを増やすために，PRGAの初期内部状態がn箇所転置された内部状態を考える．具体的には，網代らの解析手法を内部状態が1 箇所転置状態の解析と捉え，これを拡張することによりPRGA 初期内部状態復元アルゴリズムを提案する．