JP2004363739A - 改竄検知可能な、共通鍵暗号の暗号化装置または復号化装置 - Google Patents

Abstract

【課題】従来の暗号技術では，復号の際，改ざん検出を行おうとする，異なるふたつの鍵共有の必要性，メッセージの２倍となる乱数の必要性，独立の処理，別の暗号学的要素関数の追加実装などが必要であった。
【解決手段】乱数を生成して暗号化と認証処理を行い，事前計算と並列計算を達成する。また，生成する乱数の長さは，メッセージ長Ｎに対して２Ｎより少ない乱数を用いて，暗号処理と認証処理を行う。具体的には，疑似乱数生成器を使って乱数を生成しそれらをブロック毎に分割する。また平文もブロック毎に分割する。乱数ブロックと平文ブロックを排他的論理和し暗号文ブロックを得る。ハッシュ関数ＮＨは，乱数ブロックを鍵入力とし，生成された暗号文のメッセージ認証子を生成する。乱数生成は事前計算可能であり，暗号文ブロック生成演算は並列処理可能であり，ハッシュ関数ＮＨも並列処理可能であるため，高速計算ができる。
【選択図】図１

Description

【０００１】
【発明の属する技術分野】
本発明は，秘密情報のセキュリティを確保する技術に関する。
【０００２】
【従来の技術】
従来の暗号処理装置は，データを秘匿する目的のブロック暗号やストリーム暗号が提案されていた。ブロック暗号にはＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）を始め，いろいろなアルゴリズムが提案されている。
【０００３】
ブロック暗号はＥＣＢ，ＣＢＣ，ＣＦＢ，ＯＦＢ，カウンタモードなどのブロック暗号操作モードにより全体の暗号処理の安全性や性質を議論するが，これまでに暗号化処理と改ざん検出を同時に行う操作モードは，ｉａＰＣＢＣモードが知られているだけで，残りのモードは改ざんの検出がそれ自身では不可能である。ｉａＰＣＢＣモードは非特許文献１で扱っている。
【０００４】
ｉａＰＣＢＣモードはブロック暗号を用いた操作モードであり，暗号化処理では並列処理，事前計算などができないので，高速な処理が要求される環境への実装が困難であった。
【０００５】
これに対して，メッセージ認証子と呼ばれる改ざん検出のための暗号学的チェックサム（以下，ＭＡＣという）を生成する方法が提案され，ブロック暗号の上記操作モードの暗号処理でも必要に応じてＭＡＣ生成処理を同時にかつまったく独立の機構として実装することで，暗号処理と改ざん検出が同時に可能となった。しかし，この場合にはまったく独立な暗号学的鍵を２度，すなわち，暗号化用と改ざん検出用，共有する必要があるという点，それから暗号化されるデータを２度処理，つまり，暗号化処理とＭＡＣ生成処理，にかける必要があり，システムが複雑になったり，長いデータの処理に向かなくなったりなどの懸念があった。さらにブロック暗号の処理速度が現在の通信の速度に比べて低速であり，これらブロック暗号とＭＡＣの組み合わせ技術は，ギガビットやテラビット処理といった高速処理が要求される用途への応用が困難であった。
【０００６】
ＭＡＣと軽い処理との組み合わせが操作モードを実現できることが知られていた。それをモードとして用いたストリーム暗号は，暗号処理と改ざん検出を同時に行えるほか，上記ブロック暗号の処理にくらべて，２倍〜２０倍の比率でストリーム暗号がより高速であるが，どのＭＡＣ生成方法についても，ブロック暗号とＭＡＣの組み合わせ同様， メッセージの長さに対してその２倍の長さの擬似乱数を必要とし，必要な乱数生成に時間がかかったり，ひとつのメッセージについて２度の処理を行う必要などがあった。
【０００７】
より詳しくＭＡＣ生成方法を考えると，本来のストリーム暗号に，付帯的に必要となるメカ二ズムや計算量が非常に大きい。例えば，ＵＭＡＣなどのＭＡＣ生成方法では暗号学的に衝突なしで一方向性を保証している安全なハッシュ関数が必要であり，ストリーム暗号として用いるには，擬似乱数器にさらに前述のハッシュ関数を実装する必要がある。，ＵＭＡＣは以下の非特許文献２で扱っている。
【０００８】
【非特許文献１】
Ｖ．Ｇｌｉｇｏｒ，Ｐ．Ｄｏｎｅｓｃｕ著「Ｌｅｃｔｕｒｅ ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ｖｌ．１７９６」Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ出版，２０００年，ｐ．１５３−１７１
【非特許文献２】
Ｂｌａｃｋ， Ｈａｌｅｖｉ， Ｋｒａｗｃｚｙｋ， Ｋｒｏｖｅｔｚ， Ｒｏｇａｗａｙ， “ＵＭＡＣ： Ｆａｓｔ ａｎｄ Ｓｅｃｕｒｅ Ｍｅｓｓａｇｅ Ａｕｔｈｅｎｔｉｃａｔｉｏｎ，” Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ， − ＣＲＹＰＴＯ’９９， Ｌｅｃｔｕｒｅ Ｎｏｔｅｓ ｉｎ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， Ｖｏｌ． １６６６， Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ， １９９９
【０００９】
【発明が解決しようとする課題】
従来の暗号技術のほとんどは，復号化の際，改ざん検出をそれ自身ではすることができなかった。改ざん検出を行うとき，異なるふたつの鍵共有の必要性，メッセージの２倍となる乱数の必要性，独立の処理，別の暗号学的要素関数の追加実装などが必要であった。
【００１０】
処理速度の面についての課題として，ブロック暗号のこれまで知られた操作モードでは並列度や事前計算等の可能性がなく，高並列処理や高速処理には向いていないという点があり，ストリーム暗号のこれまで知られた操作モードでは，演算量が多いということや，必要な乱数が多いという理由で，ソフトウェア実装における処理速度がブロック暗号の場合と同程度であり，より高速な処理速度が必要とされている。
【００１１】
【課題を解決するための手段】
本発明は効率的で証明可能安全な暗号方法であり，改ざん検出も復号化と同時に可能であり，またデータ秘匿，データ改ざんに対する安全性については，証明可能なメッセージ認証付き暗号方法とその装置を提供する。
【００１２】
本発明は擬似乱数生成器の高速処理性能を生かしながら，事前計算や並列処理の利点をもつ，共通鍵暗号の方法とその装置を提供する。
【００１３】
本発明は従来のブロック暗号よりも高速な処理が可能というだけではなく， シングルパスで実装が可能でソフトウェアにおいて極めて効率的な処理が可能な暗号方法とその装置を提供する。
【００１４】
本発明は小さなプログラムで実装可能なストリーム暗号方法とその装置を提供する。
【００１５】
本発明は，その一態様において，乱数を生成して暗号化と認証処理を行い，事前計算と並列計算を達成する。また，生成する乱数の長さは，メッセージ長Ｎに対して２Ｎより少ない乱数を用いて，暗号処理と認証処理を行う。
【００１６】
具体的には，疑似乱数生成器を使って乱数を生成しそれらをブロック毎に分割する。また平文もブロック毎に分割する。乱数ブロックと平文ブロックを排他的論理和し暗号文ブロックを得る。非特許文献２で扱っているハッシュ関数ＮＨは，乱数ブロックを鍵入力とし，生成された暗号文のメッセージ認証子を生成する。乱数生成は事前計算可能であり，暗号文ブロック生成演算は並列処理可能であり，ハッシュ関数ＮＨも並列処理可能であるため，高速計算ができる。
【００１７】
【発明の実施の形態】
（第一の実施形態）
以下，本発明の第一の実施形態を図を用いて説明する。なお、ビットごとの排他的論理和は、以下の説明ではＥＯＲと表し、各図においてはプラス記号を円で囲んだ記号で表す。
（第一の実施形態）
図１はネットワーク１００１によって接続されたコンピュータＡ１００２，コンピュータＢ１００３を含む，コンピュータＡ１００２からコンピュータＢ１００３への暗号通信を目的としたシステム構成を示すものである。コンピュータＡ１００２は内部に演算装置（以下ＣＰＵという）１００４，記憶装置（揮発性，不揮発性を問わない。以下ＲＡＭという）１００５，ネットワークインターフェース１００６を装備しており，外部にはコンピュータＡ１００２をユーザが操作するためのディスプレイ１００７とキーボード１００８が接続されている。ＲＡＭ１００５には暗号化処理プログラムＰＲＯＧ１＿１００９，乱数生成処理プログラムＰＲＯＧ２＿１０１０，コンピュータＡ１００２とコンピュータＢ１００３間のみで共有されている秘密情報である秘密鍵Ｋ１０１１，コンピュータＡ１００２とコンピュータＢ１００３間で共有されているデータである初期ベクトルＩ１０１３，それに暗号化してコンピュータＢ１００３に送信したいデータであるメッセージＭ１０１４が保存されている。コンピュータＢ１００３は内部にＣＰＵ１０１５，ＲＡＭ１０１６，ネットワークインターフェース１０１７を装備しており，外部にはコンピュータＢ１００３をユーザが操作するためのディスプレイ１０１８とキーボード１０１９が接続されている。ＲＡＭ１０１６には復号化処理プログラムＰＲＯＧ３＿１０２０，乱数生成処理プログラムＰＲＯＧ２＿１０２１，秘密鍵Ｋ１０１１が保存されている。
【００１８】
コンピュータＡ１００２は，暗号化処理プログラムＰＲＯＧ１＿１００９を実行し，メッセージＭ１０１４の暗号文Ｃ１０２２を作成し，ネットワークインターフェース１００６を通してネットワーク１００１へ送信する。コンピュータＢ１００３は，ネットワークインターフェース１０１７を通して受信したあと，復号化処理プログラムＰＲＯＧ３＿１０２０を実行し，もし改ざんが検出されなければ復号化結果をＲＡＭ１０１６に保存する。
【００１９】
各プログラムは，互いのコンピュータまたは他のコンピュータから通信媒体、すなわちネットワーク１００１またはネットワーク１００１上を伝搬する搬送波、を介して，またはＣＤ，ＦＤなど可搬型記憶媒体を介してＲＡＭに導入することができる。各プログラムは，各コンピュータのオペレーティングシステム（図示していない）の元で動作するように構成することも可能である。また、各プログラムによる処理は、ＣＰＵが当該プログラムをメモリから読み出して実行することにより、各コンピュータ上で実現される。
【００２０】
暗号化処理プログラムＰＲＯＧ１＿１００９は，コンピュータＡ１００２において，ＲＡＭ１００５から読み出されて，ＣＰＵ１００４により実行される。暗号化処理プログラムＰＲＯＧ１＿１００９は，サブルーチンとして乱数生成処理ＰＲＯＧ２＿１０１０を内部で呼び出し，入力秘密鍵Ｋ１０１１，メッセージＭ１０１４に対して，暗号文Ｃ１０２２を出力する。
【００２１】
復号化処理プログラムＰＲＯＧ３＿１０２０は，コンピュータＢ１００３において，ＲＡＭ１０１６から読み出されてＣＰＵ１０１５により実行される。復号化処理プログラムＰＲＯＧ３＿１０２０は，サブルーチンとして乱数生成処理ＰＲＯＧ２＿１０２１を内部で呼び出し，入力秘密鍵Ｋ１０１１，暗号文Ｃ１０２２に対して，メッセージ，または改ざん検知警告を出力する。
【００２２】
暗号化処理プログラムＰＲＯＧ１＿１００９の処理の流れを説明する。
ステップ２００２：データセットサブルーチン。秘密鍵Ｋの入力を待つ。
ステップ２００３：平文準備サブルーチン。平文の入力を待ち，平文が与えられたあと決められたパディングを行い，最後に６４ビットごとに区切って平文ブロックの列Ｐ_ｉ（１≦ｉ≦Ｎ）を出力する。但し，Ｎは偶数とする。
ステップ２００４：乱数生成サブルーチン。秘密鍵Ｋと初期ベクトルＩから擬似乱数列Ｒ_ｉ（１≦ｉ≦Ｎ＋１）を出力する。
ステップ２００５：暗号化サブルーチン。擬似乱数列Ｒ_ｉと平文ブロック列Ｐ_ｉ（１≦ｉ≦Ｎ）を使って，暗号文ブロックＣ_ｉ（１≦ｉ≦Ｎ＋２）を出力する。
ステップ２００６：ステップ２００５で得られた暗号文ブロックＣ_ｉ（１≦ｉ≦Ｎ＋２）を順にビット連結し，暗号文Ｃとして出力する。
【００２３】
平文準備サブルーチンの処理を図２を用いて説明する。
ステップ２２０２：暗号処理に用いるメッセージＭの入力を待つ。メッセージＭは，キーボード１００８から入力されたり，ＲＡＭ内に保存されていたり，他の記憶媒体から導入されたりする。
ステップ２２０３：メッセージの長さを示すデータをパディング。メッセージＭの先頭にメッセージＭのビット長を表す６４ビット二進数データを付加する。
ステップ２２０４：メッセージ長をそろえるパディング。後の暗号処理のためパディング後のデータを１２８ビットの整数倍にする。メッセージＭの長さをＬビットとすると１２８−（Ｌ（ｍｏｄ １２８））個の０をステップ２２０３で長さデータを付加されたメッセージの末尾にパディングする。
ステップ２２０６：メッセージデータの平文ブロックへ分割。ステップ２２０５の結果得られたデータを６４ビットのブロックに区切り順にＰ_１，Ｐ_２，．．．，Ｐ_Ｎとする。
【００２４】
乱数生成サブルーチンの処理を図３を用いて説明する。
ステップ２３０２：必要パラメータの入力。パディング後のメッセージブロック数Ｎと， 初期ベクトルＩ
秘密鍵Ｋを得る。
ステップ２３０３：擬似乱数列Ｒの生成。乱数生成処理プログラムＰＲＯＧ２を呼び出し，長さ６４（Ｎ＋１）ビットの擬似乱数列を生成，出力をＲとする。
ステップ２３０４：乱数列Ｒをブロックに分割。擬似乱数列Ｒを６４ビットごとに区切り順にＲ_１，Ｒ_２，．．．，Ｒ_{Ｎ ＋ １}とする。
【００２５】
暗号化，メッセージ認証子生成セットアップのサブルーチンの処理を図４を用いて説明する。
ステップ２４０３：カウンタ初期化。ｉ＝１とする。
ステップ２４０４： 暗号文ブロックＣ_ｉ計算。Ｃ_ｉ ← Ｍ_ｉ ＥＯＲ Ｒ_ｉ とする。
ステップ２４０６：ｉ＝Ｎならばステップ２４０８を実行。
ステップ２４０７：カウンタｉをインクリメントしステップ２４０４へ戻る。
ステップ２４０８：Ｃ_ｉ（１≦ｉ≦Ｎ）を順にビット連結し，Ｓとする。Ｒ_ｉ（２≦ｉ≦Ｎ＋１）を順にビット連結し，Ｒとする。
ステップ２４０９：ＮＨ_Ｒ（Ｓ）の出力を６４ビットごとに区切り，Ｃ_{Ｎ ＋ １}， Ｃ_{Ｎ ＋ ２}とする。
【００２６】
ハッシュ関数ＮＨ_Ｒ（）については，図１１で解説する。
【００２７】
復号化処理プログラムＰＲＯＧ３＿１０２０の処理の流れを図５を用いて説明する。
ステップ２５０２：データセットサブルーチン。秘密鍵Ｋの入力を待つ。
ステップ２５０３：暗号文準備サブルーチン。暗号文Ｃ’の入力を待ち，暗号文Ｃ’が与えられたあと６４ビットごとに区切って暗号文ブロックの列Ｃ’_ｉ（１≦ｉ≦Ｎ＋２）を出力する。
ステップ２５０４：乱数生成サブルーチン。秘密鍵Ｋから擬似乱数列Ｒ_ｉ（１≦ｉ≦Ｎ＋１）を出力する。
ステップ２５０５：Ｃ_ｉ（１≦ｉ≦Ｎ）を順にビット連結し，Ｓとする。Ｒ_ｉ（２≦ｉ≦Ｎ＋１）を順にビット連結し，ＲとしてＮＨ_Ｒ（Ｓ）を計算する。
ステップ２５０６： ＮＨ_Ｒ（Ｓ）＝ Ｃ’_{Ｎ ＋ １}｜｜Ｃ’_{Ｎ ＋ ２}ならばステップ２５０８に進む。そうでないならばステップ２５０７に進む。
ステップ２５０７：拒否（非受理）を出力。ステップ２５１１に進む。
ステップ２５０８：復号化サブルーチン。擬似乱数列Ｒ_ｉ（１≦ｉ≦Ｎ），暗号文ブロック列Ｃ’_ｉ（１≦ｉ≦Ｎ）を使って，平文ブロックＰ’_ｉ（１≦ｉ≦Ｎ）を出力する。
ステップ２５０９：平文切り出しサブルーチン。平文ブロックの列Ｐ’_ｉをデータ列，Ｌ’，Ｍ’に分割する。
ステップ２５１０：Ｍ’をＲＡＭへ格納する。
ステップ２５１１では，復号化処理プログラムは，結果（受理／非受理あるいは復号結果）をディスプレイ１０１８に出力して，ユーザに結果を通知する。
【００２８】
暗号文準備サブルーチンの処理を図６を用いて説明する。
ステップ２６０２：暗号文Ｃ’の入力を待つ。
ステップ２６０３：暗号文Ｃ’を６４ビットごとに区切り，順にＣ’_１，Ｃ’_２，．．．，Ｃ’_{Ｎ ＋ １}，Ｃ’_{Ｎ ＋ ２}とする。
【００２９】
復号化サブルーチンの処理を図７を用いて説明する。
ステップ２７０３：カウンタ初期化。ｉ＝１とする。
ステップ２７０４：平文ブロックＰ’_ｉ計算。Ｐ’_ｉ＝Ｃ’_ｉ＾Ｒ_ｉとする。
ステップ２７０６：ｉ＝Ｎでないならばステップ２７０７を実行。
ステップ２７０７：カウンタｉをインクリメントしステップ２７０４へ戻る。
【００３０】
平文切り出しサブルーチンの処理を図８を用いて説明する。
ステップ２８０２：Ｌ’を最初の６４ビットの平文ブロックとする。
ステップ２８０３：復号文ブロックのうちＰ’_２の最上位ビットからＬ’ビットのデータまでをＭ’とする。
【００３１】
図９は，暗号化処理の説明図である。
【００３２】
メッセージＭ２９３１に長さ２９３０，適当なパディング２９３２をそれぞれ付加し，平文Ｐ２９３４を生成する。
【００３３】
これを６４ビットに分割したものをそれぞれＰ_１＿２９３５，Ｐ_２＿２９３６，．．．，Ｐ_Ｎ＿２９３８とする。
【００３４】
Ｐ_１＿２９３５はＲ_１＿２９２０と排他論理和を取り，暗号文ブロックＣ_１＿２９４３を得る。
【００３５】
Ｐ_２＿２９３６はＲ_２＿２９２１と排他論理和を取り，暗号文ブロックＣ_２＿２９４４を得る。
【００３６】
同様にしてＰ_Ｎ＿２９３８まで処理を行い，暗号文ブロックＣ_１＿２９４３，Ｃ_２＿２９４４，．．．，Ｃ_Ｎ＿２９４７を得る。Ｒ_２＿２９２１，Ｒ_３＿２９２１，Ｒ _{Ｎ ＋ １}＿２９２８をこの順で連結したものＲとＣ_１＿２９４３，Ｃ_２＿２９４４，．．．，Ｃ_Ｎ＿２９４７をこの順で連結したものＳを入力としてＮＨ_Ｒ（Ｓ）を計算する。
ＮＨ_Ｒ（Ｓ）の出力をＣ_{Ｎ ＋ １}＿２９４８，Ｃ_{Ｎ ＋ ２}＿２９４９とブロック分割し，Ｃ_１＿２９４３，Ｃ_２＿２９４４，．．．，Ｃ_Ｎ＿２９４７，Ｃ_{Ｎ ＋ １}＿２９４８，Ｃ_{Ｎ ＋ ２}＿２９４９この順で連結し，暗号文Ｃ＿２９５６を得る。
【００３７】
図１０は，復号化処理の説明図である。
【００３８】
暗号文Ｃ’＿４０３０を６４ビットのブロックに分割し，Ｃ’_１＿４０３５，Ｃ’_２＿４０３６，．．．，Ｃ’_Ｎ＿７０３７， Ｃ’_{Ｎ ＋ １}＿４０３８， Ｃ’_{Ｎ ＋ ２}＿４０３９とする。
Ｒ_２＿４０２１，Ｒ_３＿４０２２，．．．，Ｒ _{Ｎ ＋ １}＿４０２８をこの順で連結したものＲとして，Ｃ’_１＿４０３５，Ｃ’_２＿４０３６，．．．，Ｃ’_Ｎ＿７０３７をこの順で連結したものＳを入力としてＮＨ_Ｒ（Ｓ）を計算し，ＮＨ_Ｒ（Ｓ）＝Ｃ_{Ｎ ＋ ２}’＿４０３８｜｜Ｃ_{Ｎ ＋ １}’＿４０３９ならば，次に進む。
【００３９】
Ｃ_１’＿４０３５はＲ_１＿４０２０と排他論理和を取り，平文ブロックＰ_１’＿４０４３を得る。
【００４０】
Ｃ_２’＿４０３６はＲ_２＿４０２１と排他論理和を取り，平文ブロックＰ_２’＿４０４４を得る。
【００４１】
同様にしてＣ_Ｎ’＿４０３７まで処理を行い，平文ブロックＰ_１’＿４０４３， Ｐ_２’＿４０４４，．．．，Ｐ_Ｎ’＿４０４７を得た後，これらをこの順に連結し，平文Ｐ’＿４０５０とする。これをＬ’＿４０５１，Ｍ’＿４０５２に分割する。
【００４２】
図１１を用いて，非特許文献２で扱っているハッシュ関数ＮＨ_Ｒ（Ｓ）の解説を行う。
【００４３】
この関数はメッセージＭと鍵Ｋを入力とし，メッセージ認証子Ｃを生成し，出力する。は次のようにして行う。ただし，以下のアルゴリズムで，
矢印←はデータの代入を，｜｜は結合を，それぞれ表す。Ｍ＝Ｍ_１｜｜…｜｜ Ｍ_Ｎ ，Ｋ＝Ｋ_１｜｜…｜｜ Ｋ_Ｎとする。
【００４４】
【数１】

