JP4851077B2 - データ変換装置およびその方法 - Google Patents

Description

本発明は、認証方式などに使用されるデータ変換方式を実現するデータ変換装置およびその方法に関し、特に小さな実装規模で実現でき、かつ高いデータ撹乱性能有するデータ変換装置およびその方法に関する。

通信相手の正当性を確認する手段の一つであるチャレンジ−レスポンス認証方式などでは、認証側および被認証側において秘密の変換方式が必要となる。秘密の変換方式に望まれる要件としては、高いデータ撹乱性能（アバランシェ性能）のみならず、その方式を低コストで機器に実装できることが望まれる。

データ変換方式の従来例として、秘密鍵暗号方式を用いる方式がある。例えば、５６ビット鍵長ＤＥＳ（Ｄａｔａ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）暗号方式（ＤＥＳ暗号方式の詳細は、非特許文献１参照）を用いたデータ変換方式によってチャレンジ−レスポンス認証方式を実現する場合には、ＤＥＳ暗号方式の５６ビット鍵を認証用鍵として認証側、被認証側の双方で秘密に保持する。また、ＤＥＳ暗号方式の平文および暗号文をそれぞれデータ変換方式の入力および出力とする。これにより、ＤＥＳ暗号方式を、認証用の秘密のデータ変換方式として使用することができる（認証方式の詳細は、非特許文献１参照）。
岡本龍明、山本博資「現代暗号」（産業図書）、１９９７年

しかしながら、ＤＥＳ暗号方式などの秘密鍵暗号方式は、暗号回路とともに機器内で実装される他の回路との回路共有化を考慮したような方式とはなっておらず、このため、他の回路とは独立の回路として実装する必要がある。従って、従来例の秘密鍵暗号方式を用いたデータ変換方式においては、機器内に実装される他の回路とは全く独立して暗号回路を実装することになり、機器全体として回路規模が大きくなる。つまり、一般に機器を低コストで実現するためには、機器に実装される回路の総規模は極力小さくすることが要求されるので、機器に実装する暗号回路としては、他の回路と共有化できる方が望ましいが、前記従来の構成では、それが実現されていないという課題を有している。

本発明は、上述の課題を解決するためになされたものであり、機器内の総実装規模を削減することが可能なデータ変換装置を提供することを目的とする。

本発明のデータ変換装置は、入力データを複数のデータに分割する分割手段と、前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数によるべき乗演算に基づく変換を行うべき乗手段と、前記べき乗手段で変換された後の前記複数のデータに基づいて出力データを生成する出力データ生成手段とを備え、前記所定のべき数は３以上であり、かつ２^m（ｍは１以上の整数）以外の値であることを特徴とする。

この構成によると、べき乗ステップにおいて、多項式剰余環上の乗算が行なわれる。多項式剰余環上の演算を行なうと、後述するように入力データの一部でも変更されると、その影響が出力データのあらゆるビットに及ぶことになる。このため、データ撹乱性を向上させることができる。また、２つ以上の変数の乗算を行なった場合には、いずれか１つの変数が０の場合には、その他の変数がどのような値であっても乗算結果が０となり、良好なデータ撹乱性能を示さないが、入力データのべき乗の場合には、このような問題が生じず、データの撹乱性を向上させることができる。さらに、べき乗ステップでは、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における演算を行なっている。Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号や、ＢＣＨ（Bose-Chaudhuri-Hocqenghem）符号などの誤り訂正符号化回路で使用される有限体ＧＦ（２ⁿ）上の演算回路との回路共有が可能となる。このため、機器全体としての実装規模が削減でき、コンパクトな回路規模での機器実装が実現される。

以下本発明の実施の形態について、図面を参照しながら説明する。
（データ変換装置を利用した認証システムの構成）
図１は、本発明の実施の形態に係る認証システムの構成を示すブロック図である。この認証システムは、認証装置３が被認証装置４をチャレンジ−レスポンス認証方式によって認証する。本認証システムとしては、例えば認証装置３を自動車のドアの開錠および施錠を制御する車載機とし、被認証装置４をユーザが自動車のドアの開錠および施錠のために携帯する携帯端末とする自動車のキーレスエントリシステムなどが具体的に考えられる。

認証装置３は、乱数生成器５において６４ビットの乱数データを生成し、これをチャレンジデータとして被認証装置４に送付する。被認証装置４は、受信したチャレンジデータに対してデータ変換装置２においてデータ変換処理を行ない、変換結果である６４ビット変換データをレスポンスデータとして認証装置３に送付する。認証装置３は、被認証装置４が上述の処理を行っている間に前記乱数データに対してデータ変換装置１においてデータ変換処理を行ない、変換結果である６４ビット変換データを作成する。そして、認証装置３は、被認証装置４から受信した前記レスポンスデータと前記の変換データとをデータ比較器６において比較し、両者が一致する場合に限り被認証装置４を正当なものであるとして認証する。ここで、認証装置３内部のデータ変換装置１および被認証装置４内部のデータ変換装置２は同一の変換処理を行ない、その処理内容は認証装置３および被認証装置４の間で秘密に共有化されている。

（データ変換装置１、２の構成）
データ変換装置１、２は同一の構成であるから、以下ではデータ変換装置１の内部構成のみについて説明する。

図２は、データ変換装置１の内部構成を示した図である。データ変換装置１は、６４ビットの入力データに対して所定の秘密変換処理を行ない６４ビットの出力データを生成する処理装置であり、有限体多項式３乗部１０と、データ融合部１１ａ〜１１ｄ、１２および１３と、第１変換部１４と、第２変換部１５と、データ分割部１６と、データ結合部１７とからなる。以下、６４ビットの入力データが入力されたときの内部動作について説明する。

まず、データ分割部１６が、前記入力データを上位から３２ビットずつ２つのデータに分割する。ここでは２つのデータを、上位からデータＡ、データＢとする。データＡはデータ融合部１１ａおよび１１ｃに、データＢはデータ融合部１１ｂおよび１１ｄにそれぞれ入力される。データ融合部１１ａおよび１１ｃは、入力された３２ビットデータＡに対して、固定の３２ビットデータＫ１およびＫ３とのビット毎の排他的論理和演算（ＸＯＲ）をそれぞれ行ない、３２ビットデータＡ０およびＡ１をそれぞれ出力する。また、データ融合部１１ｂおよび１１ｄは、入力された３２ビットデータＢに対して、固定の３２ビットデータＫ２およびＫ４とのビット毎の排他的論理和演算（ＸＯＲ）をそれぞれ行ない、３２ビットデータＢ０およびＢ１をそれぞれ出力する。ここで、３２ビットデータＫ１〜Ｋ４は、予め所定の値に定められた固定値である。

次に、有限体多項式３乗部１０は、上記３２ビットデータＡ０、Ｂ０、Ａ１およびＢ１のそれぞれに対して、後で述べる有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の３乗算を行ない、それぞれ３２ビットデータ（Ａ０）³、（Ｂ０）³、（Ａ１）³、（Ｂ１）³を算出する。有限体多項式３乗部１０の処理の詳細については後に説明する。

