(57)【特許請求の範囲】
【請求項１】
ｗが１以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄ、ＧＦ（２）が位数２のガロア体であり、前記ガロア体ＧＦ（２）のｎ個の元ｂｎ−１，．．．，ｂ0からなる入力列Ｘを受け付ける入力部と、
ｉ＝ｄ−１，．．．，０について、ｗ個の元ｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉに含まれる元ｂｗ×（ｉ+１）−１を抽出値ｃｉとして得る抽出部と、
Ｉ０が前記ガロア体ＧＦ（２）の加法単位元であり、ｉ＝ｄ−１，．．．，０について、前記ワードＸｉごとにｗ個の元ｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，Ｉ０からなるワードＳｉを得、ｄ個の前記ワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓを得るシフト部と、
ｎ次既約多項式がｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｘが不定元、ｅｎ，．．．，ｅ０が前記ガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｊ＝ｄ−２，．．．，０、Ｋｊが前記ガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，．．．，ｋｊ，０からなる列、前記列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）が前記抽出値ｃｊ、前記列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）以外の元が前記加法単位元Ｉ０、前記抽出値ｃｄ−１が前記加法単位元Ｉ０である場合のＨがｎ個の前記加法単位元Ｉ０からなる列、前記抽出値ｃｄ−１が前記加法単位元Ｉ０でない場合のＨが前記列Ｆ、フィードバック列が
【数５】
0005730812.tif 000006
を満たす列であり、前記シフト列Ｓと前記フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］とに対する出力列Ｙ＝Ｓ＋Ｍ［ｃｄ−１，．．．，ｃ０］∈ＧＦ（２ｎ）を得る演算部と、
を有する演算装置。
【請求項２】
ｗが１以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄであり、ｎ個のビットｂｎ−１，．．．，ｂ0からなる入力列Ｘを受け付ける入力部と、
ｉ＝ｄ−１，．．．，０について、ｗ個のビットｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉに含まれるｂｗ×（ｉ+１）−１を抽出値ｃｉとして得る抽出部と、
ｉ＝ｄ−１，．．．，０について、前記ワードＸｉごとにｗ個のビットｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，０からなるワードＳｉを得、ｄ個の前記ワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓを得るシフト部と、
ｎ次既約多項式がｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｘが不定元、ｎ個のビットｅｎ，．．．，ｅ０が係数、Ｆがｎ個のビットｅｎ−１，．．．，ｅ０からなる列、ｊ＝ｄ−２，．．．，０、Ｋｊがビットｋｊ，ｎ−１，．．．，ｋｊ，０からなる列、前記列Ｋｊに含まれるｋｊ，ｗ×（ｊ＋１）が前記抽出値ｃｊ、前記列Ｋｊに含まれるｋｊ，ｗ×（ｊ＋１）以外のビットが０、フィードバック列が
【数６】
0005730812.tif 000007
を満たす列であり、前記シフト列Ｓと前記フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］との排他的論理和である出力列Ｙを得る演算部と、
を有する演算装置。
【請求項３】
請求項１または２の演算装置であって、
予め得られた前記フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］を格納した記憶部をさらに有し、
前記演算部は、前記記憶部に格納された前記フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］を用い、前記出力列Ｙを得る、
ことを特徴とする演算装置。
【請求項４】
請求項１から３の何れかの演算装置であって、
前記抽出部、前記シフト部および前記演算部の各処理はＳＩＭＤ演算である、
ことを特徴とする演算装置。
【請求項５】
ｗが１以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄ、ＧＦ（２）が位数２のガロア体であり、入力部で、前記ガロア体ＧＦ（２）のｎ個の元ｂｎ−１，．．．，ｂ0からなる入力列Ｘを受け付ける入力ステップと、
抽出部で、ｉ＝ｄ−１，．．．，０について、ｗ個の元ｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉに含まれる元ｂｗ×（ｉ+１）−１を抽出値ｃｉとして得る抽出ステップと、
Ｉ０が前記ガロア体ＧＦ（２）の加法単位元であり、シフト部で、ｉ＝ｄ−１，．．．，０について、前記ワードＸｉごとにｗ個の元ｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，Ｉ０からなるワードＳｉを得、ｄ個の前記ワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓを得るシフトステップと、
ｎ次既約多項式がｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｘが不定元、ｅｎ，．．．，ｅ０が前記ガロア体ＧＦ（２）のｎ＋１個の元である係数、Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列、ｊ＝ｄ−２，．．．，０、Ｋｊが前記ガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，．．．，ｋｊ，０からなる列、前記列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）が前記抽出値ｃｊ、前記列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）以外の元が前記加法単位元Ｉ０、前記抽出値ｃｄ−１が前記加法単位元Ｉ０である場合のＨがｎ個の前記加法単位元Ｉ０からなる列、前記抽出値ｃｄ−１が前記加法単位元Ｉ０でない場合のＨが前記列Ｆ、フィードバック列が
【数７】
0005730812.tif 000008
を満たす列であり、演算部で、前記シフト列Ｓと前記フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］とに対する出力列Ｙ＝Ｓ＋Ｍ［ｃｄ−１，．．．，ｃ０］∈ＧＦ（２ｎ）を得る演算ステップと、
を有する演算方法。
【請求項６】
ｗが１以上の整数、ｄが２以上の整数、ｎ＝ｗ×ｄであり、入力部で、ｎ個のビットｂｎ−１，．．．，ｂ0からなる入力列Ｘを受け付ける入力ステップと、
抽出部で、ｉ＝ｄ−１，．．．，０について、ｗ個のビットｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉに含まれるｂｗ×（ｉ+１）−１を抽出値ｃｉとして得る抽出ステップと、
シフト部で、ｉ＝ｄ−１，．．．，０について、前記ワードＸｉごとにｗ個のビットｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，０からなるワードＳｉを得、ｄ個の前記ワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓを得るシフトステップと、
ｎ次既約多項式がｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０、ｘが不定元、ｎ個のビットｅｎ，．．．，ｅ０が係数、Ｆがｎ個のビットｅｎ−１，．．．，ｅ０からなる列、ｊ＝ｄ−２，．．．，０、Ｋｊがビットｋｊ，ｎ−１，．．．，ｋｊ，０からなる列、前記列Ｋｊに含まれるｋｊ，ｗ×（ｊ＋１）が前記抽出値ｃｊ、前記列Ｋｊに含まれるｋｊ，ｗ×（ｊ＋１）以外のビットが０、フィードバック列が
【数８】
0005730812.tif 000009
を満たす列であり、演算部で、前記シフト列Ｓと前記フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］との排他的論理和である出力列Ｙを得る演算ステップと、
を有する演算方法。
【請求項７】
請求項１から４の何れかの演算装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、線形フィードバックシフトレジスタでの演算に関する。
【背景技術】
【０００２】
データを秘匿また改竄検知のためには暗号技術が有効である。暗号技術にはいわゆるＲＳＡ暗号を利用した非対称鍵技術およびＡＥＳなどをはじめとする共通鍵暗号を利用した対称鍵技術がある。非対称鍵技術は鍵の取扱が容易である利点があるものの、速度の面からは圧倒的に対称鍵技術が有利である。実際、大量のデータの秘匿や改竄検知を目的としてＡＥＳを利用した暗号利用モードが多く利用されており、ＳＳＬなどで実用化されている。
【０００３】
暗号利用モードは共通鍵ブロック暗号を単純な演算で組み合わせて、もともと共通鍵ブロック暗号では１ブロック（ＡＥＳでは１２８ビット）の暗号化しか出来なかったものを、多ブロックの暗号化処理や改竄検知（メッセージ認証）などの機能を追加する方法である。従来、守秘機能を実現するＣＦＢモードや、メッセージ認証を実現するＣＢＣ−ＭＡＣといった方法が知られていたが、高い安全性を示せないという問題があった。
【０００４】
その後、認証暗号モードＯＣＢ、ＭＡＣモードＰＭＡＣ、ディスク暗号ＸＴＳといった方法が提案され、高い安全性が示されるようになった。これらの暗号利用モードではガロア体ＧＦ（２ｎ）上の演算が使われている。ただしｎは１以上の整数である。ガロア体ＧＦ（２ｎ）の元は、例えば以下のｎ−１次多項式で表現でき（ＧＦ（２ｎ）の加法単位元を係数とする項を表現しない場合にはｎ−１次以下の多項式）、さらには当該ｎ−１次多項式のｎ個の係数からなるガロア体ＧＦ（２）の元の列（ベクトル）でも表現できる。
ＧＦ（２）［ｘ］／（ｆ（ｘ））      (1)
ただし、ＧＦ（２）［ｘ］はガロア体ＧＦ（２）の元を係数とする多項式の集合、ｘは不定元、ｆ（ｘ）はガロア体ＧＦ（２）上のｎ次既約多項式、α／（β）はβを法としたαの剰余の集合を表す。
【０００５】
ここで式(1)のように表現されるガロア体ＧＦ（２ｎ）の元をｘ倍する演算を「２倍算」と呼ぶ。すなわち、以下を「２倍算」と呼ぶ。
ｘ×γ∈ＧＦ（２）［ｘ］／（ｆ（ｘ））      (2)
ただし、ｘ，γ∈ＧＦ（２）［ｘ］／（ｆ（ｘ））である。
これを「２倍算」と呼ぶのは、ガロア体ＧＦ（２）の元の集合を整数集合｛０，１｝とみなし、ｘをｎ−１次多項式とみなした場合、ｎ−１次多項式ｘの係数からなる列は００...１０となり、これを二進数表記された「１０」とみなし、それを十進数表記に変換すると「２」になることに基づく。このような「２倍算」は上記モードなど多くのモードで使用されている。
【０００６】
「２倍算」は線形フィードバックシフトレジスタによって実装できる。以下に、線形フィードバックシフトレジスタで「２倍算」を行うための従来のアルゴリズム（Ａｌｇｏｒｉｔｈｍ１）を例示する（例えば、非特許文献１等参照）。このアルゴリズムでは、２を法とした剰余演算上で四則演算が定義された有限集合でガロア体ＧＦ（２）を実装（以下「ビット実装」）し、ｎ−１次多項式ｇ（ｘ）＝αｎ−１×ｘｎ−１＋...＋α０（ただしαｎ−１，...，α０∈ＧＦ（２））に対するｘ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数からなるビット列Ｙを求める。また、ｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０の係数ｅｎ，．．．，ｅ０∈｛０，１｝のうち、係数ｅｎ−１，．．．，ｅ０からなる列をＦとする。さらに、ｎ−１次多項式ｇ（ｘ）の係数αｎ−１，...，α０からなる列をＸとする。
【０００７】
［Ａｌｇｏｒｉｔｈｍ１］
入力：Ｘ
出力：Ｙ
１：ｉｆ  αｎ−１＝１  ｔｈｅｎ
２：Ｙ←（Ｘ≪１）（＋）Ｆ
３：ｅｌｓｅ
４：Ｙ←（Ｘ≪１）
５：ｅｎｄ  ｉｆ
ただし、Ｘ≪αはＸに対するαビットの左シフト演算を表し、α（＋）βはαとβとの排他的論理和を表し、α←βはβの結果をαに代入することを表す。
【０００８】
近年、Ｉｎｔｅｌ（登録商標）のＰｅｎｔｉｕｍ（登録商標） ｗｉｔｈ ＭＭＸ（登録商標） ｔｅｃｈｎｏｌｏｇｙをはじめとして、ＰＣで用いられるような汎用のＣＰＵでもＳＩＭＤ（Single instruction, multiple data）演算器が利用可能なものが増えてきている。ＳＩＭＤ演算では、処理対象のビット列に対し、複数個のビットからなるワードごとに独立に同じ演算を施す。例えば、Ｉｎｔｅｌのｘｍｍ（登録商標）レジスタは１２８ビットのビット列を格納し、例えば、３２ビットごとや６４ビットごとに同じ演算を施す。３２ビットごとに処理される場合、４つの３２ビットレジスタが並列に並んでいるものとして処理が実行される。６４ビットごとに処理される場合、２つの６４ビットレジスタが並列に並んでいるものとして処理が実行される。そのため、例えば、異なるレジスタに格納された１２８ビットのデータ同士の加算を、３２ビットや６４ビットごとに並行に実行できる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ted Krovetz and Phillip Rogaway, “The Software Performance of Authenticated Encryption Modes,” Fast Software Encryption 2011 (FSE 2011).
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ＳＩＭＤ演算器にとって、同じレジスタ内の２つのデータ間の扱いは非常に苦手である。例えば、ＳＩＭＤ演算による単純なシフト演算は、処理対象のビット列に含まれるワードごとに独立に実行される。そのため、ＳＩＭＤ演算によってビット列全体に対する左シフト演算を行うためには、各ワードでのシフト演算の他にワード間でのビットの移動処理が必要となる。例えば、６４ビットごとに処理を行うＳＩＭＤ演算器によって１２８ビットのＸに対する、Ａｌｇｏｒｉｔｈｍ１での１ビットの左シフト演算を行う場合には、６４ビットごとの左シフト演算に加え、６３ビット目から６４ビット目へのビット（ただし最下位は０ビット目）の移動処理が必要となる。しかしながら、一般的に、ＳＩＭＤ演算にはワード間でビットを直接移動させる命令は存在せず、線形フィードバックシフトレジスタでの「２倍算」をＳＩＭＤ演算によって効率的に実行する方法は存在しない。
【００１１】
またＡｌｇｏｒｉｔｈｍ１では、Ｘに含まれるビットαｎ−１が１であるか否かに応じて異なる処理が実行されるが、ＳＩＭＤ演算は特定のワードのみから特定のビットを抽出し、そのビットに応じて異なる処理（分岐処理）を実行することにも適していない。
【００１２】
本発明はこのような点に鑑みてなされたものであり、線形フィードバックシフトレジスタでの「２倍算」をＳＩＭＤ演算によって効率的に実行するための技術を提供する。
【課題を解決するための手段】
【００１３】
本発明の第１態様では、ガロア体ＧＦ（２）のｎ個の元ｂｎ−１，．．．，ｂ0からなる入力列Ｘを受け付け、ｉ＝ｄ−１，．．．，０について、ｗ個の元ｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉに含まれる元ｂｗ×（ｉ+１）−１を抽出値ｃｉとして得、ワードＸｉごとにｗ個の元ｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，Ｉ０からなるワードＳｉを得、ｄ個のワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓを得、シフト列Ｓとフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］とに対する出力列Ｙ＝Ｓ＋Ｍ［ｃｄ−１，．．．，ｃ０］∈ＧＦ（２ｎ）を得る。ただし、ｗが１以上の整数であり、ｄが２以上の整数であり、ｎ＝ｗ×ｄを満たし、ＧＦ（２）が位数２のガロア体であり、Ｉ０がガロア体ＧＦ（２）の加法単位元であり、ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０がｎ次既約多項式であり、ｘが不定元であり、係数ｅｎ，．．．，ｅ０がガロア体ＧＦ（２）のｎ＋１個の元である。Ｆがｎ個の元ｅｎ−１，．．．，ｅ０からなる列であり、ｊ＝ｄ−２，．．．，０であり、Ｋｊがガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，．．．，ｋｊ，０からなる列である。列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）が抽出値ｃｊであり、列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）以外の元が加法単位元Ｉ０である。抽出値ｃｄ−１が加法単位元Ｉ０である場合のＨがｎ個の加法単位元Ｉ０からなる列であり、抽出値ｃｄ−１が加法単位元Ｉ０でない場合のＨが列Ｆである。フィードバック列は
【数１】
0005730812.tif 000002
を満たす。
【００１４】
本発明の第２態様では、ｎ個のビットｂｎ−１，．．．，ｂ0からなる入力列Ｘを受け付け、ｉ＝ｄ−１，．．．，０について、ｗ個のビットｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉに含まれるｂｗ×（ｉ+１）−１を抽出値ｃｉとして得、ワードＸｉごとにｗ個のビットｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，０からなるワードＳｉを得、ｄ個のワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓを得、シフト列Ｓとフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］との排他的論理和である出力列Ｙを得る。ただし、ｗが１以上の整数であり、ｄが２以上の整数であり、ｎ＝ｗ×ｄを満たし、ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０がｎ次既約多項式であり、ｘが不定元であり、ビットｅｎ，．．．，ｅ０が係数であり、Ｆがｎ個のビットｅｎ−１，．．．，ｅ０からなる列であり、ｊ＝ｄ−２，．．．，０であり、Ｋｊがビットｋｊ，ｎ−１，．．．，ｋｊ，０からなる列である。列Ｋｊに含まれるｋｊ，ｗ×（ｊ＋１）が抽出値ｃｊであり、列Ｋｊに含まれるｋｊ，ｗ×（ｊ＋１）以外のビットが０である。フィードバック列は
【数２】
0005730812.tif 000003
を満たす。
【発明の効果】
【００１５】
本発明では、線形フィードバックシフトレジスタでの「２倍算」をＳＩＭＤ演算によって効率的に実行できる。
【図面の簡単な説明】
【００１６】
【図１】実施形態のデータ構成を例示するための図。
【図２】実施形態の演算装置の機能構成を例示するための図。
【図３】実施形態の演算方法を説明するための図。
【発明を実施するための形態】
【００１７】
本発明の実施形態を説明する。
＜構成＞
図１に例示するように、本形態の演算装置１は、テーブル記憶部１１、記憶部１２、入力部１３、出力部１４、制御部１５、抽出部１６、シフト部１７、および演算部１８を有する。記憶部１２はレジスタ１２１〜１２５を有する。演算装置１は、ＳＩＭＤ演算器を備える公知のコンピュータに所定のプログラムが読み込まれることで構成される特別な装置である。抽出部１６、シフト部１７、および演算部１８は、ＳＩＭＤ演算によってワードごとに各処理を実行する。
【００１８】
＜処理＞
図２および図３を参照しつつ、本形態の処理を説明する。
≪Ｘの入力（ステップＳ１１）≫
「２倍算」の対象となる入力列Ｘ∈ＧＦ（２ｎ）が入力部１３に入力される。入力列Ｘは前述の式（１）のｎ−１次多項式のｎ個の係数ｂｎ−１，．．．，ｂ0∈ＧＦ（２）からなる。例えば、ビット実装の場合、入力列Ｘはｎ個のビットｂｎ−１，．．．，ｂ0∈｛０，１｝からなるビット列である。ただしｎ＝ｗ×ｄであり、ｗはワードを構成する元（ビット）の個数を表す１以上の整数であり、ｄはワードの個数を表す２以上の整数である。入力された入力列Ｘはレジスタ１２１に格納される。
【００１９】
≪抽出値の抽出（ステップＳ１２）≫
次に抽出部１６が、ｉ＝ｄ−１，．．．，０について、レジスタ１２１に格納されたｗ個の元ｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなる処理単位であるワードＸｉに含まれる元ｂｗ×（ｉ+１）−１（各ワードＸｉ内で最も大きな次数に対応する係数）を抽出し、当該元ｂｗ×（ｉ+１）−１を抽出値ｃｉとして出力する。例えばビット実装の場合、抽出部１６はビットｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉからなるワードＸｉ（ただしｉ＝ｄ−１，．．．，０）ごとに、ワードＸｉに含まれるビットｂｗ×（ｉ+１）−１を抽出値ｃｉとして得て出力する。これらｄ個の抽出値ｃｄ−１，．．．，ｃ０はレジスタ１２２に格納される。
【００２０】
≪左シフト演算（ステップＳ１３）≫
次にシフト部１７が、ｉ＝ｄ−１，．．．，０について、レジスタ１２１に格納されたワードＸｉごとに独立に左シフト演算を行い、ｗ個の元ｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，Ｉ０からなるワードＳｉを得て出力する。ただしＩ０はガロア体ＧＦ（２）の加法単位元である。例えばビット実装の場合、シフト部１７は、ワードＸｉ（ただしｉ＝ｄ−１，．．．，０）ごとに独立にワードＸｉに対する１ビットの左シフト演算を行い、ｗ個のビットｂｗ×（ｉ+１）−２，．．．，ｂｗ×ｉ，０からなるワードＳｉを得て出力する。なお、ワードＸｉごとのαビットの左シフト演算（「≪ＳＩＭＤα」と表す）とは、ワードＸｉを構成するビットｂｗ×（ｉ+１）−１，．．．，ｂｗ×ｉを次数の大きな方向（左方向）にαビットシフトし、ワードＸｉ内で最も次数の小さなビットからα番目までのビットを０にする処理を意味する。出力されたｄ個のワードＳｄ−１，．．．，Ｓ０からなるシフト列Ｓはレジスタ１２３に格納される。
【００２１】
≪フィードバック列の抽出（ステップＳ１４）≫
テーブル記憶部１１には、ｃｄ−１，．．．，ｃ０からなる列（順序も考慮した列）に対応する予め得られたフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］からなるテーブルが格納されている。列ｃｄ−１，．．．，ｃ０は２ｄ通り存在し、テーブルは２ｄ個のフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］の配列からなる。
【００２２】
フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］は、以下の関係を満たすガロア体ＧＦ（２ｎ）の元である。
【数３】
0005730812.tif 000004
ただし、Ｈは抽出値ｃｄ−１に対応する。抽出値ｃｄ−１が加法単位元Ｉ０である場合のＨはｎ個の加法単位元Ｉ０からなる列である。一方、抽出値ｃｄ−１が加法単位元Ｉ０でない場合のＨは列Ｆである。列ＦはＧＦ（２）上のｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０の係数ｅｎ，．．．，ｅ０∈ＧＦ（２）からｅｎを除いたｅｎ−１，．．．，ｅ０からなる。Ｋｊはガロア体ＧＦ（２）のｎ個の元ｋｊ，ｎ−１，．．．，ｋｊ，０からなる。列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）は抽出値ｃｊであり、列Ｋｊに含まれる元ｋｊ，ｗ×（ｊ＋１）以外の元は加法単位元Ｉ０である。
【００２３】
例えばビット実装の場合、フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］は、以下の関係を満たすビット列である。
【数４】
0005730812.tif 000005
ただし、列Ｆはｎ次既約多項式ｆ（ｘ）＝ｅｎ×ｘｎ＋ｅｎ−１×ｘｎ−１＋．．．＋ｅ０の係数ｅｎ，．．．，ｅ０∈｛０，１｝からｅｎを除いたｅｎ−１，．．．，ｅ０からなる。Ｋｊはｎ個のビットｋｊ，ｎ−１，．．．，ｋｊ，０からなる。列Ｋｊに含まれるビットｋｊ，ｗ×（ｊ＋１）は抽出値ｃｊであり、列Ｋｊに含まれるビットｋｊ，ｗ×（ｊ＋１）以外のビットは０である。各Ｋｊは、例えばｎ個のビット０，，．．．，０，ｃｊからなるビット列（０，，．．．，０，ｃｊ）∈｛０，１｝ｎに対してｗ×（ｊ＋１）ビットの左シフト演算を施すことで得られる。
Ｋｊ＝（０，，．．．，０，ｃｊ）≪ｗ×（ｊ＋１）
【００２４】
演算部１８は、レジスタ１２２からｃｄ−１，．．．，ｃ０を読み出し、レジスタ１２２から読み出した列ｃｄ−１，．．．，ｃ０に対応するフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］をテーブル記憶部１１から読み出し、当該フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］をレジスタ１２４に格納する。
【００２５】
≪出力列生成（ステップＳ１５）≫
演算部１８は、レジスタ１２３からシフト列Ｓを読み出し、レジスタ１２４からフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］を読み出す。演算部１８は、読み出したシフト列Ｓとフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］とに対する出力列Ｙ＝Ｓ＋Ｍ［ｃｄ−１，．．．，ｃ０］∈ＧＦ（２ｎ）を得て出力する。演算部１８は、ｉ＝ｄ−１，．．．，０について、それぞれ以下のようにＹｉ＝Ｓｉ＋Ｍｉの演算を行う。
（ｙｗ×（ｉ＋１）−１，．．．，ｙｗ×ｉ）
＝（ｂｗ×（ｉ+１）−２＋ｍｗ×（ｉ＋１）−１，．．．，ｂｗ×ｉ＋ｍｗ×ｉ＋１，Ｉ０＋ｍｗ×ｉ）
ただし、フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］はｄ個のワードＭｉ（ただしｉ＝ｄ−１，．．．，０）からなり、各ワードＭｉがｗ個の元ｍｗ×（ｉ＋１）−１，．．．，ｍｗ×ｉ∈ＧＦ（２）からなる。また、出力列Ｙはｄ個のワードＹｉ（ただしｉ＝ｄ−１，．．．，０）からなり、各ワードＹｉはＧＦ（２）のｗ個の元ｙｗ×（ｉ＋１）−１，．．．，ｙｗ×ｉ∈ＧＦ（２）からなる。
【００２６】
例えばビット実装の場合、演算部１８は、シフト列Ｓとフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］との排他的論理和Ｓ（＋）Ｍ［ｃｄ−１，．．．，ｃ０］である出力列Ｙを得て出力する。演算部１８は、ｉ＝ｄ−１，．．．，０について、それぞれ以下のようにＹｉ＝Ｓｉ（＋）Ｍｉの演算を行う。
（ｙｗ×（ｉ＋１）−１，．．．，ｙｗ×ｉ）
＝（ｂｗ×（ｉ+１）−２（＋）ｍｗ×（ｉ＋１）−１，．．．，ｂｗ×ｉ（＋）ｍｗ×ｉ＋１，Ｉ０（＋）ｍｗ×ｉ）
ただし、フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］はｄ個のワードＭｉ（ただしｉ＝ｄ−１，．．．，０）からなり、各ワードＭｉはｗ個のビットｍｗ×（ｉ＋１）−１，．．．，ｍｗ×ｉ∈｛０，１｝からなる。出力列Ｙはｄ個のワードＹｉ（ただしｉ＝ｄ−１，．．．，０）からなり、各ワードＹｉはＧＦ（２）のｗ個の元ｙｗ×（ｉ＋１）−１，．．．，ｙｗ×ｉ∈｛０，１｝からなる。
【００２７】
出力された出力列Ｙはレジスタ１２５に格納される。
【００２８】
≪出力列出力（ステップＳ１６）≫
出力部１４は、レジスタ１２５から出力列Ｙを読み出し、当該出力列Ｙを出力する。
【００２９】
＜アルゴリズム＞
以下に、ビット実装する場合の本形態のアルゴリズムを示す。
［Ａｌｇｏｒｉｔｈｍ２］
入力：Ｘ，Ｍ[]
出力：Ｙ
１：ワードＸｉごとにｃｉを抽出
２：Ｓ←Ｘ≪ＳＩＭＤ１
３：ｃｄ−１，．．．，ｃ０に対応するＭ［ｃｄ−１，．．．，ｃ０］抽出
４：Ｙ←Ｓ（＋）Ｍ［ｃｄ−１，．．．，ｃ０］
５：Ｙ出力
【００３０】
＜具体例＞
簡単な例として、ｎ＝４、ｗ＝２、ｄ＝２、ｆ（ｘ）＝ｘ４＋ｘ＋１、ｇ（ｘ）＝α３×ｘ３＋α２×ｘ２＋α１×ｘ＋α０である場合に、本形態の方法によって、以下ようなｘ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）の係数ｙ３，ｙ２，ｙ１，ｙ０∈｛０，１｝を求める例を示す。
ｘ×ｇ（ｘ） ｍｏｄ ｆ（ｘ）
＝α３×ｘ４＋α２×ｘ３＋α１×ｘ２＋α０×ｘ ｍｏｄ （ｘ４＋ｘ＋１）
＝（α２×ｘ３＋α１×ｘ２＋α０×ｘ）＋α３×（ｘ＋１）
＝α２×ｘ３＋α１×ｘ２＋（α０＋α３）×ｘ＋α３
ｙ３＝α２
ｙ２＝α１
ｙ１＝α０＋α３
ｙ０＝α３
【００３１】
α３，α２，α１，α０∈｛０，１｝からなる入力列Ｘがレジスタ１２１に格納される（ステップＳ１１）。抽出値ｃ１＝α３、ｃ０＝α１がレジスタ１２２に格納される（ステップＳ１２）。ワードごとの左シフト演算によって得られたα２，０，α０，０がレジスタ１２３に格納される（ステップＳ１３）。抽出値ｃ１＝α３、ｃ０＝α１に対応するフィードバック列Ｍ［ｃ１，ｃ０］が読み出され（ステップＳ１４）、（ｙ３，ｙ２，ｙ１，ｙ０）＝（α２（＋）ｍ３，ｍ２，α０（＋）ｍ１，ｍ０）が得られる（ステップＳ１５）。
【００３２】
この例のフィードバック列Ｍ［ｃ１＝α３，ｃ０＝α１］は以下の４種類であり、（ｙ３，ｙ２，ｙ１，ｙ０）＝（α２（＋）ｍ３，ｍ２，α０（＋）ｍ１，ｍ０）＝（α２，α１，α０＋α３，α３）を満たす。
Ｍ［０，０］＝（０，０，０，０）
Ｍ［０，１］＝（０，１，０，０）
Ｍ［１，０］＝（０，０，１，１）
Ｍ［１，１］＝（０，１，１，１）
【００３３】
＜本形態の特徴＞
本形態の各ステップＳ１２〜Ｓ１５では、複数のワードに対して同一の処理が実行される。また本形態では、Ａｌｇｏｒｉｔｈｍ１のような分岐処理もない。さらに本形態では、ワードごとの左シフト演算に伴って必要となるワード間の値の移動処理と、最大次数よりも大きな項にあふれた係数に対応する係数を最大次数以下の項の係数に加算（例えば排他的論理和）するフィードバック演算と、が同時に行われる。このように本形態では、線形フィードバックシフトレジスタでの「２倍算」をＳＩＭＤ演算によって効率的に実行できる。すなわち本形態では、ＳＩＭＤ演算を４回呼び出すだけで「２倍算」を計算でき、高速に処理可能となる。これにより、ＯＣＢなどの暗号利用モードを効率的に実装可能になった。さらに、フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］を事前計算しておくことで、より演算が効率化できる。
【００３４】
＜変形例等＞
なお、本発明は上述の実施の形態に限定されるものではない。例えば、ステップＳ１３の実行後にステップＳ１４を実行するのではなく、ステップＳ１４の実行後にステップＳ１３が実行されてもよい。あるいは、ステップＳ１３および１４が同時に実行されてもよい。その他、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００３５】
または、フィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］を事前計算しておくのではなく、必要に応じてフィードバック列Ｍ［ｃｄ−１，．．．，ｃ０］が逐一計算されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００３６】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。例えば、Ｉｎｔｅｌ（登録商標）アーキテクチャではＳＳＥで１２８ビットレジスタｘｍｍ（登録商標）が導入され、ＳＳＥ２でｘｍｍレジスタに対する６４ビットワード命令群ｍｏｖｍｓｋｐｄ、またｐｓｌｌｑもしくはｐａｄｄｑ命令が導入された。ｍｏｖｍｓｋｐｄは６４ビットワード毎の最上位ビットを通常レジスタに書き出す命令であり、ｐｓｌｌｑは６４ビットワード毎にシフトする命令、またｐａｄｄｑは６４ビットワード毎に加算する命令である。Ｉｎｔｅｌアーキテクチャはｎ＝１２８（ｗ＝６４，ｄ＝２）に対する、上記の実施形態で必要なＳＩＭＤ演算器を全て備えている。Ｉｎｔｅｌアーキテクチャでも効率的に上記の処理を実施できる。Ｉｎｔｅｌ  ＣＰＵのＮｅｈａｌｅｍ（登録商標）以降のアーキテクチャではブロック暗号ＡＥＳを高速に実現するための命令セットが実装されている。ＡＥＳ命令はｘｍｍレジスタもしくはｙｍｍレジスタに対してのみ実行可能であり、通常レジスタにＡＥＳ対象のデータが保存されている場合はｘｍｍレジスタ等に移動する必要がある。通常レジスタに対して、「２倍算」はそれなりに効率的に実装可能であるが、ＡＥＳ命令と組み合わせる場合は、ｘｍｍなどのレジスタへの移動命令を必要とし、効率が悪くなる。本形態では、ＡＥＳと共に利用されることが多い「２倍算」をｘｍｍレジスタなどを利用するＳＩＭＤ命令で効率的に実装できる。
【００３７】
上記の処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００３８】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００３９】
１  演算装置
１３  入力部
１４  出力部
１６  抽出部
１７  シフト部
１８  演算部
【図１】
0005730812.tif 000010
【図２】
0005730812.tif 000011
【図３】
0005730812.tif 000012