【００４５】
最後にメッセージ認証子Ｃを出力する。
【００４６】
第一の実施形態において，暗号処理とメッセージ認証子生成という二つの処理に必要な擬似乱数の長さはメッセージのそれとほぼ同じで十分である。
【００４７】
また、一般的なＣＰＵを使用した計算機上で，本実施形態による疑似乱数生成器はブロック暗号の中で最も高速なＡＥＳに比べ２倍以上高速な処理が可能である。従って，従来技術であるｉａＰＣＢＣモードに比べ、同一環境上で２倍以上高速な処理が可能である。
（第二の実施形態）
以下，本発明の第二の実施形態について説明する。基本的には，第一の実施形態と同じだが，変更点だけ以下に示す。
【００４８】
暗号化処理プログラムＰＲＯＧ１＿１００９の処理の流れを説明する。
ステップ５００２：データセットサブルーチン。秘密鍵Ｋの入力を待つ。
ステップ５００３：平文準備サブルーチン。平文の入力を待ち，平文が与えられたあと決められたパディングを行い，最後に６４ビットごとに区切って平文ブロックの列Ｐ_ｉ（１≦ｉ≦Ｎ）を出力する。但し，Ｎは偶数とする。
ステップ５００４：乱数生成サブルーチン。秘密鍵Ｋと初期ベクトルＩから６４（３Ｎ／２＋１）ビットの擬似乱数列を出力する。
ステップ５００５：暗号化サブルーチン。ステップ５００４で得られた擬似乱数列と平文ブロック列Ｐ_ｉ（１≦ｉ≦Ｎ）を使って，暗号文ブロックＣ_ｉ（１≦ｉ≦Ｎ＋２）を出力する。
ステップ５００６：ステップ５００５で得られた暗号文ブロックＣ_ｉ（１≦ｉ≦Ｎ＋２）を順にビット連結し，暗号文Ｃとして出力する。
【００４９】
乱数生成サブルーチンの処理を図１２を用いて説明する。
ステップ５３０２：必要パラメータの入力。パディング後のメッセージブロック数Ｎと， 初期ベクトルＩと、秘密鍵Ｋを得る。
ステップ５３０３：擬似乱数列Ｒの生成。乱数生成処理プログラムＰＲＯＧ２を呼び出し，長さ
６４（３Ｎ／２＋１）ビットの擬似乱数列Ｒを生成する。
ステップ５３０４：乱数列Ｒをブロックに分割。擬似乱数列Ｒを６４ビットごとに区切り順にＲ_１，Ｒ_２，．．．，Ｒ_{Ｎ ＋ １}．．．，Ｒ_{３Ｎ／２ ＋ １}とする。
ステップ５３０５：Ｒ_{Ｎ ＋ １}．．．，Ｒ_３Ｎ／２をこの順に連結し，Ｒ’とする。
ステップ５３０６：Ｒ_{Ｎ ＋ ２}．．．，Ｒ_{３Ｎ／２ ＋ １}をこの順に連結し，Ｒ’’とする。
【００５０】
暗号化，メッセージ認証子生成セットアップのサブルーチンの処理を図１３を用いて説明する。
ステップ５４０３：カウンタ初期化。ｉ＝１とする。
ステップ５４０４： 暗号文ブロックＣ_ｉ計算。Ｃ_ｉ ← Ｍ_ｉ ＥＯＲ Ｒ_ｉ とする。
ステップ５４０５：ｉ＝Ｎならばステップ５４０７を実行。
ステップ５４０６：カウンタｉをインクリメントしステップ５４０４へ戻る。
ステップ５４０７：カウンタ初期化。ｉ＝１とする。
ステップ５４０８： Ｃ_ｉを３２ビットごとに区切り，Ｃ_{ｉ ， Ｈ}， Ｃ_{ｉ ， Ｌ}とする。
ステップ５４０９： ｉ＝Ｎ／２ならばステップ５４１１を実行。
ステップ５４１０：カウンタｉをインクリメントしステップ５４０８へ戻る。
ステップ５４１１： Ｃ_{１ ， Ｈ}， Ｃ_{１ ， Ｌ}，．．．， Ｃ_{Ｎ／２ ， Ｈ}， Ｃ _{Ｎ／２ ， Ｌ}を順にビット連結し，Ｓとする。
ステップ５４１２：ＮＨ_{Ｒ ’}（Ｓ）の出力をＣ_{Ｎ ＋ １}とする。
ステップ５４１３：ＮＨ_{Ｒ ’’}（Ｓ）の出力をＣ_{Ｎ ＋ ２}とする。
【００５１】
復号化処理プログラムの処理の流れを図１４を用いて説明する。
ステップ５５０２：データセットサブルーチン。秘密鍵Ｋの入力を待つ。
ステップ５５０３：暗号文準備サブルーチン。暗号文Ｃ’の入力を待ち，暗号文Ｃ’が与えられたあと６４ビットごとに区切って暗号文ブロックの列Ｃ’_ｉ（１≦ｉ≦Ｎ＋２）を出力する。
ステップ５５０４：乱数生成サブルーチン。秘密鍵Ｋから擬似乱数列Ｒ_ｉ（１≦ｉ≦３Ｎ／２＋１），Ｒ’，Ｒ’’を出力する。
ステップ５５０５：Ｃ_ｉ（１≦ｉ≦Ｎ）を順にビット連結し，Ｓとする。ＮＨ_{Ｒ ’}（Ｓ）とＮＨ_{Ｒ ’’}（Ｓ）を計算する。
ステップ５５０６： ＮＨ_{Ｒ ’}（Ｓ）＝ Ｃ’_{Ｎ ＋ １}かつ ＮＨ_{Ｒ ’’}（Ｓ）＝Ｃ’_{Ｎ ＋ ２}ならばステップ５５０８に進む。そうでないならばステップ５５０７に進む。
ステップ５５０７：拒否（非受理）を出力。ステップ５５１１に進む。
ステップ５５０８：復号化サブルーチン。擬似乱数列Ｒ_ｉ，暗号文ブロック列Ｃ’_ｉ（１≦ｉ≦Ｎ）を使って，平文ブロックＰ’_ｉ（１≦ｉ≦Ｎ）を出力する。
ステップ５５０９：平文切り出しサブルーチン。平文ブロックの列Ｐ’_ｉをデータ列Ｌ’，Ｍ’に分割する。
ステップ５５１０：Ｍ’をＲＡＭへ格納する。
ステップ５５１０では，復号化処理プログラムは，結果（受理／非受理あるいは復号結果）をディスプレイ１００１８に出力して，ユーザに結果を通知する。
【００５２】
図１５は，暗号化処理の説明図である。
【００５３】
メッセージＭ５９３１に長さ５９３０，適当なパディング５９３２をそれぞれ付加し，平文Ｐ５９３４を生成する。これを６４ビットに分割したものをそれぞれＰ_１＿５９３５，Ｐ_２＿５９３６，Ｐ_Ｎ／２＿５９３７，．．．，Ｐ_Ｎ＿５９３８とする。Ｐ_１＿５９３５はＲ_１＿５９２０と排他論理和を取り，暗号文ブロックＣ_１＿５９４３を得る。Ｐ_２＿５９３６はＲ_２＿５９２１と排他論理和を取り，暗号文ブロックＣ_２＿５９４４を得る。
【００５４】
同様にしてＰ_Ｎ＿５９３８まで処理を行い，暗号文ブロックＣ_１＿５９４３，Ｃ_２＿５９４４，．．．，Ｃ_Ｎ＿５９４７を得る。Ｃ_１＿５９４３，Ｃ_２＿５９４４，．．．，Ｃ_Ｎ／２＿５９４５をこの順で連結したものＳを入力としてＮＨ_{Ｒ ’}（Ｓ）を計算し，その出力をＣ_{Ｎ ＋ １}＿５９４８とする。
【００５５】
ＮＨ_{Ｒ ’’}（Ｓ）を計算し，その出力をＣ_{Ｎ ＋ ２}＿５９４９とする。Ｃ_１＿５９４３，Ｃ_２＿５９４４，．．．，Ｃ_Ｎ／２＿５９４５，．．．，Ｃ_Ｎ＿５９４７，Ｃ_{Ｎ ＋ １}＿５９４８，Ｃ_{Ｎ ＋ ２}＿５９４９この順で連結し，暗号文Ｃ＿５９５６を得る。
【００５６】
図１６は，復号化処理の説明図である。
暗号文Ｃ’＿６０３０を６４ビットのブロックに分割し，Ｃ’_１＿６０３５，Ｃ’_２＿６０３６，．．．，Ｃ’_Ｎ＿７０３７， Ｃ’_{Ｎ ＋ １}＿６０３８， Ｃ’_{Ｎ ＋ ２}＿６０３９とする。Ｃ’_１＿６０３３，Ｃ’_２＿６０３４，Ｃ’_Ｎ／２＿７０３５，．．．，Ｃ’_Ｎ＿７０３７をこの順で連結したものＳを入力としてＮＨ_Ｒ（Ｓ）を計算し，ＮＨ_{Ｒ ’}（Ｓ）＝Ｃ_{Ｎ ＋ １}’＿６０３８かつ， ＮＨ_{Ｒ ’’}（Ｓ）＝Ｃ_{Ｎ ＋ ２}’＿６０３９ならば，次に進む。
【００５７】
Ｃ_１’＿６０３３はＲ_１＿６０２０と排他論理和を取り，平文ブロックＰ_１’＿６０４３を得る。Ｃ_２’＿６０３４はＲ_２＿６０３１と排他論理和を取り，平文ブロックＰ_２’＿６０４４を得る。
【００５８】
同様にしてＣ_Ｎ’＿６０３７まで処理を行い，平文ブロックＰ_１’＿６０４３， Ｐ_２’＿６０４４，．．．， Ｐ_Ｎ’＿６０４７を得た後，これらをこの順に連結し，平文Ｐ’＿６０５０とする。これをＬ’＿６０５１，Ｍ’＿６０５２に分割する。
【００５９】
第二の実施形態において， 暗号処理とメッセージ認証子生成という二つの処理に必要な擬似乱数の長さはメッセージのそれのほぼ１．５倍である。また，一般的なＣＰＵを使用した計算機上で，本実施形態による疑似乱数生成器はブロック暗号の中で最も高速なＡＥＳに比べ２倍以上高速に乱数生成処理が可能である。以上の考察から，第二の実施形態の方法は、従来技術であるｉａＰＣＢＣモードに比べ、同一環境上で、４／３倍以上高速な処理が可能である。
【００６０】
また、非特許文献２の定理２を，ｗ ＝ ３２ ，ｔ ＝ ２として第二の実施形態に適用することにより，安全性証明ができる。すなわち，長さが同じである二つの異なるメッセージに対し，それらのメッセージ認証子が等しくなる確率は２^−６４である。
【００６１】
【発明の効果】
本発明によれば、メッセージ認証付き暗号方法をソフトウェアで実装する際，処理速度を高速化することができる。
【図面の簡単な説明】
【図１】各実施形態のシステム構成図を示す。
【図２】平文準備サブルーチンのフロー図を示す。
【図３】乱数生成サブルーチンのフロー図を示す。
【図４】暗号化サブルーチンのフロー図を示す。
【図５】図１の復号化処理プログラムのフロー図を示す。
【図６】暗号文準備サブルーチンのフロー図を示す。
【図７】復号化サブルーチンのフロー図を示す。
【図８】平文切出しサブルーチンのフロー図を示す。
【図９】暗号化処理の，データブロックによる図を示す。
【図１０】復号化処理の，データブロックによる図を示す。
【図１１】ハッシュ関数ＮＨのフロー図を示す。
【図１２】第二の実施形態の乱数生成２サブルーチンのフロー図を示す。
【図１３】第二の実施形態の暗号化２サブルーチンのフロー図を示す。
【図１４】第二の実施形態の復号化処理プログラムのフロー図を示す。
【図１５】第二の実施形態の暗号化処理の，データブロックによる図を示す。
【図１６】第二の実施形態の復号化処理の，データブロックによる図を示す。
【図１７】第一の実施形態の暗号化処理と認証処理における，乱数共有方法の概念図を示す。
【符号の説明】
１００１…ネットワーク、１００２…コンピュータＡ、１００３…コンピュータＢ、１００４…ＣＰＵ、１００５…ＲＡＭ、１００６…ネットワークインターフェース、１００７…ディスプレイ、１００８…キーボード、１００９…暗号化処理プログラムＰＲＯＧ１＿、１０１０…乱数生成処理プログラムＰＲＯＧ２＿、１０１１…秘密鍵Ｋ、１０１３…初期ベクトルＩ、１０１４…メッセージＭ、１０１５…ＣＰＵ、１０１６…ＲＡＭ、１０１７…ネットワークインターフェース、１０１８…ディスプレイ、１０１９…キーボード、１０２０…復号化処理プログラムＰＲＯＧ３＿、１０２１…乱数生成処理プログラムＰＲＯＧ２＿、１０２２…暗号文Ｃ。