次に、３２ビットデータ（Ａ０）³および（Ｂ０）³は、データ融合部１２に入力され、３２ビットデータ（Ａ１）³および（Ｂ１）³は、データ融合部１３に入力される。

データ融合部１２およびデータ融合部１３は、入力されたそれぞれ２つの３２ビットデータに対してビット毎の排他的論理和演算を行ない、３２ビットデータ（Ａ０）³（＋）（Ｂ０）³および（Ａ１）³（＋）（Ｂ１）³をそれぞれ出力する。ここで、「Ｘ（＋）Ｙ」はＸとＹとのビット毎の排他的論理和演算（ＸＯＲ）を意味する。

次に第１変換部１４は、３２ビットデータ（Ａ０）³（＋）（Ｂ０）³に対して後で説明する有限体ＧＦ（２⁸）上の演算に基づく所定の変換を行ない、３２ビットデータＧ０を出力する。また、第２変換部１５は、前記（Ａ１）³（＋）（Ｂ１）³に対して後で説明する有限体ＧＦ（２⁸）上の演算に基づく所定の変換を行ない、３２ビットデータＧ１を出力する。

以上の処理の後、データ結合部１７は、前記３２ビットデータＧ０を上位３２ビット、前記３２ビットデータＧ１を下位３２ビットとしてデータ連結し、その結果を６４ビットデータとして出力する。この６４ビットデータが、データ変換装置１の出力データとなる。次に、有限体多項式３乗部１０の内部構成と動作について説明する。

（有限体多項式３乗部１０の内部構成）
図３は、有限体多項式３乗部１０の内部構成の一例を示した図である。有限体多項式３乗部１０は、有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の３乗算を行なう処理部であり、入力制御部１０１と、有限体多項式乗算部１００と、出力制御部１０２とからなる。

入力制御部１０１は、二つの入力データのうちどちらか一方を出力するような制御を行なう。有限体多項式乗算部１００は、二つの入力データに対して有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の乗算を行なう。出力制御部１０２は、入力データを二つの出力先のうちどちらか一方に出力するような制御を行なう。

以下、有限体多項式３乗部１０に、３２ビットの入力データＸが入力された場合の内部動作について説明する。入力データＸは、入力制御部１０１および有限体多項式乗算部１００に入力される。入力制御部１０１は、前記入力データＸをそのまま有限体多項式乗算部１００に入力する。有限体多項式乗算部１００は、外部より入力された３２ビットデータＸと入力制御部１０１より入力された３２ビットデータＸとの有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の乗算（詳細は後で説明する）を行ない、乗算結果Ｘ²を出力し、出力制御部１０２に入力する。有限体多項式乗算部１００の処理の詳細については後で説明する。

出力制御部１０２は、入力データＸ²をそのまま入力制御部１０１に入力する。そして、入力制御部１０１は、入力データＸ²を有限体多項式乗算部１００に入力する。

有限体多項式乗算部１００は、前記入力データＸ²と、入力データＸとの乗算を行ない、乗算結果Ｘ³を出力制御部１０２に入力する。このときの乗算は既に述べた通り多項式剰余環上の乗算である。

出力制御部１０２は、前記入力データＸ³を有限体多項式３乗部１０の出力データとして出力する。次に、有限体多項式乗算部１００の内部構成と動作について説明する。

（有限体多項式乗算部１００の内部構成）
図４は、有限体多項式乗算部１００の内部構成の一例を示した図である。有限体多項式乗算部１００は、３２ビットの第１入力データＸと３２ビットの第２入力データＹとの有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の乗算を行ない、３２ビットの出力データＤを出力する。このときの多項式剰余環の剰余多項式はＬ（Ｘ）＝Ｘ⁴−１とし、有限体ＧＦ（２⁸）の原始多項式ｍ（ｘ）はｍ（ｘ）＝ｘ⁸＋ｘ⁴＋ｘ³＋ｘ＋１とする。有限体多項式乗算部１００の動作説明の前に、有限体ＧＦ（２⁸）上の演算および多項式剰余環上の演算について簡単に説明する。

まず、有限体ＧＦ（２⁸）上の演算について説明する。有限体ＧＦ（２⁸）上の演算では、８ビットデータＡの各ビットの値を上位からａ７、ａ６、・・・、ａ０としたとき、７次の多項式ａ（ｘ）＝ａ７×ｘ⁷＋ａ６×ｘ⁶＋・・・＋ａ１×ｘ＋ａ０と対応づけて考える。同様に８ビットデータＢの各ビットを上位からｂ７、ｂ６、・・・、ｂ０として、７次の多項式ｂ（ｘ）＝ｂ７×ｘ⁷＋ｂ６＋ｘ⁶＋・・・＋ｂ１×ｘ＋ｂ０と対応づける。このとき、有限体ＧＦ（２⁸）上におけるＡとＢの加算結果Ｃは、ｃ（ｘ）＝ａ（ｘ）＋ｂ（ｘ）を有限体ＧＦ（２）上で計算した結果のｃ（ｘ）を上で説明した７次多項式と８ビットデータとの対応付けによって８ビットデータに変換した結果になる。即ち、ｃ（ｘ）＝ｃ７×ｘ⁷＋ｃ６＋ｘ⁶＋・・・＋ｃ１×ｘ＋ｃ０としたとき、
ｃ７＝ａ７＋ｂ７
ｃ６＝ａ６＋ｂ６
・・・ ・・・ ・・・
ｃ１＝ａ１＋ｂ１
ｃ０＝ａ０＋ｂ０
として求められる。ここで上記の１ビットデータどうしの加算「＋」は全て有限体ＧＦ（２）上で行われる。即ち、０＋０＝１＋１＝０であり０＋１＝１＋０＝１として計算される。

上記のことから有限体ＧＦ（２⁸）上の加算は、ビットごとの排他的論理和演算をしていることに他ならない。即ち、Ａ、Ｂに対する加算結果Ｃは、Ｃ＝Ａ（＋）Ｂである。

次に、有限体ＧＦ（２⁸）上の乗算について説明する。８ビットデータＡ、Ｂ、Ｃを前述のように、７次多項式ａ（ｘ）、ｂ（ｘ）、ｃ（ｘ）とした時、８ビットデータＡ、Ｂの乗算結果Ｃは、それぞれに対応する７次多項式ａ（ｘ）、ｂ（ｘ）、ｃ（ｘ）による以下の計算で求められる。

