ＫＡＳＵＭＩラウンド回路
【課題】効果的なＫＡＳＵＭＩ暗号化のための技術を提供する。
【解決手段】１つの観点において、ＫＡＳＵＭＩ暗号の断片部分を生成する１つのＫＡＳＵＭＩラウンドが、８つの連続したラウンドがＫＡＳＵＭＩ出力を生成するよう、適切なフィードバックをともなって配備される。他の観点において、３つの連続するサイクルがＦＯ出力を生成するよう、ＦＯ関数の１／３が適切なフィードバックをともなって配備される。さらに他の観点において、２つの後続するサイクルがＦＩ出力を生成するよう、ＦＩ関数が適切なフィードバックをともなって配備される。さらに他の観点において、２つのシフトレジスタを備えるサブ鍵生成器が、各ラウンドとそのサブ段用のサブ鍵を効果的に生成する。これらの観点は、簡単なユーザーインタフェースをともなうＫＡＳＵＭＩにおいて、小面積や低コストの実現といった高い利点の実現を総合的にもたらす。
【解決手段】１つの観点において、ＫＡＳＵＭＩ暗号の断片部分を生成する１つのＫＡＳＵＭＩラウンドが、８つの連続したラウンドがＫＡＳＵＭＩ出力を生成するよう、適切なフィードバックをともなって配備される。他の観点において、３つの連続するサイクルがＦＯ出力を生成するよう、ＦＯ関数の１／３が適切なフィードバックをともなって配備される。さらに他の観点において、２つの後続するサイクルがＦＩ出力を生成するよう、ＦＩ関数が適切なフィードバックをともなって配備される。さらに他の観点において、２つのシフトレジスタを備えるサブ鍵生成器が、各ラウンドとそのサブ段用のサブ鍵を効果的に生成する。これらの観点は、簡単なユーザーインタフェースをともなうＫＡＳＵＭＩにおいて、小面積や低コストの実現といった高い利点の実現を総合的にもたらす。
【発明の詳細な説明】
【分野】
【０００１】
本発明は、一般に通信に関し、特にＫＡＳＵＭＩ暗号化を行う新規で改善された方法および装置に関する。
【背景】
【０００２】
無線通信システムは、音声、データ、その他の様々なタイプの通信を提供するために広く配備されている。これらのシステムは、符号分割多元接続（ＣＤＭＡ）、時分割多元接続（ＴＤＭＡ）、または他のいくつかの変調技術に基づくことができる。ＣＤＭＡシステムは、他のタイプのシステムよりも確かな利点を提供し、増加したシステム容量を含んでいる。
【０００３】
ＣＤＭＡシステムは、(1)「デュアルモード広帯域拡散スペクトルセルラシステムのためのＴＩＡ／ＥＩＡ−９５−Ｂ移動局―基地局互換性規格」（ＩＳ−９５規格）、(2)「デュアルモード広帯域拡散スペクトルセルラ移動局のためのＴＩＡ／ＥＩＡ−９８−Ｃ勧告最低基準」（ＩＳ−９８規格）、(3)「第３世代提携事業」（３ＧＰＰ）という名の共同体により提案され、文献Ｎｏｓ．３Ｇ ＴＳ ２５．２１１、３Ｇ ＴＳ ２５．２１２、３Ｇ ＴＳ ２５．２１３、および３Ｇ ＴＳ ２５．２１４（Ｗ−ＣＤＭＡ規格）を含む文献のセットに具体化されている規格、(4)「第３世代提携事業２」（３ＧＰＰ２）という名の共同体により提案され、「ｃｄｍａ２０００拡散スペクトルシステムのためのＴＲ−４５．５物理レイヤ規格」、「ｃｄｍａ２０００拡散スペクトルシステムのためのＣ．Ｓ０００５−Ａ上位レイヤ（レイヤ３）信号法規格」、および「Ｃ．Ｓ００２４ ｃｄｍａ２０００高速パケットデータ空中インターフェース仕様」（ｃｄｍａ２０００規格）を含む文献のセットに具体化されている規格、および(5)他のいくつかの規格、といった１つ以上のＣＤＭＡ規格に対応するように設計することができる。ｃｄｍａ２０００規格の高速パケットデータ仕様を実施するシステムを、本明細書中では高速データレート（ＨＤＲ）システムと称す。ＨＤＲシステムは、ＴＩＡ／ＥＩＡ−ＩＳ−８５６、「ＣＤＭＡ２０００高速パケットデータ空中インターフェース仕様」に記録されている。また、提案された無線システムは、ＨＤＲと１つの空中インターフェースを使用する低速データレートサービス（例えば、音声サービスおよびファックスサービス）との組み合わせを提供する。
【０００４】
暗号化技術は、送信データの安全性を提供するため、およびデータにアクセスしようとするユーザーに認証を提供するために、通常使用される。暗号化技術は、様々な分野で使用され、特にデジタル無線通信システムに有用である。
【０００５】
Ｗ−ＣＤＭＡ規格用に指定された１つの暗号化アルゴリズムが、ＫＡＳＵＭＩである。ＫＡＳＵＭＩは、１９９９年１２月２３日付けのＥＴＳＩ／ＳＡＧＥ仕様書「３ＧＰＰ機密性および完全性アルゴリズムの仕様」バージョン１．０の「文書２：ＫＡＳＵＭＩ仕様」（以下、ＫＡＳＵＭＩ仕様）に詳述されている。ＫＡＳＵＭＩの様々な用途が、同じＥＴＳＩ／ＳＡＧＥ仕様書において、「文書１：ｆ８およびｆ９仕様」に詳述されている。ＫＡＳＵＭＩは、１２８ビット鍵を利用して６４ビット入力から６４ビット出力を生成するブロック暗号である。ＫＡＳＵＭＩの出力は、通常、鍵ストリームのビットと暗号化されるべきデータのビットとの排他的論理和（ＸＯＲ）をとることにより、暗号化データに対する鍵ストリームとして使用することができる。
【０００６】
通信システムのための技術では、その様々なサブ関数を実行するために、ＡＳＩＣまたは他のハードウェア解法を用いるのが一般的である。ＡＳＩＣ設計において、利用面積がより小さくなると、より低いコスト、より高い歩留まり、そして多くの場合はより低い電力につながる。低コストと低電力は、固定用途と移動用途の両方で有益であるが、低電力は、電池を利用する移動機器にとって特に重要である。同時に、処理はある制限時間内で完了しなければならない。Ｗ−ＣＤＭＡシステムのような無線データシステムは、それらの加入者と基地局にＫＡＳＵＭＩの実施を組み込む必要があり、設計者は、先に述べたことを含む様々な制約の中で作業する必要がある。このような事情により、ＫＡＳＵＭＩ暗号化を効果的に行う装置および方法の技術的な必要性がある。
【発明の開示】
【概要】
【０００７】
本明細書中で開示された実施形態は、効果的なＫＡＳＵＭＩ暗号化のための効果的な装置または方法の必要性に対処している。１つの観点において、ＫＡＳＵＭＩ暗号の断片部分を生成する１つのＫＡＳＵＭＩラウンドが、８つの連続したラウンドがＫＡＳＵＭＩ出力を生成するよう、適切なフィードバックをともなって配備される。他の観点において、３つの連続するサイクルがＦＯ出力を生成するよう、ＦＯ関数の１／３が適切なフィードバックをともなって配備される。さらに他の観点において、２つの後続するサイクルがＦＩ出力を生成するよう、ＦＩ関数が適切なフィードバックをともなって配備される。さらに他の観点において、２つのシフトレジスタを備えるサブ鍵生成器が、各ラウンドとそのサブ段用のサブ鍵を効果的に生成する。これらの観点は、簡単なユーザーインタフェースをともなうＫＡＳＵＭＩにおいて、小面積や低コストの実現といった高い利点の実現を総合的にもたらす。本発明の他の様々な観点も提示される。
【０００８】
本発明は、以下でさらに詳しく述べるように、本発明の様々な観点、実施形態、および特徴を実施する方法およびシステム要素を提供する。
【０００９】
本発明の特徴、性質、および利点は、以下に述べる詳細な説明を図面とともに参照することでより明らかになる。図面全体を通じて同じ参照符号により対応付けがなされている。
【詳細な説明】
【００１０】
図１は、多数のユーザーをサポートし、本発明の様々な観点を実施できる無線通信システム１００を示す図である。システム１００は、１つ以上のＣＤＭＡ規格および／または設計（例えば、ＩＳ−９５規格、ｃｄｍａ２０００規格、ＨＤＲ仕様、Ｗ−ＣＤＭＡ規格）をサポートするよう設計することができる。簡単にするために、システム１００は、２つのアクセス端末１０６（遠隔端末または移動局と呼ぶこともできる）と通信する３つのアクセスポイント１０４（基地局と呼ぶこともできる）を含むよう図示している。アクセスポイントとそのカバレッジ領域は、まとめて「セル」と呼ばれることが多い。ＫＡＳＵＭＩアルゴリズムは、１つ以上のアクセスポイント、１つ以上のアクセス端末、またはそれら両方に配備することができる。
【００１１】
実施中のＣＤＭＡシステムに応じて、各アクセス端末１０６は、任意の時点において、順方向リンク上で１つの（または場合によってはさらに多くの）アクセスポイント１０４と通信することができ、アクセス端末がソフトハンドオフにあるか否かに応じて、逆方向リンク上で１つ以上のアクセスポイントと通信することができる。順方向リンク（すなわち、ダウンリンク）は、アクセスポイントからアクセス端末への伝送を指しており、逆方向リンク（すなわちアップリンク）はアクセス端末からアクセスポイントへの伝送を指している。
【００１２】
図２（ａ）−２（ｄ）は、ＫＡＳＵＭＩ仕様に規定されているＫＡＳＵＭＩアルゴリズムを図示している。図２（ａ）は、ＫＡＳＵＭＩ２００の一番上のレベルの図を示している。図２（ｂ）は、ＦＯ関数を示している。図２（ｃ）は、ＦＩ関数を示している。図２（ｄ）は、ＦＬ関数を示している。
【００１３】
図２（ａ）に示すように、ＫＡＳＵＭＩは８つのラウンドからなる。各ラウンドは、１つのＦＬ関数、１つのＦＯ関数、および３２ビットＸＯＲ関数から成り立っている。ＦＬ関数はＦＬｉで表わされ、ここでｉはどのラウンドを表わすかを示し、１から８までである。同様に、ＦＯ関数はＦＯｉで表わされる。各ラウンドでは、ＫＬｉ、ＫＯｉ、およびＫＩｉで表わされる様々なサブ鍵を利用する。ＫＬｉは、ＫＬｉ，１およびＫＬｉ，２で表わされる２つの１６ビットサブ鍵からなる３２ビットサブ鍵である。ＫＯｉとＫＩｉは、４８ビットサブ鍵であり、それぞれＫＯｉ，１、ＫＯｉ，２およびＫＯｉ，３と、ＫＩｉ，１、ＫＩｉ，２およびＫＩｉ，３とで表わされる３つの１６ビットサブ鍵からなる。１６ビットサブ鍵の用途については、以下で図２（ｂ）−２（ｄ）を基にさらに詳しく述べる。
【００１４】
ラウンド１は、ＦＬ１・２０２、ＦＯ１・２０４、および３２ビットのビットワイズＸＯＲ２０６を備えている。６４ビット入力は２つの３２ビットセグメントに分けられ、これらを左セグメントおよび右セグメントとして述べる。右セグメントは、ＸＯＲ２０６においてＦＯ１・２０４の出力と排他的論理和をとられ、ラウンド１の右出力を生成する。各ラウンドの右出力は、後に続くラウンドへの左入力となる。したがって、ラウンド１の右出力は左入力としてラウンド２に供給される。左入力セグメントはＦＬ１・２０２に供給され、ここで、サブ鍵ＫＬ１を利用して、以下で述べるＦＬ関数に従って処理される。ＦＬ１・２０２の出力は、これも以下で述べるＦＯ関数に従ってＫＯ１およびＫＩ１とともに処理するために、ＦＯ１・２０４に供給される。いま述べたように、ＦＯ１・２０４の出力は、入力の右セグメントとビットワイズ排他的論理和をとるために、ＸＯＲ２０６に供給される。また左入力セグメントは、右入力としてラウンド２に供給される。一般に、各ラウンドの左入力は、そのラウンドにおいて様々な処理に使用され、後に続くラウンドへの右入力となる。
【００１５】
ラウンド２は、ＦＬ２・２０８、ＦＯ２・２１０、およびＸＯＲ２１２を備えている。ラウンド２は、関数ＦＯとＦＬの順序が逆になることを除いて、ラウンド１と同様である。一般に、奇数のラウンドはＦＯ関数に供給をするＦＬ関数を有し、偶数のラウンドはＦＬ関数に供給をするＦＯ関数を有する。ラウンド２への右入力は、ＸＯＲ２１２においてＦＬ２・２１０の出力と排他的論理和をとられ、ラウンド２の右出力を生成する。既に述べたように、ラウンド２の右出力は左入力としてラウンド３に供給される。左入力セグメントは、ＦＯ関数に従ってＫＯ２およびＫＩ２とともに処理するために、ＦＯ２・２０８に供給される。ＦＯ２・２０８の出力は、ＦＬ関数に従ってＫＩ２とともに処理するために、ＦＬ２・２１０に供給される。また左入力セグメントは、右入力としてラウンド３に供給される。
【００１６】
ラウンド３、５、および７は、当然ながら各ラウンドへの入力がＫＡＳＵＭＩ入力ではなく前のラウンドの出力によるものであることを除いて、ラウンド１と同様に構成されている。ラウンド４、６、および８は、ラウンド２と同様に構成されている。
【００１７】
ラウンド３において、ＸＯＲ２１２の出力は、ＦＬ関数に従ってＫＬ３とともに処理するために、ＦＬ３・２１４に供給される。ＦＬ３・２１４の出力は、ＦＯ関数に従ってＫＯ３およびＫＩ３とともに処理するために、ＦＯ３・２１６に供給される。ＦＯ３・２１６の出力は、ＸＯＲ２０６の出力とビットワイズ排他的論理和をとるために、ＸＯＲ・２１８に供給される。
【００１８】
ラウンド４において、ＸＯＲ２１８の出力は、ＦＯ関数に従ってＫＯ４およびＫＩ４とともに処理するために、ＦＯ４・２２０に供給される。ＦＯ４・２２０の出力は、ＦＬ関数に従ってＫＬ４とともに処理するために、ＦＬ４・２２２に供給される。ＦＬ４・２２２の出力は、ＸＯＲ２１２の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２２４に供給される。
【００１９】
ラウンド５において、ＸＯＲ２２４の出力は、ＦＬ関数に従ってＫＬ５とともに処理するために、ＦＬ５・２２６に供給される。ＦＬ５・２２６の出力は、ＦＯ関数に従ってＫＯ５およびＫＩ５とともに処理するために、ＦＯ５・２２８に供給される。ＦＯ５・２２８の出力は、ＸＯＲ２１８の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２３０に供給される。
【００２０】
ラウンド６において、ＸＯＲ２３０の出力は、ＦＯ関数に従ってＫＯ６およびＫＩ６とともに処理するために、ＦＯ６・２３２に供給される。ＦＯ６・２３２の出力は、ＦＬ関数に従ってＫＬ６とともに処理するために、ＦＬ６・２３４に供給される。ＦＬ６・２３４の出力は、ＸＯＲ２２４の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２３６に供給される。
【００２１】
ラウンド７において、ＸＯＲ２３６の出力は、ＦＬ関数に従ってＫＬ７とともに処理するために、ＦＬ７・２３８に供給される。ＦＬ７・２３８の出力は、ＦＯ関数に従ってＫＯ７およびＫＩ７とともに処理するために、ＦＯ７・２４０に供給される。ＦＯ７・２４０の出力は、ＸＯＲ２３０の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２４２に供給される。
【００２２】
ラウンド８において、ＸＯＲ２４２の出力は、ＦＯ関数に従ってＫＯ８およびＫＩ８とともに処理するために、ＦＯ８・２４４に供給される。ＦＯ８・２４４の出力は、ＦＬ関数に従ってＫＬ８とともに処理するために、ＦＬ８・２４６に供給される。ＦＬ８・２４６の出力は、ＸＯＲ２３６の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２４８に供給される。
【００２３】
ＸＯＲ２４８の出力とＸＯＲ２４２の出力とは、図２（ａ）においてＣと記された６４ビットのＫＡＳＵＭＩ出力を生成するために連結される。
【００２４】
図２（ｂ）は、上述したＦＯ関数を実行する計算ステップを図示している。ＦＯ関数は３２ビット入力を取り入れ、それをそれぞれ左入力と右入力の２つの１６ビットセグメントに分ける。留意すべきは、ＦＯ関数は３つの段を含んでおり、それらは以下で詳しく述べるように、それぞれ２つの１６ビットビットワイズ排他的論理和とＦＩｉ１、ＦＩｉ２、およびＦＩｉ３で示される関数ＦＩｉのインスタンスとを含んでいることである。この説明において、図２（ａ）について上述した各ラウンドに１つのＦＯ関数があるので、ｉはラウンド番号に相当する。
【００２５】
関数ＦＯの第１段において、左１６ビット入力は、ＸＯＲ２５０において１６ビットサブ鍵ＫＯｉ，１とビットワイズ排他的論理和をとられる。上述したように、ＫＯｉ，１は４８ビットサブ鍵ＫＯｉの１６ビットサブ鍵である。また、ＫＯｉ，２とＫＯｉ，３は、ＫＯｉの１６ビットサブ鍵である。ＸＯＲ２５０の出力は、以下で述べるＦＩ関数に従ってＫＩｉ，１とともに処理するために、ＦＩｉ１・２５２に供給される。上述したように、ＫＩｉ，１は４８ビットサブ鍵ＫＩｉの１６ビットサブ鍵である。また、ＫＩｉ，２とＫＩｉ，３は、ＫＩｉの１６ビットサブ鍵である。ＦＩｉ１・２５２の出力は、右入力と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２５４に供給される。
【００２６】
関数ＦＯの第２段において、右入力は、サブ鍵ＫＯｉ，２と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２５６に供給される。その結果は、ＦＩ関数に従ってＫＩｉ，２とともに処理するために、ＦＩｉ２・２５８に供給される。ＦＩｉ２・２５８の出力は、ＸＯＲ２５４の出力と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２６０に供給される。
【００２７】
関数ＦＯの第３段において、ＸＯＲ２５４の出力は、サブ鍵ＫＯｉ，３と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２６２に供給される。その結果は、ＦＩ関数に従ってＫＩｉ，３とともに処理するために、ＦＩｉ３・２６４に供給される。ＦＩｉ３・２６４の出力は、ＸＯＲ２６０の出力と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２６６に供給される。ＸＯＲ２６０の出力は、図２（ｂ）においてＦＯと記された関数の出力を生成するために、ＸＯＲ２６６の出力と連結される。
【００２８】
図２（ｃ）は、上述したＦＩ関数を実行する計算ステップを図示している。ＦＩ関数は１６ビット入力を取り入れ、それを９ビットセグメントと７ビットセグメントとに分ける。ＦＩ関数は、同一の処理を有する２つの段を含んでおり、この２つの段の間にＸＯＲ２７６およびＸＯＲ２８６で識別されるＸＯＲステップを有している。留意すべきは、図２（ｃ）における濃い線は９ビットパスを識別するのに用いられ、薄い線は７ビットパスを識別するのに用いられていることである。
【００２９】
第１段において、９ビット入力セグメントは、以下でさらに詳しく述べるように、処理のために関数Ｓ９・２６８に供給される。７ビット入力セグメントは、ゼロ拡張され、ＸＯＲ２７０においてＳ９・２６８の出力と排他的論理和をとられる。また、７ビット入力セグメントは、以下でさらに詳しく述べるように、処理のために関数Ｓ７・２７２に供給される。ＸＯＲ２７０の９ビット出力は、７ビットに切り捨てられ、ＸＯＲ２７４においてＳ７・２７２の出力と排他的論理和をとられる。
【００３０】
ＸＯＲ２７６において、ＸＯＲ２７４の出力は、サブ鍵ＫＩｉ，ｊ，１とビットワイズ排他的論理和をとられる。ＫＩｉ，ｊ，１はＫＩｉ，ｊの７ビットサブ鍵であり、ここでｉはラウンド番号を示し、ｊはＦＩ関数が呼び出されるＦＯ段番号を示し、１はそれがＫＩｉ，ｊの１番目のサブ鍵であることを示す。ＸＯＲ２８６において、ＸＯＲ２７０の出力は、９ビットサブ鍵ＫＩｉ，ｊ，２とビットワイズ排他的論理和をとられる。ＫＩｉ，ｊ，２は、ＫＩｉ，ｊの２番目のサブ鍵である。
【００３１】
ＸＯＲ２７６の出力とＸＯＲ２８６の出力は、関数Ｆ１の第２段への入力となる。ＸＯＲ２８６の９ビット出力は、処理のために関数Ｓ９・２７８に供給される。ＸＯＲ２７６の７ビット出力は、ゼロ拡張され、ＸＯＲ２８０においてＳ９・２７８の出力と排他的論理和をとられる。また、ＸＯＲ２７６の出力は関数Ｓ７・２８２に供給される。ＸＯＲ２８０の９ビット出力は、７ビットに切り捨てられ、ＸＯＲ２８４においてＳ７・２８２の出力と排他的論理和をとられる。ＸＯＲ２８４の７ビット出力は、ＸＯＲ２８０の９ビット出力と連結され、ＦＩと記される１６ビット出力を形成する。
【００３２】
関数Ｓ７は、ＫＡＳＵＭＩ仕様で規定される。これは、７ビット入力を取り入れ、７ビット出力を返す。以下の式１−７は、ｙ０からｙ６までの各出力ビットを、ｘ０からｘ６までの７つの入力ビットの関数として定義する。ｘ１ｘ３のような２つのオペランドの連結は、オペランドの論理積（すなわち、ｘ１ ＡＮＤ ｘ３）を示す。記号
【数１】
【００３３】
は、排他的論理和関数を表わす。
【数２】
【００３４】
関数Ｓ９は、ＫＡＳＵＭＩ仕様で規定される。これは、９ビット入力を取り入れ、９ビット出力を返す。以下の式８−１６は、ｙ０からｙ８までの各出力ビットを、ｘ０からｘ８までの９つの入力ビットの関数として定義する。ｘ０ｘ２のような２つのオペランドの連結は、オペランドの論理積（すなわち、ｘ０ ＡＮＤ ｘ２）を示す。記号
【数３】
【００３５】
は、排他的論理和関数を表わす。
【数４】
【００３６】
図２（ｄ）は、図２（ａ）について上述したＦＬ関数を図示している。３２ビット入力は、２つの１６ビットセグメントである左セグメントと右セグメントに分割される。左入力セグメントは、記号∩で表わされるＡＮＤゲート２８８において、ＫＬｉ，１と、ビットワイズ論理積をとられる。ＡＮＤゲート２８８の出力は、記号＜＜＜で表わされるローテータ２９０において、１ビット分左に巡回される。ローテータ２９０の出力は、ＸＯＲ２９２において右入力セグメントとビットワイズ排他的論理和をとられる。ＸＯＲ２９２の出力は、記号∪で表わされるＯＲゲート２９８において、ビットワイズ論理和をとられる。ＯＲゲート２９８の出力は、ローテータ２９６において１ビット分左に巡回される。ローテータ２９６の出力は、ＸＯＲ２９４において左入力セグメントとビットワイズ排他的論理和をとられる。ＦＬで表わされる３２ビット出力は、ＸＯＲ２９４の出力とＸＯＲ２９２の出力とを連結することにより形成される。
【００３７】
ＫＡＳＵＭＩアルゴリズムは、いま述べたように、所望の結果を生成するために８つの計算ラウンドを必要とする。一実施形態において、単一のラウンドのためのハードウェアが配備され、８ラウンドのＫＡＳＵＭＩ出力を生成するために適切なフィードバックとともに再使用される。図３は、そのような例示的な実施形態を図示している。「例示的」という言葉は、ここでは専ら「一例、具体例、または例証となる」ことを意味するよう用いる。本明細書中で「例示的」に述べられたどの実施形態も、必ずしも他の実施形態よりも好ましくあるいは有利であるとして解釈すべきものではない。
【００３８】
図３はＫＡＳＵＭＩ３００を図示しており、これはサブ鍵生成器３１０、ＫＡＳＵＭＩラウンド３３０、およびＫＡＳＵＭＩ計算制御器３２０を備えている。ＫＡＳＵＭＩラウンド３３０は、サブ鍵生成器３１０からサブ鍵を受け入れる。ＫＬｉ，１とＫＬｉ，２は、直接接続され、ＫＯｉ，ｊおよびＫＩｉ，ｊは、それぞれｍｕｘ３４０および３５０を介して供給される。ｍｕｘ３４０は、サブ鍵生成器３１０からＫＯｉ，１，ＫＯｉ，２、およびＫＯｉ，３を受け入れる。ｍｕｘ３５０は、サブ鍵生成器３１０からＫＩｉ，１，ＫＩｉ，２、およびＫＩｉ，３を受け入れる。ｍｕｘ３４０およびｍｕｘ３５０からそれぞれＫＡＳＵＭＩラウンド３３０に供給されるべきサブ鍵のセット、ＫＯｉ，ｊおよびＫＩｉ，ｊは、ＫＡＳＵＭＩ計算制御器３２０からの制御信号、ｓｕｂｋｅｙ＿ｓｅｌｅｃｔによって決定される。全てのサブ鍵は、サブ鍵生成器３１０において、Ｋと記された１２８ビットの長さの鍵入力から生成される。またサブ鍵生成器３１０は、ＫＡＳＵＭＩ計算制御器３２０からロード信号と巡回信号を受信する。サブ鍵生成については、以下でより十分に詳述する。
【００３９】
ＫＡＳＵＭＩ計算制御器３２０は、リセット信号と開始信号を入力として受け取る。ＫＡＳＵＭＩ計算制御器３２０は、ＫＡＳＵＭＩ出力が生成されたことを示す終了信号を生成する。そのような完了を示す信号は、任意である。他の実施形態では、完了時間がシステムの特性に基づいて分かっている場合に、そのような信号を除くことができる。例示的な実施形態における開始信号は、開始信号がストローブされたときに鍵Ｋおよび６４ビット入力が有効となるように同期をとられる。ＫＡＳＵＭＩラウンド３３０の動作を制御するために、様々な信号が図３に示されている。ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗ、ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔ、およびｋａｓｕｍｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎが、ＫＡＳＵＭＩラウンド３３０内でラウンドレベルの機能を制御するために用いられる。ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔとｆｏ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎは、ＫＡＳＵＭＩラウンド３３０内でＦＯ関数を制御するために用いられる。ｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔとｆｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎは、ＫＡＳＵＭＩラウンド３３０内でＦＩ関数を制御するために用いられる。例示的な実施形態では、ＦＩ関数を制御するのに１つの制御信号のみが必要とされるので、これら最後の２つの信号は同一になっている。これらの信号のサブセットは、様々な実施形態がどのように配備されるかによって必要となることがある。メモリとフィードバック回路を制御するための様々なシグナリング方式は技術的に知られており、本発明の範囲内である。必要とされる制御の詳細な説明は、以下に提供されている。
【００４０】
ＫＡＳＵＭＩラウンド３３０は、いま述べた制御信号とサブ鍵に加えて、６４ビット出力を生成する６４ビット入力を受け入れる（その計算は、図２（ａ）−２（ｄ）を基に詳しく述べた）。
【００４１】
図４はＫＡＳＵＭＩラウンド４００を図示しており、これはいま述べたＫＡＳＵＭＩラウンド３３０の例示的な実施形態である。ＫＡＳＵＭＩラウンド４００において、６４ビット入力ｉｎは、上半分（６３：３２）と下半分（３１：０）の２つの３２ビットセグメントに分割される。上半分は、ｍｕｘ４０５の入力に接続される。下半分は、ｍｕｘ４１０の入力に接続される。２つのレジスタ４４５および４５０は、ｋａｓｕｍｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎがアサートにされた場合に、ＫＡＳＵＭＩラウンド４００内で演算された結果をラッチし、レジスタ４４５の出力とレジスタ４５０の出力は、６４ビット出力ｏｕｔを生成するために連結される。それに加えて、レジスタ４４５の出力はｍｕｘ４１０の入力としてフィードバックされ、レジスタ４５０の出力はｍｕｘ４０５の入力としてフィードバックされる。ｍｕｘ４０５および４１０はｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔにより制御され、これは、アサートにされない場合にｉｎが選択され、アサートにされる場合にフィードバック結果が選択されるようにする。ｍｕｘ４０５および４１０は、入力とレジスタ４４５および４５０により形成されるメモリの内容との間で選択を行うセレクタとして共に動作する。このようにＫＡＳＵＭＩラウンド４００は、ｉｎが選択された場合に、最初のＫＡＳＵＭＩのラウンドを実行し、前のラウンドの結果がフィードバックされた場合に、後に続くＫＡＳＵＭＩのラウンドを実行するのに利用することができる。
【００４２】
図２（ａ）−２（ｄ）に関して上述したように、ＫＡＳＵＭＩラウンドの処理の核心は、ＦＬ関数４２５、ＦＯ関数４３０、およびＸＯＲ４４０において実行される。しかしながら、上述したように、関数はそれぞれ各ラウンドで使われるので、処理順序はラウンドによって異なる。３つのｍｕｘ４１５、４２０、および４３５は、後に続くＫＡＳＵＭＩの各ラウンドにおいて構成要素を再使用するのに必要な切り換えを提供する。ＦＬ関数４２５、ＦＯ関数４３０、ＸＯＲ４４０と、ｍｕｘ４１５、４２０、および４３５とは、共に部分的なラウンド計算部の一実施形態を形成する。ｍｕｘ４０５の出力から供給されるｍｕｘ４１５への入力からなり、ＸＯＲ４４０の出力に連結される部分的なラウンド計算部の出力は、レジスタ４４５および４５０により形成されたメモリ内に格納される。部分的なラウンド計算部への入力は、ｍｕｘ４０５および４１０により形成されたセレクタの出力から発せられる。いま述べたセレクタ、部分的なラウンド計算部、およびメモリの多くの回路実装は、当業者にとって容易に明らかとなる。これらの実施形態は、どれも本発明の範囲内である。
【００４３】
３つのｍｕｘ４１５、４２０、および４３５は、偶数および奇数ラウンド計算用のＫＡＳＵＭＩラウンドを構成するためのデータフローセレクタを構成する。それらは、全てセレクタ信号ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗにより制御される。ｍｕｘ４１５は、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗがアサートにされた場合にｍｕｘ４０５の出力を選択し、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗが非アサートにされた場合に関数ＦＯ４３０のフィードバック出力を選択する。ｍｕｘ４２０は、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗが非アサートにされた場合にレジスタ４４５の出力を選択し、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗがアサートにされた場合に関数ＦＬ４２５のフィードバック出力を選択する。ｍｕｘ４１５の出力は関数ＦＬ４２５に供給され、関数ＦＬ４２５の出力はｍｕｘ４３５に供給される。ｍｕｘ４２０の出力は、関数ＦＯ４３０に供給され、関数ＦＯ４３０の出力もｍｕｘ４３５に供給される。ｍｕｘ４３５は、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗが非アサートにされた場合に関数ＦＬ４２５の出力を選択し、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗがアサートにされた場合に関数ＦＯ４３０の出力を選択する。ｍｕｘ４３５の出力は、ｉｎ入力としてビットワイズＸＯＲ４４０に供給される。ビットワイズＸＯＲ４４０の他方の入力は、ｍｕｘ４１０の出力である。上述したレジスタ４５０への入力は、ＸＯＲ４４０の出力である。上述したレジスタ４４５への入力は、ｍｕｘ４０５の出力である。当業者は、制御信号ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔ、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗ、およびｋａｓｕｍｉ＿ｏｕｔｏｕｔ＿ｒｅｇ＿ｅｎの適切な操作を結びつけた図４に図示する構成を、図２（ａ）について上述した所望のＫＡＳＵＭＩ計算を実行するのに用いることができることを認識できる。本実施形態のための制御シグナリングについては、以下でさらに詳しく述べる。
【００４４】
図５は、図４について上述した関数ＦＬ４２５として用いるのに適したＦＬ関数５００の実施形態を図示している。ＦＬ関数５００は、３２ビット入力ｉｎを受け入れ、３２ビット出力ｏｕｔを生成する。ｉｎの上半分（ビット３１から１６まで）は、ＡＮＤゲート５１０においてサブ鍵ＫＬｉ，１とビットワイズ論理積をとられる。ＡＮＤゲート５１０の出力は、ローテータ５２０において１ビット左に巡回される。ローテータ５２０の出力は、ＸＯＲ５３０において入力の下半分（ビット１５から０まで）とビットワイズ排他的論理和をとられる。ＸＯＲ５３０の結果は、ＯＲゲート５４０においてサブ鍵ＫＬｉ，２とビットワイズ論理和をとられる。ＯＲゲート５４０の出力は、ローテータ５５０において１ビット左に巡回される。ローテータ５５０の出力は、ＸＯＲ５６０において入力の上半分とビットワイズ排他的論理和をとられる。ＸＯＲ５６０の出力は、３２ビット出力ｏｕｔを生成するためにＸＯＲ５３０の出力と連結される。
【００４５】
図６は、図４について上述した関数ＦＯ４３０として用いるのに適したＦＯ関数６００の実施形態を図示している。ＦＯ関数６００は、３２ビット入力ｉｎを受け入れ、３２ビット出力ｏｕｔを生成する。本実施形態では、上述した３つのＦＯ段のうちの１つのための構成要素が配備されている。レジスタと適切なフィードバックにより、単一の段を連続して３回用いて、ＦＯ出力を生成することができるようになる。
【００４６】
２つのレジスタ６６０および６７０は、ｆｏ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎがアサートにされた場合に、中間計算値を格納する。レジスタ６６０の出力は、ｍｕｘ６２０の入力として供給される。レジスタ６７０の出力は、ｍｕｘ６１０の入力として供給される。入力ｉｎの上半分は、ｍｕｘ６１０への他方の入力となる。入力ｉｎの下半分は、ｍｕｘ６２０への他方の入力となる。信号ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔは、ｍｕｘ６１０および６２０に、それぞれ入力ｉｎとレジスタ６６０および６７０からのフィードバック値との間で選択を行うよう指示する。ｍｕｘ６１０の出力は、ＸＯＲ６３０においてサブ鍵ＫＯｉ，ｊとビットワイズ排他的論理和をとられる。ＸＯＲ６３０の出力は、関数ＦＩ６４０に供給され、以下でさらに詳しく述べるように、サブ鍵ＫＯｉ，ｊとともに処理される。関数ＦＩ６４０の出力は、ＸＯＲ６５０においてｍｕｘ６２０の出力とビットワイズ排他的論理和をとられる。ＸＯＲ６５０の出力は、上述したように、レジスタ６６０への入力として供給される。ｍｕｘ６２０の出力は、上述したように、入力としてレジスタ６７０に供給される。ｍｕｘ６２０の出力は、３２ビット出力ｏｕｔを形成するためにＸＯＲ６５０の出力と連結される。
【００４７】
レジスタ６６０とレジスタ６７０はメモリを形成する。ｍｕｘ６１０とｍｕｘ６２０はセレクタを形成する。ＸＯＲ６３０、ＦＩ関数６４０、およびＸＯＲ６５０は、部分的なＦＯ計算部を形成する。セレクタは、入力を部分的なＦＯ計算部へ供給するために、入力とメモリ結果との間で選択を行う。部分的なＦＯ計算部の出力は、メモリに格納される。いま述べたセレクタ、部分的なＦＯ計算部、およびメモリの多くの回路実装は、当業者にとって容易に明らかとなる。これらの実施形態は、どれも本発明の範囲内である。
【００４８】
図７は、図６について上述した関数ＦＩ６４０として用いるのに適したＦＩ関数７００の実施形態を図示している。ＦＩ関数７００は、１６ビット入力ｉｎを受け入れ、１６ビット出力ｏｕｔを生成する。本実施形態では、上述した２つのＦＩ段のうちの１つのための構成要素が配備されている。レジスタと適切なフィードバックにより、単一の段を連続して２回用いて、ＦＩ出力を生成することができるようになる。
【００４９】
２つのレジスタ７４５および７５０は、ｆｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎがアサートにされた場合に、中間計算値を格納するのに用いられる。９ビットレジスタ７４５の出力は、入力としてｍｕｘ７０５に供給される。７ビットレジスタ７５０の出力は、入力としてｍｕｘ７１０に供給される。入力ｉｎの上位９ビットは、ｍｕｘ７０５への他方の入力となる。入力ｉｎの下位７ビットは、ｍｕｘ７１０への他方の入力となる。信号ｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔは、ｍｕｘ７０５および７１０に、それぞれ入力ｉｎとレジスタ７４５および７５０からのフィードバック値との間で選択を行うよう指示する。ｍｕｘ７０５の出力は、上述したように関数Ｓ９・７１５における処理のために供給される。関数Ｓ９・７１５の出力は、ＸＯＲ７２０においてｍｕｘ７１０のゼロ拡張出力とビットワイズ排他的論理和をとられる。またｍｕｘ７１０の出力は、関数Ｓ７・７２５における処理のために供給される。関数Ｓ７・７２５の出力は、ＸＯＲ７３０において、ＸＯＲ７２０の切り捨てられた出力とビットワイズ排他的論理和をとられる。ＸＯＲ７２０の出力は、ＸＯＲ７３５においてサブ鍵ＫＩｉ，ｊ，２とビットワイズ排他的論理和をとられる。ＸＯＲ７３０の出力は、ＸＯＲ７４０においてサブ鍵ＫＩｉ，ｊ，１とビットワイズ排他的論理和をとられる。ＸＯＲ７３５の出力は、上述したように、入力としてレジスタ７４５に供給される。ＸＯＲ７４０の出力は、上述したように、入力としてレジスタ７５０に供給される。ＸＯＲ７３０の出力は、１６ビット出力ｏｕｔを生成するためにＸＯＲ７２０の出力と連結される。
【００５０】
本実施形態において留意すべきは、信号ｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔと信号ｆｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎは同一であり、これにより、共通の信号をｍｕｘ７０５、ｍｕｘ７１０、レジスタ７４５、およびレジスタ７５０の間で共用できることである。他の実施形態において、各ＦＩ処理サイクルがクロック制御レジスタ７４５および７５０の１つのサイクルに相当する場合は、これらのレジスタでイネーブル信号は必要ない。レジスタは、ＸＯＲ７３５とＸＯＲ７４０の結果を、それらがＦＩの後半の計算に用いられる１サイクル分遅らせるだけである。これらのような様々な技術は用いることができ、技術的に周知である。
【００５１】
レジスタ７４５とレジスタ７５０はメモリを形成する。ｍｕｘ７０５とｍｕｘ７１０はセレクタを形成する。関数Ｓ９・７１５、ＸＯＲ７２０、関数Ｓ７・７２５、ならびに、ＸＯＲ７３０、７３５、および７４０は、部分的なＦＩ計算部を形成する。セレクタは、入力を部分的なＦＩ計算部へ供給するために、入力とメモリ結果との間で選択を行う。部分的なＦＩ計算部の出力である中間値は、メモリに格納される。それに加えて、ＸＯＲ７２０およびＸＯＲ７３０の出力はＦＩ出力にもなる。いま述べたセレクタ、部分的なＦＩ計算部、およびメモリの多くの回路実装は、当業者にとって容易に明らかとなる。これらの実施形態は、どれも本発明の範囲内である。
【００５２】
図８は、サブ鍵生成器８００を図示している。サブ鍵生成器８００は、１２８ビット鍵Ｋを受け入れ、ロード信号および巡回信号と共に上述した様々なサブ鍵を生成する。サブ鍵生成器８００は、２つの１２８ビットシフトレジスタ８１０および８２０を含む。これらは、どちらもロード信号がアサートにされた場合に並列ロード可能であり、巡回信号がアサートにされた場合に８ビット左巡回を実行する。ロード信号は、ＫＡＳＵＭＩ計算の初めに１度アサートにされる。巡回信号は、各ラウンドが完了した後に、次のラウンド用の新しいサブ鍵を作成するためにイネーブルになる。これらの制御信号の他の制御信号との関連についての説明は、より詳しく以下で述べる。
【００５３】
留意すべきは、これらの巡回可能シフトレジスタを実施する多くの方法は、当業者にとって容易に明らかとなることである。例えば、シフトアウトされたビットを入力として第１段にフィードバックすることにより、シフトレジスタを巡回シストレジスタにすることができる。そのような巡回シストレジスタは、８ビット左巡回を生成するために８回シフトすることができる。あるいは、各シフトが各ビットを８桁分巡回（すなわち、バイトワイズ左巡回）するように、シフトレジスタを配線することができる。この代替は、８つのインターリーブ１６ビットシフトレジスタを実施することに相当し、それらの出力がそれらの各入力にフィードバックされるよう構成される。
【００５４】
シフトレジスタ８２０は、Ｋ１からＫ８まで名付けられた８つの１６ビットのセクションから成る。Ｋ（１２７：１１２）はＫ１用のロード入力となる。Ｋ（１１１：９６）はＫ２用のロード入力となる。Ｋ（９５：８０）はＫ３用のロード入力となる。Ｋ（７９：６４）はＫ４用のロード入力となる。Ｋ（６３：４８）はＫ５用のロード入力となる。Ｋ（４７：３２）はＫ６用のロード入力となる。Ｋ（３１：１６）はＫ７用のロード入力となる。Ｋ（１５：０）はＫ８用のロード入力となる。
【００５５】
シフトレジスタ８１０は、Ｋ１’からＫ８’まで名付けられた８つの１６ビットのセクションから成る。シフトレジスタ８１０用のロード入力は、Ｋの様々なセグメントと、ＫＡＳＵＭＩ仕様で規定される定数Ｃ１からＣ８までとのビットワイズ排他的論理和をとることにより形成される。表１は、これら定数の値を提供している。
【表１】
【００５６】
Ｋ１’へのロード入力は、ＸＯＲ８０１において、Ｋ（１２７：１１２）とＣ１とのビットワイズ排他的論理和をとることにより生成される。Ｋ２’へのロード入力は、ＸＯＲ８０２において、Ｋ（１１１：９６）とＣ２とのビットワイズ排他的論理和をとることにより生成される。Ｋ３’へのロード入力は、ＸＯＲ８０３において、Ｋ（９５：８０）とＣ３とのビットワイズ排他的論理和をとることにより生成される。Ｋ４’へのロード入力は、ＸＯＲ８０４において、Ｋ（７９：６４）とＣ４とのビットワイズ排他的論理和をとることにより生成される。Ｋ５’へのロード入力は、ＸＯＲ８０５において、Ｋ（６３：４８）とＣ５とのビットワイズ排他的論理和をとることにより生成される。Ｋ６’へのロード入力は、ＸＯＲ８０６において、Ｋ（４７：３２）とＣ６とのビットワイズ排他的論理和をとることにより生成される。Ｋ７’へのロード入力は、ＸＯＲ８０７において、Ｋ（３１：１６）とＣ７とのビットワイズ排他的論理和をとることにより生成される。Ｋ８’へのロード入力は、ＸＯＲ８０８において、Ｋ（１５：０）とＣ８とのビットワイズ排他的論理和をとることにより生成される。当然ながら、各ＸＯＲ８０１−８０８は、オペランドの１つとして定数を有するので、１２８ＸＯＲの各々は、対応する定数が「０」の場合に配線と交換することができ、対応する定数が「１」の場合にインバータと交換することができる。
【００５７】
いくつかのサブ鍵は、シフトレジスタ８１０から直接引き出される。ＫＬｉ，２はＫ３’から引き出される。ＫＩｉ，２はＫ４’から引き出される。ＫＩｉ，１はＫ５’から引き出される。ＫＩｉ，３はＫ８’から引き出される。他のサブ鍵は、シフトレジスタ８２０の様々なセグメントを巡回することにより生成される。ＫＬｉ，１は、ローテータ８３０においてＫ１を１ビット分左に巡回することにより生成される。ＫＯｉ，１は、ローテータ８４０においてＫ２を５ビット分左に巡回することにより生成される。ＫＯｉ，２は、ローテータ８５０においてＫ６を８ビット分左に巡回することにより生成される。ＫＯｉ，３は、ローテータ８６０においてＫ７を１３ビット分左に巡回することにより生成される。留意すべきは、これらローテータの各々は定数値分巡回するので、各巡回は簡単なワイヤ・マッピングによって達成できることである。当業者は、そのようなワイヤ・マッピングがどのように実施されるべきかを認識でき、巡回のための様々な他の技術も認識できる。
【００５８】
図９は、ＫＡＳＵＭＩの一実施形態において実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。これらのステップは、図４について述べたＫＡＳＵＭＩラウンド４００のような実施形態に適用することもできる。
【００５９】
開始９０２で処理が始まり、ブロック９０４に進む。ブロック９０４において、ｉは１に設定され、ここでｉはラウンド番号を表わす。ＫＡＳＵＭＩラウンドの入力は、これがラウンド１であるので、ラウンドを演算するために選択される。これは、図４に示したように、ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック判定ブロック９０６に進むと、ここで、ｉで表わされた現時のラウンドが偶数または奇数であることを決定するために試験が実行される。ｉが奇数、すなわち１、３、５、または７である場合はブロック９０８に進む。ｉが偶数、すなわち２、４、６、または８である場合はブロック９１０に進む。
【００６０】
ブロック９０８において、ＫＡＳＵＭＩラウンドのデータフローは、（ラウンド１において）入力または（ラウンド３、５および７において）フィードバックから、ＦＬ関数へ、ＦＯ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを１に設定することに相当する。
【００６１】
ブロック９１０において、ＫＡＳＵＭＩラウンドのデータフローは、フィードバックから、ＦＯ関数へ、ＦＬ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを０に設定することに相当する。
【００６２】
ブロック９０８またはブロック９１０から、ＫＡＳＵＭＩラウンドを演算するためにブロック９１２に進む。ＫＡＳＵＭＩラウンドを演算するための一実施形態は図４において詳細に示したが、ＫＡＳＵＭＩラウンドを演算するためのどの方法も、図９のフローチャートの範囲内である。一度ＫＡＳＵＭＩラウンドが演算されると、その結果はラッチ結果ブロック９１４において格納される。これは、図４に示すｋａｓｕｍｉ＿ｒｅｇ＿ｅｎ信号をアサートにすることに相当する。判定ブロック９１６に進む。
【００６３】
判定ブロック９１６において、ｉが８に等しければ、８番目である最後のラウンドが実行されており、処理はＫＡＳＵＭＩ終了ブロック９２２において完了する。図３に示すような終了信号を用いる実施形態において、その信号はこの時点でアサートにすることができる。ｉが８未満の場合、実行されるべき付加的なラウンドがあり、それによりｉはブロック９１８において１だけ増加される。ブロック９２０に進み、ここで、次のラウンドを演算するために、ブロック９１４のラッチされた結果からのフィードバックが選択される。これは、図４においてｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。判定ブロック９０６にループバックし、次のラウンドを実行する。ＫＡＳＵＭＩ終了ブロック９２２に達するまで、ステップを繰り返す。
【００６４】
図１０は、ＦＯ関数の一実施形態において実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。これらのステップは、図６について述べたＦＯ関数６００のような実施形態に適用することもできる。
【００６５】
開始１００２で処理が始まり、ブロック１００４に進む。ブロック１００４において、ｊは１に設定され、ここでｊは段番号を表わす。ＦＯ関数の入力は、これが段１であるので、演算をするために選択される。これは、図６に示したように、ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。さらに、段番号ｊは、図３に示した信号ｓｕｂｋｅｙ＿ｓｅｌｅｃｔに関連する。（いくつかの実施形態では、ｓｕｂｋｅｙ＿ｓｅｌｅｃｔ値０、１、および２は、ｊの値１、２、および３に相当する。あるいは、ｊの値と同一のｓｕｂｋｅｙ＿ｓｅｌｅｃｔ値１、２、および３に基づいて選択を行う３つの入力ｍｕｘを配備することができる。）
ブロック１００６に進み、ここでＦＯ関数の１／３が演算される。ＦＯ関数の１／３を演算できる一実施形態が図６に図示されているが、他も図１０のフローチャートの範囲内である。１／３計算の結果は、ラッチ結果ブロック１００８において格納される。これは、図６においてｆｏ＿ｏｕｔｐｕｔ＿ｅｎをアサートにすることに相当する。次に判定ブロック１０１０に進み、ｊが３に等しいか試験を行う。もしそうなら、次にＦＯ完了ブロック１０１６に進み、ＦＯ関数は完了される。ｊが３未満の場合、さらなる段がまだ完了されていない。ブロック１０１２に進み、ｊを１だけ増加する。次にブロック１０１４に進み、ここで、ブロック１００８においてラッチされた結果であるフィードバックが、ＦＯ関数への入力として選択される。これは、図６においてｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１００６にループバックし、次の段を計算し、全ての段が完了するまで処理を繰り返す。
【００６６】
図１１は、ＦＩ関数の一実施形態において実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。これらのステップは、図７について述べたＦＩ関数７００のような実施形態に適用することもできる。
【００６７】
開始１１０２で処理が始まり、ブロック１１０４に進む。ブロック１１０４において、入力が演算のために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。ブロック１１０６に進み、ここでＦＩ関数の１／２が演算される。ブロック１１０８に進み、ブロック１１０６において計算されたＦＩの前半の結果をラッチする。ブロック１１１０に進み、ここでフィードバックが演算のために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１１１２に進み、ここでＦＩの後半が演算される。ブロック１１１４に進み、ＦＩ演算は完了する。
【００６８】
図１２は、図８について上述したもののようなサブ鍵生成器の実施形態を制御するために実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。
【００６９】
開始１２０２で処理が始まり、ブロック１２０４に進む。ブロック１２０４において、ｉは１に設定され、ここでｉはラウンド番号を表わす。サブ鍵シフトレジスタがロードされる。例えば、図３におけるロード信号は、図８に示すサブ鍵生成器８００に接続することができる。ロード信号がアサートにされると、サブ鍵生成器８００は２つのシフトレジスタ８１０および８２０をロードする。ブロック１２０６に進み、使用されるべき現時のサブ鍵のセットを待ち、それは一般に１つのＫＡＳＵＭＩラウンドが生じるのに必要な時間となる。この時間の間、ラウンド１に対応するサブ鍵の１セットが有効になる。判定ブロック１２０８に進む。
【００７０】
判定ブロック１２０８において、ｉが８に等しければ、８番目である最後のＫＡＳＵＭＩラウンドが実行されており、処理は終了ブロック１２１４において完了する。他のＫＡＳＵＭＩ演算が必要な場合は、開始１２０２に戻る。ｉが８未満の場合、新しいサブ鍵のセットを必要とする付加的なラウンドがある。ブロック１２１０に進み、サブ鍵シフトレジスタを巡回する。これは、図３において巡回信号をアサートにすることに相当し、図８について上述したように、シフトレジスタ８１０および８２０において８ビット左巡回を引き起こす。ブロック１２１２に進み、ｉを１だけ増加する。ブロック１２０６にループバックし、他のＫＡＳＵＭＩラウンドのためにサブ鍵を供給する。終了ブロック１２１４に到達するまでステップを繰り返す。
【００７１】
図１３は、図３−８と上述した図９−１２におけるフローチャートとについて述べた技術を組み込んだＫＡＳＵＭＩを実行するステップを図示しているフローチャートである。図１３のステップを用いる例示的な実施形態は、上述した図３におけるＫＡＳＵＭＩ３００である。例示的なＫＡＳＵＭＩ３００は、サブ鍵生成器３１０およびＫＡＳＵＭＩラウンド３３０と共に、図１３において述べた制御ステップを実行するＫＡＳＵＭＩ計算制御器３２０を用いることができる。サブ鍵生成器３１０は、図８において述べたサブ鍵生成器８００のようなものとすることができる。ＫＡＳＵＭＩラウンド３３０は、図８において述べたＫＡＳＵＭＩラウンド４００のようなものとすることができる。ＫＡＳＵＭＩラウンド４００は、図５および図６でそれぞれ述べたＦＬ関数５００およびＦＯ関数６００を用いることができる。ＦＯ関数６００は、図７で述べたＦＩ関数７００を用いることができる。図１３のフローチャートは開始１３０２で始まり、ブロック１３０４に進む。
【００７２】
ブロック１３０４において、ｉは１に設定され、ここでｉはラウンド番号を表わす。ＫＡＳＵＭＩラウンドへの入力は、これがラウンド１であるので、ラウンドを演算するために選択される。これは、図４に示したように、ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。サブ鍵シフトレジスタがロードされる。例えば、図３におけるロード信号は、図８に示すサブ鍵生成器８００に接続することができる。ロード信号がアサートにされると、サブ鍵生成器８００は２つのシフトレジスタ８１０および８２０をロードする。
【００７３】
判定ブロック１３０６に進むと、ここで、ｉで表わされた現時のラウンドが偶数または奇数であることを決定するために試験が実行される。ｉが奇数、すなわち１、３、５、または７である場合はブロック１３０８に進む。ｉが偶数、すなわち２、４、６、または８である場合はブロック１３１０に進む。ブロック１３０８において、ＫＡＳＵＭＩラウンドのデータフローは、（ラウンド１において）入力または（ラウンド３、５および７において）フィードバックから、ＦＬ関数へ、ＦＯ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを１に設定することに相当する。ブロック１３１０において、ＫＡＳＵＭＩラウンドのデータフローは、フィードバックから、ＦＯ関数へ、ＦＬ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを０に設定することに相当する。
【００７４】
ブロック１３０８またはブロック１３１０から、ＫＡＳＵＭＩラウンドの演算を開始するためにブロック１３１２に進む。ＦＩ段およびＦＯ段のようなラウンドのサブ関数を最初に述べたが、当業者が理解するように、これらの方法ステップは本発明の範囲を逸脱することなく交換することができる。
【００７５】
ブロック１３１２において、ＦＯ関数が初期化される。ｊは１に設定され、ここでｊは段番号を表わす。ＦＯ関数の入力は、これがＦＯ段１であるので、ＦＯ関数を演算するために選択される。これは、図６に示したように、ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。さらに、段番号ｊは、図３に示した信号ｓｕｂｋｅｙ＿ｓｅｌｅｃｔに関連する。ｓｕｂｋｅｙ＿ｓｅｌｅｃｔとｊとの相関関係については、図１０について上記で詳しく述べた。ブロック１３１４に進み、ＦＩ関数を実行する。
【００７６】
ブロック１３１４において、入力がＦＩ関数を演算するために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。ブロック１３１６に進み、ここでＦＩ関数の１／２が演算される。ＦＩ関数の１／２を演算することができる一実施形態が図７に図示されているが、他も図１３のフローチャートの範囲内である。ブロック１３１８に進み、ブロック１３１６で計算されたＦＩの前半の結果をラッチする。ブロック１３２０に進み、ここでＦＩフィードバックがＦＩ関数を演算するために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１３２２に進み、ここでＦＩの後半が演算される。ブロック１３２４に進み、ＦＯ処理を続け、ＦＩ演算が完了する。
【００７７】
ブロック１３２４において、ＦＯ関数の１／３が演算される。ＦＯ関数の１／３を演算することができる一実施形態が図６に図示されているが、他も図１３のフローチャートの範囲内である。１／３計算の結果は、ラッチＦＯ結果ブロック１３２６において格納される。これは、図６においてｆｏ＿ｏｕｔｐｕｔ＿ｅｎをアサートにすることに相当する。次に判定ブロック１３２８に進み、ｊが３に等しいか試験を行う。もしそうなら、次にＦＯ処理が完了する。ブロック１３３４に進み、ＫＡＳＵＭＩ処理を続ける。ｊが３未満の場合、さらなる段がまだ完了していない。ブロック１３３０に進み、ｊを１だけ増加する。次にブロック１３３２に進み、ここで、ブロック１３２６においてラッチされたＦＯ結果であるフィードバックが、ＦＯ関数への入力として選択される。これは、図６においてｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１３１４にループバックし、次の段を計算し、全ての段が完了するまで処理を繰り返す。
【００７８】
ブロック１３３４において、ＫＡＳＵＭＩラウンドを演算する。ＫＡＳＵＭＩラウンドを演算するための一実施形態は図４において詳細に示したが、ＫＡＳＵＭＩラウンドを演算するためのどの方法も、図１３のフローチャートの範囲内である。ブロック１３３４で一度ＫＡＳＵＭＩラウンドが演算されると、その結果はラッチＫＡＳＵＭＩ結果ブロック１３３６において格納される。これは、図４に示すｋａｓｕｍｉ＿ｒｅｇ＿ｅｎ信号をアサートにすることに相当する。判定ブロック１３３８に進む。
【００７９】
判定ブロック１３３８において、ｉが８に等しければ、８番目である最後のラウンドが実行されており、処理はＫＡＳＵＭＩ終了ブロック１３４６において完了する。図３に示すような終了信号を用いる実施形態において、その信号はこの時点でアサートにすることができる。ｉが８未満の場合、実行されるべき付加的なラウンドがあり、それによりｉはブロック１３４０において１だけ増加される。ブロック１３４２に進み、ここで、次のラウンドを演算するために、ブロック１３３６のラッチされた結果であるフィードバックが選択される。これは、図４においてｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。次のラウンドでは新しいサブ鍵のセットを必要とし、そのためサブ鍵シフトレジスタを巡回するためにブロック１３４４に進む。これは、図３において巡回信号をアサートにすることに相当し、図８について上述したように、シフトレジスタ８１０および８２０において８ビット左巡回を引き起こす。判定ブロック１３０６にループバックし、次のラウンドを実行する。ＫＡＳＵＭＩ終了ブロック１３４６に到達するまで、ステップを繰り返す。
【００８０】
上述した全ての実施形態において、方法ステップは本発明の範囲を逸脱することなく交換することができることに留意すべきである。
【００８１】
当業者は、任意の様々な各種テクノロジーと技術を用いて情報および信号を表わせることを理解する。例えば、上記説明を通じて参照することができるデータ、指示、コマンド、情報、信号、ビット、記号、およびチップは、電圧、電流、電磁波、磁界または磁性粒子、光場または光粒子、あるいはそれらの組み合わせにより表わすことができる。
【００８２】
さらに当業者には、本明細書中で開示した実施形態に関連して述べられた様々な実例となる論理ブロック、モジュール、回路、およびアルゴリズムステップを、電子ハードウェア、コンピュータソフトウェア、または両方の組み合わせとして実施できることが分かる。このハードウェアおよびソフトウェアの互換性を明らかに示すために、様々な実例となる構成要素、ブロック、モジュール、回路、およびステップを、それらの機能性の点から広く述べた。そのような機能性がハードウェアとして実施されるか、またはソフトウェアとして実施されるかは、システム全体に課せられた特定の用途と設計制約による。熟練した当業者は、各特定用途のために、上述した機能性を様々に実施することができるが、そのような実施の決定は本発明の範囲からの逸脱をもたらすと解釈するべきではない。
【００８３】
本明細書中で開示した実施形態に関連して述べられた様々な実例となる論理ブロック、モジュール、および回路を、汎用プロセッサ、デジタル信号プロセッサ（ＤＡＰ）、特定用途向け集積回路（ＡＳＩＣ）、現場でプログラム可能なゲートアレイ（ＦＰＧＡ）または他のプログラム可能論理回路、ディスクリートゲートまたはトランジスタ論理、ディスクリートハードウェア部品、または本明細書中で述べた機能を実行するよう設計されたそれらの任意の組み合わせとともに実装または実行することができる。汎用プロセッサはマイクロプロセッサとすることができるが、別の方法では、プロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械とすることができる。またプロセッサを、演算装置の組み合わせ、例えばＤＳＰとマイクロプロセッサとの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアと連動する１つ以上のマイクロプロセッサ、あるいはそのような任意の他の構成として実施することができる。
【００８４】
本明細書中で開示した実施形態に関連して述べた方法のステップすなわちアルゴリズムは、ハードウェア、プロセッサにより実行されるソフトウェアモジュール、またはその２つの組み合わせに直接組み入れることができる。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取り外し可能ディスク、ＣＤ−ＲＯＭ、あるいは技術的に知られた他の任意の記憶媒体形態に常駐することができる。例示的な記憶媒体はプロセッサと結合され、そのようなプロセッサは記憶媒体から情報を読み出し、記憶媒体に情報を書き込むことができる。別の方法では、記憶媒体をプロセッサに一体化することができる。プロセッサと記憶媒体はＡＳＩＣ内に常駐することができる。ＡＳＩＣはユーザー端末内に常駐することができる。別の方法では、プロセッサと記憶媒体をディスクリート部品としてユーザー端末内に常駐することができる。
【００８５】
上記で開示された実施形態の説明は、任意の当業者が本発明を行い使用できるように提供されている。これらの実施形態の様々な変更は当業者にとって容易に明らかとなり、明細書中で規定された一般的な原理は、本発明の特質と範囲を逸脱することなく他の実施形態に適用することができる。したがって、本発明は明細書中で示された実施形態に限定されることなく、明細書中で開示された原理と新規な特徴に沿う最も広い範囲に適合することになる。
【図面の簡単な説明】
【００８６】
【図１】多数のユーザーをサポートできる無線通信システムを示す概略ブロック図。
【図２（ａ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図２（ｂ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図２（ｃ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図２（ｄ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図３】ＫＡＳＵＭＩを実行する実施形態の概略ブロック図。
【図４】ＫＡＳＵＭＩラウンドの実施形態のブロック図。
【図５】ＦＬ関数の実施形態のブロック図。
【図６】ＦＯ関数の実施形態のブロック図。
【図７】ＦＩ関数の実施形態のブロック図。
【図８】サブ鍵生成器のブロック図。
【図９】ＫＡＳＵＭＩの一実施形態のフローチャート。
【図１０】ＦＯ関数の一実施形態のフローチャート。
【図１１】ＦＩ関数の一実施形態のフローチャート。
【図１２】サブ鍵生成器の一実施形態のフローチャート。
【図１３】ＫＡＳＵＭＩの他の実施形態の制御フローを示す図
【分野】
【０００１】
本発明は、一般に通信に関し、特にＫＡＳＵＭＩ暗号化を行う新規で改善された方法および装置に関する。
【背景】
【０００２】
無線通信システムは、音声、データ、その他の様々なタイプの通信を提供するために広く配備されている。これらのシステムは、符号分割多元接続（ＣＤＭＡ）、時分割多元接続（ＴＤＭＡ）、または他のいくつかの変調技術に基づくことができる。ＣＤＭＡシステムは、他のタイプのシステムよりも確かな利点を提供し、増加したシステム容量を含んでいる。
【０００３】
ＣＤＭＡシステムは、(1)「デュアルモード広帯域拡散スペクトルセルラシステムのためのＴＩＡ／ＥＩＡ−９５−Ｂ移動局―基地局互換性規格」（ＩＳ−９５規格）、(2)「デュアルモード広帯域拡散スペクトルセルラ移動局のためのＴＩＡ／ＥＩＡ−９８−Ｃ勧告最低基準」（ＩＳ−９８規格）、(3)「第３世代提携事業」（３ＧＰＰ）という名の共同体により提案され、文献Ｎｏｓ．３Ｇ ＴＳ ２５．２１１、３Ｇ ＴＳ ２５．２１２、３Ｇ ＴＳ ２５．２１３、および３Ｇ ＴＳ ２５．２１４（Ｗ−ＣＤＭＡ規格）を含む文献のセットに具体化されている規格、(4)「第３世代提携事業２」（３ＧＰＰ２）という名の共同体により提案され、「ｃｄｍａ２０００拡散スペクトルシステムのためのＴＲ−４５．５物理レイヤ規格」、「ｃｄｍａ２０００拡散スペクトルシステムのためのＣ．Ｓ０００５−Ａ上位レイヤ（レイヤ３）信号法規格」、および「Ｃ．Ｓ００２４ ｃｄｍａ２０００高速パケットデータ空中インターフェース仕様」（ｃｄｍａ２０００規格）を含む文献のセットに具体化されている規格、および(5)他のいくつかの規格、といった１つ以上のＣＤＭＡ規格に対応するように設計することができる。ｃｄｍａ２０００規格の高速パケットデータ仕様を実施するシステムを、本明細書中では高速データレート（ＨＤＲ）システムと称す。ＨＤＲシステムは、ＴＩＡ／ＥＩＡ−ＩＳ−８５６、「ＣＤＭＡ２０００高速パケットデータ空中インターフェース仕様」に記録されている。また、提案された無線システムは、ＨＤＲと１つの空中インターフェースを使用する低速データレートサービス（例えば、音声サービスおよびファックスサービス）との組み合わせを提供する。
【０００４】
暗号化技術は、送信データの安全性を提供するため、およびデータにアクセスしようとするユーザーに認証を提供するために、通常使用される。暗号化技術は、様々な分野で使用され、特にデジタル無線通信システムに有用である。
【０００５】
Ｗ−ＣＤＭＡ規格用に指定された１つの暗号化アルゴリズムが、ＫＡＳＵＭＩである。ＫＡＳＵＭＩは、１９９９年１２月２３日付けのＥＴＳＩ／ＳＡＧＥ仕様書「３ＧＰＰ機密性および完全性アルゴリズムの仕様」バージョン１．０の「文書２：ＫＡＳＵＭＩ仕様」（以下、ＫＡＳＵＭＩ仕様）に詳述されている。ＫＡＳＵＭＩの様々な用途が、同じＥＴＳＩ／ＳＡＧＥ仕様書において、「文書１：ｆ８およびｆ９仕様」に詳述されている。ＫＡＳＵＭＩは、１２８ビット鍵を利用して６４ビット入力から６４ビット出力を生成するブロック暗号である。ＫＡＳＵＭＩの出力は、通常、鍵ストリームのビットと暗号化されるべきデータのビットとの排他的論理和（ＸＯＲ）をとることにより、暗号化データに対する鍵ストリームとして使用することができる。
【０００６】
通信システムのための技術では、その様々なサブ関数を実行するために、ＡＳＩＣまたは他のハードウェア解法を用いるのが一般的である。ＡＳＩＣ設計において、利用面積がより小さくなると、より低いコスト、より高い歩留まり、そして多くの場合はより低い電力につながる。低コストと低電力は、固定用途と移動用途の両方で有益であるが、低電力は、電池を利用する移動機器にとって特に重要である。同時に、処理はある制限時間内で完了しなければならない。Ｗ−ＣＤＭＡシステムのような無線データシステムは、それらの加入者と基地局にＫＡＳＵＭＩの実施を組み込む必要があり、設計者は、先に述べたことを含む様々な制約の中で作業する必要がある。このような事情により、ＫＡＳＵＭＩ暗号化を効果的に行う装置および方法の技術的な必要性がある。
【発明の開示】
【概要】
【０００７】
本明細書中で開示された実施形態は、効果的なＫＡＳＵＭＩ暗号化のための効果的な装置または方法の必要性に対処している。１つの観点において、ＫＡＳＵＭＩ暗号の断片部分を生成する１つのＫＡＳＵＭＩラウンドが、８つの連続したラウンドがＫＡＳＵＭＩ出力を生成するよう、適切なフィードバックをともなって配備される。他の観点において、３つの連続するサイクルがＦＯ出力を生成するよう、ＦＯ関数の１／３が適切なフィードバックをともなって配備される。さらに他の観点において、２つの後続するサイクルがＦＩ出力を生成するよう、ＦＩ関数が適切なフィードバックをともなって配備される。さらに他の観点において、２つのシフトレジスタを備えるサブ鍵生成器が、各ラウンドとそのサブ段用のサブ鍵を効果的に生成する。これらの観点は、簡単なユーザーインタフェースをともなうＫＡＳＵＭＩにおいて、小面積や低コストの実現といった高い利点の実現を総合的にもたらす。本発明の他の様々な観点も提示される。
【０００８】
本発明は、以下でさらに詳しく述べるように、本発明の様々な観点、実施形態、および特徴を実施する方法およびシステム要素を提供する。
【０００９】
本発明の特徴、性質、および利点は、以下に述べる詳細な説明を図面とともに参照することでより明らかになる。図面全体を通じて同じ参照符号により対応付けがなされている。
【詳細な説明】
【００１０】
図１は、多数のユーザーをサポートし、本発明の様々な観点を実施できる無線通信システム１００を示す図である。システム１００は、１つ以上のＣＤＭＡ規格および／または設計（例えば、ＩＳ−９５規格、ｃｄｍａ２０００規格、ＨＤＲ仕様、Ｗ−ＣＤＭＡ規格）をサポートするよう設計することができる。簡単にするために、システム１００は、２つのアクセス端末１０６（遠隔端末または移動局と呼ぶこともできる）と通信する３つのアクセスポイント１０４（基地局と呼ぶこともできる）を含むよう図示している。アクセスポイントとそのカバレッジ領域は、まとめて「セル」と呼ばれることが多い。ＫＡＳＵＭＩアルゴリズムは、１つ以上のアクセスポイント、１つ以上のアクセス端末、またはそれら両方に配備することができる。
【００１１】
実施中のＣＤＭＡシステムに応じて、各アクセス端末１０６は、任意の時点において、順方向リンク上で１つの（または場合によってはさらに多くの）アクセスポイント１０４と通信することができ、アクセス端末がソフトハンドオフにあるか否かに応じて、逆方向リンク上で１つ以上のアクセスポイントと通信することができる。順方向リンク（すなわち、ダウンリンク）は、アクセスポイントからアクセス端末への伝送を指しており、逆方向リンク（すなわちアップリンク）はアクセス端末からアクセスポイントへの伝送を指している。
【００１２】
図２（ａ）−２（ｄ）は、ＫＡＳＵＭＩ仕様に規定されているＫＡＳＵＭＩアルゴリズムを図示している。図２（ａ）は、ＫＡＳＵＭＩ２００の一番上のレベルの図を示している。図２（ｂ）は、ＦＯ関数を示している。図２（ｃ）は、ＦＩ関数を示している。図２（ｄ）は、ＦＬ関数を示している。
【００１３】
図２（ａ）に示すように、ＫＡＳＵＭＩは８つのラウンドからなる。各ラウンドは、１つのＦＬ関数、１つのＦＯ関数、および３２ビットＸＯＲ関数から成り立っている。ＦＬ関数はＦＬｉで表わされ、ここでｉはどのラウンドを表わすかを示し、１から８までである。同様に、ＦＯ関数はＦＯｉで表わされる。各ラウンドでは、ＫＬｉ、ＫＯｉ、およびＫＩｉで表わされる様々なサブ鍵を利用する。ＫＬｉは、ＫＬｉ，１およびＫＬｉ，２で表わされる２つの１６ビットサブ鍵からなる３２ビットサブ鍵である。ＫＯｉとＫＩｉは、４８ビットサブ鍵であり、それぞれＫＯｉ，１、ＫＯｉ，２およびＫＯｉ，３と、ＫＩｉ，１、ＫＩｉ，２およびＫＩｉ，３とで表わされる３つの１６ビットサブ鍵からなる。１６ビットサブ鍵の用途については、以下で図２（ｂ）−２（ｄ）を基にさらに詳しく述べる。
【００１４】
ラウンド１は、ＦＬ１・２０２、ＦＯ１・２０４、および３２ビットのビットワイズＸＯＲ２０６を備えている。６４ビット入力は２つの３２ビットセグメントに分けられ、これらを左セグメントおよび右セグメントとして述べる。右セグメントは、ＸＯＲ２０６においてＦＯ１・２０４の出力と排他的論理和をとられ、ラウンド１の右出力を生成する。各ラウンドの右出力は、後に続くラウンドへの左入力となる。したがって、ラウンド１の右出力は左入力としてラウンド２に供給される。左入力セグメントはＦＬ１・２０２に供給され、ここで、サブ鍵ＫＬ１を利用して、以下で述べるＦＬ関数に従って処理される。ＦＬ１・２０２の出力は、これも以下で述べるＦＯ関数に従ってＫＯ１およびＫＩ１とともに処理するために、ＦＯ１・２０４に供給される。いま述べたように、ＦＯ１・２０４の出力は、入力の右セグメントとビットワイズ排他的論理和をとるために、ＸＯＲ２０６に供給される。また左入力セグメントは、右入力としてラウンド２に供給される。一般に、各ラウンドの左入力は、そのラウンドにおいて様々な処理に使用され、後に続くラウンドへの右入力となる。
【００１５】
ラウンド２は、ＦＬ２・２０８、ＦＯ２・２１０、およびＸＯＲ２１２を備えている。ラウンド２は、関数ＦＯとＦＬの順序が逆になることを除いて、ラウンド１と同様である。一般に、奇数のラウンドはＦＯ関数に供給をするＦＬ関数を有し、偶数のラウンドはＦＬ関数に供給をするＦＯ関数を有する。ラウンド２への右入力は、ＸＯＲ２１２においてＦＬ２・２１０の出力と排他的論理和をとられ、ラウンド２の右出力を生成する。既に述べたように、ラウンド２の右出力は左入力としてラウンド３に供給される。左入力セグメントは、ＦＯ関数に従ってＫＯ２およびＫＩ２とともに処理するために、ＦＯ２・２０８に供給される。ＦＯ２・２０８の出力は、ＦＬ関数に従ってＫＩ２とともに処理するために、ＦＬ２・２１０に供給される。また左入力セグメントは、右入力としてラウンド３に供給される。
【００１６】
ラウンド３、５、および７は、当然ながら各ラウンドへの入力がＫＡＳＵＭＩ入力ではなく前のラウンドの出力によるものであることを除いて、ラウンド１と同様に構成されている。ラウンド４、６、および８は、ラウンド２と同様に構成されている。
【００１７】
ラウンド３において、ＸＯＲ２１２の出力は、ＦＬ関数に従ってＫＬ３とともに処理するために、ＦＬ３・２１４に供給される。ＦＬ３・２１４の出力は、ＦＯ関数に従ってＫＯ３およびＫＩ３とともに処理するために、ＦＯ３・２１６に供給される。ＦＯ３・２１６の出力は、ＸＯＲ２０６の出力とビットワイズ排他的論理和をとるために、ＸＯＲ・２１８に供給される。
【００１８】
ラウンド４において、ＸＯＲ２１８の出力は、ＦＯ関数に従ってＫＯ４およびＫＩ４とともに処理するために、ＦＯ４・２２０に供給される。ＦＯ４・２２０の出力は、ＦＬ関数に従ってＫＬ４とともに処理するために、ＦＬ４・２２２に供給される。ＦＬ４・２２２の出力は、ＸＯＲ２１２の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２２４に供給される。
【００１９】
ラウンド５において、ＸＯＲ２２４の出力は、ＦＬ関数に従ってＫＬ５とともに処理するために、ＦＬ５・２２６に供給される。ＦＬ５・２２６の出力は、ＦＯ関数に従ってＫＯ５およびＫＩ５とともに処理するために、ＦＯ５・２２８に供給される。ＦＯ５・２２８の出力は、ＸＯＲ２１８の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２３０に供給される。
【００２０】
ラウンド６において、ＸＯＲ２３０の出力は、ＦＯ関数に従ってＫＯ６およびＫＩ６とともに処理するために、ＦＯ６・２３２に供給される。ＦＯ６・２３２の出力は、ＦＬ関数に従ってＫＬ６とともに処理するために、ＦＬ６・２３４に供給される。ＦＬ６・２３４の出力は、ＸＯＲ２２４の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２３６に供給される。
【００２１】
ラウンド７において、ＸＯＲ２３６の出力は、ＦＬ関数に従ってＫＬ７とともに処理するために、ＦＬ７・２３８に供給される。ＦＬ７・２３８の出力は、ＦＯ関数に従ってＫＯ７およびＫＩ７とともに処理するために、ＦＯ７・２４０に供給される。ＦＯ７・２４０の出力は、ＸＯＲ２３０の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２４２に供給される。
【００２２】
ラウンド８において、ＸＯＲ２４２の出力は、ＦＯ関数に従ってＫＯ８およびＫＩ８とともに処理するために、ＦＯ８・２４４に供給される。ＦＯ８・２４４の出力は、ＦＬ関数に従ってＫＬ８とともに処理するために、ＦＬ８・２４６に供給される。ＦＬ８・２４６の出力は、ＸＯＲ２３６の出力とビットワイズ排他的論理和をとるために、ＸＯＲ２４８に供給される。
【００２３】
ＸＯＲ２４８の出力とＸＯＲ２４２の出力とは、図２（ａ）においてＣと記された６４ビットのＫＡＳＵＭＩ出力を生成するために連結される。
【００２４】
図２（ｂ）は、上述したＦＯ関数を実行する計算ステップを図示している。ＦＯ関数は３２ビット入力を取り入れ、それをそれぞれ左入力と右入力の２つの１６ビットセグメントに分ける。留意すべきは、ＦＯ関数は３つの段を含んでおり、それらは以下で詳しく述べるように、それぞれ２つの１６ビットビットワイズ排他的論理和とＦＩｉ１、ＦＩｉ２、およびＦＩｉ３で示される関数ＦＩｉのインスタンスとを含んでいることである。この説明において、図２（ａ）について上述した各ラウンドに１つのＦＯ関数があるので、ｉはラウンド番号に相当する。
【００２５】
関数ＦＯの第１段において、左１６ビット入力は、ＸＯＲ２５０において１６ビットサブ鍵ＫＯｉ，１とビットワイズ排他的論理和をとられる。上述したように、ＫＯｉ，１は４８ビットサブ鍵ＫＯｉの１６ビットサブ鍵である。また、ＫＯｉ，２とＫＯｉ，３は、ＫＯｉの１６ビットサブ鍵である。ＸＯＲ２５０の出力は、以下で述べるＦＩ関数に従ってＫＩｉ，１とともに処理するために、ＦＩｉ１・２５２に供給される。上述したように、ＫＩｉ，１は４８ビットサブ鍵ＫＩｉの１６ビットサブ鍵である。また、ＫＩｉ，２とＫＩｉ，３は、ＫＩｉの１６ビットサブ鍵である。ＦＩｉ１・２５２の出力は、右入力と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２５４に供給される。
【００２６】
関数ＦＯの第２段において、右入力は、サブ鍵ＫＯｉ，２と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２５６に供給される。その結果は、ＦＩ関数に従ってＫＩｉ，２とともに処理するために、ＦＩｉ２・２５８に供給される。ＦＩｉ２・２５８の出力は、ＸＯＲ２５４の出力と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２６０に供給される。
【００２７】
関数ＦＯの第３段において、ＸＯＲ２５４の出力は、サブ鍵ＫＯｉ，３と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２６２に供給される。その結果は、ＦＩ関数に従ってＫＩｉ，３とともに処理するために、ＦＩｉ３・２６４に供給される。ＦＩｉ３・２６４の出力は、ＸＯＲ２６０の出力と１６ビットビットワイズ排他的論理和をとるために、ＸＯＲ２６６に供給される。ＸＯＲ２６０の出力は、図２（ｂ）においてＦＯと記された関数の出力を生成するために、ＸＯＲ２６６の出力と連結される。
【００２８】
図２（ｃ）は、上述したＦＩ関数を実行する計算ステップを図示している。ＦＩ関数は１６ビット入力を取り入れ、それを９ビットセグメントと７ビットセグメントとに分ける。ＦＩ関数は、同一の処理を有する２つの段を含んでおり、この２つの段の間にＸＯＲ２７６およびＸＯＲ２８６で識別されるＸＯＲステップを有している。留意すべきは、図２（ｃ）における濃い線は９ビットパスを識別するのに用いられ、薄い線は７ビットパスを識別するのに用いられていることである。
【００２９】
第１段において、９ビット入力セグメントは、以下でさらに詳しく述べるように、処理のために関数Ｓ９・２６８に供給される。７ビット入力セグメントは、ゼロ拡張され、ＸＯＲ２７０においてＳ９・２６８の出力と排他的論理和をとられる。また、７ビット入力セグメントは、以下でさらに詳しく述べるように、処理のために関数Ｓ７・２７２に供給される。ＸＯＲ２７０の９ビット出力は、７ビットに切り捨てられ、ＸＯＲ２７４においてＳ７・２７２の出力と排他的論理和をとられる。
【００３０】
ＸＯＲ２７６において、ＸＯＲ２７４の出力は、サブ鍵ＫＩｉ，ｊ，１とビットワイズ排他的論理和をとられる。ＫＩｉ，ｊ，１はＫＩｉ，ｊの７ビットサブ鍵であり、ここでｉはラウンド番号を示し、ｊはＦＩ関数が呼び出されるＦＯ段番号を示し、１はそれがＫＩｉ，ｊの１番目のサブ鍵であることを示す。ＸＯＲ２８６において、ＸＯＲ２７０の出力は、９ビットサブ鍵ＫＩｉ，ｊ，２とビットワイズ排他的論理和をとられる。ＫＩｉ，ｊ，２は、ＫＩｉ，ｊの２番目のサブ鍵である。
【００３１】
ＸＯＲ２７６の出力とＸＯＲ２８６の出力は、関数Ｆ１の第２段への入力となる。ＸＯＲ２８６の９ビット出力は、処理のために関数Ｓ９・２７８に供給される。ＸＯＲ２７６の７ビット出力は、ゼロ拡張され、ＸＯＲ２８０においてＳ９・２７８の出力と排他的論理和をとられる。また、ＸＯＲ２７６の出力は関数Ｓ７・２８２に供給される。ＸＯＲ２８０の９ビット出力は、７ビットに切り捨てられ、ＸＯＲ２８４においてＳ７・２８２の出力と排他的論理和をとられる。ＸＯＲ２８４の７ビット出力は、ＸＯＲ２８０の９ビット出力と連結され、ＦＩと記される１６ビット出力を形成する。
【００３２】
関数Ｓ７は、ＫＡＳＵＭＩ仕様で規定される。これは、７ビット入力を取り入れ、７ビット出力を返す。以下の式１−７は、ｙ０からｙ６までの各出力ビットを、ｘ０からｘ６までの７つの入力ビットの関数として定義する。ｘ１ｘ３のような２つのオペランドの連結は、オペランドの論理積（すなわち、ｘ１ ＡＮＤ ｘ３）を示す。記号
【数１】
【００３３】
は、排他的論理和関数を表わす。
【数２】
【００３４】
関数Ｓ９は、ＫＡＳＵＭＩ仕様で規定される。これは、９ビット入力を取り入れ、９ビット出力を返す。以下の式８−１６は、ｙ０からｙ８までの各出力ビットを、ｘ０からｘ８までの９つの入力ビットの関数として定義する。ｘ０ｘ２のような２つのオペランドの連結は、オペランドの論理積（すなわち、ｘ０ ＡＮＤ ｘ２）を示す。記号
【数３】
【００３５】
は、排他的論理和関数を表わす。
【数４】
【００３６】
図２（ｄ）は、図２（ａ）について上述したＦＬ関数を図示している。３２ビット入力は、２つの１６ビットセグメントである左セグメントと右セグメントに分割される。左入力セグメントは、記号∩で表わされるＡＮＤゲート２８８において、ＫＬｉ，１と、ビットワイズ論理積をとられる。ＡＮＤゲート２８８の出力は、記号＜＜＜で表わされるローテータ２９０において、１ビット分左に巡回される。ローテータ２９０の出力は、ＸＯＲ２９２において右入力セグメントとビットワイズ排他的論理和をとられる。ＸＯＲ２９２の出力は、記号∪で表わされるＯＲゲート２９８において、ビットワイズ論理和をとられる。ＯＲゲート２９８の出力は、ローテータ２９６において１ビット分左に巡回される。ローテータ２９６の出力は、ＸＯＲ２９４において左入力セグメントとビットワイズ排他的論理和をとられる。ＦＬで表わされる３２ビット出力は、ＸＯＲ２９４の出力とＸＯＲ２９２の出力とを連結することにより形成される。
【００３７】
ＫＡＳＵＭＩアルゴリズムは、いま述べたように、所望の結果を生成するために８つの計算ラウンドを必要とする。一実施形態において、単一のラウンドのためのハードウェアが配備され、８ラウンドのＫＡＳＵＭＩ出力を生成するために適切なフィードバックとともに再使用される。図３は、そのような例示的な実施形態を図示している。「例示的」という言葉は、ここでは専ら「一例、具体例、または例証となる」ことを意味するよう用いる。本明細書中で「例示的」に述べられたどの実施形態も、必ずしも他の実施形態よりも好ましくあるいは有利であるとして解釈すべきものではない。
【００３８】
図３はＫＡＳＵＭＩ３００を図示しており、これはサブ鍵生成器３１０、ＫＡＳＵＭＩラウンド３３０、およびＫＡＳＵＭＩ計算制御器３２０を備えている。ＫＡＳＵＭＩラウンド３３０は、サブ鍵生成器３１０からサブ鍵を受け入れる。ＫＬｉ，１とＫＬｉ，２は、直接接続され、ＫＯｉ，ｊおよびＫＩｉ，ｊは、それぞれｍｕｘ３４０および３５０を介して供給される。ｍｕｘ３４０は、サブ鍵生成器３１０からＫＯｉ，１，ＫＯｉ，２、およびＫＯｉ，３を受け入れる。ｍｕｘ３５０は、サブ鍵生成器３１０からＫＩｉ，１，ＫＩｉ，２、およびＫＩｉ，３を受け入れる。ｍｕｘ３４０およびｍｕｘ３５０からそれぞれＫＡＳＵＭＩラウンド３３０に供給されるべきサブ鍵のセット、ＫＯｉ，ｊおよびＫＩｉ，ｊは、ＫＡＳＵＭＩ計算制御器３２０からの制御信号、ｓｕｂｋｅｙ＿ｓｅｌｅｃｔによって決定される。全てのサブ鍵は、サブ鍵生成器３１０において、Ｋと記された１２８ビットの長さの鍵入力から生成される。またサブ鍵生成器３１０は、ＫＡＳＵＭＩ計算制御器３２０からロード信号と巡回信号を受信する。サブ鍵生成については、以下でより十分に詳述する。
【００３９】
ＫＡＳＵＭＩ計算制御器３２０は、リセット信号と開始信号を入力として受け取る。ＫＡＳＵＭＩ計算制御器３２０は、ＫＡＳＵＭＩ出力が生成されたことを示す終了信号を生成する。そのような完了を示す信号は、任意である。他の実施形態では、完了時間がシステムの特性に基づいて分かっている場合に、そのような信号を除くことができる。例示的な実施形態における開始信号は、開始信号がストローブされたときに鍵Ｋおよび６４ビット入力が有効となるように同期をとられる。ＫＡＳＵＭＩラウンド３３０の動作を制御するために、様々な信号が図３に示されている。ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗ、ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔ、およびｋａｓｕｍｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎが、ＫＡＳＵＭＩラウンド３３０内でラウンドレベルの機能を制御するために用いられる。ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔとｆｏ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎは、ＫＡＳＵＭＩラウンド３３０内でＦＯ関数を制御するために用いられる。ｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔとｆｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎは、ＫＡＳＵＭＩラウンド３３０内でＦＩ関数を制御するために用いられる。例示的な実施形態では、ＦＩ関数を制御するのに１つの制御信号のみが必要とされるので、これら最後の２つの信号は同一になっている。これらの信号のサブセットは、様々な実施形態がどのように配備されるかによって必要となることがある。メモリとフィードバック回路を制御するための様々なシグナリング方式は技術的に知られており、本発明の範囲内である。必要とされる制御の詳細な説明は、以下に提供されている。
【００４０】
ＫＡＳＵＭＩラウンド３３０は、いま述べた制御信号とサブ鍵に加えて、６４ビット出力を生成する６４ビット入力を受け入れる（その計算は、図２（ａ）−２（ｄ）を基に詳しく述べた）。
【００４１】
図４はＫＡＳＵＭＩラウンド４００を図示しており、これはいま述べたＫＡＳＵＭＩラウンド３３０の例示的な実施形態である。ＫＡＳＵＭＩラウンド４００において、６４ビット入力ｉｎは、上半分（６３：３２）と下半分（３１：０）の２つの３２ビットセグメントに分割される。上半分は、ｍｕｘ４０５の入力に接続される。下半分は、ｍｕｘ４１０の入力に接続される。２つのレジスタ４４５および４５０は、ｋａｓｕｍｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎがアサートにされた場合に、ＫＡＳＵＭＩラウンド４００内で演算された結果をラッチし、レジスタ４４５の出力とレジスタ４５０の出力は、６４ビット出力ｏｕｔを生成するために連結される。それに加えて、レジスタ４４５の出力はｍｕｘ４１０の入力としてフィードバックされ、レジスタ４５０の出力はｍｕｘ４０５の入力としてフィードバックされる。ｍｕｘ４０５および４１０はｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔにより制御され、これは、アサートにされない場合にｉｎが選択され、アサートにされる場合にフィードバック結果が選択されるようにする。ｍｕｘ４０５および４１０は、入力とレジスタ４４５および４５０により形成されるメモリの内容との間で選択を行うセレクタとして共に動作する。このようにＫＡＳＵＭＩラウンド４００は、ｉｎが選択された場合に、最初のＫＡＳＵＭＩのラウンドを実行し、前のラウンドの結果がフィードバックされた場合に、後に続くＫＡＳＵＭＩのラウンドを実行するのに利用することができる。
【００４２】
図２（ａ）−２（ｄ）に関して上述したように、ＫＡＳＵＭＩラウンドの処理の核心は、ＦＬ関数４２５、ＦＯ関数４３０、およびＸＯＲ４４０において実行される。しかしながら、上述したように、関数はそれぞれ各ラウンドで使われるので、処理順序はラウンドによって異なる。３つのｍｕｘ４１５、４２０、および４３５は、後に続くＫＡＳＵＭＩの各ラウンドにおいて構成要素を再使用するのに必要な切り換えを提供する。ＦＬ関数４２５、ＦＯ関数４３０、ＸＯＲ４４０と、ｍｕｘ４１５、４２０、および４３５とは、共に部分的なラウンド計算部の一実施形態を形成する。ｍｕｘ４０５の出力から供給されるｍｕｘ４１５への入力からなり、ＸＯＲ４４０の出力に連結される部分的なラウンド計算部の出力は、レジスタ４４５および４５０により形成されたメモリ内に格納される。部分的なラウンド計算部への入力は、ｍｕｘ４０５および４１０により形成されたセレクタの出力から発せられる。いま述べたセレクタ、部分的なラウンド計算部、およびメモリの多くの回路実装は、当業者にとって容易に明らかとなる。これらの実施形態は、どれも本発明の範囲内である。
【００４３】
３つのｍｕｘ４１５、４２０、および４３５は、偶数および奇数ラウンド計算用のＫＡＳＵＭＩラウンドを構成するためのデータフローセレクタを構成する。それらは、全てセレクタ信号ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗにより制御される。ｍｕｘ４１５は、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗがアサートにされた場合にｍｕｘ４０５の出力を選択し、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗが非アサートにされた場合に関数ＦＯ４３０のフィードバック出力を選択する。ｍｕｘ４２０は、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗが非アサートにされた場合にレジスタ４４５の出力を選択し、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗがアサートにされた場合に関数ＦＬ４２５のフィードバック出力を選択する。ｍｕｘ４１５の出力は関数ＦＬ４２５に供給され、関数ＦＬ４２５の出力はｍｕｘ４３５に供給される。ｍｕｘ４２０の出力は、関数ＦＯ４３０に供給され、関数ＦＯ４３０の出力もｍｕｘ４３５に供給される。ｍｕｘ４３５は、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗが非アサートにされた場合に関数ＦＬ４２５の出力を選択し、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗがアサートにされた場合に関数ＦＯ４３０の出力を選択する。ｍｕｘ４３５の出力は、ｉｎ入力としてビットワイズＸＯＲ４４０に供給される。ビットワイズＸＯＲ４４０の他方の入力は、ｍｕｘ４１０の出力である。上述したレジスタ４５０への入力は、ＸＯＲ４４０の出力である。上述したレジスタ４４５への入力は、ｍｕｘ４０５の出力である。当業者は、制御信号ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔ、ｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗ、およびｋａｓｕｍｉ＿ｏｕｔｏｕｔ＿ｒｅｇ＿ｅｎの適切な操作を結びつけた図４に図示する構成を、図２（ａ）について上述した所望のＫＡＳＵＭＩ計算を実行するのに用いることができることを認識できる。本実施形態のための制御シグナリングについては、以下でさらに詳しく述べる。
【００４４】
図５は、図４について上述した関数ＦＬ４２５として用いるのに適したＦＬ関数５００の実施形態を図示している。ＦＬ関数５００は、３２ビット入力ｉｎを受け入れ、３２ビット出力ｏｕｔを生成する。ｉｎの上半分（ビット３１から１６まで）は、ＡＮＤゲート５１０においてサブ鍵ＫＬｉ，１とビットワイズ論理積をとられる。ＡＮＤゲート５１０の出力は、ローテータ５２０において１ビット左に巡回される。ローテータ５２０の出力は、ＸＯＲ５３０において入力の下半分（ビット１５から０まで）とビットワイズ排他的論理和をとられる。ＸＯＲ５３０の結果は、ＯＲゲート５４０においてサブ鍵ＫＬｉ，２とビットワイズ論理和をとられる。ＯＲゲート５４０の出力は、ローテータ５５０において１ビット左に巡回される。ローテータ５５０の出力は、ＸＯＲ５６０において入力の上半分とビットワイズ排他的論理和をとられる。ＸＯＲ５６０の出力は、３２ビット出力ｏｕｔを生成するためにＸＯＲ５３０の出力と連結される。
【００４５】
図６は、図４について上述した関数ＦＯ４３０として用いるのに適したＦＯ関数６００の実施形態を図示している。ＦＯ関数６００は、３２ビット入力ｉｎを受け入れ、３２ビット出力ｏｕｔを生成する。本実施形態では、上述した３つのＦＯ段のうちの１つのための構成要素が配備されている。レジスタと適切なフィードバックにより、単一の段を連続して３回用いて、ＦＯ出力を生成することができるようになる。
【００４６】
２つのレジスタ６６０および６７０は、ｆｏ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎがアサートにされた場合に、中間計算値を格納する。レジスタ６６０の出力は、ｍｕｘ６２０の入力として供給される。レジスタ６７０の出力は、ｍｕｘ６１０の入力として供給される。入力ｉｎの上半分は、ｍｕｘ６１０への他方の入力となる。入力ｉｎの下半分は、ｍｕｘ６２０への他方の入力となる。信号ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔは、ｍｕｘ６１０および６２０に、それぞれ入力ｉｎとレジスタ６６０および６７０からのフィードバック値との間で選択を行うよう指示する。ｍｕｘ６１０の出力は、ＸＯＲ６３０においてサブ鍵ＫＯｉ，ｊとビットワイズ排他的論理和をとられる。ＸＯＲ６３０の出力は、関数ＦＩ６４０に供給され、以下でさらに詳しく述べるように、サブ鍵ＫＯｉ，ｊとともに処理される。関数ＦＩ６４０の出力は、ＸＯＲ６５０においてｍｕｘ６２０の出力とビットワイズ排他的論理和をとられる。ＸＯＲ６５０の出力は、上述したように、レジスタ６６０への入力として供給される。ｍｕｘ６２０の出力は、上述したように、入力としてレジスタ６７０に供給される。ｍｕｘ６２０の出力は、３２ビット出力ｏｕｔを形成するためにＸＯＲ６５０の出力と連結される。
【００４７】
レジスタ６６０とレジスタ６７０はメモリを形成する。ｍｕｘ６１０とｍｕｘ６２０はセレクタを形成する。ＸＯＲ６３０、ＦＩ関数６４０、およびＸＯＲ６５０は、部分的なＦＯ計算部を形成する。セレクタは、入力を部分的なＦＯ計算部へ供給するために、入力とメモリ結果との間で選択を行う。部分的なＦＯ計算部の出力は、メモリに格納される。いま述べたセレクタ、部分的なＦＯ計算部、およびメモリの多くの回路実装は、当業者にとって容易に明らかとなる。これらの実施形態は、どれも本発明の範囲内である。
【００４８】
図７は、図６について上述した関数ＦＩ６４０として用いるのに適したＦＩ関数７００の実施形態を図示している。ＦＩ関数７００は、１６ビット入力ｉｎを受け入れ、１６ビット出力ｏｕｔを生成する。本実施形態では、上述した２つのＦＩ段のうちの１つのための構成要素が配備されている。レジスタと適切なフィードバックにより、単一の段を連続して２回用いて、ＦＩ出力を生成することができるようになる。
【００４９】
２つのレジスタ７４５および７５０は、ｆｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎがアサートにされた場合に、中間計算値を格納するのに用いられる。９ビットレジスタ７４５の出力は、入力としてｍｕｘ７０５に供給される。７ビットレジスタ７５０の出力は、入力としてｍｕｘ７１０に供給される。入力ｉｎの上位９ビットは、ｍｕｘ７０５への他方の入力となる。入力ｉｎの下位７ビットは、ｍｕｘ７１０への他方の入力となる。信号ｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔは、ｍｕｘ７０５および７１０に、それぞれ入力ｉｎとレジスタ７４５および７５０からのフィードバック値との間で選択を行うよう指示する。ｍｕｘ７０５の出力は、上述したように関数Ｓ９・７１５における処理のために供給される。関数Ｓ９・７１５の出力は、ＸＯＲ７２０においてｍｕｘ７１０のゼロ拡張出力とビットワイズ排他的論理和をとられる。またｍｕｘ７１０の出力は、関数Ｓ７・７２５における処理のために供給される。関数Ｓ７・７２５の出力は、ＸＯＲ７３０において、ＸＯＲ７２０の切り捨てられた出力とビットワイズ排他的論理和をとられる。ＸＯＲ７２０の出力は、ＸＯＲ７３５においてサブ鍵ＫＩｉ，ｊ，２とビットワイズ排他的論理和をとられる。ＸＯＲ７３０の出力は、ＸＯＲ７４０においてサブ鍵ＫＩｉ，ｊ，１とビットワイズ排他的論理和をとられる。ＸＯＲ７３５の出力は、上述したように、入力としてレジスタ７４５に供給される。ＸＯＲ７４０の出力は、上述したように、入力としてレジスタ７５０に供給される。ＸＯＲ７３０の出力は、１６ビット出力ｏｕｔを生成するためにＸＯＲ７２０の出力と連結される。
【００５０】
本実施形態において留意すべきは、信号ｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔと信号ｆｉ＿ｏｕｔｐｕｔ＿ｒｅｇ＿ｅｎは同一であり、これにより、共通の信号をｍｕｘ７０５、ｍｕｘ７１０、レジスタ７４５、およびレジスタ７５０の間で共用できることである。他の実施形態において、各ＦＩ処理サイクルがクロック制御レジスタ７４５および７５０の１つのサイクルに相当する場合は、これらのレジスタでイネーブル信号は必要ない。レジスタは、ＸＯＲ７３５とＸＯＲ７４０の結果を、それらがＦＩの後半の計算に用いられる１サイクル分遅らせるだけである。これらのような様々な技術は用いることができ、技術的に周知である。
【００５１】
レジスタ７４５とレジスタ７５０はメモリを形成する。ｍｕｘ７０５とｍｕｘ７１０はセレクタを形成する。関数Ｓ９・７１５、ＸＯＲ７２０、関数Ｓ７・７２５、ならびに、ＸＯＲ７３０、７３５、および７４０は、部分的なＦＩ計算部を形成する。セレクタは、入力を部分的なＦＩ計算部へ供給するために、入力とメモリ結果との間で選択を行う。部分的なＦＩ計算部の出力である中間値は、メモリに格納される。それに加えて、ＸＯＲ７２０およびＸＯＲ７３０の出力はＦＩ出力にもなる。いま述べたセレクタ、部分的なＦＩ計算部、およびメモリの多くの回路実装は、当業者にとって容易に明らかとなる。これらの実施形態は、どれも本発明の範囲内である。
【００５２】
図８は、サブ鍵生成器８００を図示している。サブ鍵生成器８００は、１２８ビット鍵Ｋを受け入れ、ロード信号および巡回信号と共に上述した様々なサブ鍵を生成する。サブ鍵生成器８００は、２つの１２８ビットシフトレジスタ８１０および８２０を含む。これらは、どちらもロード信号がアサートにされた場合に並列ロード可能であり、巡回信号がアサートにされた場合に８ビット左巡回を実行する。ロード信号は、ＫＡＳＵＭＩ計算の初めに１度アサートにされる。巡回信号は、各ラウンドが完了した後に、次のラウンド用の新しいサブ鍵を作成するためにイネーブルになる。これらの制御信号の他の制御信号との関連についての説明は、より詳しく以下で述べる。
【００５３】
留意すべきは、これらの巡回可能シフトレジスタを実施する多くの方法は、当業者にとって容易に明らかとなることである。例えば、シフトアウトされたビットを入力として第１段にフィードバックすることにより、シフトレジスタを巡回シストレジスタにすることができる。そのような巡回シストレジスタは、８ビット左巡回を生成するために８回シフトすることができる。あるいは、各シフトが各ビットを８桁分巡回（すなわち、バイトワイズ左巡回）するように、シフトレジスタを配線することができる。この代替は、８つのインターリーブ１６ビットシフトレジスタを実施することに相当し、それらの出力がそれらの各入力にフィードバックされるよう構成される。
【００５４】
シフトレジスタ８２０は、Ｋ１からＫ８まで名付けられた８つの１６ビットのセクションから成る。Ｋ（１２７：１１２）はＫ１用のロード入力となる。Ｋ（１１１：９６）はＫ２用のロード入力となる。Ｋ（９５：８０）はＫ３用のロード入力となる。Ｋ（７９：６４）はＫ４用のロード入力となる。Ｋ（６３：４８）はＫ５用のロード入力となる。Ｋ（４７：３２）はＫ６用のロード入力となる。Ｋ（３１：１６）はＫ７用のロード入力となる。Ｋ（１５：０）はＫ８用のロード入力となる。
【００５５】
シフトレジスタ８１０は、Ｋ１’からＫ８’まで名付けられた８つの１６ビットのセクションから成る。シフトレジスタ８１０用のロード入力は、Ｋの様々なセグメントと、ＫＡＳＵＭＩ仕様で規定される定数Ｃ１からＣ８までとのビットワイズ排他的論理和をとることにより形成される。表１は、これら定数の値を提供している。
【表１】
【００５６】
Ｋ１’へのロード入力は、ＸＯＲ８０１において、Ｋ（１２７：１１２）とＣ１とのビットワイズ排他的論理和をとることにより生成される。Ｋ２’へのロード入力は、ＸＯＲ８０２において、Ｋ（１１１：９６）とＣ２とのビットワイズ排他的論理和をとることにより生成される。Ｋ３’へのロード入力は、ＸＯＲ８０３において、Ｋ（９５：８０）とＣ３とのビットワイズ排他的論理和をとることにより生成される。Ｋ４’へのロード入力は、ＸＯＲ８０４において、Ｋ（７９：６４）とＣ４とのビットワイズ排他的論理和をとることにより生成される。Ｋ５’へのロード入力は、ＸＯＲ８０５において、Ｋ（６３：４８）とＣ５とのビットワイズ排他的論理和をとることにより生成される。Ｋ６’へのロード入力は、ＸＯＲ８０６において、Ｋ（４７：３２）とＣ６とのビットワイズ排他的論理和をとることにより生成される。Ｋ７’へのロード入力は、ＸＯＲ８０７において、Ｋ（３１：１６）とＣ７とのビットワイズ排他的論理和をとることにより生成される。Ｋ８’へのロード入力は、ＸＯＲ８０８において、Ｋ（１５：０）とＣ８とのビットワイズ排他的論理和をとることにより生成される。当然ながら、各ＸＯＲ８０１−８０８は、オペランドの１つとして定数を有するので、１２８ＸＯＲの各々は、対応する定数が「０」の場合に配線と交換することができ、対応する定数が「１」の場合にインバータと交換することができる。
【００５７】
いくつかのサブ鍵は、シフトレジスタ８１０から直接引き出される。ＫＬｉ，２はＫ３’から引き出される。ＫＩｉ，２はＫ４’から引き出される。ＫＩｉ，１はＫ５’から引き出される。ＫＩｉ，３はＫ８’から引き出される。他のサブ鍵は、シフトレジスタ８２０の様々なセグメントを巡回することにより生成される。ＫＬｉ，１は、ローテータ８３０においてＫ１を１ビット分左に巡回することにより生成される。ＫＯｉ，１は、ローテータ８４０においてＫ２を５ビット分左に巡回することにより生成される。ＫＯｉ，２は、ローテータ８５０においてＫ６を８ビット分左に巡回することにより生成される。ＫＯｉ，３は、ローテータ８６０においてＫ７を１３ビット分左に巡回することにより生成される。留意すべきは、これらローテータの各々は定数値分巡回するので、各巡回は簡単なワイヤ・マッピングによって達成できることである。当業者は、そのようなワイヤ・マッピングがどのように実施されるべきかを認識でき、巡回のための様々な他の技術も認識できる。
【００５８】
図９は、ＫＡＳＵＭＩの一実施形態において実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。これらのステップは、図４について述べたＫＡＳＵＭＩラウンド４００のような実施形態に適用することもできる。
【００５９】
開始９０２で処理が始まり、ブロック９０４に進む。ブロック９０４において、ｉは１に設定され、ここでｉはラウンド番号を表わす。ＫＡＳＵＭＩラウンドの入力は、これがラウンド１であるので、ラウンドを演算するために選択される。これは、図４に示したように、ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック判定ブロック９０６に進むと、ここで、ｉで表わされた現時のラウンドが偶数または奇数であることを決定するために試験が実行される。ｉが奇数、すなわち１、３、５、または７である場合はブロック９０８に進む。ｉが偶数、すなわち２、４、６、または８である場合はブロック９１０に進む。
【００６０】
ブロック９０８において、ＫＡＳＵＭＩラウンドのデータフローは、（ラウンド１において）入力または（ラウンド３、５および７において）フィードバックから、ＦＬ関数へ、ＦＯ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを１に設定することに相当する。
【００６１】
ブロック９１０において、ＫＡＳＵＭＩラウンドのデータフローは、フィードバックから、ＦＯ関数へ、ＦＬ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを０に設定することに相当する。
【００６２】
ブロック９０８またはブロック９１０から、ＫＡＳＵＭＩラウンドを演算するためにブロック９１２に進む。ＫＡＳＵＭＩラウンドを演算するための一実施形態は図４において詳細に示したが、ＫＡＳＵＭＩラウンドを演算するためのどの方法も、図９のフローチャートの範囲内である。一度ＫＡＳＵＭＩラウンドが演算されると、その結果はラッチ結果ブロック９１４において格納される。これは、図４に示すｋａｓｕｍｉ＿ｒｅｇ＿ｅｎ信号をアサートにすることに相当する。判定ブロック９１６に進む。
【００６３】
判定ブロック９１６において、ｉが８に等しければ、８番目である最後のラウンドが実行されており、処理はＫＡＳＵＭＩ終了ブロック９２２において完了する。図３に示すような終了信号を用いる実施形態において、その信号はこの時点でアサートにすることができる。ｉが８未満の場合、実行されるべき付加的なラウンドがあり、それによりｉはブロック９１８において１だけ増加される。ブロック９２０に進み、ここで、次のラウンドを演算するために、ブロック９１４のラッチされた結果からのフィードバックが選択される。これは、図４においてｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。判定ブロック９０６にループバックし、次のラウンドを実行する。ＫＡＳＵＭＩ終了ブロック９２２に達するまで、ステップを繰り返す。
【００６４】
図１０は、ＦＯ関数の一実施形態において実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。これらのステップは、図６について述べたＦＯ関数６００のような実施形態に適用することもできる。
【００６５】
開始１００２で処理が始まり、ブロック１００４に進む。ブロック１００４において、ｊは１に設定され、ここでｊは段番号を表わす。ＦＯ関数の入力は、これが段１であるので、演算をするために選択される。これは、図６に示したように、ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。さらに、段番号ｊは、図３に示した信号ｓｕｂｋｅｙ＿ｓｅｌｅｃｔに関連する。（いくつかの実施形態では、ｓｕｂｋｅｙ＿ｓｅｌｅｃｔ値０、１、および２は、ｊの値１、２、および３に相当する。あるいは、ｊの値と同一のｓｕｂｋｅｙ＿ｓｅｌｅｃｔ値１、２、および３に基づいて選択を行う３つの入力ｍｕｘを配備することができる。）
ブロック１００６に進み、ここでＦＯ関数の１／３が演算される。ＦＯ関数の１／３を演算できる一実施形態が図６に図示されているが、他も図１０のフローチャートの範囲内である。１／３計算の結果は、ラッチ結果ブロック１００８において格納される。これは、図６においてｆｏ＿ｏｕｔｐｕｔ＿ｅｎをアサートにすることに相当する。次に判定ブロック１０１０に進み、ｊが３に等しいか試験を行う。もしそうなら、次にＦＯ完了ブロック１０１６に進み、ＦＯ関数は完了される。ｊが３未満の場合、さらなる段がまだ完了されていない。ブロック１０１２に進み、ｊを１だけ増加する。次にブロック１０１４に進み、ここで、ブロック１００８においてラッチされた結果であるフィードバックが、ＦＯ関数への入力として選択される。これは、図６においてｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１００６にループバックし、次の段を計算し、全ての段が完了するまで処理を繰り返す。
【００６６】
図１１は、ＦＩ関数の一実施形態において実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。これらのステップは、図７について述べたＦＩ関数７００のような実施形態に適用することもできる。
【００６７】
開始１１０２で処理が始まり、ブロック１１０４に進む。ブロック１１０４において、入力が演算のために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。ブロック１１０６に進み、ここでＦＩ関数の１／２が演算される。ブロック１１０８に進み、ブロック１１０６において計算されたＦＩの前半の結果をラッチする。ブロック１１１０に進み、ここでフィードバックが演算のために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１１１２に進み、ここでＦＩの後半が演算される。ブロック１１１４に進み、ＦＩ演算は完了する。
【００６８】
図１２は、図８について上述したもののようなサブ鍵生成器の実施形態を制御するために実行されるステップを詳細に示したフローチャートである。さらに、これらのステップは、図３について述べたような実施形態が配備されている場合に、ＫＡＳＵＭＩ計算制御器３２０により利用することができる。
【００６９】
開始１２０２で処理が始まり、ブロック１２０４に進む。ブロック１２０４において、ｉは１に設定され、ここでｉはラウンド番号を表わす。サブ鍵シフトレジスタがロードされる。例えば、図３におけるロード信号は、図８に示すサブ鍵生成器８００に接続することができる。ロード信号がアサートにされると、サブ鍵生成器８００は２つのシフトレジスタ８１０および８２０をロードする。ブロック１２０６に進み、使用されるべき現時のサブ鍵のセットを待ち、それは一般に１つのＫＡＳＵＭＩラウンドが生じるのに必要な時間となる。この時間の間、ラウンド１に対応するサブ鍵の１セットが有効になる。判定ブロック１２０８に進む。
【００７０】
判定ブロック１２０８において、ｉが８に等しければ、８番目である最後のＫＡＳＵＭＩラウンドが実行されており、処理は終了ブロック１２１４において完了する。他のＫＡＳＵＭＩ演算が必要な場合は、開始１２０２に戻る。ｉが８未満の場合、新しいサブ鍵のセットを必要とする付加的なラウンドがある。ブロック１２１０に進み、サブ鍵シフトレジスタを巡回する。これは、図３において巡回信号をアサートにすることに相当し、図８について上述したように、シフトレジスタ８１０および８２０において８ビット左巡回を引き起こす。ブロック１２１２に進み、ｉを１だけ増加する。ブロック１２０６にループバックし、他のＫＡＳＵＭＩラウンドのためにサブ鍵を供給する。終了ブロック１２１４に到達するまでステップを繰り返す。
【００７１】
図１３は、図３−８と上述した図９−１２におけるフローチャートとについて述べた技術を組み込んだＫＡＳＵＭＩを実行するステップを図示しているフローチャートである。図１３のステップを用いる例示的な実施形態は、上述した図３におけるＫＡＳＵＭＩ３００である。例示的なＫＡＳＵＭＩ３００は、サブ鍵生成器３１０およびＫＡＳＵＭＩラウンド３３０と共に、図１３において述べた制御ステップを実行するＫＡＳＵＭＩ計算制御器３２０を用いることができる。サブ鍵生成器３１０は、図８において述べたサブ鍵生成器８００のようなものとすることができる。ＫＡＳＵＭＩラウンド３３０は、図８において述べたＫＡＳＵＭＩラウンド４００のようなものとすることができる。ＫＡＳＵＭＩラウンド４００は、図５および図６でそれぞれ述べたＦＬ関数５００およびＦＯ関数６００を用いることができる。ＦＯ関数６００は、図７で述べたＦＩ関数７００を用いることができる。図１３のフローチャートは開始１３０２で始まり、ブロック１３０４に進む。
【００７２】
ブロック１３０４において、ｉは１に設定され、ここでｉはラウンド番号を表わす。ＫＡＳＵＭＩラウンドへの入力は、これがラウンド１であるので、ラウンドを演算するために選択される。これは、図４に示したように、ｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。サブ鍵シフトレジスタがロードされる。例えば、図３におけるロード信号は、図８に示すサブ鍵生成器８００に接続することができる。ロード信号がアサートにされると、サブ鍵生成器８００は２つのシフトレジスタ８１０および８２０をロードする。
【００７３】
判定ブロック１３０６に進むと、ここで、ｉで表わされた現時のラウンドが偶数または奇数であることを決定するために試験が実行される。ｉが奇数、すなわち１、３、５、または７である場合はブロック１３０８に進む。ｉが偶数、すなわち２、４、６、または８である場合はブロック１３１０に進む。ブロック１３０８において、ＫＡＳＵＭＩラウンドのデータフローは、（ラウンド１において）入力または（ラウンド３、５および７において）フィードバックから、ＦＬ関数へ、ＦＯ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを１に設定することに相当する。ブロック１３１０において、ＫＡＳＵＭＩラウンドのデータフローは、フィードバックから、ＦＯ関数へ、ＦＬ関数へ、ＸＯＲゲートへと流れる構成となっている。これは、図４においてｋａｓｕｍｉ＿ｄａｔａ＿ｆｌｏｗを０に設定することに相当する。
【００７４】
ブロック１３０８またはブロック１３１０から、ＫＡＳＵＭＩラウンドの演算を開始するためにブロック１３１２に進む。ＦＩ段およびＦＯ段のようなラウンドのサブ関数を最初に述べたが、当業者が理解するように、これらの方法ステップは本発明の範囲を逸脱することなく交換することができる。
【００７５】
ブロック１３１２において、ＦＯ関数が初期化される。ｊは１に設定され、ここでｊは段番号を表わす。ＦＯ関数の入力は、これがＦＯ段１であるので、ＦＯ関数を演算するために選択される。これは、図６に示したように、ｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。さらに、段番号ｊは、図３に示した信号ｓｕｂｋｅｙ＿ｓｅｌｅｃｔに関連する。ｓｕｂｋｅｙ＿ｓｅｌｅｃｔとｊとの相関関係については、図１０について上記で詳しく述べた。ブロック１３１４に進み、ＦＩ関数を実行する。
【００７６】
ブロック１３１４において、入力がＦＩ関数を演算するために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。ブロック１３１６に進み、ここでＦＩ関数の１／２が演算される。ＦＩ関数の１／２を演算することができる一実施形態が図７に図示されているが、他も図１３のフローチャートの範囲内である。ブロック１３１８に進み、ブロック１３１６で計算されたＦＩの前半の結果をラッチする。ブロック１３２０に進み、ここでＦＩフィードバックがＦＩ関数を演算するために選択され、これは図７においてｆｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１３２２に進み、ここでＦＩの後半が演算される。ブロック１３２４に進み、ＦＯ処理を続け、ＦＩ演算が完了する。
【００７７】
ブロック１３２４において、ＦＯ関数の１／３が演算される。ＦＯ関数の１／３を演算することができる一実施形態が図６に図示されているが、他も図１３のフローチャートの範囲内である。１／３計算の結果は、ラッチＦＯ結果ブロック１３２６において格納される。これは、図６においてｆｏ＿ｏｕｔｐｕｔ＿ｅｎをアサートにすることに相当する。次に判定ブロック１３２８に進み、ｊが３に等しいか試験を行う。もしそうなら、次にＦＯ処理が完了する。ブロック１３３４に進み、ＫＡＳＵＭＩ処理を続ける。ｊが３未満の場合、さらなる段がまだ完了していない。ブロック１３３０に進み、ｊを１だけ増加する。次にブロック１３３２に進み、ここで、ブロック１３２６においてラッチされたＦＯ結果であるフィードバックが、ＦＯ関数への入力として選択される。これは、図６においてｆｏ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを０に設定することに相当する。ブロック１３１４にループバックし、次の段を計算し、全ての段が完了するまで処理を繰り返す。
【００７８】
ブロック１３３４において、ＫＡＳＵＭＩラウンドを演算する。ＫＡＳＵＭＩラウンドを演算するための一実施形態は図４において詳細に示したが、ＫＡＳＵＭＩラウンドを演算するためのどの方法も、図１３のフローチャートの範囲内である。ブロック１３３４で一度ＫＡＳＵＭＩラウンドが演算されると、その結果はラッチＫＡＳＵＭＩ結果ブロック１３３６において格納される。これは、図４に示すｋａｓｕｍｉ＿ｒｅｇ＿ｅｎ信号をアサートにすることに相当する。判定ブロック１３３８に進む。
【００７９】
判定ブロック１３３８において、ｉが８に等しければ、８番目である最後のラウンドが実行されており、処理はＫＡＳＵＭＩ終了ブロック１３４６において完了する。図３に示すような終了信号を用いる実施形態において、その信号はこの時点でアサートにすることができる。ｉが８未満の場合、実行されるべき付加的なラウンドがあり、それによりｉはブロック１３４０において１だけ増加される。ブロック１３４２に進み、ここで、次のラウンドを演算するために、ブロック１３３６のラッチされた結果であるフィードバックが選択される。これは、図４においてｋａｓｕｍｉ＿ｉｎｐｕｔ＿ｓｅｌｅｃｔを１に設定することに相当する。次のラウンドでは新しいサブ鍵のセットを必要とし、そのためサブ鍵シフトレジスタを巡回するためにブロック１３４４に進む。これは、図３において巡回信号をアサートにすることに相当し、図８について上述したように、シフトレジスタ８１０および８２０において８ビット左巡回を引き起こす。判定ブロック１３０６にループバックし、次のラウンドを実行する。ＫＡＳＵＭＩ終了ブロック１３４６に到達するまで、ステップを繰り返す。
【００８０】
上述した全ての実施形態において、方法ステップは本発明の範囲を逸脱することなく交換することができることに留意すべきである。
【００８１】
当業者は、任意の様々な各種テクノロジーと技術を用いて情報および信号を表わせることを理解する。例えば、上記説明を通じて参照することができるデータ、指示、コマンド、情報、信号、ビット、記号、およびチップは、電圧、電流、電磁波、磁界または磁性粒子、光場または光粒子、あるいはそれらの組み合わせにより表わすことができる。
【００８２】
さらに当業者には、本明細書中で開示した実施形態に関連して述べられた様々な実例となる論理ブロック、モジュール、回路、およびアルゴリズムステップを、電子ハードウェア、コンピュータソフトウェア、または両方の組み合わせとして実施できることが分かる。このハードウェアおよびソフトウェアの互換性を明らかに示すために、様々な実例となる構成要素、ブロック、モジュール、回路、およびステップを、それらの機能性の点から広く述べた。そのような機能性がハードウェアとして実施されるか、またはソフトウェアとして実施されるかは、システム全体に課せられた特定の用途と設計制約による。熟練した当業者は、各特定用途のために、上述した機能性を様々に実施することができるが、そのような実施の決定は本発明の範囲からの逸脱をもたらすと解釈するべきではない。
【００８３】
本明細書中で開示した実施形態に関連して述べられた様々な実例となる論理ブロック、モジュール、および回路を、汎用プロセッサ、デジタル信号プロセッサ（ＤＡＰ）、特定用途向け集積回路（ＡＳＩＣ）、現場でプログラム可能なゲートアレイ（ＦＰＧＡ）または他のプログラム可能論理回路、ディスクリートゲートまたはトランジスタ論理、ディスクリートハードウェア部品、または本明細書中で述べた機能を実行するよう設計されたそれらの任意の組み合わせとともに実装または実行することができる。汎用プロセッサはマイクロプロセッサとすることができるが、別の方法では、プロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械とすることができる。またプロセッサを、演算装置の組み合わせ、例えばＤＳＰとマイクロプロセッサとの組み合わせ、複数のマイクロプロセッサ、ＤＳＰコアと連動する１つ以上のマイクロプロセッサ、あるいはそのような任意の他の構成として実施することができる。
【００８４】
本明細書中で開示した実施形態に関連して述べた方法のステップすなわちアルゴリズムは、ハードウェア、プロセッサにより実行されるソフトウェアモジュール、またはその２つの組み合わせに直接組み入れることができる。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、取り外し可能ディスク、ＣＤ−ＲＯＭ、あるいは技術的に知られた他の任意の記憶媒体形態に常駐することができる。例示的な記憶媒体はプロセッサと結合され、そのようなプロセッサは記憶媒体から情報を読み出し、記憶媒体に情報を書き込むことができる。別の方法では、記憶媒体をプロセッサに一体化することができる。プロセッサと記憶媒体はＡＳＩＣ内に常駐することができる。ＡＳＩＣはユーザー端末内に常駐することができる。別の方法では、プロセッサと記憶媒体をディスクリート部品としてユーザー端末内に常駐することができる。
【００８５】
上記で開示された実施形態の説明は、任意の当業者が本発明を行い使用できるように提供されている。これらの実施形態の様々な変更は当業者にとって容易に明らかとなり、明細書中で規定された一般的な原理は、本発明の特質と範囲を逸脱することなく他の実施形態に適用することができる。したがって、本発明は明細書中で示された実施形態に限定されることなく、明細書中で開示された原理と新規な特徴に沿う最も広い範囲に適合することになる。
【図面の簡単な説明】
【００８６】
【図１】多数のユーザーをサポートできる無線通信システムを示す概略ブロック図。
【図２（ａ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図２（ｂ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図２（ｃ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図２（ｄ）】ＫＡＳＵＭＩを実行するのに必要な計算を図示する。
【図３】ＫＡＳＵＭＩを実行する実施形態の概略ブロック図。
【図４】ＫＡＳＵＭＩラウンドの実施形態のブロック図。
【図５】ＦＬ関数の実施形態のブロック図。
【図６】ＦＯ関数の実施形態のブロック図。
【図７】ＦＩ関数の実施形態のブロック図。
【図８】サブ鍵生成器のブロック図。
【図９】ＫＡＳＵＭＩの一実施形態のフローチャート。
【図１０】ＦＯ関数の一実施形態のフローチャート。
【図１１】ＦＩ関数の一実施形態のフローチャート。
【図１２】サブ鍵生成器の一実施形態のフローチャート。
【図１３】ＫＡＳＵＭＩの他の実施形態の制御フローを示す図
【特許請求の範囲】
【請求項１】
８つのラウンドを順序付けてＫＡＳＵＭＩ出力を生成するための計算制御器に動作可能に結合され、ＫＡＳＵＭＩ暗号の断片部分を生成するＫＡＳＵＭＩラウンドを有する装置。
【請求項２】
前記計算制御器に接続され、前記ＫＡＳＵＭＩラウンドにより使用される各ラウンド用のサブ鍵を生成するためのサブ鍵生成器をさらに備えた請求項１に記載の装置。
【請求項３】
ＫＡＳＵＭＩ入力に対して鍵によりＫＡＳＵＭＩ暗号化を実行し、ＫＡＳＵＭＩ出力を生成する装置であり、
ＫＡＳＵＭＩ暗号の断片部分を生成し、偶数ラウンドおよび奇数ラウンドの計算用に構成でき、ＫＡＳＵＭＩ出力を生成するために８つのラウンドが計算されるＫＡＳＵＭＩラウンドと、
前記ＫＡＳＵＭＩラウンドの出力を格納するメモリと、
前記ＫＡＳＵＭＩラウンドへ入力を供給し、前記ＫＡＳＵＭＩ入力が最初のラウンドの間に選択され、前記メモリの内容が後に続くラウンドの間に選択されるセレクタと、
を備えた装置。
【請求項４】
前記鍵に基づき各ラウンド用のサブ鍵を生成するサブ鍵生成器をさらに備えた請求項３に記載の装置。
【請求項５】
前記装置はアクセスポイントにおいて動作可能に構成された請求項３に記載の装置。
【請求項６】
前記装置はアクセス端末において動作可能に構成された請求項３に記載の装置。
【請求項７】
前記装置はＷ−ＣＤＭＡシステムにおいて動作可能に構成された請求項３に記載の装置。
【請求項８】
入力を受け入れて出力を生成し、前記出力が生成される部分ラウンド計算部により動作可能なＫＡＳＵＭＩラウンドであり、
前記部分ラウンド計算部からの中間値を格納するメモリと、
前記部分ラウンド計算部への供給のために前記入力と前記メモリの内容との間で選択を行なうセレクタと、
を備えたＫＡＳＵＭＩラウンド。
【請求項９】
６４ビット入力を受け入れ、６４ビット出力を生成するＫＡＳＵＭＩラウンドであり、
ＦＯ関数と、
ＦＬ関数と、
ＸＯＲゲートと、
第１のレジスタと、
前記ＸＯＲゲートの出力を受け入れ、出力が前記第１のレジスタの出力と連結し、前記６４ビット出力を生成する第２のレジスタと、
入力選択信号の制御下で前記６４ビット入力の上半部と前記第２のレジスタの出力との間で選択を行い、出力が前記第１のレジスタで受け入れられる第１の入力ｍｕｘと、
前記入力選択信号の制御下で前記６４ビット入力の下半部と前記第１のレジスタの出力との間で選択を行い、出力が第２のオペランドとして前記ＸＯＲゲートに供給される第２の入力ｍｕｘと、
出力が前記ＦＬ関数に供給され、データフロー信号の制御下で前記第１の入力ｍｕｘの出力と前記ＦＯ関数の出力との間で選択を行う第１のデータパスｍｕｘと、
出力が前記ＦＯ関数に供給され、データフロー信号の制御下で前記ＦＬ関数の出力と前記第１のレジスタの出力との間で選択を行う第２のデータパスｍｕｘと、
出力が第１のオペランドとして前記ＸＯＲゲートに供給され、データフロー信号の制御下で前記ＦＬ関数の出力と前記ＦＯ関数との間で選択を行う第３のデータパスｍｕｘと、
を備えたＫＡＳＵＭＩラウンド。
【請求項１０】
入力を受け入れて出力を生成し、前記出力が生成される部分ＦＯ計算部により動作可能なＦＯ関数であり、
前記部分ＦＯ計算部からの中間値を格納するメモリと、
前記部分ＦＯ計算部への供給のために前記入力と前記メモリの内容との間で選択を行うセレクタと、
を備えたＦＯ関数。
【請求項１１】
３２ビット入力を受け入れ、３２ビット出力を生成するＦＯ関数であり、
ＫＯサブ鍵を第１のオペランドとして受け入れる第１のＸＯＲゲートと、
前記第１のＸＯＲゲートの出力を受け入れるＦＩ関数と、
前記ＦＩ関数の出力を第１のオペランドとして受け入れる第２のＸＯＲゲートと、
前記第２のＸＯＲゲートの出力を受け入れる第１のレジスタと、
第２のレジスタと、
出力が第２のオペランドとして前記第１のＸＯＲゲートに供給され、入力選択信号の制御下で前記３２ビット入力の上半分と前記第２のレジスタの出力との間で選択を行う第１の入力ｍｕｘと、
出力が前記第２のオペランドとして前記第２のＸＯＲゲートに供給されるとともに入力として前記第２のレジスタに供給され、入力選択信号の制御下で前記３２ビット入力の下半分と前記第１のレジスタの出力との間で選択を行い、出力が前記第２のＸＯＲゲートの出力と連結し前記３２ビット出力を生成する第２の入力ｍｕｘと、
を備えたＦＯ関数。
【請求項１２】
入力を受け入れて出力を生成し、中間値と前記出力が生成される部分ＦＩ計算部により動作可能なＦＩ関数であり、
前記部分ＦＩ計算部からの前記中間値を格納するメモリと、
前記部分ＦＩ計算部への供給のために前記入力と前記メモリの内容との間で選択を行うセレクタと、
を備えたＦＩ関数。
【請求項１３】
１６ビット入力を受け入れ、１６ビット出力を生成するＦＩ関数であり、
第１のレジスタと、
第２のレジスタと、
入力選択信号の制御下で前記第１のレジスタの出力と前記１６ビット入力の上位９ビットとの間で選択を行う第１の入力ｍｕｘと、
入力選択信号の制御下で前記第２のレジスタの出力と前記１６ビット入力の下位７ビットとの間で選択を行う第２の入力ｍｕｘと、
前記第１の入力ｍｕｘの出力を受け入れるＳ９関数と、
前記Ｓ９関数の出力と前記第２の入力ｍｕｘのゼロ拡張出力とをオペランドとして受け入れる第１のＸＯＲと、
前記第２の入力ｍｕｘの出力を受け入れるＳ７関数と、
前記第１のＸＯＲの切り捨てられた出力と前記Ｓ７関数の出力とをオペランドとして受け入れ、出力が前記第１のＸＯＲの出力と連結し前記１６ビット出力を生成する第２のＸＯＲと、
出力が前記第１のレジスタに供給され、第１のＫＩサブ鍵と前記第１のＸＯＲの出力とをオペランドとして受け入れる第３のＸＯＲと、
出力が前記第２のレジスタに供給され、第２のＫＩサブ鍵と前記第２のＸＯＲの出力とをオペランドとして受け入れる第４のＸＯＲと、
を備えたＦＩ関数。
【請求項１４】
鍵を受け入れ、各ラウンドのために８つのサブ鍵を生成するサブ鍵生成器であり、
前記鍵をロード可能で、巡回信号の制御下で８ビット分左巡回可能であり、出力から前記８つのサブ鍵のうち４つが得られる第１のシフトレジスタと、
前記鍵のマスクされたバージョンをロード可能で、前記巡回信号の制御下で８ビット分左巡回可能であり、出力から前記８つのサブ鍵のうち４つが得られる第２のシフトレジスタと、
を備えたサブ鍵生成器。
【請求項１５】
１２８ビット鍵を受け入れ、各ラウンドのために８つの１６ビットサブ鍵を生成するサブ鍵生成器であり、
鍵をロード可能な第１の１２８ビットシフトレジスタと、
前記鍵のマスクされたバージョンをロード可能で、第１のサブ鍵が第３の最上位１６ビットから生成され、第２のサブ鍵が第４の最上位１６ビットから生成され、第３のサブ鍵が第５の最上位１６ビットから生成され、第４のサブ鍵が最下位１６ビットから生成される第２の１２８ビットシフトレジスタと、
前記第１のシフトレジスタの最上位１６ビットに位置する内容を１ビット分左に巡回して、第５のサブ鍵を生成するローテータと、
前記第１のシフトレジスタの第２の最上位１６ビットに位置する内容を５ビット分左に巡回して、第６のサブ鍵を生成するローテータと、
前記第１のシフトレジスタの第３の最下位１６ビットに位置する内容を８ビット分左に巡回して、第７のサブ鍵を生成するローテータと、
前記第１のシフトレジスタの第２の最下位１６ビットに位置する内容を１３ビット分左に巡回して、第８のサブ鍵を生成するローテータと、
を備えたサブ鍵生成器。
【請求項１６】
ＫＡＳＵＭＩ暗号化を実行する方法であり、
８つの各ラウンドに対して、
第１のラウンドの間に計算ステップで用いる入力を選択し、
後に続くラウンドにおける計算ステップで用いる格納された結果を選択し、
部分結果を計算し、
メモリに前記部分結果を格納し、
前記格納された結果を出力として供給することを含む方法。
【請求項１７】
前記計算ステップは、
前記ラウンドが奇数の場合、
前記選択ステップにおいて選択された前記入力または格納された結果の上半
分に対してＦＬ関数を実行し、
前記ＦＬ関数の出力に対してＦＯ関数を実行し、
前記選択ステップにおいて選択された前記入力または格納された結果の下半
分と、前記ＦＯ関数の出力との排他的論理和をとり、
前記ラウンドが偶数の場合、
前記格納された結果の上半分に対してＦＯ関数を実行し、
前記ＦＯ関数の出力に対してＦＬ関数を実行し、
前記格納された結果の下半分と前記ＦＬ関数の出力との排他的論理和をとり、
前記選択ステップにおいて選択された前記入力または格納された結果の上半分と連結した前記排他的論理和ステップの出力を、前記部分結果として供給することを含む請求項１６に記載の方法。
【請求項１８】
各ラウンド用のサブ鍵を生成することをさらに含む請求項１６に記載の方法。
【請求項１９】
ＦＯ関数を実行する方法であり、
３つの各段に対して、
第１の段における計算ステップで用いる入力を選択し、
後に続く段における計算ステップで用いる格納された結果を選択し、
部分結果を計算し、
メモリに前記部分結果を格納し、
前記部分結果を出力として供給することを含む方法。
【請求項２０】
前記計算ステップは、
前記選択ステップにおいて選択された前記入力または格納された結果の上半分とサブ鍵との排他的論理和をとり、
前記排他的論理和ステップの出力に対してＦＩ関数を実行し、
前記選択ステップにおいて選択された前記入力または格納された結果の下半分と、前記ＦＩ関数の出力との排他的論理和をとり、
前記選択ステップにおいて選択された前記入力または格納された結果の上半分を前記第２の排他的論理和ステップの出力と連結したものを、前記部分結果として供給することを含む請求項１９に記載の方法。
【請求項２１】
ＦＩ関数を実行する方法であり、
入力を用いて部分結果を計算し、
前記部分結果とサブ鍵との排他的論理和をとり、
前記部分結果をメモリに格納し、
前記格納された結果を用いて第２の部分結果を計算し、
前記第２の部分結果を出力として供給することを含む方法。
【請求項２２】
前記計算ステップは、
前記入力または格納された結果の上位９ビットに対してＳ９関数を実行し、
前記入力または格納された結果の下位７ビットをゼロ拡張し、
前記ゼロ拡張された入力または格納された結果と前記Ｓ９関数の出力との排他的論理和をとり、
前記入力または格納された結果の下位７ビットに対してＳ７関数を実行し、
前記排他的論理和ステップの出力を切り捨て、
前記切り捨てられたＸＯＲ出力と前記Ｓ７関数の出力との排他的論理和をとり、
前記第１の排他的論理和ステップの出力と連結した前記第２の排他的論理和ステップの出力を、前記部分結果として供給することを含む請求項２１に記載の方法。
【請求項２３】
サブ鍵を生成する方法であり、
２つのサブ鍵シフトレジスタにロードし、
８つの各ラウンドに対して、
前記サブ鍵シフトレジスタから前記サブ鍵を導出し、
前記２つのサブ鍵シフトレジスタを８ビット分左に巡回することを含む方法。
【請求項２４】
前記ロードステップは、
鍵を前記第１のサブ鍵シフトレジスタにロードし、
前記鍵をマスクし、
前記マスクされた鍵を前記第２のサブ鍵シフトレジスタにロードすることを含む請求項２３に記載の方法。
【請求項２５】
前記導出するステップは、
前記第２のシフトレジスタの第３の最上位１６ビットのセットから第１のサブ鍵を導出し、
前記第２のシフトレジスタの第４の最上位１６ビットのセットから第２のサブ鍵を導出し、
前記第２のシフトレジスタの第５の最上位１６ビットのセットから第３のサブ鍵を導出し、
前記第２のシフトレジスタの最下位１６ビットのセットから第４のサブ鍵を導出し、
前記第１のシフトレジスタの最上位１６ビットのセットを１ビット分左に巡回して、第５のサブ鍵を生成し、
前記第１のシフトレジスタの第２の最上位１６ビットのセットを５ビット分左に巡回して、第６のサブ鍵を生成し、
前記第１のシフトレジスタの第３の最下位１６ビットのセットを８ビット分左に巡回して、第７のサブ鍵を生成し、
前記第１のシフトレジスタの第２の最下位１６ビットのセットを１３ビット分左に巡回して、第８のサブ鍵を生成することを含む請求項２４に記載の方法。
【請求項１】
８つのラウンドを順序付けてＫＡＳＵＭＩ出力を生成するための計算制御器に動作可能に結合され、ＫＡＳＵＭＩ暗号の断片部分を生成するＫＡＳＵＭＩラウンドを有する装置。
【請求項２】
前記計算制御器に接続され、前記ＫＡＳＵＭＩラウンドにより使用される各ラウンド用のサブ鍵を生成するためのサブ鍵生成器をさらに備えた請求項１に記載の装置。
【請求項３】
ＫＡＳＵＭＩ入力に対して鍵によりＫＡＳＵＭＩ暗号化を実行し、ＫＡＳＵＭＩ出力を生成する装置であり、
ＫＡＳＵＭＩ暗号の断片部分を生成し、偶数ラウンドおよび奇数ラウンドの計算用に構成でき、ＫＡＳＵＭＩ出力を生成するために８つのラウンドが計算されるＫＡＳＵＭＩラウンドと、
前記ＫＡＳＵＭＩラウンドの出力を格納するメモリと、
前記ＫＡＳＵＭＩラウンドへ入力を供給し、前記ＫＡＳＵＭＩ入力が最初のラウンドの間に選択され、前記メモリの内容が後に続くラウンドの間に選択されるセレクタと、
を備えた装置。
【請求項４】
前記鍵に基づき各ラウンド用のサブ鍵を生成するサブ鍵生成器をさらに備えた請求項３に記載の装置。
【請求項５】
前記装置はアクセスポイントにおいて動作可能に構成された請求項３に記載の装置。
【請求項６】
前記装置はアクセス端末において動作可能に構成された請求項３に記載の装置。
【請求項７】
前記装置はＷ−ＣＤＭＡシステムにおいて動作可能に構成された請求項３に記載の装置。
【請求項８】
入力を受け入れて出力を生成し、前記出力が生成される部分ラウンド計算部により動作可能なＫＡＳＵＭＩラウンドであり、
前記部分ラウンド計算部からの中間値を格納するメモリと、
前記部分ラウンド計算部への供給のために前記入力と前記メモリの内容との間で選択を行なうセレクタと、
を備えたＫＡＳＵＭＩラウンド。
【請求項９】
６４ビット入力を受け入れ、６４ビット出力を生成するＫＡＳＵＭＩラウンドであり、
ＦＯ関数と、
ＦＬ関数と、
ＸＯＲゲートと、
第１のレジスタと、
前記ＸＯＲゲートの出力を受け入れ、出力が前記第１のレジスタの出力と連結し、前記６４ビット出力を生成する第２のレジスタと、
入力選択信号の制御下で前記６４ビット入力の上半部と前記第２のレジスタの出力との間で選択を行い、出力が前記第１のレジスタで受け入れられる第１の入力ｍｕｘと、
前記入力選択信号の制御下で前記６４ビット入力の下半部と前記第１のレジスタの出力との間で選択を行い、出力が第２のオペランドとして前記ＸＯＲゲートに供給される第２の入力ｍｕｘと、
出力が前記ＦＬ関数に供給され、データフロー信号の制御下で前記第１の入力ｍｕｘの出力と前記ＦＯ関数の出力との間で選択を行う第１のデータパスｍｕｘと、
出力が前記ＦＯ関数に供給され、データフロー信号の制御下で前記ＦＬ関数の出力と前記第１のレジスタの出力との間で選択を行う第２のデータパスｍｕｘと、
出力が第１のオペランドとして前記ＸＯＲゲートに供給され、データフロー信号の制御下で前記ＦＬ関数の出力と前記ＦＯ関数との間で選択を行う第３のデータパスｍｕｘと、
を備えたＫＡＳＵＭＩラウンド。
【請求項１０】
入力を受け入れて出力を生成し、前記出力が生成される部分ＦＯ計算部により動作可能なＦＯ関数であり、
前記部分ＦＯ計算部からの中間値を格納するメモリと、
前記部分ＦＯ計算部への供給のために前記入力と前記メモリの内容との間で選択を行うセレクタと、
を備えたＦＯ関数。
【請求項１１】
３２ビット入力を受け入れ、３２ビット出力を生成するＦＯ関数であり、
ＫＯサブ鍵を第１のオペランドとして受け入れる第１のＸＯＲゲートと、
前記第１のＸＯＲゲートの出力を受け入れるＦＩ関数と、
前記ＦＩ関数の出力を第１のオペランドとして受け入れる第２のＸＯＲゲートと、
前記第２のＸＯＲゲートの出力を受け入れる第１のレジスタと、
第２のレジスタと、
出力が第２のオペランドとして前記第１のＸＯＲゲートに供給され、入力選択信号の制御下で前記３２ビット入力の上半分と前記第２のレジスタの出力との間で選択を行う第１の入力ｍｕｘと、
出力が前記第２のオペランドとして前記第２のＸＯＲゲートに供給されるとともに入力として前記第２のレジスタに供給され、入力選択信号の制御下で前記３２ビット入力の下半分と前記第１のレジスタの出力との間で選択を行い、出力が前記第２のＸＯＲゲートの出力と連結し前記３２ビット出力を生成する第２の入力ｍｕｘと、
を備えたＦＯ関数。
【請求項１２】
入力を受け入れて出力を生成し、中間値と前記出力が生成される部分ＦＩ計算部により動作可能なＦＩ関数であり、
前記部分ＦＩ計算部からの前記中間値を格納するメモリと、
前記部分ＦＩ計算部への供給のために前記入力と前記メモリの内容との間で選択を行うセレクタと、
を備えたＦＩ関数。
【請求項１３】
１６ビット入力を受け入れ、１６ビット出力を生成するＦＩ関数であり、
第１のレジスタと、
第２のレジスタと、
入力選択信号の制御下で前記第１のレジスタの出力と前記１６ビット入力の上位９ビットとの間で選択を行う第１の入力ｍｕｘと、
入力選択信号の制御下で前記第２のレジスタの出力と前記１６ビット入力の下位７ビットとの間で選択を行う第２の入力ｍｕｘと、
前記第１の入力ｍｕｘの出力を受け入れるＳ９関数と、
前記Ｓ９関数の出力と前記第２の入力ｍｕｘのゼロ拡張出力とをオペランドとして受け入れる第１のＸＯＲと、
前記第２の入力ｍｕｘの出力を受け入れるＳ７関数と、
前記第１のＸＯＲの切り捨てられた出力と前記Ｓ７関数の出力とをオペランドとして受け入れ、出力が前記第１のＸＯＲの出力と連結し前記１６ビット出力を生成する第２のＸＯＲと、
出力が前記第１のレジスタに供給され、第１のＫＩサブ鍵と前記第１のＸＯＲの出力とをオペランドとして受け入れる第３のＸＯＲと、
出力が前記第２のレジスタに供給され、第２のＫＩサブ鍵と前記第２のＸＯＲの出力とをオペランドとして受け入れる第４のＸＯＲと、
を備えたＦＩ関数。
【請求項１４】
鍵を受け入れ、各ラウンドのために８つのサブ鍵を生成するサブ鍵生成器であり、
前記鍵をロード可能で、巡回信号の制御下で８ビット分左巡回可能であり、出力から前記８つのサブ鍵のうち４つが得られる第１のシフトレジスタと、
前記鍵のマスクされたバージョンをロード可能で、前記巡回信号の制御下で８ビット分左巡回可能であり、出力から前記８つのサブ鍵のうち４つが得られる第２のシフトレジスタと、
を備えたサブ鍵生成器。
【請求項１５】
１２８ビット鍵を受け入れ、各ラウンドのために８つの１６ビットサブ鍵を生成するサブ鍵生成器であり、
鍵をロード可能な第１の１２８ビットシフトレジスタと、
前記鍵のマスクされたバージョンをロード可能で、第１のサブ鍵が第３の最上位１６ビットから生成され、第２のサブ鍵が第４の最上位１６ビットから生成され、第３のサブ鍵が第５の最上位１６ビットから生成され、第４のサブ鍵が最下位１６ビットから生成される第２の１２８ビットシフトレジスタと、
前記第１のシフトレジスタの最上位１６ビットに位置する内容を１ビット分左に巡回して、第５のサブ鍵を生成するローテータと、
前記第１のシフトレジスタの第２の最上位１６ビットに位置する内容を５ビット分左に巡回して、第６のサブ鍵を生成するローテータと、
前記第１のシフトレジスタの第３の最下位１６ビットに位置する内容を８ビット分左に巡回して、第７のサブ鍵を生成するローテータと、
前記第１のシフトレジスタの第２の最下位１６ビットに位置する内容を１３ビット分左に巡回して、第８のサブ鍵を生成するローテータと、
を備えたサブ鍵生成器。
【請求項１６】
ＫＡＳＵＭＩ暗号化を実行する方法であり、
８つの各ラウンドに対して、
第１のラウンドの間に計算ステップで用いる入力を選択し、
後に続くラウンドにおける計算ステップで用いる格納された結果を選択し、
部分結果を計算し、
メモリに前記部分結果を格納し、
前記格納された結果を出力として供給することを含む方法。
【請求項１７】
前記計算ステップは、
前記ラウンドが奇数の場合、
前記選択ステップにおいて選択された前記入力または格納された結果の上半
分に対してＦＬ関数を実行し、
前記ＦＬ関数の出力に対してＦＯ関数を実行し、
前記選択ステップにおいて選択された前記入力または格納された結果の下半
分と、前記ＦＯ関数の出力との排他的論理和をとり、
前記ラウンドが偶数の場合、
前記格納された結果の上半分に対してＦＯ関数を実行し、
前記ＦＯ関数の出力に対してＦＬ関数を実行し、
前記格納された結果の下半分と前記ＦＬ関数の出力との排他的論理和をとり、
前記選択ステップにおいて選択された前記入力または格納された結果の上半分と連結した前記排他的論理和ステップの出力を、前記部分結果として供給することを含む請求項１６に記載の方法。
【請求項１８】
各ラウンド用のサブ鍵を生成することをさらに含む請求項１６に記載の方法。
【請求項１９】
ＦＯ関数を実行する方法であり、
３つの各段に対して、
第１の段における計算ステップで用いる入力を選択し、
後に続く段における計算ステップで用いる格納された結果を選択し、
部分結果を計算し、
メモリに前記部分結果を格納し、
前記部分結果を出力として供給することを含む方法。
【請求項２０】
前記計算ステップは、
前記選択ステップにおいて選択された前記入力または格納された結果の上半分とサブ鍵との排他的論理和をとり、
前記排他的論理和ステップの出力に対してＦＩ関数を実行し、
前記選択ステップにおいて選択された前記入力または格納された結果の下半分と、前記ＦＩ関数の出力との排他的論理和をとり、
前記選択ステップにおいて選択された前記入力または格納された結果の上半分を前記第２の排他的論理和ステップの出力と連結したものを、前記部分結果として供給することを含む請求項１９に記載の方法。
【請求項２１】
ＦＩ関数を実行する方法であり、
入力を用いて部分結果を計算し、
前記部分結果とサブ鍵との排他的論理和をとり、
前記部分結果をメモリに格納し、
前記格納された結果を用いて第２の部分結果を計算し、
前記第２の部分結果を出力として供給することを含む方法。
【請求項２２】
前記計算ステップは、
前記入力または格納された結果の上位９ビットに対してＳ９関数を実行し、
前記入力または格納された結果の下位７ビットをゼロ拡張し、
前記ゼロ拡張された入力または格納された結果と前記Ｓ９関数の出力との排他的論理和をとり、
前記入力または格納された結果の下位７ビットに対してＳ７関数を実行し、
前記排他的論理和ステップの出力を切り捨て、
前記切り捨てられたＸＯＲ出力と前記Ｓ７関数の出力との排他的論理和をとり、
前記第１の排他的論理和ステップの出力と連結した前記第２の排他的論理和ステップの出力を、前記部分結果として供給することを含む請求項２１に記載の方法。
【請求項２３】
サブ鍵を生成する方法であり、
２つのサブ鍵シフトレジスタにロードし、
８つの各ラウンドに対して、
前記サブ鍵シフトレジスタから前記サブ鍵を導出し、
前記２つのサブ鍵シフトレジスタを８ビット分左に巡回することを含む方法。
【請求項２４】
前記ロードステップは、
鍵を前記第１のサブ鍵シフトレジスタにロードし、
前記鍵をマスクし、
前記マスクされた鍵を前記第２のサブ鍵シフトレジスタにロードすることを含む請求項２３に記載の方法。
【請求項２５】
前記導出するステップは、
前記第２のシフトレジスタの第３の最上位１６ビットのセットから第１のサブ鍵を導出し、
前記第２のシフトレジスタの第４の最上位１６ビットのセットから第２のサブ鍵を導出し、
前記第２のシフトレジスタの第５の最上位１６ビットのセットから第３のサブ鍵を導出し、
前記第２のシフトレジスタの最下位１６ビットのセットから第４のサブ鍵を導出し、
前記第１のシフトレジスタの最上位１６ビットのセットを１ビット分左に巡回して、第５のサブ鍵を生成し、
前記第１のシフトレジスタの第２の最上位１６ビットのセットを５ビット分左に巡回して、第６のサブ鍵を生成し、
前記第１のシフトレジスタの第３の最下位１６ビットのセットを８ビット分左に巡回して、第７のサブ鍵を生成し、
前記第１のシフトレジスタの第２の最下位１６ビットのセットを１３ビット分左に巡回して、第８のサブ鍵を生成することを含む請求項２４に記載の方法。
【図１】
【図２（ａ）】
【図２（ｂ）】
【図２（ｃ）】
【図２（ｄ）】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２（ａ）】
【図２（ｂ）】
【図２（ｃ）】
【図２（ｄ）】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２００８−１４８３５２（Ｐ２００８−１４８３５２Ａ）
【公開日】平成２０年６月２６日（２００８．６．２６）
【国際特許分類】
【外国語出願】
【出願番号】特願２００８−１６７９４（Ｐ２００８−１６７９４）
【出願日】平成２０年１月２８日（２００８．１．２８）
【分割の表示】特願２００３−５０１１２４（Ｐ２００３−５０１１２４）の分割
【原出願日】平成１４年５月３１日（２００２．５．３１）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
【公開日】平成２０年６月２６日（２００８．６．２６）
【国際特許分類】
【出願番号】特願２００８−１６７９４（Ｐ２００８−１６７９４）
【出願日】平成２０年１月２８日（２００８．１．２８）
【分割の表示】特願２００３−５０１１２４（Ｐ２００３−５０１１２４）の分割
【原出願日】平成１４年５月３１日（２００２．５．３１）
【出願人】（５９５０２０６４３）クゥアルコム・インコーポレイテッド (7,166)
【氏名又は名称原語表記】ＱＵＡＬＣＯＭＭ ＩＮＣＯＲＰＯＲＡＴＥＤ
【Ｆターム（参考）】
[ Back to top ]