JP3992742B2

JP3992742B2 - データブロックおよび鍵を非線形的に結合する暗号方法および装置

Info

Publication number: JP3992742B2
Application number: JP54191697A
Authority: JP
Inventors: ブールホイベルトデン
Original assignee: Philips Electronics NV
Current assignee: Koninklijke Philips NV
Priority date: 1996-05-20
Filing date: 1997-05-13
Publication date: 2007-10-17
Anticipated expiration: 2017-05-13
Also published as: JPH11509940A; DE69721439T2; WO1997044935A1; US7079651B2; US20020034295A1; US6298136B1; EP0839418A1; EP0839418B1; DE69721439D1

Description

本発明は、ディジタル入力ブロックをディジタル出力ブロックに変換する方法に関係し、前記変換は、前記ディジタル入力ブロックの選択された部分Ｍ１を第１鍵Ｋ１と結合し、前記選択された部分Ｍ１および第１鍵Ｋ１に非線形的に依存するデータブロックＢ１を発生するステップを具え、前記ディジタル出力ブロックの選択された部分を前記データブロックＢ１から得る。
さらに本発明は、ディジタル入力ブロックをディジタル出力ブロックに暗号的に変換する装置に関係し、前記装置は、前記ディジタル入力ブロックを得る第１入力手段と、第１鍵Ｋ１を得る第２入力手段と、前記ディジタル入力ブロックを前記ディジタル出力ブロックに変換する暗号処理手段と、前記ディジタル出力ブロックを出力する出力手段とを具え、前記変換が、前記ディジタル入力ブロックの選択された部分Ｍ１を前記第１鍵Ｋ１と結合することと、前記選択された部分Ｍ１および第１鍵Ｋ１に非線形的に依存するデータブロックＢ１を発生することとを具え、前記ディジタル出力ブロックの選択された部分を前記データブロックＢ１から得る。
国家標準局のデータ暗号化標準（ＤＥＳ）［ＦＩＰＳ刊行物４６、１９７７年１月１５日］は、ディジタル入力ブロックをディジタル出力ブロックに変換する、広く使用されているアルゴリズムを記載している。このようなアルゴリズムは、一般的に、ブロック暗号と呼ばれている。このＤＥＳアルゴリズムは、バイナリ符号化情報の暗号化および暗号復号化に使用される。暗号化は、プレーンテキストと呼ばれる明瞭なデータを、暗号テキストと呼ばれる不明瞭な形態に変換する。前記暗号テキストを暗号復号化することは、そのデータをその元の形態に変換し戻す。いわゆる電子コードブックモードにおいて、ＤＥＳを使用し、プレーンテキストの６４ビットのブロックを、対応する暗号テキストの６４ビットのブロックに変換する。このモードにおいて、暗号化は、６４ビット鍵から得られる鍵を使用し、その５６ビットを自由に選択してもよい。図１は、暗号化中のＤＥＳの構造のすべてを示す。暗号化計算において、最初に入力（プレーンテキスト）を６４ビットから固定された順列ＩＰを使用する６４ビットに並べ替える。その結果、３２左ビットＬ₀および３２右ビットＲ₀に分割される。これら右ビットを、暗号関数ｆ（Ｒ₀，Ｋ₁）を使用して変換し、ここでＫ₁をサブ鍵とする。この結果ｆ（Ｒ₀，Ｋ₁）を前記左ビットに（２を法とするビット幅）加算し、その後、２つの結果３２ビットブロックＬ₀▲＋▼ｆ（Ｒ₀，Ｋ₁）およびＲ₀を交換する。この手順を、合計１６ラウンド、反復的に続ける。最後のラウンドの終了において、最初の順列の逆順列を用いる。
ｆ（Ｒ_i，Ｋ_i+1）の計算において、図２に示すように、最初に３２右ビットＲ_iをボックスＥにおける４８ビットに拡張する。所定の表に従って、この拡張を、いくつかの入力ビットの出力ビットを２倍にし、他の入力ビットの出力ビットを１倍にすることによって行う。次に、拡張された４８ビットを、４８鍵ビットＫ_iに（２を法とするビット幅）加算する。結果として生じる４８ビットを、各々６ビットの８グループに分割する。これらのグループの各々を、Ｓボックス（Ｓ_i）によって処理し、Ｓボックスは、前記６ビットを４ビットに非線形演算において減少させる。８個のＳ_iボックスを、表の形態において与える。合計の出力は３２ビットであり、これをボックスＰにおいて並べ替える。Ｐも、表の形態において与える。
図３は、鍵スケジュール計算を説明する。６４ビットの鍵内容のうち５６ビットのみをこのアルゴリズムにおいて使用する。これらの５６ビットを、ランダムに選択すべきである。８個の補足するエラー検出ビットを使用し、前記鍵の各々のビットを部分的に余りにする。前記５６ビットの選択を、並べ替えと共にボックスＰＣ１において行う。その結果を、２つのビットワードＣ₀およびＤ₀に分割する。各々のラウンド毎に４８鍵ビットを得るために、最初にワードＣ₀およびＤ₀を左に１回または２回シフトする。次に、選択および並べ替えＰＣ２をこの結果に用いる。ＰＣ２の出力は、ｆ（Ｒ₀，Ｋ₁）に使用する４８ビットサブ鍵Ｋ₁である。前記シフト、選択および並べ替えのプロセスを繰り返し、各々のラウンド毎にサブ鍵を発生する。表は、その後のラウンドのサブ鍵の次の４８ビットを得るためにどの位多くのシフトを行わなければならないかを明示する。
同じアルゴリズムおよび鍵を、暗号テキストの暗号復号化に使用することができる。暗号復号化に対する最初の並べ替えは、暗号化の逆並べ替えを取り消す。各々のラウンドは、いわゆるFeistel暗号から成り立つ。Feistel暗号に関して、逆の演算は、暗号化に対して使用したのと同じラウンドを使用するが、前記サブ鍵を逆の順序で用いることから成り立つことが知られている。このように、第１の復号化ラウンドには、第１６の暗号化ラウンドに使用したのと同じサブ鍵を供給しなければならず、第２の復号化ラウンドには、第１５の暗号化ラウンドに使用したのと同じサブ鍵を供給しなければならない、等である。どのようにＤＥＳアルゴリズムを暗号フィードバックモードのような他の暗号化モードにおいて使用できるかも既知である。このモードにおいて、ＤＥＳアルゴリズムを使用し、統計的にランダムのバイナリビットのストリームを発生し、これらを、例えば、排他的論理和を使用して前記プレーンテキストに結合する。
ＤＥＳアルゴリズムは、本質的に、最初の並べ替えを具え、データの一部における１６の鍵依存計算が続き、逆並べ替えによって終了する。各々の鍵依存計算は、鍵依存ビットの前記データ部分への（２を法とする）加算を具え、前記データ部分のサブブロックにおける非線形演算が続き、前記データ部分の並べ替え（線形演算）によって終了する。
一般的に、ＤＥＳは、良好な暗号化／暗号復号化ツールであると考えられる。しかしながら、特に、最近の極めて強力な差別的な暗号解読攻撃にかんがみて、ＤＥＳが長年に渡り安全であったかどうかは未解決の問題である。
本発明の目的は、暗号解読攻撃に対してより堅牢な、上述した種類の暗号方法および装置を提供することである。
この目的を達成するために、本発明による暗号方法は、前記結合ステップを、前記選択された部分Ｍ１および第１鍵Ｋ１を、１つの逐次的に分離できないステップにおいて非線形的に結合する非線形関数ｇを実行することによって行うことを特徴とする。図２に示すようなＤＥＳシステムにおいて、第１の処理ステップにおいて、前記Ｒデータを前記鍵にビット幅加算し、その結果（Ｓボックス）を非線形的に処理する第２の処理ステップが続く。本発明によれば、データを鍵に１つのステップ（すなわち、１つの逐次的に分離できないステップ）において結合するアルゴリズムを使用する。このように、前記鍵ビットの前記データへの加算は、非線形演算の１つに統合された部分となり、システムを、差別的な暗号解読のような最近の攻撃に対して、より免疫性にする。
従属の請求の範囲２に規定される本発明による方法の１実施形態において、各々のラウンドにおいて、前記ディジタル入力ブロックの双方の部分を処理し、これは、各々のラウンド中に前記ディジタル入力ブロックの半分のみを処理する、ＤＥＳのような慣例的なFeistel暗号に対するよりも良い暗号化結果を与える。同じシステムを暗号化および暗号復号化の双方に使用できることを保証するために、前記データの一方の部分を演算ｇを使用して処理し、他方の半分を逆演算ｇ^-1を使用して処理する。この案を使用することによって、暗号復号化を、同じシステムを使用するが、前記鍵を前記ラウンドと逆の順序で供給する（暗号復号化中、前記第１の非線形ステップに、暗号化中に前記最後の非線形ステップに供給した鍵を供給する、等）ことによって行う。２倍多くのラウンドを使用するFeistel暗号の慣例的な実現化と比較して、本発明によるシステムはより高速である。
従属の請求の範囲３に規定される方法は、例えば６４ビットの比較的より大きいデータブロックおよび鍵を、より小さいサブブロックおよびサブ鍵に分割し、リアルタイム非線形処理を簡単にする。
従属の請求の範囲５に規定される本発明による方法の１実施形態において、定数を使用し、前記暗号化の品質を向上させる。有利に、前記定数をシステム毎に予め決定し、例えば、顧客特定定数を形成する。代わりに、前記定数を、疑似乱数発生器によって発生する。
従属の請求の範囲６に規定の方法は、１ステップにおける前記データサブブロックおよびサブ鍵の非線形結合の方法を与える。加えて、異なった入力は、すべて異なった出力になる。これは、非線形演算が６ビット入力サブブロックを４ビット出力サブブロックに減少し、同じ出力が４つの異なった入力毎に発生するＤＥＳと比較して、暗号解析攻撃に対するシステムの免疫性を増加する。
従属の請求の範囲７に規定される本発明による方法の１実施形態において、定数を使用し、前記暗号化の品質を向上させる。有利に、前記定数をシステム毎に予め決定し、例えば、顧客特定定数を形成する。代わりに、前記定数を、疑似乱数発生器によって発生する。
従属の請求の範囲８に規定の方法は、前記暗号化の品質をさらに向上させる。
従属の請求の範囲１０に規定される本発明による方法の１実施形態において、前記ディジタル入力ブロックの異なった部分に対応する個々のサブブロックを交換し、前記暗号化の品質を改善する。
好適には、サブブロックｍ_iは、８個のデータビットを具える。これは、前記非線形演算が６から４ビットに変換するＤＥＳと比較して、前記非線形演算の品質をさらに改善する。
従属の請求の範囲１１に規定される方法は、ＧＦ（２⁸）における乗算をＧＦ（２⁴）における演算に減少し、より簡単またはより費用効果的な実現化を達成できるようにするという利点を有する。
従属の請求の範囲１２に規定される方法は、ＧＦ（２⁸）における乗算をＧＦ（２⁴）における演算に減少する効率的な方法を与える。
本発明による方法の１実施形態は、βを、ＧＦ（２）に関する既約多項式ｈ（ｘ）＝ｘ⁴＋ｘ³＋ｘ²＋ｘ＋１の根とすることを特徴とする。これは、βに対する好適な選択であり、いわゆる、シフトされた多項式の底の使用を可能にする。
本発明による方法の１実施形態は、ＧＦ（２⁸）の逆関数の計算が、ＧＦ（２⁴）における一組の計算の実行を具えることを特徴とする。ＧＦ（２⁸）における逆演算がＧＦ（２⁴）における演算に減少することによって、より簡単、またはより費用効果的な実現化を達成することができる。
本発明による方法の１実施形態は、前記要素ｂの逆数の計算が、（ａ₀ ²＋ａ₀ａ₁＋ａ₁ ²β）^-1（（ａ₀＋ａ₁）＋ａ₁Ｄ）の計算を具えることを特徴とする。これは、ＧＦ（２⁸）における逆演算をＧＦ（２⁴）における演算に減少する効率的な方法である。
本発明による方法の１実施形態は、前記第１鍵Ｋ１が６４ビットデータを具え、前記サブ鍵ｋ_iの各々が８データビットを具えることを特徴とする。大きな鍵を使用することによって、前記暗号化の品質は向上する。
本発明の目的を達成するために、本発明による装置は、前記暗号処理方法を、前記結合を前記選択された部分Ｍ１および第１鍵Ｋ１を、１つの逐次的に分離できないステップにおいて非線形的に結合する非線形関数ｇを実行することによって行うように配置したことを特徴とする。
本発明のこれらのおよび他の態様は、図面に示す実施形態の参照から明らかになるであろう。
図１は、ＤＥＳシステムに関する処理ステップを示す。
図２は、データを鍵に結合することと、ＤＥＳにおける非線形演算との詳細を説明する。
図３は、ＤＥＳにおける鍵計算の詳細を説明する。
図４は、暗号装置のブロック図を示す。
図５は、ディジタル入力ブロックの２つの部分の別々の処理を説明する。
図６は、サブブロックの形態におけるディジタル入力ブロックの一部の処理を説明する。
図７は、サブブロックの形態における２つの部分の処理を説明する。
図８は、全体的な暗号システムを示す。
図４は、本発明による暗号装置４００のブロック図を示す。本発明を説明する目的のために、本システムを電子コードブックモードにおいて説明する。当業者は、本システムを他のモードにおいて同様に使用することができるであろう。装置４００は、ディジタル入力ブロックＭを得る第１入力手段４１０を具える。ディジタル入力ブロックＭを、どのような適切なサイズとしてもよい。好適には、Ｍを十分に大きく、例えば１２８ビットとし、適度に安全な暗号結果を得る。装置４００は、前記ディジタル入力ブロックをディジタル出力ブロックに変換する暗号処理手段４２０をさらに具える。有利に、前記ディジタル出力ブロックは、前記ディジタル入力ブロックとほぼ等しい長さを有する。装置４００は、前記ディジタル出力ブロックを出力する出力手段４３０を具える。基本的に、暗号処理手段４２０は、前記ディジタル入力ブロックＭを前記ディジタル出力ブロックに、前記ディジタル入力ブロックＭの選択された部分Ｍ１を第１鍵Ｋ１に結合し、Ｍ１およびＫ１に非線形的に依存するデータブロックＢ１を発生することによって変換する。この結合を、１つの逐次的に分離できないステップにおいて行う。前記ディジタル出力ブロックを、Ｂ１と、Ｍ１の部分でないＭの残りの部分とから得る。第１鍵Ｋ１を得るために、暗号装置４００は、第２入力手段４４０を具える。後により詳細に説明するように、前記ディジタル入力ブロックの第２の部分Ｍ２を、好適には、Ｍ１およびＫ１を結合する演算と逆の演算を使用して第２鍵Ｋ２と非線形的に結合し、データブロックＢ２を発生してもよい。この場合において、前記ディジタル出力ブロックは、Ｂ２にも依存する。第２鍵Ｋ２を得るために、暗号装置４００は、第３入力手段４５０を具える。
暗号装置４００を、ＰＣのような慣例的なコンピュータを使用するか、専用の暗号化／暗号復号化装置を使用して実現してもよいことは明らかであろう。前記ディジタル入力ブロックを、ハードディスクまたはフロッピーディスクのようなデータ記憶媒体から通信ネットワークを経るような、または、ユーザによって直接入力するような種々の方法において得ても良い。同様に、前記ディジタル出力ブロックを、通信ネットワークを経て、データ記憶媒体に格納するか、ユーザに対して表示するような、種々の方法において出力してもよい。好適には、安全な手段をこの目的に使用する。暗号処理手段４２０を、例えば、パーソナルコンピュータにおいて使用されるような慣例的なプロセッサとしてもよいが、専用の暗号プロセッサとしてもよい。暗号装置４００を、部分的または全体的に、スマートカードにおいて実現してもよい。
この文書の残りの部分において、前記暗号変換の詳細を、プレーンテキストの１２８ビットのブロックを、対応する暗号テキストの１２８ビットのブロックに暗号化することについて与えた。当業者は、本システムを他のブロックサイズに同様に使用することができるであろう。図に示すデータサイズは、明瞭にする目的のために与えられており、例としてのみ取り扱うべきである。この説明は、データの非線形処理と、１ラウンドにおいて行われる鍵のデータとの結合とに焦点を合わせている。このように、本発明を、多数のラウンドを具え、各々のラウンドにおいて前記データブロックにおける線形演算を含む、図１に示すようなシステムにおいて使用することができる。
図５に示すように、１２８ビットのメッセージブロックＭを、第１の部分Ｍ１および第２の部分Ｍ２（左および右ブロック）に分割する。好適には、双方の部分を、等しいサイズ、６４ビットのものとする。Ｍ１を、非線形関数ｇを使用して処理する。原理的に、同じラウンド中にＭ２を処理する必要はない。有利に、Ｍ２を、同じラウンド中に逆関数ｇ^-1を使用して処理する。関数ｇおよびｇ^-1の各々は、Ｍ１または各々Ｍ２を、鍵Ｋ１または各々Ｋ２と非線形的に結合する。好適には、前記データ部分および鍵は、同じサイズを有する。大きなデータブロックにおける良好な非線形演算は困難であり、大きなデータブロックにおける非線形処理は時間が掛かることから、データ部分Ｍ１およびＭ２をサブブロックに分割する。図６は、Ｍ１に関するこの分割を説明する。図７は、Ｍ１およびＭ２の分割を説明する。６４ビットデータ部分Ｍ１およびＭ２を使用して、有利に、これらの部分を、８個の８ビット要素に各々分割し、Ｍ１＝（ｍ₀，ｍ₁，．．．，ｍ₇）およびＭ２＝（ｍ₈，ｍ₉，．．．，ｍ₁₅）とする。２つの鍵Ｋ１およびＫ２を、より大きな鍵から、例えば、１２８ビット鍵を２つの６４ビット鍵Ｋ１およびＫ２に分割することによって得る。２つの鍵Ｋ１およびＫ２を、さらに分割してもよい。６４ビット鍵を使用して、有利に、各々の鍵を８ビットサブ鍵に分割し、合計１６個の８ビットサブ鍵ｋ_j，ｊ＝０．．１５を与える。サブ鍵ｋ_jの各々を、対応するサブブロックｍ_jに関連付ける。各々のサブブロックを、別々に処理する。好適には、これらのサブブロックを、並列に処理する。望ましければ、あるラウンドに関係する前記サブブロックを、順次に処理してもよい。Ｍ１を形成する前記サブブロックの第１のグループを、暗号関数ｆによって各々処理する。前記サブブロックの第２のグループを、逆関数ｆ^-1によって各々処理する。
前記暗号演算に関して、ｎビットサブブロックまたはサブ鍵を、ＧＦ（２ⁿ）（ガロア域）の要素を表すと考える。したがって、すべての演算は、ＧＦ（２ⁿ）における。
その基本的な形態において、暗号関数ｆは、図６および７にも説明するように、２つの入力ｍ_jおよびｋ_jと１つの出力ｔ_jとを有し、ここでｊ＝０ないし７に対して、ｔ_j＝ｆ（ｍ_j，ｋ_j）とする。この基本的な形態において、暗号関数ｆは、ｂ_jとほぼ等しいサイズの出力を伴う１つの演算ｈ（ｂ_j，ｋ_j）を含む。関数ｈは、データサブブロックｂ_jおよびサブ鍵ｋ_jを入力として有し、暗号関数ｆのこの基本的な形態に関して、ｂ_j＝ｍ_jとする。関数ｆ（この実施形態において関数ｈと同じ）を、ｊ＝０．．７に関して以下のように規定する。
１．ｈ（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j≠ｋ_jならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、（ｋ_j）^-2
ｋ_j＝０ならば、（ｂ_j）^-2
ｂ_j＝ｋ_jならば、０
同様に、その基本的な形態において、逆暗号関数ｆ^-1は、図６および７にも説明するように、２つの入力ｍ_jおよびｋ_jと１つの出力ｔ_jとを有し、ここでｊ＝８ないし１５に対して、ｔ_j＝ｆ^-1（ｍ_j，ｋ_j）とする。逆暗号関数ｆ^-1も、ｂ_jとほぼ等しいサイズの出力を伴う１つの演算ｈ^-1（ｂ_j，ｋ_j）を含む。関数ｈ^-1をｈの逆関数とする。前のように、暗号関数ｆ^-1のこの基本的な形態において、ｂ_j＝ｍ_jとする。関数ｆ^-1（この実施形態において関数ｈ^-1と同じ）を、ｊ＝８．．１５に関して以下のように規定する。
１．ｈ^-1（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j．ｋ_j ²≠１ならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、ｋ_j
ｋ_j＝０ならば、（ｂ_j）^-1/2
ｂ_j．ｋ_j ²＝１ならば、０
他の実施形態において、暗号関数ｆの出力ｔ_j（ｊ＝０ないし７に関して、ｔ_j＝ｆ（ｍ_j，ｋ_j））および逆暗号関数ｆ^-1の出力（ｊ＝８ないし１５に関して、ｔ_j＝ｆ^-1（ｍ_j，ｋ_j））を以下の方法において交換する。ｔ_j＜−＞ｔ_15-j。これを、図７において説明する。
他の実施形態において、関数ｈを実行する前に、定数を各々のデータサブブロックｍ_jに（２を法とするビット幅）加算する。好適には、８個の別個の定数ｐ_j（ｊ＝１．．７）を使用し、各々を対応するデータサブブロックｍ_jに加算する。前と同じ関数ｈを使用し、ここでは、ｂ_j＝ｍ_j▲＋▼ｐ_jにおいて演算する。暗号関数ｆを、ここで以下のように規定する。
１．ｂ_j＝ｍ_j▲＋▼ｐ_j
２．ｈ（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j≠ｋ_jならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、（ｋ_j）^-2
ｋ_j＝０ならば、（ｂ_j）^-2
ｂ_j＝ｋ_jならば、０
同様に、逆暗号関数ｆ^-1に関しても、定数を各々のデータサブブロックｍ_jに（２を法とするビット幅）加算する。逆関数ｆ^-1を、暗号関数ｆを使用して暗号化されたテキストを暗号復号化するために使用できるようにするために、関数ｈの後、前記定数を加算する。好適には、暗号関数ｆに使用したのと同じ８個の別個の定数ｐ_j（ｊ＝０．．７）を使用する。ここで、定数ｐ_jを、１５−ｊ番目のストリーム（ｊ＝０．．７）に加算する。結果として、逆暗号関数ｆ^-1は、以下の２つの演算を含む（ｊ＝８．．１５）。
１．ｈ^-1（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j．ｋ_j ²≠１ならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、ｋ_j
ｋ_j＝０ならば、（ｂ_j）^-1/2
ｂ_j．ｋ_j ²＝１ならば、０
２．ｔ_j＝ｈ^-1（ｂ_j，ｋ_j）▲＋▼ｐ_15-j
最後に、ｔ_jおよびｔ_15-jを交換する（ｊ＝０．．７）。
他の実施形態において、関数ｈの実行後に、他の定数を各々のデータサブブロックｍ_jに（２を法とするビット幅）加算する。好適には、８個の別個の定数ｄ_j（ｊ＝１．．７）を使用し、各々を対応するデータサブブロックｍ_jに加算する。前と同じ関数ｈを使用する。暗号関数ｆを、ここで以下のように規定する。
１．ｂ_j＝ｍ_j▲＋▼ｐ_j
２．ｈ（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j≠ｋ_jならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、（ｋ_j）^-2
ｋ_j＝０ならば、（ｂ_j）^-2
ｂ_j＝ｋ_jならば、０
３．ｔ_j＝ｈ（ｂ_j，ｋ_j）▲＋▼ｄ_j
同様に、逆暗号関数ｆ^-1に関しても、定数を各々のデータサブブロックｍ_jに（２を法とするビット幅）加算する。逆関数ｆ^-1を、暗号関数ｆを使用して暗号化されたテキストを暗号復号化するために使用できるようにするために、関数ｈの実行前に、前記定数を加算する。好適には、暗号関数ｆに使用したのと同じ８個の別個の定数ｄ_j（ｊ＝０．．７）を使用する。ここで、定数ｄ_jを、１５−ｊ番目のストリーム（ｊ＝０．．７）に加算する。前と同じ関数ｈ^-1を使用し、ここでは、ｂ_j＝ｍ_j▲＋▼ｄ_15-jにおいて演算する。結果として、逆暗号関数ｆ^-1は、以下の３つの演算を含む（ｊ＝８．．１５）。
１．ｂ_j＝ｍ_j▲＋▼ｄ_15-j
２．ｈ^-1（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j．ｋ_j ²≠１ならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、ｋ_j
ｋ_j＝０ならば、（ｂ_j）^-1/2
ｂ_j．ｋ_j ²＝１ならば、０
３．ｔ_j＝ｈ^-1（ｂ_j，ｋ_j）▲＋▼ｐ_15-j
最後に、ｔ_jおよびｔ_15-jを交換する（ｊ＝０．．７）。定数ｐ_jを使用せずに定数ｄ_jを使用することもできることは、明らかであろう。
他の実施形態において、暗号関数ｆは、関数ｈの結果を自乗する。前と同じ関数を使用する。暗号関数ｆを、ここで以下のように規定する。
１．ｂ_j＝ｍ_j▲＋▼ｐ_j
２．ｈ（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j≠ｋ_jならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、（ｋ_j）^-2
ｋ_j＝０ならば、（ｂ_j）^-2
ｂ_j＝ｋ_jならば、０
３．ｓ_j＝ｈ（ｂ_j，ｋ_j）²⁺ⁱ
４．ｔ_j＝ｓ_j▲＋▼ｄ_j
同様に、暗号関数ｆ^-1も、データサブブロックを自乗する。逆関数ｆ^-1を、暗号関数ｆを使用して暗号化されたテキストを暗号復号化するために使用できるようにするために、関数ｈの実行前に、前記加算演算を行う。前と同じ関数ｈ^-1を使用し、ここでは、ｂ_j＝ｍ_j▲＋▼ｄ_15-jにおいて演算する。結果として、逆暗号関数ｆ^-1は、以下の４つの演算を含む（ｊ＝８．．１５）。
１．ｑ_j＝ｍ_j▲＋▼ｄ_15-j
２．ｂ_j＝ｑ_j ^2+(j-7)
３．ｈ^-1（ｂ_j，ｋ_j）＝
ｂ_j≠０，ｋ_j≠０かつｂ_j．ｋ_j ²≠１ならば、（ｂ_j．ｋ_j）^-1
ｂ_j＝０ならば、ｋ_j
ｋ_j＝０ならば、（ｂ_j）^-1/2
ｂ_j．ｋ_j ²＝１ならば、０
４．ｔ_j＝ｈ^-1（ｂ_j，ｋ_j）▲＋▼ｐ_15-j
最後に、ｔ_jおよびｔ_15-jを交換する（ｊ＝０．．７）。定数ｄ_jおよびｐ_jの一方または双方を使用せずに、自乗の演算を使用することもできることは、明らかであろう。
暗号復号化のために、暗号化に使用したのと同じアルゴリズムを使用するが、前記サブ鍵を交換し、ｋ_jの代わりにｋ_15-jを使用し、ｊ＝０．．１５とする。
ＧＦ（２⁸）における乗算
原理的に、本発明に関して、ＧＦ（２⁸）におけるどのような乗算を使用してもよい。ＧＦ（２^m）におけるＶＬＳＩ実現化の一例は、［P. A. Scott,“A fast VLSI multiplier for GF(2^m)”, IEEE Journal on selected areas in communications, Vol. SAC-4, No.1, January 1986, pages 62-66］において与えられる。有利に、以下の方法を使用し、ＧＦ（２^m）ⁿにおける乗算をＧＦ（２⁴）における乗算および加算の列に減少する。
ＧＦ（２⁴）において、βをβ⁵＝１の自明でない根とする（自明でないとはβ≠１を意味し、または、等しく、ｘ⁵＋１＝（ｘ＋１）（ｘ⁴＋ｘ³＋ｘ²＋ｘ＋１）から、βをＧＦ（２）に関する既約多項式ｈ（ｘ）＝ｘ⁴＋ｘ³＋ｘ²＋ｘ＋１の根とする）。底β、β²、β⁴、β⁸を、ＧＦ（２⁴）における底として選択する。多項式β⁸＝β³に従うことから、これは、いわゆるシフトされた多項式底β、β²、β³、β⁴と同じである。
Ｄを、ＧＦ（２⁴）に関する既約多項式ｈ（ｘ）＝ｘ²＋ｘ＋βの根として規定されるＧＦ（２⁸）の要素とする。ＧＦ（２⁸）のすべての要素を、ａ₀＋ａ₁．Ｄとして表すことができ、ａ₀およびａ₁をＧＦ（２⁴）の要素とする。バイナリ用語において、ＧＦ（２⁸）の数ｂを、ベクトル（ａ₀，ａ₁）として配置された８ビットを使用して表すことができ、ａ₀，ａ₁は、ＧＦ（２⁴）の数を表す４ビットを有する。このように、ＧＦ（２⁸）における底は、β、β²、β³、β⁴、Ｄβ、Ｄβ²、Ｄβ³、Ｄβ⁴である。ａ_i∈ＧＦ（２⁴）として、ｂ＝ａ₀＋ａ₁．Ｄおよびｃ＝ａ₂＋ａ₃．Ｄとして表され、ＧＦ（２⁸）の２つの要素ｂおよびｃを、
ｂ．ｃ＝（ａ₀＋ａ₁．Ｄ）．（ａ₂＋ａ₃．Ｄ）
＝ａ₀ａ₂＋（ａ₁ａ₂＋ａ₀ａ₃）．Ｄ＋ａ₁ａ₃．Ｄ²
のように乗算することができる。Ｄがｋ（ｘ）の根であり、Ｄ²＝Ｄ＋βを意味するという事実を利用して、これは、乗算結果、
ｂ．ｃ＝（ａ₀ａ₂＋ａ₁ａ₃β）＋（ａ₁ａ₂＋ａ₀ａ₃＋ａ₁ａ₃）．Ｄ
を与える。これは、ＧＦ（２⁸）の２つの要素の乗算を、ＧＦ（２⁴）における乗算および加算の列に減少している。
ＧＦ（２⁸）における逆
原理的に、どのような既知の方法を使用してＧＦ（２⁸）における要素の逆を計算してもよい。有利に、前の方法を使用してＧＦ（２⁸）における乗算をＧＦ（２⁴）における乗算に減少し、次に以下の方法を使用してＧＦ（２⁸）における逆演算をＧＦ（２⁴）における逆演算に減少する。
ＧＦ（２⁸）における要素ｂの逆ｂ^-1は、ａ_i∈ＧＦ（２⁴）として、ｂをｂ＝ａ₀＋ａ₁．Ｄとして表し、
ｂ^-1．ｂ＝（ａ₀ ²＋ａ₀ａ₁＋ａ₁ ²β）^-1．（ａ₀＋ａ₁＋ａ₁Ｄ）
．（ａ₀＋ａ₁Ｄ）
＝（ａ₀ ²＋ａ₀ａ₁＋ａ₁ ²β）^-1．（ａ₀ ²＋ａ₀ａ₁
＋ａ₁ ²Ｄ＋ａ₁ ²Ｄ²）
であり、Ｄ²＋Ｄ＝βで、これは、ｂ^-1．ｂ＝１を与えることから、
ｂ^-1＝（ａ₀ ²＋ａ₀ａ₁＋ａ₁ ²β）^-1．（ａ₀＋ａ₁＋ａ₁Ｄ）
によって与えられる。この方法において、ＧＦ（２⁸）における逆演算を、ＧＦ（２⁴）における逆演算と、ＧＦ（２⁴）における乗算および加算の列とに減少する。
ＧＦ（２⁴）における乗算
原理的に、ＧＦ（２⁴）におけるどのような乗算を使用してもよい。有利に、上述したように、シフトされた多項式底β、β²、β³、β⁴をＧＦ（２⁴）における底として選択し、ここでβをＧＦ（２）に関する既約多項式ｈ（ｘ）＝ｘ⁴＋ｘ³＋ｘ²＋ｘ＋１の根とし、β⁵＝１とする。βをｈの根とし、これは、β⁴＋β³＋β²＋β＝１を意味する。これらの底要素をｅ₁、ｅ₂、ｅ₃およびｅ₄と名付け、ｅ_i＝βⁱとし、これらの底要素を、βの定義を使用して、
ｅ₁．ｅ₁＝β．β＝β²＝ｅ₂
ｅ₁．ｅ₂＝β．β²＝β³＝ｅ₃
ｅ₁．ｅ₃＝β．β³＝β⁴＝ｅ₄
ｅ₁．ｅ₄＝β．β⁴＝β⁵＝１＝ｅ₁＋ｅ₂＋ｅ₃＋ｅ₄
ｅ₂．ｅ₂＝β²．β²＝β⁴＝ｅ₄
ｅ₂．ｅ₃＝β²．β³＝β⁵＝１＝ｅ₁＋ｅ₂＋ｅ₃＋ｅ₄
ｅ₂．ｅ₄＝β²．β⁴＝β⁶＝β＝ｅ₁
ｅ₃．ｅ₃＝β³．β³＝β⁶＝β＝ｅ₁
ｅ₃．ｅ₄＝β³．β⁴＝β⁷＝β²＝ｅ₂
ｅ₄．ｅ₄＝β⁴．β⁴＝β⁸＝β³＝ｅ₃
のように乗算する。これは、原理的に、ＧＦ（２⁴）における乗算を規定する。バイナリにおいて、前記乗算を、以下のように考えることができる。前記底に関して、ＧＦ（２⁴）における各々の要素ｂを、ｂ_i∈ＧＦ（２）として、ｂ＝ｂ₀ｅ₁＋ｂ₁ｅ₂＋ｂ₂ｅ₃＋ｂ₃ｅ₄として表すことができる。このように、要素ｂを、バイナリ成分（ｂ₀，ｂ₁，ｂ₂，ｂ₃）を有する４次元ベクトルによって表すことができる。マイクロプロセッサにおいて、これを、ニブルを使用して表すことができる。バイナリにおいて、ＧＦ（２⁴）における２つの要素ｂおよびｃの乗算を、これら２つの要素をｂ＝（ｂ₀，ｂ₁，ｂ₂，ｂ₃）およびｃ＝（ｃ₀，ｃ₁，ｃ₂，ｃ₃）によって表すとして、以下のように考えることができる。通常の方法におけるこれら２つの要素の乗算は、
ｂ．ｃ＝（ｂ₀ｃ₀）β²＋（ｂ₀ｃ₁＋ｂ₁ｃ₀）β³＋（ｂ₀ｃ₂
＋ｂ₁ｃ₁＋ｂ₂ｃ₀）β⁴＋（ｂ₀ｃ₃＋ｂ₁ｃ₂十ｂ₂ｃ₁
＋ｂ₃ｃ₀）β⁵＋（ｂ₁ｃ₃＋ｂ₂ｃ₂＋ｂ₃ｃ₁）β⁶
＋（ｂ₂ｃ₃＋ｂ₃ｃ₂）β⁷＋（ｂ₃ｃ₃）β⁸
を与える。β⁵をβ⁴＋β³＋β²＋βと交換し、β⁶をβと交換し、β⁷をβ²と交換し、β⁸をβ³と交換するβの定義を使用することは、以下の４つの成分、
ｂ．ｃ＝（ｂ₁ｃ₃＋ｂ₂ｃ₂＋ｂ₃ｃ₁＋ｂ₀ｃ₃＋ｂ₁ｃ₂＋ｂ₂ｃ₁
＋ｂ₃ｃ₀）β＋（ｂ₀ｃ₀＋ｂ₂ｃ₃＋ｂ₃ｃ₂＋ｂ₀ｃ₃
＋ｂ₁ｃ₂＋ｂ₂ｃ₁＋ｂ₃ｃ₀）β²＋（ｂ₀ｃ₁＋ｂ₁ｃ₀
＋ｂ₃ｃ₃＋ｂ₀ｃ₃＋ｂ₁ｃ₂＋ｂ₂ｃ₁＋ｂ₃ｃ₀）β³
＋（ｂ₀ｃ₂＋ｂ₁ｃ₁＋ｂ₂ｃ₀＋ｂ₀ｃ₃＋ｂ₁ｃ₂＋ｂ₂ｃ₁
＋ｂ₃ｃ₀）β⁴
を与える。したがって、この乗算のバイナリにおける結果は、
ｂ．ｃ＝（ｂ₁ｃ₃＋ｂ₂ｃ₂＋ｂ₃ｃ₁＋ｂ₀ｃ₃＋ｂ₁ｃ₂＋ｂ₂ｃ₁
＋ｂ₃ｃ₀，ｂ₀ｃ₀＋ｂ₂ｃ₃＋ｂ₃ｃ₂＋ｂ₀ｃ₃＋ｂ₁ｃ₂
＋ｂ₂ｃ₁＋ｂ₃ｃ₀，ｂ₀ｃ₁＋ｂ₁ｃ₀＋ｂ₃ｃ₃＋ｂ₀ｃ₃
＋ｂ₁ｃ₂＋ｂ₂ｃ₁＋ｂ₃ｃ₀，ｂ₀ｃ₂＋ｂ₁ｃ₁＋ｂ₂ｃ₀
＋ｂ₀ｃ₃＋ｂ₁ｃ₂＋ｂ₂ｃ₁＋ｂ₃ｃ₀）
によって与えられる。
ＧＦ（２⁴）における逆演算
基底β、β²、β⁴、β⁸を使用して、ＧＦ（２⁴）の各々の要素ｘを、ａ、ｂ、ｃ、ｄ∈ＧＦ（２）として、ｂ＝ａ．β＋ｂ．β²＋ｃ．β⁴＋ｄ．β⁸と書くことができる。このように、各々の要素を、４次元ベクトル（ａ，ｂ，ｃ，ｄ）によって表すことができる。
ｂの逆数（ｂ^-1）を得るために、
− 以下の中間結果、