ｃ（ｘ）＝ａ（ｘ）×ｂ（ｘ） ｍｏｄ ｍ（ｘ）
ここで、「ｆ（ｘ） ｍｏｄ ｇ（ｘ）」は、ｇ（ｘ）を法とするｆ（ｘ）の剰余計算結果であり、ｍ（ｘ）は、前にも述べた通り有限体ＧＦ（２⁸）上の原始多項式ｍ（ｘ）＝ｘ⁸＋ｘ⁴＋ｘ³＋ｘ＋１である。また、このときの多項式乗算、剰余算における係数の加算、乗算は有限体ＧＦ（２）上で行なう。有限体ＧＦ（２）上の加算は既に述べたとおりであり、乗算は０×０＝０×１＝１×０＝０、１×１＝１として計算される。

上記の乗算の例を挙げる。Ａ＝５７（１６進数）、Ｂ＝８３（１６進数）としたとき、ａ（ｘ）＝ｘ⁶＋ｘ⁴＋ｘ²＋ｘ＋１、ｂ（ｘ）＝ｘ⁷＋ｘ＋１である。これより、ａ（ｘ）×ｂ（ｘ）＝ｘ¹³＋ｘ¹¹＋ｘ⁹＋ｘ⁸＋ｘ⁶＋ｘ⁵＋ｘ⁴＋ｘ³＋１となり、ａ（ｘ）×ｂ（ｘ） ｍｏｄ ｍ（ｘ）＝ｘ⁷＋ｘ⁶＋１となるので、Ａ、Ｂの乗算結果Ｃは１６進数でＣ１となる。

次に有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の演算について説明する。多項式剰余環上の演算では、３２ビットデータＡの各バイトを上位バイトからＡ０、Ａ１、Ａ２、Ａ３としたとき、１バイトデータＡ０〜Ａ３を３次の多項式Ａ（Ｘ）＝Ａ０＋Ａ１×Ｘ＋Ａ２×Ｘ²＋Ａ３×Ｘ³と対応づけて考える。同様に３２ビットデータＢ、Ｃの各バイトを上位バイトからＢ０、Ｂ１、Ｂ２、Ｂ３およびＣ０、Ｃ１、Ｃ２、Ｃ３としたとき、１バイトデータＢ０〜Ｂ３およびＣ０〜Ｃ３を３次の多項式Ｂ（Ｘ）＝Ｂ０＋Ｂ１×Ｘ＋Ｂ２×Ｘ²＋Ｂ３×Ｘ³およびＣ（Ｘ）＝Ｃ０＋Ｃ１×Ｘ＋Ｃ２×Ｘ²＋Ｃ３×Ｘ³とそれぞれ対応づけて考える。このとき、多項式剰余環上の加算はＣ（Ｘ）＝Ａ（Ｘ）＋Ｂ（Ｘ）として求められる。このときの多項式係数の加算は先ほど説明した有限体ＧＦ（２⁸）上の加算である。上記のことから言い換えると、３２ビットデータＡとＢとの加算は、単にビット毎の排他的論理和演算を行えば良いことになる。

次に、多項式剰余環上の乗算について説明する。３２ビットデータＡおよびＢの乗算結果を３２ビットデータＣとし、上記のように各データを３次の多項式Ａ（Ｘ）、Ｂ（Ｘ）およびＣ（Ｘ）と対応づけたとき、多項式剰余環上の乗算は、以下のような多項式演算で示される。

Ｃ（Ｘ）＝Ａ（Ｘ）×Ｂ（Ｘ） ｍｏｄ Ｌ（Ｘ）
ここで、Ｌ（Ｘ）は既に説明した通り、剰余多項式Ｌ（Ｘ）＝Ｘ⁴−１であり、上記の多項式係数の加算、乗算は有限体ＧＦ（２⁸）上で行われる。このため、上式は、以下のように計算される。

Ｃ（Ｘ）＝ Ａ０×Ｂ０
＋（Ａ０×Ｂ１＋Ａ１×Ｂ０）×Ｘ
＋（Ａ０×Ｂ２＋Ａ２×Ｂ０＋Ａ１×Ｂ１）×Ｘ²
＋（Ａ０×Ｂ３＋Ａ１×Ｂ２＋Ａ２×Ｂ１＋Ａ３×Ｂ０）×Ｘ³
＋（Ａ１×Ｂ３＋Ａ３×Ｂ１＋Ａ２×Ｂ２）×Ｘ⁴
＋（Ａ２×Ｂ３＋Ａ３×Ｂ２）×Ｘ⁵
＋（Ａ３×Ｂ３）×Ｘ⁶ （ｍｏｄ Ｘ⁴−１）
このとき、Ｘ４ ＝ １（ｍｏｄ Ｘ⁴−１）であることから、上記の式はさらに、以下のように変形できる。

Ｃ（Ｘ）＝ （Ａ０×Ｂ０＋Ａ３×Ｂ１＋Ａ２×Ｂ２＋Ａ１×Ｂ３）
＋（Ａ１×Ｂ０＋Ａ０×Ｂ１＋Ａ３×Ｂ２＋Ａ２×Ｂ３）×Ｘ
＋（Ａ２×Ｂ０＋Ａ１×Ｂ１＋Ａ０×Ｂ２＋Ａ３×Ｂ３）×Ｘ²
＋（Ａ３×Ｂ０＋Ａ２×Ｂ１＋Ａ１×Ｂ２＋Ａ０×Ｂ３）×Ｘ³
このことより、
Ｃ０＝Ａ０×Ｂ０＋Ａ３×Ｂ１＋Ａ２×Ｂ２＋Ａ１×Ｂ３
Ｃ１＝Ａ１×Ｂ０＋Ａ０×Ｂ１＋Ａ３×Ｂ２＋Ａ２×Ｂ３
Ｃ２＝Ａ２×Ｂ０＋Ａ１×Ｂ１＋Ａ０×Ｂ２＋Ａ３×Ｂ３
Ｃ３＝Ａ３×Ｂ０＋Ａ２×Ｂ１＋Ａ１×Ｂ２＋Ａ０×Ｂ３
としてＣは計算できることが分かる。このとき上記の加算「＋」、乗算「×」は有限体ＧＦ（２⁸）上で行われる。

以上で有限体ＧＦ（２⁸）上の演算および多項式剰余環上の演算について説明が終わったので、有限体多項式乗算部１００の動作説明を行なう。

有限体多項式乗算部１００は、二つの入力データに対して有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の乗算を行なう処理部であり、有限体乗算部１１０と、データ分割部１１１〜１１２と、データ加算部１１３〜１１５と、データ結合部１１６と、演算制御部１１７とからなる。

有限体乗算部１１０は、有限体ＧＦ（２⁸）上の乗算を行なう。データ分割部１１１〜１１２の各々は、３２ビットの入力データを４個の８ビットのデータに分割する。データ加算部１１３〜１１５の各々は、２つの入力データに対して有限体ＧＦ（２⁸）上の加算を行なう。データ結合部１１６は、４個の８ビットデータを結合して３２ビットデータとして出力する。演算制御部１１７は、データ分割部１１１およびデータ分割部１１２から有限体乗算部１１０へ入力される被乗数および乗数の入力制御および有限体乗算部１１０から出力されるデータの出力先制御を行なう。以下、有限体多項式乗算部１００の動作について説明する。

