(57)【特許請求の範囲】
【請求項１】
平文ブロックをなす２n個のｎビット２進数のいずれか１つを、暗号化ブロックをなす２n個のｎビット２進数の対応する１つに置換することを行う暗号装置であって：
暗号化ブロックをなす２n個のｎビット２進数であって、平文ブロックをなす２n個のｎビット２進数それぞれでアドレス可能な、暗号化ブロックをなすｎビット２進数を格納するメモリを備え；
平文ブロックをなす２n個のｎビット２進数から、暗号化ブロックをなす２n個のｎビット２進数を導出する非線形換字数式ジェネレータを備え；
（ａ）前記非線形換字数式ジェネレータでは、直交写像を表す２n個の数式の第１の行列Ｇnが用いられ、それらの数式の各々が、左側の列中の２n個の平文ブロックのうちの１つのブロックに対して中央の列中の２n個のｎビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して右側の列中の対応する固有のｎビット・ブロックを与えることを表し、前記２n個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が前記第１の行列中の１つの数式でもあることを特徴とし、前記１つの数式が識別数式Θ▲＋▼Θ＝Θを含み、残りの２n−１個の数式が、次式のように順序付けることができ、
0003701969.tif 000318
上式でｍ＝２n−１であり、Ｌn、Ｍn、Ｒnがそれぞれ、左側、中央、右側の列であるとしてＧn＝Ｌn Ｘ Ｍn Ｘ Ｒnが数式の集合を表し、Ｇn-1が、前記第１の行列Ｇnからの２n-1の数式からなる、Ｇnの部分群であって、Ｇn中の連続したｎ−１個の非零数式の選択によって定まり、それら全ての和と識別数式とによって下記する追加式で定まり、
0003701969.tif 000319
がＧn中のＧn-1の補数であり、Ｇn-1＝Ｌn-1 Ｘ Ｍn-1 Ｘ Ｒn-1であり、
0003701969.tif 000320
であり、Ｗn-1＝Ln-1∩Ｍn-1であり、Ｇn-2が、Ｇn-1中のｎ−２個の数式によって生成されるＧn-1の部分群であり、かつ２n-2個の数式の部分行列であり、
0003701969.tif 000321
が、Ｇn-1中のＧn-2の補数であり、Ｇn-2＝Ｌn-2 Ｘ Ｍn-2 Ｘ Ｒn-2であり、
0003701969.tif 000322
であり、Ｗn-2＝Ｌn-2∩Ｍn-2であり、
0003701969.tif 000323
が、Ｗn-1中のＷn-2の補数であり、類似の部分群がｎ−２ないし２の指数で定義され、
0003701969.tif 000324
であり、ｘ≠ｑであり、Ｗ1＝｛ｑ｝であり、
0003701969.tif 000325
であり、２n-1個の前記追加式は、次式のように順序付けることができ、
0003701969.tif 000326
上式で、ｓ＝２n-1−１であり、
0003701969.tif 000327
が、Ｇn-1には含まれないＧnから得たすべての残りの２n-1個の数式であり、Ｇn-2に対応しては、２n-2個の数式の部分集合であって、Ｇn-1からｎ−２個の連続数式を選択し、それら全ての和と識別数式とによって定まる、２n-2個の数式の部分集合があり、
0003701969.tif 000328
が、Ｇn-2に含まれないＧn-1から得たすべての残りの２n-2個の数式であり、以下連続的に小さくなる各部分群に関して、識別数式とＧ3から得た２つの連続数式とそれらの和とを含む２2＝４個の数式を含むＧ2が選択されるまで、かつ
0003701969.tif 000329
がＧ2を含まないＧ3の４つの数式となるまで、同様であり、
（ｂ）前記非線形換字数式ジェネレータには、２n個の数式の第１の行列中の２n−１個の非零数式のうちの複数の数式を、非線形直交写像を表す２n個の数式の第２の行列を与えるように修正する修正手段が含まれ、修正済みの複数の数式が全体として、左側の列中の平文ブロックを右側の列中の固有の暗号化ｎビット・ブロックに写像するが、各修正済み数式が未修正の第１の集合中のどんな数の数式のｍｏｄ２和にもならないように非線形的に写像するように、前記複数の数式が修正され、２n−１個の非零数式のうちの前記複数の数式の前記修正が、次の手段、すなわち、
Ｗn-2中の２n-3個の混合変換をＧn-1に適用し、
Ｗn-3中の２n-4個の混合変換をＧn-2に適用し、
0003701969.tif 000330
に達するまで混合変換の適用を継続する
手段によって行われ、
（ｃ）暗号化すべき左側の列中の各平文ブロックごとに、２n個の数式の第２の行列の対応する数式に従って中央の列中の前記ブロックに対応する２n個のｎビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して、右側の列中の暗号化ブロックを得るように、２n個の数式の第２の行列が用いられる、
ことを特徴とする、暗号装置。
【請求項２】
請求項１記載の暗号装置において、前記修正手段には、
0003701969.tif 000331
を適用する手段が含まれることを特徴とする暗号装置。
【請求項３】
請求項１記載の暗号装置において、前記修正手段には、
0003701969.tif 000332
にΘを適用する手段が含まれることを特徴とする暗号装置。
【発明の詳細な説明】
関連出願
本出願は、１９８９年１０月４日に出願された米国特許出願第０７／４１６９５３号の一部継続出願である、１９９３年８月５日に出願された米国特許出願第０７／７４１０９７号の一部継続出願である。
発明の背景
１．発明の分野
本発明は、暗号化装置および方法の分野に関し、詳細には、ブロック換字暗号化方法および装置に関する。
２．従来の技術
多くの場合、受信側にとって明確であるが、送信側と受信側の間に割って入る者には分からないように、ある位置から別の場所へディジタル形で情報を伝達することが望ましい。したがって、多くの例では、何らかの所定の暗号化プロセスによって、伝達すべき情報を暗号化し、暗号化された形の情報を送信し、次いで、受信側位置でその情報を復号するのが一般的である。偶然に送信側と受信側に間に入った者にとってはどんなレベルの暗号化でも送信の意味がわからないので、所望のセキュリティの程度に応じて、比較的簡単で容易に破られる暗号化を使用することもできる。他の状況では、所望のセキュリティの程度は、暗号解析によって復号することがより困難な暗号化技法を使用するものであり、あるいは、最高のレベルのセキュリティで、復号がほぼ不可能になることが望ましい。そのような暗号化技法の応用例には、製造工場、銀行支店など間の機密通信などの商業応用例と、ＩＦＦ（敵味方識別装置）を含むが、これに限らない軍事応用例が含まれる。あるケースでは、暗号化の主要な目的は、第３者が通信中の情報を復号することを妨げることであるが、他のケース、すなわちＩＦＦなどでの主要な目的は、第３者が、所期の受信側を誤らせるように同じ暗号化方式で擬情報を発信するのを妨げることである。多くの応用例では、２つの目的が共に存在することが多い。
ブロック換字とは、２進数の列の形の平文メッセージを暗号化するために使用される方法である。この方法によれば、ブロック換字装置が、平文中の各２進数ブロックを新しい固有の２進数ブロックで置き換えることによって、列が、いくつかの所定のブロック長ｎのブロックに分割される。換字ブロックは、暗号化メッセージまたは符号テキストを構成し、各換字ブロックは、平文ブロックの明確な１対１の情報を表す。従来技術では、そのような換字は一般に、参照テーブル、スイッチング構成、またはフィードバック・シフト・レジスタによって行われる。しかし、符号または換字方式を頻繁に変更しないと、暗号化が符号解析によって破られることがある。しかし、参照テーブルを変更するのは厄介であり、実施できる可能なスイッチング構成の数は限られており、シフト・レジスタを繰り返し巡回させるのは時間がかかる。パターンもバイアスも有さない換字を見つける際にはそれ以外の問題が発生する。現在、コンピュータ・シミュレーションによって、候補換字が可能な体系的パターンがあるかどうか調べられており、あるケースでは、この問題を補償するために追加回路が使用されている。
従来技術では、様々なタイプの暗号化装置および方法が周知である。たとえば、米国特許第３７９６８３０号、米国特許第３７９８３５９号、米国特許第４０７８１５２号、米国特許第４１９５２００号、米国特許第４２２５８１１号、米国特許第４３１６０５５号、米国特許第４５２０２３２号を参照されたい。一般に、これらのシステムは、ブロック換字に関するものであるとき、鍵依存暗号化・復号化システムであり、本発明とは異なり、ある加算置換済み数の集合と別の加算置換済み数の集合のｍｏｄ（モジュロ）２加算による換字に基づくものではない。
親の親特許出願では、換字方式を比較的簡単なハードウェアと共に使用できるようにするブロック換字技法によるｍｏｄ２加算ベースの暗号化を開示した。このブロック換字は、ｎビット２進数のそれ自体への１対１写像であり、ｎビット２進数のある種の置換によって、ある置換済み数の集合と別の置換済み数の集合のｍｏｄ２加算によるブロック換字が定義されることと、このような定義済み数式が、ベクトルとして見たときに加算関係を有し、そのため、数式の限られた部分集合から集合の残りの部分を生成することができることに基づくものである。これによって頻繁に行われる変換の変更が簡単になる。変換の様々な特性とこの変換を使用する方法が開示されている。
しかし、セット数式の残りの部分が数式の限られた部分集合から生成できることによって、符号解析は、ある種の応用例で必要とされるよりも難しいものになる。親出願は、セット数式の残りの部分がもはや、数式の限られた部分集合からは生成できないように、数式をやはり整然と容易に変更できるように非線形化する方法および装置に関するものであった。
本発明は、数式を非線形化するこれ以外の方法を提供するものである。
発明の簡単な説明
置換方式を比較的簡単なハードウェアと共に使用できるようにし、しかも暗号解析をさらに困難にする、ブロック換字技法によるｍｏｄ２加算ベースの暗号化を非線形化する方法および装置。この基本ブロック換字は、ｎビット２進数のそれ自体への１対１写像であり、ｎビット２進数のある種の置換によって、ある置換済み数の集合と別の置換済み数の集合のｍｏｄ２加算によるブロック換字が定義されることと、このような定義済み数式が、ベクトルとして見たときに加算関係を有することができることに基づくものである。これによって、変換を簡単に頻繁に変更することができる。その場合、数式の集合の残りの部分がもはや、数式の限られた部分集合からは生成できないように、数式がやはり整然と容易に変更できるように非線形化される。この変換の様々な特性と、この変換を使用する方法を開示する。具体的には、本発明によって提供される非線形化方法は、部分群の入れ子系列と、フィット済みコセット（fitted coset）と、互いに素なコラプチブル（corruptible）部分群のコセットとを含む。
【図面の簡単な説明】
第１図は、ｍｏｄ２加算によるある３ビット２進数の集合の別の２進数の集合への複数対単一変換を示す図である。
第２図は、ｍｏｄ２加算によるある３ビット２進数の集合の別の２進数の集合への１対１変換を示す図である。
第３図は、第１の数式を除いて、第１列中の３桁数が前の行の第２列中の３桁数と同じになるように順序変更された第２図の変換数式を示す図である。第１の数式を除いて、各列は、同じ順序ではあるが、異なる開始位置を有するものとなっている。
第４図は、第１列および第３列が第２列に対して垂直にシフトされた、第３図に対応する図である。このシフトはそれぞれ、下向きに６つおよび２つの位置である。第１の数式を除いて、各列は同じ順序ではあるが、異なる開始位置を有する。
第５図は、暗号化のために▲＋▼符号および＝符号が相互に交換された、第４図に対応する図である。
第６図は、データを暗号化する装置のブロック図である。
第７図は、第６図の装置によって暗号化されたデータを復号する装置のブロック図である。
第８図は、第６図を使用する暗号化の一例を示す図である。
第９図は、第７図を使用する暗号化の一例を示す図である。
第１０図は、第４図の列１および２に固定語００１が加算された、第４図の変換数式に対応する変換数式の集合を示す図である。第１の数式を除いて、列１および２は同じ順序ではあるが、異なる開始位置を有する。
第１１図は、第１０図の変換数式のような変換数式の集合によってデータを暗号化する装置のブロック図である。
第１２図は、第１１図の装置によって暗号化されたデータを復号する装置のブロック図である。
第１３図は、第１１図を使用する暗号化の一例を示す図である。
第１４図は、第１２図を使用する暗号化の一例を示す図である。
第１５図は、第２図中の数式を一般形ｘn-1▲＋▼ｘn＝ｚnに再構成した数式を示す図である。
第１６図は、本発明による暗号化・復号化システムのブロック図である。
第１７図は、ある数式の集合の第１列および第２列にオフセット０１０１を加算することによって導出された暗号化の第１列および第２列にオフセット０１０１を加算することによって導出された暗号化および復号化に有用な数式の集合を示す図である。
第１８図は、部分群の入れ子系列を使用して数式群を非線形化する方法を図示する図である。
第１９図は、部分群の入れ子系列を使用する暗号化方法を示すブロック図である。
第２０図は、ブロック・サイズｎ＝８の２進数に関する最大長線形直交写像の多重コセット分割を示す図である。
第２１図は、第２０図に図示した異なる部分群から得たフィット済みコセットを使用する暗号化方法を示すブロック図である。
第２２図は、ブロック・サイズｎ＝８の場合の第２１図の方法を示すブロック図である。
第２３図は、互いに素なコラプチブル部分群を使用する暗号化方法を示すブロック図である。
発明の詳細な説明
本発明は、親出願および親の親出願で詳細に説明したブロック換字によってｍｏｄ２加算ベースの暗号化を非線形化する方法および装置を含む。本出願では、本発明を改良する基礎を提供するために、親出願および親の親出願の開示を繰り返す。具体的には、親の親出願の態様を下記の第Ｉ節「ブロック置換」で述べる。親出願の発明の説明は、第ＩＩ節「非線形化の概要」に記載する。本発明に関連する開示は、残りの節に記載する。具体的には、第ＩＩＩ節「線形直交写像の修正（MODIFICATION OF LINEAR ORTHOMORPHISMS）」で、親出願および親の親出願で説明した線形直交写像（linear orthomorphisms）の予備的な修正および変形について説明する。第ＩＶ節「完全な非線形直交写像の構築」では、非線形直交写像の一般化を行う。第ＩＶ節「完全な非線形直交写像の構築」には、ブロック・サイズｎ＝８の場合の直交写像の構築を説明する詳細な例を提示する。ブロック換字数式の集合を非線形化する改良された第１の方法を第Ｖ節「部分群の入れ子系列」に提示する。改良された第２の非線形化方法を第ＶＩ節「異なる部分群からのフィット済みコセット」に提示する。改良された第３の非線形化方法を第ＶＩＩ節「互いに素なコラプチブル部分群のコセット」に提示する。第ＶＩＩ節はさらに、ブロック・サイズｎ＝８を有するブロック換字システムの詳細な例を含む。最後に、第ＶＩＩＩ節「用語および記号の定義」は、親出願および親出願に添付の付録内で使用された語の用語集である。第ＶＩＩＩ節「用語および記号の定義」ではさらに、本明細書で使用するある種の計算記号を定義する。
Ｉ．ブロック換字
下記の説明ではまず、親出願の方法および装置を、ｎビット２進数のブロック（ｎ＝３）に関して説明する。次いで、この方法および装置を一般的にｎビット・ブロックに展開し、ｎ＝８までのブロックのある特性を提示する。ｎ＝３の場合の下記の例を提示することによって、より多くの集合を有するより大きなブロックを使用するケースよりも、原発明の概念がよりよく理解されると思われる。
ブロック換字とは、通常、ｎビット２進数のそれ自体への１対１写像に適用される語である。この写像は、次式のように、２n個のｎビット数を対にしたものとして書くことができる。
0003701969.tif 000002
上式で、各列は、互いに素であるが、異なる順序で書かれた、同じ２n個のｎビット数の集合である。したがって、この写像は、下記のようにｎビット数を置換したものとみることも、
0003701969.tif 000003
あるいは、ある種の指標の集合では（Ｘl Ｘi Ｘj）とみることもできる。この通常の置換表記法は、Ｘl→Ｘi，Ｘi→Ｘj（以下同様）であることを意味するに過ぎない。
列表記法に戻ると、最初の集合およびその写像から簡単な数式の集合を定義することができる。
0003701969.tif 000004
上式で、▲＋▼は、ｍｏｄ２加算（すなわち、桁上げなしの対応する数字の加算）を意味する。一般に、集合｛Ｙ1，Ｙ2．．．｝は、全て異なる値ではないが、ある種の状況ではすべて異なる。原発明によれば、集合の値が異なっているとき、従来型の手段ではなくｍｏｄ２加算によってブロック換字を生成することができる。この場合、主として、この方式が作用する状況がもしあれば、それを判定し、さらに、どうすれば換字を迅速に変更できるかと、バイアスがないことを判定しなければならない。
ブロック換字がｍｏｄ２加算によって生成できるかどうかは自明ではない。たとえば、第１図に示した、ｍｏｄ２加算によって３ビット２進数のある構成で他の構成を置き換える試みを検討する。右側の列３で、０１１および１００はそれぞれ２回現れるが、００１および１１０は一度も現れない。左側の列１中の数は、中央の列２の数に作用し、列１の３ビット２進語の集合のそれ自体への変換を構成するものである。これは、多数対単一変換であり、変換済みブロック０１１および１００の最初のブロックを回復しようとする際に生じるあいまいさのためにブロック換字には無用である。
第２図に示すように他の構成を試みると、異なる結果が得られる。この場合、任意の１対の列が、１対１変換を構成する。具体的には、この変換は、列３の３ビット２進数（平文）からそれ自体、すなわち、列１の暗号文への１対１変換である。各列は、一度しか現れないすべて３ビットの数から成る。
第２図の変換を使用して、３桁２進ブロックを暗号化２進ブロックに変換し、もちろん、同じ数式を使用して、列１中の復号語を見つけ、次いで第２図の同じ行・列３中の対応する平文語を選択することによって、暗号化メッセージを復号することができることは自明である。これは、第５図に示したように、▲＋▼および＝を相互交換する場合に最も好都合である。復号語を平文に変換する等価変換は、列１の語を列２の語に加算して列３の語を得る場合に行われる。
再び第２図を参照すると、この変換の興味深い特性が示されており、そのため、本明細書に関するタイプのすべての変換を見ることができる。具体的には、３つの２進数の８つのブロックのうちで、小さい数の４つのブロック０００、００１、０１０、０１１は、小さい数の４つのブロックのうちの２つのブロック、すなわち０００および００１と、大きいの数の４つのブロックのうちの２つのブロック、すなわち１１０および１１１にマップされる。同様にもちろん、８つのブロックのうちのより大きな数の４つのブロックは、そのうちの２つが小さな数の４つのブロックにマップされ、他の２つが大きい数の４つのブロックにマップされる。同様に、偶数ブロック０００、０１０、１００、１１０は、２つの偶数ブロック０００および０１０と、２つの奇数ブロック００１および０１１にマップされる。４つの奇数ブロックは、そのうちの半分が奇数ブロックにマップされ、残りの半分が偶数ブロックにマップされる。復号にも同じことが当てはまるのは自明である。したがって、大きい、小さい、偶数、奇数など、暗号化ブロックのある種の特性の知識が、非暗号化ブロックの特性の同様な知識を与えることはない。この結果、この暗号化は不偏であると言われる。そのため、各ブロックの中央の数字を検討した場合でも、中央の数字がゼロである第２図の４つのブロックは、そのうちの２つのブロックが、やはり中央の数字がゼロであるブロックにマップされ、残りの２つのブロックが、中央の数字が１であるブロックにマップされることに留意されたい。同様にもちろん、中央の数字が１である４つのブロックは、そのうちの２つのブロックが、中央の数字が１であるブロックにマップされ、残りの２つのブロックが、中央の数字がゼロであるブロックにマップされる。この特性は、すべてのブロック・サイズに適用され、代数的には最大部分群として特徴付けることができるすべてが等しいブロックの集合への分割に拡張する。暗号化のこの不偏特性は、特に暗号化の頻繁な変更に関して本明細書で開示する暗号化方式の非常に有用な特性である。
具体的には、もちろん、任意の実際的な暗号化装置で、パターンが、それを符号分析するのに十分な時間にわたって持続しないように暗号化方式を頻繁に変更することができる。このために、第２図の行を第３図に示したように再構成することによって、第２図の数式のある種の特性を認識することができる。もちろん、どのように行を再構成しても、各数式が、それ自体の完全性をテーブル中の位置とは別に維持するので、変換に影響が及ぶことはない。基本的に、第３図の第２行は、第２図中の第４行であり、第３図の第３行は第２図中の第５行であり、各連続行は、その左側の列が、その前の行の第２列と同じ３ビット数を含むように構成される。そのように構成すると、第１行または識別行を無視した場合、３つの列のそれぞれが、ラップアラウンドによる３ビット２進数の同じ系列を含むことに留意されたい。具体的には、第１列は、第２列と同じ系列を有するが、第２列から下向きに１つの位置（あるいは、上向きに６つの位置）だけ変位されており、第３列は、第２列と同じ系列を有するが、列２から下向きに３つの位置（あるいは、上向きに４つの位置）だけ変位されている。
再び第３図の第１行または識別行を無視すると、ラップアラウンドによって、列１中の３ビット２進数を、第２列に対して下向きに合計で６つの位置だけシフトした場合でも、第４図に示したように、１対１変換が行われることに留意されたい。識別行を除いて、変換は、第３図の変換とはまったく異なるものである。一例を挙げると、第３図の列３の１１１は列１の０１１にマップされ、第４図の列１の１００にマップされる。第４図の列１および３中の３桁数の系列（識別行を除く）が、それぞれの数がラップアラウンドによって列２に対してシフトされるにもかかわらず、第３図と第４図の列２中の系列と同じであることに留意されたい。したがって、第３図の変換は、単に第３列の第１列中の数を第２列中の数に対してシフトし、第３列中の数も、第２列中の数に対して異なる量だけシフトしてｍｏｄ２加算式の完全性を維持することによって、第４図の新しい変換に変更された。この場合も、復号に関しては、第５図のように第４図の記号▲＋▼と記号＝を相互交換することができる。
さらに一般的に、任意のブロック・サイズに関して、数式の集合を下記のように書くことができる。
0003701969.tif 000005
0003701969.tif 000006
ブロック・サイズｎの場合、ｍ＝２n−１である。θ＝００．．．００であり、ｎビット語はすべてゼロから成る。
列１を列２に対してＳ個の位置だけシフトした場合、ｍｏｄ２加算式の完全性を維持するために、列３は、異なる量Ｐsだけシフトされる。所与のシフトＳの場合、Ｐsはシフト・プログラマによって決定される。
次に第６図を参照すると、前記で論じた暗号化技法および復号技法によって暗号化を実施するシステムのブロック図を見ることができる。
平文語は、メモリＩ中の前記語のアドレスに送られる。これは、列３からθ以外の語Ｘk-Psを選択することに対応する。この概念はＸk-Psを列２の対応するものに加算することである。Ｘk-Psが、θ以外のものであり、Ｘkに加算される予定である場合、これは、列３中の順序データＫ−Ｐsを含む語を、やはり列３中の順序Ｋ−Ｐs＋Ｐs＝Ｋを含む語に加算することと等価である。したがって、平文語Ｋ−Ｐsの順序データは、Ｐsに加算すべき加算器へ送られる。この新しい順序数は、メモリＩＩ中のその数のアドレスへ送られる。そのアドレスの内容は、平文語にｍｏｄ２加算され、列１中の暗号化語Ｘk-sが得られる。平文語がθである場合、その暗号文写像は同じである。
順序データの加算は、２つの加算器、桁上げ（Ｃ）、および最下位ビット（ＬＳＢ）によって行われる。桁上げ加算器は、従来どおり桁上げによって数を加算し、たとえば、００１＋０１１＝１００とする。しかし、加算でｎ桁よりも多くの桁が必要である場合、１がｎ＋１位置に桁上げされ、その余分の１はその代わりに、第１の位置に加算され、たとえば、１００＋１１０＝１０１０＝＞０１１となる。これは、ＬＳＢ加算器によって行われる。ｍ＝２n−１の場合、これはｍｏｄｍ加算に過ぎない。この例では、ｎ＝３、ｍ＝７であり、１０進項で表される加算は４＋６＝１０≡３ｍｏｄ７（１００＝＞４、１１０＝＞６、０１１＝＞３）である。
復号に関するブロック図を第７図に示す。暗号文語は、メモリＩ中の前記語のアドレスに送られる。これは、列１からθ以外の語Ｘk-sを選択することに対応する。この概念は、Ｘk-sをそれに対応するもの、すなわち、列２中のＸkに加算することである。これは、列１中のＸk-sを、やはり列１中の順序データＫ−ｓ＋ｓ＝Ｋを含む語に加算することと等価である。したがって、暗号文語の順序データのＫ−ｓは、ｓに加算すべき加算器へ送られる。この新しい順序数は、メモリＩＩ中のその数のアドレスへ送られる。そのアドレスの内容は、暗号文語にｍｏｄ２加算され、列３中の復号化語Ｘk-Psが得られる。暗号文語がθである場合、その語はθとして復号される。
順序データの加算、すなわち、Ｋ−Ｓ＋ＳおよびＫ−Ｐs＋Ｐsは、ｍｏｄｍまたはラップアラウンドによるものと理解される。すなわち、順序データがｍよりも大きい場合、最後の位置のｍが順序データが減算される。暗号文語がθである場合、その語は同じ語として復号される。
シフト・プログラムは、列１中のシフトＳが列３中の対応するＰsシフトＳと共に使用される順序を決定する。任意の所望の順序を使用することができる。シフトＳは、８ページで説明した基本置換の累乗に対応する。これは、加算による換字を決定する。
したがって、一例を挙げると、第８図で、平文データ値が０１０である場合、メモリＩ中の前記データ値のアドレスは順序データ００１を提供する。これは、０１０がメモリＩ中の系列中の位置１（数式の集合の列３）にあることを示す２進表記法である。プログラム中の第１のシフト位置はＳ＝６であり、この場合、Ｐ6＝２である。０１０の位置、すなわちＫ−Ｐ6＝１にＰ6＝２が加算される。２進表記法では、００１＋０１０＝０１１である。メモリＩＩ中のアドレス０１１には数１００が対応する（これは、１００が列３中の位置３にあると言うのと等価である）。１１０＝１００▲＋▼０１０は、暗号文語である。これは、第５図中の加算式のうちの第１の数式を表す。
復号の場合、暗号文語は１１０である。第９図で、メモリＩ中の前記語のアドレスは、順序データ１００、またはメモリＩ中の系列中の位置４を提供する。プログラム中の第１のシフト位置はＳ＝６である。１１０の位置、すなわち、Ｋ−６＝４に６、あるいは２進表記法では１１０が加算される。すなわち、４＋６＝１０である。ｍ＝７を減算すると、１０−７＝３であり、あるいはラップアラウンドによる位置３が得られる。２進表記法では、１００＋１１０＝０１１ｍｏｄ７である。メモリＩＩ中のアドレス０１１には数１００が対応する。すなわち、１１０▲＋▼１００＝０１０である。これは、第図中の加算式のうちの第１の数式を表す。
第４図の第１列および第２列に固定数をｍｏｄ２加算した場合、次の１対１変換が行われる。
0003701969.tif 000007
0003701969.tif 000008
次に、第１１図および第１２図を参照すると、任意のブロック・サイズに関して、θ以外の固定語、すなわち、ゼロ語を使用して暗号化および復号化を実施するためのブロック図を見ることができる。この手順は、前述の手順とほぼ同じものであり、暗号化プロセス中の最後のステップおよび復号プロセス中の第１のステップとして固定語のｍｏｄ２加算を行う追加ステップを含む。
一例を第１３図および第１４図に示す。この場合、０００はもはや固定されず、００１に変換される。次に、１１０がそれ自体に変換され、したがって、この場合は固定される。
固定語加算器は、ユーザが選択した順序でどれかまたはすべてのｎビット語を連続的に加算することができる。
次に、第８図を参照すると、一例として、前記で論じた暗号化技法および復号化技法によって暗号化を実施するシステムのブロック図を見ることができる。図のように、０００を除く平文データ２０の任意の値が、メモリ２２へのアドレスとして提供される。様々なメモリ・アドレスに、平文データ値に関する順序データ、すなわち、第４図（および第５図および第１０図）の右側の列の順序付き系列中の前記平文データ値の、２進数で表された位置が記憶される。この位置は、加算器２４および２６の組合せとして示した加算器へのメモリ２２の出力として提供される。これらの加算器は、シフト・プログラマ２８の制御に応じてメモリの出力をシフト値Ｐsに加算するように結合される。この加算は、ｍｏｄ２加算ではなく、通常の２進加算である。ただし、最上位ビットから桁上げは、最下位ビットのキャリーインに結合される。したがって、この加算器は、結果００１を、１０００でも単なる０００でもなく、１１１よりも大きな和１として提供する。したがって、加算器の出力は、順序データ系列で量Ｐsだけシフトされた新しい３ビット２進値である。この場合、この新しい位置は、メモリ３０向けのアドレスとして使用され、メモリ３０は、第４図の列２中の値に対応する３ビット２進値、または第３図中の対応する平文データ値を、その出力として提供する。したがって、一例を挙げると、平文データが０１０である場合、メモリＩへのアドレスとしてのこの値は、この値の位置、すなわち系列中の００１を提供する。シフト・プログラムがＳ＝６を選択した場合、Ｐ6＝２であり、列３は、列２から下向きに２つの位置だけ、あるいは量０１０だけシフトされる。その場合に平文データ値０１０に隣接する３ビット２進数は、第５図のように１００である。この平文データ０１０に加算されるｍｏｄ２は、第５図の値に対応する暗号値１１０を提供する。しかし、平文データ値が０００である場合、メモリＩへのアドレスとしてのこの値は、この値の位置、すなわち、系列中の０００を提供する。これはシフトされず、未変更でメモリ３０中の順序データとして提供される。したがって、それ自体に加算された０００は、固定されたままである。
第５図の列２の基本順序データに対する第５図の列３の系列の下向きシフトＰsはもちろん、相補上向きシフトに対応する。したがって、ｎビット・ブロックでは、Ｐsの下向きシフトは、ｍ−Ｐsの上向きシフトと等価である。３ビット・ブロックでは、可能なシフトのすべての値が、所望の１対１写像を提供することにも留意されたい。ただし、ゼロの第２列に対する第１列のシフトと、７およびその倍数のシフトはこの限りではない、なぜなら、そのようなシフトは、第１列の対応する行と同じ各行を有する第２列を行列中に提供し、それ自体にｍｏｄ２加算された数はゼロになるからである。したがって、７またはその倍数のシフトでは、すべての平文データ値が０００にマップされ、暗号化には無用である。しかし、一般に、３ビットより大きなｎビット・ブロックでは、ゼロおよびｍの整数倍数以外のすべてのシフトが所望の結果を与え、したがって、これらのシフトが原発明によって使用できることを後で示す。
第７図による復号に関するブロック図を第９図に示す。ハードウェアの観点からは、この図は、暗号化に関する第８図の図とまったく同じであり、復号化の暗号化と異なる点は、暗号化用の所与のシフトＰsの代わりにシフトＳが適用されることだけである。１４ページの例の場合と同様に、第８図および第９図のテーブルに示したように、暗号化用のシフトＰsが２である場合、シフト６によって妥当な復号が行われる。復号時に平文データをうまく回復するには、暗号化ハードウェアおよび復号化ハードウェアが関連するシフトを使用しなければならないことは自明である。ただし、符号分析が、ほぼ不可能にするのは無理にしても、非常に困難なものにするために双方で適用可能なシフトを頻繁に変更することができる。
第５図の任意の一対の列に固定数をｍｏｄ２加算した場合、次の１対１変換が行われる。一例を挙げると、第１０図で、第５図の第１列および第２列に固定数００１をｍｏｄ２加算した。この場合、平文語としての０１０は暗号化語１１１にマップされ、これに対して、第８図の例では、０１０は１１０にマップされる。
固定語加算器を使用する暗号化に関するブロックの一例は第１３図に見ることができる。この図は、第８図と同じものであるが、第１列の０１０と同じ、第２列の行中の値に対応するメモリ３０の出力に固定語（この例では００１）を加算するために、固定語加算器３２が含まれている。したがって、固定語加算器は、列２の値に固定語（この例では００１）を加算するに過ぎず、その後、その結果に平文語がｍｏｄ２加算されて、暗号化データが得られる。この場合も、たとえば、平文データ０１０をメモリ２２へのアドレスとして使用すると、メモリの出力は００１になる。第８図の例と同じシフトを使用すると、００１に０１０、すなわちＰs＝２が加算され、メモリ３０へのアドレス０１１が提供される。この結果、メモリ３０の出力が１００となり、固定語加算器がこの値に固定語００１をｍｏｄ２加算して、１０１が与えられる。このように平文語０１０へのｍｏｄ２加算によって、第１０図に示したように、暗号化語１１１が与えられる。
第１３図の暗号化に関するブロック図に対応する、復号化に関するブロック図を第１４図に示す。図から分かるように、第１４図は、第１３図と同じものであるが（ただし、この場合も、復号化用のシフトは暗号化用のシフトとは異なる）、固定語加算器は、固定語を、メモリ２２に適用する前に暗号化データにｍｏｄ２加算する。このｍｏｄ２加算は基本的に、固定語の第２のｍｏｄ２加算である。というのは、暗号化語を得るために、第１１図で固定語の第１のｍｏｄ２加算が行われたからである。したがって、第１２図中の暗号化データの後で、そのデータに固定語がｍｏｄ２加算されるように、同じ語の第２のｍｏｄ２加算が実際上、第１のｍｏｄ２加算を取り消すので、ｍｏｄ２加算の結果を第１０図の数式と共に復号のために使用することができる。したがって、一例を挙げると、第１３図の例の暗号化語１１１を使用した場合、第１４図のメモリ２２へのアドレスとして１１１▲＋▼００１＝１１０が得られる。この場合、メモリ出力は１００になり、この値にＳ＝６の値または１１０が加算される。すなわち、ラップアラウンドによって１００＋１１０＝１０１０＝＞０１１となる。これによって、メモリ３０へのアドレス０１１またはメモリ３０の出力１００が与えられ、その値にｍｏｄ２  １１０、すなわちメモリ２２へのアドレスが加算され、平文データ０１０が回復される。さらにもちろん、第１３図および第１４図の固定語加算器は固定語００１を使用したが、他の任意の３ビットの固定語を使用することができ、そのため、シフトの変更と共に、あるいはシフトの変更とは別に、必要に応じて固定語を変更することができ、固定語０００は基本的に、システムの動作を第８図および第９図の動作に低減する。
第６図、第７図、第１１図、第１２図に関して説明した方法が、プログラム制御下のマイクロプロセッサ・ベースのシステムで容易に実施できることは自明である。また、メモリは、基本的に参照テーブルとして使用される読取り専用メモリに容易に事前プログラムすることもでき、加算器およびｍｏｄ２加算器は、暗号化・復号化システムの少なくとも主要な要素が高速離散構成要素中で、あるいはカスタム集積チップを通じて実現できるように従来型の加算器回路であってよい。シフト・プログラムは、シフトが何度必要であるか、シフト順序自体を変更する程度などに応じて様々な形をとることができ、必要に応じてシフト・レジスタ実施態様を含めて、マイクロプロセッサ・ベースの集積回路またはその他の実施態様を容易に適用することができる。
ＩＩ．非線形化の概要
ここでの非線形性は、平文から暗号文へ（および暗号文から平文へ）の写像が、ビットごとのｍｏｄ２加算動作の下では非線形であることを意味する。なお、第１図が、ｍｏｄ２加算によるある３ビット２進数の集合の別の２進数の集合への多数対単一変換を示すことを指摘した。この特定の例は、第１列中の３ビット数の８つの可能な値をそれぞれ、ｍｏｄ２加算によって、２つ（１００および０１１）がそれぞれ２回繰り返される、８つの可能な組合せのうちの６つからなる列３中の６つの３ビット数にマップするものである。２つの３ビット数（０１０および１０１）が同じ３ビット数（１００）にマップされ、他の２つの３ビット数（１００および１１０）が同じ３ビット数（０１０）にマップされるので、この逆写像はあいまいさを有し、第１図に示した写像は、暗号化および復号化には適さない。
一方、第２図ないし第５図は、８つの可能な３ビット平文語のうちのどれか（列１）を、対応するあいまいでない暗号化語（列３）に暗号化する数式の集合を提供するものである。これらの数式は、列１と列３を相互交換しても有効なままであり、したがって、この相互交換によって、相互交換の前の数式が暗号化用の数式を形成するのと同様に、対応する復号用の数式を形成する。しかし、第２図ないし第５図のそれぞれに示した数式の集合は、所与の数式の集合内の２つの数式（第２図ないし第５図の場合のように３ビット数の場合は８つの数式）の加算が、その数式の集合のうちの１つであるという点で線形である。たとえば、第２図で、第１の数式すなわち零数式を任意の他の数式に加算すると、後者の数式が生成され、したがって、この加算は自明であり、第２の数式と第３の数式を加算すると、第４の数式が与えられ、第３の数式と第４の数式を加算すると、第２の数式が与えられ、第４の数式と第５の数式を加算すると、第８の数式が与えられ、以下同様である。１つの数式をそれ自体にｍｏｄ２加算するときでも、８つの数式のうちの１つ、すなわち、零数式が得られる。これは、２つよりも多くの数式、一例を挙げると、数式２、３、４をｍｏｄ２加算したときと同様であり、その場合、数式２と数式３を加算することによって数式４が生成され、数式４をそれ自体に加算することによって零数式が生成される。なお、２つの数式をｍｏｄ２加算することは、それよりも多くの数の数式を加算することと等価であるとみなすことができる。なぜなら、加算される数式のどちらかまたは両方を２つ以上の他の数式の和とみなすことができるからである。さらに、所与の数式の集合のうちのいくつかの数式の和は必ず、その集合のうちの他の数式となる。符号分析の観点から最も重要なことは、零数式以外の７つの数式のうちの右側の３つが与えられた場合、残りの４つの数式が、３つの既知の数式の組合せの妥当な和によって求められることである。たとえば、第２図の数式２、３、４の和の組合せを使用して残りの数式を生成することはできないが、数式２、３、または４と、数式５、６、７、または８をそのように使用することができる。数式２、４、８を一例として説明すると、数式２と数式４を加算すると数式３が与えられ、数式２と数式８を加算すると数式７が与えられ、数式２、４、８を加算すると数式６が与えられ、数式４と数式８を加算すると数式５が与えられる。もちろん、前記の規則は他のビット長の語の暗号化にも適用され、４ビット語を暗号化するための１６個の数式用の母数式は、４つの独立数式の様々な組合せをｍｏｄ２加算することによって求めることができる。
第１０図中の数式の集合に関しては、２つの数式を加算しても、その組の数式の第３の数式は与えられない。ただし、第１０図の左側の各列に００１を加算すると、この場合も第５図の数式の集合の零数式と残りの部分とになる。この数式の集合は一般に、その数式の集合のうちの３つの独立数式によって与えられる。この能力によって、基底独立数式の集合から数式の残りの部分が生成される。本発明は、この能力をなくするものであり、基底線形数式の集合を必要に応じて、あるいは動的に原出願で開示した様々な方法で、変更できるだけでなく、その結果得られる基底数式の集合を必要に応じて、あるいは動的に様々な程度に様々な組合せで非線形化することもできるように、整然と論理的にこれを行い、符号分析を以前よりもずっと困難なものとする。
再び第２図を参照すると、数式の順序を再構成した場合、もちろん列１中の数から列３中の数へのマップに変化はない。したがって、第２図中の数式は、第１５図に示したように再構成することができる。具体的には、零数式を無視すると、列２中に現れる第１の数（００１）が、列１の次の行に現れ、列２の第２の数（１１１）が列１の第３行に現れ、以下同様であり、ラップアラウンドの結果、列２中の最後の数（１０１）が列１の第１行に現れる（この場合も、零数式を無視する）。零数式と、２n−１個の非ゼロ数式とを有する任意のビット長の語（数）を表す任意の数式の集合を、それによって定義される写像を変更せずに、そのように構成することができる。というのは、そのような構成は、数式の見かけの順序を変更するものに過ぎず、数式自体を変更するものではないからである。
列１および２に現れる語を再構成して、対応する新しいｍｏｄ２加算式を与えることによって、そのような数式のある種の群を変更できることが示されている。新しいｍｏｄ２加算式は、それによって最初の数式の集合内の最初の数式群を置き換えても、１対１写像を維持し、したがって、この数式は、暗号化および復号化で使用するのに適している。なお、選択された数式群の列１および２に現れるマルチビット語の順序が変更されるので１対１写像が維持されるが、語自体は変更されず、その結果、マップされる語群と、選択された数式によってそれらの語がマップされる語群は変更されない。ただし、その２つの群内で、列１中のどの語が列３中のどの語にマップされるかは変更される。変更されたこれらの数式の正味効果は、それらがもはや、数式の線形拡張ではなく、すなわち、もはや２つ以上の未変更数式を加算しても生成することができないことである。したがって、これによって最初の数式の集合の線形性が無効になり、符号分析は必要に応じてより困難になる。線形性の無効化の程度については後で論じる。
付録２の第３．２節に、ある種の条件下で、所与の数式の集合内のいくつかの数式群を修正し、それらを使用して完全な数式の集合用の１対１写像を維持し、同時に、前述のようにその１組の数式の線形特性を無効化するように、最初の集合内の対応する最初の数式群を置き換えることができることが示されている。このような条件は、付録２の第３．３節に数式形でより具体的に示されている。この節には、２つの可能な修正が数式形で示されている。基本的な概念は、最初の数式の集合中の行の連続３つ組を合計することであり、付録２の第３．２節の分析では、第３．３節で述べるように、そのような行の連続３つ組を合計することによる非線形化が作用するのが、最初の数式の集合のうちの３つまたは４つの連続行の集合を使用する場合だけであることが示されている。３つの連続行を使用する場合、実際には４つの行、すなわち、最初の数式の集合の３つの連続行と、そのｍｏｄ２ベクトル和に対応する４番目の行が修正される。この修正は、４つの行のそれぞれに次式をベクトル的に加算することによって得ることができる。
0003701969.tif 000009
最初の線形数式の集合の４つの連続行を使用する場合、最初の数式の集合の６つの行、すなわち、４つの連続行と、そのうちの最初の３行のベクトル和を表す行、および最初の数式の集合の４つの連続行のうちの最初の３行のベクトル和に対応する行（たとえば、付録２の１０ページに示したように、行１、２、３の和に対応する行と、行２、３、４の和に対応する行）が修正される。この場合の修正は、対応する６つの行に次式をベクトル的に加算することによって得ることができる。
0003701969.tif 000010
上記の数式と付録２のＡ２ページに示した最初の数式の形は、非線形化が作用するのが、最初の線形数式の集合の第１行、第２行、第３行、および他の１行をとり、あるいは、最初の線形数式の集合の第１行、第２行、第３行、第４行、および他の２行をとる場合であることを示す。この方法が作用するのは、修正のために選択される最初の数式の集合のうちの数式がそれらの範囲内で線形であるためなので、本発明の方法によって一度非線形化された数式はもはや、非線形化プロセスの一部として使用することはできない。このため、このプロセスでは４つまたは６つの数式しか非線形化できない傾向があり、これはもちろん、より大きな語サイズの場合の総数式としては不十分な数である（たとえば、４ビット語では１６個の数式が必要であり、８ビット語では２５６個の数式が必要であり、以下同様である）。しかし、再び第１５図を参照すると、列２中のどの語または数を非零行からｘ1として選択すべきかが任意であることが理解されよう。一例を挙げると、００１ではなく０１１をｘ1として選択した場合、第３の非ゼロ行が第１行になり、第４の非ゼロ行が第２行になり、第５の非ゼロ行が第３行になり、第６の非ゼロ行が第４行になり、第７の非ゼロ行が第５行になり、第１の非ゼロ行が第６行になり、以下同様であり、基本的に下の５つの数式がシフトされ、上の２つの非ゼロ数式がラップアラウンドされ、その結果、数式自体も、数式の順序付けも変更されず、その系列の開始点のみが変更される。そのような数式構成を第３図に示した。この図で、ｘ1＝１００およびｘm＝（＝ｘ7）＝０１１である。したがって、付録２の１０ページに提示した数式は、３つの連続行と、その和に対応する行を修正する場合（非線形化）、任意の３つの連続行をそのように選択することができ、選択した３行と、その３行の和に対応する行のうちのどれも、より早く選択することによって事前に非線形化しておくことはできないことによってのみ制限されるという点で一般的なものである。同様に、４つの連続行と、前述の２つの和行を選択する場合、任意の４つの連続行をそのように使用することができる。ただし、この場合も、選択した４行と２つの和行のうちのどれも、このプロセスによって事前に非線形化しておくことはできない。数式を非線形化向けに一般化するには、ｘ1を、選択した３つまたは４つの連続行のうちの第１行の第２列中の値とみなし、それに応じて、各列の値の変更するだけでよい。
非線形プロセスが零数式以外の数式に対して実施されることに留意されたい。２n−１（ｎは、使用される語のドット長）個のそのような数式があるので、必然的に、非線形化ではｎの値にはかかわらずに奇数の数式が利用できるが、非線形化プロセスは、偶数（４または６）個の数式を一度に非線形化する（高速システムでは、所与の線形数式の集合の重ならない異なる群を同時に非線形化する装置を提供することができる。なぜなら、どのプロセスを使用するかにかかわらず、重ならない群に対する非線形化プロセスは完全に相互に独立するものだからである）。したがって、所与の線形集合中のすべての数式を非線形化できるわけではないことは明らかである。したがって、いくつの数式を線形化することができるかと、非線形化すべき数式を選択するための論理的な方法があるかどうかに関する問題がある。一般に、すべての数式を非線形化できるわけではないが、通常、４ビット以上の語サイズでは大多数の数式を非線形化し、重要でない残りの非線形化数式を残して、おそらく、それにより、場合によっては符号分析の観点から誤りに導くことができる。さらにもちろん、非線形化すべき行の数および識別と、どの非線形技法を使用するかを必要に応じて変更し、あるいは動的に変更することによって、符号分析の問題がさらに複雑になることに留意されたい。ただし、そのような時変非線形化も動的可変非線形化もハードウェアの観点からは難しいものではない（ソフトウェア制御下で実施する場合はソフトウェアの観点からも難しくない）。なぜなら、簡単で容易に変更できる母関数から開始線形数式の集合（この数式自体を、前述のように、必要に応じて、あるいは動的に変更することができる）を生成することができ、その数式の集合を論理プロセスを使用する方法でかつそのような範囲に非線形化することができ、その方法および範囲自体をそれぞれ、必要に応じて、あるいは動的に変更することができるからである。
最後に、非線形化数式は、最初の２列のそれぞれにオフセットをｍｏｄ２加算することによって、さらに修正することができる。これはもちろん、このオフセットをそれ自体に加算することと等価であり、これはもちろん、０になり、したがって第３列中の数には影響を与えない。具体的な例として、第１７図は、前記で説明し付録２のＡ１２ページに図示した、第１および第２列にオフセット０１０１を加算することによって修正された第３の例の数式の集合を提示するものである。
第１６図は、本出願の本発明による典型的暗号化・復号化装置のブロック図を示す。第１６図で分かるように、最終的に、平文データ・ブロックまたは暗号文データ・ブロック（どちらも長さｎビット）がメモリへのアドレスと並列して提示され、データがそれぞれのデータ・ブロックの暗号化および復号化に対応するアドレスに記憶される読取り／書込みメモリの形の参照テーブルを使用すると好都合である。そのために、メモリ・アドレス範囲が、操作すべきデータ・ブロックよりも１ビットだけ広くなるように、暗号化または復号化に必要なアドレス零間（たとえば、ｎ＋１アドレス・ビット）の２倍のアドレス零間のメモリを使用すると好都合である。このように、１ビットのメモリ・アドレスを使用して、動作を暗号化動作とするか、それとも復号化動作とするかを指定することができる。具体的な例を挙げると、メモリ・アドレスの最上位ビットは、復号プロセスを示す０、または暗号化プロセスを示す１でよく、メモリのアドレス範囲の下半分に復号データを記憶し、メモリの上部アドレス範囲に暗号化データを記憶することができる。したがって、暗号化と復号化は共に、単一ビットを制御することによって参照テーブルに応じて実行することができ、ｎビットのブロックの暗号化も復号化も単一メモリ・サイクルで行うことができる。
暗号化および復号化用の写像を周期的または動的に、あるいはその周期的でかつ動的に変更すると仮定すると、参照テーブルの内容を修正するある方法を提示することができる。これは、専用ハードウェアによって実行することができるが、プログラム制御下で適当なプロセッサによってこれを行うと好都合である。というのは、暗号化方式および復号化方式の修正は通常、暗号化および復号化自体を実施することよりもずっとまれにしか行われないからである。したがって、このような修正を暗号化および復号化自体と同じ速度で行う必要はない。したがって、第１６図に示した非線形動的換字ジェネレータは、それへの様々な入力に基づくプログラム制御下で動作することができる。具体的には、暗号化用の数式は、それを定義する何らかの基本情報、一例を挙げると、ブロック換字ビット・サイズ（ｎ）、ｎ個の線形独立数の基底集合、母関数、非線形化を開始する線形集合の開始数式、実行すべき非線形化関数の反復数が与えられた場合、暗号化用の数式をプログラム制御下で生成することができる。
非線形化数式にオフセットを適用した後、列３中の各数またはブロックは、符号化に割り当てられた参照テーブルの、それぞれの行の列１中のブロックに等しいアドレスの部分に記憶される。したがって、列１中の数またはブロックをアドレスとして適用したとき、メモリから読み取られる数は、それぞれの暗号化ブロックを表すその行の列３中の数である。テーブルの復号部分に関しては、このプロセスが反転され、その場合、列３中のブロックがメモリ・アドレス（より適切には、アドレス部分、完全なアドレスはアドレス・ビット指定復号を含む）として使用され、そのようなアドレスに記憶されるデータは列１中のそれぞれのブロックである。したがって、復号時に、メモリは、暗号化ブロックによって定義されたアドレスから開始し、それぞれのアドレスに記憶されているデータは、関連する平文ブロックに対応する出力として提供される。
暗号化プロセスおよび復号化プロセスを完全にプログラム制御下で実施できることは自明である。なぜなら、２つのプロセスは共に、ある種の（可変）開始情報が与えられた場合、論理処理しか必要としないからである。しかし、プロセッサが同じ暗号化数式および復号化数式を何度も再生成するので、暗号化および復号化を実施する速度は、大幅に減少される。これに対して、参照テーブルを使用すると、完全な暗号化数式および復号化数式の集合を一度に求めることができ、暗号化または復号化すべきデータ・ブロックに関するその情報は、数式が変更されるまで連続的に単一のメモリ・サイクルで得ることができる。
ＩＩＩ．線形直交写像（linear orthomorphisms）の修正
本節では、前記の第ＩおよびＩＩ節で説明した線形直交写像に対するある種の修正を提示する。
一般性を失わず、かつθ、すなわち加算識別を固定点として使用する場合、次式のように最大長直交写像を数式の集合として書くことができる。
0003701969.tif 000011
上式で、ｍ＝２n−１、Ｒ（ｘk-1）＝ｘkおよびＳ（ｘk-1）＝ｚkは３つの可能な写像のうちの２つである。従来どおり、本出願人の暗号写像またはブロック換字としてＳ（ｘ）を使用した。
線形直交写像の場合、θは、固定点でなければならず、極大である場合、代表数式は、次式のように非常に簡単な形をとる。
0003701969.tif 000012
線形バージョンを適切に修正することによって非線形直交写像を構築することができる。任意のｎビット数ｗ≠θを選択し、数式ｗ▲＋▼ｗ＝θをベクトルとみなす。数式（１１）中の線形直交写像を表す各数式にｗ▲＋▼ｗ＝θをベクトル的に加算すると、次式が得られる。
0003701969.tif 000013
各列は、すべての可能なｎビット数から成り、写像Ｓ（ｘk-1▲＋▼ｗ）＝ｘk-pはアフィンである。さらに全体的に非線形であるには、数式の線形アレイを部分集合に分割し、異なる方法で修正する必要がある。線形直交写像中のａ番目の行の個別の数式
0003701969.tif 000014
は次式になるように修正しなければならない。
0003701969.tif 000015
上式で、最初の線形直交写像において、ｘc-1は左側の列の行ｃに現れ、ｘbは、中央の列の行ｂに現れる。この場合、次式が成立する。
0003701969.tif 000016
上式は、数式１２と同様に行ａ中の数式を変換するように適用される。
線形直交写像中の２n個の数式の集合全体がコラプチブル（corruptible）であり、数式（１０）から、最小コラプチブル集合の候補は、３つの行または数式から成る。しかし、３つの数式のコラプチブル集合（corruptible set）を含む線形直交写像は、極大ではないので、暗号には無用である。
命題１：３つの数式のコラプチブル集合を有する
0003701969.tif 000017
に関する線形直交写像が、それが表す置換に３サイクルを有することを示すことができる。
下記の分析は、前記の命題１を証明するものである。線形直交写像中の３つの数式のコラプチブル集合
0003701969.tif 000018
は、指数の行列で示すことができる。
0003701969.tif 000019
非線形化（コラプション）後、行の順序が自明なので、次式のように可能な指数行列は２つしかない。
0003701969.tif 000020
左側の行列をとると、対応するコラプトされた数式は次式のとおりである。
0003701969.tif 000021
指数ａおよびｂを含む任意の２つの数式を選択することができるが、数式ｃには矛盾する３つの条件がある。下記では、そのような数式が線形アレイ中に存在すると仮定する。数式の線形アレイは群なので、指数ｄ群には、最初の３つの指数の和である下記の第４の数式が存在する。
0003701969.tif 000022
線形アレイ中のこの４つの数式は、線形アレイ中の位数４の部分群から導出されるコセットを形成する。この部分群は、コセット中の４つの数式の１つを他の３つ、たとえば、数式ａに加算して次式を得ることによって、得ることができる。
0003701969.tif 000023
数式１９を使用すると、この部分群は、次式のようになる。
0003701969.tif 000024
最後の３つの数式は、線形アレイの正規化形（数式１９）に連続的に現れ、３サイクルを形成する。他の指数行列を使用した場合、左側の列と中央の列を相互交換し、なおかつ等性を維持することができ、同じ結果が得られる。
前記の命題は、ブロック・サイズｎの極大線形アレイで、任意のｎ個の連続行が線形に独立しているという認識にも従うものである。位数４の部分群が線形に独立な行を有することはできないので、アレイを極大にすることはできない。
次に、４つの行ａ、ｂ、ｃ、ｄのコセットを検討し、最初の３つの行を前述のように修正すると、結果は次式のとおりである。
0003701969.tif 000025
数式２４を線形バージョン（数式１１）と比較して、下記の混合変換を導出することができる。
0003701969.tif 000026
ｗc＝ｗa▲＋▼ｗbなので、混合変換の集合｛θ，ｗa，ｗb，ｗc｝は群である。
３つの連続行とその和がコラプチブル集合を構成した。これは、任意の２つの非ゼロ行をとることに一般化される。
0003701969.tif 000027
次式によって指定される第３の行ｃを求め、
0003701969.tif 000028
次式によって指定される第４の行ｄを求める。
0003701969.tif 000029
したがって、数式の線形直交写像アレイ中の任意に選択された２つの非ゼロ行は、４つの数式の２つのコラプチブル集合を指定する。これらの集合のうちの第２の集合は、次式によって第３の行ｃを選択することによって指定される。
0003701969.tif 000030
どちらの場合も、混合変換ｗ≡ｘa▲＋▼ｘbは、４つの数式のこの集合を非線形直交写像の４数式セグメントに変換する。最初の４つの数式が、位数４の部分群での相対補数であり、あるいは、そのような部分群から導出されたコセットと等価であることは明らかである。前記の命題１の場合と同様に、この部分群は、次式のように、４つの数式のうちの１つを４つの数式のそれぞれ、たとえば行ａに加算することによって導出することができる。
0003701969.tif 000031
第１のケースでは、ｘa-1▲＋▼ｘc-1＝ｘa▲＋▼ｘbなので、第２および第３の数式は線形アレイで連続している。同様の結果が第２のケースでも成立する。したがって、４つのコラプチブル数式を求めるプロセスは、２つの連続行を含む位数４の部分群によって定義される
0003701969.tif 000032
のコセット分割で任意のコセットを求めることに低減される。さらに一般的には、極大線形直交写像を
0003701969.tif 000033
とし、位数２kの部分群を
0003701969.tif 000034
とする。この部分群は、次式の形を有する。
0003701969.tif 000035
上式で、ｓ＝２k−１である。コセットは、
0003701969.tif 000036
中の任意の行、たとえばｘa-1▲＋▼ｘa＝ｘa-pをとり、それを
0003701969.tif 000037
の各行に加算して次式を得ることによって、形成することができる。
0003701969.tif 000038
上式で、ｘaＭk＝｛ｘa▲＋▼ｘi｜ｘiεＭk｝である。ｗが混合変換であり、行ｉが
0003701969.tif 000039
中にある場合、次式が成立する。
0003701969.tif 000040
ｘi-1εｘa-1ＬkおよびｘiεｘaＭk。ｘi-1▲＋▼ｗεｘa-1Ｌkおよびｘi▲＋▼ｗεｘaＭkも真でなければならない。こうなるのは、ｗεＬk∩Ｍkである場合だけである。行ｉが
0003701969.tif 000041
にある場合も同様である。なぜなら、その場合、ｘi-1εＬkおよびｘiεＭkであるからである。
0003701969.tif 000042
によって決定される混合変換群は、Ｗk＝Ｌk∩Ｍkである。ある種の状況では、Ｗk＝｛θ｝であり、建設的コラプションは不可能である。前記のことは、下記の第ＩＶ節でさらに詳しく説明する。
部分群のコセットでも相対補数でもないコラプチブル・セットがある。たとえば、コラプチブル・セットは、次式のように、４つの連続数式と、最初の３つの数式および最後の３つの数式をとることによって生成される。
0003701969.tif 000043
上式で、ｘq＝ｘ1▲＋▼ｘ2▲＋▼ｘ3であり、以下同様であり、ミクサはｗ1＝ｘ1▲＋▼ｘ2、ｗ2＝ｘ1▲＋▼ｘ3、ｗ3＝ｗ1▲＋▼ｗ2である。次式を使用してさらに２つの行を加算することができる。
0003701969.tif 000044
この結果得られる８つの数式は、３つの連続行の１つの集合と２つの連続行の１つの集合を含む位数８の部分群から導出されるものとして容易に示すことができるコセットを構成する。
建設的コラプションは、非線形直交写像を形成するようにアセンブルできる非線形セグメントを与えるが、このように得ることができない非線形セグメントがあるかどうかに関して問題が発生する。
命題２：一般に、建設的コラプションによって任意の極大長非線形直交写像を線形（自己同型）直交写像から導出することができる。
前記の命題は、下記の分析によって証明される。一般性を失わずに、θを固定点と仮定することができる。極大長非線形直交写像の正規化形はを数式１１ａに示す。右側の列中のｎビット数は、次式のように、置換の新しい位数が線形直交写像になるように置換される。
0003701969.tif 000045
これは、ｚiの補線形独立集合に線形母関数、すなわち原子多項式を適用することによって多数の方法で実行することができる。したがって、ｕi＝ｚjである。ここで、ｉ＝ｆ（ｊ）は前述の置換を表す。この同じ置換を、非線形直交写像Ｓ（ｘk-1）＝ｚkを変更せずに数式１１ａ中の数式アレイに適用することができる。しかし、｛ｕi｝置換はこの場合、線形直交写像を定義する。この正味結果は、次式の形のｍ＝２n−１数式の二重集合である。
0003701969.tif 000046
対応する混合変換は次式のとおりである。
0003701969.tif 000047
前記の分析の主要な結果は、特殊な部分群を使用するコセット分割が、成分ごとの非線形化の候補を見つけるための有効で系統だった手段であり、そのような技法を使用した場合、非線形直交写像のどのクラスも見逃されないことである。次節では、どんなサイズの成分をコラプトすべきかを判定する分析と、成分をどのようにして、暗号用の望ましい特性を有する非線形直交写像としてアセンブルすべきかを提示する。
ＩＶ．完全な非線形直交写像の構築
第ＩＩＩ節では、それ自体の中で非線形化することができる線形直交写像の成分（数式のコラプチブル集合）を求めるにはどうすべきかを説明した。本節では、成分を２n−１個の数式の完全な非線形直交写像としてアセンブルするにはどうすべきかを説明する。本節ではさらに良好な線形直交写像および良好な非線形代入を構成するものについて説明する。一方の極端な例では、位数４のコセットを修正して、残りの２n−４個の数式を修正しないでおくことができる。他方の極端な例では、すべての２n個の数式を単一の混合変換で修正することができる。成分ごとの線形化もアフィン写像も十分ではない。任意の写像Ｓの場合、次式を評価することができる。
0003701969.tif 000048
Ｓがアフィン写像である場合、数式３９の和は、Ｓが線形である場合はすべての対ｘ、ｙ、ｃ＝θに対してある種の固定数ｃとなる。したがって、非線形性の自然な尺度は、Ｎ（ｘ，ｙ）の範囲および分布である。
命題３：極大長線形直交写像中の位数２kの部分群の場合、対応する混合変換群の位数Ｗkが２2k-n≦｜Ｗk｜≦２k-1となることを証明することができる。
前記の命題は、下記の分析によって証明される。直交写像の部分群は
0003701969.tif 000049
である。ここで、Ｌk、Ｍk、Ｒkは、
0003701969.tif 000050
の部分群であり、それぞれ、位数は２kである。Wk＝Lk∩Mkである。｜Wk｜＝２kである場合、Ｌk＝Ｍkであり、
0003701969.tif 000051
が直交写像中のサイクルであることを示す。これは極大であるので、｜Ｗk｜≦２k-1である。ＬkおよびＭkはそれぞれ、ｋ個の線形独立数の集合を有し、それらの集合はそれぞれ、{ｘ1，ｘ2，．．．．，ｘk}εＬkおよび{ｘk+1，ｘk+2，．．．，ｘ2k}εＭkで示される（これらの指数は、この場合、数式１１とは異なり、行を指すものではない）。
0003701969.tif 000052
の任意の部分集合には最大でｎ個の線形独立数がある。したがって、２ｋ＞ｎである場合、｛ｘ1，．．．，ｘk，ｘk+1，．．．，ｘ2k｝には、相互に依存する２ｋ−ｎ個の数の部分集合がある。一般性を失わずに、{ｘk+1，ｘk+2，．．．，ｘn}が｛ｘ1，．．．，ｘk｝から独立していると仮定することができる。残りの数｛ｘn+1，．．．，ｘ2k｝は｛ｘ1，．．．，ｘk｝εＬkに依存しなければならない。相互に独立な２ｋ−ｎ個のそのような数があり、したがって、｛ｘn+1，．．．，ｘ2k｝εＬk∩Ｍkである。
前記の直接的な系は、極大線形直交写像Ｇnの部分群
0003701969.tif 000053
が位数
0003701969.tif 000054
を有することである場合、
0003701969.tif 000055
およびそのコセットがコラプチブルであるということである。
位数２kのコセットは、対応する混合変換群が位数２k-1である場合「完全にコラプチブル」であると言われる。
0003701969.tif 000056
に関する線形直交写像を表す２n個の数式の集合をＧnとする。数式３１と同様に２k個の数式から成るＧnの部分群を
0003701969.tif 000057
とする。｜Ｗk｜＝２k-1と仮定する。前記の仮定および定義を用いた場合、コセット分割は次式の形をとる。
0003701969.tif 000058
上式で、ｃ＝２n-k−１であり、
0003701969.tif 000059
は、
0003701969.tif 000060
中の２k個の数式のそれぞれに数式（ベクトル）ｘi-1▲＋▼ｘi＝ｘi-pを加算することによって算出されるコセットである。各連続数式は、
0003701969.tif 000061
にも、分割中の前のコセットにも現れてはならない。実際的な目的のために、コラプチブル集合への分割が望ましい。これらのコセットのそれぞれは、利用可能な同じ混合変換群を有する。
線形直交写像を表す数式の極大部分群は、連続ステップによって非線形直交写像に変換することができる互いに素な部分集合に分割することができる。これは、完全にコラプチブルなコセットに一般化することができる。
建設的なコラプションの実際的な問題は、非線形化すべき線形直交写像アレイ中の数式の集合のサイズをどのように選択すべきかと、矛盾なしで混合変換を割り当てる方法である。
0003701969.tif 000062
が位数２kの数式のアレイの部分群であり、完全にコラプチブルである場合、混合変換集合の位数は｜Ｗk｜＝２k-1である。コセット
0003701969.tif 000063
は、
0003701969.tif 000064
中にないある数式ｘi-1▲＋▼ｘi＝ｘi-pを
0003701969.tif 000065
中のすべての数式にベクトル的に加算することによって得られる。このコセットは、Ｗk中のいくつかまたはすべての混合変換を適用することによってコラプトすることができる。ｗεＷkを１つしか使用しない場合、その結果、アフィン集合が得られる。すべてのｗを使用しようとした場合、ｗを矛盾なしで割り当てるにはどうすべきかという問題がある。常に、完全にコラプチブルな部分群
0003701969.tif 000066
をとり、
0003701969.tif 000067
の２つのコセットに分割し、次いで、この２つの小さなコセットを別々にコラプトすることができる。問題は、混合変換集合の位数｜Ｗk-1｜が２k-2であることであり、そのため、混合変換が適用される数式の数の半分の混合変換しか得られないことである。ｋ＝２であり、コセットの位数が４であるという限界のために、Ｗ2＝｛θ，ｗ｝であり、したがって、すべての２n-2−１個のコセットに適用できる混合変換は１つしかない。下記では、部分群
0003701969.tif 000068
から導出されるコセット
0003701969.tif 000069
の部分集合を求め、その結果、この部分集合の左側の列と中央の列中の数をそれら自体の間組み合わせることができ、しかも、それらの数の和が、
0003701969.tif 000070
すなわち右側の列の全範囲にわたるようにする方法を提示する。
この方法は、「カット・アンド・トライ」法ではなく整然としたプロセスへの複数の混合変換の割当てを簡略化するものである。下記では、ｋ≦ｎ−１の場合のすべての位数
0003701969.tif 000071
の部分群にこのプロセスを一般化する。この方法は、極大部分群と同様に働く部分群を求めようとするものである。
命題４：位数２kの完全にコラプチブルな部分群が、極大線形直交写像を表す完全な数式アレイの数式のｋ個の連続行を有することを証明することができる。
前記の命題は、下記の分析によって証明される。位数２kの完全にコラプチブルな部分群を
0003701969.tif 000072
とする。その場合、定義上、｜Ｗk｜＝２k-1である。
0003701969.tif 000073
は、ｋ個の線形独立数式の極大集合を有する。Ｗkは、ｋ−１個の数の極大線形独立集合を有する。完全な線形アレイ中の列ＬまたはＭから連続数の最大集合を含む集合を求めることが望ましい。ｋ−１個のそのような数ｘa，ｘa+1，．．．ｘa+k-2がある場合、これらの数は、
0003701969.tif 000074
中の下記の行、すなわち、ｋ個の連続行に対応する。
0003701969.tif 000075
ｋ−１個の線形独立数の集合中の連続数がｋ−１個よりも少ない場合、これらの数は、連続数のより小さな集合とすることができる。最大のそのような集合は、ｘa，ｘa+1，．．．ｘa+ka-2であり、２番目に大きなそのような集合はｘb，ｘb+1，．．．，ｘb+kb-2であり、以下同様であり、最終的に、Ｗk中のｋ−１個の独立数の集合が（ｋa−１）＋（ｋb−１）＋．．．＝ｋ−１によってアセンブルされる。そのような各集合は、次式の形の、すべてが連続する
0003701969.tif 000076
中の数式の集合を定義する。
0003701969.tif 000077
ｘが線形に独立しているので、数式４２中のｋa＋ｋb＋．．．＞ｋ個の個別の数式は、線形に独立している。したがって、
0003701969.tif 000078
は矛盾を表す。
完全にコラプチブルな部分群は、非線形直交写像を導出するうえで有用であるだけでなく、下記で示すように、より小さな部分群の構造にも影響を及ぼす。
命題５：位数２kの完全にコラプチブルな部分群では（ｋ≧４）、位数２k-1の各部分群がコラプチブルであることを証明することができる。
前記の命題は、下記によって証明される。そのような完全にコラプチブルな部分群を
0003701969.tif 000079
とする。命題４によって、
0003701969.tif 000080
は、完全な直交写像写アレイから得たｋ個の連続数式を有する。
0003701969.tif 000081
は、ｋ個の連続数式の隣接する対の和である別のｋ−１個の連続数式の集合も有する。なぜなら、これは
0003701969.tif 000082
の生成元の集合であるからである。連続行の連続的に小さくなるｋ組の系列がある。この系列の指数を表Ｉに提示する。
0003701969.tif 000083
ｋ≧４なので、少なくとも４つの連続ａ行、３つのｂ行、２つのｃ行がある。ｋ−１行の連続する３つの集合
0003701969.tif 000084
は、線形独立集合であり、ｋ−１個の連続行を含む
0003701969.tif 000085
を生成するために使用される。同様に、（ｂ，ａ＋２，ａ＋３，．．．，ａ＋ｋ−１）は、ｋ−２個の連続行を含む
0003701969.tif 000086
を生成する。ｘbがｘa+2，．．．，ｘa+k-1から独立していることに留意されたい。
0003701969.tif 000087
がコラプチブルでないようにするには、上記の指数からすべての対をなくする必要がある。１つを除くすべてのａ、たとえば、ａないしａ＋ｋ−２をなくした場合、ｘa，．．．，ｘa+k-2は、相対補数
0003701969.tif 000088
中に含まれる行を定義するが、ｘa▲＋▼ｘa+1＝ｘbであり、以下同様である。少なくとも、
0003701969.tif 000089
のｂもなくさなければならない。したがって、ある種の３重加算が
0003701969.tif 000090
中に存在することにより、これは補数に対する矛盾である。ｋが偶数であるか、それとも奇数であるかに応じて、
0003701969.tif 000091
の代替ａ行が部分群補数に委ねられる可能性もあるが、ｘa▲＋▼ｘa+2＝ｘcであり、以下同様である。この場合も、ｃ指数を含む連続行をなくするために、いくつかのそのような行が補数中に存在することになり、したがってその結果、３重和が得られる。
ｎ≧５の場合、これは、位数２n-2の部分群がコラプチブルであり、もちろん、命題４によって、位数２n-1の部分群が完全にコラプチブルであることを意味する。
命題６：
0003701969.tif 000092
に関する極大直交写像は線形またはアフィンである。
前記の命題は下記によって証明される。非線形直交写像は、線形直交写像からの建設的コラプションによって導出することができる。すべての８つの行にｗ▲＋▼ｗ＝θ（ｗ≠θ）をベクトル的に適用した場合、写像はアフィンとなる。直交写像が３サイクルを有することはないので、最小コラプチブル集合は位数４を有する。
直交写像を
0003701969.tif 000093
とし、対応する単一コセット（補数）を含むコラプチブル部分群を
0003701969.tif 000094
とする。｜Ｇ2｜＝２2なので、Ｗ＝｛θ，ｗ｝である。ここで、ｗは、自明でない単一の混合変換である。Ｓ（ｘ）＝ｚが最初の線形写像である場合、コセットに関してはＳ’（ｘ▲＋▼ｗ）≡Ｓ（ｘ）であり、部分群に関してはＳ’（ｙ）≡Ｓ（ｙ）である。ｗεＧ2であり、したがってＳ’（ｗ）＝Ｓ（ｗ）である。
0003701969.tif 000095
である場合、
0003701969.tif 000096
についても同様である。Ｓ’（ｘ）＝Ｓ’（ｘ▲＋▼ｗ▲＋▼ｗ）＝Ｓ（ｘ▲＋▼ｗ）＝Ｓ（ｘ）▲＋▼Ｓ（ｗ）である。下記の３つのケースがある。
0003701969.tif 000097
極大部分群の補数が単一の混合変換でコラプトされる場合、同じ結果が任意のブロック・サイズに対して成立する。次のステップは、コセット対またはその部分集合が、完全な混合変換群を使用する場合でも、最小限の相互作用で修正できるという追加特性を有する完全にコラプチブルな部分群を求めることによって、建設的コラプションのプロセスをさらに向上させることである。
命題７：位数２k（ｋ＞２）の完全にコラプチブルなコセット
0003701969.tif 000098
を位数２k-1の２つのコセットに分割し、その結果、そのようなより小さな各コセットの左側の列および中央の列中の数が、それらの間で再構成できるようになり、かつその結果得られる和が、親コセット
0003701969.tif 000099
の列全体にわたって分散されることを証明することができる。
前記の証明は、下記によって証明される。完全にコラプチブルな部分群
0003701969.tif 000100
およびコセット
0003701969.tif 000101
は、下記のように表すことができる。
0003701969.tif 000102
上式で、ｓ＝２k−１およびｔ＝２kである。
0003701969.tif 000103
が極大部分群でない場合、次式が成立する。
0003701969.tif 000104
命題４によって、位数２kの部分群
0003701969.tif 000105
は、完全にコラプチブルなので、数式の完全な直交写像集合から得たｋ個の連続行または数式の集合を含む。このｋ個の行は、線形独立集合である。このｋ個の行のすべての偶数和をとることによって生成される部分群は、位数２k-1の部分群
0003701969.tif 000106
すなわち、列Ｌk-1⊂Ｌk、Ｍk-1⊂Ｍk、Ｒk-1⊂Ｒkを含む
0003701969.tif 000107
である。数の同じ和がＬk-1およびＭk-1内とＬk-1とＭk-1の間で発生するので、Ｌk-1⊂ＲkおよびＭk-1⊂Ｒkである。この直交写像は極大なので、妥当なサイクルはなく、したがって、Ｌk-1≠Ｒk-1およびＭk-1≠Ｒk-1である。したがって、Ｌk-1∩Ｒk＼Ｒk-1およびＭk-1∩Ｒk＼Ｒk-1が空ではない。この場合、Ｒk＼Ｒk-1はＲk中の数の集合であるが、Ｒk-1中の数の集合ではない。Ｌk-1およびＭk-1がＲkの部分群なので、任意のｘεＬk-1およびｙεＭk-1について、ｘ▲＋▼ｙεＲkである。ある種のそのような和は、たとえばｘεＬk-1∩Ｒk＼Ｒk-1である場合、ｘ▲＋▼θεＲkであるので、Ｒk＼Ｒk-1中になければならない。したがって、Ｌk-1およびＭk-1中の数の対を再構成すると、Ｌk-1×Ｍk-1×Ｒk中にコラプトされた数式がもたらされる。
0003701969.tif 000108
は、
0003701969.tif 000109
の２つの異なるコセットに分割され、すなわち、
0003701969.tif 000110
である。１つのコセット
0003701969.tif 000111
を検討する。これは、
0003701969.tif 000112
中のすべての数式にある数式ｘa-1▲＋▼ｘa＝ｘa-pをベクトル的に加算することによって得られる。コセット
0003701969.tif 000113
は、
0003701969.tif 000114
中の３つのコセットの直積として表すことができる。すなわち、次式が成立する。
0003701969.tif 000115
したがって、ｕεｘa-1Ｌk-1およびｖεｘaＭk-1である場合（あるｘεＬk-1およびｙεＭk-1に関してｕ＝ｘa-1▲＋▼ｘおよびｖ＝ｘa▲＋▼ｙ）、この証明の第１の部分によって、ｘ▲＋▼ｙ＝ｚεＲk-1である。したがって。次式が成立する。
0003701969.tif 000116
したがって、数の任意の対ｕ，ｖ（ｕεｘa-1Ｌk-1およびｖεｘaＭk-1）の場合、ｕ▲＋▼ｖ＝ｗであるようにｗεｘa-pＲk-1が存在する。同じことが、他のコセット
0003701969.tif 000117
の場合も成立する。
前記の一例を挙げると、非線形化方法は、母関数ｘk＝ｘk-8▲＋▼ｘk-6▲＋▼ｘk-3▲＋▼ｘk-2によって定義されるブロック・サイズ８極大長線形直交写像を検討する。８ビット２進数の完全な線形独立集合を｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ．Ｆ，Ｇ，Ｈ｝とする。この場合、各文字は、８ビット２進数を表し、具体的にはＡ＝Ｘ，Ｂ＝Ｘ2，．．．．．，Ｈ＝Ｘ8である。都合上、そして話を簡単にするため、表記法ＡＢＣはＡ▲＋▼Ｂ▲＋▼Ｃを表す。前記の完全線形独立集合にその順序で母関数を適用すると、直交写像を表す２8＝２５６個の数式または行が定義される。たとえば、Ｘ9＝Ｘ1▲＋▼Ｘ3▲＋▼Ｘ6▲＋▼Ｘ7＝Ａ▲＋▼Ｃ▲＋▼Ｆ▲＋▼Ｇ＝ＡＣＦＧとなる。この一部を次式に示す。
0003701969.tif 000118
暗号化に使用される直交写像はたとえば、行５のＳ（Ｄ）＝ＤＥである。話を簡単にするために、８つの数式によって定義される位数８の部分群
0003701969.tif 000119
を選択すると次式が成立する。
0003701969.tif 000120
Ｗ3＝Ｌ3∩Ｍ3から混合変換Ｗ3＝｛Θ，Ｂ，Ｃ，Ｂ，Ｃ｝を読み取ることができ、したがって、
0003701969.tif 000121
は完全にコラプチブルである。次に、たとえば行６を使用してコセットを構築することができる。
0003701969.tif 000122
位数４のコラプチブル部分群の一例
0003701969.tif 000123
を下記に示す。
0003701969.tif 000124
Ｗ2＝｛Θ，Ｂ｝である。これから、次式のように、
0003701969.tif 000125
を２つのコセットに分割することができる。
0003701969.tif 000126
このコセット分割を使用する場合、別のコセット上で使用できる唯一の自明でない混合変換はＢである。
次に、
0003701969.tif 000127
中のｋ＝３個の連続行に命題７を適用すると、次式に示すように、やはり完全にコラプチブルな異なる部分群が得られる。
0003701969.tif 000128
数式５３中の部分群とは異なり、この場合、次式のように、Ｌ2⊂Ｒ3およびＭ2⊂Ｒ3によって、
0003701969.tif 000129
の異なるコセット分割が与えられる。
0003701969.tif 000130
命題７から、建設的コラプションを適用すると、
0003701969.tif 000131
は、
0003701969.tif 000132
では閉じるが、
0003701969.tif 000133
では閉じず、すなわち、たとえば、
0003701969.tif 000134
のＬ3中の数が
0003701969.tif 000135
の数と組み合わされることはない。この情報を使用して、様々な混合変換を矛盾なしで使用することができる。表ＩＩを参照されたい。
0003701969.tif 000136
縦座標は、数式５３の左側の列中の２進ブロックの行番号をリストし、横座標は、数式５３の中央の列中の２進ブロックの行番号をリストしたものである。表の項目は、線形アレイ数式５３中の数式の行番号と、対応する
0003701969.tif 000137
ブロックを対応する
0003701969.tif 000138
ブロックに加算することによって当該の数式を非線形アレイ中の別の数式に変換する混合変換である。たとえば、
0003701969.tif 000139
に対応する項目は、行１６９：ＡＥ▲＋▼ＢＦ＝ＡＢＥＦが、混合変換Ｃ▲＋▼Ｃ＝θを適用することによって、
0003701969.tif 000140
ブロックがＡＣＥであり、
0003701969.tif 000141
ブロックがＢＣＦであるＡＣＥ▲＋▼ＢＣＦ＝ＡＢＥＦに変換されることを意味する。項目がない場合、組合せは不可能である。８つの矩形がそれぞれ、２つのコセット
0003701969.tif 000142
のうちの一方の行を含むことに留意されたい。各列および各行を使用できるのは１度だけであり、表項目（行番号）を繰り返すことはできない。これが三次元表である場合は、各行、各列、各軸が１度しか使用できないことを意味する。
表ＩＩを使用して、建設的コラプションのパターンを選択することができる。たとえば、ミクサＢによって行１５５から変換される
0003701969.tif 000143
を選択する。次に、
0003701969.tif 000144
を選択する。
0003701969.tif 000145
には２つの選択肢が残る。
0003701969.tif 000146
を選択する。この場合、
0003701969.tif 000147
には１つの可能性、すなわち、
0003701969.tif 000148
とのペアリングしかない。次に、
0003701969.tif 000149
ブロックに進むと、識別変換を受け入れない限り、１つの選択肢、すなわち、
0003701969.tif 000150
しかない。残りの部分に関しては、選択肢はまったくなく、
0003701969.tif 000151
は選択されない。この場合、２つの混合変換を使用した。
他の手法は、識別変換を含め、すなわち、いくつかの行、たとえば、
0003701969.tif 000152
を未修正のままにしておくことである。この場合、すべての混合変換が使用されているが、２つの行６および１５５は未修正のままである。他の何らかのコセットの一部またはその和、すなわち、行３を修正することができるので、この２行は後で変換することができる。
前記の方法は、非線形化プロセスを整然と実行できるように、任意のサイズの部分群およびコセットに適用し、次いで、連続的に小さくなる部分群に適用することができる。線形アレイ中のすべての行を修正しなくても、通常、
0003701969.tif 000153
となるようにし、かつ値を均一に分散することができる。
前記は、完全な非線形直交写像を構築するための一般的な技法および方法を提示するものである。前記のｎ＝８の例は、具体的な数式を含む一般的な技法を例示するために与えられている。下記の節では、暗号でブロック換字を実施するのに適した特定の非線形化技法について説明する。
Ｖ．部分群の入れ子系列
第１８図および第１９図を参照すると、第１の好ましい非線形化方法が提示されている。この方法は、部分群の入れ子系列を使用するものである。
２n個の数式の線形アレイ中の数式の極大部分群から開始することによる非線形化である。Ｇn-1は、２n-1個のそのような部分群のうちの１つであり、｜Ｇn-1｜＝２n-1である。すべてのそのような極大部分群は、
0003701969.tif 000154
の極大部分群である３つの列のうちの１つ中のｎビット数を選択することによって指定することができる。すべての極大部分群は、すべて、所与のビット位置に零を有する数によって指定される
0003701969.tif 000155
のｎ個の極大部分群から求めることができる。直交写像アレイＧnのこれらの極大部分群はすべて、基本的に、同じ行間隔を有し、かつすべて同じ増分だけメンバー行の指数を変更することによって他方の部分群から得ることができる点で、相互の像である。したがって、数式のｎビット数の極大部分群も線形直交写像アレイの極大部分群も、容易に求めることができ、かつ容易に処理することができる。
Ｇn-1＝Ｌn-1×Ｍn-1×Ｒn-1は、Ｌn-1、Ｍn-1、Ｒn-1がそれぞれ、左側、中央、右側の列である２n-1個の数式の集合である。
0003701969.tif 000156
は補数である。混合変換の集合Ｗn-1＝Ｌn-1∩Ｍn-1は群であり、｜Ｗn-1｜＝２n-2である。Ｇn-1から、次式のような完全にコラプチブルな部分群の入れ子系列と、
0003701969.tif 000157
次式のような相対補数の同様な系列を構築することができる。
0003701969.tif 000158
上式で、
0003701969.tif 000159
であり、各数式は、次式のような関連混合変換群を含む。
0003701969.tif 000160
これらの部分群も、次式のような入れ子系列を形成する。
0003701969.tif 000161
限界では、Ｇ2は、ある指数ｉに関して中央列Ｍ2＝｛θ，ｘi，ｘi+1，ｘi▲＋▼ｘi｝であり、これに対応してＷ2＝｛θ，ｘi｝である。各１≦ｋ≦ｎ−２ごとに、次式が成立する。
0003701969.tif 000162
すなわち、
0003701969.tif 000163
は、Ｗn-k中のＷn-k-1の補数である。簡単で整然とした非線形化手順を下記に示す（かつ第１８図に図示する）。
ａ．
0003701969.tif 000164
中の２n-3個の混合変換を
0003701969.tif 000165
に適用する。これらの混合変換は、ｋ＞１の場合はＷn-kにはなく、したがって、その後に続くコセットＧn-kでは使用されない。
ｂ．
0003701969.tif 000166
中の２n-4個の混合変換をＧn-2に適用する。
ｃ．２つの混合変換が８つの数式に適用される
0003701969.tif 000167
に達するまで、このプロセスを順次継続する。
ｄ．位数４の最後の部分群Ｇ2では、ｗ＝ｘiを単独で
0003701969.tif 000168
に適用することも、あるいは、単にそのままにしておき、すなわち、ｗ＝θを適用することもできる。
前記の方法は、簡単であるだけでなく、２n-2−１個の自明でない混合変換を使用するという利点も有する。また、少なくとも２n−４個の数式が変換される。しかし、その結果得られる構造はある順序を保持する。Ｇn-1は、ｎ−１個の連続行の単一の集合を有し、群構造のために、ｎ−２個の連続行の別の集合を有する。したがって、命題４から、すなわち、ｎ−２個の行の集合を生成元として使用し、あるいは、Ｇn-1中のｎ−１個の連続行の集合の最初の行または最後の行を省略して、Ｇn-2を完全にコラプチブルな部分群として構築する３つの方法がある。まず、２n−１個の極大部分群を選択し、それに続く各レベルで３つの部分群を選択する必要がある。したがって、そのような入れ子系列の可能な総数は（２n−１）（３n-2）である。
次に、
0003701969.tif 000169
の左側の列、すなわち、
0003701969.tif 000170
中の２つの数ｘ、ｙを検討する。群補数であるために
0003701969.tif 000171
である。したがって、あるｋ＞１に関しては
0003701969.tif 000172
である。ｘおよびｙに適用される混合変換をそれぞれ、ｗaおよびｗbとする。
0003701969.tif 000173
である。
0003701969.tif 000174
に対する混合変換の集合は、
0003701969.tif 000175
である。したがって、ある例では、
0003701969.tif 000176
である。その場合、
0003701969.tif 000177
であり、建設的コラプションにもかかわらず、いくつかの線形部分群が残る。
前記の検討すべき点を考慮に入れ、特に第１９図を参照して、部分群の入れ子系列を使用するための好ましい暗号化方法について説明する。この方法は、ｎビット２進数の２n個のｎビット平文ブロックのうちのどれかを、関連する固有のｎビット２進数暗号化ブロックで置き換えることによって、データ・ブロックを暗号化するように動作する。この方法は、第１６図に概略的に示したように、非線形動的換字ジェネレータを使用して実施することができる。
第１９図を参照すると分かるように、第１の方法は、（１０）の場合と同様に、２n個の数式の第１の行列Ｇn、すなわち、各数式が、左側の列上の２n個のブロックのうちの１つと中央の列中の２nビット数のうちの固有の１つをｍｏｄ２加算して、右側の列の関連する固有のｎビット・ブロックを与えることを表す、線形直交写像を求めるために使用される。２n個の数式の第１の行列中のすべての数式は、任意の数の数式のｍｏｄ２ベクトル和が、第１の行列中の１つの数式でもあることを特徴とする。この数式は、識別数式Θ▲＋▼Θ＝Θを含む。ステップ１０２で、ＦＩＲＳＴ行中のｎ−１個の連続数式を選択し、これらの連続数式と識別数式のすべての和を求めて次式を得ることによって、ＦＩＲＳＴ行列の２n-1個の数式の部分集合Ｇn-1が選択される。
0003701969.tif 000178
上式で、ｓ＝２n-1−１であり、Ｌn-1、Ｍn-1、Ｒn-1はそれぞれ、左側、中央、右側の列であり、Ｇn-1＝Ｌn-1ＸＭn-1ＸＲn-1は、数式の集合を表し、
0003701969.tif 000179
は、Ｇn-1，Ｗn-1＝Ｌn-1∩Ｍn-1の補数であり、｜Ｗn-1｜＝２n-2である。
ステップ１０２ないし１１０で、２n個の数式の第１の行列中の２n個の非零数式のうちの複数の数式が、２n個の数式の第２の行列を形成するように修正される。数式は、修正済みの数式が全体として、第１の行列の左側の列と同じではあるが順序の異なる平文ブロックを、第１の行列の右側の列と同じ固有のｎビット・ブロックに、未修正の数式の最初の順序で写像するように修正される。複数の数式は、修正済み数式が、第２の行列中の他のどんな数の数式のｍｏｄ２和にもならないように修正される。２n−１個の非零数式の修正がステップ１０４ないし１０６で行われる。
具体的にはステップ１０４で、
0003701969.tif 000180
中の２n-3個の混合変換が
0003701969.tif 000181
に適用される。次にステップ１０６で、
0003701969.tif 000182
中の２n-4個の混合変換が
0003701969.tif 000183
に適用される。次にステップ１０８で、混合変換が、
0003701969.tif 000184
に達するまでＧn中のコセットに反復的に適用される。ステップ１０８の反復回数は、ｎの値に依存する。ｎ＝８を用いた場合、
0003701969.tif 000185
に達するには、ステップ１０４ないし１０８内で混合変換を合計で５回反復する必要がある。ステップ１１０で、
0003701969.tif 000186
は、θと単一の混合変換から成り、このどちらかが
0003701969.tif 000187
に適用される。最後にステップ１１２で、２n個の数式の第２の行列の左側の列中の２n個のｎビット数のうちの１つとしてユニークに位置する暗号化すべき各平文ブロックが、関連する数式の中央の列中のブロックにｍｏｄ２加算され、関連する数式の右側の列中の暗号化ブロックが得られる。
ステップ１１２は、最終的な暗号化ブロックを得るように働く。前記の第ＩおよびＩＩ節で説明した前の暗号化方法の場合と同様に、第１９図に示した方法のステップは、最大変換速度が得られるハードウェア回路を使用して実施することが好ましい。しかし、プログラムされたマイクロプロセッサを使用して、第１９図に示した様々な方法ステップを実行することができる。
ＶＩ．異なる部分群のフィット済みコセット（fitted coset）
次に、第２０図および第２１図を参照して、本発明の第２の好ましい暗号化方法について説明する。
第２０図の方法は、異なる部分群から、したがって、それぞれ異なるが、ジグゾー・パズルのようにはめ合わせることができる混合変換群によって、コセットを求めるものである。
第２０図および第２１図の方法は、異なる部分群からのフィット済みコセットを使用して、暗号化を実施する。最初に、この方法を概略的に説明し、次いで、第２１図に関して詳細に説明する。
0003701969.tif 000188
が、位数
0003701969.tif 000189
の互いに素な２つのコラプチブル部分群である場合、ｎビット数に関する極大線形直交写像のうちで、
0003701969.tif 000190
を、２つの異なるコセット分割と２つの異なる混合変換群とを含む位数２2kの１つの部分群として結合することができる。
0003701969.tif 000191
の組合せ生成元によって生成される部分群を
0003701969.tif 000192
とする。
0003701969.tif 000193
は、それぞれ、位数２kの
0003701969.tif 000194
の部分群と同型であり、したがって、相互に同型である、２つのコセット分割である。それぞれ、
0003701969.tif 000195
の一方から成る、コセット対は１つの行のみを共用する。複数の行を共用する場合、共用する対の和が
0003701969.tif 000196
中に存在するので、
0003701969.tif 000197
の場合は不可能である。１つのコセット対が行を共用しない場合、他の対が、複数の行を共用する必要がある。
0003701969.tif 000198
が互いに素なので、対応する混合変換群も互いに素である。ただし、
0003701969.tif 000199
中のある行が
0003701969.tif 000200
中のある行に隣接する場合、
0003701969.tif 000201
に対応する混合変換群は、追加メンバーを有する。次に、完全な
0003701969.tif 000202
のコセットに分割することができ、さらに、
0003701969.tif 000203
のコセットの交項集合として分割することができる。これは、ブロック・サイズｎに応じて、２つよりも多くのコセット分割に拡張することができる。２ではなく、位数２kの互いに素なある数ｃのコラプチブル部分群を選択した場合、
0003701969.tif 000204
である。
下記は、ｎ＝８の場合の一例であり、極大長線形直交写像は、識別の他に２５５の数式または行を含む。
この例を第２０図と下記の表ＩＩＩに示す。第２０図は、ブロック・サイズｎ＝８のブロック番号の２進数の極大長線形直交写像に関する多重コセット分割を図示したものである。表３は、ブロック・サイズが８の場合の極大長線形直交写像に関する１６行の４行コセットへの分割を示すものである。
0003701969.tif 000205
位数４の互いに素な３つのコラプチブル部分群、すなわち、
0003701969.tif 000206
を選択する。各部分群は、２つの連続行と、それらの和と、識別行とを有する。各部分群は、それ自体と、それぞれ、４つの数式から成る、６３個のコセットとから成る完全な線形アレイの固有のコセット分割を確立する。位数４の部分群は、位数１６の３つの部分群、すなわち、
0003701969.tif 000207
を定義するように結合される。位数１６の部分群は、互いに素ではない。最後に、これらの部分群は、
0003701969.tif 000208
からの位数６４の部分群
0003701969.tif 000209
として結合することができる。この部分群と、その３つのコセット
0003701969.tif 000210
は、完全な線形直交写像の分割を形成する。第２０図に示したように、６４行Ｑコセットのそれぞれを、３つの方法で、それぞれ１６行の４つのコセットに分割することができる。たとえば、
0003701969.tif 000211
に分割することができる。Ｍ分割を選択した場合、たとえば、
0003701969.tif 000212
をそれぞれ４行の４つのコセット、
0003701969.tif 000213
に分割することができる（表ＩＩＩ参照）。最後に、混合変換を適用して、建設的コラプション・プロセスを完了することができる。
必要に応じて、線形アレイ中のすべての数式をこのように修正することができる。この方法は、第Ｖ節の順序手法よりもある程度複雑ではあるが、数式９によって測定した非線形性に関してより優れた結果を与えた。
次に、異なる部分群からなるフィット済みコセットを用いたデータ暗号化の好ましい方法を第２１図を参照して具体的に説明する。上記の第Ｖ節で説明した方法と同様に、この方法は、２n個の固有のｎビット２進数平文ブロックのうちの１つを、関連する固有のｎビット２進数暗号化ブロックで置き換えることによって暗号化を達成する。最初、ステップ２０２で、２n個の数式の第１の行列Ｇnが求められる。この方法ステップは、第１９図のステップ１０２と同じものであり、本明細書ではこれ以上詳しくは説明しない。
ステップ２０４で、位数２kの２つ以上の互いに素なコラプチブル部分群
0003701969.tif 000214
がＧnから選択される
0003701969.tif 000215
次にステップ２０６で、必ずしも互いに素とは限らない位数
0003701969.tif 000216
の部分群
0003701969.tif 000217
の対から形成される。このプロセスは、ステップ２０８で部分群
0003701969.tif 000218
が選択されるまで継続する。ｎが偶数であるか、それとも奇数であるかに応じて、Ｇnが、ステップ２１０で、
0003701969.tif 000219
のコセットの交項集合に分割される。この場合、各部分群およびコセットは、連続的に小さくなるコセットに分割される。ステップ２１２で、選択されたコセットが、そのそれぞれの混合変換によって修正される。この結果得られる２n個の数式の第２の行列は、非線形直交写像である。
最後に、ステップ２１４で、２n個の数式の第２の行列の左側の列中の２n個のｎビット数のうちの１つとしてユニークに位置する暗号化すべき各平文ブロックが、関連する数式の中央の列中のブロックにｍｏｄ２加算され、関連する数式の右側の列中の暗号化ブロックが得られる。最後のステップ２１４は、前述の方法の暗号化ステップによるものであり、これについては詳しくは述べない。
第２２図は、ｎ＝８の暗号化に関する第２１図の方法を示す。最初、ステップ３０２で、２５６個の数式の第１の行列Ｇ8が求められる。２５６個の数式の第１の行列中のすべての数式は、任意の数の数式のｍｏｄ２ベクトル和も、第１の行列中の１つの数式であることを特徴とする。２５６個の数式の集合のうちの１つのは識別数式Θ▲＋▼Θ＝Θである。残りの２５５個の数式は、ステップ１１ｂに示したように順序付けることができる。しかし、これらの数式が一般的なｎビット・システムを表すのに対して、第２２図の方法のステップ３０２によって生成される数式は、８ビット・システムに対応する。したがって、Ｌ8、Ｍ8、Ｒ8はそれぞれ、左側、中央、右側の列である。Ｇ8＝Ｌ8ＸＭ8ＸＲ8である。
ステップ３０４ないし３１４は、２５６個の数式の第１の行列中の複数の非零数式を、２５６個の数式の第２の行列形成するように修正する。これらの数式は、修正済みの数式が全体として、対応する未修正数式の場合のように線形的ではなく、暗号化ブロックに対して非線形的に平文ブロックを写像するように修正される。複数の数式は、修正済みの数式が、数式の第２の行列中の他のどんな数の数式のｍｏｄ２加算にもならないように修正される。
ステップ３０４で、位数４の互いに素な３つのコラプチブル部分群がＧ8から選択される。互いに素な３つのコラプチブル部分群は、
0003701969.tif 000220
によって識別される。ステップ３０６で、位数４の互いに素なコラプチブル部分群対から位数１６の３つの部分群が生成される。位数１６の３つの部分群は、
0003701969.tif 000221
として識別される。
0003701969.tif 000222
から導出される。
0003701969.tif 000223
から導出される。
0003701969.tif 000224
から導出される。
ステップ３０８で、位数６４の部分群
0003701969.tif 000225
は、互いに素な３つのコラプチブル部分群の合併集合
0003701969.tif 000226
から導出される。ステップ３１０で、コセット
0003701969.tif 000227
が生成される。ステップ３１２で、１６行コセットは、それぞれ４行の４つのコセットに分割される。次に、ステップ３１４で、４つのコセットのそれぞれが、それぞれ４行の４つのコセットに分割される。ステップ３１６で、コセットは、上記の第ＩＩＩ節に示したようにそれぞれの混合変換によって変換される。
最後に、ステップ３１８で、暗号化すべき左側の列中の各平文ブロックが、２５６個の数式の第２の行列の関連する数式の中央の列中の対応するブロックにｍｏｄ２加算され、右側の列中の暗号化ブロックが得られる。
前述の実施例の場合と同様に、第２１図および第２２図に示した方法は、上述のブロック換字装置を使用して実施されるが、本明細書で述べたブロックの特定の処理を実施するように修正される。この処理を実施するハード回線回路を提供することが好ましい。しかし、プログラムされたコンピュータまたはマイクロプロセッサを使用することもできる。
ＶＩＩ．互いに素なコラプチブル部分群のコセット
次に、第２３図を参照して、データを暗号化するための第３の好ましい方法を説明する。この方法は、互いに素なコラプチブル部分群のコセットを使用するものである。最初に、この方法を一般的な数学的な観点から説明し、次いで、この方法の特定のステップを図面に関して説明する。
識別行を除いて２つの部分群が互いに素である場合、それらの部分群も、互いに素な混合変換部分群を有する。位数４の部分群対を考察すると、対応するコセット対が共用する行は１つだけである。そのような互いに素なコセットの集合をアセンブルする場合、各コセットが、異なる混合変換によってコラプトされる。このため、下記の２つの基本的な問題が発生する。
ａ．所与の線形直交写像でいくつのそのような互いに素なコラプチブル・コセットが見つかるか。
ｂ．対応する混合変換の集合にどんな群構造が存在するか。
良好な非線形直交写像を作成し、すなわち、数式３９で、
0003701969.tif 000228
にわたって一様な分布を有させるには、十分な数式をコラプトし、かつ頻繁に相互に無効化することのない混合変換の集合を有する必要がある。
極大長線形直交写像数式アレイでは、それぞれ、同じ相対間隔を有する、ｋ個の数式の２つの部分集合は、「相似」であると定義される。そのような２つの部分集合中央の列は、ある整数ｌに関して下記の形式を有する。
0003701969.tif 000229
極大部分群は、類似部分集合の例である。
命題８：
0003701969.tif 000230
が、位数４のコラプチブル部分群
0003701969.tif 000231
によって定義されるコセット分割中の位数２2＝４のコセットであり、
0003701969.tif 000232
に相似しているが、
0003701969.tif 000233
とは互いに素な４つの数式の集合である場合、
0003701969.tif 000234
は、他のコラプチブル部分群
0003701969.tif 000235
によって定義される分割中のコセットである。
前記の命題は、下記によって証明される。位数４のコラプチブル部分群は、次式の形式を有する。
0003701969.tif 000236
上式で、ｘq＝ｘj▲＋▼ｘj+1である。対応する混合変換はｘj▲＋▼ｘj＝θである。コセットは、部分群ではなく、部分群中の各行に行を加算して次式を得ることによって生成される。
0003701969.tif 000237
コセットの中央の列中の最初の２つの数の和ｘa▲＋▼（ｘj▲＋▼ｘa）＝ｘjは、混合変換を回復する。指数ｂのある行の場合はｘj▲＋▼ｘa＝ｘbである。同様に、ある指数ｃおよびｄの場合はｘj+1▲＋▼ｘa＝ｘcおよびｘq▲＋▼ｘa＝ｘdである。すべての指数をある整数ｌだけシフトした場合、下記のような数式の類似集合が形成される。
0003701969.tif 000238
指数をシフトする前は、ｘa▲＋▼ｘb＝ｘj、すなわち、最初の混合変換である。しかし、線形再帰関数によって生成される線形直交写像アレイの構造のために、ある指数ｋに関してｘa+1▲＋▼ｘb+1＝ｘk≠ｘjである。他の３つの行のそれぞれに行ａ＋１を換算すると、次式のような新しいコラプチブル部分群が得られる。
0003701969.tif 000239
上式で、ｘr＝ｘk▲＋▼ｘk+1である。３つの非零行は、
0003701969.tif 000240
中の対応する位置から、指数の差ｋ−ｊだけ変位される。
次に、前記の概略的な説明を考慮に入れて、この方法を第２３図に関して説明する。前述の第ＶおよびＶＩ節の方法と同様に、第２３図の方法は、関連する固有のｎビット２進数暗号化ブロックで置き換えることによって、２n個の固有のｎビット２進数平文ブロックの集合を暗号化するように働く。前述の方法と同様に、暗号化は、ステップ４０２で、各数式が、左側の列中の２n個の平文ブロックのうちの１つを、中央の列中の２n個のｎビット数のうちの固有の１つとｍｏｄ２加算して、右側の列中の関連する固有のｎビット・ブロックを与えることを表し、２n個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ２ベクトル和が第１の行列の１つの数式でもあることを特徴とする、線形直交写像を表す２n個の数式の第１の行列Ｇnを求めることによって開始する。数式は、零数式と、前記の数式１１ｂに示したように順序付けできる残りの２n−１個の数式とを含む。ステップ４０４ないし４１４で、第１の行列中の２n−１個の非零数式のうちの複数の数式が、２n−１個の数式の第２の行列を与えるように修正される。
ステップ３０４で、位数４のコラプチブル部分群がＧnから選択される。位数４のそのような部分群は一般に、次式で表される。
0003701969.tif 000241
上式でｘq＝ｘ1▲＋▼ｘ2である。
ステップ３０６で、位数４のコラプチブル部分群にはない、指数ａによって表される数式を選択することによって生成される。この数式が、コラプチブル部分群にベクトル的に加算されて、次式によって表されるコセットが生成される。
0003701969.tif 000242
上式で、ｘb＝ｘa▲＋▼ｘ1，ｘc＝ｘa▲＋▼ｘ2，ｘd＝ｘa▲＋▼ｘqである。ｍが素数でない場合は、ｍを除する整数ｌを選択する。
その後、ステップ３０８で、値ａ  ｍｏｄ１、ｂ  ｍｏｄ２、ｃ  ｍｏｄ２、ｄ  ｍｏｄ１に関して値が求められる。ステップ３１０で、ステップ３０８で求めた値のうちのどれかがが重複している場合、異なる指数の数式によってステップ３０６および３０８が反復される。重複のない値の集合が得られた後、ステップ３１２が実行され、ｍ／ｌ個の追加コセットが生成される。追加コセットは次式の形式を有する。
0003701969.tif 000243
上式で、
0003701969.tif 000244
である。
ステップ３１４で、混合変換が対応するコセットに適用される。この混合変換は、ｗkl▲＋▼ｗkl＝Θ（ｗkl＝ｗa+kl▲＋▼Ｘb+kl）で表される。各混合変換は、対応するコセットを建設的にコラプトするように適用され、そのため、２n個の数式の第２の行列を生成する。
最後に、ステップ３１６で、暗号化すべき左側の列中の各平文ブロックが、２n個の数式の第２の行列の関連する数式の中央の列中の対応するブロックにｍｏｄ２加算され、右側の列中の暗号化ブロックが得られる。最後のステップ３１６は、前記で本発明の好ましい他の実施例に関して説明した最後のステップに類似している。
第２３図で述べた様々なステップを実施するハード回線回路を提供することが好ましい。しかし、プログラムされたコンピュータまたはマイクロプロセッサを使用することもできる。
第２３図の方法の具体的な例として、数式５１中の直交写像を考察する。次式を
0003701969.tif 000245
とする。
0003701969.tif 000246
混合変換はＡである。行７を使用して、次式のようにコセットを生成する。
0003701969.tif 000247
中央の列から、混合変換は、ｘ7▲＋▼ｘ50＝Ｇ▲＋▼ＡＧ＝Ａである。指数をｌ＝５だけ変位して次式を得る。
0003701969.tif 000248
対応する部分群は、次式のように、行１２を他の３つに加算することによって求めることができる。
0003701969.tif 000249
新しいコセットまたは対応する部分群から、新しい混合変換はＦ▲＋▼Ｆ＝θである。
このプロセスは、より大きな位数の部分群に適用できるが、位数４のコセットと共に建設的コラプションに使用するのが特に容易である。手順は、下記のとおりである。位数４の任意のコラプチブル部分群を選択する。一般性を失わないように、部分群は次式のようになる。
0003701969.tif 000250
最初、ｍ＝２n−１が素数でない（すなわち、Ｍｅｒｓｅｎｎｅ素数でない）と仮定する。ｍを除するある整数ｌを選択し、前述の命題８の証明の場合と同様に、これを指数のシフトとして使用する。その同じ証明の場合と同様に、部分群中にない、ある指数ａを含む数式を選択する。この数式を数式７６中の各数式にベクトル的に加算すると、次式のコセットが得られる。
0003701969.tif 000251
次に、４つの値ａ  ｍｏｄ  ｌ、ｂ  ｍｏｄ  ｌ、ｃ  ｍｏｄ  ｌ、ｄ  ｍｏｄ  ｌを求める。重複がある場合は、このコセットを拒否して別のコセットを試す。なぜなら、これらの指数の増分としてｌの倍数を使用することによって類似の連続コセットを求めると、矛盾がもたらされるからである。たとえば、ａ≡ｂ  ｍｏｄ  ｌであると仮定する。その場合、ある整数ｇに関して、後に続くあるコセットが前のコセットと同じ行を有するようにａ＝ｂ＋ｇｌとなる。次に、ａ、ｂ、ｃ、ｄが異なるｍｏｄｌであると仮定する。次式の形式の
0003701969.tif 000252
の類似のコセットを生成する。
0003701969.tif 000253
上式で、
0003701969.tif 000254
である。これによって、建設的コラプションの候補として線形直交写像中の合計で
0003701969.tif 000255
の数式が与えられる。各コセットで、混合変換はｗkl▲＋▼ｗkl＝θ（ｗkl＝ｘa+kl▲＋▼ｘb+kl）である。数式７６および７７からｗ0＝ｘa▲＋▼ｘb＝ｘ1であり、したがって、ｗkl＝ｘ1+klである。したがって、混合変換の集合は、Ｗ＝｛ｘi｜ｉ≡１  ｍｏｄ  ｌ｝であり、
0003701969.tif 000256
である。
命題９：
0003701969.tif 000257
の類似のコラプチブル・コセットでは、
0003701969.tif 000258
の場合、任意の対ｘi，ｘjεＷに関して
0003701969.tif 000259
であることを証明することができる。３｜ｍでありｘｉ▲＋▼ｘｊ＝ｘｋである場合、すべての元がＷ中にある場合は
0003701969.tif 000260
である。
前記の命題は下記によって証明することができる。Ｗ∩θは群ではない。これが群である場合は、
0003701969.tif 000261
の部分群であり、ある正の整数ｋに関して
0003701969.tif 000262
である。その場合、
0003701969.tif 000263
である。ｌ＝２n-k｜ｌ−１である場合でも、この比率は奇数でなければならず、これに対して２kは、ｋ＞０の場合は偶数である。一般性を失わずに、ある関数ｇおよびｈに関してｘ1▲＋▼ｘ1+gl＝ｘ1+hlであり、すなわち、ｘ1，ｘ1+gl，ｘ1+hlεＷであると仮定する。ｈｌ＞ｍである場合、ｈｌ≡ｃｌ  ｍｏｄ  ｍであり、ｌ｜ｍなのでｃｌ＜ｍである。下付き文字が線形直交写像アレイ中の行の指数であることを考慮すると、ｘ1+gl▲＋▼ｘ1+2gl＝ｘ1+gl+hlも真である。
0003701969.tif 000264
であると仮定し、ｘ1+gl▲＋▼ｘ1+2gl＝ｘ1+gl+hlとｘ1▲＋▼ｘ1+gl＝ｘ1+hlを結合して次式を得る。
0003701969.tif 000265
さらに一般的には、すべての整数ｊに関して次式が成立する。
0003701969.tif 000266
したがって、すべてのｘkεＷに関してｘ1▲＋▼ｘkεＷである。同じ推論を、ｘ1ではなく他のｘiεＷに適用することができる。これは、Ｗ∩θが群であることを意味し、これは命題に矛盾する。次に、３｜ｍであると仮定する。次式の可能な和を考察する。
0003701969.tif 000267
数式８０をもたらす同じ手順を使用する場合、次式が成立する。
0003701969.tif 000268
したがって、同じ数式が得られる。したがって、これを使用して群を生成することはできない。
このことの実際的な結果は、２つの数式が同じコセット中にある場合、それらの和は他の位置にあるということである。これらの数式は、建設的コラプション用の共通の混合変換、たとえばｗiを有する。この和は、数式７６の部分群中の自明でない３つの数式のうちの１つになる。Ｓ（ｘ）＝Ｓ’（ｘ）▲＋▼ｗｉであることに留意されたい。この場合、Ｓ’（ｘ）は、線形直交写像から得た最初の写像であり、Ｓ（ｘ）は、建設的コラプションの後に結果として得られる写像であり、和数式が他のコラプチブル・コセットのうちの１つ中にない場合、数式４から次式が成立する。
0003701969.tif 000269
さらに、３つ組は線形になる。和数式は、他のコラプチブル・コセットにある場合、あるｗj≠ｗiを混合変換として有し、そのため、次式が成立する。
0003701969.tif 000270
異なるコセットから得た２つの数式を、それぞれの混合変換ｗiおよびｗjによって加算する場合、和数式がコセット中にあるか、それとも最初のコセットのうちの１つ中にあるか、それとも第３のコセット中にあるかに応じて、３つの可能性がある。
0003701969.tif 000271
２つの数式、すなわち、コセットから得た数式と、どのコセットにもない数式を加算する場合、前のケースと同様に、次式のような３つの可能性がある。
0003701969.tif 000272
最後に、どちらも、どちらのコラプチブル・コセットにも含まれない、２つの数式を加算する場合、その和がコセット中にあるか、それともないかに応じて、次式のような２つの可能性がある。
0003701969.tif 000273
残留線形性を最小限に抑えるには、前記から、２つの条件、すなわち、コセットに含まれない残りの数式の集合が、小さいことと、部分群を含まないことが必要であることが明らかである。一例として、８ビット２進数に関する数式５１中の同じ線形直交写像と、数式７２および７３中の部分群およびコセットを考察する。
0003701969.tif 000274
この場合も、行指数に増分としてｌ＝５を適用し、コセットの系列を生成する。次式に留意されたい。
0003701969.tif 000275
ｍ＝２n−１＝２５５＝５・５１なので、ｌ｜ｍであり、前記の行指数の集合が、ｌ＝５だけ増分されたときに重なることがなく、すなわち、すべての整数ｉ、ｊに関して７＋５i≠５０＋５jであり、他の対に関しても同じである。したがって、このプロセスによって、４つの数式のそれぞれの５１個のコセット、すなわち、建設的コラプションで修正すべき合計で２０４個の数式が生成される。命令８の証明で示したように、前記コセットの混合変換はＧ▲＋▼ＡＧ＝Ａであり、すなわち、最初の２つの数式の中央の項の和は、コセット中にある。
これは、線形直交写像中の第１の非零行の中央の項である。
0003701969.tif 000276
したがって、第１の数式が次式であるコセットとしてコセット５ｋを指定すると、
0003701969.tif 000277
対応する混合変換を下記に示す。
0003701969.tif 000278
したがって、加算識別を含めて、Ｗ＝｛θ，ｘ1，ｘ6，．．．，ｘ251｝であり、｜Ｗ｜＝５２である。ｍ＝２５５＝３・８５であるので、３｜ｍであり、ｘ1▲＋▼ｘ86＝ｘ171である。命題９の証明の場合と同様に、これは、すべてＷ中に存在する数のそのような３つ組に過ぎない。この例では、次式が成立する。
0003701969.tif 000279
もちろん、異なる部分群からコセットを選択することができる。たとえば、ｍ＝２５５＝１５・１７なので、同じ線形直交写像中でｌ＝１７を選択する。３つの異なる部分から得た３つのコセット（下記に示す）を考察する。
0003701969.tif 000280
0003701969.tif 000281
すべての行指数が異なるｍｏｄ１７なので、増分ｌ＝１７を使用しても重なりはない。このプロセスによって、建設的コラプションの候補として３×１５＝４５個のコセットまたは１８０個の数式が生成される。混合変換の集合を下記に示す。
0003701969.tif 000282
他の多数の可能性がある。たとえば、数式５２中の位数８の部分群を使用することができる。この部分群のコセットは完全にコラプチブルであり、すなわち、４つの混合変換の群を有する。命題７を適用すると、次式のように、数式５３の８つの数式のコセットを選択することができ、このうちの６つは非線形化することができる。
0003701969.tif 000283
増分ｌ＝１７を使用すると、次式から、それぞれ６行の互いに素な１５個の集合を得ることができる。
0003701969.tif 000284
行指数を７だけシフトすると、次式から、それぞれ６行の互いに素な１５個の集合をさらに得ることができる。
0003701969.tif 000285
この組合せは、非線形化用の１８０個の行または数式を与えるが、混合変換の集合はもはや、加算３つ組から自由ではなく、その結果、混合変換間にある種の群構造が生じる。
行指数をｍだけシフトする際に不連続な部分があるので、２n−１＝ｍが素数であるとき、互いに素な部分群からコラプチブル・コセットを得るプロセスは、わずかにより複雑になる。一例として、下記の母関数によって定義されるブロック・サイズ７極大長線形直交写像を考察する。
0003701969.tif 000286
数式５２の場合と同様に、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ｝を７ビット２進数の任意の完全な線形独立集合とすることができる。前述のように、表記法ＡＢＣは、Ａ▲＋▼Ｂ▲＋▼Ｃを短縮したものである。結果として得られる数式のリストの一部を下記に示す。
0003701969.tif 000287
位数４の典型的なコラプチブル部分群を下記に示す。
0003701969.tif 000288
これから、下記のコセットを構築することができる。
0003701969.tif 000289
0003701969.tif 000290
であるが、異なる行指数ｍｏｄ５を含むコセットが得られた場合、増分間隔が可能である。この場合、次式が成立する。
0003701969.tif 000291
これらの指数を５だけ変位すると、次式が得られる。
0003701969.tif 000292
これらの指数をさらに１５だけ変位すると、次式が得られる。
0003701969.tif 000293
これらの指数をさらに２０だけ変位すると、次式が得られる。
0003701969.tif 000294
これらの指数をさらに８０だけ変位すると、次式が得られる。
0003701969.tif 000295
最終的に１０だけ増分してさらに１ステップだけ進むことができる。
0003701969.tif 000296
このプロセスによって、建設的なコラプション・プロセス用の互いに素な２７個のコセットまたは１２７行のうちの１０４行が生成された。前記の手順では、指数０または３ｍｏｄ５のすべての行が使い尽くされた。したがって、他の異なる行指数を有するコラプチブル・コセットはもはや存在しない。しかし、指数１ｍｏｄ５の１５行、指数２ｍｏｄ５の２行、指数４ｍｏｄ５の２行が残る。混合変換は、各コセット中の最初の２行の中央の列中の数の和であり、すなわち、次式が成立する。
0003701969.tif 000297
したがって、混合変換の集合は、０≦ｋ≦２５の場合、Ｗ＝｛θ，ｘ1+5k，ｘ4｝であり、｜Ｗ｜＝２８である。この場合、命題９の条件が成立せず、すなわち
0003701969.tif 000298
であり、和もＷに存在するいくつかの対がＷ中に存在することに留意されたい。
非線形プロセス用のコラプチブル・コセットを選択するための他の多数の方法がある。異なる指数の混合コセットは、線形アレイ中のほぼすべての数式を含める機構を提供することができるが、これは、混合変換の集合の構造に対して平衡させなければならない。ｎビット数に関する直交写像の総数は不明である。
本明細書では、本発明の暗号化および復号化に関する好ましい実施例を開示し説明したが、当業者には、本発明の趣旨および範囲から逸脱せずに本発明の態様および詳細に様々な変更を加えられることが自明であろう。
ＶＩＩＩ．用語および記号の定義
すべての下記の定義は、ビットごとのｍｏｄ２加算（ＸＯＲｉｎｇ）演算を受けるｎビット２進数と、このような数に関する全単射写像を対象とするものである。
アフィン写像：定数ｃおよびすべての
0003701969.tif 000299
に対してＴ（ｘ）▲＋▼Ｔ（ｙ）＝Ｔ（ｘ▲＋▼ｙ）▲＋▼ｃになるような全単射写像、Ｔ  ｏｎ  Ｚ2。工学的には、これは線形と呼ばれることが多い。この場合、線形の語は、ｃ＝θであるケース、すなわち、加算識別に使用される。
平衡写像：
0003701969.tif 000300
の極大部分群をＨｉとし、すなわち、Ｈiは、位数｜Ｈi｜＝２n-1の部分群である。
0003701969.tif 000301
である。全単射写像Ｔが、すべての極大部分群に関して特性
0003701969.tif 000302
を有する場合、Ｔを平衡写像と言う。完全にコラプチブル：極大数の混合変換を含むコラプチブル・コセット。完全にコラプチブルなコセットの位数が２kである場合、対応する混合変換の集合の位数は２k-1である。
建設的コラプション：線形数式アレイの２つの列中のブロックの順序を再構成し（第２図）、第３列を固定されたままにし、同時に、各行の等性を維持することによって、線形直交写像を非線形直交写像に変換するプロセス。
コラプチブル集合：建設的コラプション・プロセスによって独立集合として非線形化することができる数式の集合、通常はコセットまたは部分群。
動的換字装置：
0003701969.tif 000303
すなわち、ｎビット２進数に関する直交写像を使用して暗号化または復号化を行うブロック換字装置またはＳボックス。
母関数：下記の形式の再帰関数。
0003701969.tif 000304
ｎビット数の完全な線形独立集合に適用されたときに、数式１１中の線形直交写像を定義する。これは、線形フィードバック・シフト・レジスタの母関数と同じものであるが、個別の２進ビットではなく定義域
0003701969.tif 000305
を含む。母関数は、ガロア体ＧＦ（２n）における原子多項式である。
線形アレイ：
0003701969.tif 000306
に関する線形（同型）写像を表す２n個の数式のアレイ（数式１１参照）。
線形直交写像：写像
0003701969.tif 000307
が線形である直交写像。
極大直交写像：単一の固定点を除いて巡回を有さない
0003701969.tif 000308
の置換として表すことができる
0003701969.tif 000309
に関する直交写像。
混合変換：建設的コラプション・プロセスで使用される形式ｗ▲＋▼ｗ＝θの数式。混合変換が線形直交写像中の数式のコラプチブル集合にベクトル的にｍｏｄ２加算されて、非線形直交写像が得られる。
直交写像：各数がその像にｍｏｄ２加算されたときに
0003701969.tif 000310
のすべてが生成されるような
0003701969.tif 000311
に関する１対１写像、すなわち、次式のような
0003701969.tif 000312
0003701969.tif 000313
直交置換：直交写像によって定義される
0003701969.tif 000314
に関する置換。
行：
0003701969.tif 000315
に関する直交写像を表す数式のアレイ中の単一の数式（数式１０参照）。シフト：線形直交写像を表す数式のアレイ中のｎビット数の列間の変位。各列は、同じ順序であるが、異なる開始点を有する（数式１１参照）。
相似集合：同じ相対間隔を有する線形アレイ中の数式の部分集合。
ベクトル：
0003701969.tif 000316
中の係数を有する三次元中のベクトルとみなすことができる線形アレイ中の行または数式。
0003701969.tif 000317
【図１】
0003701969.tif 000333
【図２】
0003701969.tif 000334
【図３】
0003701969.tif 000335
【図４】
0003701969.tif 000336
【図５】
0003701969.tif 000337
【図１０】
0003701969.tif 000338
【図６】
0003701969.tif 000339
【図７】
0003701969.tif 000340
【図８】
0003701969.tif 000341
【図９】
0003701969.tif 000342
【図１１】
0003701969.tif 000343
【図１２】
0003701969.tif 000344
【図１３】
0003701969.tif 000345
【図１４】
0003701969.tif 000346
【図１５】
0003701969.tif 000347
【図１７】
0003701969.tif 000348
【図１６】
0003701969.tif 000349
【図１８】
0003701969.tif 000350
【図１９】
0003701969.tif 000351
【図２０】
0003701969.tif 000352
【図２１】
0003701969.tif 000353
【図２２】
0003701969.tif 000354
【図２３】
0003701969.tif 000355