(57)【要約】  メッセージ認証コード（ＭＡＣ）が電子回路において生成され、そこでＭＡＣ完全性によってデータ値（ＰＤ）が保護される。電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）が受信される。第１の暗号化された値（Ｋ’）をＲＮＤ及びＫから生成する第１の関数Ｇ（ＲＮＤ，Ｋ）が評価される。但し、Ｋは電子回路に格納されている秘密鍵の値である。第２の暗号化された値（Ｋ”）をＲＮＤ及びＫから生成する第２の関数Ｆ（ＲＮＤ，Ｋ）が評価される。次いで、ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lに基づいてＭＡＣが生成される。ここで、ｍ1、ｍ2，．．．，ｍlは、体ＧＦ（２n）においてｌ組の要素としてデータ値（ＰＤ）を表すことによって導き出される（但し、ｎは０よりも大きい整数）。上記ＭＡＣ及び他のＭＡＣを生成するためのハードウェアの効率的な配置構成も開示される。【選択図】  図９
2010513941.tif 000002
【特許請求の範囲】
【請求項１】
認証コードを生成する装置であって、
複数の制御信号を生成するための制御・サポート論理回路と、
シフトレジスタと、フィードバック回路とを備えた線形フィードバックシフトレジスタ（ＬＦＳＲ）回路と、
前記ＬＦＳＲ回路に接続された追加回路と、
を備え、
第１の状態の前記制御信号は、前記ＬＦＳＲ回路と前記追加回路とを鍵生成装置として一体的に機能させ、
第２の状態の前記制御信号は、前記ＬＦＳＲ回路と前記追加回路とを乗算器として一体的に機能させる
ことを特徴とする装置。
【請求項２】
前記装置は電子回路の一部であり、
前記装置は、
前記電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記電子回路に記憶されている秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第１の値を生成する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第２の値を生成する論理回路と、
を備え、
前記制御・サポート論理回路は信号を生成する論理回路を備え、該信号は、
前記ＬＦＳＲ回路に前記第１の値から第１の擬似ランダム値を生成させ、
前記第２の値から第２の擬似ランダム値を生成する第２の線形フィードバックシフトレジスタとして前記追加回路が利用されるようにし、
前記ＬＦＳＲ回路と前記追加回路とを前記鍵生成装置として一体的に機能させ、
前記第１の擬似ランダム値と前記第２の擬似ランダム値とから第１の鍵の値（Ｋ’）を前記鍵生成装置に生成させる
ことを特徴とする請求項１に記載の装置。
【請求項３】
前記制御・サポート論理回路は、信号を生成する論理回路を備え、該信号は、
一連の項Ｋ’i+1と（ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍiＫ’i），（１≦ｉ≦ｌ）とを前記ＬＦＳＲ回路と追加回路とに同時に生成させ、
ｍ1、ｍ2，．．．，ｍlは、体ＧＦ（２n）（ｎは０よりも大きい整数）におけるｌ組の要素として周辺機器データ（ＰＤ）によって導き出される
ことを特徴とする請求項２に記載の装置。
【請求項４】
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第３の値を生成する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第４の値を生成する論理回路と、を備え、
前記制御・サポート論理回路は信号を生成する論理回路を備え、
該信号は、
前記ＬＦＳＲ回路に前記第３の値から第３の擬似ランダム値を生成させ、
第４の擬似ランダム値を前記第４の値から生成する前記第２の線形フィードバックシフトレジスタとして前記追加回路が利用されるようにさせ、
前記ＬＦＳＲ回路と前記追加回路とを前記鍵生成装置として一体的に機能させて、前記第３の擬似ランダム値と前記第４の擬似ランダム値とから第２の鍵の値（Ｋ”）を生成させ、
前記第２の鍵の値（Ｋ”）が（ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l）と組み合わされるようにさせ、それによってメッセージ認証コード（ＭＡＣ）：
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lを生成させる
ことを特徴とする請求項３に記載の装置。
【請求項５】
前記追加回路は、
シフトレジスタとフィードバック回路とを備えた多目的論理回路と、
前記ＬＦＳＲ回路と、前記多目的論理回路と、置換論理回路とによって供給される加算信号用のための合計回路と、
前記合計回路によって供給される１以上の信号を受信するための入力ポートと、前記合計回路へ信号を供給するための出力ポートとを備えた前記置換論理回路と、
を備え、
前記多目的論理回路の前記フィードバック回路を経由してフィードバックされた信号が、前記ＬＦＳＲ回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号のいずれかによって、又は、前記多目的論理回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号によって、選択的に供給され、
前記多目的論理回路の前記シフトレジスタのフィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、前記多目的論理回路の前記シフトレジスタの入力段が前記フィードバック信号を利用できるようになっており、
前記鍵生成装置はストリーム暗号生成装置であり、
前記制御信号の前記第１の状態は、前記ＬＦＳＲ回路と、前記多目的論理回路と、前記合計回路と、前記置換論理回路とを前記ストリーム暗号生成装置として一体的に機能させ、
前記制御信号の前記第２の状態は、前記ＬＦＳＲ回路と、前記多目的論理回路の前記フィードバック回路とを前記乗算器として一体的に機能させるようになっている
ことを特徴とする請求項１に記載の装置。
【請求項６】
前記制御信号の前記第２の状態は、さらに、乗算の積を前記多目的論理回路の前記シフトレジスタの中へ格納させることを特徴とする請求項５に記載の装置。
【請求項７】
前記合計回路により動作されて、１以上の供給信号を受信し、格納するＫ’レジスタで示されるシフトレジスタを備えることを特徴とする請求項５に記載の装置。
【請求項８】
値１のデュアル基底表現を前記ＬＦＳＲ回路の前記シフトレジスタの中へロードするための回路と、
前記Ｋ’レジスタの出力信号を乗算中オペランドとして用いられるように多目的論理回路へ供給させる回路と、
を備えることを特徴とする請求項７に記載の装置。
【請求項９】
前記制御信号の第３の状態に応じて、前記多目的論理回路のシフトレジスタから得られた値を前記ＬＦＳＲ回路の前記シフトレジスタの中へコピーするための回路を備えることを特徴とする請求項５に記載の装置。
【請求項１０】
補助シフトレジスタと、
補助フィードバック回路と、
を備え、
前記補助フィードバック回路を介してフィードバックされる信号が、前記ＬＦＳＲ回路の前記シフトレジスタの１以上の段によって供給される出力信号であり、
前記補助フィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、前記補助シフトレジスタの入力段が前記フィードバック信号を利用することができ、
前記制御信号の第３の状態は、次の動作、すなわち、
前記第１の積を生成する乗算器として一体的に機能すると共に前記第１の積が生成されると、該第１の積を前記多目的論理回路の前記シフトレジスタの中へ格納するようになっている、前記多目的論理回路の前記ＬＦＳＲ回路並びに前記フィードバック回路と、
第２の積を生成し、該第２の積が生成されると、該積を前記補助シフトレジスタの中へ格納する乗算器として一体的に機能する前記ＬＦＳＲ回路及び前記補助フィードバック回路と、を同時に実行させる
ことを特徴とする請求項５に記載の装置。
【請求項１１】
前記合計回路によって供給される１以上の信号を、前記補助シフトレジスタによって供給される対応する番号の信号と順次結合する加算器を備えることを特徴とする請求項１０に記載の装置。
【請求項１２】
出力信号を補助フィードバック回路へ供給するために前記加算器が接続され、
前記加算器の前記出力信号を補助シフトレジスタへ供給するために前記補助フィードバック回路が接続される
ことを特徴とする請求項１０に記載の装置。
【請求項１３】
シフトレジスタと、フィードバック回路とを備えたＬＦＳＲに接続されている線形フィードバックシフトレジスタ（ＬＦＳＲ）回路及び追加回路を備えた装置において認証コードを生成する方法であって、
第１の動作モードにおいて、前記ＬＦＳＲ回路と前記追加回路とを鍵生成装置として一体的に機能させ、
第２の動作モードにおいて、前記ＬＦＳＲ回路と前記追加回路とを乗算器として一体的に機能させる
ことを特徴とする方法。
【請求項１４】
電子回路において実行される方法であって、
前記電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記電子回路に格納されている秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第１の値を生成するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第２の値を生成するステップと、
前記ＬＦＳＲ回路に前記第１の値から第１の擬似ランダム値を生成させるステップと、
第２の擬似ランダム値を前記第２の値から生成する第２の線形フィードバックシフトレジスタとして前記追加回路が利用されるようにするステップと、
前記ＬＦＳＲ回路と前記追加回路とを鍵生成装置として一体的に機能させることによって前記第１の擬似ランダム値と前記第２の擬似ランダム値とから第１の鍵の値（Ｋ’）を生成するステップと、
を有することを特徴とする請求項１３に記載の方法。
【請求項１５】
一連の項Ｋ’i+1と（ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍiＫ’i）（１≦ｉ≦ｌ）とを前記ＬＦＳＲ回路と追加回路とに同時に生成させるステップを有し、
ｍ1、ｍ2，．．．，ｍlは、体ＧＦ（２n）（ｎは０よりも大きい整数）におけるｌ組の要素として周辺機器データ（ＰＤ）によって導き出される
ことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第３の値を生成するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第４の値を生成するステップと、
前記ＬＦＳＲ回路に前記第３の値から第３の擬似ランダム値を生成させるステップと、
第４の擬似ランダム値を前記第４の値から生成する前記第２の線形フィードバックシフトレジスタとして前記追加回路が利用されるようにするステップと、
前記ＬＦＳＲ回路と前記追加回路とを前記鍵生成装置として一体的に機能させることによって前記第３の擬似ランダム値と前記第４の擬似ランダム値とから第２の鍵の値（Ｋ”）を生成するステップと、
前記追加回路に、前記第２の鍵の値（Ｋ”）を（ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l）と組み合わせさせ、それによって、メッセージ認証コード（ＭＡＣ）：
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lを生成するようにするステップと、
を有することを特徴とする請求項１５に記載の方法。
【請求項１７】
前記追加回路は、
シフトレジスタとフィードバック回路とを備えた多目的論理回路であって、
前記ＬＦＳＲ回路と、前記多目的論理回路と、置換論理回路とによって供給される加算信号用の合計回路と、
前記合計回路によって供給される１以上の信号を受信するための入力ポートと、前記合計回路へ信号を供給するための出力ポートとを備えた前記置換論理回路と、を備え、
前記多目的論理回路の前記フィードバック回路を経由してフィードバックされた信号が、前記ＬＦＳＲ回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号のいずれかによって、又は、前記多目的論理回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号によって選択的に供給され、
前記多目的論理回路の前記シフトレジスタのフィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、前記多目的論理回路の前記シフトレジスタの入力段が前記フィードバック信号を利用できるようになっており、
前記第１の動作モードは、前記ＬＦＳＲ回路と、前記多目的論理回路と、前記合計回路と、前記置換論理回路とを前記鍵生成装置として一体的に機能させるステップを有し、
前記第２の動作モードは、前記ＬＦＳＲ回路と、前記多目的論理回路の前記フィードバック回路とを前記乗算器として一体的に機能するようにさせるステップを有する
ことを特徴とする請求項１３に記載の方法。
【請求項１８】
前記第２の動作モードは、乗算の積が前記多目的論理回路の前記シフトレジスタの中へ格納されるようにさせるステップをさらに有することを特徴とする請求項１７に記載の方法。
【請求項１９】
Ｋ’レジスタとして示されるシフトレジスタを動作させて、合計回路により供給される１以上の供給信号を受信し、格納するステップを有することを特徴とする請求項１７に記載の方法。
【請求項２０】
値１のデュアル基底表現を前記ＬＦＳＲ回路の前記シフトレジスタの中へロードするステップと、
前記Ｋ’レジスタの出力信号を乗算中オペランドとして用いられるように多目的論理回路へ供給させるステップと、を有することを特徴とする請求項１９に記載の方法。
【請求項２１】
前記多目的論理回路のシフトレジスタから得られた値を前記ＬＦＳＲ回路の前記シフトレジスタの中へコピーするステップを有することを特徴とする請求項１７に記載の方法。
【請求項２２】
前記ＬＦＳＲ回路及び前記多目的論理回路の前記フィードバック回路が、第１の積を生成する乗算器として一体的に機能し、前記第１の積が生成されると、該第１の積を前記多目的論理回路の前記シフトレジスタの中へ格納する動作と、
前記ＬＦＳＲ回路及び補助フィードバック回路が、第２の積を生成し、該第２の積が生成されると、該積を補助シフトレジスタの中へ格納する乗算器として一体的に機能する動作と、
を同時に実行させるステップを有し、
前記補助フィードバック回路を介してフィードバックされる信号は、前記ＬＦＳＲ回路の前記シフトレジスタの１以上の段によって供給される出力信号であり、
前記補助フィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成すると共に、前記補助シフトレジスタの入力段が前記フィードバック信号を利用できるようにする
ことを特徴とする請求項１７に記載の方法。
【請求項２３】
前記合計回路によって供給される１以上の信号を、前記補助シフトレジスタによって供給される対応する番号の信号と順次結合することによって合計を生成するステップを有することを特徴とする請求項２２に記載の方法。
【請求項２４】
前記合計を前記補助フィードバック回路へ供給するステップと、
前記加算器の前記出力信号を前記補助シフトレジスタへ供給するために前記補助フィードバック回路を動作させるステップと、
を有することを特徴とする請求項２３に記載の方法。
【請求項２５】
電子回路においてメッセージ認証コード（ＭＡＣ）を生成する方法であって、前記ＭＡＣはデータ値（ＰＤ）の完全性を保護し、
前記電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信するステップと、
第１の暗号化された値（Ｋ’）をＲＮＤ及びＫから生成する第１の関数Ｇ（ＲＮＤ，Ｋ）（但し、Ｋは前記電子回路に格納されている秘密鍵の値である）を評価するステップと、
第２の暗号化された値（Ｋ”）をＲＮＤ及びＫから生成する第２の関数Ｆ（ＲＮＤ，Ｋ）を評価するステップと、
前記メッセージ認証コードを下式、
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l、
に基づいて生成するステップと、
を有し、
ｍ1ｍ2，．．．，ｍlは、体ＧＦ（２n）におけるｌ組の要素として前記データ値（ＰＤ）により導き出される（但し、ｎは０よりも大きい整数）
ことを特徴とする方法。
【請求項２６】
第１の関数Ｇ（ＲＮＤ，Ｋ）を評価するステップは、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第１の値を生成するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第２の値を生成するステップと、
前記第１の値から第１の擬似ランダム値を生成するために第１の線形フィードバックシフトレジスタを利用するステップと、
前記第２の値から第２の擬似ランダム値を生成するために第２の線形フィードバックシフトレジスタを利用するステップと、
前記第１及び第２の擬似ランダム値をストリーム暗号生成装置に印加し、それによって、前記第１の暗号化された値（Ｋ’）を生成するようになっているステップと、
を有することを特徴とする請求項２５に記載の方法。
【請求項２７】
前記第２の関数Ｆ（ＲＮＤ，Ｋ）を評価するステップは、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第３の値を生成するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第４の値を生成するステップと、
前記第３の値から第３の擬似ランダム値を生成するために前記第１の線形フィードバックシフトレジスタを利用するステップと、
前記第４の値から第４の擬似ランダム値を生成するために前記第２の線形フィードバックシフトレジスタを利用するステップと、
前記第３及び第４の擬似ランダム値をストリーム暗号生成装置に印加し、それによって、前記第２の暗号化された値（Ｋ”）を生成するようになっているステップと、
を有することを特徴とする請求項２６に記載の方法。
【請求項２８】
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lに基づいて前記メッセージ認証コードを生成するステップは、
第１の乗算器回路と第２の乗算器回路とを同時に動作させて、それぞれのｍlＫ’i項とＫ’i+1項（１≦ｉ≦ｌ）とを同時に生成するステップを含み、
前記第１の乗算器回路は、前記第１の線形フィードバックシフトレジスタと、該第１の線形フィードバックシフトレジスタを含む前記第２の乗算器回路とを含む
ことを特徴とする請求項２７に記載の方法。
【請求項２９】
電子回路においてメッセージ認証コード（ＭＡＣ）を生成する装置であって、前記ＭＡＣはデータ値（ＰＤ）の完全性を保護し、
前記電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信する論理回路と、
第１の暗号化された値（Ｋ’）をＲＮＤ及びＫから生成する第１の関数Ｇ（ＲＮＤ，Ｋ）（但し、Ｋは前記電子回路に格納されている秘密鍵の値である）を評価する論理回路と、
第２の暗号化された値（Ｋ”）をＲＮＤ及びＫから生成する第２の関数Ｆ（ＲＮＤ，Ｋ）を評価する論理回路と、
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l
に基づいて前記メッセージ認証コードを生成する論理回路と、
を備え、
ｍ1ｍ2，．．．，ｍlは、体ＧＦ（２n）におけるｌ組の要素として前記データ値（ＰＤ）により導き出される（但し、ｎは０よりも大きい整数）
ことを特徴とする装置。
【請求項３０】
前記第１の関数Ｇ（ＲＮＤ，Ｋ）を評価する前記論理回路は、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第４の値を生成する論理回路と、
第１の線形フィードバックシフトレジスタと、
前記第１の値から第１の擬似ランダム値を生成するために前記第１の線形フィードバックシフトレジスタを利用する論理回路と、
第２の線形フィードバックシフトレジスタと、
前記第２の値から第２の擬似ランダム値を生成するために第２の線形フィードバックシフトレジスタを利用する論理回路と、
ストリーム暗号生成装置と、
前記第１及び第２の擬似ランダム値をストリーム暗号生成装置に印加し、それによって、前記第１の暗号化された値（Ｋ’）を生成するようになっている論理回路と、
を備えることを特徴とする請求項２９に記載の装置。
【請求項３１】
前記第２の関数Ｆ（ＲＮＤ，Ｋ）を評価する前記論理回路は、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第３の値を生成する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第４の値を生成する論理回路と、
前記第３の値から第３の擬似ランダム値を生成するために前記第２の線形フィードバックシフトレジスタを利用する論理回路と、
前記第４の値から第４の擬似ランダム値を生成するために前記第２の線形フィードバックシフトレジスタを利用する論理回路と、
前記第３及び第４の擬似ランダム値をストリーム暗号生成装置に印加し、前記第２の暗号化された値（Ｋ”）を生成する論理回路と、
を備えることを特徴とする請求項３０に記載の装置。
【請求項３２】
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lに基づいて前記メッセージ認証コードを生成する前記論理回路は、
前記第１の線形フィードバックシフトレジスタを含む第１の乗算器回路と、
前記第１の線形フィードバックシフトレジスタを含む第２の乗算器回路と、
第１の乗算器回路と第２の乗算器回路とを同時に動作させて、それぞれのｍlＫ’i項とＫ’i+1項（１≦ｉ≦ｌ）とを同時に生成する論理回路と、
を備えることを特徴とする請求項３１に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータに対して完全性保護を効率的に提供するステップに関する。
【背景技術】
【０００２】
不正な再プログラミングから機器を保護したいというニーズが多くのタイプのプログラム可能な電子機器に対して存在する。このニーズは（セルラ通信機器などの）移動通信機器について存在するものであり、このようなケースでは唯一のタイプの承認済みソフトウェアを機器上で実行することを保証する必要があるだけでなく、（安全な加入者情報モジュール（ＳＩＭ）のロックメカニズムなどの）機器に記憶されている機密情報に対する安全なロックメカニズムを提供することも保証する必要がある。不正な再プログラミングに対抗する保護を行うためのシステム・ソリューションにおける１つの重要な構成要素として、１回のプログラムが可能な（ＯＴＰ：ワンタイム・プログラマブル）メモリの利用がある。その名称が表しているように、ＯＴＰメモリは、情報を記憶領域の中へ一回だけ保存することが許されるタイプのメモリデバイスである。ＯＴＰメモリは不揮発性メモリ（すなわち、電源が切れているときにもメモリの情報を保持するメモリ）である。最初、ＯＴＰはプログラムされていない状態になっている。次いで、メモリビットをプログラムするプログラミング段が存在する（例えば、単一の処理時に１段ずつ、あるいは、ブロック全体としてプログラミングが行われるが、この特別の実装構成は、本解説を理解する上で本質的に重要な部分ではない）。（以下「ＯＴＰデータ」と呼ぶことにする）情報の保存に続いて、ＯＴＰメモリは、いずれの情報もメモリの当該部分に書き込まれないようにするいくつかの技術のうちの任意の技術によってロックされる。多くの場合、ＯＴＰがひとたび「ロック」状態に入ると、情報の消去は不可能となる。いくつかの実装構成では、消去は許されるが、この消去は、メモリビットのブロック全体に適用される場合にのみに許されるものである。個々のメモリロケーションに対して消去を選択的に適用することはできない。
【０００３】
ＯＴＰメモリは多くのタイプのアプリケーションにおいて有用である。多くの生じる可能性のある例のほんの１例として、移動通信機器がカスタマイズされる前に、機器のソフトウェアは（フラッシュメモリデバイスなどの）不揮発性メモリの中へ格納できなければならないという点が挙げられる。したがって、新たなソフトウェアとパラメータとを機器内へプログラムすることを許す、攻撃を受け易い「バージン（virgin）」状態が存在することになる。したがって、機器が工場から出荷されるとすぐに、いかなる制御されない方法でも機器を「バージン」状態へ戻すことができないことを確認することが重要になる。というのは、この「バージン」状態が不正な再プログラミングを可能にすることになるからである。ＯＴＰメモリはこの目的のために非常に有用なものである。というのは、ＯＴＰメモリの内容は、工場から出荷した機器をそうでない機器と識別する情報を保持するために用いることができるからである。例えば、機器のカスタマイズが終了すると、いわゆる製造フラグをＯＴＰメモリ内にセットすることが可能となる。次いで、このフラグは、機器がカスタマイズされていること、並びに、何らかの再プログラミングを行うには特別の認証処理を必要とすることを機器ブート用及びローダ用ソフトウェアに知らせることになる。
【０００４】
ＯＴＰ情報を利用するソフトウェアは、一般に（移動電話機などの移動通信装置のメインベースバンドプロセッサなどの）メインプロセッサ機器において実行される。これは、最も安全なＯＴＰベースのソリューションは、ＯＴＰメモリがメインプロセッサとして（移動電話機内のベースバンドプロセッサなどの）同じ集積回路（「チップ」）上に存在するソリューションであるということを意味するものである。なぜなら、このソリューションによってＯＴＰの読出し機能の改竄がはるかに困難になるからである。不都合なことに、複数の技術上及びコスト上の制約に起因して、オンチップＯＴＰメモリの提供は常に可能であるとはかぎらない。したがって、外部のハードウェア構成要素の中にＯＴＰメモリを実現しなければならない場合が多い。このような構成では、外部のハードウェア構成要素からメインプロセッサへＯＴＰ読出しを送るために通信リンクを設けることが必要となる。この通信リンクはＯＴＰメモリとベースバンドチップ間でのデータ転送操作に対してＯＴＰ読出し機能を曝すことになる。操作したデータによって、機器はその「バージン」状態に戻っているように思わされて、不正な再プログラミングを受けやすくなる可能性がある。
【０００５】
ＯＴＰメモリに関してここまで説明した状況は、周辺機器に記憶されているデータ（以後「周辺機器データ」又は「ＰＤ」と呼ぶことにする）が「メイン」プロセッサによる読出し時に不正操作に曝される場合に生じるさらに一般的な問題のほんの１例にすぎない。
【０００６】
暗号手段によってＰＤの読出し動作を保護することにより上記不正操作の脅威を著しく低減することが可能となる。さらに詳細には、メインプロセッサは、該メインプロセッサが周辺機器のメモリから読出し動作を開始する時刻に又はそのおよその時刻に、ランダムな（又は擬似ランダムな）チャレンジワード（ＲＮＤ）を外部のハードウェア構成要素へ送出することによって、メインプロセッサ自体と（ＯＴＰメモリなどの）周辺機器のメモリ間での通信リンクから該メインプロセッサが受信するデータが真正なものであるかどうかの判定を行うことが可能となる。外部のハードウェア構成要素は、周辺機器のメモリからデータを読み出すと共に、暗号化処理手順を用いて、周辺機器データから「メッセージ認証コード」（ＭＡＣ）と、事前に格納された秘密鍵（Ｋ）と、ランダムなチャレンジワード（ＲＮＤ）とを取得する。この生成されたＭＡＣは、次いで、周辺機器データと共にメインプロセッサへ返信される。メインプロセッサは、秘密鍵Ｋのコピーも保持し、秘密鍵Ｋと、受信済みの周辺機器データと、送出されたランダムなチャレンジワード（ＲＮＤ）とを用いて基準ＭＡＣ値の計算を行う。ＭＡＣが受信したＭＡＣ値に等しければ、受信した周辺機器データは有効なデータ（すなわち改竄を受けていない）と見なされる。
【０００７】
本目的及び他の目的のためにＭＡＣを構成する最も一般的な方法として、ＳＨＡ−Ｉ及びＭＤ５のようないわゆる一方向ハッシュ関数をＭＡＣのベースにする方法がある。この方法に関心をお持ちの読者は、さらに詳細については、非特許文献１（９．４章、ｐ．３３８〜３５１）を参照されたい。最も広く用いられているＭＡＣ関数のうちの１つは実際には一方向ハッシュ関数に基づくＨＭＡＣ関数である。この関数に関心をお持ちの読者は、非特許文献２を参照されたい。
【０００８】
例えば、（上述のＯＴＰデータなどの）周辺機器ユニットによって供給されるデータの完全性を保護するメカニズムの提供を目的として、周辺機器ユニットにおいてＭＡＣを生成する場合、考え得る最小の部品を用いてＭＡＣ計算用ハードウェアを実装することが望ましい。残念なことに、一方向ハッシュ関数又はブロック暗号に基づくＭＡＣの実装構成はかなり複雑な構成となるため、上記基準が満たされなくなる。例えば、最適化されたＳＨＡ−Ｉハードウェアの実装は単独で通常１４Ｋゲート前後のサイズを有するものとなる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ｊ．メネンゼス（Menezes），Ｐ．Ｃ．ヴァン  オールショット（van Oorschot），及びＳ．Ａ．ヴァンストーン（Vanstone）著「応用暗号法ハンドブック」（１９９７年）
【非特許文献２】「メッセージ認証用ＨＭＡＣ鍵・ハッシュ」、ＩＥＴＦ  ＲＦＣ２１０４
【発明の概要】
【発明が解決しようとする課題】
【００１０】
したがって、セキュリティ性の高いデータ完全性装置及び方法を部品効率良く提供することが望ましい。
【課題を解決するための手段】
【００１１】
「備える」という語が本明細書において用いられる場合、記載される特徴、数値、ステップまたは構成要素の存在を規定するものと解釈されるが、これら用語の使用は１以上の他の特徴、数値、ステップ、構成要素、またはそれらの組合せの存在または追加を排除するものではないことが強調されるべきである。
【００１２】
本発明の１つの側面によれば、前述の目的およびその他の目的は、認証コードを生成する方法と装置の少なくともいずれかを包含する実施形態において達成される。これは、線形フィードバックシフトレジスタ（ＬＦＳＲ）回路及びＬＦＳＲに接続された追加回路を備えた装置において、シフトレジスタ及びフィードバック回路を備えたＬＦＳＲを含むものであり、第１の動作モードでＬＦＳＲ回路及び追加回路を鍵生成装置として一体的に機能させると共に、第２の動作モードでＬＦＳＲ回路と追加回路とを乗算器として一体的に機能させるものである。
【００１３】
別の側面では、上記方法は電子回路において実施され、該方法には、ランダムなチャレンジワード（ＲＮＤ）を電子回路の外部にあるソースから受信するステップが含まれる。第１の値が、ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって生成される（但し、Ｋは電子回路に格納されている）。第２の値が、ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって生成される。ＬＦＳＲ回路によって第１の値から第１の擬似ランダム値が生成され、さらに、追加回路は、第２の値から第２の擬似ランダム値を生成する第２の線形フィードバックシフトレジスタとして利用される。ＬＦＳＲ回路と追加回路とを鍵生成装置として一体的に機能させることによって、第１の擬似ランダム値と第２の擬似ランダム値とから第１の鍵の値（Ｋ’）が生成される。
【００１４】
さらに別の側面では、ＬＦＳＲ回路と追加回路とによって一連の項Ｋ’i+1、及び、（ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍi，Ｋ’i）、（１≦ｉ≦ｌ）が同時に生成される。
ここで、ｍ1，ｍ2，．．．，ｍlは、体ＧＦ（２n）内のｌ組の要素として周辺機器データ（ＰＤ）を表すことにより導き出される。但し、ｎは０よりも大きい整数である。
【００１５】
さらに別の側面では、第３の値が、ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって生成される。第４の値が、ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって生成される。ＬＦＳＲ回路によって第３の値から第３の擬似ランダム値が生成され、さらに、追加回路は、第２の値から第４の擬似ランダム値を生成する第２の線形フィードバックシフトレジスタとして利用される。ＬＦＳＲ回路と追加回路とを鍵生成装置として一体的に機能させることによって、第１の擬似ランダム値と第２の擬似ランダム値とから第２の鍵の値（Ｋ”）が生成される。第２の鍵の値（Ｋ”）が（ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l）と組み合わされ、これによって、追加回路は下記のメッセージ認証コード（ＭＡＣ）を生成することになる。
【００１６】
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l
【００１７】
いくつかの実施形態では、認証コードを生成するステップは複数の制御信号を生成するステップを含み、該制御信号は、線形フィードバックシフトレジスタ（ＬＦＳＲ）回路、多目的論理回路、合計回路並びに置換論理回路をストリーム暗号生成装置として一体的に機能させる。さらに、ＬＦＳＲ回路及び多目的論理回路のフィードバック回路は乗算器として一体的に機能させられ、乗算の積が生成され、それによって、この積は多目的論理回路のシフトレジスタの中へ格納される。
【００１８】
ＬＦＳＲ回路はシフトレジスタとフィードバック回路とを含み、その場合、フィードバック回路は、シフトレジスタの対応する１以上の段により供給される１以上の出力信号から導き出されるフィードバック信号を生成するように構成される。フィードバック回路は、１以上の制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、シフトレジスタの入力段がフィードバック信号を利用できるように構成される。
【００１９】
多目的論理回路はシフトレジスタとフィードバック回路とを備え、その場合、多目的論理回路のフィードバック回路を介してフィードバックされる信号は、下記の少なくとも２つのソースのうちの１つのソースによって選択的に供給される：
（１）ＬＦＳＲ回路のシフトレジスタの対応する１以上の段によって供給される１以上の出力信号、又は、
（２）多目的論理回路のシフトレジスタの対応する１以上の段によって供給される１以上の出力信号。
【００２０】
また、多目的論理回路のシフトレジスタのフィードバック回路は、１以上の制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、多目的論理回路のシフトレジスタの入力段がフィードバック信号を利用できるように構成される。
【００２１】
上述の合計回路は、ＬＦＳＲ回路、多目的論理回路、及び置換論理回路によって供給される加算信号用の回路である。さらに、置換論理回路は、合計回路によって供給される１以上の信号を受信するための入力ポートと、合計回路へ信号を供給するための出力ポートとを備える。
【００２２】
別の側面では、Ｋ’レジスタで示されるシフトレジスタが合計回路により動作されて、１以上の供給信号を受信し、格納する。
【００２３】
さらに別の側面では、値１のデュアル基底表現がＬＦＳＲ回路のシフトレジスタの中へロードされると共に、乗算中のオペランドとして用いるためのＫ’レジスタの出力信号が多目的論理回路へ供給させられることになる。これはＫ’レジスタに格納されている値のデュアル基底表現を生成するために役に立つ。
【００２４】
さらに別の側面では、制御信号の第３の状態に応じて、多目的論理回路のシフトレジスタから得られた値がＬＦＳＲ回路のシフトレジスタの中へコピーされる。この機能の有用性を示す一例として、後続する乗算演算時に前回の演算から得られた結果を用いることが可能になるということが挙げられる。
【００２５】
さらに別の側面では、以下の動作が同時に実行される：
・  多目的論理回路のＬＦＳＲ回路とフィードバック回路とを第１の積を生成する乗算器として一体的に機能させることが可能であり、第１の積が生成されると、この第１の積は多目的論理回路のシフトレジスタの中へ格納される。
・  ＬＦＳＲ回路と補助フィードバック回路とを第２の積を生成する乗算器として一体的に機能させ、第２の積が生成されると、この第２の積は補助シフトレジスタの中へ格納される。
【００２６】
上記側面に従う実施形態において、補助フィードバック回路を介してフィードバックされた信号は、ＬＦＳＲ回路のシフトレジスタの１以上の段によって供給される出力信号となる。次いで、補助フィードバック回路は、１以上の制御信号によって指定された機能に基づいてフィードバック信号を生成する。補助シフトレジスタの入力段はフィードバック信号を利用できるようになっている。
【００２７】
さらに別の側面では、合計回路によって供給される１以上の信号を、補助シフトレジスタによって供給される対応する番号の信号と順次結合することによって合計信号が生成される。
【００２８】
さらに別の側面では、上記合計信号は補助フィードバック回路へ供給される。補助フィードバック回路が動作されて、補助シフトレジスタへ合計信号を供給する。
【００２９】
さらに別の側面では、メッセージ認証コード（ＭＡＣ）が電子回路において生成され、そこでＭＡＣによってデータ値（ＰＤ）の完全性が保護される。このステップには、電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信するステップが含まれる。第１の暗号化された値（Ｋ’）をＲＮＤとＫとから生成する第１の関数Ｇ（ＲＮＤ，Ｋ）が評価される。但し、Ｋは電子回路に格納されている秘密鍵の値である。第２の暗号化された値（Ｋ”）をＲＮＤとＫとから生成する第２の関数Ｆ（ＲＮＤ，Ｋ）が評価される。メッセージ認証コードは下式に基づいて生成される：
【００３０】
ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l
【００３１】
上式において、ｍ1、ｍ2，．．．，ｍlは、体ＧＦ（２n）内のｌ組の要素としてデータ値（ＰＤ）を表すことによって導き出される。但し、ｎは０よりも大きい整数である。
【００３２】
別の側面では、第１の関数Ｇ（ＲＮＤ，Ｋ）を評価するステップには、ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第１の値を生成するステップが含まれる。第２の値が、ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって生成される。第１の値から第１の擬似ランダム値を生成するために第１の線形フィードバックシフトレジスタが利用される。第２の値から第２の擬似ランダム値を生成するために第２の線形フィードバックシフトレジスタが利用される。第１及び第２の擬似ランダム値がストリーム暗号生成装置に印加され、それによって、第１の暗号化された値（Ｋ’）が生成されるようになっている。
【００３３】
さらに別の側面では、第２の関数Ｆ（ＲＮＤ，Ｋ）を評価するステップには、ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第３の値を生成するステップが含まれる。第４の値が、ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって生成される。第３の値から第３の擬似ランダム値を生成するために第１の線形フィードバックシフトレジスタが利用される。第４の値から第４の擬似ランダム値を生成するために第２の線形フィードバックシフトレジスタが利用される。第３及び第４の擬似ランダム値がストリーム暗号生成装置に印加され、それによって、第２の暗号化された値（Ｋ”）が生成されるようになっている。
【００３４】
さらに別の側面では、ＭＡＣ＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lに基づいてメッセージ認証コードを生成するステップには、第１の乗算器回路と第２の乗算器回路とを同時に動作させて、それぞれのｍiＫ’i項とＫ’i+1項（１≦ｉ≦ｌ）とを同時に生成するステップが含まれる。この場合、第１の乗算器回路には、第１の線形フィードバックシフトレジスタと、該第１の線形フィードバックシフトレジスタを含む第２の乗算器回路とが含まれる。
【図面の簡単な説明】
【００３５】
図面を参照して以下の詳細な説明を読むことにより本発明の目的及び利点は理解されるであろう。
【図１】メインプロセッサを収納する集積回路の外部にある周辺機器ユニットにＯＴＰメモリが実装された配置構成を示すブロック図である。
【図２】例示の線形フィードバックシフトレジスタを示すブロック図である。
【図３】本発明に一致する実施形態の１側面である例示のストリーム暗号回路を示すブロック図である。
【図４ａ】本発明に一致する実施形態の１側面であるＩＩＲフィルタにおいて用いられる関数への例示の入力を示す。
【図４ｂ】本発明に一致する実施形態の１側面であるＩＩＲフィルタにおいて用いられる例示のブール関数のスペクトルウォルシュのテーブルである。
【図５】（ｎ回のステップで）シーケンシャルにｙ∈ＧＦ（２n）にｘ∈ＧＦ（２n）を乗算する能力を備えた周知のデュアル基底のビットシリアル乗算器を示すブロック図である。
【図６】乗算の結果を受信するためのレジスタを装備した乗算器を示すブロック図である。
【図７】本発明に従う例示プロセスにおいて実行されるステップを描くフローチャートである。
【図８】第２の結果レジスタと第３の多段フィードバックレジスタとを図６に描かれている配置構成へ追加する利点を例示する回路構成を示すブロック図である。
【図９】Ｋ’及びＫ”を生成し、次いで、これらの値を用いて、ＭＡＣ値を計算することが可能な回路の例示の実施形態を示すブロック図である。
【発明を実施するための形態】
【００３６】
以下、図面を参照して本発明の種々の特徴を説明するが、図面では、同一要素に対して同一の参照番号が付されている。
【００３７】
本発明の種々の側面を幾つかの例示の実施形態と関係づけてより詳細に説明する。本発明の理解を容易にするために、プログラムされた命令を実行する能力を備えたコンピュータシステム又は他のハードウェアの要素により実施される動作シーケンスによって本発明の多くの側面を説明する。各実施形態において、種々の動作が、特別の回路（例えば、特別の機能を実行するために相互結合されたディスクリート論理ゲート）、１以上のプロセッサにより実行されるプログラム命令、または両者の組み合わせにより実行できることが認められる。さらに加えて、本明細書に記載の技術をプロセッサに実行させるための適切なコンピュータ命令セットを含む、固体メモリ、磁気ディスク、光ディスクまたは搬送波（無線周波数、音声周波数または光周波数の搬送波などの）任意の形態のコンピュータ読取可能な媒体において本発明は完全に実施可能である。従って、本発明の種々の側面は多くの異なる形式で実施することが可能であり、そのような形式は全て本発明の範囲に属するものと考えられる。本発明の種々の側面のそれぞれに対応する、このような任意の形式による実施形態は、本明細書に記載の動作を実行するように「構成された論理素子」、またはこれとは別に、記載の動作を実行する「論理素子」を意味することができる。
【００３８】
本発明の側面は、発明の背景のセクションに記載し、例示の構成を示すブロック図である図１に示したような認証手続きに対して適用可能である（但しこれらのみに限定されるわけではない）。上記例示の構成によって、メインプロセッサを含む集積回路の外部にある周辺機器ユニットに（ＯＴＰメモリなどの）周辺機器のメモリが実装されることになる。したがって、ＰＤの読出し処理手順は、メインプロセッサ１０１が、周辺機器のメモリ１０５を含む周辺機器ユニット１０３へ向かってランダムなチャレンジ（ＲＮＤ）を送出するステップ（ステップ１）を含むことになる。ランダムなチャレンジ（ＲＮＤ）と、周辺機器のメモリ内容（ＰＤ）、並びに、メインプロセッサを備えたユニットと周辺機器ユニット間で共有される秘密鍵１０７が完全性保護アルゴリズムへの入力として用いられる。次いで、完全性保護アルゴリズムから得られたメッセージ認証コード（ＭＡＣ）と共にＰＤがメインプロセッサ１０１へ返送される（ステップ２）。ＭＡＣは、メッセージ（この場合、周辺機器ユニットのメモリから読み出されたＰＤ）と、周辺機器ユニット１０３に記憶されている秘密鍵（Ｋ）との関数として生成された値である。メインプロセッサ１０１は、受信したＰＤと、秘密鍵Ｋ１０９自身のコピーと、最初に送信されたランダムなチャレンジ（ＲＮＤ）についてのその情報とに基づいて、受信した完全性値（ＭＡＣ）が予想していたものであるかどうかの判定を行うことによって、受信したＰＤの有効性のチェックを行う。
【００３９】
本発明の実施形態の側面は、ＭＡＣを生成する際に用いられる数学関数の特殊な数式に関するものである。
【００４０】
本発明の実施形態の他の側面は、効率的なハードウェア構成と、ＭＡＣ生成関数を計算する能力を備えたアルゴリズムとに関する。
【００４１】
これらの側面並びにその他の側面について以下さらに詳述する。
【００４２】
ＨはＭＡＣ関数を示すものとする；すなわち、ＭＡＣ＝Ｈ（Ｋ、ＲＮＤ、ＰＤ）。ＭＡＣ関数は以下の別個の３つの部分に分けることができる。
・マスキング鍵導出部
・完全性鍵導出部
・絶対的に安全なＭＡＣ部
絶対的に安全なＭＡＣ部は本願では関数Ｈ’（）によって示される。完全性鍵導出部は本願では関数Ｇ（）によって示し、この関数Ｇ（）が生成する完全性鍵は本願ではＫ’によって示される。すなわち、Ｋ’＝Ｇ（ＲＮＤ，Ｋ）（但し、ＲＮＤはランダムなチャレンジであり、Ｋは前述の秘密鍵である）。完全性鍵（Ｋ’）は総当たり攻撃に対抗してデータの完全性保護を提供する鍵である。
【００４３】
マスキング鍵導出関数は本願ではＦ（）によって示され、Ｆ（）が生成するマスキング鍵は本願ではＫ”、すなわち、Ｋ”＝Ｆ（ＲＮＤ，Ｋ）によって示される。マスキング鍵は完全性保護データのマスク／ブラインドを行う役割を果たし、それによって高められたセキュリティが追加されることになる。
【００４４】
関数Ｈは前述の基準を満たし、複数の異なる形式のうちの任意の形式をとることが可能である。本発明の例示の実施形態では、２つの鍵の値と共に入力として保護されるメッセージの形をとる関数形式（本願ではＨ’で示される）が用いられる。これらの鍵のうちの第１の鍵は完全性鍵（Ｋ’）であり、これらの鍵のうちの第２の鍵はマスキング鍵（Ｋ”）である。したがって、例示のＭＡＣ関数は以下のように表現することができる：
【００４５】
ＭＡＣ＝Ｈ（Ｋ，ＲＮＤ，ＰＤ）＝Ｈ’（Ｋ”，Ｋ’，ＰＤ）＝Ｈ’（Ｆ（ＲＮＤ，Ｋ）、Ｇ（ＲＮＤ，Ｋ），ＰＤ）
【００４６】
非常に高いセキュリティを示す関数は多項式評価法を用いて構成することができる。この一般的原理は公知のものであるため本明細書で詳細に説明する必要はない。上記の原理に関心をお持ちの読者は、さらなる情報については、Ｇ．カバチアンスキ、Ｂ．スミーツ及びＴ．ヨハンソンによる「誤り訂正コードを介する体系的コードの濃度」（情報理論に関するＩＥＥＥ会報、第４２巻、ｎｏ．２、１９９６年）を参照されたい。
【００４７】
本発明の実施形態は、ＭＡＣ関数（Ｈ’）の形式の多項式評価法を採用することによって上記特徴を利用するものである。この結果、Ｈ’に対して任意の所定値を計算するステップは、鍵生成と、乗算と、加算との３つのメインタスクを含むことになる。３つすべてを行う効率的な方法及び手段が本願において提示される。
【００４８】
例えば、Ｊ．Ｌ．マッシー（Massey）及びＲ．Ａ．ルーペル（Rueppel）による「デジタルシーケンスを符号化された形式に変換するための方法及び装置」（米国特許第４，７９７，９２２号、１９８９年）、並びに、ゲールマン、Ｊ．ペールソン、及びＢ．スミーツによる「ブルートゥースセキュリティ」（ｐ．７４〜８０、アーテック・ハウス、２００４年）に記載されている加算結合器ストリーム暗号技術（summation combiner stream cipher technology）によって初期値から擬似ランダム鍵を生成するステップを達成することができる。このような技術は、線形フィードバックシフトレジスタ（「ＬＦＳＲ」、但し、「ＬＦＳＲ」とはシフトレジスタの組み合わせ及び関連付けられたフィードバック回路を意味する）並びに追加のサポート用論理回路の利用に依拠するものである。
【００４９】
多項式乗算は、ＬＦＳＲ及び低複雑性サポート用ハードウェアを用いて非常に効率的に達成することも可能である。したがって、本発明に一致する実施形態の側面によれば、１組のＬＦＳＲが鍵生成と乗算の２つの目的のために用いられることになる。これによって、以下の記載から理解されるように、完全な関数Ｈからなる非常に効率的なハードウェアの実装が可能となる。
【００５０】
ＧＦ（２n）によってサイズ２nの有限体を示す。この体の中にｌ組の要素としてＰＤを表現する。すなわち、ＰＤ＝（ｍ1，ｍ2，．．．，ｍl）；ｍ1∈ＧＦ（２n）
この場合、関数Ｈ’（Ｋ”，Ｋ’，ＰＤ）は以下のように表現することができる：
【００５１】
Ｈ’（Ｋ”，Ｋ’，ＰＤ）＝Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’l  （１）
【００５２】
鍵Ｋ’及びＫ”が個々の新たなＭＡＣの計算のために完全にランダムに選ばれた場合、総当たり攻撃の成功確率は１×２-nに等しくなる。しかし、暗号上正常な関数ＦとＧとを発見できると仮定すれば、関数Ｆ及びＧによってＫとＲＮＤから導き出される鍵を用いて真の乱数値Ｋ’及びＫ”を置換する際にも上記理論値が有効であることを主張することができる。
【００５３】
ＬＦＳＲは、鍵生成と乗算の双方において用いられ、したがって本発明の様々な実施形態において重要な役割を果たすものとなる。図２は例示のＬＦＳＲ２００を示すブロック図である。ＬＦＳＲ２００は、入力段Ｓn-1及び出力段Ｓ0を含む複数個（ｎ個）の段を有するシフトレジスタ２０１を含む。ＬＦＳＲ２００には、シフトレジスタ２０１の出力段Ｓ0によって供給される出力信号を受信するように接続された第１の入力部を含む複数の入力部、並びに、シフトレジスタ２０１の別の対応する段の１つによって供給される出力信号を受信するように接続された１以上の別の入力部を有する多段フィードバック論理回路２０３が含まれている。多段フィードバック論理回路２０３は複数の段を備え、この複数の段は、個々の段が（シフトレジスタ２０１の対応する段によって供給される）対応する入力信号と、多段フィードバック論理回路２０３の隣接する先行段によって生成されたフィードバック信号との合計信号を含むフィードバック信号を生成するように構成されている。
【００５４】
多段フィードバック論理回路２０３の他の入力部の個数及び位置はアプリケーションによって変動する。図２に描かれている例示の実施形態は、以下のようにＬＦＳＲ２００の再構成を可能にする一般的ケースを示す実施形態である。これら他の段の各段は、（加算器２０５などの）加算器及び（乗算器２０７などの）乗算器を備える。乗算器２０７は、対応する段のシフトレジスタ２０１の出力部から信号を、そして、（Ｐn-3などの）多項式から項を受信する。乗算器２０７の出力はシフトレジスタの出力信号と、多項式の項との積を表す信号である。この積は加算器２０５の１つの入力部へ供給される。加算器２０５の別の入力部が、隣接する先行段からフィードバック信号（本例では、段０によって生成されたフィードバック信号）を受信する。加算器２０５からの出力は該加算器の２つの入力の合計を表し、追加の段が存在しなければ、この出力が多段フィードバック論理回路２０３内の次の段へ供給される。その場合、この出力が多段フィードバック論理回路２０３からの出力信号となる。
【００５５】
多項式の項Ｐ0．．．Ｐn-1を変えることによって多段フィードバック論理回路２０３の機能を変更できることが分かる。多段フィードバック論理回路２０３が構成された後、論理回路２０３の機能を変更する必要がないことが予想される場合、多項式の項が０になる任意の段に関連づけられた加算器及び乗算器を省くことによってハードウェアを節減することが可能となる。というのは、対応する乗算器の出力も０になる必要があるからである。
【００５６】
任意の段において１ビットの２進値のみを用いる実施形態では、単一の論理「ＡＮＤ」ゲートによって乗算器の各々を構成することが可能であること、及び、加算器の各々は、単一の論理「排他的ＯＲ」ゲートによって構成することが可能であることも認識される。
【００５７】
次にＭＡＣ生成関数の側面についての説明を参照すると、前述したいわゆる加重結合器（summation combiner）ストリーム暗号を用いて、良好な鍵生成アルゴリズムＦ及びＧを構成することが可能となる。図３は本発明のこの側面に係る例示回路３００を示すブロック図である。回路３００は第１のＬＦＳＲ３０１及び第２のＬＦＳＲ３０３を備える。第１及び第２のＬＦＳＲ３０１、３０３の各々は、他の回路とは独立に動作して、周知の原理に基づいて擬似乱数を生成することができる。第１のＬＦＳＲ３０１は、フィードバック多項式、ｐi（０≦ｉ≦ｎ−１）を有し、この多項式は第１のＬＦＳＲ３０１の長さに対して与えられる最大長のシーケンスを得ることができるように選択されることが望ましい。第２のＬＦＳＲ３０３は同様に、フィードバック多項式、Ｉi（０≦ｉ≦ｎ−１）を有し、この多項式は第２のＬＦＳＲ３０３の長さに対して与えられる最大長のシーケンスを得ることができるように選択されることが望ましい。第２のフィードバック多項式Ｉlは、第１のフィードバック多項式Ｐiと同じになるように、あるいは第１のフィードバック多項式Ｐiとは異なるように選択されてもよい。
【００５８】
回路３００は、合計回路３０５と、無限インパルス応答（ＩＩＲ）フィルタ３０７によって例示される置換論理回路とをさらに含む。ＩＩＲフィルタ３０７は、合計回路３０５の出力部と入力部との間にあるフィードバックパスに位置されているため、入力の１つを合計回路３０５へ供給することになる。合計回路３０５は、第１のＬＦＳＲ３０１の出力から第２の入力も受信し、次いで、第２のＬＦＳＲ３０３の出力から第３の入力を受信する。
【００５９】
この例示の実施形態において、ＬＦＳＲ３０１、３０３内の個々の段は１ビットのみを構成する。この例示の実施ではＩＩＲフィルタ３０７の出力もまた１ビットのみである。したがって合計回路３０５からの出力は０から３までの範囲の値になり、この値は２進の２つの数字によって表すことができる。本実施形態では、これら２進数の最上位ビットはＩＩＲフィルタ３０７への入力として用いられる。これらの２進数の最下位ビットは最終出力（すなわち、ストリーム暗号生成装置の暗号化されたデータ）を供給する。
【００６０】
次いで、代替の実施形態では、個々の第１及び第２のＬＦＳＲの段はマルチビット値を保持するように設計することも可能であることが認識される。残りの回路は適宜サイズの変更が行われて、この変更に適合される。しかし、説明の簡略化のために、及び、本発明の範囲に含まれる他の可能な実施形態に関する言外の意味や限定を含むことのないように、本説明の残り部分は１ビットの実施形態の場合を想定するものとする。
【００６１】
この例示の実施形態では、ＩＩＲフィルタ３０７は、線形長１１のシフトレジスタのデュアル実装構成を（ＧＦ（２）にわたって）備え、フィードバックとして、多項式ｆ（ｘ）＝１＋ｆ1ｘ＋ｆ2ｘ2＋．．．＋ｆ10ｘ10＋ｘ11を有するようになっている。例えば、ｆ（ｘ）＝１＋ｘ3＋ｘ5＋ｘ7＋ｘ11を選択することも可能である。このケースでは、ＩＩＲフィルタ３０７の出力は、７個の変数で表される４次の２相関免疫（2-correlation immune）ブール関数（Ｆ）の関数値となる。実際には、この出力は（７、２、４、５６）関数値となる。この関数への入力が図４ａに示されている。これは、非線形次数が２であること、及び、２つの入力変数と関数の出力値との間に相関が存在しないことを意味するものである。関数は線形構造から距離５６を有する。これらの同じパラメータを有するいくつかのブール関数（Ｆ）が存在し、これらのうちのいずれも使用可能である。一例として、図４ｂは、これらのブール関数のうちの１つのウォルシュ・スペクトルを示すテーブルである。
【００６２】
次に、乗算のパフォーマンスに関係する本発明の実施形態の側面に解説の焦点をしぼることにする。図５は、（ｎ回のステップで）シーケンシャルにｙ∈ＧＦ（２n）にｘ∈ＧＦ（２n）を乗算する能力を備えた周知のデュアル基底のビットシリアル乗算器を示すブロック図である。ここでｙは正常の（正規）基底ｙ＝ｙ0＋ｙ1α＋ｙ2α2＋．．．＋ｙn-1αn-1で表される（但し、α∈ＧＦ（２n）は多項式ｐ（ｔ）＝ｐ0＋ｐ1ｔ＋ｐ2ｔ2＋．．．＋ｐn-1ｔn-1＋ｐnｔn，ｐi∈ＧＦ（２）の０であり、かつ、ｙi∈ＧＦ（２）はｙ座標である）。次に、例えば、Ｒ．Ｊ．メリース（McEliece）による「コンピュータ科学者及び技術者のための有限体」（ｐ．９７〜１１８、クルーワー出版、１９８７年）に記載のように、β1，．．．，βn-1をいわゆる（トレース）デュアル基底とする。すなわち、
【００６３】
ｉ＝ｊであればＴＲ（αiβj）＝１、そうでなければＴＲ（αiβj）＝０。
【００６４】
ここでＴＲ（）はトレース関数を示す。次いで、以下のようにそのデュアル表現によってｘを表現することが可能となる：
【００６５】
ｘ＝［ｘ］0β0＋［ｘ］1β1＋［ｘ］2β2＋．．．＋［ｘ］n-1βｎ−ｉ（［ｘ］i∈ＧＦ（２））
【００６６】
ここで、［．］という表記法は本願ではデュアル座標を示すために用いられているという点に留意されたい。
【００６７】
図５の構成を用いて量Ｘと量Ｙの間で乗算を実行するために、Ｘのデュアル基底表現はＬＦＳＲ５０１のシフトレジスタの中へ格納される。多項式ｐi（０＜ｉ＜ｎ−１）の項がＬＦＳＲの乗算器のそれぞれの入力に印加されて、当業で公知の原理に基づいて必要な所望のフィードバックが達成される。
【００６８】
段を備えた多段フィードバック論理回路５０３の第２の構成が与えられ、個々の段は（乗算器５０５などの）乗算器と、（加算器５０７などの）加算器とを備える。個々の段において、乗算器は、ＬＦＳＲ５０１のシフトレジスタの対応する段と、（ビットなどの）量Ｙの対応する部分とによって供給される出力信号の積を生成する。第２の多段フィードバック論理回路５０３の段は、個々の段が、それ自身の乗算器出力の合計を含むフィードバック信号と、第２の多段フィードバック論理回路５０３の隣接する先行段によって生成されたフィードバック信号とを生成するように構成される。ＬＦＳＲ５０１のシフトレジスタがｎ回クロック入力されると、（デュアル基底表現での）積ＸＹは、第２の多段フィードバック論理回路５０３の最終段の出力時に順次供給される。
【００６９】
図６は、乗算の結果を受信するためのレジスタ６０１を装備した同じ乗算器を示すブロック図である。結果レジスタ６０１の段と、ＬＦＳＲ５０１のシフトレジスタの段との間の接続によって、ＬＦＳＲ５０１のシフトレジスタの中へ結果レジスタ６０１の内容をフィードバックすることが可能になる。図６並びに、例示のプロセスで実行されるステップを描くフローチャートである図７を参照しながら以下説明するように、この構成は、数式（１）において必要に応じて数値Ｋ’，Ｋ’2，．．．，Ｋ’lを計算するのに有益である。
【００７０】
最初のステップとして、Ｋ’のデュアル基底表現を有するＬＦＳＲ５０１のシフトレジスタ（以後Ｘレジスタと呼ぶ）をロードすることが望ましい。これは、複数の異なる方法のうちの任意の方法で実行することができる。例えば、他の回路において必要な所望の量の計算を行い、次いで、Ｘレジスタの中へクロック入力を行うことができる。これを達成するための接続は図を過度に複雑にすることを避けるために描かれていないが、これらの接続は当業者によって容易に確かめることが可能である。
【００７１】
上記とは別に、及び、本発明の様々な実施形態の他の側面に従って、Ｋ’のデュアル基底表現を決定するために描かれた回路が利用される。この決定は、（図示されていないメモリデバイスにのみ記憶されていて、かつ、必要なときに取り出される定数である）番号１のデュアル基底表現と共にＸレジスタを最初にロードすることにより達成される（ステップ７０１）。（この説明を通じてずっと、角括弧を用いて、角括弧の中に提示される量のデュアル基底表現を示すことにする）。Ｋ’の値が乗算器のＹ入力に印加され（ステップ７０３）、次いで、Ｘレジスタがｎ回クロック入力される（ステップ７０５）。このようにして、Ｋ’のデュアル基底表現が結果レジスタ６０１において最後になるまで積１×Ｙ＝Ｋ’はｎ回のステップで計算される。
【００７２】
別の側面では、結果レジスタ６０１の内容（＝Ｋ’）を該レジスタ６０１からＸレジスタの中へコピーする（ステップ７０７）ことによってＫ’2の値を計算し、次いで、乗算器（７０９）のＹ入力にＫ’の値を印加し続けることができる。次いで、回路はさらにｎ回クロック入力され（ステップ７１１）、これによって計算Ｋ’−Ｋ’＝Ｋ’2が達成されて、結果レジスタ６０１に現れる（デュアル基底表現で表される）計算結果が得られる。この一連の動作（すなわち、結果レジスタ６０１からＸレジスタの中へ最後の計算値を移動させ、Ｋ’を乗算器のＹ入力に印加し続け、次いで、回路にｎ回クロック入力を行う動作）を、デュアル表現で表されている場合であっても、必要に応じて反復して、Ｋ’のＫ’lまで増加する冪を得るようにすることができる。しかし、ＭＡＣコードの計算を必要とするアプリケーション（又は同様のアプリケーション）の場合、計算結果をデュアル基底表現で放置しておいてもよい。なぜなら、デュアル基底から正規基底へのマッピングは線形マッピングであるため、ＭＡＣコードのセキュリティパラメータに影響を与えることはないからである。
【００７３】
図８は、第２の結果レジスタ８０１と第３の多段フィードバック論理回路８０３とを追加することによって達成可能となる追加の利点を例示する回路構成を示すブロック図である。第３の多段フィードバック論理回路８０３は複数の段を備え、個々の段は（乗算器８０５などの）乗算器及び（加算器８０７などの）加算器を備える。個々の段において、第３の乗算器は、ＬＦＳＲ５０１のＸレジスタの対応する段と、（ビットなどの）量Ｍの対応する部分とによって供給される出力信号の積を生成する。第３の多段フィードバック論理回路８０３の段は、個々の段が、該段自身の乗算器出力の合計を含むフィードバック信号と、第３の多段フィードバック論理回路８０３の隣接する先行段によって生成されたフィードバック信号とを生成するように構成される。ＬＦＳＲ５０１のシフトレジスタがｎ回クロック入力されると、（デュアル基底表現で表される）積ＸＭは、第３の多段フィードバック論理回路８０３の最終段の出力時に順次供給される。第２の結果レジスタ８０１の入力段と、第３の多段フィードバック論理回路８０３の最終段との間での接続によって積ＸＭが生成されると、第２の結果レジスタ８０１の中へ積ＸＭを順次クロック入力することが可能となる。好適には、このクロック入力は、第２の多段フィードバック論理回路５０３の最終段の中から第１の結果レジスタ６０１の中へ積をクロック入力すると同時に実行できることが望ましい。
【００７４】
２個のデュアル乗算器を備えることによって、今度はｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍ1Ｋ’lを容易に計算することが可能となる。１つの乗算器（ＬＦＳＲ５０１と第２の多段フィードバック論理回路５０３との組み合わせ）は、デュアル表現Ｋ’，Ｋ’2，．．．，Ｋ’lを計算し、もう一方の乗算器（ＬＦＳＲ５０１と第３の多段フィードバック論理回路８０３との組み合わせ）は、同時実行中に、このもう一方の乗算器によって計算できるようなＫ’iから積ｍ1Ｋ’iを計算する。
【００７５】
次に示すように、比較的小型の論理回路によって、量ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lを第２の結果レジスタ８０１において容易に計算し、収集することが可能になる。さらに、２つの乗算器内の論理回路を用いて、Ｋ’だけでなくＫ”の生成も可能となる。
【００７６】
図９は、Ｋ’及びＫ”の生成が可能であると共に、次いで、これらの値を用いて、数式（１）に基づいてＭＡＣ値の計算が可能な回路９００の例示の実施形態を示すブロック図である。回路９００は以下に記載のハードウェアにおいて用いられる制御信号と定数のすべてを生成する制御・サポート論理回路９０１を含む。制御・サポート論理回路９０１は、配線タイプかプログラム可能タイプかの少なくともいずれかのタイプの論理回路として実装可能であり、この論理回路の設計は以下の説明から当業者には容易に理解されよう。
【００７７】
回路９００には、ＬＦＳＲ９０３、第１の多段フィードバック論理回路９０５、及びシフトレジスタ機能を有する第１の結果レジスタ９０７が含まれている。第１の多段フィードバック論理回路９０５と、ＬＦＳＲ９０３と、第１の結果レジスタ９０７との間で切り替え可能な接続によって、これらの論理素子が（例えばストリーム暗号モードで）図３に関連して前述したように、あるいは上記とは別に、（乗算器モードで）図６及び図７に関連して前述したように機能することが可能になる。特に、１組のスイッチ９０９によって、第１の多段フィードバック論理回路９０５は、ＬＦＳＲ９０３内のシフトレジスタか、第１の結果レジスタ９０７のいずれかのレジスタの種々の段から入力信号を取得することができる。スイッチ９０９の制御は、制御・サポート論理回路９０１によって生成される制御信号によって支配される。制御・サポート論理回路９０１は、第１の結果レジスタ９０７の内容が直接ＬＦＳＲ９０３内のシフトレジスタの中へクロック入力されるか、結果レジスタ９０７が独立したシフトレジスタとして動作するかの判定を行う信号も生成する回路である。図９において、第１の多段フィードバック論理回路９０５を特定するボックスにスイッチ９０９が描かれていることに留意されたい。しかし、スイッチ９０９が多段フィードバック論理回路９０５から独立したかつ分離された部品であることは容易に考えることができる。
【００７８】
回路９００は、合計回路９１１と、無限インパルス応答（ＩＩＲ）フィルタ９１３によって示される置換論理回路とをさらに含む回路である。ＩＩＲフィルタ９１３は、合計回路９１１の出力部と入力部との間にあるフィードバックパスに配置されているため、入力を合計回路９１１へ供給することになる。制御・サポート論理回路９０１によって生成された信号の指揮の下で、合計回路９１１は、ＬＦＳＲ９０３の出力から第２の入力を受信する能力を備えていると共に、シフトレジスタとして動作するように構成された結果レジスタ９０７の出力から第３の入力を受信する能力も備えている。
【００７９】
スイッチ９０９が、第１の結果レジスタ９０７から第１の多段フィードバック論理回路９０９へ信号を供給するように構成されているとき、（シフトレジスタとして動作している）結果レジスタ９０７を第２のＬＦＳＲとして動作させるようにすることができる。その場合、多項式Ｉn-1、Ｉn-2，．．．，Ｉ0は、制御・サポート論理回路９０１によって生成され、次いで、第１の多段フィードバック論理回路９０５内に配置されている乗算器の入力部へ供給される。
【００８０】
ここまで説明した回路は、数式（１）に基づいてＭＡＣを生成するために必要なＫ’項を生成するために好適に利用される。例えば、（ｎビットなどの）ＰＤの第１の部分は、ランダムなチャレンジ（ＲＮＤ）の第１の部分と、ＬＦＳＲ９０３のＸレジスタの中へロードされた計算結果とに対してビット単位で排他的論理和（ＸＯＲ）を実行することができる。ＰＤの第２部分はランダムなチャレンジ（ＲＮＤ）の第２部分と、第１の結果レジスタ９０７の中へロードされた当該計算結果とに対しＸＯＲを実行することができる。ＰＤの第１の部分はＰＤの第２部分と同じにならないようにしなければならない。同様に、ランダムなチャレンジ（ＲＮＤ）の第１の部分はランダムなチャレンジ（ＲＮＤ）の第２部分と同じにならないようにしなければならない。多項式ＰとＩから得られた適切な項を第１及び第２の乗算器内のＬＦＳＲに印加することによって、合計回路９１１及びＩＩＲフィルタ９１３と組み合わせて、これらのＬＦＳＲを図３に関連して上述したストリーム暗号生成装置として動作させ、合計回路９１１の出力の最下位ビット（ＬＳＢ）を生成することが可能となり、ビットストリームによって項Ｋ’が構成される。好適な実施形態において、ＩＩＲフィルタ９１３の入力部につながるスイッチ９１２が閉じられ、さらに、ＩＩＲフィルタ９１３は、（ＩＩＲフィルタ９１３のそれぞれのフィードバック回路を経由して）Ｘレジスタ及び第１の結果レジスタ９０７の内容と共に、（１００回などの）複数回循環を行うことが可能となる。Ｘレジスタと第１の結果レジスタ９０７との循環を行うことによって、これらのレジスタの中に含まれている値のさらに良好なランダム化が行われ、次いで、ＩＩＲフィルタ９１３へのクロック入力が、合計回路９１１の出力部において提示される状態変数のスクランブリングを助けることになる。
【００８１】
上記回路へのさらなるクロック入力は、値Ｋ’の生成を引き起こし、次いで、合計回路９１１のＬＳＢ出力時に値Ｋ’を利用できるようにする。生成された値Ｋ’の受信及び格納を行うために別のシフトレジスタ（Ｋ’レジスタ９１５）が提供される。スイッチ９２３と９２９を閉じることによって、合計回路９１１のＬＳＢ出力時にＫ’レジスタ９１５が利用できるようになるとすぐに、Ｋ’レジスタ９１５の中へ値Ｋ’をロードすることが可能になる。
【００８２】
別の動作モードで、多項式ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍ1Ｋ’lが生成される。この生成を達成するために、第１の多段フィードバック論理回路９０５と、第２の多段フィードバック論理回路９１７と、シフトレジスタ機能を備えた第２の結果レジスタ９１９と、第２の組のスイッチ９２１とが組み合わされたＬＦＳＲ９０３が用いられる。第１のＬＦＳＲ９０３内のシフトレジスタから第１の多段フィードバック論理回路９０５の乗算器の入力部へ出力を供給して、図６に描かれている配置構成に相当する第１の乗算器の配置構成を形成するようにスイッチ９０９はセットされる。前述したように、この配置構成は、ＬＦＳＲ９０３内のＸレジスタの内容と、第１の多段フィードバック論理回路９０５の乗算器の入力部へ供給される値との間の乗算の実行を可能にする構成である。本例では、上記値がＫ’レジスタ段から出力時に供給されるようにスイッチがセットされる。Ｋ’のデュアル基底表現を行う必要があることに起因して、番号１のデュアル基底表現をＬＦＳＲ９０３のＸレジスタの中へロードし、次いで、論理回路のサイクリングを行うことによって、このデュアル基底表現を好適に生成して、ＬＦＳＲ９０３のＸレジスタと、Ｋ’レジスタ９１５に格納されているＫ’の値との間で乗算を実行することが可能となる。上記結果は第１の結果レジスタ９０７に格納されたＫ’のデュアル基底表現になる。次のステップにおいて、この値はＬＦＳＲ９０３のＸレジスタにクロック入力することができる。
【００８３】
ここで、スイッチ９２３と９２５とをそれらの開放位置にセットして（あるいは、値「０」の転送を保証する任意の代替方法で）多項式ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍ1Ｋ’lを計算できるように上記配置構成は準備される。スイッチ９０９は、ＬＦＳＲ９０３内のＸレジスタから第１の多段フィードバック論理回路９０５内の乗算器へ出力を供給し続ける。第２の多段フィードバック論理回路９１７内の乗算器の１つの入力がＬＦＳＲ９０３内のＸレジスタの対応する段によって供給されるように、スイッチ９２１も閉じられる。ＬＦＳＲ９０３内の多項式の項Ｐが乗算用としてセットされる。第２の多段フィードバック論理回路９１７内の乗算器のその他の入力が同様に、項ｍi（０≦ｉ≦ｌ）（数式（１）を参照のこと）を表すビットとなるようにセットされる。但し、ｍ1、ｍ2，．．．，ｍlは、体ＧＦ（２n）におけるｌ組の要素として表現されるデータ値（ＰＤ）を表すことにより導き出される。第２の多段フィードバック論理回路９１７によって生成された結果は第２の結果レジスタ９１９にクロック入力される。
【００８４】
上記配置構成は、図８に描かれている配置構成に非常に似たものとしてここで構成され、図８に関して上述したように動作して、多項式ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍ1Ｋ’lを生成することができる。特に、ＬＦＳＲ９０３のシフトレジスタがｎ回クロック入力されると、（デュアル基底表現で表される）積Ｋ’×［Ｘレジスタの内容］は第１の多段フィードバック論理回路９０５の最終段の出力時に順次供給され、次いで、この積は第１の結果レジスタ９０７の入力段に順次クロック入力されることができる。Ｘレジスタの内容が上述のように初期化されて、Ｋ’のデュアル基底表現を格納するようになると、結果として第１の結果レジスタ９０７は乗算演算の最後に値Ｋ’2をこの結果レジスタの中に格納したことになる。これが生じているのと同時に、（デュアル基底表現で表される）積ｍi×［Ｘレジスタの内容］が、第２の多段フィードバック論理回路９１７の最終段の出力時に順次供給され、次いで、この積を第２の結果レジスタ９１９の入力段に順次クロック入力することが可能となる。ｍiが項ｍ1に等しくセットされると、その結果として第２の結果レジスタ９１９は、第１の反復後に値ｍ1Ｋ’をこの結果レジスタの中に格納したことになる。
【００８５】
第１の結果レジスタ９０９の内容をＬＦＳＲ９０３のＸレジスタの中へクロック入力することによって、さらにまた、（値ｍ1Ｋ’が加算器９２７へ順次供給されるように）スイッチ９２５を閉じることによってＬＦＳＲ９２３のシフトレジスタをさらにｎ回クロック入力することによって、値Ｋ’2を生成し、第１の結果レジスタ９０７の中へクロック入力することが可能となる。これと同時に、ｍiは次項ｍ2に等しくセットされ、それによって値ｍ1Ｋ’＋ｍ2Ｋ’2が生成され、次いで、この値は第２の結果レジスタ９１９の中へクロック入力される。
【００８６】
上記処理のさらなる反復は、最終的に、多項式ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lが計算され、第２の結果レジスタ９１９の中へ格納されてしまうまで、（第１の結果レジスタ９０７に格納されている）Ｋ’のより高い冪と数式（１）との計算を生成することになる。
【００８７】
次の処理段において、制御・サポート論理回路９０１は、Ｋ”の値が生成されている間第２の結果レジスタ９１９の内容が安定状態をそのまま維持することを保証する信号を生成する。Ｋ’値の生成に関して上述したのと同じステップに後続してＫ”値の生成を実行することが望ましい。すなわち、結果レジスタ９０７は独立したシフトレジスタとして動作され、第１の多段フィードバック論理回路９０５、合計回路９１１、及びＩＩＲフィルタ９１３はストリーム暗号生成装置としてＬＦＳＲ９０３と連携して動作するように構成される。ＰＤの部分は、ランダムなチャレンジ（ＲＮＤ）の部分と、ＬＦＳＲ９０３のＸレジスタの中へロードされた結果とに対してビット単位で排他的論理和（ＸＯＲ）を実行することができる。ＰＤの別の部分は、ランダムなチャレンジ（ＲＮＤ）の別の部分と、第１の結果レジスタ９０７の中へロードされた当該結果とに対してビット単位でＸＯＲを実行することができる。ＰＤの２つの部分は互いに同じにならないようにしなければならない。同様に、ランダムなチャレンジ（ＲＮＤ）の２つの部分は互いに同じにならないようにしなければならない。暗号生成に適した多項式ＰとＩとは、再びＬＦＳＲ９０３と第１の多段フィードバック論理回路９０５とへそれぞれ供給される。ＩＩＲフィルタ９１３の入力部につながるスイッチ９１２が閉じられ、次いで、ＩＩＲフィルタ９１３は、ＬＦＳＲ９０３のＸレジスタと第１の結果レジスタ９０７との内容と共に（１５０回などの）複数回クロック入力される。
【００８８】
次いで、スイッチ９２３と９２５は閉じられる。回路のさらなるクロック入力によって値Ｋ”は合計回路９１１のＬＳＢの中からシーケンシャルにシフトされることになる。スイッチ９２３と９２５とを閉じた状態で、値Ｋ”＋ｍ1Ｋ’＋ｍ2Ｋ’2＋．．．＋ｍlＫ’lが第２の多段フィードバック論理回路９１７の出力時に生成される。上記値は第２の結果レジスタ９１９の中へ格納することが可能であると共に、この結果レジスタ９１９から、制御・サポート論理回路９０１によって上記値を取り出し、生成されたＭＡＣ値として該値を利用することが可能である。
【００８９】
上記配置構成において、（互いに素である周期を得るために）ｎ次未満の多項式に従ってＩ個の多項式の値がセットされることが望ましい。
【００９０】
上記実施形態は単に例示のためのものであり、本発明の種々の側面に従う多くの代替の実施形態を導き出すことが可能である。例えば、項Ｋ’の生成時に、初期化が、ランダムなチャレンジ（ＲＮＤ）の１以上の部分に対してＰＤの１以上の部分のＸＯＲをビット単位で行う必要があることについてはすでに述べた。代替の実施形態では、関数Ｇ（）に対する一意の定数を用いて、結果として得られる（単複の）値に対してさらにＸＯＲを行うことが可能である。
【００９１】
同様に、項Ｋ”の生成時に、初期化が、ランダムなチャレンジ（ＲＮＤ）の１以上の部分に対してＰＤの１以上の部分のＸＯＲをビット単位で行う必要があることについてもすでに述べた。代替の実施形態では、関数Ｆ（）に対する一意の定数を用いて、結果として得られる（単複の）値に対してさらにＸＯＲを行うことが可能である。
【００９２】
他の代替例では、Ｋ’の計算プロセスを修正することによって、以下のようにＭＡＣの強度の改善を行うことが可能となる：合計回路９１１の出力時にＫ’値を直接読み出す代わりに、前述したように回路を実行して値Ｋを生成することができる。次いで、Ｘレジスタと残りの回路の状態が変化しない状態で放置されている間、上記値は第１の結果レジスタ９０７の中へロードされる。次いで、回路は再び複数回クロック入力され、それから、値Ｋ’は合計回路９１１から読み出される。所望の場合、この計算プロセスを任意の回数反復してもよい。
【００９３】
上記実施形態はデータに対する完全性保護を提供するというコンテキストに関連して提示されたものである。しかし、種々の実施形態は上記特定アプリケーションのみに限定されるわけではない。全く同一の回路を用いて、左右対称の鍵を共有する２つのピア間においてデータ通信の完全性保護を実行することも可能である。このような場合、図１に示すチャレンジ＆レスポンス方式は用いられない。代わりに、２つのピアは通信セッションを開始する前に例えば２つの乱数を交換することができる。次いで、例えば、単に乱数及び共有化鍵（Ｋ）からだけでなく、当該メッセージが、保護を受ける対象メッセージである一連のメッセージの中のどのメッセージであるかを特定するインデックスからも初期鍵を生成することが可能となる。こうすることによって、ランダムなデータの新たな交換を行うことなく、個々の新たなメッセージ用として独立の鍵Ｋ”及びＫ’を用いることが可能となる。
【００９４】
本発明の実施形態の種々の側面を拡張して、データの機密性保護と完全性保護の双方を実行するケースをカバーするように図ることも可能である。このケースでは、（図９に示すような）暗号化エンジンを用いて、完全性が保護される前又は完全性が保護された後にデータの暗号化を実行することも可能である。この場合、暗号化エンジンの初期化鍵は、完全性保護のために用いる初期化鍵すなわちＫ’及びＫ”とは異なる鍵にしなければならない。
【００９５】
他の代替例では、図９に記載され、示されている基本構成を拡張して、さらに多くのシフトレジスタとフィードバック多項式とをカバーすることが可能であるが、上記以外の場合でも、同じ基本構造を保持できることは当業者であれば認識するであろう。これにより、さらに大きなハードウェアにコストをかければより高いセキュリティを得ることが可能となる。
【００９６】
種々の実施形態によって、相対的に小型の完全性保護用ハードウェアの実装を実現することが可能となる。本発明に従う実施形態は、安全な記憶装置用アプリケーションにおいて、かつ、安全な通信メッセージ状況においても利用することができる。
【００９７】
個々の実施形態を参照しながら本発明について説明した。しかしながら、以上に説明した実施形態以外の特定の形で本発明の実施が可能であることは、当業者には容易に理解されよう。好ましい実施形態は単に説明のために役立てるべきものであり、いかなる点においても限定的なものとして考えられるべきではない。
【００９８】
例えば、図９の詳細な説明は、個々の例示要素の動作と、他の例示要素のそのインタラクションの動作とに焦点を絞った説明である。しかし、要素の例示の組み合わせは、代替の実施形態の中に含まれている複数の側面も同様に示すものであることが認識される。例えば、第１の多段フィードバック論理回路９０５と、第１の結果レジスタ９０７と、スイッチ９０９とは、シフトレジスタとフィードバック回路とを一体に備えた多目的論理回路の実施形態を例示するものであり、その場合、多目的論理回路のフィードバック回路を経由してフィードバックされる信号は、以下のいずれかによって選択的に供給されることになる：
１）ＬＦＳＲ回路９０３のシフトレジスタの対応する１以上の段によって供給される１以上の出力信号、又は、
２）多目的論理回路のシフトレジスタの対応する１以上の段によって供給される１以上の出力信号。
【００９９】
多目的論理回路のシフトレジスタのフィードバック回路は、１以上の制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、多目的論理回路のシフトレジスタの入力段がフィードバック信号を利用できるように構成される。
【０１００】
ＬＦＳＲ９０３のシフトレジスタからか、あるいは、（第１の結果レジスタ９０７によって図９に例示されている）多目的論理回路自体のシフトレジスタからかのいずれかのシフトレジスタから得られた入力を選択的に取得することは、多目的論理回路のフィードバック回路のフィードバック回路の能力であり、上記シフトレジスタが、ＬＦＳＲ９０３と組み合わされて、ストリーム暗号演算か、乗算関数のいずれかを実行するために多目的論理回路を用いることを可能にするものである。
【０１０１】
また、ＬＦＳＲ９０３のシフトレジスタに接続されている（第２の多段フィードバック論理回路９１７などの）補助フィードバック回路を設けることによって、（ＬＦＳＲ９０３などの同じ線形フィードバックシフトレジスタ部に個々に含まれている）同時演算が可能な乗算器による同時乗算演算の実行が可能になることが理解される。次いで、上記乗算演算の実行は、それぞれのｍiＫ’i項並びにＫ’i+1項（１≦ｉ≦ｌ）の同時生成を順に可能にする。
【０１０２】
さらに一般的に見ると、実施形態はＬＦＳＲ回路とＬＦＳＲ回路とに接続された追加回路を含み、その場合、制御信号の第１の状態は、ＬＦＳＲ回路と追加回路とを鍵生成装置として一体的に機能させる。さらに、制御信号の第２の状態は、ＬＦＳＲ回路と追加回路とを乗算器として一体的に機能させる。
【０１０３】
代替の実施形態の別例として、体ＧＦ（２n）を用いる本発明の実施形態について説明した。しかし、当業者であれば、代替の実施形態は、代わりに任意のタイプの体ＧＦ（（２m））nか、あるいはさらに風変わりなタイプの体ＧＦ（（ｐm））n（「ｐ」は素数）を用いることも可能であることを認めるであろう。
【０１０４】
さらに別の例では、有限状態シフトレジスタ機能が必要とされるときはいつでも上記記載の種々の実施形態はすべてＬＦＳＲ構成に依拠するものであった。しかし、ＬＦＳＲの代わりに非線形有限状態シフトレジスタによってストリーム暗号生成を達成することも可能である。当業者であれば、ＬＦＳＲの代わりに非線形有限状態シフトレジスタを利用する種々の実施形態を上記記載の原理及び他の教示からどのように導き出すことができるかは容易に理解されるであろう。本願明細書では、「有限状態シフトレジスタ」（ＦＳＲ）という用語は、一般的な意味で用いられ、当該配置構成が線形フィードバックシフトレジスタを構成するか、非線形フィードバックシフトレジスタを構成するかにかかわりなく、任意のタイプのシフトレジスタ／フィードバックの配置構成を意味する用語である。
【０１０５】
このように、記載の実施形態は単なる例示であり、いかなる点でも限定するものと考えるべきではない。
【図１】
2010513941.tif 000003
【図２】
2010513941.tif 000004
【図３】
2010513941.tif 000005
【図４ａ】
2010513941.tif 000006
【図４ｂ】
2010513941.tif 000007
【図５】
2010513941.tif 000008
【図６】
2010513941.tif 000009
【図７】
2010513941.tif 000010
【図８】
2010513941.tif 000011
【図９】
2010513941.tif 000012
【手続補正書】
【提出日】平成21年7月22日(2009.7.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
認証コードを生成する装置であって、
複数の制御信号を生成するための制御・サポート論理回路と、
シフトレジスタと、フィードバック回路とを備えた線形フィードバックシフトレジスタ（ＬＦＳＲ）回路と、
前記ＬＦＳＲ回路に接続された追加回路と、
を備え、
第１の状態の前記制御信号は、前記ＬＦＳＲ回路と前記追加回路とを鍵生成装置として一体的に機能させ、
第２の状態の前記制御信号は、前記ＬＦＳＲ回路と前記追加回路とを乗算器として一体的に機能させる
ことを特徴とする装置。
【請求項２】
前記装置は電子回路の一部であり、
前記装置は、
前記電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記電子回路に記憶されている秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第１の値を生成する論理回路と、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第２の値を生成する論理回路と、
を備え、
前記制御・サポート論理回路は信号を生成する論理回路を備え、該信号は、
前記ＬＦＳＲ回路に前記第１の値から第１の擬似ランダム値を生成させ、
前記第２の値から第２の擬似ランダム値を生成する第２の線形フィードバックシフトレジスタとして前記追加回路が利用されるようにし、
前記ＬＦＳＲ回路と前記追加回路とを前記鍵生成装置として一体的に機能させ、
前記第１の擬似ランダム値と前記第２の擬似ランダム値とから第１の鍵の値（Ｋ’）を前記鍵生成装置に生成させる
ことを特徴とする請求項１に記載の装置。
【請求項３】
前記追加回路は、
シフトレジスタとフィードバック回路とを備えた多目的論理回路と、
前記ＬＦＳＲ回路と、前記多目的論理回路と、置換論理回路とによって供給される加算信号用のための合計回路と、
前記合計回路によって供給される１以上の信号を受信するための入力ポートと、前記合計回路へ信号を供給するための出力ポートとを備えた前記置換論理回路と、
を備え、
前記多目的論理回路の前記フィードバック回路を経由してフィードバックされた信号が、前記ＬＦＳＲ回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号のいずれかによって、又は、前記多目的論理回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号によって、選択的に供給され、
前記多目的論理回路の前記シフトレジスタのフィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、前記多目的論理回路の前記シフトレジスタの入力段が前記フィードバック信号を利用できるようになっており、
前記鍵生成装置はストリーム暗号生成装置であり、
前記制御信号の前記第１の状態は、前記ＬＦＳＲ回路と、前記多目的論理回路と、前記合計回路と、前記置換論理回路とを前記ストリーム暗号生成装置として一体的に機能させ、
前記制御信号の前記第２の状態は、前記ＬＦＳＲ回路と、前記多目的論理回路の前記フィードバック回路とを前記乗算器として一体的に機能させるようになっている
ことを特徴とする請求項１に記載の装置。
【請求項４】
前記制御信号の前記第２の状態は、さらに、乗算の積を前記多目的論理回路の前記シフトレジスタの中へ格納させることを特徴とする請求項３に記載の装置。
【請求項５】
前記合計回路により供給された１以上の供給信号を受信し、格納するＫ’レジスタで示されるシフトレジスタと、
値１のデュアル基底表現を前記ＬＦＳＲ回路の前記シフトレジスタの中へロードするための回路と、
前記Ｋ’レジスタの出力信号を乗算中オペランドとして用いられるように多目的論理回路へ供給させる回路と、
を備えることを特徴とする請求項３に記載の装置。
【請求項６】
前記制御信号の第３の状態に応じて、前記多目的論理回路のシフトレジスタから得られた値を前記ＬＦＳＲ回路の前記シフトレジスタの中へコピーするための回路を備えることを特徴とする請求項３に記載の装置。
【請求項７】
補助シフトレジスタと、
補助フィードバック回路と、
を備え、
前記補助フィードバック回路を介してフィードバックされる信号が、前記ＬＦＳＲ回路の前記シフトレジスタの１以上の段によって供給される出力信号であり、
前記補助フィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、前記補助シフトレジスタの入力段が前記フィードバック信号を利用することができ、
前記制御信号の第３の状態は、次の動作、すなわち、
前記第１の積を生成する乗算器として一体的に機能すると共に前記第１の積が生成されると、該第１の積を前記多目的論理回路の前記シフトレジスタの中へ格納するようになっている、前記多目的論理回路の前記ＬＦＳＲ回路並びに前記フィードバック回路と、
第２の積を生成し、該第２の積が生成されると、該積を前記補助シフトレジスタの中へ格納する乗算器として一体的に機能する前記ＬＦＳＲ回路及び前記補助フィードバック回路と、を同時に実行させる
ことを特徴とする請求項３に記載の装置。
【請求項８】
前記合計回路によって供給される１以上の信号を、前記補助シフトレジスタによって供給される対応する番号の信号と順次結合する加算器を備えることを特徴とする請求項７に記載の装置。
【請求項９】
出力信号を補助フィードバック回路へ供給するために前記加算器が接続され、
前記加算器の前記出力信号を補助シフトレジスタへ供給するために前記補助フィードバック回路が接続される
ことを特徴とする請求項７に記載の装置。
【請求項１０】
シフトレジスタと、フィードバック回路とを備えたＬＦＳＲに接続されている線形フィードバックシフトレジスタ（ＬＦＳＲ）回路及び追加回路を備えた装置において認証コードを生成する方法であって、
第１の動作モードにおいて、前記ＬＦＳＲ回路と前記追加回路とを鍵生成装置として一体的に機能させ、
第２の動作モードにおいて、前記ＬＦＳＲ回路と前記追加回路とを乗算器として一体的に機能させる
ことを特徴とする方法。
【請求項１１】
電子回路において実行される方法であって、
前記電子回路の外部にあるソースからランダムなチャレンジワード（ＲＮＤ）を受信するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも一部と、前記電子回路に格納されている秘密鍵の値（Ｋ）の少なくとも一部との間で論理演算を実行することによって第１の値を生成するステップと、
前記ランダムなチャレンジワード（ＲＮＤ）の少なくとも別の一部と、前記秘密鍵の値（Ｋ）の少なくとも別の一部との間で論理演算を実行することによって第２の値を生成するステップと、
前記ＬＦＳＲ回路に前記第１の値から第１の擬似ランダム値を生成させるステップと、
第２の擬似ランダム値を前記第２の値から生成する第２の線形フィードバックシフトレジスタとして前記追加回路が利用されるようにするステップと、
前記ＬＦＳＲ回路と前記追加回路とを鍵生成装置として一体的に機能させることによって前記第１の擬似ランダム値と前記第２の擬似ランダム値とから第１の鍵の値（Ｋ’）を生成するステップと、
を有することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記追加回路は、
シフトレジスタとフィードバック回路とを備えた多目的論理回路であって、
前記ＬＦＳＲ回路と、前記多目的論理回路と、置換論理回路とによって供給される加算信号用の合計回路と、
前記合計回路によって供給される１以上の信号を受信するための入力ポートと、前記合計回路へ信号を供給するための出力ポートとを備えた前記置換論理回路と、を備え、
前記多目的論理回路の前記フィードバック回路を経由してフィードバックされた信号が、前記ＬＦＳＲ回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号のいずれかによって、又は、前記多目的論理回路の前記シフトレジスタの対応する１以上の段によって供給される１以上の出力信号によって選択的に供給され、
前記多目的論理回路の前記シフトレジスタのフィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成するように構成されると共に、前記多目的論理回路の前記シフトレジスタの入力段が前記フィードバック信号を利用できるようになっており、
前記第１の動作モードは、前記ＬＦＳＲ回路と、前記多目的論理回路と、前記合計回路と、前記置換論理回路とを前記鍵生成装置として一体的に機能させるステップを有し、
前記第２の動作モードは、前記ＬＦＳＲ回路と、前記多目的論理回路の前記フィードバック回路とを前記乗算器として一体的に機能するようにさせるステップを有する
ことを特徴とする請求項１０に記載の方法。
【請求項１３】
前記ＬＦＳＲ回路及び前記多目的論理回路の前記フィードバック回路が、第１の積を生成する乗算器として一体的に機能し、前記第１の積が生成されると、該第１の積を前記多目的論理回路の前記シフトレジスタの中へ格納する動作と、
前記ＬＦＳＲ回路及び補助フィードバック回路が、第２の積を生成し、該第２の積が生成されると、該積を補助シフトレジスタの中へ格納する乗算器として一体的に機能する動作と、
を同時に実行させるステップを有し、
前記補助フィードバック回路を介してフィードバックされる信号は、前記ＬＦＳＲ回路の前記シフトレジスタの１以上の段によって供給される出力信号であり、
前記補助フィードバック回路は、１以上の前記制御信号により指定された機能に基づいてフィードバック信号を生成すると共に、前記補助シフトレジスタの入力段が前記フィードバック信号を利用できるようにする
ことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記合計回路によって供給される１以上の信号を、前記補助シフトレジスタによって供給される対応する番号の信号と順次結合することによって合計を生成するステップを有することを特徴とする請求項１３に記載の方法。
【請求項１５】
前記合計を前記補助フィードバック回路へ供給するステップと、
前記加算器の前記出力信号を前記補助シフトレジスタへ供給するために前記補助フィードバック回路を動作させるステップと、
を有することを特徴とする請求項１４に記載の方法。
【国際調査報告】
2010513941.tif 000013
2010513941.tif 000014
2010513941.tif 000015
2010513941.tif 000016
2010513941.tif 000017