Claims (25)

1. 共通鍵暗号の暗号化装置であって，
   冗長データとメッセージとからなる平文を特定の長さで区切った複数の平文ブロックを生成する処理部と，
   秘密鍵から，前記平文よりも長い乱数列を生成し，前記乱数列から前記平文ブロックに対応する暗号化のための乱数ブロックを生成し，前記平文ブロックと前記乱数ブロックを用いて暗号文ブロックを暗号演算する処理部と，
   前記乱数列から前記暗号文ブロックに対応する認証のための乱数ブロックを生成し，暗号文ブロックと前記乱数ブロックを用いてメッセージ認証子ブロックを認証演算する処理部とを備える共通鍵暗号の暗号化装置。
2. 請求項１記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部と前記認証演算処理部は一つ以上の，その合計の長さは，前記平文ブロックの合計より長く平文ブロックの合計の２倍より短い前記乱数ブロックを用いる共通鍵暗号の暗号化装置。
3. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部は，前記平文ブロックを用いた２項演算や単項演算を決められた手順に従って１回以上行い，
   前記認証演算処理部は，前記暗号文ブロックを用いた２項演算や単項演算を決められた手順に従って１回以上行い，
   得られた複数の暗号文ブロックとメッセージ認証子ブロックを組み合わせ，暗号文として出力する処理部を備える共通鍵暗号の暗号化装置。
4. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部は、前記暗号演算を排他的論理和によって行い，
   前記認証演算処理部は、前記認証演算を算術乗算と算術加算により行う共通鍵暗号の暗号化装置。
5. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部は、前記暗号演算を排他的論理和によって行い，
   前記認証演算処理部は、前記認証演算を有限体上の乗算と算術加算により行う共通鍵暗号の暗号化装置。
6. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部と前記認証演算処理部とは、使う乱数ブロックを共有する共通鍵暗号の暗号化装置。
7. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部と前記認証演算処理部とは、使う乱数ブロックを共有する共通鍵暗号の暗号化装置。
8. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記暗号演算処理部と前記認証演算処理部とは、異なる乱数ブロックを使用する共通鍵暗号の暗号化装置。
9. 請求項２記載の共通鍵暗号の暗号化装置であって，
   前記秘密鍵から前記乱数列を生成する擬似乱数生成処理部を備える共通鍵暗号の暗号化装置。
10. 請求項９の共通鍵暗号の暗号化装置であって，
    前記メッセージを複数に分割する処理部を備え，
    前記擬似乱数生成処理部は，前記分割数分の乱数列を生成し，
    前記分割したメッセージと前記乱数列のいずれかをそれぞれ異なる演算ユ二ットに割り当て，並列処理を行わせる処理部を備える共通鍵暗号の暗号化装置。
