(57)【特許請求の範囲】
【請求項１】
Ｎが１以上の整数であり、Ｍが２以上の整数であり、ｎ＝０，…，Ｎ−１であり、ｍ＝０，…，Ｍ−１であり、Ｎ個のブロックｂ０，…，ｂＮ−１のそれぞれのブロックｂｎがＭ個の部分列ｃｎ，０，…，ｃｎ，Ｍ−１を含み、
前記部分列ｃ０，ｍ，…，ｃＮ−１，ｍに対して乗算を含む演算を行って部分検知符号Ｃｍを得る部分処理部と、
前記部分検知符号Ｃ０，…，ＣＭ−１に対応する検知符号を得る統合部と、
を有し、
前記部分検知符号Ｃ０，…，ＣＭ−１のそれぞれの部分検知符号Ｃｍの長さがＬであり、ｋ＝０，…，Ｋ−１であり、Ｋ＜Ｍであり、前記部分列ｃｎ，０，…，ｃｎ，Ｍ−１のそれぞれの部分列ｃｎ，ｍの長さがＬであり、
前記統合部は、前記部分検知符号Ｃ０，…，ＣＭ−１をＫ個の部分集合Ｓｕｂ０，…，ＳｕｂＫ−１に区分し、前記部分集合Ｓｕｂ０，…，ＳｕｂＫ−１のそれぞれについて部分集合Ｓｕｂｋの要素の線形結合演算を行って、Ｋ個の中間検知符号ＳＣ０，…，ＳＣＫ−１を得、前記中間検知符号ＳＣ０，…，ＳＣＫ−１からなる長さがＬのＫ倍である列を前記検知符号とする、検知機能付加装置。
【請求項２】
請求項１の検知機能付加装置であって、
ＱおよびＬが１以上の整数であり、Ｋが２以上の整数であり、ｑ＝０，…，Ｑ−１であり、
入力された処理単位ブロックＢ０，…，ＢＱ−１から前記ブロックｂ０，…，ｂＮ−１または前記部分列ｃ０，ｍ，…，ｃＮ−１，ｍを得る区分部を有し、
前記部分列ｃ０，ｍ，…，ｃＮ−１，ｍのそれぞれの部分列ｃｎ，ｍの長さがＬであり、
前記処理単位ブロックＢ０，…，ＢＱ−１のそれぞれの処理単位ブロックＢｑの長さがＬのＫ倍である、検知機能付加装置。
【請求項３】
請求項１または２の検知機能付加装置であって、
前記統合部は、前記部分検知符号Ｃ０，…，ＣＭ−１を被演算子とした線形結合演算を行って前記検知符号を得る、検知機能付加装置。
【請求項４】
請求項１から３の何れかの検知機能付加装置であって、
前記部分処理部は、何れか複数のｍについて並列に前記乗算を含む演算を行って前記部分検知符号Ｃｍを得る、検知機能付加装置。
【請求項５】
請求項１から４の何れかの検知機能付加装置であって、
Ｎ≧２であり、
前記部分処理部は、
任意値Ｒｍを得る任意値選択部と、
初期値Ｃ０，ｍ＝Ｒｍ２ｃ０，ｍを得る初期値生成部と、
ｉ＝０，…，Ｎ−２での再帰処理によって中間値Ｃｉ＋１，ｍ＝（ｃｉ＋１，ｍ＋Ｃｉ，ｍ）Ｒｍを得、ＣＮ−１，ｍを前記部分検知符号Ｃｍとする再帰処理部と、を含む、検知機能付加装置。
【請求項６】
Ｎが１以上の整数であり、Ｍが２以上の整数であり、ｎ＝０，…，Ｎ−１であり、ｍ＝０，…，Ｍ−１であり、Ｎ個のブロックｂ’０，…，ｂ’Ｎ−１のそれぞれのブロックｂ’ｎがＭ個の部分列ｃ’ｎ，０，…，ｃ’ｎ，Ｍ−１を含み、
前記部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍに対して乗算を含む演算を行って部分検知符号Ｃ’ｍを得る部分処理部と、
前記部分検知符号Ｃ’０，…，Ｃ’Ｍ−１を被演算子とした線形結合演算を行って検知符号を得る統合部と、
入力符号と前記検知符号とが一致するかを判定する判定部と
を有し、
前記部分検知符号Ｃ’０，…，Ｃ’Ｍ−１のそれぞれの部分検知符号Ｃ’ｍの長さがＬであり、ｋ＝０，…，Ｋ−１であり、Ｋ＜Ｍであり、前記部分列ｃ’ｎ，０，…，ｃ’ｎ，Ｍ−１のそれぞれの部分列ｃ’ｎ，ｍの長さがＬであり、
前記統合部は、前記部分検知符号Ｃ’０，…，Ｃ’Ｍ−１をＫ個の部分集合Ｓｕｂ’０，…，Ｓｕｂ’Ｋ−１に区分し、前記部分集合Ｓｕｂ’０，…，Ｓｕｂ’Ｋ−１のそれぞれについて部分集合Ｓｕｂ’ｋの要素の線形結合演算を行って、Ｋ個の中間検知符号ＳＣ’０，…，ＳＣ’Ｋ−１を得、前記中間検知符号ＳＣ’０，…，ＳＣ’Ｋ−１からなる長さがＬのＫ倍である列を前記検知符号とする検知装置。
【請求項７】
請求項６の検知装置であって、
ＱおよびＬが１以上の整数であり、Ｋが２以上の整数であり、ｑ＝０，…，Ｑ−１であり、
入力された処理単位ブロックＢ’０，…，Ｂ’Ｑ−１から前記ブロックｂ’０，…，ｂ’Ｎ−１または前記部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍを得る区分部を有し、
前記部分列ｃ０，ｍ，…，ｃＮ−１，ｍのそれぞれの部分列ｃｎ，ｍの長さがＬであり、
前記処理単位ブロックＢ’０，…，Ｂ’Ｑ−１のそれぞれの処理単位ブロックＢ’ｑの長さがＬのＫ倍である、検知装置。
【請求項８】
請求項１から５の何れかの検知機能付加装置もしくは請求項６または７の検知装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの改ざんまたは誤りを検知する技術に関する。
【背景技術】
【０００２】
暗号文の改ざんまたは誤りを検知する機能（以下「検知機能」）を有するブロック暗号方式としてＧＣＭ（Galois/Counter Mode）がある（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】NIST: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, NIST Special Publication 800-38D, November, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＧＣＭでは「検知機能」を付加するためにブロックごとに乗算を含む演算を行う必要があり、その処理速度に改善の余地がある。これはＧＣＭに限られたことではなく、ブロックごとに区分されたデータに対し、ブロックごとの乗算を含む演算を行って「検知機能」を付加する場合に共通する。
【０００５】
本発明の課題は、検知機能を付加するための演算を高速化することである。
【課題を解決するための手段】
【０００６】
本発明では、Ｎが１以上の整数であり、Ｍが２以上の整数であり、ｎ＝０，…，Ｎ−１であり、ｍ＝０，…，Ｍ−１であり、Ｎ個のブロックｂ０，…，ｂＮ−１のそれぞれのブロックｂｎがＭ個の部分列ｃｎ，０，…，ｃｎ，Ｍ−１を含む。部分列ｃ０，ｍ，…，ｃＮ−１，ｍに対して乗算を含む演算を行って部分検知符号Ｃｍを得、部分検知符号Ｃ０，…，ＣＭ−１に対応する検知符号を得る。
【発明の効果】
【０００７】
これにより、検知機能を付加するための演算を高速化できる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態の検知システムの機能構成を例示したブロック図である。
【図２】図２Ａおよび図２Ｂは、実施形態の部分処理部の機能構成を例示したブロック図である。
【図３】図３は、実施形態の処理を説明するためのフロー図である。
【図４】図４は、実施形態の処理の具体例を説明するためのフロー図である。
【図５】図５は、実施形態の処理の具体例を説明するためのフロー図である。
【図６】図６Ａから図６Ｃは、実施形態の処理の具体例を説明するための図である。
【図７】図７Ａから図７Ｃは、実施形態の処理の具体例を説明するための図である。
【図８】図８Ａおよび図８Ｂは、実施形態の処理の具体例を説明するための図である。
【図９】図９Ａおよび図９Ｂは、実施形態の統合部の機能構成を例示したブロック図である。
【図１０】図１０Ａおよび図１０Ｂは、実施形態の処理の具体例を説明するための図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［概要］
本実施形態では、検知機能付加装置が検知符号Ｃを生成し、検知装置が入力された検知符号Ｃ（入力符号）を用いて改ざんおよび誤りの少なくとも一方を検知する。
【００１０】
本形態の検知機能付加装置は、Ｎ個のブロックｂ０，…，ｂＮ−１のそれぞれのブロックｂｎがＭ個の部分列ｃｎ，０，…，ｃｎ，Ｍ−１を含むものとし、部分列ｃ０，ｍ，…，ｃＮ−１，ｍに対して乗算を含む演算を行って部分検知符号Ｃｍを得、部分検知符号Ｃ０，…，ＣＭ−１に対応する検知符号Ｃを得る。ただし、Ｎは１以上の整数であり、Ｍは２以上の整数であり、ｎ＝０，…，Ｎ−１であり、ｍ＝０，…，Ｍ−１である。乗算に必要な演算量は被演算子が長いほど大きくなり、通常、被演算子の長さの増加に対して指数関数的に増加する。本形態では、ブロックｂｎよりも短い部分列ｃｎ，ｍに対して乗算を含む演算を行うため、ブロックｂｎに対して乗算を含む演算を行うよりも演算量を削減でき、高速化できる。このような演算は、例えば拡大体上で行われる。ある有限体Ｆ（ｐ）（ただし、ｐは２以上の整数。例えば、ｐ＝２。）を基礎体とした拡大次数ｗ（ただし、ｗは１以上の整数）の拡大体Ｆ（ｐｗ）での演算は、有限体Ｆ（ｐ）のｗ個の元からなる列の演算（例えば、ｗ次元ベクトルの演算）として実装できる。
【００１１】
ブロックｂ０，…，ｂＮ−１または部分列ｃ０，ｍ，…，ｃＮ−１，ｍは、検知機能付加装置にそのまま入力されてもよいし、検知機能付加装置に入力された処理単位ブロックＢ０，…，ＢＱ−１から得られてもよい。後者の場合、処理単位ブロックＢ０，…，ＢＱ−１そのものをブロックｂ０，…，ｂＮ−１としてもよいし、処理単位ブロックＢ０，…，ＢＱ−１またはそれにパディングした列を再区分してブロックｂ０，…，ｂＮ−１または部分列ｃ０，ｍ，…，ｃＮ−１，ｍを得てもよい。ただし、処理単位ブロックＢｑの長さが部分列ｃｎ，ｍの長さＬのＫ倍でとする。ここで、ＱおよびＬは１以上の整数（例えば２以上の整数）であり、Ｋは２以上の整数であり、ｑ＝０，…，Ｑ−１である。Ｎ＞Ｑであってもよいし、Ｎ＝Ｑであってもよいし、Ｎ＜Ｑであってもよい。Ｍ＞Ｋであってもよいし、Ｍ＝Ｋであってもよいし、Ｍ＜Ｋであってもよい。この場合、処理単位ブロックＢｑよりも短い部分列ｃｎ，ｍに対して乗算を含む演算を行うことになるため、処理単位ブロックＢｑに対して乗算を含む演算を行うよりも演算量を削減でき、高速化できる。
【００１２】
検知機能付加装置は、部分検知符号Ｃ０，…，ＣＭ−１そのものを検知符号Ｃ＝（Ｃ０，…，ＣＭ−１）としてもよいし、部分検知符号Ｃ０，…，ＣＭ−１を被演算子とした線形結合演算によって得られる値を検知符号Ｃとしてもよい。前者の例はＣ０，…，ＣＭ−１の連結Ｃ０｜…｜ＣＭ−１である。後者の場合、線形結合演算が必要となるが、このような線形結合演算の演算量は非常に小さく、検知符号Ｃを得るための演算量の合計は、ブロックｂｎまたは処理単位ブロックＢｑごとに乗算を含む演算を行って検知符号Ｃを得るための演算量よりも小さい。線形結合演算の例は和であり、例えば、拡大体上の和（ｐ＝２の場合にはｗ個の元のそれぞれでの排他的論理和）である。
【００１３】
検知符号Ｃの長さを処理単位ブロックＢｑの長さと同一にしてもよい。例えば、検知機能付加装置が、部分検知符号Ｃ０，…，ＣＭ−１をＫ個の部分集合Ｓｕｂ０，…，ＳｕｂＫ−１に区分し、部分集合Ｓｕｂ０，…，ＳｕｂＫ−１のそれぞれについて部分集合Ｓｕｂｋの要素の線形結合演算を行って、Ｋ個の中間検知符号ＳＣ０，…，ＳＣＫ−１を得、中間検知符号ＳＣ０，…，ＳＣＫ−１からなる長さがＬのＫ倍である列を検知符号Ｃとしてもよい。ただし、各部分検知符号Ｃｍの長さがＬであり、ｋ＝０，…，Ｋ−１である。これにより、処理単位ブロックＢ０，…，ＢＱ−１と検知符号Ｃとを同一長のブロックとして扱うことができ、取り扱い上の利便性が向上する。なお、Ｍ≧Ｋであってもよいし、Ｍ＜Ｋであってもよい。部分集合Ｓｕｂ０，…，ＳｕｂＫ−１は互いに重複する要素を含んでいてもよいし、含んでいなくてもよい。一部の部分集合Ｓｕｂｋ’（ただし、ｋ’∈｛０，…，Ｋ−１｝）が空集合であってもよく、それに対応する中間検知符号ＳＣｋ’が固定値であってもよい。検知機能の面からは、Ｋ個の部分集合Ｓｕｂ０，…，ＳｕｂＫ−１の和集合が部分検知符号Ｃ０，…，ＣＭ−１を要素とする集合Ｓｅｔとなることが望ましいが、この和集合が集合Ｓｅｔの部分集合となってもよい。
【００１４】
また、本形態の部分検知符号Ｃｍはｍごとに独立しているため、検知機能付加装置が、いくつか複数のｍについて並列に前述の「乗算を含む演算」を行い、部分検知符号Ｃ０，…，ＣＭ−１を得てもよい。例えば、すべてのｍ＝０，…，Ｍ−１について並列にこの演算を行い、部分検知符号Ｃ０，…，ＣＭ−１を得てもよい。これにより、演算速度をさらに向上できる。
【００１５】
「乗算を含む演算」に特に限定はない。例えば、以下のように部分検知符号Ｃｍを得る演算であってもよい。ただし、Ｎ≧２であり、Ｒｍを任意値とする。
【数１】
0006023852.tif 000002
式（１）の例の場合、検知機能付加装置は、例えば、任意値Ｒｍを得、初期値Ｃ０，ｍ＝Ｒｍ２ｃ０，ｍを得、ｉ＝０，…，Ｎ−２での再帰処理によって中間値Ｃｉ＋１，ｍ＝（ｃｉ＋１，ｍ＋Ｃｉ，ｍ）Ｒｍを得、ＣＮ−１，ｍを部分検知符号Ｃｍとする。任意値Ｒｍの例は、擬似乱数、乱数、または定数である。その他、Ｃｍ＝ｃ０，ｍＲｍＮ＋１＋ｃ１，ｍＲｍＮ…＋ｃＮ−１，ｍＲｍであってもよいし、Ｃｍ＝ｃ０，ｍｃ１，ｍ…ｃＮ−１，ｍであってもよいし、Ｃｍ＝ｃ０，ｍＲｍ＋ｃ１，ｍＲｍ…＋ｃＮ−１，ｍＲｍであってもよい。
【００１６】
処理単位ブロックＢ０，…，ＢＱ−１またはブロックｂ０，…，ｂＮ−１および検知符号Ｃは検知装置に入力される。説明の便宜上、検知装置で扱う処理単位ブロックＢ０，…，ＢＱ−１を「処理単位ブロックＢ’０，…，Ｂ’Ｑ−１」と表記し、ブロックｂ０，…，ｂＮ−１を「ブロックｂ’０，…，ｂ’Ｎ−１」と表記し、検知符号Ｃを「入力符号Ｃ’」と表記する。上述と同様、各ブロックｂ’ｎはＭ個の部分列ｃ’ｎ，０，…，ｃ’ｎ，Ｍ−１を含む。部分列ｃ’ｎ，０，…，ｃ’ｎ，Ｍ−１は前述の部分列ｃｎ，０，…，ｃｎ，Ｍ−１と同じ基準に基づいて区分される。検知装置は、部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍに対して乗算を含む演算を行って部分検知符号Ｃ’ｍを得、部分検知符号Ｃ’０，…，Ｃ’Ｍ−１を被演算子とした線形結合演算を行って検知符号Ｃ”を得、入力符号Ｃ’と検知符号Ｃ”とが一致するかを判定する。ここで、Ｃ’＝Ｃ”であれば成功とし、そうでなければ失敗とする。
【００１７】
［第１実施形態］
図面を参照して、第１実施形態を説明する。
＜構成＞
図１に例示するように、本形態の検知システム１は、検知機能付加装置１１および検知装置１２を有し、インターネット等の安全ではないネットワーク１３を通じて通信可能に構成されている。検知機能付加装置１１は、入力部１１１、区分部１１２、部分処理部１１３、統合部１１４、合成部１１５、および出力部１１６を有する。図２Ａに例示するように、部分処理部１１３は、例えば、制御部１１３０、任意値選択部１１３１、初期値生成部１１３２−０〜１１３２−（Ｍ−１）、および再帰処理部１１３３−０〜１１３３−（Ｍ−１）を有する。
【００１８】
検知装置１２は、入力部１２１、区分部１２２、部分処理部１２３、統合部１２４、および判定部１２６を有する。図２Ｂに例示するように、部分処理部１２３は、例えば、制御部１２３０、初期値生成部１２３２−０〜１２３２−（Ｍ−１）、および再帰処理部１２３３−０〜１２３３−（Ｍ−１）を有する。
【００１９】
各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）およびＲＡＭ（random-access memory）・ＲＯＭ（read-only memory）等のメモリ等を備える汎用または専用のコンピュータが所定のプログラムを実行することで構成される装置である。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。
【００２０】
＜検知機能付加処理＞
検知機能付加装置１１（図１）が、入力されたＱ個の処理単位ブロックＢ０，…，ＢＱ−１に検知符号Ｃを付加する処理を説明する。図３に例示するように、まず、入力部１１１に処理単位ブロックＢ０，…，ＢＱ−１が入力される。処理単位ブロックＢ０，…，ＢＱ−１の例は、ブロック暗号方式の暗号文に含まれたブロックである。ただし、これは本発明を限定するものではない。例えば、時間フレームごとに区分された時系列データ、周波数バンドごとに区分された周波数領域データ、その他の区分データを処理単位ブロックＢ０，…，ＢＱ−１としてもよい。また、本形態の処理単位ブロックＢｑ（ただし、ｑ＝０，…，Ｑ−１）は、Ｋ×Ｌ個の有限体Ｆ（ｐ）の元からなる列（長さＫ×Ｌ）である。例えば、ｐ＝２、Ｌ＝６４、Ｋ＝２、ｗ＝１２８の場合、処理単位ブロックＢｍは１２８ビット列である。入力された処理単位ブロックＢ０，…，ＢＱ−１は、区分部１１２および合成部１１５に送られる（ステップＳ１１１）。
【００２１】
区分部１１２は、処理単位ブロックＢ０，…，ＢＱ−１からブロックｂ０，…，ｂＮ−１を得、さらに各ブロックｂｍから部分列ｃ０，ｍ，…，ｃＮ−１，ｍ（ただし、ｍ＝０，…，Ｍ−１）を得るか、または、処理単位ブロックＢ０，…，ＢＱ−１から直接に部分列ｃ０，ｍ，…，ｃＮ−１，ｍ（ただし、ｍ＝０，…，Ｍ−１）を得る。本形態の各ブロックｂｎ（ただし、ｎ＝０，…，Ｎ−１）は、Ｍ×Ｌ個の有限体Ｆ（ｐ）の元からなる列（長さＭ×Ｌ）であり、Ｍ個の部分列ｃｎ，０，…，ｃｎ，Ｍ−１からなる。本形態の各部分列ｃｎ，ｍ（ただし、ｎ＝０，…，Ｎ−１）は、Ｌ個の有限体Ｆ（ｐ）の元からなる列（長さＬ）であり、拡大次数Ｌの拡大体Ｆ（ｐＬ）の元である。図６Ａおよび図６Ｂは、Ｋ＝ＭかつＱ＝Ｎの場合の例である。この場合には、処理単位ブロックＢｑがそのままブロックｂｎとなり、区分部１１２は処理単位ブロックＢｑ＝ｂｎをＫ等分して部分列ｃｎ，０，…，ｃｎ，Ｍ−１を得る。この場合、Ｂｑ＝ｂｎ＝（ｃｎ，０，…，ｃｎ，Ｍ−１）を満たす。図７Ａおよび図７Ｂは、Ｋ＜ＭかつＱ＞ＮかつＫ×Ｌ×Ｑ＝Ｍ×Ｌ×Ｎの場合の例である。この場合、区分部１１２は、処理単位ブロック（Ｂ０，…，ＢＱ−１）全体をＭ×Ｎ等分して部分列ｃ０，０，…，ｃ０，Ｍ−１，…，ｃＮ−１，０，…，ｃＮ−１，Ｍ−１を得る。図８Ａは、Ｍ＞ＫかつＫ×Ｌ×Ｑ＜Ｍ×Ｌ×Ｎの例である。この場合、区分部１１２は、処理単位ブロックＢ０，…，ＢＱ−１に長さＭ×Ｌ×Ｎ−Ｋ×Ｌ×ＱのパディングＰＤ（すなわち、Ｍ×Ｌ×Ｎ−Ｋ×Ｌ×Ｑ個の有限体Ｆ（ｐ）の元からなる列）を付加し、（Ｂ０，…，ＢＱ−１，ＰＤ）全体をＭ×Ｎ等分して部分列ｃ０，０，…，ｃ０，Ｍ−１，…，ｃＮ−１，０，…，ｃＮ−１，Ｍ−１を得る。図８Ｂは、Ｍ＜ＫかつＱ＜ＮかつＫ×Ｌ×Ｑ＝Ｍ×Ｌ×Ｎの場合の例である。この場合、区分部１１２は、処理単位ブロック（Ｂ０，…，ＢＱ−１）全体をＭ×Ｎ等分して部分列ｃ０，０，…，ｃ０，Ｍ−１，…，ｃＮ−１，０，…，ｃＮ−１，Ｍ−１を得る。図８Ｃは、Ｍ＜ＫかつＫ×Ｌ×Ｑ＜Ｍ×Ｌ×Ｎの例である。この場合、区分部１１２は、処理単位ブロックＢ０，…，ＢＱ−１に長さＭ×Ｌ×Ｎ−Ｋ×Ｌ×ＱのパディングＰＤを付加し、（Ｂ０，…，ＢＱ−１，ＰＤ）全体をＭ×Ｎ等分して部分列ｃ０，０，…，ｃ０，Ｍ−１，…，ｃＮ−１，０，…，ｃＮ−１，Ｍ−１を得る。部分列ｃ０，ｍ，…，ｃＮ−１，ｍ（ただし、ｍ＝０，…，Ｍ−１）は部分処理部１１３に送られる（ステップＳ１１２）
【００２２】
部分処理部１１３は、入力された部分列ｃ０，ｍ，…，ｃＮ−１，ｍに対し、拡大体Ｆ（ｐＬ）上で乗算を含む演算を行って部分検知符号Ｃｍ∈Ｆ（ｐＬ）（ただし、ｍ＝０，…，Ｍ−１）を得る（図６Ｂおよび図７Ｂ）。部分処理部１１３は、各ｍについて順番にこの演算を行ってもよいし、いくつか複数のｍについて並列にこの演算を行ってもよい。
【００２３】
≪部分処理部１１３の処理の具体例≫
Ｎ≧２であり、すべてのｍ＝０，…，Ｍ−１について並列に前述の式（１）の演算を行って部分検知符号Ｃ０，…，ＣＭ−１を得る例を示す。
【００２４】
図４に例示するように、部分処理部１１３の制御部１１３０（図２Ａ）がｉ：＝０に設定する。なお、「α：＝β」はαがβであると定義すること（αにβを代入すること）を意味する（ステップＳ１１３０ａ）。任意値選択部１１３１は、Ｍ個の任意値Ｒ０，…，ＲＭ−１を得る。ただし、Ｒｍ∈Ｆ（ｐＬ）である。例えば、任意値選択部１１３１は、Ｍ×Ｌ個の拡大体Ｆ（ｐＬ）の元からなる擬似乱数列Ｒを生成し、Ｒ：＝（Ｒ０，…，ＲＭ−１）とする。擬似乱数に代え、予め定められたＭ×Ｌ個の拡大体Ｆ（ｐＬ）の元（例えば、零元）からなる列（零ブロック）をＲとしてもよい。各任意値Ｒｍ（ただし、ｍ＝０，…，Ｍ−１）は初期値生成部１１３２−ｍおよび再帰処理部１１３３−ｍに送られる（ステップＳ１１３１）。各初期値生成部１１３２−ｍは、部分列ｃ０，ｍおよび任意値Ｒｍを入力とし、初期値Ｃ０，ｍ：＝Ｒｍ２ｃ０，ｍ∈Ｆ（ｐＬ）を得て出力する。これらは各ｍ＝０，…，Ｍ−１について並列に実行され、（Ｃ０，０，…，Ｃ０，Ｍ−１）：＝（Ｒｍ２ｃ０，０，…，Ｒｍ２ｃ０，Ｍ−１）が得られる。各初期値Ｃ０，ｍは再帰処理部１１３３−ｍに送られる（ステップＳ１１３２）。各再帰処理部１１３３−ｍは、Ｃｉ，ｍ，ｃｉ＋１，ｍ，Ｒｍを用い、中間値Ｃｉ＋１，ｍ：＝（ｃｉ＋１，ｍ＋Ｃｉ，ｍ）Ｒｍ∈Ｆ（ｐＬ）を得る。これらも並列に実行され、（Ｃｉ＋１，０，…，Ｃｉ＋１，Ｍ−１）：＝（（ｃｉ＋１，０＋Ｃｉ，０）Ｒ０，…，（ｃｉ＋１，Ｍ−１＋Ｃｉ，Ｍ−１）ＲＭ−１）が得られる（ステップＳ１１３３ａ）。制御部１１３０は、ｉ＝Ｎ−２であるかを判定する。ここで、ｉ＝Ｎ−２でなければ、制御部１１３０は、ｉ＋１を新たなｉ（すなわち、ｉ：＝ｉ＋１）とし（ステップＳ１１３０ｃ）、処理をステップＳ１１３３ａに戻す。一方、ｉ＝Ｎ−２であれば、各再帰処理部１１３３−ｍは、ＣＮ−１，ｍを部分検知符号Ｃｍ∈Ｆ（ｐＬ）として出力する。これにより、部分検知符号Ｃ０，…，ＣＭ−１が得られる（ステップＳ１１３３ｂ）。
【００２５】
得られた部分検知符号Ｃ０，…，ＣＭ−１は統合部１１４に送られる（ステップＳ１１３）。
【００２６】
統合部１１４は、部分検知符号Ｃ０，…，ＣＭ−１に対応する検知符号Ｃ∈Ｆ（ｐＬ）を得て出力する（図６Ｂおよび図７Ｂ）。例えば、Ｃ＝（Ｃ０，…，ＣＭ−１）としてもよいし、部分検知符号Ｃ０，…，ＣＭ−１を被演算子とした線形結合演算を行って検知符号Ｃを得てもよい。この線形結合演算は拡大体Ｆ（ｐＬ）上で実行される。以下に線形結合演算の具体例を示す。
【００２７】
≪例１≫
【数２】
0006023852.tif 000003
【００２８】
≪例２≫
【数３】
0006023852.tif 000004
ただし、ｍｅｖｅｎは０以上Ｍ−１以下の偶数を表し、ｍｏｄｄは０以上Ｍ−１以下の奇数を表す。
【００２９】
得られた検知符号Ｃは合成部１１５に入力される。検知符号Ｃの生成過程で任意値Ｒ０，…，ＲＭ−１が利用された場合には、これらの任意値Ｒ０，…，ＲＭ−１も合成部１１５に送られる。ただし、任意値Ｒ０，…，ＲＭ−１が予め定められた値である場合にはこれらが合成部１１５に送られなくてもよい（ステップＳ１１４）。
【００３０】
合成部１１５は、処理単位ブロックＢ０，…，ＢＱ−１に検知符号Ｃを付加した列ＢＳ：＝（Ｂ０，…，ＢＱ−１，Ｃ）を得て出力する（図６Ｃ）。任意値Ｒ０，…，ＲＭ−１が入力された場合、合成部１１５は、さらにこれらを付加した列ＢＳ：＝（Ｂ０，…，ＢＱ−１，Ｃ，Ｒ０，…，ＲＭ−１）を得て出力してもよい（図７Ｃ）（ステップＳ１１４）。列ＢＳは出力部１１６から出力され、ネットワーク１３を通じて検知装置１２に送られる（ステップＳ１１６）。
【００３１】
＜検知処理＞
次に、検知装置１２（図１）による検知処理を説明する。図３に例示するように、まず検知装置１２に列ＢＳが入力される。列ＢＳは（Ｂ’０，…，Ｂ’Ｑ−１，Ｃ’）または（Ｂ’０，…，Ｂ’Ｑ−１，Ｃ’，Ｒ’０，…，Ｒ’Ｍ−１）である。列ＢＳに改ざんや誤りがなければ、（Ｂ’０，…，Ｂ’Ｑ−１）は（Ｂ０，…，ＢＱ−１）であり、Ｃ’はＣであり、（Ｒ’０，…，Ｒ’Ｍ−１）は（Ｒ０，…，ＲＭ−１）である。列ＢＳは区分部１２２に送られ、列ＢＳが含む入力符号Ｃ’は判定部１２６に送られる（ステップＳ１２１）。
【００３２】
区分部１２２は、前述の区分部１１２と同じ基準に則って、列ＢＳに含まれた処理単位ブロックＢ’０，…，Ｂ’Ｑ−１からブロックｂ’０，…，ｂ’Ｎ−１を得、さらに各ブロックｂ’ｍから部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍ（ただし、ｍ＝０，…，Ｍ−１）を得るか、または、処理単位ブロックＢ’０，…，Ｂ’Ｑ−１から直接に部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍ（ただし、ｍ＝０，…，Ｍ−１）を得る。本形態の各ブロックｂ’ｎ（ただし、ｎ＝０，…，Ｎ−１）は、Ｍ×Ｌ個の有限体Ｆ（ｐ）の元からなる列（長さＭ×Ｌ）であり、Ｍ個の部分列ｃ’ｎ，０，…，ｃ’ｎ，Ｍ−１からなる。本形態の各部分列ｃ’ｎ，ｍ（ただし、ｎ＝０，…，Ｎ−１）は、Ｌ個の有限体Ｆ（ｐ）の元からなる列（長さＬ）であり、拡大次数Ｌの拡大体Ｆ（ｐＬ）の元である。部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍ（ただし、ｍ＝０，…，Ｍ−１）は部分処理部１２３に送られる。ＢＳ＝（Ｂ’０，…，Ｂ’Ｑ−１，Ｃ’，Ｒ’０，…，Ｒ’Ｍ−１）の場合には、（Ｒ’０，…，Ｒ’Ｍ−１）も部分処理部１２３に送られる（ステップＳ１２２）
【００３３】
部分処理部１２３は、前述の部分処理部１１３と同じ基準に則って、入力された部分列ｃ’０，ｍ，…，ｃ’Ｎ−１，ｍに対し、拡大体Ｆ（ｐＬ）上で乗算を含む演算を行って部分検知符号Ｃ’ｍ∈Ｆ（ｐＬ）（ただし、ｍ＝０，…，Ｍ−１）を得る。部分処理部１２３は、各ｍについて順番にこの演算を行ってもよいし、いくつか複数のｍについて並列にこの演算を行ってもよい。
【００３４】
≪部分処理部１２３の処理の具体例≫
Ｎ≧２であり、すべてのｍ＝０，…，Ｍ−１について並列に前述の式（１）の演算を行って部分検知符号Ｃ’０，…，Ｃ’Ｍ−１を得る例を示す。
【００３５】
図５に例示するように、部分処理部１２３の制御部１２３０（図２Ｂ）がｉ：＝０に設定する（ステップＳ１２３０ａ）。各初期値生成部１２３２−ｍは、部分列ｃ’０，ｍおよび任意値Ｒ’ｍを用い、初期値Ｃ’０，ｍ：＝Ｒ’ｍ２ｃ’０，ｍ∈Ｆ（ｐＬ）を得て出力する。なお、任意値Ｒ’ｍは区分部１２２から送られたものであるか、予め定められた値（Ｒ’ｍ＝Ｒｍ）である。これらは各ｍ＝０，…，Ｍ−１について並列に実行され、（Ｃ’０，０，…，Ｃ’０，Ｍ−１）：＝（Ｒ’ｍ２ｃ０，０，…，Ｒ’ｍ２ｃ’０，Ｍ−１）が得られる。各初期値Ｃ’０，ｍは再帰処理部１２３３−ｍに送られる（ステップＳ１２３２）。各再帰処理部１２３３−ｍは、Ｃ’ｉ，ｍ，ｃ’ｉ＋１，ｍ，Ｒ’ｍを用い、中間値Ｃ’ｉ＋１，ｍ：＝（ｃ’ｉ＋１，ｍ＋Ｃ’ｉ，ｍ）Ｒ’ｍ∈Ｆ（ｐＬ）を得る。これらも並列に実行され、（Ｃ’ｉ＋１，０，…，Ｃ’ｉ＋１，Ｍ−１）：＝（（ｃ’ｉ＋１，０＋Ｃ’ｉ，０）Ｒ’０，…，（ｃ’ｉ＋１，Ｍ−１＋Ｃ’ｉ，Ｍ−１）Ｒ’Ｍ−１）が得られる（ステップＳ１２３３ａ）。制御部１２３０は、ｉ＝Ｎ−２であるかを判定する。ここで、ｉ＝Ｎ−２でなければ、制御部１２３０は、ｉ＋１を新たなｉ（すなわち、ｉ：＝ｉ＋１）とし（ステップＳ１２３０ｃ）、処理をステップＳ１２３３ａに戻す。一方、ｉ＝Ｎ−２であれば、各再帰処理部１２３３−ｍは、Ｃ’Ｎ−１，ｍを部分検知符号Ｃ’ｍ∈Ｆ（ｐＬ）として出力する。これにより、部分検知符号Ｃ’０，…，Ｃ’Ｍ−１が得られる（ステップＳ１２３３ｂ）。
【００３６】
得られた部分検知符号Ｃ’０，…，Ｃ’Ｍ−１は統合部１２４に送られる（ステップＳ１２３）。
【００３７】
統合部１２４は、前述の統合部１１４と同じ基準に則って、部分検知符号Ｃ’０，…，Ｃ’Ｍ−１に対応する検知符号Ｃ”∈Ｆ（ｐＬ）を得て出力する。検知符号Ｃ”は判定部１２６に送られる（ステップＳ１２４）。
【００３８】
判定部１２６は、入力符号Ｃ’と検知符号Ｃ”との等号判定を行う。ここで、Ｃ’＝Ｃ”であれば、判定部１２６は、成功である（改ざんおよび誤りが存在しない）旨の結果を出力し（ステップＳ１２５２）、処理を終了する。一方、Ｃ’≠Ｃ”であれば、判定部１２６は、失敗である（改ざんまたは誤りが存在する）旨の結果を出力し（ステップＳ１２５３）、処理を終了する。
【００３９】
［第２実施形態］
本形態は第１実施形態の変形例であり、検知符号Ｃの長さを処理単位ブロックＢｑの長さと同一にする。本形態では、検知機能付加装置が、部分検知符号Ｃ０，…，ＣＭ−１をＫ個の部分集合Ｓｕｂ０，…，ＳｕｂＫ−１に区分し、部分集合Ｓｕｂ０，…，ＳｕｂＫ−１のそれぞれについて部分集合Ｓｕｂｋの要素の線形結合演算を行って、Ｋ個の中間検知符号ＳＣ０，…，ＳＣＫ−１を得、中間検知符号ＳＣ０，…，ＳＣＫ−１からなる長さがＬのＫ倍である列を検知符号Ｃとする。ただし、各部分検知符号Ｃｍの長さはＬであり、ｋ＝０，…，Ｋ−１であり、Ｍ≧Ｋである。以下ではこれまで説明した事項との相違点を中心に説明し、すでに説明した事項については既に使用された参照番号を引用して説明を簡略化する。
【００４０】
＜構成＞
図１に例示するように、本形態の検知システム２は、検知機能付加装置２１および検知装置２２を有し、インターネット等の安全ではないネットワーク１３を通じて通信可能に構成されている。検知機能付加装置２１は、入力部１１１、区分部１１２、部分処理部１１３、統合部２１４、合成部１１５、および出力部１１６を有する。検知装置２２は、入力部１２１、区分部１２２、部分処理部１２３、統合部２２４、および判定部１２６を有する。図９Ａに例示するように、本形態の統合部２１４は、区分部２１４１、線形結合部２１４２−０〜２１４２−（Ｋ−１）、および統合部２１４３を有する。図９Ｂに例示するように、本形態の統合部２２４は、区分部２２４１、線形結合部２２４２−０〜２２４２−（Ｋ−１）、および統合部２１４３を有する。
【００４１】
＜検知機能付加処理＞
第１実施形態との相違点は、ステップＳ１１４がステップＳ２１４に置換される点である。以下ではステップＳ２１４の処理のみを説明する。
【００４２】
≪ステップＳ２１４の処理≫
統合部２１４（図９Ａ）の区分部２１４１に部分検知符号Ｃ０，…，ＣＭ−１が入力される。区分部２１４１は、Ｍ個の部分検知符号Ｃ０，…，ＣＭ−１をＫ個の部分集合Ｓｕｂ０，…，ＳｕｂＫ−１に区分する（図１０Ａ）。この区分方法に限定はない。例えば、Ｋ＝２とし、ｍ＝ｍｅｖｅｎ（偶数）の部分検知符号Ｃｍを部分集合Ｓｕｂ０の要素とし、ｍ＝ｍｏｄｄ（奇数）の部分検知符号Ｃｍを部分集合Ｓｕｂ１の要素としてもよい。例えば、Ｋ＝２、Ｙを１＜Ｙ＜Ｍ−１の整数とし、Ｓｕｂ０＝｛Ｃ０，…，ＣＹ｝，Ｓｕｂ１＝｛ＣＹ−１，…，ＣＭ−１｝としてもよい。例えば、２以上の整数ＴについてＭ＝Ｋ×Ｔとし、Ｓｕｂｋ＝｛ＣＴ×ｋ，…，ＣＴ×ｋ＋Ｔ−１｝としてもよい。例えば、Ｋ＞Ｍとし、０≦ｋ≦Ｍ−１についてＳｕｂｋ＝｛Ｃｋ｝とし、Ｍ≦ｋ≦Ｋ−１についてＳｕｂｋ＝｛固定値｝としてもよい。各部分集合Ｓｕｂｋ（ただし、ｋ＝０，…，Ｋ−１）は、線形結合部２１４２−ｋに送られる。
【００４３】
各線形結合部２１４２−ｋは、入力された部分集合Ｓｕｂｋの要素の線形結合演算を行って中間検知符号ＳＣｋ∈Ｆ（ｐＬ）を得て出力する。例えば、各線形結合部２１４２−ｋは、部分集合Ｓｕｂｋの要素の和（拡大体Ｆ（ｐＬ）上の和）によって中間検知符号ＳＣｋ∈Ｆ（ｐＬ）を得る。例えば、ｍ＝ｍｅｖｅｎ（偶数）の部分検知符号Ｃｍを部分集合Ｓｕｂ０の要素とし、ｍ＝ｍｏｄｄ（奇数）の部分検知符号Ｃｍを部分集合Ｓｕｂ１の要素とした場合、以下のように中間検知符号ＳＣ０，ＳＣ１を得る。
【数４】
0006023852.tif 000005
得られたＫ個の中間検知符号ＳＣ０，…，ＳＣＫ−１は統合部２１４３に送られる（図１０Ａ）。なお、各中間検知符号ＳＣｋは同一の線形結合演算によって得られてもよいし、そうでなくてもよい。また、中間検知符号ＳＣ０，…，ＳＣＫ−１が並列に計算されてもよいし、そうでなくてもよい。
【００４４】
統合部２１４３は、入力された中間検知符号ＳＣ０，…，ＳＣＫ−１からなる長さがＬのＫ倍である列を検知符号Ｃとして出力する。例えば、Ｃ＝（ＳＣ０，…，ＳＣＫ−１）を出力する（図１０Ａ）。
【００４５】
このように得られた検知符号Ｃの長さは、処理単位ブロックＢｑの長さと同一（Ｋ×Ｌ）となり、列ＢＳを長さＫ×Ｌのブロックに統一することができる（図１０Ｂ）。
【００４６】
＜検知処理＞
第１実施形態との相違点は、ステップＳ１２４がステップＳ２２４に置換される点である。以下ではステップＳ２２４の処理のみを説明する。
【００４７】
≪ステップＳ２２４の処理≫
統合部２２４（図９Ｂ）の区分部２２４１に部分検知符号Ｃ’０，…，Ｃ’Ｍ−１が入力される。区分部２２４１は、区分部２１４１と同じ基準に則って、Ｍ個の部分検知符号Ｃ’０，…，Ｃ’Ｍ−１をＫ個の部分集合Ｓｕｂ’０，…，Ｓｕｂ’Ｋ−１に区分する。各部分集合Ｓｕｂ’ｋ（ただし、ｋ＝０，…，Ｋ−１）は、線形結合部２２４２−ｋに送られる。
【００４８】
各線形結合部２２４２−ｋは、線形結合部２１４２−ｋと同じ基準に則って、入力された部分集合Ｓｕｂ’ｋの要素の線形結合演算を行って中間検知符号ＳＣ’ｋ∈Ｆ（ｐＬ）を得て出力する。得られたＫ個の中間検知符号ＳＣ’０，…，ＳＣ’Ｋ−１は統合部２２４３に送られる。
【００４９】
統合部２２４３は、統合部２１４３と同じ基準に則って、入力された中間検知符号ＳＣ’０，…，ＳＣ’Ｋ−１からなる長さがＬのＫ倍である列を検知符号Ｃ’として出力する。
【００５０】
［その他の変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。
【００５１】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５３】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５５】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００５６】
各実施形態の技術は、例えば、ブロック暗号方式の暗号文の改ざん検知や誤り検知に利用できる。
【符号の説明】
【００５７】
１，２  検知システム
１１，２１  検知機能付加装置
１２，２２  検知装置
【要約】
【課題】改ざんや誤りの検知機能を付加するための演算を高速化する。
【解決手段】Ｎが１以上の整数であり、Ｍが２以上の整数であり、ｎ＝０，…，Ｎ−１であり、ｍ＝０，…，Ｍ−１であり、Ｎ個のブロックｂ０，…，ｂＮ−１のそれぞれのブロックｂｎがＭ個の部分列ｃｎ，０，…，ｃｎ，Ｍ−１を含むものとする。部分列ｃ０，ｍ，…，ｃＮ−１，ｍに対して乗算を含む演算を行って部分検知符号Ｃｍを得、部分検知符号Ｃ０，…，ＣＭ−１に対応する検知符号を得る。
【選択図】図１【図１】
0006023852.tif 000006
【図２】
0006023852.tif 000007
【図３】
0006023852.tif 000008
【図４】
0006023852.tif 000009
【図５】
0006023852.tif 000010
【図６】
0006023852.tif 000011
【図７】
0006023852.tif 000012
【図８】
0006023852.tif 000013
【図９】
0006023852.tif 000014
【図１０】
0006023852.tif 000015