(57)【特許請求の範囲】
【請求項１】
平文とｔｗｅａｋの組を入力する入力手段と、
所定の固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算手段と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化し暗号文として出力する内部暗号化手段と、
前記暗号文を出力する出力手段と、
を含む、ことを特徴とする調整機能付きブロック暗号化装置。
【請求項２】
平文とｔｗｅａｋの組を入力する入力手段と、
所定の固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算手段と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化した結果と前記オフセットとの和をとり暗号文として出力する内部暗号化手段と、
前記暗号文を出力する出力手段と、
を含む、ことを特徴とする調整機能付きブロック暗号化装置。
【請求項３】
平文とｔｗｅａｋの組を入力する入力手段と、
所定の固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算手段と、
内部暗号化手段と、
を備え、
前記内部暗号化手段は、前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果を暗号文として出力するか、
前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果と前記オフセットとの和をとって暗号文として出力するかを、前記ｔｗｅａｋの値によって決定し、
さらに、前記内部暗号化手段からの前記暗号文を出力する出力手段を含む、ことを特徴とする調整機能付きブロック暗号化装置。
【請求項４】
請求項１乃至３のいずれか１項に記載の調整機能付きブロック暗号化装置において、
前記内部暗号化手段と、前記オフセット計算手段で用いられるブロック暗号が、ＡＥＳであり、
前記オフセット計算手段で用いられる前記部分ブロック暗号が、ＡＥＳの段関数の４段の繰り返しである、ことを特徴とする調整機能付きブロック暗号化装置。
【請求項５】
請求項１乃至３のいずれか１項に記載の調整機能付きブロック暗号化装置において、
前記オフセット計算手段では、前記部分ブロック暗号として、前記ブロック暗号と、前記ブロック暗号の一部分から導出されるブロック単位の処理として段関数を予め定められた所定回の繰り返す置換処理を用いる、ことを特徴とする調整機能付きブロック暗号化装置。
【請求項６】
入力装置と、オフセット計算ユニットと、内部暗号化ユニットと、出力装置を備え、調整機能付きブロック暗号化装置を構成するコンピュータに、
前記入力装置から平文とｔｗｅａｋの組を入力する処理と、
所定の固定平文を入力し、前記固定平文をブロック暗号で暗号化した値と、前記入力装置から入力した前記ｔｗｅａｋとの和をとり、その結果を、部分ブロック暗号で暗号化しオフセットとして出力する前記オフセット計算ユニットの処理と、
前記オフセット計算処理から出力される前記オフセットを入力し、前記入力装置から入力した前記平文と前記オフセットとの和をとり、前記ブロック暗号で暗号化し暗号文として出力する前記内部暗号化ユニットの処理と、
前記出力装置から前記暗号文を出力する処理と、
を実行させるプログラム。
【請求項７】
入力装置と、オフセット計算ユニットと、内部暗号化ユニットと、出力装置を備え、調整機能付きブロック暗号化装置を構成するコンピュータに、
前記入力装置から平文とｔｗｅａｋの組を入力する処理と、
所定の固定平文を入力し、前記固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力する前記オフセット計算ユニットの処理と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化した結果と前記オフセットとの和をとり暗号文として出力する前記内部暗号化ユニットの処理と、
前記出力装置から前記暗号文を出力する処理と、
を実行させるプログラム。
【請求項８】
入力装置と、オフセット計算ユニットと、内部暗号化ユニットと、出力装置を備え、調整機能付きブロック暗号化装置を構成するコンピュータに、
前記入力装置から平文とｔｗｅａｋの組を入力する処理と、
所定の固定平文を入力し、前記固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力する前記オフセット計算ユニットの処理と、
前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果を暗号文として出力するか、
前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果と前記オフセットとの和をとって暗号文として出力するかを、前記ｔｗｅａｋの値によって決定する前記内部暗号化ユニットの処理と、
前記出力装置から前記暗号文を出力する処理と、
を実行させるプログラム。
【請求項９】
請求項６乃至８のいずれか１項に記載のプログラムにおいて、
前記内部暗号化処理と、前記オフセット計算処理で用いられるブロック暗号が、ＡＥＳであり、
前記オフセット計算処理で用いられる前記部分ブロック暗号が、ＡＥＳの段関数の４段の繰り返しである、ことを特徴とするプログラム。
【請求項１０】
請求項６乃至８のいずれか１項に記載のプログラムにおいて、
前記オフセット計算ユニットの処理では、前記部分ブロック暗号として、前記ブロック暗号と、前記ブロック暗号の一部分から導出されるブロック単位の処理として段関数を予め定められた所定回の繰り返す置換処理を用いる、ことを特徴とするプログラム。
【請求項１１】
入力装置と、オフセット計算ユニットと、内部暗号化ユニットと、出力装置を備えたコンピュータによる調整機能付きブロック暗号化方法であって、
前記入力装置から平文とｔｗｅａｋの組を入力する工程と、
前記オフセット計算ユニットが、所定の固定平文を入力し、前記固定平文をブロック暗号で暗号化した値と、前記入力装置から入力した前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算工程と、
前記内部暗号化ユニットが、前記オフセット計算ユニットから出力される前記オフセットを入力し、前記入力装置から入力した前記平文との和をとり前記ブロック暗号で暗号化し暗号文として出力する内部暗号化工程と、
前記出力装置が、前記暗号文を出力する工程と、
を含む、ことを特徴とする調整機能付きブロック暗号化方法。
【請求項１２】
入力装置と、オフセット計算ユニットと、内部暗号化ユニットと、出力装置を備えたコンピュータによる調整機能付きブロック暗号化方法であって、
前記入力装置から平文とｔｗｅａｋの組を入力する工程と、
前記オフセット計算ユニットが、所定の固定平文を入力し、前記固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算工程と、
前記内部暗号化ユニットが、前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化した結果と前記オフセットとの和をとり暗号文として出力する内部暗号化工程と、
前記出力装置から前記暗号文を出力する工程と、
を含む、ことを特徴とする調整機能付きブロック暗号化方法。
【請求項１３】
入力装置と、オフセット計算ユニットと、内部暗号化ユニットと、出力装置を備えたコンピュータによる調整機能付きブロック暗号化方法であって、
前記入力装置から平文とｔｗｅａｋの組を入力する工程と、
前記オフセット計算ユニットが、所定の固定平文を入力し、前記固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算工程と、
前記内部暗号化ユニットが、前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果を暗号文として出力するか、
前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果と前記オフセットとの和をとって暗号文として出力するかを、前記ｔｗｅａｋの値によって決定する内部暗号化工程と、
前記出力装置から前記暗号文を出力する工程と、
を含む、ことを特徴とする調整機能付きブロック暗号化方法。
【請求項１４】
請求項１１乃至１３のいずれか１項に記載の調整機能付きブロック暗号化方法において、
前記内部暗号化工程と、前記オフセット計算工程で用いられるブロック暗号が、ＡＥＳであり、
前記オフセット計算工程で用いられる前記部分ブロック暗号が、ＡＥＳの段関数の４段の繰り返しである、ことを特徴とする調整機能付きブロック暗号化方法。
【請求項１５】
請求項１１乃至１３のいずれか１項に記載の調整機能付きブロック暗号化方法において、前記オフセット計算工程では、前記部分ブロック暗号として、前記ブロック暗号と、前記ブロック暗号の一部分から導出されるブロック単位の処理として段関数を予め定められた所定回の繰り返す置換処理を用いる、ことを特徴とする調整機能付きブロック暗号化方法。
【請求項１６】
前記入力手段は、平文Ｍとｔｗｅａｋを入力し、
前記オフセット計算手段は、ブロックサイズをｎビットとし、ｔｗｅａｋをｎビットとした場合、
定数ｃｏｎｓｔをブロック暗号Ｅで暗号化した値と入力したｔｗｅａｋとの和
Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋ                  ・・・（Ａ．１）
（但し、上式（Ａ．１）において、
＋は排他的論理和、
Ｅはｎビットブロックのブロック暗号、
ＫはＥの鍵、
ｃｏｎｓｔはｎビットの任意の値の定数）
を計算し、
次に、ｏｆｆｓｅｔ（オフセット）を、ｎビット入力、ｎビット出力の関数Ｇ
Ｇ（Ｋｓｕｂ，Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋ）    ・・・（Ａ．２）
（但し、上式（Ａ．２）において、
Ｇは、ブロック暗号Ｅの一部分（部分ブロック暗号）であり、Ｇの一つ目の引数を鍵、二つ目の引数を入力とした鍵付きのｎビット関数、もしくはｎビット置換であり、ブロック暗号Ｅがあるラウンド関数をｒ回繰り返す構造の場合、Ｇは、同じラウンド関数を、ｒ以下の整数ｓについてｓ回繰り返し、
鍵ＫｓｕｂとＫは、それぞれ独立とし、その長さは、必ずしも一致しなくてよく、また、Ｋｓｕｂは定数としてもよい。
Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋは、上式（Ａ．１）の計算結果である。）
によって求め、
前記内部暗号化手段は、前記ｏｆｆｓｅｔと前記平文Ｍとの和をとり、前記ブロック暗号Ｅで暗号化した値
Ｅ（Ｋ，Ｍ＋ｏｆｆｓｅｔ）                      ・・・（Ａ．３）
（但し、上式（Ａ．３）において、
Ｅはブロック暗号、
ＫはＥの鍵であり、
＋は排他的論理和）
を、暗号文Ｃとして出力する、ことを特徴とする請求項１記載の調整機能付きブロック暗号化装置。
【請求項１７】
前記入力手段は、平文Ｍとｔｗｅａｋを入力し、
前記オフセット計算手段は、ブロックサイズをｎビットとし、ｔｗｅａｋをｎビットとした場合、
定数ｃｏｎｓｔをブロック暗号Ｅで暗号化した値と入力したｔｗｅａｋとの和
Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋ                  ・・・（Ａ．１）
（但し、上式（Ａ．１）において、
＋は排他的論理和、
Ｅはｎビットブロックのブロック暗号、
ＫはＥの鍵、
ｃｏｎｓｔはｎビットの任意の値の定数）
を計算し、
次に、ｏｆｆｓｅｔ（オフセット）を、ｎビット入力、ｎビット出力の関数Ｇ
Ｇ（Ｋｓｕｂ，Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋ）    ・・・（Ａ．２）
（但し、上式（Ａ．２）において、
Ｇは、ブロック暗号Ｅの一部分（部分ブロック暗号）であり、Ｇの一つ目の引数を鍵、二つ目の引数を入力とした鍵付きのｎビット関数、もしくはｎビット置換であり、ブロック暗号Ｅがあるラウンド関数をｒ回繰り返す構造の場合、Ｇは、同じラウンド関数を、ｒ以下の整数ｓについてｓ回繰り返し、
鍵ＫｓｕｂとＫは、それぞれ独立とし、その長さは、必ずしも一致しなくてよく、また、Ｋｓｕｂは定数としてもよい。
Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋは、上式（Ａ．１）の計算結果である。）
によって求め、
前記内部暗号化手段は、前記ｏｆｆｓｅｔと前記平文Ｍとの和をとり前記ブロック暗号Ｅで暗号化した値と前記ｏｆｆｓｅｔとの和
Ｅ（Ｋ，Ｍ＋ｏｆｆｓｅｔ）＋ｏｆｆｓｅｔ        ・・・（Ａ．４）
（但し、上式（Ａ．４）において、
Ｅはブロック暗号、
ＫはＥの鍵であり、
＋は排他的論理和）
を、暗号文Ｃとして出力する、ことを特徴とする請求項２記載の調整機能付きブロック暗号化装置。
【請求項１８】
関数Ｇは、次式（Ａ．５）で示されるＧ（Ｋｓｕｂ，＊）の最大平均差分確率が十分小さいこと、もしくは十分小さいということが高い信頼性を持って推測でき、さらに、次式（Ａ．６）と次式（Ａ．７）で示される値も十分小さいか、もしくは、十分小さいということが高い信頼性を持って推測できるという条件をみたす、
ｍａｘ｛Ｐｒ（Ｇ（Ｋｓｕｂ，Ｘ）＋Ｇ（Ｋｓｕｂ，Ｘ＋ａ）＝ｂ）｝  ・・・（Ａ．５）
（但し、上式（Ａ．５）において、
最大値（ｍａｘ）は、すべての非ゼロのａと、全ての（ゼロを含む）ｂについてとられ、確率空間は、鍵Ｋｓｕｂと、ｎビットの一様乱数であるＸとによって定義され、鍵Ｋｓｕｂが定数ｃに固定されている場合には、Ｘによってのみ定義される）、
ｍａｘ｛Ｐｒ（Ｇ（Ｋｓｕｂ，Ｘ）＝ｂ）｝                ・・・（Ａ．６）
ｍａｘ｛Ｐｒ（Ｇ（Ｋｓｕｂ，Ｘ）＋Ｘ＝ｂ）｝            ・・・（Ａ．７）
（但し、上式（Ａ．６）と上式（Ａ．７）において、
最大値（ｍａｘ）は、全ての（ゼロを含む）ｂについてとられ、
確率空間は、鍵Ｋｓｕｂと、ｎビットの一様乱数であるＸとによって定義され、鍵Ｋｓｕｂが定数ｃに固定されている場合には、Ｘによってのみ定義される。）
ことを特徴とする請求項１６又は１７記載の調整機能付きブロック暗号化装置。
【請求項１９】
定数ｃｏｎｓｔをブロック暗号Ｅで暗号化した値Ｅ（Ｋ，ｃｏｎｓｔ）は、事前に計算され記憶装置に記憶されている、ことを特徴とする請求項１６又は１７記載の調整機能付きブロック暗号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）本願は、先の日本特許出願２００６−２１８５５８号（２００６年８月１０日出願）の優先権を主張するものであり、前記先の出願の全記載内容は、本書に引用をもって繰込み記載されているものとみなされる。
本発明は、ブロック暗号技術に関し、特にブロック暗号と、ブロック暗号の一部の処理との組合せによる汎用的で高速な調整機能付きブロック暗号装置、および方法とプログラムに関する。
【背景技術】
【０００２】
調整機能付きブロック暗号とは、通常のブロック暗号が持つ入出力である（平文、暗号文、鍵）以外に、「ｔｗｅａｋ」と呼ばれる調整値を持つブロック暗号のことである。【０００３】
調整機能付きブロック暗号においては、調整値が異なる二つのブロック暗号の出力が、調整値と入力が攻撃者に既知であっても、その攻撃者には互いに独立でランダムな値に見えることが要求される。この性質が満たされるとき、調整機能付きブロック暗号は安全であるという。【０００４】
ｔｗｅａｋと同様な補助入力を持つブロック暗号は、従来いくつか提案されてきたが、安全性などについて厳密な要求は定義されていなかった。【０００５】
調整機能付きブロック暗号の形式的な定義は、非特許文献１において最初になされた。【０００６】
また非特許文献１において、理論的に安全な調整機能付きブロック暗号が通常のブロック暗号の運用モード（以後、単に「モード」と略記する）として得られる、つまり、ブロック暗号をブラックボックスとして用いた変換として得られるということが示された。【０００７】
但し、ここでいう理論的安全性とは、あるブロック暗号のモードとして得られる調整機能付きブロック暗号の安全性が、元となるブロック暗号の安全性に帰着できる、つまり安全なブロック暗号を用いる限り、得られる調整機能付きブロック暗号も安全である、ということを指す。【０００８】
さらに、安全性の定義には、
（I）攻撃者が選択平文攻撃（ｃｈｏｓｅｎ−ｐｌａｉｎｔｅｘｔ  ａｔｔａｃｋ，  「ＣＰＡ」という）のみ可能な場合の安全性と、
（II）選択平文攻撃と選択暗号文攻撃（ｃｈｏｓｅｎ−ｃｉｐｈｅｒｔｅｘｔ  ａｔｔａｃｋ，  「ＣＣＡ」）とを組み合わせて実行可能な場合の安全性、
の２種類がある。（I）を「ＣＰＡ−ｓｅｃｕｒｉｔｙ」と呼び、（II）を「ＣＰＡ／ＣＣＡ−ｓｅｃｕｒｉｔｙ」と呼ぶ。【０００９】
安全な調整機能付きブロック暗号は、高度な暗号化機能の実現のための鍵となる技術であることが知られている。【００１０】
例えば、非特許文献３では、
・ＣＰＡ／ＣＣＡ−ｓｅｃｕｒｉｔｙを有する調整機能付きブロック暗号を用いると、大変効率のよい認証機能付き暗号化が実現できることや、
・ＣＰＡ−ｓｅｃｕｒｉｔｙを有する調整機能付きブロック暗号を用いると効率のよい、並列実行可能なメッセージ認証コードが実現できること
が指摘されている。【００１１】
また、ＣＰＡ／ＣＣＡ−ｓｅｃｕｒｉｔｙを有する調整機能付きブロック暗号は、ディスクセクタ暗号化などのストレージ暗号化のための必須の技術であることも知られている。【００１２】
ここでは、非特許文献１で提案されたモードを、「ＬＲＷモード」と呼ぶことにする。このＬＲＷモードの図を図７に示す。【００１３】
ＬＲＷモードにおいては、ブロック暗号以外に、ある鍵つき関数ｆ（Ｋ，＊）が必要となる。【００１４】
ｆ（Ｋ，＊）は、セキュリティパラメータをｅ（ｅは０以上１以下）としたとき、
任意のｃ，ｘ，ｘ’（但しｘとｘ’は異なる）、
について確率Ｐｒ［ｆ（Ｋ，ｘ）＋ｆ（Ｋ，ｘ’）＝ｃ］
が、ｅ以下であるという性質をもつ必要がある。【００１５】
但し、＋は排他的論理和をあらわす。【００１６】
この性質を持つとき、
ｆ（Ｋ，＊）は、「ｅ−ａｌｍｏｓｔ  ＸＯＲ  ｕｎｉｖｅｒｓａｌ  」、略して、「ｅ−ＡＸＵ」であるという。【００１７】
ｅ−ＡＸＵ関数はユニバーサルハッシュ関数の一種である。ｅ−ＡＸＵ関数は、有限体上の多項式演算や、非特許文献２などで提案されている方式で実現可能である。【００１８】
これらは特定の実装環境においては、一般的なブロック暗号より数倍高速である。【００１９】
しかしながら、どのような計算機環境でも実装可能であり、かつ、ブロック暗号よりも高速であるｅ−ＡＸＵ関数は知られていない。【００２０】
このため、ｅ−ＡＸＵ関数が高速に実装可能な環境でないと有効でない、ということが問題となる。【００２１】
また、ブロック暗号とｅ−ＡＸＵ関数という、二つの部品を実装するため、ブロック暗号のみを使う場合と比べてプログラムのサイズが一般に大きくなるということも問題となる。【００２２】
一方、ブロック暗号のみを用いる調整機能付きブロック暗号として、非特許文献３にあるＸＥＸモードも知られている。図８（Ａ）に、ＸＥＸモード（ＸＥＸ  ｃｏｎｓｔｒｕｃｔｉｏｎ）を示す。【００２３】
図８（Ａ）において、ｍｕｌはある基数をｂ、ｔｗｅａｋ２を指数とした場合の有限体上の積演算＊を示す。【００２４】
すなわち、オフセットは、
ｂ＾｛ｔｗｅａｋ２｝＊Ｅ（Ｋ１，ｔｗｅａｋ１）
となっている。【００２５】
このオフセットは、ｔｗｅａｋ２をインクリメントするとき、すなわち、直前のｔｗｅａｋ２の値へ１を足すだけのとき、１回のビットシフトと、１回の定数の排他的論理和のみで計算できる、という利点を持つ。【００２６】
つまり、オフセットの計算は、ブロック暗号の暗号化と比べて、極めて短時間で実行可能で、結果として、１ブロックの暗号化に、ほぼ１ブロック分のブロック暗号による暗号化の計算量しか必要としない。【００２７】
しかし、ある時点でのｔｗｅａｋは、直前のｔｗｅａｋをインクリメントしたものにしかできないため、ＸＥＸモードは、認証機能付き暗号化などには応用が可能であるが、ストレージ暗号化などいくつかの用途には適していない。【００２８】
なお、ＸＥＸモードと類似したモードを用いた認証機能付き暗号化は、ＯＣＢモードとして特許文献１に記載されている。また、ＸＥＸモードそのものを利用した認証機能付き暗号化は、ＯＣＢ１モードとして、非特許文献３に記載されている。【００２９】
一方、一般的に、ｅ−ＡＸＵ関数はどの入力についてもほぼ同等の計算量で出力を求めることができるため、上記ＸＥＸモードの制約は、一般的に、ＬＲＷモードには存在しない。【００３０】
この問題は、図８（Ａ）において、ｔｗｅａｋ１を定数に固定し、ｔｗｅａｋ２のみをｔｗｅａｋとして扱うことで、形式的には解決できるが、今度は、オフセットの計算に、１ブロックの暗号化の計算量を必要とすることになる。【００３１】
したがって、この場合のＸＥＸモードは、１ブロックの暗号化に、２ブロック分のブロック暗号による暗号化の計算量を必要とすることになる。【００３２】
ＬＲＷモードとＸＥＸモードの両方とも、ＣＰＡ／ＣＣＡ−ｓｅｃｕｒｉｔｙを有するが、もし、ＬＲＷモードとＸＥＸモードにおいて、オフセットによる２回目の排他的論理和を省くと、得られるモードは、ＣＰＡ−ｓｅｃｕｒｉｔｙのみを有するモードとなる。【００３３】
ＣＰＡ−ｓｅｃｕｒｉｔｙの方が安全性の概念としては弱いが、前述のように、ＣＰＡ−ｓｅｃｕｒｉｔｙでもいくつかの用途には十分であることが知られている。【００３４】
また、ＸＥＸモードについて、オフセットによる２回目の排他的論理和を省いたモードは、非特許文献３において、ＸＥモードとして定義されている。図８（Ｂ）に、ＸＥモード（ＸＥ  ｃｏｎｓｔｒｕｃｔｉｏｎ）を示す。【００３５】
【非特許文献１】Ｍｏｓｅｓ  Ｌｉｓｋｏｖ，  Ｒｏｎａｌｄ  Ｌ．  Ｒｉｖｅｓｔ，  Ｄａｖｉｄ  Ｗａｇｎｅｒ：  Ｔｗｅａｋａｂｌｅ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒｓ．  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＣＲＹＰＴＯ  ２００２，  ２２ｎｄ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｏｎｆｅｒｅｎｃｅ，  Ｓａｎｔａ  Ｂａｒｂａｒａ，  Ｃａｌｉｆｏｒｎｉａ，  ＵＳＡ，  Ａｕｇｕｓｔ  １８−２２，  ２００２，  Ｐｒｏｃｅｅｄｉｎｇｓ．  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ２４４２  Ｓｐｒｉｎｇｅｒ  ２００２，  ｐｐ．  ３１−４６．
【非特許文献２】Ｓ．  Ｈａｌｅｖｉ  ａｎｄ  Ｈ．  Ｋｒａｗｃｚｙｋ，  ＭＭＨ：Ｓｏｆｔｗａｒｅ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｉｎ  ｔｈｅ  Ｇｂｉｔ／ｓｅｃｏｎｄ  ｒａｔｅｓ，  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ，  ４ｔｈ  Ｉｎｔｅｒｎａｔｉｏａｎｌ  Ｗｏｒｋｓｈｏｐ，  ＦＳＥ  ’９７，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ；  Ｖｏｌ．  １２６７，  Ｆｅｂ．  １９９７
【非特許文献３】Ｐｈｉｌｌｉｐ  Ｒｏｇａｗａｙ：  Ｅｆｆｉｃｉｅｎｔ  Ｉｎｓｔａｎｔｉａｔｉｏｎｓ  ｏｆ  Ｔｗｅａｋａｂｌｅ  Ｂｌｏｃｋｃｉｐｈｅｒｓ  ａｎｄ  Ｒｅｆｉｎｅｍｅｎｔｓ  ｔｏ  Ｍｏｄｅｓ  ＯＣＢ  ａｎｄ  ＰＭＡＣ．  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −ＡＳＩＡＣＲＹＰＴ  ２００４，  １０ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  ｔｈｅ  Ｔｈｅｏｒｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ，  Ｊｅｊｕ  Ｉｓｌａｎｄ，  Ｋｏｒｅａ，  Ｄｅｃｅｍｂｅｒ  ５−９，２００４，  Ｐｒｏｃｅｅｄｉｎｇｓ．  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ３３２９  Ｓｐｒｉｎｇｅｒ  ２００４，  ｐｐ．  １６−３１
【非特許文献４】Ｊ．  Ｄａｅｍｅｎ  ａｎｄ  Ｖ．  Ｒｉｊｍｅｎ，  ＡＥＳ  Ｐｒｏｐｏｓａｌ：  Ｒｉｊｎｄａｅｌ，  ＡＥＳ  ｓｕｂｍｉｓｓｉｏｎ，  １９９８．  インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｃｓｒｃ．ｎｉｓｔ．ｇｏｖ／ＣｒｙｐｔｏＴｏｏｌｋｉｔ／ａｅｓ／ｒｉｊｎｄａｅｌ／Ｒｉｊｎｄａｅｌ．ｐｄｆ＞
【非特許文献５】Ｓ．  Ｐａｒｋ，  Ｓ．  Ｈ．  Ｓｕｎｇ，  Ｓ．  Ｌｅｅ，  ａｎｄ  Ｊ．  Ｌｉｍ，  Ｉｍｐｒｏｖｉｎｇ  ｔｈｅ  Ｕｐｐｅｒ  Ｂｏｕｎｄ  ｏｎ  ｔｈｅ  Ｍａｘｉｍｕｍ  Ｄｉｆｆｅｒｅｎｔｉａｌ  ａｎｄ  ｔｈｅ  Ｍａｘｉｍｕｍ  Ｌｉｎｅａｒ  Ｈｕｌｌ  Ｐｒｏｂａｂｉｌｉｔｙ  ｆｏｒ  ＳＰＮ  Ｓｔｒｕｃｔｕｒｅ  ａｎｄ  ＡＥＳ，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ，  ＦＳＥ  ２００３，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ；  Ｖｏｌ．  ２８８７，  Ｆｅｂ．  ２００３
【特許文献１】米国特許第７，０４６，８０２号明細書
【発明の開示】
【発明が解決しようとする課題】
【００３６】
なお、上記非特許文献１〜５と特許文献１の全開示内容はその引用をもって本書に繰込み記載する。
上記した従来の手法は下記記載の課題を有している（本発明者の分析結果による）。【００３７】
ブロック暗号のみを用いて調整機能付きブロック暗号を実現する従来のＸＥＸモードとＸＥモードは、
・ｔｗｅａｋの更新に１ブロック暗号化の計算量を要するか、
・ｔｗｅａｋがインクリメンタルにしか更新できない、という、いずれかの問題点を有することである。【００３８】
また、ブロック暗号と高速なｅ−ＡＸＵ関数を組み合わせたＬＲＷモードは、実装できる環境が限定されるということである。これは、あらゆる環境で高速に動作するｅ−ＡＸＵ関数は知られていないことによる。また、仮に実装できる環境だとしても、ブロック暗号とｅ−ＡＸＵ関数の両方を実装するためにプログラムサイズが大きくなるからである。【００３９】
したがって、本発明の目的は、ブロック暗号とその一部の部品を組み合わせて、ｔｗｅａｋの任意の更新を１ブロック暗号化よりも少ない計算量で実行可能とするとともに、事前処理や使用するメモリ量の点でも効率のよい、理論的安全性を有する調整機能付きブロック暗号化装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００４０】
本願で開示される発明は、前記目的を達成するため、概略以下の構成とされる。【００４１】
本発明の第１の調整機能付きブロック暗号化装置は、平文とｔｗｅａｋの組を入力する入力手段と、ある固定平文をブロック暗号で暗号化した値と該ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算手段と、該オフセットと該平文との和をとり該ブロック暗号で暗号化し、その結果と該オフセットとの和をとり暗号文として出力する内部暗号化手段と、該暗号文を出力する出力手段と、を備えている。【００４２】
また本発明の第２の調整機能付きブロック暗号化装置は、平文とｔｗｅａｋの組を入力する入力手段と、ある固定平文をブロック暗号で暗号化した値と該ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算手段と、該オフセットと該平文との和をとり該ブロック暗号で暗号化し、その結果を出力する内部暗号化手段と、該暗号文を出力する出力手段とを備えている。【００４３】
本発明の第３の調整機能付きブロック暗号化装置は、前記第１又は第２の調整機能付きブロック暗号装置において、前記内部暗号化手段と前記オフセット計算手段が用いるブロック暗号がＡＥＳ(Advanced Encryption Standard)であり、前記オフセット計算手段が用いる部分ブロック暗号がＡＥＳの段関数の４段の繰り返しである。【００４４】
本発明の第４の調整機能付きブロック暗号化装置は、前記第１又は第２の調整機能付きブロック暗号化装置において、ブロック暗号と、該ブロック暗号の段関数を利用した処理とを用いる。【００４５】
本発明に係る第１のプログラムは、調整機能付きブロック暗号化装置を構成するコンピュータに、
平文とｔｗｅａｋの組を入力装置から入力する処理と、
所定の固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算処理と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化し、その結果と前記オフセットとの和をとり暗号文として出力する内部暗号化処理と、
前記暗号文を出力装置から出力する処理と、
を実行させるプログラムよりなる。【００４６】
本発明に係る第２のプログラムは、調整機能付きブロック暗号化装置を構成するコンピュータに、
平文とｔｗｅａｋの組を入力装置から入力する処理と、
ある固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算処理と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化し暗号文として出力する内部暗号化処理と、
前記暗号文を出力装置から出力する処理と、
を実行させるプログラムよりなる。【００４７】
本発明に係る第３のプログラムにおいて、前記内部暗号化処理と、前記オフセット計算処理で用いられるブロック暗号が、ＡＥＳであり、前記オフセット計算処理で用いられる前記部分ブロック暗号が、ＡＥＳの段関数の４段の繰り返しである。【００４８】
本発明に係る第４のプログラムにおいて、前記ブロック暗号と、前記ブロック暗号の段関数を利用した処理とを用いる。【００４９】
本発明に係る第１の方法は、コンピュータによる調整機能付きブロック暗号化方法であって、
平文とｔｗｅａｋの組を入力装置から入力する工程と、
所定の固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算工程と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化し、その結果と前記オフセットとの和をとり暗号文として出力する内部暗号化工程と、
前記暗号文を出力装置から出力する工程と、
を含む。【００５０】
本発明に係る第２の方法は、コンピュータによる調整機能付きブロック暗号化方法であって、
平文とｔｗｅａｋの組を入力装置から入力する工程と、
ある固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算工程と、
前記オフセットと前記平文との和をとり前記ブロック暗号で暗号化し暗号文として出力する内部暗号化工程と、
前記暗号文を出力装置から出力する工程と、
を含む。【００５１】
本発明に係る第３の方法において、前記内部暗号化工程と、前記オフセット計算工程で用いられるブロック暗号が、ＡＥＳであり、前記オフセット計算工程で用いられる前記部分ブロック暗号が、ＡＥＳの段関数の４段の繰り返しである。【００５２】
本発明に係る第４の方法において、前記ブロック暗号と、前記ブロック暗号の段関数を利用した処理とを用いる。【００５３】
本発明の第５の調整機能付きブロック暗号化装置は、平文とｔｗｅａｋの組を入力する入力手段と、ある固定平文をブロック暗号で暗号化した値と該ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算手段と、前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果を暗号文として出力するか、前記ブロック暗号で暗号化した結果と前記オフセットとの和をとって暗号文として出力するかを、前記ｔｗｅａｋの値によって決定する内部暗号化手段を備えている。【００５４】
本発明に係る第５のプログラムは、調整機能付きブロック暗号化装置を構成するコンピュータに、
平文とｔｗｅａｋの組を入力装置から入力する処理と、
所定の固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算処理と、
前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果を暗号文として出力するか、前記ブロック暗号で暗号化した結果と前記オフセットとの和をとって暗号文として出力するかを、前記ｔｗｅａｋの値によって決定する内部暗号化処理と、
前記暗号文を出力装置から出力する処理と、
を実行させるプログラムよりなる。【００５５】
本発明に係る第５の方法は、コンピュータによる調整機能付きブロック暗号化方法であって、
平文とｔｗｅａｋの組を入力装置から入力する工程と、
ある固定平文をブロック暗号で暗号化した値と前記ｔｗｅａｋとの和をとり、その結果を部分ブロック暗号で暗号化しオフセットとして出力するオフセット計算工程と、
前記オフセットと前記平文との和を前記ブロック暗号で暗号化した結果を暗号文として出力するか、前記ブロック暗号で暗号化した結果と前記オフセットとの和をとって暗号文として出力するかを、前記ｔｗｅａｋの値によって決定する内部暗号化工程と、
前記暗号文を出力装置から出力する工程と、
を含む。
【発明の効果】
【００５６】
本発明の第１の効果は、一般的に知られる代数的なｅ−ＡＸＵ関数を用いたＬＲＷモードよりもプログラムサイズを小さくすることができる、ということである。【００５７】
その理由は、本発明においては、ＬＲＷモードで必要なｅ−ＡＸＵ関数の代わりに、ブロック暗号の一部をブロック暗号そのものと組み合わせて用いているためである。本発明において、その他に必要な演算は排他的論理和などの極めて単純な関数のみである。これにより、実質ブロック暗号のみで実現が可能となっている。【００５８】
本発明の第２の効果は、ＸＥＸモードでは不可能であるｔｗｅａｋの任意の更新を、高速に実行することができる、ということである。【００５９】
その理由は、本発明においては、ｔｗｅａｋの更新を行い新たなオフセットを計算するにあたり、ブロック暗号の一部の処理だけを必要とする構成としたためである。なお、本発明においては、定数平文の暗号化も必要となるが、これは、事前に計算してメモリに置いておくことが可能であるため、ｔｗｅａｋの更新時には計算は不要である。【００６０】
本発明の第３の効果は、既知のブロック暗号に適用したとき、用いるブロック暗号の部分によっては、従来のモードと同等の理論的安全性を有するように構成することができるということである。【００６１】
その理由は、本発明で用いるブロック暗号の一部分の平均最大差分確率と、それに関連したある種の差分確率とが十分小さい場合には、本発明が理論的安全性を有することが証明できるからである。
【図面の簡単な説明】
【００６２】
【図１】本発明の第１の実施例の構成を示す図である。
【図２】本発明の第１の実施例の装置構成を示す図である。
【図３】本発明の第１の実施例の動作を説明するためのフローチャートである。
【図４】本発明の第２の実施例の構成を示す図である。
【図５】本発明の第２の実施例の装置構成を示す図である。
【図６】本発明の第２の実施例の動作を示すフローチャートである。
【図７】非特許文献１に記載されるＬＲＷモードの構成を示す図である。
【図８】（Ａ）、（Ｂ）は、非特許文献３に記載されるＸＥＸモードとＸＥモードの構成を示す図である。
【図９】本発明の第３の実施例の構成を示す図である。
【図１０】本発明の第３の実施例の装置構成を示す図である。
【図１１】本発明の第３の実施例の動作を示すフローチャートである。
【符号の説明】
【００６３】
１０  調整機能付きブロック暗号化装置
２０  調整機能付きブロック暗号化装置
３０  調整機能付きブロック暗号化装置
１００  入力手段
１０１  オフセット計算手段
１０２  内部暗号化手段
１０３  出力手段
２００  入力手段
２０１  オフセット計算手段
２０２  内部暗号化手段
２０３  出力手段
３００  入力手段
３０１  オフセット計算手段
３０２  内部暗号化手段
３０３  出力手段
【発明を実施するための最良の形態】
【００６４】
上記した発明についてさらに詳細に説述すべく、添付図面を参照して説明する。本発明は、ブロック暗号の一部分から導出されるブロック単位の処理と、ブロック暗号そのものとを組み合わせて、調整機能付きブロック暗号を構成する。前者の処理としては、ブロック暗号の短縮段、つまり段関数の何回かの繰り返しによる置換を用いるのが典型的である。この置換処理とブロック暗号そのものとを組み合わせて、ＸＥＸモードでは不可能な、ｔｗｅａｋの任意の更新を可能とする高速な調整機能付きブロック暗号を構成する。【００６５】
ブロック暗号の一部分から導出される置換処理を用いる場合は、ｔｗｅａｋとある定数平文を入力としたブロック暗号の出力との和をとり、これを置換処理に入力することで、オフセットと呼ばれる中間変数を求める。【００６６】
通常のブロック暗号の入力と出力へこのオフセットを足して暗号化処理することで、調整機能付きブロック暗号が得られる。この方式は、ブロック暗号が安全であり、ブロック暗号の一部分から導出される置換処理のいくつかの種類の差分確率が小さい場合には、選択平文・暗号文攻撃に対して、理論的に安全な調整機能付きブロック暗号となる。【００６７】
図１は、本発明の一実施形態の構成（ｃｏｎｓｔｒｕｃｔｉｏｎ）を示す図である。図１を参照すると、ある固定平文（定数）をブロック暗号Ｅで暗号化し（但し、ＫはＥの鍵）、ｔｗｅａｋとの和をとり、その結果を、部分ブロック暗号Ｇで暗号化し（ＫｓｕｂはＧの鍵）、これをオフセットとし、このオフセットと平文Ｍとの和をとりブロック暗号Ｅで暗号化し、その結果とオフセットとの和を暗号文Ｃとする。部分ブロック暗号Ｇは、ブロック暗号Ｅの一部分である。【００６８】
また、本発明の第２の実施形態においては、図４に示すように、該オフセットと平文Ｍとの和をとりブロック暗号Ｅで暗号化し、その結果を暗号文Ｃとする。本発明において、ブロック暗号の出力側へのオフセットの加算を省略した場合には、選択平文攻撃に安全な調整機能付きブロック暗号となる。【００６９】
また、本発明の第３の実施形態においては、図９に示すように、オフセットと平文Ｍとの和をとりブロック暗号Ｅで暗号化し、その結果を暗号文Ｃとするか、その結果とオフセットとの和を暗号文Ｃとするかｔｗｅａｋの値によって選択する。本発明において、あるｔｗｅａｋの値においてブロック暗号の出力側へのオフセットの加算を省略した場合には、そのｔｗｅａｋにおいては選択平文攻撃に安全な調整機能付きブロック暗号となり、そのほかのｔｗｅａｋにおいては、選択平文・暗号文攻撃に安全な調整機能付きブロック暗号となる。【００７０】
本発明において、ブロック暗号として、ＡＥＳを使い、その一部の処理として、ＡＥＳの４段短縮段を用いた場合には、１ブロックの暗号化にＡＥＳの段関数を１４段必要とする。一方、任意のｔｗｅａｋの更新が可能な、ブロック暗号のみによるモードがＸＥＸモードの変形として得られるが、これは、１ブロックの暗号化に、ＡＥＳの段関数を２０段必要とする。よって、本発明の方式の方が１．４倍高速となる。以下実施例に即して説明する。
【実施例】
【００７１】
図２は、本発明の第１の実施例の調整機能付きブロック暗号化装置の装置構成を示すブロック図である。【００７２】
図２を参照すると、本実施例の調整機能付きブロック暗号化装置１０は、入力手段１００と、オフセット計算手段１０１と、内部暗号化手段１０２と、出力手段１０３とを備えている。なお、調整機能付きブロック暗号化装置１０は、不図示のＣＰＵとメモリとディスク装置等を備えた情報処理装置により実現可能である。調整機能付きブロック暗号化装置１０の各手段は、プログラムを記憶装置又は記憶媒体に格納しておき、このプログラムを、主記憶等にロードしＣＰＵ上で動作させることにより実現することができる。【００７３】
次に、調整機能付きブロック暗号化装置１０を構成する各手段について説明する。【００７４】
入力手段１００は、暗号化の対象となる平文と、ｔｗｅａｋを入力する手段である。これは例えばキーボードなどの文字入力装置により実現される。【００７５】
オフセット計算手段１０１は、ｔｗｅａｋに依存したオフセット値ｏｆｆｓｅｔを計算する手段である。オフセット計算手段１０１は、次式（１）の計算を行う。ブロックサイズがｎビットの場合、ｔｗｅａｋもｎビットで、この処理はｎビット入力、ｎビット出力の鍵付き関数である。【００７６】
ｏｆｆｓｅｔ＝Ｇ（Ｋｓｕｂ，Ｅ（Ｋ，ｃｏｎｓｔ）＋ｔｗｅａｋ）    ・・・(1)
上式（１）において、
＋は排他的論理和、
Ｅはｎビットブロックのブロック暗号、
ＫはＥの鍵、
ｃｏｎｓｔは任意の定数ｎビット値、
である。【００７７】
また上式（１）のＧは、Ｅの一部分であり、Ｇの一つ目の引数を鍵、二つ目の引数を入力としたある鍵付きのｎビット関数、もしくはｎビット置換である。例えばＥがあるラウンド関数をｒ回繰り返す構造の場合、Ｇは、同じラウンド関数を、ｒ以下の整数ｓについてｓ回繰り返す（このときのＧをブロック暗号の「短縮段」と呼ぶ）としてよい。但し、ＫとＫｓｕｂは、それぞれ独立であるとする。その長さは、必ずしも一致しなくてよい。さらに、Ｋｓｕｂは定数としてもよい。【００７８】
式（１）における、Ｅ（Ｋ，ｃｏｎｓｔ）は、事前に計算し、記憶しておくことが可能である。【００７９】
Ｇに対する条件は３つある。【００８０】
条件の１つとして、次式（２）で示されるＧ（Ｋｓｕｂ，＊）の最大平均差分確率が
・十分小さいこと、もしくは、
・十分小さいということが高い信頼性を持って推測できること
がある。【００８１】
ｍａｘ｛Ｐｒ（Ｇ（Ｋｓｕｂ，Ｘ）＋Ｇ（Ｋｓｕｂ，Ｘ＋ａ）＝ｂ）｝    ・・・(2)
但し、式（２）において、最大値（ｍａｘ）は、すべての非ゼロのａと、全ての（ゼロを含む）ｂについてとられる。また確率空間は、鍵Ｋｓｕｂと、ｎビットの一様乱数であるＸとによって定義される。もし、鍵Ｋｓｕｂが定数ｃに固定されている場合には、確率空間は、Ｘによってのみ定義される。【００８２】
残る２つの条件として、同様に、以下の式（３）と式（４）で示される値も、十分小さい、もしくは、十分小さいということが高い信頼性を持って推測できること、が必要である。【００８３】
ｍａｘ｛Ｐｒ（Ｇ（Ｋｓｕｂ，Ｘ）＝ｂ）｝                ・・・(3)
ｍａｘ｛Ｐｒ（Ｇ（Ｋｓｕｂ，Ｘ）＋Ｘ＝ｂ）｝            ・・・(4)
但し、式（３）と式（４）において、最大値（ｍａｘ）は、全ての（ゼロを含む）ｂについてとられる。また、確率空間は鍵Ｋｓｕｂと、ｎビットの一様乱数であるＸとによって定義される。もし鍵Ｋｓｕｂが定数ｃに固定されている場合には、確率空間はＸによってのみ定義される。【００８４】
近年のブロック暗号は差分攻撃と線形攻撃に対する耐性を持たせるために、Ｇをラウンド関数の何段かの繰り返しとした場合に、式（２）で示される最大平均差分確率と最大平均線形確率を小さくすることを念頭において設計されていることが多い。【００８５】
また、いくつかのブロック暗号では、実際に最大平均差分確率と最大平均線形確率が小さいと証明されている場合がある。例として、非特許文献５では、非特許文献４のブロック暗号ＡＥＳでは、４段の繰り返しが高々２の−１１３乗の最大平均差分確率を持つことが示されている。【００８６】
また、
・式（３）の確率は、Ｇが置換の場合には、理論最小値（ブロックサイズがｎなら２の−ｎ乗）を持つことと、
・式（４）で示される確率が線形確率と関連するために、線形攻撃に対する耐性を持ったブロック暗号のラウンド関数の適切な回数の繰り返しでは十分小さい値を持つと期待できること、
から、安全なブロック暗号の短縮段をＧとして用いることで、安全性に対して高い信頼性をもって、本発明の実施例を構築することが可能である。【００８７】
内部暗号化手段１０２は、オフセット計算手段１０１の出力するオフセット値と平文とを用いて暗号文を生成する手段である。平文をＭとし、オフセット計算手段１０１の出力するオフセット値をｏｆｆｓｅｔとすると、内部暗号化手段１０２の出力する暗号文は次式（５）で与えられる。【００８８】
Ｅ（Ｋ，Ｍ＋ｏｆｆｓｅｔ）＋ｏｆｆｓｅｔ        ・・・(5)
但し、
Ｅはブロック暗号、
ＫはＥの鍵であり、
＋は排他的論理和を表す。【００８９】
出力手段１０３は、内部暗号化手段１０２が出力したされた暗号文をコンピュータディスプレイやプリンターなどへ出力する手段である。【００９０】
本発明の第１の実施例の動作について図２及び図３の流れ図を参照して詳細に説明する。【００９１】
まず、入力手段１００へ平文とｔｗｅａｋを入力し（図３のステップＡ１）、ｔｗｅａｋを用いてオフセット計算手段１０１が、式（１）に従ってｏｆｆｓｅｔを求める（図３のステップＡ２）。【００９２】
次にオフセット計算手段１０１が出力したｏｆｆｓｅｔと平文を用いて内部暗号化手段１０２は暗号文を求める（図３のステップＡ３）。【００９３】
最後に暗号文を出力する（図３のステップＡ４）。【００９４】
次に、本発明の第２の実施例について説明する。図５は、本発明の第２の実施例の調整機能付きブロック暗号化装置の構成を示すブロック図である。【００９５】
本実施例の調整機能付きブロック暗号化装置２０は、入力手段２００と、オフセット計算手段２０１と、内部暗号化手段２０２と、出力手段２０３とを備えている。調整機能付きブロック暗号化装置２０は、図２の前記第１の実施例と同様、不図示のＣＰＵとメモリとディスク装置等を備えた情報処理装置により実現可能である。調整機能付きブロック暗号化装置２０の各手段は、プログラムを記憶装置又は記憶媒体に格納しておき、このプログラムを、主記憶等にロードしＣＰＵ上で動作させることにより実現することができる。【００９６】
入力手段２００と、オフセット計算手段２０１と、出力手段２０３は、それぞれ前記第１の実施例の入力手段１００と、オフセット計算手段１０１と、出力手段１０３と同じである。【００９７】
内部暗号化手段２０２は、オフセット計算手段２０１の出力するオフセット値と平文とを用いて暗号文を生成する手段である。平文をＭとし、オフセット計算手段２０１の出力するオフセット値をｏｆｆｓｅｔとすると、内部暗号化手段２０２の出力する暗号文は、次式（６）で与えられる。【００９８】
Ｅ（Ｋ，Ｍ＋ｏｆｆｓｅｔ）            ・・・(6)
但し、
Ｅはブロック暗号、
ＫはＥの鍵であり、
＋は排他的論理和を表す。【００９９】
本発明の第２の実施例の全体の動作について、図５と図６の流れ図を参照して詳細に説明する。【０１００】
まず、入力手段２００へ平文とｔｗｅａｋを入力し（図６のステップＢ１）、ｔｗｅａｋを用いてオフセット計算手段２０１が式（１）に従ってｏｆｆｓｅｔを求める（図６のステップＢ２）。【０１０１】
次にオフセット計算手段２０１が出力したｏｆｆｓｅｔと平文を用いて内部暗号化手段２０２は暗号文を求める（図６のステップＢ３）。【０１０２】
最後に暗号文を出力する（図６のステップＢ４）。【０１０３】
次に、本発明の第３の実施例について説明する。図１０は、本発明の第３の実施例の調整機能付きブロック暗号化装置の構成を示すブロック図である。【０１０４】
図１０を参照すると、本実施例の調整機能付きブロック暗号化装置３０は、入力手段３００と、オフセット計算手段３０１と、内部暗号化手段３０２と、出力手段３０３とを備えている。調整機能付きブロック暗号化装置３０は、図２の前記第１の実施例と同様、不図示のＣＰＵとメモリとディスク装置等を備えた情報処理装置により実現可能である。調整機能付きブロック暗号化装置３０の各手段は、プログラムを記憶装置又は記憶媒体に格納しておき、このプログラムを、主記憶等にロードしＣＰＵ上で動作させることにより実現することができる。【０１０５】
入力手段３００と、オフセット計算手段３０１と、出力手段３０３は、それぞれ、前記第１の実施例の入力手段１００と、オフセット計算手段１０１と、出力手段１０３と同じである。【０１０６】
内部暗号化手段３０２は、オフセット計算手段３０１の出力するオフセット値と平文とを用いて暗号文を生成する手段である。平文をＭとし、オフセット計算手段３０１の出力するオフセット値をｏｆｆｓｅｔとすると、内部暗号化手段３０２の出力する暗号文は、次式（７）で与えられる。【０１０７】
Ｅ（Ｋ，Ｍ＋ｏｆｆｓｅｔ）＋ｓｅｌ（ｔｗｅａｋ, ｏｆｆｓｅｔ）  ・・・(7)
但し、
Ｅはブロック暗号、
ＫはＥの鍵であり、
＋は排他的論理和を表す。【０１０８】
ｓｅｌは、ｔｗｅａｋの値によってｏｆｆｓｅｔもしくは全ゼロを出力する関数である。ｓｅｌがいずれを出力するかを判断するロジックは、あらかじめ決められているものとする。例えば、ｔｗｅａｋの最下位ビットの値が０ならｏｆｆｓｅｔを、１なら全ゼロを出力する、としてもよい。【０１０９】
また、ｓｅｌの出力が全ゼロの場合、全ゼロを足しても結果は変わらないため、和をとる処理が省略できる。【０１１０】
本発明の第３の実施例の全体の動作について、図１０と図１１の流れ図を参照して詳細に説明する。【０１１１】
まず、入力手段３００へ平文とｔｗｅａｋを入力し（図１１のステップＣ１）、ｔｗｅａｋを用いてオフセット計算手段３０１が式（１）に従ってｏｆｆｓｅｔを求める（図１１のステップＣ２）。【０１１２】
次にオフセット計算手段３０１が出力したｏｆｆｓｅｔと平文およびｓｅｌ（ｔｗｅａｋ, ｏｆｆｓｅｔ）を用いて内部暗号化手段３０２は暗号文を求める（図１１のステップＣ３）。【０１１３】
最後に暗号文を出力する（図１１のステップＣ４）。【０１１４】
上記した実施例の作用効果について説明する。【０１１５】
ＬＲＷモードで必要なｅ−ＡＸＵ関数の代わりに、ブロック暗号の一部をブロック暗号そのものと組み合わせて用いているため、一般的に知られる代数的なｅ−ＡＸＵ関数を用いたＬＲＷモードよりもプログラムサイズ、構成を小さくすることができる。本発明において、その他に必要な演算は、排他的論理和などの極めて単純な関数のみである。これにより、実質、ブロック暗号のみで実現が可能となっている。【０１１６】
ＸＥＸモードでは不可能であるｔｗｅａｋの任意の更新を、高速に実行することができる。その理由は、本発明においては、ｔｗｅａｋの更新を行い新たなオフセットを計算するにあたり、ブロック暗号の一部の処理だけを必要とする構成としたためである。なお、本発明においては、定数平文の暗号化も必要となるが、これは、事前に計算してメモリに置いておくことが可能であるため、ｔｗｅａｋの更新時には計算は不要である。【０１１７】
例として、非特許文献４に記載のブロック暗号ＡＥＳと、ＡＥＳの段関数の４回の繰り返し（４段ＡＥＳ）とを用いた場合、ＡＥＳのＸＥＸモード（但し、図８（Ａ）のｔｗｅａｋ２を固定し、任意のｔｗｅａｋの更新を可能としたバージョンで）よりも約１．４倍高速となる。【０１１８】
既知のブロック暗号に適用したとき、用いるブロック暗号の部分によっては、従来のモードと同等の理論的安全性を有するように構成することができる。【０１１９】
その理由は、本発明で用いるブロック暗号の一部分の平均最大差分確率と、それに関連したある種の差分確率とが十分小さい場合には、本発明は理論的安全性を有することが証明できるからである。【０１２０】
ここで、ブロック暗号の段関数の数回の繰り返しが小さい平均最大差分確率を持つことは、差分攻撃に十分な安全性を持つブロック暗号の必須条件と言えるため、近年提案されたブロック暗号の多くがこの性質を持つように設計されていることに注意されたい。具体的には、前述の例のように４段ＡＥＳを用いる場合を考えると、４段ＡＥＳが十分小さい平均最大差分確率を持つことが非特許文献５に記載されている。【０１２１】
また、求められるその他の種類の差分確率についても十分小さいことが分かっている。【０１２２】
このため、４段ＡＥＳとＡＥＳを組み合わせて用いる場合には、本発明による調整機能付きブロック暗号の安全性はＡＥＳの安全性に帰着できることが証明可能である。【０１２３】
また、差分確率の最大値が厳密には証明できないような複雑な構造を用いて本発明を実現した場合でも、差分確率の最大値が十分小さいと信じられる場合には、その信頼度に応じた安全性の保証を与えることができる。【０１２４】
ＡＥＳの４段を部品として用いること自体は、先願（特願２００６−００４８１２号；本願出願時未公開）に記載されているが、これはメッセージ認証コードへの応用を目的としたものであり、本発明とは目的も使用方法も異なっている。【０１２５】
本発明によれば、無線もしくは有線のデータ通信における認証と暗号化といった用途や、ストレージ上のデータの暗号化と改ざん防止といった用途に適用できる。【０１２６】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。
【図１】
0005182091.tif 000002
【図２】
0005182091.tif 000003
【図３】
0005182091.tif 000004
【図４】
0005182091.tif 000005
【図５】
0005182091.tif 000006
【図６】
0005182091.tif 000007
【図７】
0005182091.tif 000008
【図８】
0005182091.tif 000009
【図９】
0005182091.tif 000010
【図１０】
0005182091.tif 000011
【図１１】
0005182091.tif 000012