11. 共通鍵暗号の復号化装置であって，
    暗号文を特定の長さで区切った複数の暗号文ブロックを生成する処理部と，
    秘密鍵から，前記暗号文よりも長い乱数列を生成し，前記乱数列から前記暗号文ブロックに対応する認証のための乱数ブロックを生成し，暗号文ブロックと前記乱数ブロックを用いてメッセージ認証子ブロックを認証演算する処理部と，
    前記乱数列から暗号文ブロックに対応する復号のための乱数ブロックを生成し，前記暗号文ブロックと，前記乱数ブロックを用いて平文ブロックを復号演算する処理部とを備える共通鍵暗号の復号化装置。
12. 請求項１１記載の共通鍵暗号の復号化装置であって，
    前記認証演算処理部と前記復号演算処理部は一つ以上の，その合計の長さは，前記平文ブロックの合計より長く平文ブロックの合計の２倍より短い前記乱数ブロックを用いる共通鍵暗号の復号化装置。
13. 請求項１２記載の共通鍵暗号の復号化装置であって，
    前記平文ブロックを複数連結して平文を生成する処理部と，
    前記平文に含まれる冗長データを抽出する処理部と，
    前記冗長データを検査し，前記暗号文への改ざんの有無を検出する処理部とを備える共通鍵暗号の復号化装置。