データ分割部１１１は、３２ビットの第１入力データを上位から８ビットずつ４つのデータに分割する。ここでは、４つのデータを上位からデータＸ０、Ｘ１、Ｘ２およびＸ３とする。データ分割部１１２も同様に、３２ビットの第２入力データを上位から８ビットずつ４つのデータに分割する。ここでは、４つのデータを上位からデータＹ０、Ｙ１、Ｙ２およびＹ３とする。以下、有限体乗算部１１０およびデータ加算部１１３〜１１５は、演算制御部１１７によりその入出力データが適宜制御されて、次式（１）〜（４）に従い、８ビットデータＤ０、Ｄ１、Ｄ２およびＤ３の値を計算する。

Ｄ０＝Ｘ０×Ｙ０＋Ｘ３×Ｙ１＋Ｘ２×Ｙ２＋Ｘ１×Ｙ３ ・・・（１）
Ｄ１＝Ｘ１×Ｙ０＋Ｘ０×Ｙ１＋Ｘ３×Ｙ２＋Ｘ２×Ｙ３ ・・・（２）
Ｄ２＝Ｘ２×Ｙ０＋Ｘ１×Ｙ１＋Ｘ０×Ｙ２＋Ｘ３×Ｙ３ ・・・（３）
Ｄ３＝Ｘ３×Ｙ０＋Ｘ２×Ｙ１＋Ｘ１×Ｙ２＋Ｘ０×Ｙ３ ・・・（４）
但し、上記の乗算「×」、加算「＋」は全て有限体ＧＦ（２⁸）上で行われる。上記の式がデータＸおよびデータＹの積を示している理由については既に説明した通りである。

上記４つの式のうち、データＤ０の計算を行なう際の有限多項式乗算部１００の動作についてのみ説明する。データＤ１〜Ｄ３については、これと同様の動作によって計算される。

演算制御部１１７は、有限体乗算部１１０への入力として、８ビットデータＸ０〜Ｘ３のうちからデータＸ０を、８ビットデータＹ０〜Ｙ３のうちからデータＹ０をそれぞれ選択する。有限体乗算部１１０は、データＸ０およびデータＹ０に対して有限体ＧＦ（２⁸）上の乗算を行ない、乗算結果をデータＺ０として出力する。即ち、
Ｚ０＝Ｘ０×Ｙ０
を計算する。

次に同様な動作により、有限体乗算部１１０は、データＸ３とＹ１に対して有限体ＧＦ（２⁸）上の乗算を行ない、データＺ１として出力する。即ち、
Ｚ１＝Ｘ３×Ｙ１
を計算する。同様にして
Ｚ２＝Ｘ２×Ｙ２
Ｚ３＝Ｘ１×Ｙ３
を計算する。

上記Ｚ０〜Ｚ３の出力が完了後、データ加算部１１３〜１１５は、上記データＺ０〜Ｚ３に対して、有限体ＧＦ（２⁸）上の加算を行なう。即ち、
Ｄ０＝Ｚ０＋Ｚ１＋Ｚ２＋Ｚ３
を計算する。但し有限体ＧＦ（２⁸）上の加算はビット毎の排他的論理和演算に他ならない。このため、上記の計算はデータＺ０〜Ｚ３に対してビット毎の排他的論理和演算を行なうことになる。同様にして、データ加算部１１３〜１１５は、
Ｄ１＝Ｘ１×Ｙ０＋Ｘ０×Ｙ１＋Ｘ３×Ｙ２＋Ｘ２×Ｙ３
Ｄ２＝Ｘ２×Ｙ０＋Ｘ１×Ｙ１＋Ｘ０×Ｙ２＋Ｘ３×Ｙ３
Ｄ３＝Ｘ３×Ｙ０＋Ｘ２×Ｙ１＋Ｘ１×Ｙ２＋Ｘ０×Ｙ３
を計算する。データ結合部１１６は、上位からデータＤ０、Ｄ１、Ｄ２およびＤ３を連結して３２ビットデータＤを有限体多項式乗算部１００の出力データとして出力する。

次に、第１変換部１４の内部構成と動作について説明する。
（第１変換部１４の内部構成）
図５は、第１変換部１４の内部構成の一例を示した図である。

第１変換部１４は、３２ビットの入力データＸに対して、有限体ＧＦ（２⁸）上の演算を用いた所定の変換を行ない、３２ビットの出力データＹを出力する処理部であり、データ分割部２０と、データ結合部２１と、定数記憶部２２と、有限体乗算部２１０とからなる。データ分割部２０は、３２ビット入力データを４つの８ビットデータに分割する。データ結合部２１は、４つの８ビットデータを結合して３２ビットデータとして出力する。定数記憶部２２は、４つの８ビット定数Ｃ１〜Ｃ４を記憶する。有限体乗算部２１０は、２つの８ビット入力データに対して、有限体ＧＦ（２⁸）上の乗算を行って８ビットの出力データを出力する。以下、第１変換部１４の動作について説明する。

データ分割部２０は、３２ビットの入力データＸを上位から８ビットずつ分割する。ここでは、分割後の８ビットデータを上位からデータＸ０、Ｘ１、Ｘ２およびＸ３とする。有限体乗算部２１０は、データＸ０と、定数記憶部２２に記憶されている８ビット定数Ｃ１との有限体ＧＦ（２⁸）上の乗算を行ない、出力データＹ０として出力する。同様に、有限体乗算部２１０は、データＸ１と定数Ｃ２との乗算を行ないデータＹ１として出力し、データＸ２と定数Ｃ３との乗算を行ないデータＹ２として出力し、データＸ３と定数Ｃ４との乗算を行ないデータＹ３として出力する。上記一連の動作により
Ｙ０＝Ｃ１×Ｘ０
Ｙ１＝Ｃ２×Ｘ１
Ｙ２＝Ｃ３×Ｘ２
Ｙ３＝Ｃ４×Ｘ３
が計算される。但し、上記の乗算「×」は全て有限体ＧＦ（２⁸）上で行われる。

上記処理の後、データ結合部２１は、上位からデータＹ０、Ｙ１、Ｙ２およびＹ３を結合して３２ビットデータＹを第１変換部１４の出力データとして出力する。

（第２変換部１５の内部構成）
第２変換部１５の内部構成は図６に示す通り、第１変換部１４の構成において、定数記憶部３２に記憶される定数がＣ１、Ｃ２、Ｃ３およびＣ４からＣ５、Ｃ６、Ｃ７およびＣ８にそれぞれに変わるだけであり、その他の内部構成および動作は第１変換部１４と同一である。このため、その詳細な説明はここでは繰り返さない。

次に、図７を参照して、有限体乗算部１１０、２１０および３１０の内部構成と動作とについて説明する。