を計算し、ここで、ａｂをａおよびｂのバイナリＡＮＤ（ａＡＮＤｂ）とし、

を（ＮＯＴａ）のバイナリ成分とし、

のように使用することによって、ｂ^-1の第１ビットを計算し、

のように使用することによって、ｂ^-1の第２ビットを計算し、

のように使用することによって、ｂ^-1の第３ビットを計算し、

のように使用することによって、ｂ^-1の第４ビットを計算する。
図１に示すようなＤＥＳのようなシステムにおいて使用するのに加えて、専用のシステムを、本発明の非線形アルゴリズムの周囲に組み立てることができるこのようなシステムを、図８において示す。このシステムにおいて、前記ブロックを、本発明の非線形演算ＮＬと、線形演算ＬＩＮとを使用して処理する。前記第１ステップは、非線形演算である。これに、線形演算の繰り返しを続け、非線形演算を続ける。線形演算が前記データビットを完全に混合するならば、十分に安全なシステムを、６つの非線形演算を実行することによって達成することが期待される。好適には、１５ラウンドを使用する。これらの線形演算の各々は、同じである。また、前記非線形演算の各々も同じであるが、各々の非線形演算は、１２８ビットの異なった鍵を使用する。有利に、鍵を、例えば、２５６ビットの１つの包括的な鍵から、鍵スケジュール計算を使用して得る。同じ鍵を、暗号化と暗号復号化とに使用する。大部分の場合において、前記鍵を、スマートカードを使用して与える。前記線形演算に関して、有利に、順列の代わりに、より複雑なマトリックスを使用する。上述したように、前記鍵に加えて、各々の非線形演算は、定数ｐ_jおよびｄ_jに分割する１２８ビットの定数Ｃを任意に使用してもよい。この定数を、各々の演算に対して同じにしてもよい。有利に、各々の非線形演算に、別々の定数を与える。これらの定数を、システムごとに予め決めてもよい（例えば、顧客特定定数）。代わりに、前記定数を、擬似乱数発生器を使用して発生する。