14. コンピュータに，共通鍵暗号の暗号化処理を実行させるプログラムを記憶した媒体であって，
    前記プログラムは，前記コンピュータに，
    冗長データとメッセージとからなる平文を特定の長さで区切った複数の平文ブロックを生成させ，
    秘密鍵から，前記平文よりも長い乱数列を生成し，前記乱数列から前記平文ブロックに対応する暗号化のための乱数ブロックを生成し，前記平文ブロックと前記乱数ブロックを用いて暗号文ブロックを暗号演算させ，
    前記乱数列から前記暗号文ブロックに対応する認証のための乱数ブロックを生成させ，暗号文ブロックと前記乱数ブロックを用いてメッセージ認証子ブロックを認証演算させる、プログラムを記憶した媒体。
15. 請求項１４のプログラムを記憶した媒体であって，
    前記暗号演算と前記認証演算は一つ以上の，その合計の長さは，前記平文ブロックの合計より長く平文ブロックの合計の２倍より短い前記乱数ブロックを用いる、プログラムを記憶した媒体。
16. 請求項１５のプログラムを記憶した媒体であって，
    前記暗号演算として，前記平文ブロックを用いた２項演算や単項演算を決められた手順に従って１回以上行わせ，
    前記認証演算として，前記暗号文ブロックを用いた２項演算や単項演算を決められた手順に従って１回以上行わせ，
    得られた複数の暗号文ブロックとメッセージ認証子ブロックを組み合わせ，暗号文として出力させる、プログラムを記憶した媒体。