（有限体乗算部１１０、２１０および３１０の内部構成）
有限体乗算部１１０、２１０および３１０は、いずれも同一の内部構成を有し、同一の動作を行なう。このため、ここでは、有限体乗算部１１０の動作についてのみ説明する。有限体ＧＦ（２⁸）上の乗算方法については、既に述べた通りであるが、ここでは、その計算をコンパクトな回路で実現した場合の構成を説明する。

有限体乗算部１１０は、８ビットの第１入力データＸと第２入力データＹに対して、有限体ＧＦ（２⁸）上の乗算を行ない、８ビットの出力データＺを出力する処理部であり、第１入力制御部４１１と、第２入力制御部４１４と、出力制御部４１２と、有限体２倍算部４１０と、データ融合部４１３と、データ分割部４１５とからなる。

第１入力制御部４１１および第２入力制御部４１４の各々は、２つの入力データのうちのどちらか一方を選択して、出力するよう制御を行なう。有限体２倍算部４１０は、入力データに対して有限体ＧＦ（２⁸）上の２倍算を行なう。データ融合部４１３は、２つの入力データを融合させる。データ分割部４１５は、入力データを複数のデータに分割する。以下、有限体乗算部１１０の動作について説明する。

まず、データ分割部４１５は、８ビットの第２入力データＹを上位から１ビットずつに分割して、それぞれ値Ｙ７、Ｙ６、・・・、Ｙ０とする。次に、ｉ＝７、６、５、４、３、２、１、０の順に以下の（１）から（５）の処理を繰り返し実行する。

（１）第１入力制御部４１１は、ｉ＝７のときは８ビットの初期値＝０を、ｉ≠７のときは出力制御部４１２から出力される８ビットデータを有限体２倍算部４１０に入力する。

（２）有限体２倍算部４１０は、第１入力制御部４１１から入力される８ビットデータに対して有限体ＧＦ（２⁸）上の２倍算を行ない、結果の８ビットデータをデータ融合部４１３に入力する。

（３）第２入力制御部４１４は、Ｙｉ（ｉ＝７、６、・・・、０）が０の場合は８ビット定数０を、それ以外の場合は第１入力データＸをデータ融合部４１３に入力する。

（４）データ融合部４１３は、有限体２倍算部４１０から入力される８ビットデータと、第２入力制御部４１４から入力される８ビットデータとに対してビット毎の排他的論理和演算を行ない、演算結果の８ビットデータを出力制御部４１２に入力する。

（５）ｉ≠０の場合は、出力制御部４１２は、データ融合部４１３から入力される８ビットデータを第１入力制御部４１１に入力する。その後、ｉの値が１だけ減らされ、（１）から処理が再度開始される。ｉ＝０の場合は、出力制御部４１２は、データ融合部４１３から入力される８ビットデータを有限体乗算部１１０の出力データとして出力する。その後、一連の処理が終了する。

上記の処理によって第１入力データＸと第２入力データＹとの乗算結果が計算できる理由について簡単に説明する。

第２入力データは、各ビットの値Ｙ７、Ｙ６、・・・、Ｙ０を用いると
Ｙ＝Ｙ７×２⁷＋Ｙ６×２⁶＋・・・＋Ｙｉ×２ⁱ＋・・・＋Ｙ０
と表せるので、
Ｘ×Ｙ＝Ｘ×（Ｙ７×２⁷＋Ｙ６×２⁶＋・・・＋Ｙｉ×２ⁱ＋・・・＋Ｙ０）
＝（・・・（（（（（０＋Ｘ×Ｙ７）×２＋Ｘ×Ｙ６）×２＋Ｘ×Ｙ５）×２＋Ｘ×Ｙ４）×２＋Ｘ×Ｙ３）・・・）×２＋Ｘ×Ｙ０
と表すことができる。この計算式を元にした処理を上記で行っている。

次に、有限体２倍算部４１０の内部構成および動作について説明する。
（有限体２倍算部４１０の内部構成）
図８は、有限体２倍算部４１０の内部構成を示した図である。

有限体２倍算部４１０は、入力される８ビットデータＸに対して有限体ＧＦ（２⁸）上の２倍算を行ない、その結果の８ビットデータＹを出力する処理部であり、データ分割部５１１と、データ結合部５１２と、データ融合部５１３〜５１５とからなる。

データ分割部５１１は、入力データを１ビットずつのデータに分割する。データ結合部５１２は、複数個の入力データを結合して１つのデータとして出力する。データ融合部５１３〜５１５の各々は、２つの入力データを融合する。以下、有限体２倍算部４１０の動作について説明する。

まず、データ分割部５１１は、８ビット入力データＸを上位から１ビットずつ分割して、上位からデータＸ７、Ｘ６、・・・、Ｘ０として出力する。次に、データ融合部５１３は、データＸ７とデータＸ３との排他的論理和演算を行ないデータＹ４として出力する。データ融合部５１４は、データＸ７とデータＸ２との排他的論理和演算を行ないデータＹ３として出力する。データ融合部５１５は、データＸ７とデータＸ０との排他的論理和演算を行ないデータＹ１として出力する。また、データＸ６、Ｘ５、Ｘ４、Ｘ１およびＸ７はそれぞれデータＹ７、Ｙ６、Ｙ５、Ｙ２およびＹ０とされる。データ結合部５１２は、データＹ７、Ｙ６、Ｙ５、・・・、Ｙ０を上位からこの順序で結合した８ビットデータを、有限体２倍算部４１０の出力データとして出力する。

有限体２倍算部４１０は、８ビット入力データＸの各ビットＸ７、Ｘ６、・・・、Ｘ０に対して、
Ｙ７＝Ｘ６
Ｙ６＝Ｘ５
Ｙ５＝Ｘ４
Ｙ４＝Ｘ３（＋）Ｘ７
Ｙ３＝Ｘ２（＋）Ｘ７
Ｙ２＝Ｘ１
Ｙ１＝Ｘ０（＋）Ｘ７
Ｙ０＝Ｘ７
として、８ビット出力データＹの各ビットＹ７、Ｙ６、・・・、Ｙ０の値を算出している。このとき出力データＹは、入力データＸに対して有限体ＧＦ（２⁸）上の２倍算を行った結果になっている。このことを簡単に説明する。

入力データＸは、係数が有限体ＧＦ（２）の値である以下のようなαの多項式によって表せる。

Ｘ７×α⁷＋Ｘ６×α⁶＋・・・＋Ｘ１×α＋Ｘ０
このとき、有限体ＧＦ（２⁸）上で２倍算を行なうということは、上の多項式にαを掛け算することであるから、
Ｘ７×α⁸＋Ｘ６×α⁷＋・・・＋Ｘ１×α²＋Ｘ０×α
となる。ここで、原始多項式がｘ⁸＋ｘ⁴＋ｘ³＋ｘ＋１であることから、α⁸＝α⁴＋α³＋α＋１ が成り立つ。このため、上記の多項式は、
Ｘ６×α⁷＋Ｘ５×α⁶＋Ｘ４×α⁵＋（Ｘ３＋Ｘ７）×α⁴＋（Ｘ２＋Ｘ７）×α³＋Ｘ１×α＋（Ｘ０＋Ｘ７）
と書き直される。これが
Ｙ７×α⁷＋Ｙ５×α⁶＋・・・＋Ｙ１×α＋Ｙ０
に対応することから、上述の有限体２倍算部４１０のような処理を行なう理由が説明できる。