Claims

ディジタル入力ブロックをディジタル出力ブロックに暗号的に変換する方法であって、前記変換が、前記ディジタル入力ブロックの選択された第１の部分Ｍ１を第１鍵Ｋ１と結合し、前記選択された第１の部分Ｍ１および第１鍵Ｋ１に非線形的に依存するデータブロックＢ１を発生するステップを実行するための暗号処理手段を使用するステップを具え、前記暗号処理手段を使用して、前記ディジタル出力ブロックの選択された部分が前記データブロックＢ１から得られる方法において、
前記第１の部分Ｍ１を第１鍵Ｋ１と結合するステップが、前記選択された第１の部分Ｍ１および第１鍵Ｋ１を、１つの順次分離できないステップにおいて非線形的に結合するためのアルゴリズムを使用する非線形関数ｇを実行することによって行われることを特徴とする方法。
請求の範囲１に請求の方法において、該方法が、
− 前記結合するステップを実行する前に、前記ディジタル入力ブロックを、前記選択された第１の部分Ｍ１と、第２の部分Ｍ２とに分割するステップと、
− 前記ディジタル入力ブロックの第２の部分Ｍ２を第２鍵Ｋ２に１つの順次分離できないステップにおいて結合するためのアルゴリズムを使用する非線形関数ｇ^-1を実行し、データブロックＢ２を出力として発生し、前記非線形関数ｇ^-1 は前記非線形関数ｇの逆関数になるステップと、
− 前記データブロックＢ１におけるデータと前記データブロックＢ２におけるデータとから結合されたデータを形成し、前記ディジタル出力ブロックは前記結合されたデータから得られるステップと
を実行するための暗号処理手段を使用するステップを有する方法。
請求の範囲１に請求の方法において、前記非線形関数ｇを実行する前記結合するステップが、
− 前記選択された第１の部分Ｍ１を、等しい長さの第１の複数ｎのサブブロックｍ₀,..，ｍ_n-1に分割するステップと、
− 前記第１鍵Ｋ１を、等しい長さを有する第１の複数ｎのサブ鍵ｋ₀,..，ｋ_n-1に分割し、前記サブ鍵ｋ_iがｉ＝０ないしｎ−１に対して前記サブブロックｍ_iに対応するステップと、
− ｂ _i ＝ｍ _i とすることによって、前記サブブロックｍ _i の各々からサブブロックｂ _i を得るステップと、
− 前記サブブロックｍ_iの各々を、前記サブブロックｍ_iの各々に対して、前記サブブロックｍ_iから得られた前記サブブロックｂ_iを前記対応するサブ鍵ｋ_iに１つの順次分離できないステップにおいて一つのステップで非線形的に結合するアルゴリズムを使用する同じ非線形関数ｈを実行することによって別々に処理し、前記第１の複数の出力サブブロックｈ（ｂ_i，ｋ_i）を発生するステップと、
− ｔ _i ＝ｈ（ｂ _i ，ｋ _i ）とすることによって、前記第１の複数ｎの前記出力サブブロックｈ（ｂ _i ，ｋ _i ）からサブブロックｔ _i を得るステップと、
− 前記第１の複数ｎの前記出力サブブロックｈ（ｂ_i，ｋ_i）から得られる前記サブブロックｔ_iを結合し、前記データブロックＢ１を形成するステップとを具えることを特徴とする方法。
請求の範囲２または３に請求の方法において、前記非線形関数ｇ^-1を実行するステップが、
− 前記第２の部分Ｍ２を、等しい長さを有する第１の複数ｎのサブブロックｍ_n,..，ｍ_2n-1に分割するステップと、
− 前記第２鍵Ｋ２を、等しい長さを有する前記第１の複数ｎのサブ鍵ｋ_n,..，ｋ_2n-1に分割し、前記サブ鍵ｋ_iがｉ＝ｎないし２ｎ−１に対して前記サブブロックｍ_iに対応するステップと、
− ｂ _i ＝ｍ _i とすることによって、ｉ＝ｎないし２ｎ−１に対して、前記サブブロックｍ _i の各々からサブブロックｂ _i を得るステップと、
− ｉ＝ｎないし２ｎ−１に対して、前記サブブロックｍ_iの各々に対して、前記サブブロックｍ_iから得られた前記サブブロックｂ_iを前記対応するサブ鍵ｋ_iに１つのステップにおいて非線形的に結合すると共に前記第１の複数の出力サブブロックｈ^-1（ｂ_i，ｋ_i）を発生させるためのアルゴリズムを使用する同じ非線形関数ｈ ^-1 を実行し、前記関数ｈ^-1 は前記関数ｈの逆関数になるステップと、
− ｔ _i ＝ｈ ^-1 （ｂ _i ，ｋ _i ）とすることによって、ｉ＝ｎないし２ｎ−１に対して、前記第１の複数ｎの前記出力サブブロックｈ ^-1 （ｂ _i ，ｋ _i ）からサブブロックｔ _i を得るステップと、
− ｉ＝ｎないし２ｎ−１に対して、前記第１の複数ｎの前記出力サブブロックｈ^-1（ｂ_i，ｋ_i）から得られた前記サブブロックｔ_iを結合し、前記データブロックＢ２を形成するステップと
を具えることを特徴とする方法。
請求の範囲３に請求の方法において、所定の定数ｐ_iを各々の前記サブブロックｍ_iに２を法としてビット加算することによって、前記サブブロックｂ _i は前記サブブロックｍ _i から得られ、前記定数ｐ_iが前記サブブロックｍ_iと等しい長さを有することを特徴とする方法。
請求の範囲３に請求の方法において、前記関数ｈ（ｂ_i，ｋ_i）は、
ｂ_j≠０，ｋ_j≠０かつｂ_j≠ｋ_jならば、ｈ（ｂ_j，ｋ_j）＝（ｂ_j，ｋ_j）^-1
ｂ_j＝０ならば、ｈ（ｂ_j，ｋ_j）＝（ｋ_j）^-2
ｋ_j＝０ならば、ｈ（ｂ_j，ｋ_j）＝（ｑ_j）^-2
ｂ_j＝ｋ_jならば、ｈ（ｂ_j，ｋ_j）＝０
によって規定され、前記ｈ（ｂ _j ，ｋ _j ）を規定する乗算および逆演算が、所定のガロア域乗算および逆演算になることを特徴とする方法。
請求の範囲６に請求の方法において、前記サブブロックｔ_iを前記出力サブブロックｈ（ｂ_i，ｋ_i）から得るステップが、所定の定数ｄ_iを各々の前記出力サブブロックｈ（ｂ_i，ｋ_i）に２を法としてビット加算するステップを具え、前記定数ｄ_i は前記サブブロックｍ_iとほぼ等しい長さを有することを特徴とする方法。
請求の範囲７に請求の方法において、前記サブブロックｔ_iを前記出力サブブロックｈ（ｂ_i，ｋ_i）から得るステップが、前記所定のガロア域乗算を使用して、ｈ（ｂ_i，ｋ_i）＋ｄ_iを２ⁱ乗するステップをさらに具えることを特徴とする方法。
請求の範囲６に請求の方法において、前記サブブロックｔ_iを前記出力サブブロックｈ（ｂ_i，ｋ_i）から得るステップが、前記所定のガロア域（ＧＦ）乗算を使用して、前記出力サブブロックｈ（ｂ_i，ｋ_i）を２ⁱ乗するステップを具えることを特徴とする方法。
請求の範囲４に請求の方法において、前記結合されたデータは、
− 前記サブブロックｔ_iおよびｔ_2n-1-iをｉ＝０ないしｎ−１に関して交換するステップと、
− これらの交換されたサブブロックを連結するステップと
によって形成されることを特徴とする方法。
請求の範囲６に請求の方法において、前記サブブロックｍ_i は、８データビットを具え、前記ＧＦ（２⁸）の２つの要素ｂ _i 及びｋ _i の乗算ステップが、ＧＦ（２⁴）における乗算および加算の列を実行するステップを具え、ＧＦ（２ ⁴ ）は２ ⁴ 要素でのガロア域を示すことを特徴とする方法。
請求の範囲１１に請求の方法において、前記２つの要素ｂ _i 及びｋ _iの乗算ステップが、
− ｂ _iをａ₀＋ａ₁．Ｄとして表し、ｋ _iをａ₂＋ａ₃．Ｄとして表し、ａ₀、ａ₁、ａ₂およびａ₃ はＧＦ（２⁴）の要素であり、Ｄは、ＧＦ（２⁴）に関する既約多項式ｈ（ｘ）＝ｘ²＋ｘ＋βの根として規定されるＧＦ（２⁸）の要素であり、βはＧＦ（２⁴）の要素であるステップと、
− （ａ₀ａ₂＋ａ₁ａ₃β）＋（ａ₁ａ₂＋ａ₀ａ₃＋ａ₁ａ₃）．Ｄを計算するステップと
を具えることを特徴とする方法。
請求の範囲１２に請求の方法において、βは、ＧＦ（２）に関する既約多項式ｈ（ｘ）＝ｘ⁴＋ｘ³＋ｘ²＋ｘ＋１の根であることを特徴とする方法。
請求の範囲６に請求の方法において、前記サブブロックｍ_iが８データビットを具え、前記ＧＦ（２⁸）の要素ｂ _i ｋ _i 又はｋ _i ² 若しくはｑ _i ²の逆数を計算するステップが、ＧＦ（２⁴）における計算の列を実行するステップを具え、前記ＧＦ（２ ⁴ ）は２ ⁴ 要素でのガロア域を示すことを特徴とする方法。
請求の範囲１４に請求の方法において、前記要素ｂ _i ｋ _i 又はｋ _i ² 若しくはｑ _i ²の逆数を計算するステップが、
− 前記要素ｂ _i ｋ _i 又はｋ _i ² 若しくはｑ _i ²をａ₀＋ａ₁．Ｄとして表し、ａ₀およびａ₁ はＧＦ（２⁴）の要素であり、Ｄは、ＧＦ（２⁴）に関する既約多項式ｈ（ｘ）＝ｘ²＋ｘ＋βの根として規定されるＧＦ（２⁸）の要素であり、βはＧＦ（２⁴）の要素であるステップと、
− （ａ₀ ²＋ａ₀ａ₁＋ａ₁ ²β）^-1（（ａ₀＋ａ₁）＋ａ₁Ｄ）を計算するステップと
を具えることを特徴とする方法。
ディジタル入力ブロックをディジタル出力ブロックに暗号的に変換する装置であって、
前記ディジタル入力ブロックを得る第１入力手段と、
第１鍵Ｋ１を得る第２入力手段と、
前記ディジタル入力ブロックを前記ディジタル出力ブロックに変換する暗号処理手段であって、前記変換が、前記ディジタル入力ブロックの選択された第１の部分Ｍ１を前記第１鍵Ｋ１と結合するステップと、前記選択された第１の部分Ｍ１および第１鍵Ｋ１に非線形的に依存するデータブロックＢ１を発生するステップとを具え、前記ディジタル出力ブロックの選択された部分が前記データブロックＢ１から得られる、暗号処理手段と、
前記ディジタル出力ブロックを出力する出力手段と
を具える装置において、前記暗号処理手段は、前記選択された第１の部分Ｍ１を第１鍵Ｋ１に、１つの順次分離できないステップにおいて非線形的に結合するためのアルゴリズムを使用する非線形関数ｇを実行することによって前記結合するステップを行うことを特徴とする装置。
請求の範囲１６に請求の装置において、該装置が、第２鍵Ｋ２を得る第３入力手段を具え、前記変換が、
− 前記結合するステップを行う前に、前記ディジタル入力ブロックを、前記選択された第１の部分Ｍ１と、第２の部分Ｍ２とに分割するステップと、
− 前記ディジタル入力ブロックの第２の部分Ｍ２を第２鍵Ｋ２に１つの順次分離できないステップにおいて結合するためのアルゴリズムを使用する非線形関数ｇ^-1を実行し、データブロックＢ２を出力として発生し、前記非線形関数ｇ^-1 は前記非線形関数ｇの逆関数になるステップと、
− 前記データブロックＢ１におけるデータと前記データブロックＢ２におけるデータとから結合されたデータを形成するステップと
を具え、前記ディジタル出力ブロックは前記結合されたデータから得られるようにしたことを特徴とする装置。
請求の範囲１６に請求の装置において、前記第１の部分Ｍ１を第１鍵Ｋ１と結合するステップが、
− 前記選択された第１の部分Ｍ１を、等しい長さの第１の複数ｎのサブブロックｍ₀,..，ｍ_n-1に分割するステップと、
− 前記第１鍵Ｋ１を、等しい長さを有する第１の複数ｎのサブ鍵ｋ₀,..，ｋ_n-1に分割し、前記サブ鍵ｋ_iがｉ＝０ないしｎ−１に対して前記サブブロックｍ_iに対応するステップと、
− ｂ _i ＝ｍ _i とすることによって、前記サブブロックｍ _i の各々からサブブロックｂ _i を得るステップと、
− 前記サブブロックｍ_iの各々を、前記サブブロックｍ_iの各々に対して、前記サブブロックｍ_iから得られたサブブロックｂ_iを前記対応するサブ鍵ｋ_iに１つの順次分離できないステップにおいて一つのステップで非線形的に結合するアルゴリズムを使用する同じ非線形関数ｈを実行することによって別々に処理し、前記第１の複数の出力サブブロックｈ（ｂ_i，ｋ_i）を発生するステップと、
− ｔ _i ＝ｈ（ｂ _i ，ｋ _i ）とすることによって、前記第１の複数ｎの前記出力サブブロックｈ（ｂ _i ，ｋ _i ）からサブブロックｔ _i を得るステップと、
− 前記第１の複数ｎの前記出力サブブロックｈ（ｂ_i，ｋ_i）から得られるサブブロックｔ_iを結合し、前記データブロックＢ１を形成するステップと
を具えることを特徴とする装置。
請求の範囲１８に請求の装置において、前記関数ｈ（ｂ_i，ｋ_i）は、
ｂ_j≠０，ｋ_j≠０かつｂ_j≠ならばＫ_j、ｈ（ｂ_j，ｋ_j）＝（ｂ_j，ｋ_j）^-1
ｂ_j＝０ならば、ｈ（ｂ_j，ｋ_j）＝（ｋ_j）^-2
ｋ_j＝０ならば、ｈ（ｂ_j，ｋ_j）＝（ｂ_j）^-2
ｂ_j＝ｋ_jならば、ｈ（ｂ_j，ｋ_j）＝０
によって規定され、前記ｈ（ｂ _j ，ｋ _j ）を規定する乗算および逆演算が、所定のガロア域乗算および逆演算になることを特徴とする装置。
請求の範囲１９に請求の装置において、前記サブブロックｍ_iが８データビットを具え、前記ＧＦ（２⁸）の２つの要素ｂ _i 及びｋ _iの乗算ステップが、
− ｂ _iをａ₀＋ａ₁．Ｄとして表し、ｋ _iをａ₂＋ａ₃．Ｄとして表し、ａ₀、ａ₁、ａ₂およびａ₃ はＧＦ（２⁴）の要素であり、Ｄは、ＧＦ（２⁴）に関する既約多項式ｈ（ｘ）＝ｘ²＋ｘ＋βの根として規定されるＧＦ（２⁸）の要素であり、βはＧＦ（２⁴）の要素であるステップと、
− （ａ₀ａ₂＋ａ₁ａ₃β）＋（ａ₁ａ₂＋ａ₀ａ₃＋ａ₁ａ₃）．Ｄを計算するステップと
を具え、
前記ＧＦ（２⁸）の要素ｂ _i ｋ _i 又はｋ _i ² 若しくはｑ _i ²の逆数を計算するステップが、
− （ａ₀ ²＋ａ₀ａ₁＋ａ₁ ²β）（（ａ₀＋ａ₁）＋ａ₁Ｄ）の計算をするステップを具えることを特徴とする装置。