17. 請求項１５のプログラムを記憶した媒体であって，
    前記暗号演算を排他的論理和によって行わせ，
    前記認証演算を算術乗算と算術加算により行わせる、プログラムを記憶した媒体。
18. 請求項１５のプログラムを記憶した媒体であって，
    前記暗号演算を排他的論理和によって行わせ，
    前記認証演算を有限体上の乗算と算術加算により行わせる、プログラムを記憶した媒体。
19. 請求項１５のプログラムを記憶した媒体であって，
    前記暗号演算と前記認証演算とが使う乱数ブロックを共有させる、プログラムを記憶した媒体。
20. 請求項１５のプログラムを記憶した媒体であって，
    前記暗号演算と前記認証演算とが使う乱数ブロックを共有させる、プログラムを記憶した媒体。
21. 請求項１５のプログラムを記憶した媒体であって，
    前記秘密鍵から前記乱数列を生成させる擬似乱数生成処理を行わせる，プログラムを記憶した媒体。
22. 請求項２１のプログラムを記憶した媒体であって，
    前記メッセージを複数に分割し，
    前記擬似乱数生成処理によって，前記分割数分の乱数列を生成させ，
    前記分割したメッセージと前記乱数列のいずれかをそれぞれ異なる演算ユ二ットに割り当て，並列処理を行わせる、プログラムを記憶した媒体。
