(57)【要約】現在のＭＡＣアルゴリズムは、メッセージをリアルタイムで処理するために大きなシステム性能の要求を課す。本発明の好適例によれば、ＭＡＣを発生するハードウェアで実現された発生器が提供され、この発生器は、メッセージをリアルタイムで処理するためのハードウェア性能要求における大幅な改善をもたらす。このエンジンは、安全なＭＡＣを発生するように構成された線形フィードバック・シフトレジスタに基づく。
2008532410.tif 000002
【特許請求の範囲】
【請求項１】
メッセージ認証コードを発生する発生器において、
第１データセットの線形性除去を実行して第２データセットを生成するように構成された第１回路を具え、
前記第１データセットは元のコードを含み、
前記線形性除去は、線形フィードバック・シフトレジスタ構成及び擬似乱数ストリームに基づく
ことを特徴とするメッセージ認証コード発生器。
【請求項２】
さらに、前記第２データセットのエラー検出コードの発生を実行して、第３データセットを生成するように構成された第２回路を具え、
前記第１回路が第１線形フィードバック・シフトレジスタを具え、
前記第１回路は前記第２回路とは異なる
ことを特徴とする請求項１に記載の発生器。
【請求項３】
前記第１回路が、
少なくとも１つの下位重み段と；
少なくとも１つの上位重み段とを具え、
前記第１データセットの線形性除去は、前記第１データセットの複数のコピーを生成して任意に遅延させ、前記第１データセットと排他的論理和をとって混合することを含み；
前記少なくとも１つの下位重み段は、前記第１データセットの各ビットの影響が、前記第１回路のその後のすべての状態を通して伝搬されることを保証するように構成され；
前記少なくとも１つの上位重み段は、擬似乱数列に従ってジャム処理され、
前記少なくとも１つの上位重み段は、前記擬似乱数列によって駆動されて、前記少なくとも１つの下位重み段の状態を論理的に任意に遅延させたサブシーケンスを発生する
ことを特徴とする請求項１に記載の発生器。
【請求項４】
さらに、第１擬似乱数の発生を実行するように構成された第１擬似乱数発生エンジンを含む第４回路を具え、
前記第４回路は、発生した前記第１擬似乱数を前記第１回路に供給するように構成されていることを特徴とする請求項１に記載の発生器。
【請求項５】
前記擬似乱数発生エンジンを、少なくとも１つの第２線形フィードバック・シフトレジスタの組合せ、カウンタモードで動作する第１ブロック暗号器、及び出力フィードバックモードで動作する第２ブロック暗号器から成るグループから選択したことを特徴とする請求項４に記載の発生器。
【請求項６】
前記少なくとも１つの第２線形フィードバック・シフトレジスタの組合せの初期状態をランダムに選定し、２つ以上のメッセージ用のメッセージ認証コードを発生するために再使用せず、
前記初期状態を用いて、前記擬似乱数の発生を実行することを特徴とする請求項５に記載の発生器。
【請求項７】
前記第２回路が巡回冗長検査回路を具え、
前記エラー検出コードの発生は、前記第２回路によって実行される巡回冗長検査の構成に基づく
ことを特徴とする請求項２に記載の発生器。
【請求項８】
前記第２回路を、巡回冗長検査回路、暗号ＭＤＣ機能回路、及び一致発生器から成るグループから選択したことを特徴とする請求項２に記載の発生器。
【請求項９】
前記第２回路を、データの効率的なインデックス付けを実行するために使用するハッシュ関数、及びネットワークのデータセットの効率的なルーティングを実行するために使用するハッシュ関数から成るグループから選択したことを特徴とする請求項２に記載の発生器。
【請求項１０】
前記第１回路の最終状態を抽出して自己収縮発生器回路の初期状態として使用し、所望のサイズの出力が得られるまで前記自己収縮発生器回路を動作させることによって、前記第２回路を実現することを特徴とする請求項２に記載の発生器。
【請求項１１】
弾性非線形関数を用いて前記第１回路の状態をサンプリングし、その結果を巡回冗長検査の構成に供給することによって、前記第２回路を実現することを特徴とする請求項２に記載の発生器。
【請求項１２】
弾性非線形関数を用いて前記第１回路の状態をサンプリングし、その結果を、データの効率的なインデックス付けを実行するために使用するハッシュ関数、及びネットワークのデータセットの効率的なルーティングを実行するために使用するハッシュ関数から成るグループから選択した関数に供給することによって、前記第２回路を実現することを特徴とする請求項２に記載の発生器。
【請求項１３】
前記線形性除去を実行する前に、前記第１データセットに接頭文字または接尾文字の少なくとも一方を付加することを特徴とする請求項１に記載の発生器。
【請求項１４】
さらに、第２擬似乱数の発生を実行するように構成された第２擬似乱数発生エンジンを含む第５回路を具え、
前記第５回路は、発生した前記第２擬似乱数を前記第１回路に供給するように構成されていることを特徴とする請求項４に記載の発生器。
【請求項１５】
さらに、第３擬似乱数の発生を実行するように構成された第３擬似乱数発生エンジンを具え、
前記第１回路が、第１混合エンジン及び第２混合エンジンを具えていることを特徴とする請求項４に記載の発生器。
【請求項１６】
さらに、１ビット・マルチプレクサを具え、
前記第１回路がＦＩＦＯレジスタを具え、
前記１ビット・マルチプレクサは、第１多項式及び第２多項式を用いることによって前記ＦＩＦＯレジスタの入力を決定するように構成され、
前記第１擬似乱数発生エンジンは、前記第１多項式及び前記第２多項式の選択を制御するように構成されていることを特徴とする請求項４に記載の発生器。
【請求項１７】
前記第１回路の最終状態を抽出して自己収縮発生器回路の初期状態として使用し、所望のサイズの出力が得られるまで前記自己収縮発生器回路を動作させることによって、前記第２回路を実現することを特徴とする請求項１６に記載の発生器。
【請求項１８】
弾性非線形関数を用いて前記第１回路の状態をサンプリングし、その結果を巡回冗長検査の構成に供給することによって、前記第２回路を実現することを特徴とする請求項１６に記載の発生器。
【請求項１９】
弾性非線形関数を用いて前記第１回路の状態をサンプリングし、その結果を、データの効率的なインデックス付けを実行するために使用するハッシュ関数、及びネットワークのデータセットの効率的なルーティングを実行するために使用するハッシュ関数から成るグループから選択した関数に供給することによって、前記第２回路を実現することを特徴とする請求項１６に記載の発生器。
【請求項２０】
前記第１擬似乱数発生エンジンが、収縮ストリームを決定するように構成されていることを特徴とする請求項４に記載の発生器。
【請求項２１】
メッセージ認証コードを発生する方法において、
第１回路によって第１データセットの線形性除去を実行して第２データセットを生成するステップを具え、
前記第１データセットは元のコードを含み、
前記線形性除去は、線形フィードバック・シフトレジスタ構成及び擬似乱数ストリームに基づく
ことを特徴とするメッセージ認証コードの発生方法。
【請求項２２】
さらに、第２回路によって前記第２データセットのエラー検出コードの発生を実行して、第３データセットを生成するステップを具え、
前記第１回路が第１線形フィードバック・シフトレジスタを具え、
前記第１回路は前記第２回路とは異なる
ことを特徴とする請求項２１に記載の方法。
【請求項２３】
さらに、擬似乱数発生エンジンを具えた第４回路によって擬似乱数の発生を実行するステップと；
発生した前記擬似乱数を前記第１回路に供給するステップと
を具えていることを特徴とする請求項２１に記載の方法。
【請求項２４】
前記第１回路の状態に対して非線形関数の演算を実行し、その結果を巡回冗長検査の構成に供給することによって、前記第２回路を実現することを特徴とする請求項２１に記載の方法。
【請求項２５】
前記第１回路の状態に対して非線形関数の演算を実行し、その結果を、データの効率的なインデックス付けを実行するために使用するハッシュ関数、及びネットワークのデータセットの効率的なルーティングを実行するために使用するハッシュ関数から成るグループから選択した関数に供給することによって、前記第２回路を実現する
ことを特徴とする請求項２１に記載の方法。
【請求項２６】
前記第１回路の最終状態を抽出して自己収縮発生器回路の初期状態として使用し、所望のサイズの出力が得られるまで前記自己収縮発生器回路を動作させることによって、前記第２回路を実現することを特徴とする請求項２１に記載の方法。
【請求項２７】
メッセージ認証コードを発生するプログラム要素であって、プロセッサによって実行した際に、
第１回路によって第１データセットの線形性除去を実行して第２データセットを生成するステップを実行するように構成され、
前記第１データセットは元のコードを含み、
前記線形性除去は、線形フィードバック・シフトレジスタ構成及び擬似乱数ストリームに基づく
ことを特徴とするプログラム要素。
【請求項２８】
メッセージ認証コードを発生するコンピュータプログラムを格納したコンピュータ読取可能媒体において、
前記コンピュータプログラムは、プロセッサによって実行した際に、
第１回路によって第１データセットの線形性除去を実行して第２データセットを生成するステップを実行するように構成され、
前記第１データセットは元のコードを含み、
前記線形性除去は、線形フィードバック・シフトレジスタ構成及び擬似乱数ストリームに基づく
ことを特徴とするコンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ伝送の分野に関するものである。特に、本発明は、メッセージ認証コード（符号）を発生する発生器、メッセージ認証コードを発生する方法、プログラム要素、及びコンピュータ読取可能媒体に関するものである。
【背景技術】
【０００２】
ほとんどすべてのメッセージ認証コード（ＭＡＣ：Message Authentication Code）アルゴリズムは、次の原始アルゴリズムのグループ：即ち、ＳＨＡ−１、ＲＩＰＥＭＤ−１６０、ＭＤ５のようなキー（鍵）なしハッシュ関数、及びＤＥＳ、ＡＥＳ、ＩＤＥＡ、等のようなブロック暗号の一方の上に構成されている。
【０００３】
すべての場合において、これらの方式は、メッセージの各ビットを、ハッシュ関数またはブロック暗号のいずれかの少なくとも１回の実行によって処理することを必要とする実現を生じさせる。このことは、深いパイプラインの設定による専用ハードウェア上で効率的に実現することができるが、この方法は次の欠点をもたらす：
【０００４】
第１に、非常に多数の論理ゲートが、シリコン面積の相当量の消費をもたらし、このことはチップ製造コストを押し上げる主要因の１つである。
【０００５】
第２に、メッセージの最終ビットをＭＡＣ処理エンジンに供給した後に、最終結果を得るまでに、幾分顕著な遅延がある。
【０００６】
第３に、メッセージの処理全体中に同時に変化する何千個ものトランジスタによる高い電力消費である。
【０００７】
第１の欠点は、深いパイプラインの方法によって悪化するが、後の２つの欠点は、すべてのハードウェア実現を通して不変であり、アルゴリズム自体に固有のものである。
【０００８】
特に、後の２つの欠点は非常に複雑であり、一部の設定ではまさに、次のものの効率的な実現を妨げる：
極めて効率的な電力管理を必要とするシステム、例えば常時オンのスタンドアロンの（独立型）医療装置。
最大通信速度が最重要なシステム、例えばインターネットの基幹（バックボーン）を動作させる超高速ルータ。
動作中に、外部に記憶された状態の強力な完全性チェックを必要とするシステム、例えば作業データを外部ＲＡＭに記憶する安全なマイクロプロセッサ。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ＭＡＣを最適化するハードウェアを提供することが要望される。
【課題を解決するための手段】
【００１０】
本発明の好適例によれば、上記要望は、メッセージ認証コードを発生する発生器によってかなえることができ、この発生器は、元のコード（即ちプレーンテキスト（平文））を含む第１データセットの線形性除去（デリニアライゼーション、デリニアリゼーション）を実行して第２データセットを生成するように構成された第１回路を具え、この線形性除去は、線形フィードバック・シフトレジスタ構成及び擬似乱数入力に基づく。
【００１１】
本発明のこの好適例によれば、線形フィードバック・シフトレジスタ（ＬＦＳＲ：Linear Feedback Shift Register）をその主なセキュリティエンジンとして使用する新たなＭＡＣ発生器が提供されることが有利である。ＬＦＳＲが発生するストリームを活用するために使用される革新的なメカニズムにより、上記方式を攻撃するために開発された現在のノウハウは、新たな設計に直接適用可能ではない。
【００１２】
本発明の他の好適例によれば、前記発生器はさらに、前記第２データセットのエラー検出コードの発生を実行して第３データセット（即ち、メッセージ認証コード）を生成するように構成された第２回路を具え、前記第１回路は第１線形フィードバック・シフトレジスタを具え、前記第１回路は前記第２回路とは異なる。
【００１３】
換言すれば、上記線形性除去は、ＬＦＳＲの挙動に連続的に影響を与えて、再使用不可能な擬似乱数列に従ってプレーンテキストを混ぜ合わせることによって得られる。本発明の好適例によれば、エラー検出コードの計算に使用するのはＬＦＳＲではなく、エラー検出コードはこれとは異なる第２回路によって計算することが有利である。
【００１４】
本発明の他の好適例によれば、前記第１回路が、少なくとも１つの下位重み（付け）段及び上位重み段を具え、前記第１データセットの線形性除去は、前記第１データセットの複数のコピーを生成して任意に遅延させ、前記第１データセットとの排他的論理和（ＸＯＲ）をとることを含む。さらに、前記少なくとも１つの下位重み段は、前記第１データセットの各ビットの影響が、前記第１回路のその後のすべての状態を通して伝搬されることを保証するように構成され、そして前記少なくとも１つの上位重み段は、擬似乱数列に従ってジャム（妨害、攪乱）処理され、この擬似乱数列は、前記少なくとも１つの下位重み段の状態を論理的に任意に遅延させたサブシーケンス（副列）を発生する。
【００１５】
このようにして、プレーンテキストのすべてのビットをエラー検出コードの計算に影響させつつ、これらのビットの大部分は、敵対者が推測不可能なランダムに遅延された位置に置かれる。
【００１６】
本発明の他の好適例によれば、前記発生器はさらに、擬似乱数発生を実行するように構成された擬似乱数発生エンジンを含む第４回路を具え、この第４回路は、前記擬似乱数を前記第１回路に供給するように構成されている。
【００１７】
従って、前記第１回路が外部的に発生した擬似乱数を用いてプレーンテキストまたは元のコードの線形性除去を行うことができることが有利である。この擬似乱数発生は、上記混ぜ合わせまたは非線形除去の回路とは異なる回路によって実行することができることが有利である。
【００１８】
本発明の他の好適例によれば、前記擬似乱数発生エンジンは、少なくとも１つの第２線形フィードバック・シフトレジスタの組合せ、及び／またはカウンタモードで動作するブロック暗号器から成るグループから選択する。さらに、前記少なくとも１つの第２線形フィードバック・シフトレジスタの組合せの初期状態はランダム（無作為）に選択することができ、そして２つ以上のメッセージ認証コードを発生するために使用することはできず、この初期状態を用いて前記乱数発生を実行することができる。
【００１９】
本発明のこの好適例によれば、「キーイングＬＦＳＲ」を連続的に動作させること、即ち、メッセージ(i)を処理してメッセージ(i+1)の処理の初期状態にする際に達成されるＬＦＳＲの最終状態を用いることを可能にすることができる。
【００２０】
さらに、本発明の他の好適例によれば、前記第２回路が巡回冗長検査（サイクリック・リダンダンシー・チェック）回路を具え、前記エラー検出コードの発生は、前記第２回路によって実行される巡回冗長検査の構成に基づく。
【００２１】
前記巡回冗長検査の構成は、エラー検出コードの計算において非常に効率的であり、その上、ハードウェアで非常に効率的に実現することができる。これは実際に、１Gbpsのイーサネット（登録商標）において用いられるもののような高速ネットワーク装置におけるエラー検出コード用の回路の選定である。さらに、前記巡回冗長検査の構成は、異なるサイズ（即ち、エラー検出強度）のコードを発生するように容易に拡張可能（スケーラブル）である。
【００２２】
本発明の他の好適例によれば、前記線形性除去を実行する前に、前記第１データセットに接尾文字または接頭文字の少なくとも一方を付加する。
【００２３】
従って、最終段階において支障が発生していないことを仮定して、プレーンテキストの（１つ以上の）最終ビットを改変することに焦点を合わせた攻撃を回避することができることが有利である。
【００２４】
本発明の他の好適例によれば、メッセージ認証コードを発生する方法が開示され、この方法は、第１回路によって第１データセットの線形性除去を実行して第２データセットを生成するステップを具え、この線形性除去は線形フィードバック・シフトレジスタの構成に基づく。
【００２５】
このことは、より少ないハードウェア・リソース（資源）及びより少ない電力を用いて、高速でハードウェアの最適化されたＭＡＣ発生を提供することができることが有利である。
【００２６】
本発明は、メッセージ認証コードを発生するコンピュータ読取可能媒体、及びコンピュータ読取可能媒体に格納されメッセージ認証コードを発生するプログラム要素にも関するものである。このプログラム要素は、プロセッサによって実行した際に、第１回路によって第１データセットの線形性除去を実行して第２データセットを生成するステップを具えている。このプログラム要素は、例えば常時スタンドアロン（独立型）の医療装置、またはインターネットの基幹において動作する超高速ルータの一部分とすることができる。本発明の好適例によれば、このプログラム要素は、データプロセッサの作業メモリにロードすることができることが好ましい。従って前記データプロセッサは、本発明の方法の好適例を実行するように構成することができる。このコンピュータ・プログラムは、例えばＣ＋＋のようなあらゆる適切なプログラミング言語で書くことができ、そしてＣＤ−ＲＯＭのようなコンピュータ読取可能媒体上に記憶することができる。また、前記コンピュータ・プログラムは、ワールドワイド・ウェブのようなネットワークから入手することができ、こうしたネットワークから、プロセッサまたはあらゆる適切なコンピュータにダウンロードすることができる。
【００２７】
本発明のさらなる好適例は従属請求項に記載する。
【００２８】
本発明の態様は、メッセージ認証コードを発生する発生器が線形フィードバック・シフトレジスタに基づくものであり、この発生器は、元のコードの線形性除去の手順を実行することによって安全なＭＡＣを発生することができる、というものとすることができる。
【００２９】
本発明の上記及び他の態様は、以下に述べる実施例の説明を参照すれば明らかになる。
【００３０】
以下、本発明の好適な実施例について図面を参照しながら説明する。
【発明を実施するための最良の形態】
【００３１】
図面の図示は概略的なものである。異なる図面では、類似または同一の要素には同じ参照番号を付ける。
【００３２】
図１に、本発明の好適な実施例によるＳＮ−ＭＡＣ発生器を概略表現で示す。図１に示す実施例によれば、このＭＡＣ発生器は、主要動作グループ、即ち擬似乱数発生器グループ１を具え、この発生器は「キーＬＦＳＲ」ブロックによって実現される。さらに、この発生器は、中央プレーンテキスト（平文）混合器グループ２を具え、この混合器グループは５段ＬＦＳＲ（負荷制御フリップフロップＬＦＳＲ）２３、２４、２５、２６、２７、多項式生成ＸＯＲ（排他的論理和）２２、４１、３３、３４、３５、４３、及びプレーンテキスト混合ＸＯＲ２１で実現される。（第３の主要グループとして、上記発生器はチェックサム（合計検査）発生ブロック３を具え、このブロックは標準的なＣＲＣ−３２手順を実行するＣＲＣ−３２ブロックで実現される。）
【００３３】
なお、本発明の一態様によれば、発生器は最終のＣＲＣ段３を含まず、回路１及び２のみを含む。
【００３４】
擬似乱数発生器グループ１は、負荷入力１４、初期入力１５、クロック１３、新たなビット入力１６、及びビット出力１２を具え、ビット出力１２はＬＦＳＲ段２６及び２７に供給される。
【００３５】
クロック信号１３は擬似乱数発生器グループ１に供給され、そしてライン４４、４５、４６、４７、４８経由で５つのＬＦＳＲ段２３〜２７の各々に供給される。
【００３６】
新たなビット１６は擬似乱数発生器グループ１に供給され、そして素子１８経由でチェックサム発生ブロック３に供給される。
【００３７】
負荷入力１４はさらに、それぞれライン４９〜５３経由でＬＦＳＲ段２３〜２７に供給される。
【００３８】
チェックサム発生ブロック３はさらに、安全なＣＲＣ出力３１及びレディ（準備完了）ピン３２を具えている。
【００３９】
ＮＯＴ（否定論理）ゲート１８は、入力プレーンテキスト１１の処理と出力ＭＡＣ３１の発生との間の正しい動作モードを確立する手助けをする。
【００４０】
ＸＯＲゲート２１は、多項式の結果４１を計算した後に、プレーンテキスト１１をＬＦＳＲ状態に導入する。
【００４１】
【非特許文献１】A. S. Tanenbaum: “Computer Networks”, 4th Edition
【００４２】
ＣＲＣ−３２アルゴリズムは、３２ビットまでのエラーバースト及び奇数個のビットに影響するすべてのエラーバーストを含むプレーンテキスト上のランダムな変化を検出するには十分適しているが（参考文献として本明細書に含めるA. S. Tanenbaum著：“Computer Networks”, 4th Editionに開示されているように、IEEE 802に規定されているＣＲＣ−３２多項式（Ｘ32＋Ｘ26＋Ｘ23＋Ｘ22＋Ｘ16＋Ｘ12＋Ｘ11＋Ｘ10＋Ｘ8＋Ｘ7＋Ｘ5＋Ｘ4＋Ｘ2＋Ｘ1＋１）を使用するものと仮定する）、ＣＲＣ−３２アルゴリズムは、プレーンテキストの検出されない手の込んだ改変を防止することは全くできない。しかし、この周知のアルゴリズムは、攻撃者が秘密値（即ちキー）を知らずに内部ストリームの内容を推測することを実行不可能にすることのできる方法で、プレーンテキスト１１をこの内部ストリーム中に再混合することによって、安全なＭＡＣを発生することに利用することができる。このストリームは図１では「秘密（シークレット）ストリーム」２８とラベル付けする。
【００４３】
「秘密ストリーム」２８を出力する混合ブロックは、プレーンテキスト１１の複数のコピーを任意に遅延させて、プレーンテキスト１１自体とのＸＯＲをとって混合させることによって動作する、というのはこのことは混合ブロック２の役目だからである。混合エンジン２は次の２つの主要な副構成要素を具えている：
混合ＬＦＳＲの下位重み段は、プレーンテキスト１１の各ビットの影響が、混合エンジン２のその後のすべての状態を通して伝搬することを保証する。なお、これらの段は孤立して、最大長のＬＦＳＲ（図１については原始多項式Ｘ3＋Ｘ＋１）を形成する
擬似乱数列に従って「ジャム処理される」上位重み段は、ＬＦＳＲの下位重み段の状態の論理的にランダムに遅延されたサブシーケンス（副列）を発生し、そして拡張によって、プレーンテキスト１１自体の論理的にランダムに遅延されたサブシーケンスを発生する。
【００４４】
このようにして、プレーンテキストのすべてのビットをＣＲＣ−３２の計算に影響させつつ、これらのビットの大部分は、敵対者が推測することが不可能であるように遅延されたランダムな位置でも、この計算に影響を与える。
【００４５】
なお、図１に示す接続多項式は唯一可能な選択ではなく、実際に、初期段階用の他の原始多項式の形を有するあらゆる原始的な接続多項式を用いることができる。さらに、図１には５段のみの混合エンジン２を示しているが、本発明によれば、より多数またはより少数の段を実現することができる。
【００４６】
最後に、「キーイングＬＦＳＲ」ブロック１は、原始多項式を有する標準的なＬＦＳＲブロックであり、その出力ストリーム１２によって混合ブロック２の上位重み段にクロック供給する役割を持つことができる。
【００４７】
なお、図１はクロック制御の代わりにローディング制御を示している。しかし、これらはアルゴリズム的観点からすれば等価であるが、前者はハードウェアで容易に実現することができる。「キーイングＬＦＳＲ」の初期状態はＭＡＣキーであり、仕組みにおいて秘密に保つべき単一部分である。もちろん、より長い長さも許容され、ＣＲＣ段が３３ビット以上を生成する場合に必要である。もちろん、より小さい長さも可能であり、本発明の範囲内である。
【００４８】
安全にするためには、クロック発生ＬＦＳＲの初期状態はランダムに選定すべきであり、そして２つ以上のメッセージ用のＭＡＣを発生すべく再使用すべきでないことは明らかである。しかし、「キーイングＬＦＳＲ」を連続的に動作させること、即ち、メッセージ(i)を処理してメッセージ(i+1)の処理の初期状態にする際に達成されるＬＦＳＲの最終状態を使用することは可能である。
【００４９】
エンジンを再始動する際に、混合ブロック及びＣＲＣ−３２ブロックは共にクリア（消去）すべきである（このことは、耐プリイメージ（事前イメージ、事前画像）を達成するために必要となり得る）。
【００５０】
プレーンテキスト・メッセージの第１ビットは、混合エンジンによって影響される機会が少ししかないことがあり、従って、検出されないメッセージ改変の容易な標的になり得る。このことが発生するのを防ぐために、割増量のビットをメッセージに前付けすることが必要になり得る。この付加は秘密にすべきでなく、そして固定のアルゴリズム・パラメータにすることができる。０と１の混合のバランス（釣り合い）のとれた、混合エンジンのサイズより大きいあらゆるシーケンスで十分である。５段の混合エンジンのサイズ用には、バイトＡＡhex（１６進数”ＡＡ”）で表わされるシーケンスを用いることができる。
【００５１】
最後に、プレーンテキスト・メッセージの最終ビットは、予測不可能な方法で混合エンジンの状態に影響を与える機会が少ししかなく、従って、検出されないメッセージ改変の容易な標的となり得る。このことが発生するのを防ぐために、割増量のビットをメッセージに付加することが有利であり得る。この付加は秘密にすべきでなく、そして固定のアルゴリズム・パラメータとすることができる。ＣＲＣの出力段以上の大きさのあらゆるシーケンスが使える。従って、１６ビットのＣＲＣについては、１６個の０のシーケンスを用いることができる。
【００５２】
図２に、本発明の他の好適な実施例による他のＳＮ−ＭＡＣ発生器の概略表現を示し、この発生器は、第２擬似乱数発生器４及びさらなる乱数出力ストリーム４２を具えている。
【００５３】
図２は、本発明による発生器のさらに一層安全な実施例を示し、この発生器は比較的小量の追加的ハードウェアしか必要としない。図２はこの代案の構成の表現である。
【００５４】
このバージョンのアルゴリズムでは、混合ブロックのランダム化した各段のクロックは、異なる擬似乱数発生器ＬＦＳＲによって制御される。
【００５５】
ＬＦＳＲの長さどうしは互いに素にすることができ、ＣＲＣ−３２ベースの出力用には長さ６１及び６７にすることができる。この構成では、ＭＡＣキーは１２８ビット長である。
【００５６】
上述した安全な動作のために、同じベースラインの要求が当てはまる。
【００５７】
図３に、本発明の好適な実施例による、ロード可能なフリップフロップを有するキー付きプレーンテキスト混合エンジンの概略表現を示す。
【００５８】
図３を孤立した混合エンジンの基本ブロックとすれば、この基本ブロックを図４の例に示すより複雑な構成に組み立てることによって、この基本ブロックの代案の、そして恐らくはより安全な変形を構成することができる。
【００５９】
図４に、本発明の他の好適な実施例による混合エンジンの概略表現を示す。
【００６０】
なお、以上に提示した実施例は大いにカスタマイズ（顧客対応）可能である。実際に、以下に述べる構成とする本発明の一般化を実行することができる。
【００６１】
図３よりわかるように、ランダム・ストリーム１２及びプレーンテキスト・ストリーム１１を与えたエンジンは、プレーンテキスト・ストリーム１１の状態を維持できる非線形関数である第３のストリームを発生する。
【００６２】
本発明の好適な実施例によれば、上記発生器は次のものを具えることができる：
【００６３】
【非特許文献２】P. Camion and A. Canteaut: “Correlation-immune and resilient functions over a finite alphabet and their applications in cryptography”, Designs, Codes and Cryptography, (16)
【００６４】
任意数の段、及び／または、
ＬＦＳＲの特性多項式中で、１に設定された一致する指数を有するＭＳＢ段を駆動する任意数の入力ランダム・ストリーム、及び／または、
図３に提示するものの代わりに、第１フリップ段の入力から抽出し、ＬＦＳＲのＸＯＲをプレーンテキストの入力のＸＯＲに集約した出力、及び／または、
すべてのＬＦＳＲ段の出力の（非）線形結合関数として、特に、弾性関数（参考文献として本明細書に含める、P. Camion and A. Canteaut著：“Correlation-immune and resilient functions over a finite alphabet and their applications in cryptography”, Designs, Codes and Cryptography, (16), 1999年の121〜149ページ参照）を用いて計算した出力、及び／または、
あらゆる種類の特性多項式、及び／または、
追加的なクリア及び／またはセット信号、及び／または、
プレーンテキスト１１をいくつかの混合エンジン１０００、１１００にわたって分配した混合エンジンの構成、これは、図４に示す二次入力ランダム・ストリーム１００、２００、３００によって制御される。これらの二次入力ランダム・ストリーム１００、２００、３００はすべて、独立したキーイングＬＦＳＲから来たものである。
【００６５】
なお、上述した非線形結合関数を用いる際には、擬似乱数キーイング・ストリームを再使用することを可能にすることができる。この場合には、線形性除去は混合エンジン（またはその組合せ）によって直接実行せず、上記非線形関数によって一意的に実行する。このことは、複数の非同期メッセージが関係者間で交換される際に、ＭＡＣ関数のキー管理を大幅に簡略化するという利点を有する。
【００６６】
図４では、完結した非線形プレーンテキスト混合回路の最終出力５００が、各混合エンジン１２、４２の出力のＸＯＲ４００である。なお、ＸＯＲ４００の出力混合関数は、他のあらゆるブール関数及び／または上述した弾性関数に置き換えることができる。
【００６７】
段「キーイングＬＦＳＲ」は、擬似乱数発生エンジンに、特に、カウンタモード及び／または出力フィードバックモードで動作するブロック暗号器に、あるいはＬＦＳＲのあらゆる組合せに置き換えることができる。
【００６８】
さらに、出力段「ＣＲＣ−３２」は、エラー検出コードを発生することのできるあらゆるブロックに、特に任意のエラー検出コードに、特に任意の長さ及びチェックサムのＣＲＣに、ＳＨＡ−１またはＲＩＰＥＭＤ−１６０のような暗号ＭＤＣ機能に、あるいは一致発生器に、あるいは以下に記載する回路に置き換えることができる。
【００６９】
混合エンジンの最終状態を取得して、この状態を自己収縮ＬＦＳＲの初期状態として使用する。
【００７０】
この自己収縮発生器ＬＦＳＲは、所望のサイズのＭＡＣ出力が得られるまで動作させる。
【００７１】
以下では、ＬＦＳＲ及びＣＬＣについてのさらなる情報を提供する：
【００７２】
以下では、線形フィードバック・シフトレジスタ、線形有限状態マシン、巡回冗長コード、自己収縮発生器、及び非線形フィルタ生成器についてのさらなる情報を提供する。
【００７３】
ここで、線形フィードバック・シフトレジスタ（ＬＦＳＲ）の主な特徴を要約する。明細書全体を通して、２進数フィールドＦを考える。長さｎのＬＦＳＲはｎ個のメモリセルから成り、一緒になって状態（ｓ0, ｓ1,...,ｓn-1）を形成する。これらのメモリセルはＤフリップフロップとも称する。ＬＦＳＲは出力シーケンス｛ｓi｝i≧0を規定し、このシーケンスは次式の再帰的関係によって規定される：
【数１】
2008532410.tif 000003
または等価的に、
【数２】
2008532410.tif 000004
ここに、定義によりｃn＝１である。ｓ(i)は時刻ｉにおけるＬＦＳＲの状態を規定し、即ちｓ(i)＝(ｓi, ｓi+1,...,ｓi+n-1)である。
【００７４】
すると、状態について次式の同様の関係が成り立つ：
【数３】
2008532410.tif 000005
係数ｃiはフィードバック係数と称され、ｃi＝０ならば対応するスイッチが開であり、ｃi＝１ならばこのスイッチは閉である、というのは、さもなければ、出力シーケンスはｃ0＝１なるシーケンスの単なる遅延版だからである。
【００７５】
通常のように、次式によって定義されるいわゆる特性多項式ｆ(ｘ)をＬＦＳＲに関連付ける：
【数４】
2008532410.tif 000006
ここに、定義によりｃn＝１であり、定義によりｃ0＝１である。ｆ(ｘ)の相反多項式は次式によって定義される：
【数５】
2008532410.tif 000007
【００７６】
シーケンス｛ｓi｝i≧0に、パワー列
【数６】
2008532410.tif 000008
を関連付ける。
Ｓ(ｘ)は、ｓ0, ｓ1,...,ｓn-1、及びｆ(ｘ)によって一意的に定まることが知られ、この依存性を明示的に次式のように記述し：
【数７】
2008532410.tif 000009
ここに、
【数８】
2008532410.tif 000010
【００７７】
多項式ｇ(ｘ)∈Ｆ[ｘ]は、多項式Ｆ[ｘ]の環内でより小さい正の次数の多項式に因数分解できない場合に、Ｆ上で既約であると言う。なお、非線形の再帰は、すべての２nの状態を通して反復することができる、というのは０の状態が禁止されているからである。他方では、非０の状態から始めて、すべての２n−１の非０状態を通して再帰を繰り返す際には、こうしたＬＦＳＲ（シーケンス）は最大長ＬＦＳＲ（シーケンス）と称され、対応する特性多項式は原始的であると言われる。こうした最大長シーケンスの周期ＴはＴ＝２n−１である。なお、すべての原始多項式は既約である。
【００７８】
【非特許文献３】J. Massy: “Shiftregister synthesis and BCH decoding”, IEEE Transactions on Information, Theory 15(24)
【００７９】
シーケンスの線形複雑度をＬで表し、これは当該シーケンスを発生する最短のＬＦＳＲの長さである。この線形複雑度は、参考文献として本明細書に含めるJ. Massy著：“Shiftregister synthesis and BCH decoding”, IEEE Transactions on Information, Theory 15(24), 1969年の122〜127ページに開示されているバーリカンプ−マシー・アルゴリズム（Berlekamp-Massey algorism）で特定することができ、このアルゴリズムは、出力シンボルのうち少なくとも２Ｌ個で与えられる特性多項式を効率的に計算する。従って、純粋なＬＦＳＲは良好なキーストリーム発生器ではない。例として、長さｎのＬＦＳＲをとり上げることができ、これは長さ２n−１の最大長のシーケンスを発生するが、バーリカンプ−マシー・アルゴリズムは、既知のプレーンテキスト攻撃において、フィードバック多項式及び初期状態、従って完結したシーケンスを完全に定めるために２ｎ個の連続ビットしか必要としない。
【００８０】
ｎビットの線形有限状態マシン（ＬＦＳＭ：Linear Finite State Machine）は、ｎ×ｎ行列Ｍで与えられる特定の線形演算子の実現または実施である。ＬＦＳＭの内部状態はｎビットのベクトルｖ∈Ｆnによって記述される。時間と共に進む展開（漸進的変化）は、次式のｎビットベクトルのシーケンス：
【数９】
2008532410.tif 000011
によって記述され、
ｖ(i+1)＝Ｍｖ(i)          (6)
を満足する。
【００８１】
ここで、ｖ(0)は初期状態である。２進フィールドＦ内に成分（元、要素）を有する行列Ｍの特性多項式は、次式：
char(Ｍ)＝det(ｘＩ−Ｍ)∈Ｆ[ｘ]          (7)
となるように規定され、ここでＩは通常のようにｎ×ｎの単位行列を表す。
Ｍの特性多項式がＦ上で原始的であれば、各シーケンス
2008532410.tif 000012
（ｊ＝0, 1,...,n-1）は周期２n−１を有することは周知である。(3)式によって与えられる多項式ｆ(ｘ)の随伴行列を次のように定義する：
【数１０】
2008532410.tif 000013
【００８２】
ＬＦＳＭの最も一般的なサブクラスは、ＬＦＳＲ及びセルラ・オートマトン（ＣＡ）である。ＣＡは、三重対角の定義行列Ｍを有するＬＦＳＭである。(3)式によって与えられる特性多項式ｆ(ｘ)を有するＬＦＳＲは、(8)式によって与えられるｆ(ｘ)の随伴行列に設定された定義行列を有するＬＦＳＭである。次のことは周知である。
【００８３】
定理１：ｆ(ｘ)を正方行列Ｍの特性多項式とする。ｆ(ｘ)の随伴行列をＬで表す。ｆ(ｘ)が既約であれば、次式：
ＴＭＴ-1＝Ｌ
を満足する可逆行列Ｔが存在する。
【００８４】
この定理に出てくる行列Ｔは一意的ではない。定理１を用いて、ＬＦＳＭをＬＦＳＲに約すことができる。ＬＦＳＭの内部状態が(6)式によって与えられることを思い出せば、ＬＦＳＭの初期状態がｖ(0)であれば、状態ｖ(i)は次式：
ｖ(i)＝Ｍiｖ(0)
によって与えられる。
【００８５】
同様に、ｆ(ｘ)（行列Ｌ）によって規定されるＬＦＳＲの初期状態がｓ(0)であったとすれば、状態ｓ(i)は次式：
ｓ(i)＝Ｌiｓ(0)
によって与えられる。
【００８６】
ここで、上記初期状態がｓ(0)＝Ｔｖ(0)の関係を満足すれば、（定理１によって、）ＬＦＳＭの現在状態ｖ(i)は、関連するＬＦＳＲの内部状態ｓ(i)を用いて、次の単純な線形方程式：
ｖ(i)＝Ｔ-1ｓ(i)
によって計算することができる。
【００８７】
従って、ＬＦＳＭはＬＦＳＲよりもずっと複雑に見えても、これら２つは単純な線形変換によって区別される。
【００８８】
ｇ(ｘ)を次数ｓの既約多項式とする。以下では、各２進（バイナリ）ストリングＳを、Ｓのビットに対応する係数を有するＦ上の多項式Ｓ(ｘ)に、明示的または暗黙的に関連付ける。Ｂを長さｍのメッセージとし、従って、Ｂ(ｘ)はこれに対応する次数ｍの多項式である。そして、（ｇ(ｘ)に基づく）ＣＲＣ値は、次式の関係：
Ｃ(ｘ)＝ｘsＢ(ｘ) mod ｇ(ｘ)          (9)
即ち、ｘsＢ(ｘ)＋Ｃ(ｘ)はｇ(ｘ)で整除される（割り切れる）
を満足する次数ｓ−１の多項式Ｃ(ｘ)として定義することができる。次の補助定理を導出することは容易である。
補助定理１：与えられた多項式ｇ(ｘ)及びＣ(ｘ)についての上記の表記では、(9)式を満足する２m-s個の多項式Ｂ(ｘ)が存在する。
【００８９】
【非特許文献４】D. Coppersmith, H. Krawczyk, Y. Mansour: “The shrinking generator”, CRYPTO’93, LNCS 773
【非特許文献５】W. Meier, O. Staffelbach: “The self-shrinking generator”, EUROCRYPT’94, LNCS 905
【非特許文献６】S. Blackburn: “The linear complexity of the self-shrinking generator”, IEEE Transactions on Information, Theory, 45(6)
【００９０】
参考文献として本明細書に含めるD. Coppersmith, H. Krawczyk, Y. Mansour著：“The shrinking generator”, CRYPTO’93, LNCS 773, 1993年の22〜39ページには、概念的に単純なキーストリーム発生器、いわゆる収縮発生器が提案されている。この発生器は２つのＬＦＳＲのみを組み合わせ、一方が他方の出力を制御し、従って出力キーストリームは、最大長シーケンスを不規則に間引きしたサブシーケンス（副列）である。一年後に、さらに洗練された構成である自己収縮発生器が、W. Meier, O. Staffelbach著：“The self-shrinking generator”, EUROCRYPT’94, LNCS 905, 1994年の205〜214ページによって提言された。実際には、上記収縮発生器からの２つのＬＦＳＲを組み合わせて１つのＬＦＳＲにし、このＬＦＳＲはビットの対に分割されたシーケンスを出力する。通常は最初のビットである選択ビットは、他のビット、即ちアクティブ（有効）ビットを出力キーストリームに取り入れるか廃棄するかを定める。Meier及びStaffelbachが指摘するように、上記自己収縮発生器は上記収縮発生器と機能的に等価である。なお、自己収縮発生器の選択論理より、平均的に、ＬＦＳＲによって発生される４ビットのうち３ビットが廃棄されるのに対し、収縮発生器については、平均的に２ビットのうち１ビットが廃棄される。自己収縮発生器の周期Ｔは、２[n/2]≦Ｔ≦２n-1を満足するが、実験結果は、この周期は常に可能な最大値をとることを示している。また、上記線形複雑度はＴ／２≦Ｌ≦２n-1−(ｎ−２)を満足することも示されている（S. Blackburn著：“The linear complexity of the self-shrinking generator”, IEEE Transactions on Information, Theory, 45(6), 1999年の2073〜2077ページ参照）。従って、Ｔ＝２n-1ならば、Ｌ＝Ｏ(２n-1)である。
【００９１】
【非特許文献７】E. Zenner, M. Krause, S. Lucks: “Improved cryptanalysis of the self-shrinking generator”, ACISP’01, LNCS 2119
【非特許文献８】H. Krawczyk: “LFSR-based Hashing and Authentication”, CRYPTO’94, LNCS 839
【００９２】
自己収縮発生器の暗号解読は、既知のフィードバック（帰還）多項式を仮定することが多い。長いＯ(２0.5n)観測キーストリームを用いる攻撃の演算の複雑度は、Ｏ(２0.5n)からＯ(２0.75n)まで変化し得る。また、演算の複雑度Ｏ(２0.69n)によるが、非常に短い長さの観測キーストリームを用いる攻撃は、E. Zenner, M. Krause, S. Lucks著：“Improved cryptanalysis of the self-shrinking generator”, ACISP’01, LNCS 2119, 2001年の21〜35ページに提案されている。後者の攻撃は、H. Krawczyk著：“LFSR-based Hashing and Authentication”, CRYPTO’94, LNCS 839, 1994年の129〜139ページにおいて改良され、複雑度をＯ(２0.64n)に低減し、ここでも非常に短い長さの観測キーストリーム・シーケンスを用いている。弱い（希薄な）フィードバック多項式の特定クラスについては、さらに効率的な攻撃が存在し得る。
【００９３】
非線形フィルタ生成器は、（長さｎを有する）単一のＬＦＳＲ、及びいくつかのシフトレジスタ段からｒ個の入力（ｒ≦ｎ）を取り出して出力を計算する非線形関数ｆ(ｘ)から成る。
【００９４】
代数的な次数ｋのブール関数については、キーストリームの線形複雑度は少なくとも
2008532410.tif 000014
であり、その周期は２n−１に等しいままであることが非常にありがちである。いくつかの種類の攻撃、例えば（高速）相関、反転、代数的攻撃が存在する。これらの攻撃に耐えるために、ブール関数は高度に非線形であり、高い次数を有し、そして相関の攻撃を受けにくく、かつ代数的攻撃を受けにくいべきである。
【００９５】
（ビルディング・ブロック）
ここで、本発明の好適な実施例による線形有限状態マシン、即ち、連続的に供給される（連続供給型）線形フィードバック・シフトレジスタ、ジャミング（ジャム処理）線形フィードバック・シフトレジスタ、収縮線形有限状態マシン、及び自己収縮線形フィードバック・シフトレジスタに基づくいくつかの暗号法プリミティブ（原始的要素）を説明する。
長さｎのＬＦＳＲを考え、次式：
【数１１】
2008532410.tif 000015
ここに、
【数１２】
2008532410.tif 000016
のシーケンスは次数ｎ−１の多項式である。Ｐ(j)(ｘ)に対応するｎビットのベクトルをＰ(j)＝(ｐnj, ｐnj+1,...,ｐnj+n-1)で表す。ここで、特性多項式ｆ(ｘ)（行列Ｌ）によって規定されるＬＦＳＲの内部状態は、ｓ(i)＝Ｌｓ(i-1)、ここにｓ(0)＝Ｐ(0)によって計算されることを思い起こす。さらに、Ｐ(j)(ｘ)を、同じＬＦＳＲで新たなシーケンスＳ(j)(ｘ)を発生するための初期状態として用いる。換言すれば、（「線形フィードバック・シフトレジスタ」において上述したように）ＬＦＳＲに１回供給してシーケンスＳ(ｘ)を発生する代わりに、ＬＦＳＲに周期的に供給する。このことは次の２つの方法で行うことができる：
１．ｎ番目の時間フレーム毎に、現在の状態をｓ(nj)←ｓ(nj)＋Ｐ(j)（これはｊ番目の供給）のように変更することによってＬＦＳＲに供給する。このようにして、ＬＦＳＲはこうした供給の各回において、（Ｓ(j)(ｘ)で表される）新たな追加的なシーケンスを発生する。
従って、結果的なシーケンス
【数１３】
2008532410.tif 000017
は、シフト付きのシーケンスの総和である。
２．時間フレーム毎に、現在状態と１つの新たな値とのＸＯＲをとることによってＬＦＳＲに供給する。いくつかのｊについてｉ＝ｎ(ｊ−１)とし、ｋ＝0,...,n-1について、次の手順：
ｓ(i+k)←ｓ(i+k)＋(ｐnj+n-1-k, 0,..., 0)、及びｓ(i+k+1)＝Ｌｓ(i+k)を反復する。その結果、ＬＦＳＲは新たな追加的なシーケンスを発生し、これを
2008532410.tif 000018
で表す。しかし、今度は
【数１４】
2008532410.tif 000019
であり、ここに
2008532410.tif 000020
はｎ回の供給及びシフトから来たものであり、即ち、
【数１５】
2008532410.tif 000021
であり、そしてＳ(j)(ｘ)は前の場合と同じシーケンスである（(11)式参照）。従って、結果的なシーケンスは今度は、
【数１６】
2008532410.tif 000022
となる。
【００９６】
(11)式と(12)式の違いは、(12)式では新たなシーケンスの各々に多項式を加算していることにある。
【００９７】
両方の場合に、パワー列Ｓ(j)(ｘ)及び
2008532410.tif 000023
は、「線形フィードバック・シフトレジスタ」について以上で規定したのと同じ方法で、その初期状態Ｐ(j)(ｘ)によって一意的に決まる。ここで、公式な定義を与え、そしていくつかの基本的な性質を導出する。
【００９８】
定義１：ＬＦＳＲ及び入力シーケンスＰ(ｘ)が与えられている。ＬＦＳＲが、その内部状態を周期的に更新する（入力シーケンスとのＸＯＲをとる）ことによって出力シーケンスＳ(ｘ)を発生する際に、このことを「連続供給型ＬＦＳＲ」と称する。
【００９９】
補助定理２：長さｎの連続供給型ＬＦＳＲを考える。出力シーケンスＳ(ｘ)及びＬＦＳＲ（即ちｆ(ｘ)またはＬ）は既知であるものとする。第１の場合（(11)式）には、入力シーケンスＰ(ｘ)は効率的に再構成されるの対し、第２の場合（(12)式）には、Ｐ(ｘ)のｎ個の連続ビットも知る必要がある。
【０１００】
シーケンスＳ(ｘ)は既知であるが、ｆ(ｘ)は未知であるものとする。バーリカンプ−マシー・アルゴリズムを適用して入力シーケンスＰ(ｘ)を再構成するためには、攻撃者は、第１の場合（(11)式）にはＰ(ｘ)のｎ個の連続ビットを必要とするのに対し、第２の場合（(12)式）には、Ｐ(ｘ)の２ｎ個の連続ビットを必要とする。
【０１０１】
以下の周知の定義から始める：
定義２：シーケンス{σi}i≧０が与えられているものとする。Ｄ−フリップフロップ・セルを１ビットレジスタと称し、（時刻ｉにおける）シーケンスの値σi＝０であれば、前のセル状態を繰り返して入力を無視し、σi＝１であれば、セル状態を入力に置き換える。両方の場合に、出力は前のセル状態である。
【０１０２】
換言すれば、１ビットレジスタは、シーケンスの対応する値が０である際以外は通常のＤ−フリップフロップ（単なる遅延素子）として働き、上記値が０である場合を「ジャムがある」と称する。シーケンス{σi}i≧0を収縮シーケンスと称する。
【０１０３】
定義３：セル（Ｄ−フリップフロップ）の１つ以上が１ビットレジスタに置き換えられれば、ＬＦＳＲジャミングと称する。
【０１０４】
長さｎのＬＦＳＲを考える。通常のように、ＬＦＳＲはシーケンス{ｓi}i≧0を発生するものとする。ここで、固定のｌ（エル）番目（ｌ≦ｎ）のＤ−フリップフロップ、即ちＬＦＳＲセルを１ビットレジスタに置き換えるものとする。１ビットレジスタを持つためには、フリップフロップ・セルがジャム処理される時点を制御する収縮シーケンスを必要とする。時刻ｉにおけるＬＦＳＲの状態を次式：
ｓ(i)＝(ｓi, ｓi+1,...,ｓi+l-2, ｓi+l-1, ｓi+l, ｓi+l+1,..., ｓi+n-1)
とし、ＬＦＳＲ（そのｌ（エル）番目のフリップフロップ）がジャム処理されるものと仮定すれば、時刻ｉ＋１におけるＬＦＳＲの「次の状態」は：
ｓ(i+1)＝(ｓi+1, ｓi+2,...,ｓi+l-1, ｓi+l, ｓi+l+1, ｓi+l+2,..., ｓi+n)
となる。
従って、ｓ(i+1)＝Ｌ’ｓ(i)が成り立ち、ここで随伴行列Ｌは次のようにＬ’に変化する：
【数１７】
2008532410.tif 000024
【０１０５】
従って、セルのすべてのジャムが新たなシーケンスを発生し、この新たなシーケンスは、このジャムがもたらす、通常状態（ジャムなし）と比べた差を与える。
通常のシーケンスは次式：
ｓi+n+1＝ｃ0ｓi+1＋ｃ1ｓi+2＋...＋ｃl-1ｓi+l＋ｃlｓi+l+1＋...＋ｃn-1ｓi+n
のように計算されるものと仮定し、フリップフロップがジャム処理されると、この式は
【数１８】
2008532410.tif 000025
のように変化し、従って、
【数１９】
2008532410.tif 000026
がこれらの差である。
【０１０６】
従って、新たな追加的なシーケンスは次の初期状態：
【数２０】
2008532410.tif 000027
を有する。結論は、すべてのジャムが（ジャムが発生した時刻にシフトされた）新たなシーケンスＳjam(i)(ｘ)を発生する、ということである。従って、ジャムが時刻ｉで発生すれば、ＬＦＳＲの出力はＳ(ｘ)＋ｘiＳjam(i)(ｘ)となる。結果として、初期状態から計算され、収縮シーケンスに依存するジャミングＬＦＳＲの出力が得られる。従って、ジャミングＬＦＳＲの出力シーケンスは次式：
【数２１】
2008532410.tif 000028
の形を有し、ここでｉ、従ってＳjam(i)の初期状態は収縮シーケンス{σi}i≧0に依存する。σi＝０である場合のみに、時刻ｉにおいてジャムが発生する（即ち、Ｓjam(i)(ｘ)が存在する）ことを想起されたい。
【０１０７】
ジャミングＬＦＳＲの内部状態シーケンス{ｓ(i)}i≧0を考え、そして(8)式及び(13)式を考慮に入れれば、
【数２２】
2008532410.tif 000029
であることがわかる。
【０１０８】
内部状態が変化する様式である(15)式は一般化に至り、これについて以下で説明する。
【０１０９】
収縮ＬＦＳＭの公式な定義から始める。
定義４：収縮シーケンス{σi}i≧0があるものと仮定する。内部状態は長さｎを有するものとする。それぞれｎ×ｎ行列Ｍ及びＭ’、及びこれに対応する原始特性多項式を有する２つのＬＦＳＭを考える。これらのＬＦＳＭが共通の内部状態を有し、そして収縮シーケンスに応じて一方のＬＦＳＭを適用することによって次の状態を計算する場合に、これらのＬＦＳＭを収縮ＬＦＳＭと称する。ＬＦＳＭをＬＦＳＲに置き換えることによって、収縮ＬＦＳＲを得る。
【０１１０】
図７に、本発明の好適な実施例による収縮線形有限状態マシン（ＬＦＳＭ）を示す。収縮ＬＦＳＭは、ＬＦＳＲ的なレジスタ７００を具え、その入力は１つの多項式によっては決まらず、２つの多項式を用いる１ビット・マルチプレクサ（多重器）７０１、７０２、７０３によって決まる。キーイングＬＦＳＲはどの多項式を選択するかを制御する。
【０１１１】
収縮ＬＦＳＭの内部状態シーケンスを{ｖ(i)}i≧0とし、そして収縮シーケンスを{σi}i≧0とすれば、次式の関係が成り立つ：
【数２３】
2008532410.tif 000030
【０１１２】
従って、
【数２４】
2008532410.tif 000031
であり、ここに、シーケンス
2008532410.tif 000032
はｉ1個の０から始まり、ｉ2個の１、ｉ3個の０、等と続いてｉl個の１で終わる構成である。これらの関係に基づいて、次の定理を証明することができる。
【０１１３】
定理２：（秘密）収縮シーケンスが周期ＴDを有するものとする。収縮ＬＦＳＭが、長さｎの内部状態ｖを有するものとする。すると、この収縮ＬＦＳＭの出力シーケンスｖi（０≦ｉ≦ｎ−１）は周期Ｔ＝ｃＴDを有し、ここにｃは１≦ｃ≦２n−１なる定数であり、そして線形複雑度Ｌ＝ｎＴDである。
【０１１４】
証明：収縮シーケンス
2008532410.tif 000033
が、ｉ1個の０から始まり、ｉ2個の１、ｉ3個の０、等と続いてｉl個の１で終わる構成であるものとする。行列Ｍ’を、
【数２５】
2008532410.tif 000034
と定義する。すると、
【数２６】
2008532410.tif 000035
となる。対応する行列Ｍ”を有する
2008532410.tif 000036
とｖ(j)（０≦ｊ≦ＴD）について、類似の関係を導出することができる。これらの関係より、出力シーケンスはＴD個のサブシーケンスから成る、ということになり、このことが上記定理を証明する。
【０１１５】
収縮シーケンスの必要なしに、Ｍ”を最大長のものとする（即ちｃ＝２n−１）ために、ＭとＭ’のどちらの条件を満足すべきか、ということが未解決の問題のままである。
【０１１６】
命題１：（秘密）収縮シーケンス{σi}i≧0は周期ＴDを有するものとする。攻撃者は、初期状態及び収縮シーケンスを復元するために、収縮ＬＦＳＭの２Ｌ＝２ｎＴD個の出力ビットを必要とする。
【０１１７】
【非特許文献９】J. Hong, D. Lee, S. Lee, P. Sarkar: “Vulnerability of nonlinear filter generators based on linear finite state machine”FSE’04, LNCS 3017
【０１１８】
証明：長さ２ｎを有するサブシーケンスの各々にバーリカンプ−マシー・アルゴリズムを適用することによって、攻撃者はこれらのサブシーケンスを発生する対応するＬＦＳＲを復元することができる。よって、攻撃者は初期状態を得て、J. Hong, D. Lee, S. Lee, P. Sarkar著：“Vulnerability of nonlinear filter generators based on linear finite state machine”FSE’04, LNCS 3017, 2004年の193〜209ページからの結果を用いて行列Ｍ”を計算することもできる。そして、ＴD個のサブシーケンスのすべてを尽くして、攻撃者は収縮シーケンスを復元することができる。
【０１１９】
いくつかの収縮シーケンスを用いて内部状態を計算する方法を制御する際に、収縮ＬＦＳＭの思想は直ちに、いくつかの（３つ以上の）ＬＳＦＭに一般化される。
【０１２０】
なお、ジャミングＬＦＳＲは収縮ＬＦＳＲではない。それぞれ行列Ｌ及びＬ’によって規定される２つのＬＦＳＲ（ＬＦＳＭ）があるが、２番目の行列Ｌ’は最大長ではない。さらに悪いことに、その行列式は０であり、従って、シーケンスはある点からすべて０になり、このことは不所望である。他方では、ジャミングＬＦＳＲは自己収縮ＬＦＳＲと似ており、即ち、収縮シーケンスに応じて異なる２つのＬＦＳＲとして挙動する。従って、ここでは、ジャミングＬＦＳＲが持つ単純な構造を用いて、ジャミングＬＦＳＲに基づくこうした自己収縮ＬＦＳＲが構成される。なお、(13)式のＬ’の定義に戻れば、（(3)式で定義される）原始多項式ｆ(ｘ)、及び１ビットレジスタ（即ちｌ（エル））に置き換えられるフリップフロップの位置次第で、次式の行列を最長のものにすることができる：
【数２７】
2008532410.tif 000037
【０１２１】
なお、Ｌ’と
2008532410.tif 000038
とはｌ番目の行のみが異なり、この行では（ｌ＋１）番目の列に１が加算される。ここで、自己収縮ＬＦＳＲを次のように定義する用意が整う。
【０１２２】
定義５：収縮シーケンスが与えられているものとする。（(3)式で与えられる）原始多項式ｆ(ｘ)を有するＬＦＳＲが（それぞれ(8)式及び(17)式で与えられる）行列Ｌ及び
2008532410.tif 000039
を有する収縮ＬＦＳＭであると考えられる際に、このＬＦＳＲを自己収縮ＬＦＳＲと称する。このことを図８に示す。
【０１２３】
図８に、本発明の好適な実施例による自己収縮ＬＦＳＲを示し、これは図１の（ＣＲＣ段なしの）スタンドアロン回路の代替を示し、ここで収縮ストリーム８００はキーイングＬＦＳＲによって決まる。
【０１２４】
なお、行列Ｌ及び
2008532410.tif 000040
は共に、原始特性多項式を有する必要がある。ここで結果として、定理２及び命題１は自己収縮ＬＦＳＲについても成り立つ。
【０１２５】
（メッセージ認証コード）
一方向性ハッシュ関数（ＯＷＨＦ：One-Way Hash Function）及び耐衝突性ハッシュ関数（ＣＲＨＦ：Collision Resistant Hash Function）の第１の非公式な定義を提供する。ＯＷＨＦは、任意長の引数Ｘ、及び固定長の出力ｈ(Ｘ)を有する公開関数であり、次の条件を満足する：ｈ及びＸが与えられれば、ｈ(Ｘ)を計算するのは容易であるが、長さｈのＹが与えられると、ｈ(Ｘ)＝ＹとなるＸを見出すことは困難であり、そしてＸ及びｈ(Ｘ)が与えられると、ｈ(Ｘ)＝ｈ(Ｘ’)となるＸ’を見出すことは困難である。ＣＲＨＦは追加的に耐衝突性のＯＷＨＦであり、このことは、ハッシュ関数の同じ出力をもたらす２つの異なるの引数を見出すことは「困難」であることを意味する。（第２の）プリイメージを生成する「理想的なセキュリティ」の場合には２n回の操作を必要とするのに対し、衝突を発生することは２n/2回の操作を必要とする（ｎはハッシュ長）ことを思い出されたい。ＯＷＨＦ及びＣＲＨＦはそれぞれ、弱い一方向性ハッシュ関数及び強い一方向性ハッシュ関数としても知られている。
【０１２６】
ＭＡＣは２つの引数を受け取る関数ｈである。この関数は公に知られ、その第１引数Ｘ（テキスト）も公に知られ、そして任意長のものであり、第２の引数Ｋ（キー）のみが秘密であり、そして固定長を有し、この関数の出力は固定長を有する。ＭＡＣは秘密キーＫを知らない人にとっては、一方向性関数であると共に耐衝突性であるべきである。さらに、攻撃者が引数｛Ｘi｝の大きな集合を選択し、かつ、これに対応する対｛Ｘi, ｈ{Ｘi, Ｋ}｝の集合を得ている際に、キーＫを特定すること、あるいは任意のＸ’≠Ｘについてｈ(Ｘ’, Ｋ)を計算することが「困難」でなければならない。最後のものは適応的選択文書（プレーンテキスト）攻撃として知られている。キーの長さをｎで表し、そしてＭＡＣのタグの長さをｓで表す。セキュリティ・パラメータｎ及びｓを有するＭＡＣは、あり得る攻撃に対する耐性を複雑度ｏ(２min(n, s))で提供すべきであることを想起されたい。
【０１２７】
本発明の好適な実施例によるメッセージ認証コードの一般的設計を開示する。固定の入力サイズを有する圧縮関数の反復に基づく標準的な方法とは対照的に、ストリームにより適したＭＡＣを構成する異なる方法を提案する。
【０１２８】
特性原始多項式ｆ(ｘ)、及び随伴行列Ｌ及びＬ’を有する長さｎの自己収縮ＬＦＳＲを考える。収縮シーケンス{σi}i≧0も与えられているものとする。上述したように、こうした自己収縮ＬＦＳＲの出力シーケンスは
【数２８】
2008532410.tif 000041
となり、ここに
2008532410.tif 000042
は（ジャミングなしの）ＬＦＳＲの通常の出力である。
2008532410.tif 000043
は時刻ｉにおけるＬＦＳＲの状態によって一意的に決まることを想起されたい。「連続供給型ＬＦＳＲ」において上述したように、このＬＦＳＲに連続的に供給する。次の(19)式の入力シーケンスがあるものとする（(10)式参照）：
【数２９】
2008532410.tif 000044
ここに、
2008532410.tif 000045
は次数ｎ−１の多項式である。そして、「連続供給型ＬＦＳＲ」において上述したように、２次の場合に、次の(20)式の出力シーケンスが得られる（(12)式参照）：
【数３０】
2008532410.tif 000046
【０１２９】
2008532410.tif 000047
は、対応する初期状態
2008532410.tif 000048
によって一意的に決まることを想起されたい。ここで、(18)式と(20)式をまとめれば、シーケンスＳ1(ｘ)が連続的に供給される際に、自己収縮ＬＦＳＲは
【数３１】
2008532410.tif 000049
を生成する、ということが得られ、ここに
2008532410.tif 000050
は、対応する初期状態
2008532410.tif 000051
によって一意的に決まり、そして
2008532410.tif 000052
は、時刻ｉにおけるＬＦＳＲの状態によって決まる。時刻ｉにおいてσi＝０である場合のみにジャムが発生する（即ち
2008532410.tif 000053
が存在する）ことを想起すれば、従って(21)式は次式：
【数３２】
2008532410.tif 000054
のように書き換えることもできる。
【０１３０】
なお、連続供給型自己収縮ＬＦＳＲの２つの入力にそれぞれ収縮シーケンス
2008532410.tif 000055
及び
2008532410.tif 000056
が供給され、これに対応して（
2008532410.tif 000057
及び
2008532410.tif 000058
で表す）２つの出力シーケンスが発生される場合には、計算は線形であるので、出力シーケンス
2008532410.tif 000059
は入力シーケンス
2008532410.tif 000060
に対応する。
【０１３１】
補助定理３：（秘密）収縮シーケンス{σi}i≧0が周期ＴDを有するものとする。長さｎの連続供給型自己収縮ＬＦＳＲを考える。このＬＦＳＲの入力シーケンスをＰ(ｘ)で表し、出力シーケンスをＳ(ｘ)で表す。すると、攻撃者がこの収縮シーケンスを復元するためには、Ｐ(ｘ)の連続する２ｎＴD個の入力ビット、及びこれらに対応するＳ(ｘ)からの出力ビットを必要とする。収縮シーケンスの知識は、攻撃者がさらに、シーケンスＰ(ｘ)の全体をＳ(ｘ)から計算することを可能にする。
【０１３２】
上述した長さｎの連続供給型自己収縮ＬＦＳＲを考える。収縮シーケンスを{σi}i≧0とし、入力シーケンスをＳ1(ｘ)とする。自己収縮ＬＦＳＲは長さｎの内部状態を有することを想起されたい。ｆを、ｒ≦ｎ個の入力を有する非線形関数とする。ＬＦＳＲのいくつかの段（タップ）を関数ｆの入力とすることによる標準的な方法で（上述した「非線形フィルタ生成器」の章を参照）、関数ｆをＬＦＳＲの内部状態に適用する。このようにして、標準的なＬＦＳＲの出力Ｓ4(ｘ)（(22)式）を新たなシーケンスに変換する。この変換を次式のように表す：
【数３３】
2008532410.tif 000061
【０１３３】
なお、非線形関数ｆ(ｘ)を適用することによって、次の２つのゴールに達する：第１に、入力と出力との線形依存性を壊す；第２に、新たなシーケンスＳ5(ｘ)はＳ4(ｘ)と同じ周期を有するが、線形複雑度は増加する。ブール関数ｆの代数的な次数をdeg(ｆ)で表し、なお、ｆの非線形性はdeg(ｆ)≧２を暗に意味する。関数ｆは、上述した「非線形フィルタ生成」の章で挙げた他のいくつかの性質も有するべきであることを強調する。従って、補助定理３を次のように改善することができる。
【０１３４】
定理３：（秘密）収縮シーケンス{σi}i≧0が周期ＴDを有するものとする。非線形フィルタ関数ｆを有する長さｎの連続供給型収縮ＬＦＳＲを考える。ＬＦＳＲへの入力シーケンスをＰ(ｘ)で表し、ｆによって発生される出力シーケンスをＳ(ｘ)で表す。すると、攻撃者は収縮シーケンスを復元するために、Ｐ(ｘ)の少なくとも
2008532410.tif 000062
個連続する入力ビット、及びこれらに対応するＳ(ｘ)からの出力ビットを必要とする。収縮シーケンスの知識は、攻撃者がさらに、シーケンスＰ(ｘ)の全体をＳ(ｘ)から計算することを可能にする。
【０１３５】
図９に、本発明の好適な実施例によるＳＮ−ＭＡＣを示す。
【０１３６】
ＳＮ−ＭＡＣアルゴリズムを提供する用意は整い、このアルゴリズムは、図９に示す次のビルディングブロックを含む：
自己収縮ＬＦＳＲ９００を規定する（即ち、対応する随伴行列Ｌ及び
2008532410.tif 000063
を有する）次数ｎ3の２つの原始多項式ｆ3(ｘ)及び
2008532410.tif 000064
。
暗号シーケンスを発生する自己収縮発生器９０１を規定する次数ｎ1の原始多項式ｆ1(ｘ)。
収縮シーケンス{σi}i≧0９０４を発生するＬＦＳＲを規定する次数ｎ2の原始多項式ｆ2(ｘ)。
ＣＲＣ９０２を規定する次数ｓの既約多項式ｇ(ｘ)。
所望の特性９０３を有する非線形（フィルタ）関数ｆ(ｘ)。
【０１３７】
ＳＮ−ＭＡＣは長さｎ＝ｎ1＋ｎ2のキーを有し、長さｓを有するタグを生成し、即ち、ＳＮ−ＭＡＣはセキュリティ・パラメータｎ及びｓを有するＭＡＣである。ＳＮ−ＭＡＣは、固定の構成に代わるＭＡＣアルゴリズム用の一般的なフレームワーク（枠組み）である。従って、提案するいずれのパラメータも固定せず、ユーザが自分の用途に最も適したパラメータを選定することを可能にする。ＳＮ−ＭＡＣの核心は、非線形フィルタ関数を有する連続供給型自己収縮ＬＦＳＲである（上述した「連続供給型自己収縮ＬＦＳＲに非線形フィルタを適用」の章を参照）。ＳＮ−ＭＡＣはさらに、混合エンジンと称する。このＳＮ−ＭＡＣアルゴリズムは次のように記述することができる：
１．プレーンテキストが特定次数の多項式Ｐ(ｘ)として提供されるものとする。このプレーンテキストは２ｓ−２ｎ3の最小長を有する必要がある。
２．パッドを、長さ２n3の固定の接尾文字（例えば０）としてプレーンテキストに追加する。パッドを追加したプレーンテキストをＰＰ(ｘ)で表し、そしてこれを次数ｍの多項式とする。
３．パッドを追加したプレーンテキストＰＰ(ｘ)を、自己収縮発生器によって発生される暗号シーケンスとのＸＯＲをとることによって暗号化する。
４．Ｓ1(ｘ)は混合エンジン用の入力シーケンスである（(19)式参照）。
５．混合エンジン用の上記収縮シーケンス{σi}i≧0は、特性原始多項式ｆ2(ｘ)を有するＬＦＳＲによって発生する。
６．混合エンジンの出力シーケンスをＳ5(ｘ)で表す（(2)式参照）。
７．最終ステップは、（Ｓ5(ｘ)からのｇ(ｘ)に基づいて）ＣＲＣ値を計算することである。この長さｓのＣＲＣ値は本発明のＭＡＣアルゴリズムの出力、即ちＭＡＣのタグである。
【０１３８】
ここで、本発明の好適な実施例によるいくつかの設計上の選択を説明する。なお、すべてのジャムは、テキストの終わりまで差を伝搬させ、従って攻撃者の観点からは、攻撃者がプレーンテキストの最終ビットを改変すれば成功の確率はより高くなる。この種の攻撃を回避するために、プレーンテキストに固定の接尾文字を付加することを必要とする。
【０１３９】
パッド（接尾文字）を付加したプレーンテキストＰＰ(ｘ)は次数ｍであるので、これに対応する出力Ｓ5(ｘ)も次数ｍの多項式である。与えられたＳ5(ｘ)及びｇ(ｘ)に対して、(9)式を満足する２m-s個の多項式が存在する（補助定理１参照）ことを想起されたい。従って、（Ｓ5(ｘ)については）与えられたタグに対して少なくとも２s個の対応する異なる選択肢を持つために、パッドを付加したプレーンテキストはｍ≧２ｓなる長さを有する必要がある。
【０１４０】
なお、収縮シーケンスを発生するＬＦＳＲは周期
【数３４】
2008532410.tif 000065
を有し、従って、定理３より、混合エンジンの出力シーケンスの線形複雑度は少なくとも
【数３５】
2008532410.tif 000066
である。他方では、自己収縮発生器によって発生される暗号シーケンスは周期
2008532410.tif 000067
及び線形複雑度
2008532410.tif 000068
を有する。両方のキー・サブシーケンス（暗号シーケンス及び収縮シーケンス）は互いに素の周期を有するので、キー・シーケンスの周期は
【数３６】
2008532410.tif 000069
である。さらに、攻撃者はキーを導出するために、即ち混合エンジン及び自己収縮発生器を共に解読するために、対応する入力／出力対（即ちＰＰ(ｘ)／Ｓ5(ｘ)の）少なくとも
【数３７】
2008532410.tif 000070
ビットを必要とする。なお、この計算では、定理３からのより「強い」結果の代わりに補助定理３からの結果を用いる。
【０１４１】
ＳＮ−ＭＡＣはＭＡＣアルゴリズムに指向したストリームであるので、ストリーム暗号が特定量の情報を操作する際にキーを変更するために用いるのと同じ方法を用いる。上述した計算に基づけば、２n-2ビットの情報を操作する際に、現在のＳＮ−ＭＡＣキーを置き換える必要がある。なお、後者は、キー当たり１つのＭＡＣしか許容されないことを暗に意味するものではなく、その代わりに、ストリーム暗号が働く際に、キー・シーケンスをリセットせずに何回か暗号化（ＭＡＣタグを計算）することができる。１つのキーで操作することを許容される情報は、キー・シーケンスの期間に等しく、そしてこの期間は、攻撃者がキーを明らかにするために必要とする最小量の情報であることを示している、ということを強調する。
【０１４２】
ＭＡＣアルゴリズムについての厳密な証明は通常、ブロック暗号のようなプリミティブまたは専用のハッシュ関数のいずれかに基づく、あるいは汎用的なハッシュ・パラダイム（理論的枠組み）に基づくアルゴリズムについて得られる。本発明が提案するアルゴリズムはストリーム用に特別に設計したものであり、従って、圧縮関数の下になる標準的な方法に頼るものではない。ＯＷＨＦ／ＣＲＨＦの定義を、任意長の入力に対して（固定長の出力の代わりに）（当該入力と）同じ長さを有する出力を計算する関数に拡張する。ＳＮ−ＭＡＣアルゴリズムを概略的に次式のように提示する：
Ｆ：ＰＰ(ｘ)→Ｓ5(ｘ)          (24)
Ｇ：Ｓ5(ｘ)→タグ
【０１４３】
換言すれば、最終ステップ（ＣＲＣの計算）なしのＳＮ−ＭＡＣを、与えられた（任意長の）入力ＰＰ(ｘ)に対して同じ長さを有する出力Ｓ5(ｘ)を計算する関数Ｆとして考える。同様に、最終ステップを、任意長の入力を取り入れて固定長の出力を生成する関数Ｇとして定義する。従って、以上で示したように、（固定キーを有する）関数Ｆは任意長を有するＯＷＨＦである。Ｆは任意長を有するＣＲＨＦでもあることを証明することは、まだ継続する作業である。任意長のＦが与えられた際に、合成Ｇ０ＦがＣＲＨＦとなるようにＧをどのように選定するかは興味ある公開された問題である。この目的を達成するために、Ｇをエラー検出コードになるように選定する。
【０１４４】
従って、本発明の好適な実施例によれば、高度に制約された装置に十分なレベルの安全性（セキュリティ）を提供し、そしてストリーム暗号と共に使用される、メッセージ認証コードＳＮ−ＭＡＣのための新たな設計を開示する。この設計は、無力な装置用の、ハードウェアで最適化されたＭＡＣアルゴリズムである。一方向性（耐衝突性）ハッシュ関数の定義は、任意長の関数に拡張されている。また、対称暗号法用の新たないくつかのビルディングブロックも、単独で興味あるものであり、これらも開示する。
【０１４５】
従って、次の構成を開示する：
Ａ．図１のスタンドアロン回路から最終のＣＲＣ段（他のＬＦＳＲによるキーを用いる、ジャムのあるロード可能なＬＦＳＲ）をなくしたもの。この回路の出力は「そのままの形で」使うことはできないが、ＭＡＣを発生する完結した回路が必要とする基本的な情報である。
Ｂ．ＣＲＣ回路３を具えた、図１のスタンドアロン回路。
Ｃ．ハッシュ関数を、効率的なルックアップテーブル（早見表）及びルーティング（経路設定）アルゴリズムを生成するために用いられる関数として用いる、上記Ａによる回路。
Ｄ．２つのキーイングＬＦＳＲ１、４（図２参照）を用いる、上記Ａによる回路。
Ｅ．（図４に示す）上記Ａによる２つの回路１０００、１１００、入力３００、１００、２００はすべて、独立したキーイングＬＦＳＲから来る。
Ｆ．（図７に示す）上記Ａによる回路の代替、１つのＬＦＳＲ的なレジスタ７００によって実現され、その入力は１つの多項式によって決まらず、２つの多項式を用いた１ビット・マルチプレクサ７０１、７０２、７０３によって決まる。キーイングＬＦＳＲはどちらの多項式を選択するかを制御する。
Ｇ．図８のように実現される、上記Ａによる回路の代替、収縮ストリーム８００はキーイングＬＦＳＲによって決まる。
Ｈ．図９に示す回路全体。
Ｉ．擬似乱数発生器９０１、及びこれに関連するプレーンテキスト暗号化ＸＯＲなしの、図９に示す回路。
Ｊ．一旦、プレーンテキストがすべて上記Ａ（あるいはその代替Ｄ、Ｆ及びＧのうちの１つ）に供給され、次の段の入力として、ＡにおけるＬＦＳＲの最終状態をとる。この状態を、回路Ａに等しいサイズのＳＳＧ（Self Shrinking Generator：自己収縮発生器）の初期状態として用いる。初期状態のサイズ（例えば６４ビットのＬＦＳＲに対する６４ビットの出力）を得るまでＳＳＧを動作させる。この出力が最終的なＭＡＣである。
【０１４６】
図５に、本発明による発生器でメッセージ認証コードを発生する方法の好適な実施例のフローチャートを示す。この方法はステップＳ１における、プレーンテキストデータの取得から始まり、このデータは混合エンジンに伝送される。ステップＳ２では、擬似乱数発生器によって擬似乱数発生を実行し、発生した擬似乱数は混合エンジンに伝送される。ステップＳ３では、混合エンジンはＬＦＳＲを具えることができ、線形フィードバック・シフトレジスタの構成、及び発生した擬似乱数に基づく線形性除去を実行する。その後にステップＳ４では、線形性除去したデータセットに基づいてチェックサムまたはエラー検出コードを発生し、その後に、ステップＳ５では、ＭＡＣ発生を実行する。
【０１４７】
なお、プレーンテキストデータの線形性除去及び擬似乱数発生、並びにエラー検出コードの発生は異なるハードウェア構成要素によって実行することができる。
【０１４８】
図６に、本発明による方法の好適な実施例を実行する、本発明による処理装置の好適な実施例を示す。図６に示す実施例は中央処理装置（ＣＰＵ）１５１を具え、ＣＰＵ１５１は、第１、第２、または第３のデータセットを記憶するためのメモリ１５２に接続されている。データプロセッサ１５１は、キーボードまたはコンピュータ・トモグラフィ（断層撮影）装置のような複数の入力／出力ネットワーク装置に接続することができる。データプロセッサ１５１はさらに、プロセッサ１５１に記憶されている情報またはプレーンテキストを表示する表示装置１５４、例えばコンピュータモニタに接続することができる。オペレータまたはユーザは、キーパッド１５１及び／または他の出力装置を介してプロセッサ１５１と対話することができ、このことは図６には示していない。
【０１４９】
さらに、バスシステム１５３を介して、プロセッサ１５１を、例えば符号化されたデータストリームを受信すべく構成された受信ステーションに接続することもできる。
【０１５０】
以上で説明したように、本発明は耐タンパ性の通信を次の一般的な領域で実現するために直ちに利用することができる：
極めて効率的なパワーマネージメント（消費電力管理）を必要とするシステム、例えば常時オンのスタンドアロン医療装置。
最大通信速度が最重要であるシステム、インターネットのバックボーン（基幹）を動作させる例えば超高速ルータ。
【０１５１】
これに加えて、本発明は、動作中に外部記憶された状態の強力な完全性（インテグリティ）のチェックを要求されるシステム、例えば作業データを外部ＲＡＭに記憶する安全なマイクロプロセッサを最適化するために用いることができる。
【０１５２】
さらに、本発明は：
埋込みデバイス内のファームウェア及びオペレーティングシステムの認証；
ＯＭＡ  ＤＲＭ（Open Mobile Alliance Digital Right Management：携帯電話向け著作権管理規格）、
に有利に適用することができる。
【０１５３】
なお、「具えている、具えた」は他の要素またはステップを排除するものではなく、各構成要素は複数存在し得る。そして、単一のプロセッサまたはシステムが、請求項に挙げたいくつかの手段またはユニットを実現することができる。また、異なる実施例に関連して記載した要素を組み合わせることができる。
【図面の簡単な説明】
【０１５４】
【図１】本発明の好適な実施例によるＳＮ−ＭＡＣ発生器の概略表現を示す図である。
【図２】本発明の好適な実施例による他のＳＮ−ＭＡＣ発生器の概略表現を示す図である。
【図３】本発明の好適な実施例による、ロード可能なフリップフロップを有するキー付きプレーンテキスト混合エンジンの概略表現を示す図である。
【図４】本発明の他の好適な実施例による混合エンジンの概略表現を示す図である。
【図５】本発明による、メッセージ認証コードを発生する方法の好適な実施例のフローチャートである。
【図６】本発明による方法の好適な実施例を実行するための、本発明によるプロセッサの好適な実施例を示す図である。
【図７】本発明の好適な実施例による収縮線形有限状態マシン（ＬＦＳＭ）を示す図である。
【図８】本発明の好適な実施例による自己収縮ＬＦＳＲを示す図である。
【図９】本発明の好適な実施例によるＳＮ−ＭＡＣを示す図である。特に、プレーンテキストを、ブロック９００によって形成される混合エンジンにプレーンテキストを供給する前に、回路９０１によって発生される擬似乱数列との排他的論理和をとることによって事前処理する。最後に、自己収縮ＬＦＳＲ９００の出力を、ＣＲＣ回路９０２によって処理する前に、非線形関数回路９０３によって発生する。
【図１】
2008532410.tif 000071
【図２】
2008532410.tif 000072
【図３】
2008532410.tif 000073
【図４】
2008532410.tif 000074
【図５】
2008532410.tif 000075
【図６】
2008532410.tif 000076
【図７】
2008532410.tif 000077
【図８】
2008532410.tif 000078
【図９】
2008532410.tif 000079
【国際調査報告】
2008532410.tif 000080
2008532410.tif 000081