データ変換装置１および２は、６４ビットの入力データＸに対して以下の処理を行っていることになる。

（１）入力データＸを上位３２ビット、下位３２ビットに分割してデータＸ０およびＸ１とする。

（２）Ｔ０＝（Ｘ０＋Ｋ１）³＋（Ｘ１＋Ｋ２）³ および Ｔ１＝（Ｘ０＋Ｋ３）³＋（Ｘ１＋Ｋ４）³ を計算する。但し、ここでの加算、乗算は全て有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上で行なう。

（３）３２ビットのデータＴ０を上位から８ビットずつに分割して、データａ０、ａ１、ａ２およびａ３とし、３２ビットのデータＴ１を上位から８ビットずつに分割して、データｂ０、ｂ１、ｂ２およびｂ３とする。

（４）Ｇ０＝Ｃ１×ａ０‖Ｃ２×ａ１‖Ｃ３×ａ２‖Ｃ４×ａ３ および Ｇ１＝Ｃ５×ｂ０‖Ｃ６×ｂ１‖Ｃ７×ｂ２‖Ｃ８×ｂ３を計算し、Ｇ０‖Ｇ１を出力データとして出力する。但し、「‖」はデータ連結を表し、上記の乗算は全て有限体ＧＦ（２⁸）上で行なわれる。

有限体ＧＦ（２⁸）上の値を係数とする多項式剰余環上の乗算は式（１）〜式（４）から分かるように、入力データの一部でも変更されると、その変更の影響が出力データの全てに及ぶことになる。例えば、式（１）〜式（４）においてデータＸ０の値が変更されるものとする。データＸ０は式（１）〜式（４）の全ての計算に使用されている。このため、出力データＤ０〜Ｄ３の全てに影響が及ぶことになる。他の値（Ｘ１〜Ｘ３、Ｙ０〜Ｙ３）についても同様のことが言える。このことにより、本実施の形態では、変換処理に上記の乗算を用いることで高いデータ撹乱性能を実現することができる。次に、本実施の形態では、二つ以上の変数の乗算（例えば、Ｘ×Ｙ、Ｘ×Ｙ×Ｚ）ではなく、べき乗算を用いているが、これは、二つ以上の変数の乗算の場合、それらの変数のうちいずれか一つでも０の場合、その他の変数がどのような値であっても乗算結果は常に０となり、演算結果の値が０になる入力変数値の組み合わせが多数存在することになり、良好なデータ撹乱性能を示さないからである。一方、べき乗算を用いた場合には、入力変数値が０の時にしか演算結果が０とならないので、上記のようなデータ撹乱性能を低下させる問題がなくなり、高いデータ撹乱性能が保証される。

また、本実施の形態では、３乗のべき乗算を用いているが、これは以下の理由による。まず２乗算を用いて、Ｙ＝Ｘ²のような変換を考えたとき、入力値αに対する出力値は、α²である。次に、入力値αに差分Δが加わったときの出力値は、（α＋Δ）²＝α²＋α×Δ＋Δ×α＋Δ²であり、α×Δ＝Δ×αかつα×Δ＋α×Δ＝０（いずれも、有限体ＧＦ（２⁸）上の計算方法から明らか）であることから、（α＋Δ）²＝α²＋Δ²となる。従って、差分Δを入力値に加えることによる出力値の変化分は、Δ²である。即ち、出力値の変化分は、入力値αによらず一定の出力差分Δ²となってしまい、データ撹乱という観点からは好ましい性質とはいえない。これにより、少なくとも３乗以上のべき乗算を用いる必要があるが、べき数が大きいほどべき乗処理が多くなり変換処理負荷が高くなるため、本実施の形態では３乗のべき乗算を用いている。このとき、
（α＋Δ）³＝（α＋Δ）×（α＋Δ）×（α＋Δ）
＝（α²＋α×Δ＋Δ×α＋Δ²）×（α＋Δ）
＝（α²＋Δ²）×（α＋Δ）
＝α³＋Δ×α²＋Δ²×α＋Δ³
となるので、３乗のべき乗算の場合には、２乗のべき乗算のように出力差分が入力値αによらず一定になることはない。なお、べき乗算のべき数ＮをＮ＝２^k （ｋは１以上の整数）とした場合には、べき乗算Ｘ^Nをデータ変換処理として入力値αに入力差分Δを与えたときの出力値（α＋Δ）＾（２^k）＝α＾（２^k）＋Δ＾（２^k）となり、入力値によらず一定になることが以下のようにして分かる。ここで、「Ｘ＾α」はＸのα乗を意味する。

ｋ＝１の場合、べき数＝２であるから、上記説明から出力値は（α＋Δ）²＝α²＋Δ²である。次にｋ＝ｍ、即ちべき数＝２^mのときに（α＋Δ）＾（２^m）＝α＾（２^m）＋Δ＾（２^m）が成り立つとしたとき、（α＋Δ）＾（２^m+1）＝｛（α＋Δ）＾（２^m）｝²＝｛α＾（２^m）＋Δ＾（２^m）｝²＝α＾（２^m+1）＋Δ＾（２^m+1）が成り立つのでｋ＝ｍ＋１の時にも上記のことは成り立つ。従って、数学的帰納法より１以上の任意の整数ｋに対して（α＋Δ）＾（２^k）＝α＾（２^k）＋Δ＾（２^k）、となることが示される。従って、べき数としては２^k（ｋは１以上の整数）以外の値であれば良いことが分かる。即ち、本実施の形態ではべき数として３を用いているが、これは、データ変換装置での処理時間に多少の時間がかかっても良いのであれば、２^k（ｋは１以上の整数）以外である３以上の値であれば何でも良い。

また、本実施の形態では、（Ｘ＋Ｋ）³のようにべき乗算の前に、定数Ｋによる加算（排他的論理和演算）を行っているが、この定数Ｋを変更することによって、データ変換装置の変換処理に多くのバリエーションを与えることができる。例えば、この定数Ｋを認証する相手ごとに使い分けることで、認証相手ごとに認証に用いる変換処理の使い分けができることになる。

このとき、（Ｘ＋Ｋ）³の値が０になるのは、Ｘ＝Ｋの時だけであるから、先に述べたようなべき乗演算を用いることにより、高いデータ撹乱性能が保障できるというメリットは損なわれない。

また、本実施の形態では、４つのデータＡ０〜Ａ３に対して同一のべき数３によるべき乗算を行っているが、これは同一のべき数である必要はなく、それぞれ異なるべき数であってもよい。