23. コンピュータに，共通鍵暗号の復号化処理を実行させるプログラムを記憶した媒体であって，
    前記プログラムは，前記コンピュータに，
    暗号文を特定の長さで区切った複数の暗号文ブロックを生成させ，
    秘密鍵から，前記暗号文よりも長い乱数列を生成させ，前記乱数列から前記暗号文ブロックに対応する認証のための乱数ブロックを生成させ，暗号文ブロックと前記乱数ブロックを用いてメッセージ認証子ブロックを認証演算させ，
    前記乱数列から暗号文ブロックに対応する復号のための乱数ブロックを生成させ，前記暗号文ブロックと，前記乱数ブロックを用いて平文ブロックを復号演算させる、プログラムを記憶した媒体。
24. 請求項２３のプログラムを記憶した媒体であって，
    前記復号演算と前記認証演算とに一つ以上の，その合計の長さは，前記平文ブロックの合計より長く平文ブロックの合計の２倍より短い前記乱数ブロックを用いらせる、プログラムを記憶した媒体。
25. 請求項２４のプログラムを記憶した媒体であって，
    前記平文ブロックを複数連結して平文を生成させ，
    前記平文に含まれる冗長データを抽出させ，
    前記冗長データを検査させ，前記暗号文への改ざんの有無を検出させる、プログラムを記憶した媒体。

Images