さらに、本実施の形態のデータ変換装置では、データ撹乱のコアとなる処理に有限体ＧＦ（２⁸）上の演算処理を用いている。このため、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号や、ＢＣＨ（Bose-Chaudhuri-Hocqenghem）符号などの誤り訂正符号化回路で使用される有限体ＧＦ（２⁸）上の演算回路との回路共有が可能となる。このため、機器全体としての実装規模が削減でき、コンパクトな回路規模での機器実装が実現される。

なお、本実施の形態の各データサイズはあくまでも一例であって、ここで述べたデータサイズ以外であってもかまわない。また、本実施の形態の原始多項式、剰余多項式もあくまでも一例であって、これに限られるものではない。

また、本実施の形態ではデータ変換装置を認証システムに用いた場合について述べているが、秘密のデータ変換を使用するようなものであれば何でも、本実施の形態のデータ変換装置が使用できる。データ変換装置の他の応用例としては、例えば図９に示すようなコンテンツ配信システムへの適用が考えられる。コンテンツ配信システムは、コンテンツを暗号化された状態で放送またはネットワークを介して配信するコンテンツ配信機器７と、前記配信される暗号化コンテンツを受信して復号化して再生する再生機器８とからなる。コンテンツ配信機器７は、データ変換装置７０において鍵シードデータ（コンテンツ鍵を生成するためのシードとなるデータ）にデータ変換処理を行ない、コンテンツ鍵を生成する。そして、コンテンツ暗号化装置７１において、平文のコンテンツデータに対して暗号化を行ない暗号化コンテンツデータを生成する。上記の処理の後、コンテンツ配信機器７は、鍵シードデータと暗号化コンテンツデータとを再生機器８に送付する。前記データを受信した再生機器８は、まずデータ変換装置８０において、鍵シードデータに対して変換処理を行ない、コンテンツ鍵を生成する。そして、コンテンツ復号化装置８１において、暗号化コンテンツデータを復号化し平文のコンテンツを得る。コンテンツの再生を認められた再生機器のみがコンテンツ配信機器が有するものと同じデータ変換装置を搭載することによって、不正規再生機器による配信コンテンツの再生を阻止することができる。

また、本実施の形態ではデータ融合部１１ａ〜１１ｄにおいてデータ融合を行なう固定値Ｋ１〜Ｋ４を予め定められた固定値としているが、これらの固定値をデータ変換装置外部から入力するようにして、使用者が自由に設定できるようにしてもよい。さらに、定数記憶部２２に記憶される定数Ｃ１〜Ｃ４も予め設定された固定値としているが、これらも、データ変換装置外部から入力するようにして、使用者が自由に設定できるようにしてもよい。

また、本実施の形態では、有限体として有限体ＧＦ（２⁸）を用いたが、それ以外の有限体であっても良く、例えば、有限体ＧＦ（２ⁿ）（ｎは自然数）であってもよい。

なお、ブロック図（図２など）の各機能ブロックは典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。

図１０は、図２に示したデータ変換装置と同様の機能を有するデータ変換装置を含む誤り訂正・データ変換装置のＬＳＩの外観図を示している。図１１は、誤り訂正・データ変換装置のＬＳＩの構成を示す機能ブロック図である。

図１１に示すように、誤り訂正・データ変換装置６００は、データに対して誤り訂正符号化を行なった後、データ変換を行なう装置であり、リードソロモン誤り訂正符号化部６０１と、データ変換装置６０４とを備えている。

リードソロモン誤り訂正符号化部６０１は、入力されたデータに対してＲｅｅｄ−Ｓｏｌｏｍｏｎ誤り訂正符号化を行ない、符号化されたデータを出力する処理部であり、データ受信部６０２と、符号化部６０３とを備えている。データ受信部６０２は、外部より入力されるデータを受信する処理部である。符号化部６０３は、データ受信部６０２で受信されたデータに対し、有限体ＧＦ（２ⁿ）上の乗算を行なうことにより、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ誤り訂正符号化を行なう処理部である。符号化部６０３は、有限体ＧＦ（２ⁿ）上の乗算を行なう有限体乗算部１１０を備えている。有限体乗算部１１０の構成は上述したとおりである。

データ変換装置６０４は、上述のデータ変換装置１（２）と同様の構成を有するが、有限体多項式乗算部１００の代わりに有限体多項式乗算部６０５を用い、第１変換部１４の代わりに第１変換部６０６を用い、第２変換部１５の代わりに第２変換部６０７を用いている。有限体多項式乗算部６０５は、符号化部６０３に設けられた有限体乗算部１１０を用いて有限体ＧＦ（２ⁿ）上の乗算を行なう点が有限体多項式乗算部１００と異なり、その他の構成は有限体多項式乗算部１００と同様である。第１変換部６０６は、符号化部６０３に設けられた有限体乗算部１１０を用いて有限体ＧＦ（２ⁿ）上の乗算を行なう点が第１変換部１４と異なり、その他の構成は第１変換部１４と同様である。第２変換部６０７は、符号化部６０３に設けられた有限体乗算部１１０を用いて有限体ＧＦ（２ⁿ）上の乗算を行なう点が第２変換部１５と異なり、その他の構成は第２変換部１５と同様である。

このように、リードソロモン誤り訂正符号化部６０１とデータ変換装置６０４とで有限体乗算部１１０を共有化することができる。このため、ＬＳＩの回路規模を削減することができる。

ここでは、ＬＳＩにより誤り訂正・データ変換装置６００を実現したが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。

また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用しても良い。

さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。別技術としてバイオ技術等が可能性としてありえる。

本発明にかかるデータ変換装置は、誤り訂正符号化回路とデータ変換回路の共有化を図ることにより、データ変換装置を含む回路全体の規模削減が可能であるという効果を有するので、例えば通信路を介して相手認証をする機能を有する機器などに有用である。また、この例に限られず、何らかのデータ変換回路の実装が必要な機器であればどのような機器であっても適用が可能である。

本発明の実施の形態に係る認証システムの構成を示すブロック図である。 本発明の実施の形態に係るデータ変換装置の構成の一例を示すブロック図である。 本発明の実施の形態に係る有限体多項式３乗部の構成の一例を示すブロック図である。 本発明の実施の形態に係る有限体多項式乗算部の構成の一例を示すブロック図である。 本発明の実施の形態に係る第１変換部の構成の一例を示すブロック図である。 本発明の実施の形態に係る第２変換部の構成の一例を示すブロック図である。 本発明の実施の形態に係る有限体乗算部の構成の一例を示すブロック図である。 本発明の実施の形態に係る有限体２倍算部の構成の一例を示すブロック図である。 本発明の変換装置をコンテンツ配信システムに適用した場合のシステム構成の一例を示すブロック図である。 誤り訂正・データ変換装置のＬＳＩの外観図である。 誤り訂正・データ変換装置の構成の一例を示すブロック図である。

符号の説明

１，２，７０，８０ データ変換装置
３ 認証装置
４ 被認証装置
５ 乱数生成器
６ データ比較器
７ コンテンツ配信機器
８ 再生機器
１０ 有限体多項式３乗部
１１ａ，１１ｂ，１１ｃ，１１ｄ，１２，１３，４１３，５１３，５１４，５１５ データ融合部
１４ 第１変換部
１５ 第２変換部
１６，２０，３０，１１１，１１２，４１５，５１１ データ分割部
１７，２１，３１，１１６，５１２ データ結合部
２２，３２ 定数記憶部
７１ コンテンツ暗号化装置
８１ コンテンツ復号化装置
１００ 有限体多項式乗算部
１０１ 入力制御部
１０２，４１２ 出力制御部
１１０，２１０，３１０ 有限体乗算部
１１３，１１４，１１５ データ加算部
４１０ 有限体２倍算部
４１１ 第１入力制御部
４１４ 第２入力制御部

Claims (6)

1. 有限体ＧＦ（２ⁿ）上の乗算を行なう有限体乗算手段と、
   複数のデータを取得する取得手段と、
   前記有限体乗算手段を利用して前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数による、べき乗演算に基づく変換を行うべき乗手段と、
   前記べき乗手段で変換された後の前記複数のデータに基づいて出力データを生成する出力データ生成手段とを備え、
   前記所定のべき数は３以上であり、かつ２^m（ｍは１以上の整数）以外の値であり、
   前記べき乗手段は、第１入力データと第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の乗算を行う有限体多項式乗算部を有し、前記複数のデータの各々について、当該データを前記第１入力データとし、初回の多項式剰余環上の乗算では当該データを前記第２入力データとし、２回目以降の多項式剰余環上の乗算では直近の多項式剰余環上の乗算結果を前記第２入力データとして、前記有限体多項式乗算部により前記第１入力データと前記第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の乗算を、（前記所定のべき数−１）回繰り返した乗算結果を変換後の値とすることにより、前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数による、べき乗演算に基づく変換を行い、
   前記有限体多項式乗算部は、前記第１入力データをｎビットずつ分割した複数の第１分割データの各々と、前記第２入力データをｎビットずつ分割した複数の第２分割データの各々とを前記有限体乗算手段の入力とすることにより得られる有限体ＧＦ（２ⁿ）上の乗算結果を加算器を用いて加算し、加算結果を結合することにより、前記第１入力データと前記第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の結果を得る
   ことを特徴とするデータ変換装置。
2. 前記出力データ生成手段は、
   前記べき乗手段で変換された後の前記複数のデータ同士で、前記多項式剰余環上の加算を行なう加算部と、
   前記加算部の加算結果に対して所定の定数との前記有限体ＧＦ（２ⁿ）上の乗算を行なう乗算部とを有する
   ことを特徴とする請求項１に記載のデータ変換装置。
3. 有限体乗算手段、取得手段、べき乗手段および出力データ生成手段を備えるデータ変換装置が実行するデータ変換方法であって、
   前記べき乗手段は、有限体多項式乗算部を有し、
   前記データ変換方法は、
   前記取得手段が、複数のデータを取得する取得ステップと、
   前記べき乗手段が、前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数による、べき乗演算に基づく変換を行なうべき乗ステップと、
   前記出力データ生成手段が、前記べき乗ステップで変換された後の前記複数のデータに基づいて出力データを生成する出力データ生成ステップとを含み、
   前記所定のべき数は３以上であり、かつ２^m（ｍは１以上の整数）以外の値であり、
   前記べき乗ステップでは、前記べき乗手段が、第１入力データと第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の乗算を行う前記有限体多項式乗算部を用いて、前記複数のデータの各々について、当該データを前記第１入力データとし、初回の多項式剰余環上の乗算では当該データを前記第２入力データとし、２回目以降の多項式剰余環上の乗算では直近の多項式剰余環上の乗算結果を前記第２入力データとして、前記有限体多項式乗算部により前記第１入力データと前記第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の乗算を、（前記所定のべき数−１）回繰り返した乗算結果を変換後の値とすることにより、前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数による、べき乗演算に基づく変換を行い、
   前記有限体多項式乗算部は、前記第１入力データをｎビットずつ分割した複数の第１分割データの各々と、前記第２入力データをｎビットずつ分割した複数の第２分割データの各々とを、有限体ＧＦ（２ⁿ）上の乗算を行なう前記有限体乗算手段の入力とすることにより得られる有限体ＧＦ（２ⁿ）上の乗算結果を加算器を用いて加算し、加算結果を結合することにより、前記第１入力データと前記第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の結果を得る
   ことを特徴とするデータ変換方法。
4. 前記出力データ生成手段は加算部と乗算部とを含み、
   前記出力データ生成ステップは、
   前記加算部が、前記べき乗ステップで変換された後の前記複数のデータ同士で、前記多項式剰余環上の加算を行なう加算サブステップと、
   前記乗算部が、前記加算サブステップの加算結果に対して所定の定数との前記有限体ＧＦ（２ⁿ）上の乗算を行なう乗算サブステップとを含む
   ことを特徴とする請求項３に記載のデータ変換方法。
5. 有限体ＧＦ（２ⁿ）（ｎは自然数）上の乗算を行なう有限体乗算手段と、
   複数のデータを取得する取得手段と、
   前記有限体乗算手段を利用して前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数による、べき乗演算に基づく変換を行なうべき乗手段と、
   前記べき乗手段で変換された後の前記複数のデータに基づいて出力データを生成する出力データ生成手段とを備え、
   前記所定のべき数は３以上であり、かつ２^m（ｍは１以上の整数）以外の値であり、
   前記べき乗手段は、第１入力データと第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の乗算を行う有限体多項式乗算部を有し、前記複数のデータの各々について、当該データを前記第１入力データとし、初回の多項式剰余環上の乗算では当該データを前記第２入力データとし、２回目以降の多項式剰余環上の乗算では直近の多項式剰余環上の乗算結果を前記第２入力データとして、前記有限体多項式乗算部により前記第１入力データと前記第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の乗算を、（前記所定のべき数−１）回繰り返した乗算結果を変換後の値とすることにより、前記複数のデータの各々に対して、有限体ＧＦ（２ⁿ）（ｎは自然数）上の値を係数とする多項式剰余環上における所定のべき数による、べき乗演算に基づく変換を行い、
   前記有限体多項式乗算部は、前記第１入力データをｎビットずつ分割した複数の第１分割データの各々と、前記第２入力データをｎビットずつ分割した複数の第２分割データの各々とを前記有限体乗算手段の入力とすることにより得られる有限体ＧＦ（２ⁿ）上の乗算結果を加算器を用いて加算し、加算結果を結合することにより、前記第１入力データと前記第２入力データとの有限体ＧＦ（２^ｎ）上の値を係数とする多項式剰余環上の結果を得る
   ことを特徴とする集積回路。
6. コンピュータを、請求項１または請求項２に記載のデータ変換装置として機能させるためのプログラム。

Images