JPH09501281A - 非線形動的換字装置およびブロック換字方法 - Google Patents

Abstract

(57)【要約】 換字方式自体を比較的簡単なハードウェアと併用できるようにし、しかも暗号分析をより困難にする、ブロック換字技法（２２および３０）によってｍｏｄ２加算ベースの暗号化を非線形化する方法および装置。基本ブロック換字（２２および３０）は、ｎビット２進数のそれ自体への１対１写像であり、ｎビット２進数のある種の置換によって、線形直交写像が定義され、そのため、ある数の置換済み集合を別の置換済み集合にｍｏｄ２加算することによるブロック換字が可能になることに基づくものである。線形直交写像を表すこれらの数式は、ベクトルとみなしたときに加算関係を有し、実際に、代数的に加群を形成する。これらの線形直交写像を定義するｎビット２進（２２）数の置換は、このような置換を累乗し、すなわち、置換を、前に置換された数（３０）に連続的に適用すると、新しい線形直交写像が生成されるという他の特性を有する。

Description

【発明の詳細な説明】 非線形動的換字装置およびブロック換字方法関連出願 本出願は、１９８９年１０月４日に出願された米国特許出願第０７／４１６９ ５３号の一部継続出願である、１９９３年８月５日に出願された米国特許出願第 ０７／７４１０９７号の一部継続出願である。発明の背景 １．発明の分野 本発明は、暗号化装置および方法の分野に関し、詳細には、ブロック換字暗号 化方法および装置に関する。 ２．従来の技術 多くの場合、受信側にとって明確であるが、送信側と受信側の間に割って入る 者には分からないように、ある位置から別の場所へディジタル形で情報を伝達す ることが望ましい。したがって、多くの例では、何らかの所定の暗号化プロセス によって、伝達すべき情報を暗号化し、暗号化された形の情報を送信し、次いで 、受信側位置でその情報を復号するのが一般的である。偶然に送信側と受信側に 間に入った者にとってはどんなレベルの暗号化でも送信の意味がわからないので 、所望のセキュリティの程度に応じて、比較的簡単で容易に破られる暗号化を使 用することもできる。他の状況では、所望のセキュリティの程度は、暗号解析に よって復号することがより困難な暗号化技法を使用するものであり、あるいは、 最高のレベルのセキュリティで、復号がほぼ不可能になることが望ましい。その ような暗号化技法の応用例には、製造工場、銀行支店など間の機密通信などの商 業応用例と、ＩＦＦ（敵味方識別装置）を含むが、これに限らない軍事応用例が 含まれる。あるケースでは、暗号化の主要な目的は、第３者が通信中の情報を復 号することを妨げることであるが、他のケース、すなわちＩＦＦなどでの主要な 目的は、第３者が、所期の受信側を誤らせるように同じ暗号化方式で擬情報を発 信 するのを妨げることである。多くの応用例では、２つの目的が共に存在すること が多い。 ブロック換字とは、２進数の列の形の平文メッセージを暗号化するために使用 される方法である。この方法によれば、ブロック換字装置が、平文中の各２進数 ブロックを新しい固有の２進数ブロックで置き換えることによって、列が、いく つかの所定のブロック長ｎのブロックに分割される。換字ブロックは、暗号化メ ッセージまたは符号テキストを構成し、各換字ブロックは、平文ブロックの明確 な１対１の情報を表す。従来技術では、そのような換字は一般に、参照テーブル 、スイッチング構成、またはフィードバック・シフト・レジスタによって行われ る。しかし、符号または換字方式を頻繁に変更しないと、暗号化が符号解析によ って破られることがある。しかし、参照テーブルを変更するのは厄介であり、実 施できる可能なスイッチング構成の数は限られており、シフト・レジスタを繰り 返し巡回させるのは時間がかかる。パターンもバイアスも有さない換字を見つけ る際にはそれ以外の問題が発生する。現在、コンピュータ・シミュレーションに よって、候補換字が可能な体系的パターンがあるかどうか調べられており、ある ケースでは、この問題を補償するために追加回路が使用されている。 従来技術では、様々なタイプの暗号化装置および方法が周知である。たとえば 、米国特許第３７９６８３０号、米国特許第３７９８３５９号、米国特許第４０ ７８１５２号、米国特許第４１９５２００号、米国特許第４２２５８１１号、米 国特許第４３１６０５５号、米国特許第４５２０２３２号を参照されたい。一般 に、これらのシステムは、ブロック換字に関するものであるとき、鍵依存暗号化 ・復号化システムであり、本発明とは異なり、ある加算置換済み数の集合と別の 加算置換済み数の集合のｍｏｄ（モジュロ）２加算による換字に基づくものでは ない。 親の親特許出願では、換字方式を比較的簡単なハードウェアと共に使用できる ようにするブロック換字技法によるｍｏｄ２加算ベースの暗号化を開示した。こ のブロック換字は、ｎビット２進数のそれ自体への１対１写像であり、ｎビット ２進数のある種の置換によって、ある置換済み数の集合と別の置換済み数の集合 のｍｏｄ２加算によるブロック換字が定義されることと、このような定義済み数 式が、ベクトルとして見たときに加算関係を有し、そのため、数式の限られた部 分集合から集合の残りの部分を生成することができることに基づくものである。 これによって頻繁に行われる変換の変更が簡単になる。変換の様々な特性とこの 変換を使用する方法が開示されている。しかし、セット数式の残りの部分が数式 の限られた部分集合から生成できることによって、符号解析は、ある種の応用例 で必要とされるよりも難しいものになる。親出願は、セット数式の残りの部分が もはや、数式の限られた部分集合からは生成できないように、数式をやはり整然 と容易に変更できるように非線形化する方法および装置に関するものであった。 本発明は、数式を非線形化するこれ以外の方法を提供するものである。発明の簡単な説明 置換方式を比較的簡単なハードウェアと共に使用できるようにし、しかも暗号 解析をさらに困難にする、ブロック換字技法によるｍｏｄ２加算ベースの暗号化 を非線形化する方法および装置。この基本ブロック換字は、ｎビット２進数のそ れ自体への１対１写像であり、ｎビット２進数のある種の置換によって、ある置 換済み数の集合と別の置換済み数の集合のｍｏｄ２加算によるブロック換字が定 義されることと、このような定義済み数式が、ベクトルとして見たときに加算関 係を有することができることに基づくものである。これによって、変換を簡単に 頻繁に変更することができる。その場合、数式の集合の残りの部分がもはや、数 式の限られた部分集合からは生成できないように、数式がやはり整然と容易に変 更できるように非線形化される。この変換の様々な特性と、この変換を使用する 方法を開示する。具体的には、本発明によって提供される非線形化方法は、部分 群の入れ子系列と、フィット済みコセット（fitted coset）と、互いに素なコラ プチブル（corruptible）部分群のコセットとを含む。図面の簡単な説明 第１図は、ｍｏｄ２加算によるある３ビット２進数の集合の別の２進数の集合 への複数対単一変換を示す図である。 第２図は、ｍｏｄ２加算によるある３ビット２進数の集合の別の２進数の集合 への１対１変換を示す図である。 第３図は、第１の数式を除いて、第１列中の３桁数が前の行の第２列中の３桁 数と同じになるように順序変更された第２図の変換数式を示す図である。第１の 数式を除いて、各列は、同じ順序ではあるが、異なる開始位置を有するものとな っている。 第４図は、第１列および第３列が第２列に対して垂直にシフトされた、第３図 に対応する図である。このシフトはそれぞれ、下向きに６つおよび２つの位置で ある。第１の数式を除いて、各列は同じ順序ではあるが、異なる開始位置を有す る。 対応する図である。 第６図は、データを暗号化する装置のブロック図である。 第７図は、第６図の装置によって暗号化されたデータを復号する装置のブロッ ク図である。 第８図は、第６図を使用する暗号化の一例を示す図である。 第９図は、第７図を使用する暗号化の一例を示す図である。 第１０図は、第４図の列１および２に固定語００１が加算された、第４図の変 換数式に対応する変換数式の集合を示す図である。第１の数式を除いて、列１お よび２は同じ順序ではあるが、異なる開始位置を有する。 第１１図は、第１０図の変換数式のような変換数式の集合によってデータを暗 号化する装置のブロック図である。 第１２図は、第１１図の装置によって暗号化されたデータを復号する装置のブ ロック図である。 第１３図は、第１１図を使用する暗号化の一例を示す図である。 第１４図は、第１２図を使用する暗号化の一例を示す図である。 す図である。 第１６図は、本発明による暗号化・復号化システムのブロック図である。 第１７図は、付録２のＡ１２ページに提示した数式の集合の第１列および第２ 列にオフセット０１０１を加算することによって導出された暗号化および復号化 に有用な数式の集合を示す図である。 第１８図は、部分群の入れ子系列を使用して数式群を非線形化する方法を図示 する図である。 第１９図は、部分群の入れ子系列を使用する暗号化方法を示すブロック図であ る。 第２０図は、ブロック・サイズｎ＝８の２進数に関する最大長線形直交写像の 多重コセット分割を示す図である。 第２１図は、第２０図に図示した異なる部分群から得たフィット済みコセット を使用する暗号化方法を示すブロック図である。 第２２図は、ブロック・サイズｎ＝８の場合の第２１図の方法を示すブロック 図である。 第２３図は、互いに素なコラプチブル部分群を使用する暗号化方法を示すブロ ック図である。発明の詳細な説明 本発明は、親出願および親の親出願で詳細に説明したブロック換字によってｍ ｏｄ２加算ベースの暗号化を非線形化する方法および装置を含む。本出願では、 本発明を改良する基礎を提供するために、親出願および親の親出願の開示を繰り 返す。具体的には、親の親出願の態様を下記の第Ｉ節「ブロック置換」で述べる 。親出願の発明の説明は、第ＩＩ節「非線形化の概要」に記載する。本発明に関 連する開示は、残りの節に記載する。具体的には、第ＩＩＩ節「線形直交写像の 修正（MODIFICATION OF LINEAR ORTHOMORPHISMS）」で、親出願および親の親出 願で説明した線形直交写像（linear orthomorphisms）の予備的な修正および変 形について説明する。第ＩＶ節「完全な非線形直交写像の構築」では、非線形直 交写像の一般化を行う。第ＩＶ節「完全な非線形直交写像の構築」には、ブロッ ク・サイズｎ＝８の場合の直交写像の構築を説明する詳細な例を提示する。ブロ ック換字数式の集合を非線形化する改良された第１の方法を第Ｖ節「部分群の入 れ子系列」に提示する。改良された第２の非線形化方法を第ＶＩ節「異なる部分 群からのフィット済みコセット」に提示する。改良された第３の非線形化方法を 第ＶＩ Ｉ節「互いに素なコラプチブル部分群のコセット」に提示する。第ＶＩＩ節はさ らに、ブロック・サイズｎ＝８を有するブロック換字システムの詳細な例を含む 。最後に、第ＶＩＩＩ節「用語および記号の定義」は、親出願および親出願に添 付の付録内で使用された語の用語集である。第ＶＩＩＩ節「用語および記号の定 義」ではさらに、本明細書で使用するある種の計算記号を定義する。 本明細書には、付録Ｉ「不偏ブロック換字」、付録ＩＩ「ブロック換字機構と しての非線形動的置換装置」、付録ＩＩＩ「非線形動的換字方法」、付録ＩＶ「 建設的コラプション：非線形動的換字を生成する方法」、付録Ｖ「建設的コラプ ションＩＩ：非線形動的換字を生成する方法」、付録ＶＩ「２進数の非線形写像 の代数構造」を含む６つの付録も添付されている。 Ｉ．ブロック換字 下記の説明ではまず、親出願の方法および装置を、ｎビット２進数のブロック （ｎ＝３）に関して説明する。次いで、この方法および装置を一般的にｎビット ・ブロックに展開し、ｎ＝８までのブロックのある特性を提示する。ｎ＝３の場 合の下記の例を提示することによって、より多くの集合を有するより大きなブロ ックを使用するケースよりも、原発明の概念がよりよく理解されると思われる。 ブロック換字とは、通常、ｎビット２進数のそれ自体への１対１写像に適用さ れる語である。この写像は、次式のように、２ⁿ個のｎビット数を対にしたもの として書くことができる。 上式で、各列は、互いに素であるが、異なる順序で書かれた、同じ２ⁿ個のｎ ビット数の集合である。したがって、この写像は、下記のようにｎビット数を置 換したものとみることも、 あるいは、ある種の指標の集合では（Ｘ_l Ｘ_i Ｘ_j）とみることもできる。の 通常の置換表記法は、Ｘ_l→Ｘ_i，Ｘ_i→Ｘ_j（以下同様）であることを意味するに 過ぎない。 列表記法に戻ると、最初の集合およびその写像から簡単な数式の集合を定義す ることができる。 を意味する。一般に、集合｛Ｙ₁，Ｙ₂，．．．｝は、全て異なる値ではないが、 ある種の状況ではすべて異なる。原発明によれば、集合の値が異なっているとき 、従来型の手段ではなくｍｏｄ２加算によってブロック換字を生成することがで きる。この場合、主として、この方式が作用する状況がもしあれば、それを判定 し、 さらに、どうすれば換字を迅速に変更できるかと、バイアスがないことを判定し なければならない。 ブロック換字がｍｏｄ２加算によって生成できるかどうかは自明ではない。た とえば、第１図に示した、ｍｏｄ２加算によって３ビット２進数のある構成で他 の構成を置き換える試みを検討する。右側の列３で、０１１および１００はそれ ぞれ２回現れるが、００１および１１０は一度も現れない。左側の列１中の数は 、中央の列２の数に作用し、列１の３ビット２進語の集合のそれ自体への変換を 構成するものである。これは、多数対単一変換であり、変換済みブロック０１１ および１００の最初のブロックを回復しようとする際に生じるあいまいさのため にブロック換字には無用である。 第２図に示すように他の構成を試みると、異なる結果が得られる。この場合、 任意の１対の列が、１対１変換を構成する。具体的には、この変換は、列３の３ ビット２進数（平文）からそれ自体、すなわち、列１の暗号文への１対１変換で ある。各列は、一度しか現れないすべて３ビットの数から成る。 第２図の変換を使用して、３桁２進ブロックを暗号化２進ブロックに変換し、 もちろん、同じ数式を使用して、列１中の復号語を見つけ、次いで第２図の同じ 行・列３中の対応する平文語を選択することによって、暗号化メッセージを復号 ＝を相互交換する場合に最も好都合である。復号語を平文に変換する等価変換は 、列１の語を列２の語に加算して列３の語を得る場合に行われる。 再び第２図を参照すると、この変換の興味深い特性が示されており、そのため 、本明細書に関するタイプのすべての変換を見ることができる。具体的には、３ つの２進数の８つのブロックのうちで、小さい数の４つのブロック０００、００ １、０１０、０１１は、小さい数の４つのブロックのうちの２つのブロック、す なわち０００および００１と、大きいの数の４つのブロックのうちの２つのブロ ック、すなわち１１０および１１１にマップされる。同様にもちろん、８つのブ ロックのうちのより大きな数の４つのブロックは、そのうちの２つが小さな数の ４つのブロックにマップされ、他の２つが大きい数の４つのブロックにマップさ れる。同様に、偶数ブロック０００、０１０、１００、１１０は、２つの偶数ブ ロック ０００および０１０と、２つの奇数ブロック００１および０１１にマップされる 。４つの奇数ブロックは、そのうちの半分が奇数ブロックにマップされ、残りの 半分が偶数ブロックにマップされる。復号にも同じことが当てはまるのは自明で ある。したがって、大きい、小さい、偶数、奇数など、暗号化ブロックのある種 の特性の知識が、非暗号化ブロックの特性の同様な知識を与えることはない。こ の結果、この暗号化は不偏であると言われる。そのため、各ブロックの中央の数 字を検討した場合でも、中央の数字がゼロである第２図の４つのブロックは、そ のうちの２つのブロックが、やはり中央の数字がゼロであるブロックにマップさ れ、残りの２つのブロックが、中央の数字が１であるブロックにマップされるこ とに留意されたい。同様にもちろん、中央の数字が１である４つのブロックは、 そのうちの２つのブロックが、中央の数字が１であるブロックにマップされ、残 りの２つのブロックが、中央の数字がゼロであるブロックにマップされる。この 特性は、すべてのブロック・サイズに適用され、代数的には最大部分群として特 徴付けることができるすべてが等しいブロックの集合への分割に拡張する。暗号 化のこの不偏特性は、特に暗号化の頻繁な変更に関して本明細書で開示する暗号 化方式の非常に有用な特性である。 具体的には、もちろん、任意の実際的な暗号化装置で、パターンが、それを符 号分析するのに十分な時間にわたって持続しないように暗号化方式を頻繁に変更 することができる。このために、第２図の行を第３図に示したように再構成する ことによって、第２図の数式のある種の特性を認識することができる。もちろん 、どのように行を再構成しても、各数式が、それ自体の完全性をテーブル中の位 置とは別に維持するので、変換に影響が及ぶことはない。基本的に、第３図の第 ２行は、第２図中の第４行であり、第３図の第３行は第２図中の第５行であり、 各連続行は、その左側の列が、その前の行の第２列と同じ３ビット数を含むよう に構成される。そのように構成すると、第１行または識別行を無視した場合、３ つの列のそれぞれが、ラップアラウンドによる３ビット２進数の同じ系列を含む ことに留意されたい。具体的には、第１列は、第２列と同じ系列を有するが、第 ２列から下向きに１つの位置（あるいは、上向きに６つの位置）だけ変位されて おり、第３列は、第２列と同じ系列を有するが、列２から下向きに３つの位置（ あ るいは、上向きに４つの位置）だけ変位されている。 再び第３図の第１行または識別行を無視すると、ラップアラウンドによって、 列１中の３ビット２進数を、第２列に対して下向きに合計で６つの位置だけシフ トした場合でも、第４図に示したように、１対１変換が行われることに留意され たい。識別行を除いて、変換は、第３図の変換とはまったく異なるものである。 一例を挙げると、第３図の列３の１１１は列１の０１１にマップされ、第４図の 列１の１００にマップされる。第４図の列１および３中の３桁数の系列（識別行 を除く）が、それぞれの数がラップアラウンドによって列２に対してシフトされ るにもかかわらず、第３図と第４図の列２中の系列と同じであることに留意され たい。したがって、第３図の変換は、単に第３列の第１列中の数を第２列中の数 に対してシフトし、第３列中の数も、第２列中の数に対して異なる量だけシフト してｍｏｄ２加算式の完全性を維持することによって、第４図の新しい変換に変 ＝を相互交換することができる。 さらに一般的に、任意のブロック・サイズに関して、数式の集合を下記のよう に書くことができる。 ブロック・サイズｎの場合、ｍ＝２ⁿ−１である。θ＝００．．．００であり 、ｎビット語はすべてゼロから成る。 列１を列２に対してＳ個の位置だけシフトした場合、ｍｏｄ２加算式の完全性 を維持するために、列３は、異なる量Ｐ_sだけシフトされる。所与のシフトＳの 場合、Ｐ_sはシフト・プログラマによって決定される。 次に第６図を参照すると、前記で論じた暗号化技法および復号技法によって暗 号化を実施するシステムのブロック図を見ることができる。 平文語は、メモリＩ中の前記語のアドレスに送られる。これは、列３からθ以 外の語Ｘ_k-Psを選択することに対応する。この概念はＸ_k-Psを列２の対応するも のに加算することである。Ｘ_k-Psが、θ以外のものであり、Ｘ_kに加算される予 定である場合、これは、列３中の順序データＫ−Ｐ_sを含む語を、やはり列３中 の順序Ｋ−Ｐ_s＋Ｐ_s＝Ｋを含む語に加算することと等価である。したがって、平 文語Ｋ−Ｐ_sの順序データは、Ｐ_sに加算すべき加算器へ送られる。この新しい順 序数は、メモリＩＩ中のその数のアドレスへ送られる。そのアドレスの内容は、 平文語にｍｏｄ２加算され、列１中の暗号化語Ｘ_k-sが得られる。平文語がθで ある場合、その暗号文写像は同じである。 順序データの加算は、２つの加算器、桁上げ（Ｃ）、および最下位ビット（Ｌ ＳＢ）によって行われる。桁上げ加算器は、従来どおり桁上げによって数を加算 し、たとえば、００１＋０１１＝１００とする。しかし、加算でｎ桁よりも多く の桁が必要である場合、１がｎ＋１位置に桁上げされ、その余分の１はその代わ りに、第１の位置に加算され、たとえば、１００＋１１０＝１０１０＝＞０１１ となる。これは、ＬＳＢ加算器によって行われる。ｍ＝２ⁿ−１の場合、これは ｍｏｄｍ加算に過ぎない。この例では、ｎ＝３、ｍ＝７であり、１０進項で表さ れる加算は４＋６＝１０≡ｍｏｄ７（１００＝＞４、１１０＝＞６、０１１＝＞ ３）である。 復号に関するブロック図を第７図に示す。暗号文語は、メモリＩ中の前記語の アドレスに送られる。これは、列１からθ以外の語Ｘ_k-sを選択することに対応 する。この概念は、Ｘ_k-sをそれに対応するもの、すなわち、列２中のＸ_kに加算 することである。これは、列１中のＸ_k-sを、やはり列１中の順序データＫ−ｓ ＋ｓ＝Ｋを含む語に加算することと等価である。したがって、暗号文語の順序デ ータのＫ−ｓは、ｓに加算すべき加算器へ送られる。この新しい順序数は、メモ リＩＩ中のその数のアドレスへ送られる。そのアドレスの内容は、暗号文語にｍ ｏｄ２加算され、列３中の復号化語Ｘ_k-Psが得られる。暗号文語がθである場合 、その語はθとして復号される。 順序データの加算、すなわち、Ｋ−Ｓ＋ＳおよびＫ−Ｐ_s＋Ｐ_sは、ｍｏｄｍま たはラップアラウンドによるものと理解される。すなわち、順序データがｍより も大きい場合、最後の位置のｍが順序データが減算される。暗号文語がθである 場合、その語は同じ語として復号される。 シフト・プログラムは、列１中のシフトＳが列３中の対応するＰ_sシフトＳと 共に使用される順序を決定する。任意の所望の順序を使用することができる。シ フトＳは、８ページで説明した基本置換の累乗に対応する。これは、加算による 換字を決定する。 したがって、一例を挙げると、第８図で、平文データ値が０１０である場合、 メモリＩ中の前記データ値のアドレスは順序データ００１を提供する。これは、 ０１０がメモリＩ中の系列中の位置１（数式の集合の列３）にあることを示す２ 進表記法である。プログラム中の第１のシフト位置はＳ＝６であり、この場合、 Ｐ₆＝２である。０１０の位置、すなわちＫ−Ｐ₆＝１にＰ₆＝２が加算される。 ２進表記法では、００１＋０１０＝０１１である。メモリＩＩ中のアドレス０１ １には数１００が対応する（これは、１００が列３中の位置３にあると言うのと の加算式のうちの第１の数式を表す。 復号の場合、暗号文語は１１０である。第９図で、メモリＩ中の前記語のアド レスは、順序データ１００、またはメモリＩ中の系列中の位置４を提供する。プ ログラム中の第１のシフト位置はＳ＝６である。１１０の位置、すなわち、Ｋ− ６＝４に６、あるいは２進表記法では１１０が加算される。すなわち、４＋６＝ １０である。ｍ＝７を減算すると、１０−７＝３であり、あるいはラップアラウ ンドによる位置３が得られる。２進表記法では、１００＋１１０＝０１１ｍｏｄ ７である。メモリＩＩ中のアドレス０１１には数１００が対応する。すなわち、 式を表す。 第４図の第１列および第２列に固定数をｍｏｄ２加算した場合、次の１対１変 換が行われる。 次に、第１１図および第１２図を参照すると、任意のブロック・サイズに関し て、θ以外の固定語、すなわち、ゼロ語を使用して暗号化および復号化を実施す るためのブロック図を見ることができる。この手順は、前述の手順とほぼ同じも のであり、暗号化プロセス中の最後のステップおよび復号プロセス中の第１のス テップとして固定語のｍｏｄ２加算を行う追加ステップを含む。 一例を第１３図および第１４図に示す。この場合、０００はもはや固定されず 、００１に変換される。次に、１１０がそれ自体に変換され、したがって、この 場合は固定される。 固定語加算器は、ユーザが選択した順序でどれかまたはすべてのｎビット語を 連続的に加算することができる。 次に、第８図を参照すると、一例として、前記で論じた暗号化技法および復号 化技法によって暗号化を実施するシステムのブロック図を見ることができる。図 のように、０００を除く平文データ２０の任意の値が、メモリ２２へのアドレス として提供される。様々なメモリ・アドレスに、平文データ値に関する順序デー タ、すなわち、第４図（および第５図および第１０図）の右側の列の順序付き系 列中の前記平文データ値の、２進数で表された位置が記憶される。この位置は、 加算器２４および２６の組合せとして示した加算器へのメモリ２２の出力として 提供される。これらの加算器は、シフト・プログラマ２８の制御に応じてメモリ の出力をシフト値Ｐ_sに加算するように結合される。この加算は、ｍｏｄ２加算 ではなく、通常の２進加算である。ただし、最上位ビットから桁上げは、最下位 ビットのキャリーインに結合される。したがって、この加算器は、結果００１を 、１０００でも単なる０００でもなく、１１１よりも大きな和１として提供する 。したがって、加算器の出力は、順序データ系列で量Ｐ_sだけシフトされた新し い３ビット２進値である。この場合、この新しい位置は、メモリ３０向けのアド レスとして使用され、メモリ３０は、第４図の列２中の値に対応する３ビット２ 進値、または第３図中の対応する平文データ値を、その出力として提供する。し たがって、一例を挙げると、平文データが０１０である場合、メモリＩへのアド レスとしてのこの値は、この値の位置、すなわち系列中の００１を提供する。シ フト・プログラムがＳ＝６を選択した場合、Ｐ₆＝２であり、列３は、列２から 下向きに２つの位置だけ、あるいは量０１０だけシフトされる。その場合に平文 データ値０１０に隣接する３ビット２進数は、第５図のように１００である。こ の平文データ０１０に加算されるｍｏｄ２は、第５図の値に対応する暗号値１１ ０を提供する。しかし、平文データ値が０００である場合、メモリＩへのアドレ スとしてのこの値は、この値の位置、すなわち、系列中の０００を提供する。こ れはシフトされず、未変更てメモリ３０中の順序データとして提供される。した がって、それ自体に加算された０００は、固定されたままである。 第５図の列２の基本順序データに対する第５図の列３の系列の下向きシフトＰ_s はもちろん、相補上向きシフトに対応する。したがって、ｎビット・ブロック では、Ｐ_sの下向きシフトは、ｍ−Ｐ_sの上向きシフトと等価である。３ビット・ ブロックでは、可能なシフトのすべての値が、所望の１対１写像を提供すること にも留意されたい。ただし、ゼロの第２列に対する第１列のシフトと、７および その倍数のシフトはこの限りではない、なぜなら、そのようなシフトは、第１列 の対応する行と同じ各行を有する第２列を行列中に提供し、それ自体にｍｏｄ２ 加算された数はゼロになるからである。したがって、７またはその倍数のシフト では、すべての平文データ値が０００にマップされ、暗号化には無用である。し かし、一般に、３ビットより大きなｎビット・ブロックでは、ゼロおよびｍの整 数倍数以外のすべてのシフトが所望の結果を与え、したがって、これらのシフト が原発明によって使用できることを後で示す。 第７図による復号に関するブロック図を第９図に示す。ハードウェアの観点か らは、この図は、暗号化に関する第８図の図とまったく同じであり、復号化の暗 号化と異なる点は、暗号化用の所与のシフトＰ_sの代わりにシフトＳが適用され ることだけである。１４ページの例の場合と同様に、第８図および第９図のテー ブルに示したように、暗号化用のシフトＰ_sが２である場合、シフト６によって 妥当な復号が行われる。復号時に平文データをうまく回復するには、暗号化ハー ドウェアおよび復号化ハードウェアが関連するシフトを使用しなければならない ことは自明である。ただし、符号分析が、ほぼ不可能にするのは無理にしても、 非常に困難なものにするために双方で適用可能なシフトを頻繁に変更することが できる。 第５図の任意の一対の列に固定数をｍｏｄ２加算した場合、次の１対１変換が 行われる。一例を挙げると、第１０図で、第５図の第１列および第２列に固定数 ００１をｍｏｄ２加算した。この場合、平文語としての０１０は暗号化語１１１ にマップされ、これに対して、第８図の例では、０１０は１１０にマップされる 。 固定語加算器を使用する暗号化に関するブロックの一例は第１３図に見ること ができる。この図は、第８図と同じものであるが、第１列の０１０と同じ、第２ 列の行中の値に対応するメモリ３０の出力に固定語（この例では００１）を加算 するために、固定語加算器３２が含まれている。したがって、固定語加算器は、 列２の値に固定語（この例では００１）を加算するに過ぎず、その後、その結果 に平文語がｍｏｄ２加算されて、暗号化データが得られる。この場合も、たとえ ば、平文データ０１０をメモリ２２へのアドレスとして使用すると、メモリの出 力は００１になる。第８図の例と同じシフトを使用すると、００１に０１０、す なわちＰ_s＝２が加算され、メモリ３０へのアドレス０１１が提供される。この 結果、メモリ３０の出力が１００となり、固定語加算器がこの値に固定語００１ をｍｏｄ２加算して、１０１が与えられる。このように平文語０１０へのｍｏｄ ２加算によって、第１０図に示したように、暗号化語１１１が与えられる。 第１３図の暗号化に関するブロック図に対応する、復号化に関するブロック図 を第１４図に示す。図から分かるように、第１４図は、第１３図と同じものであ るが（ただし、この場合も、復号化用のシフトは暗号化用のシフトとは異なる） 、固定語加算器は、固定語を、メモリ２２に適用する前に暗号化データにｍｏｄ ２加算する。このｍｏｄ２加算は基本的に、固定語の第２のｍｏｄ２加算である 。というのは、暗号化語を得るために、第１１図で固定語の第１のｍｏｄ２加算 が行われたからである。したがって、第１２図中の暗号化データの後で、そのデ ータに固定語がｍｏｄ２加算されるように、同じ語の第２のｍｏｄ２加算が実際 上、第１のｍｏｄ２加算を取り消すので、ｍｏｄ２加算の結果を第１０図の数式 と共に復号のために使用することができる。したがって、一例を挙げると、第１ ３図の例の暗号化語１１１を使用した場合、第１４図のメモリ２２へのアドレス とし この値にＳ＝６の値または１１０が加算される。すなわち、ラップアラウンドに よって１００＋１１０＝１０１０＝＞０１１となる。これによって、メモリ３０ へのアドレス０１１またはメモリ３０の出力１００が与えられ、その値にｍｏｄ ２ １１０、すなわちメモリ２２へのアドレスが加算され、平文データ０１０が 回復される。さらにもちろん、第１３図および第１４図の固定語加算器は固定語 ００１を使用したが、他の任意の３ビットの固定語を使用することができ、その ため、シフトの変更と共に、あるいはシフトの変更とは別に、必要に応じて固定 語を変更することができ、固定語０００は基本的に、システムの動作を第８図お よび第９図の動作に低減する。 第６図、第７図、第１１図、第１２図に関して説明した方法が、プログラム制 御下のマイクロプロセッサ・ベースのシステムで容易に実施できることは自明で ある。また、メモリは、基本的に参照テーブルとして使用される読取り専用メモ リに容易に事前プログラムすることもでき、加算器およびｍｏｄ２加算器は、暗 号化・復号化システムの少なくとも主要な要素が高速離散構成要素中で、あるい はカスタム集積チップを通じて実現できるように従来型の加算器回路であってよ い。シフト・プログラムは、シフトが何度必要であるか、シフト順序自体を変更 する程度などに応じて様々な形をとることができ、必要に応じてシフト・レジス タ実施態様を含めて、マイクロプロセッサ・ベースの集積回路またはその他の実 施態様を容易に適用することができる。 ＩＩ．非線形化の概要 下記の付録１で、前述の本明細書の変換をさらに分析し、その様々な特性につ いて述べる。付録２では、親の親出願のブロック換字方法のある態様を再検討し 、非線形性の概念と、平文から暗号文への非線形写像（およびその逆）を提示す る。この意味での非線形性は、平文から暗号文へ（および暗号文から平文へ）の 写像が、ビットごとのｍｏｄ２加算動作の下では非線形であることを意味する。 なお、第１図が、ｍｏｄ２加算によるある３ビット２進数の集合の別の２進数の 集合への多数対単一変換を示すことを指摘した。この特定の例は、第１列中の３ ビット数の８つの可能な値をそれぞれ、ｍｏｄ２加算によって、２つ（１００お よび０１１）がそれぞれ２回繰り返される、８つの可能な組合せのうちの６つか らなる列３中の６つの３ビット数にマップするものである。２つの３ビット数（ ０１０および１０１）が同じ３ビット数（１００）にマップされ、他の２つの３ ビット数（１００および１１０）が同じ３ビット数（０１０）にマップされるの で、この逆写像はあいまいさを有し、第１図に示した写像は、暗号化および復号 化には適さない。 一方、第２図ないし第５図は、８つの可能な３ビット平文語のうちのどれか（ 列１）を、対応するあいまいでない暗号化語（列３）に暗号化する数式の集合を 提供するものである。これらの数式は、列１と列３を相互交換しても有効なまま であり、したがって、この相互交換によって、相互交換の前の数式が暗号化用の 数式を形成するのと同様に、対応する復号用の数式を形成する。しかし、第２図 ないし第５図のそれぞれに示した数式の集合は、所与の数式の集合内の２つの数 式（第２図ないし第５図の場合のように３ビット数の場合は８つの数式）の加算 が、その数式の集合のうちの１つであるという点で線形である。たとえば、第２ 図で、第１の数式すなわち零数式を任意の他の数式に加算すると、後者の数式が 生成され、したがって、この加算は自明であり、第２の数式と第３の数式を加算 すると、第４の数式が与えられ、第３の数式と第４の数式を加算すると、第２の 数式が与えられ、第４の数式と第５の数式を加算すると、第８の数式が与えられ 、以下同様である。１つの数式をそれ自体にｍｏｄ２加算するときでも、８つ の数式のうちの１つ、すなわち、零数式が得られる。これは、２つよりも多くの 数式、一例を挙げると、数式２、３、４をｍｏｄ２加算したときと同様であり、 その場合、数式２と数式３を加算することによって数式４が生成され、数式４を それ自体に加算することによって零数式が生成される。なお、２つの数式をｍｏ ｄ２加算することは、それよりも多くの数の数式を加算することと等価であると みなすことができる。なぜなら、加算される数式のどちらかまたは両方を２つ以 上の他の数式の和とみなすことができるからである。さらに、所与の数式の集合 のうちのいくつかの数式の和は必ず、その集合のうちの他の数式となる。符号分 析の観点から最も重要なことは、零数式以外の７つの数式のうちの右側の３つが 与えられた場合、残りの４つの数式が、３つの既知の数式の組合せの妥当な和に よって求められることである。たとえば、第２図の数式２、３、４の和の組合せ を使用して残りの数式を生成することはできないが、数式２、３、または４と、 数式５、６、７、または８をそのように使用することができる。数式２、４、８ を一例として説明すると、数式２と数式４を加算すると数式３が与えられ、数式 ２と数式８を加算すると数式７が与えられ、数式２、４、８を加算すると数式６ が与えられ、数式４と数式８を加算すると数式５が与えられる。もちろん、前記 の規則は他のビット長の語の暗号化にも適用され、４ビット語を暗号化するため の１６個の数式用の母数式は、４つの独立数式の様々な組合せをｍｏｄ２加算す ることによって求めることができる。 第１０図中の数式の集合に関しては、２つの数式を加算しても、その組の数式 の第３の数式は与えられない。ただし、第１０図の左側の各列に００１を加算す ると、この場合も第５図の数式の集合の零数式と残りの部分とになる。この数式 の集合は一般に、その数式の集合のうちの３つの独立数式によって与えられる。 この能力によって、基底独立数式の集合から数式の残りの部分が生成される。本 発明は、この能力をなくするものであり、基底線形数式の集合を必要に応じて、 あるいは動的に原出願で開示した様々な方法で、変更できるだけでなく、その結 果得られる基底数式の集合を必要に応じて、あるいは動的に様々な程度に様々な 組合せで非線形化することもできるように、整然と論理的にこれを行い、符号分 析を以前よりもずっと困難なものとする。 再び第２図を参照すると、数式の順序を再構成した場合、もちろん列１中の数 から列３中の数へのマップに変化はない。したがって、第２図中の数式は、第１ ５図に示したように再構成することができる。具体的には、零数式を無視すると 、列２中に現れる第１の数（００１）が、列１の次の行に現れ、列２の第２の数 （１１１）が列１の第３行に現れ、以下同様であり、ラップアラウンドの結果、 列２中の最後の数（１０１）が列１の第１行に現れる（この場合も、零数式を無 視する）。この結果得られる数式の構成は、付録２の７ページに示した形のもの であり、付録２の第１５図で、ｘ₁は００１であり、ｘ_mは１０１である。零数式 と、２ⁿ−１個の非ゼロ数式とを有する任意のビット長の語（数）を表す任意の 数式の集合を、それによって定義される写像を変更せずに、そのように構成する ことができる。というのは、そのような構成は、数式の見かけの順序を変更する ものに過ぎず、数式自体を変更するものではないからである。 付録２の第３．２節に、列１および２に現れる語を再構成して、対応する新し いｍｏｄ２加算式を与えることによって、そのような数式のある種の群を変更で きることが示されている。新しいｍｏｄ２加算式は、それによって最初の数式の 集合内の最初の数式群を置き換えても、１対１写像を維持し、したがって、この 数式は、暗号化および復号化で使用するのに適している。なお、選択された数式 群の列１および２に現れるマルチビット語の順序が変更されるので１対１写像が 維持されるが、語自体は変更されず、その結果、マップされる語群と、選択され た数式によってそれらの語がマップされる語群は変更されない。ただし、その２ つの群内で、列１中のどの語が列３中のどの語にマップされるかは変更される。 変更されたこれらの数式の正味効果は、それらがもはや、数式の線形拡張ではな く、すなわち、もはや２つ以上の未変更数式を加算しても生成することができな いことである。したがって、これによって最初の数式の集合の線形性が無効にな り、符号分析は必要に応じてより困難になる。線形性の無効化の程度については 後で論じる。 付録２の第３．２節に、ある種の条件下で、所与の数式の集合内のいくつかの 数式群を修正し、それらを使用して完全な数式の集合用の１対１写像を維持し、 同時に、前述のようにその１組の数式の線形特性を無効化するように、最初の集 合内の対応する最初の数式群を置き換えることができることが示されている。こ のような条件は、付録２の第３．３節に数式形でより具体的に示されている。こ の節には、２つの可能な修正が数式形で示されている。基本的な概念は、最初の 数式の集合中の行の連続３つ組を合計することであり、付録２の第３．２節の分 析では、第３．３節で述べるように、そのような行の連続３つ組を合計すること による非線形化が作用するのが、最初の数式の集合のうちの３つまたは４つの連 続行の集合を使用する場合だけであることが示されている。３つの連続行を使用 する場合、実際には４つの行、すなわち、最初の数式の集合の３つの連続行と、 そのｍｏｄ２ベクトル和に対応する４番目の行が修正される。この修正は、４つ の行のそれぞれに次式をベクトル的に加算することによって得ることができる。 最初の線形数式の集合の４つの連続行を使用する場合、最初の数式の集合の６ つの行、すなわち、４つの連続行と、そのうちの最初の３行のベクトル和を表す 行、および最初の数式の集合の４つの連続行のうちの最初の３行のベクトル和に 対応する行（たとえば、付録２の１０ページに示したように、行１、２、３の和 に対応する行と、行２、３、４の和に対応する行）が修正される。この場合の修 正は、対応する６つの行に次式をベクトル的に加算することによって得ることが できる。 上記の数式と付録２のＡ２ページに示した最初の数式の形は、非線形化が作用 するのが、最初の線形数式の集合の第１行、第２行、第３行、および他の１行を とり、あるいは、最初の線形数式の集合の第１行、第２行、第３行、第４行、お よび他の２行をとる場合であることを示す。この方法が作用するのは、修正のた めに選択される最初の数式の集合のうちの数式がそれらの範囲内で線形であるた めなので、本発明の方法によって一度非線形化された数式はもはや、非線形化プ ロセスの一部として使用することはできない。このため、このプロセスでは４つ または６つの数式しか非線形化できない傾向があり、これはもちろん、より大き な語サイズの場合の総数式としては不十分な数である（たとえば、４ビット語で は１６個の数式が必要であり、８ビット語では２５６個の数式が必要であり、以 下同様である）。しかし、再び第１５図を参照すると、列２中のどの語または数 を非零行からｘ₁として選択すべきかが任意であることが理解されよう。一例を 挙げると、００１ではなく０１１をｘ₁として選択した場合、第３の非ゼロ行が 第１行になり、第４の非ゼロ行が第２行になり、第５の非ゼロ行が第３行になり 、第６の非ゼロ行が第４行になり、第７の非ゼロ行が第５行になり、第１の非ゼ ロ行が第６行になり、以下同様であり、基本的に下の５つの数式がシフトされ、 上の２つの非ゼロ数式がラップアラウンドされ、その結果、数式自体も、数式の 順序付けも変更されず、その系列の開始点のみが変更される。そのような数式構 成を第３図に示した。この図で、ｘ₁＝１００およびｘ_m＝（＝ｘ₇）＝０１１で ある。したがって、付録２の１０ページに提示した数式は、３つの連続行と、そ の和に対応する行を修正する場合（非線形化）、任意の３つの連続行をそのよう に選択することができ、選択した３行と、その３行の和に対応する行のうちのど れも、より早く選択することによって事前に非線形化しておくことはできないこ とによってのみ制限されるという点で一般的なものである。同様に、４つの連続 行と、前述の２つの和行を選択する場合、任意の４つの連続行をそのように使用 することができる。ただし、この場合も、選択した４行と２つの和行のうちのど れも、このプロセスによって事前に非線形化しておくことはできない。数式を非 線形化向けに一般化するには、ｘ₁を、選択した３つまたは４つの連続行のうち の第１行の第２列中の値とみなし、それに応じて、各列の値の変更するだけでよ い。 非線形プロセスが零数式以外の数式に対して実施されることに留意されたい。 ２ⁿ−１（ｎは、使用される語のビット長）個のそのような数式があるので、必 然的に、非線形化ではｎの値にはかかわらずに奇数の数式が利用できるが、非線 形化プロセスは、偶数（４または６）個の数式を一度に非線形化する（高速シス テムでは、所与の線形数式の集合の重ならない異なる群を同時に非線形化する装 置を提供することができる。なぜなら、どのプロセスを使用するかにかかわらず 、重ならない群に対する非線形化プロセスは完全に相互に独立するものだからで ある）。したがって、所与の線形集合中のすべての数式を非線形化できるわけで はないことは明らかである。したがって、いくつの数式を線形化することができ るかと、非線形化すべき数式を選択するための論理的な方法があるかどうに関す る問題がある。これらの考慮すべき点については、付録２の第３．４ないし３． ６節で論じる。一般に、すべての数式を非線形化できるわけではないが、通常、 ４ビット以上の語サイズでは大多数の数式を非線形化し、重要でない残りの非線 形化数式を残して、おそらく、それにより、場合によっては符号分析の観点から 誤りに導くことができる。さらにもちろん、非線形化すべき行の数および識別と 、どの非線形技法を使用するかを必要に応じて変更し、あるいは動的に変更する ことによって、符号分析の問題がさらに複雑になることに留意されたい。ただし 、そのような時変非線形化も動的可変非線形化もハードウェアの観点からは難し いものではない（ソフトウェア制御下で実施する場合はソフトウェアの観点から も難しくない）。なぜなら、簡単で容易に変更できる母関数から開始線形数式の 集合（この数式自体を、前述のように、必要に応じて、あるいは動的に変更する ことができる）を生成することができ、その数式の集合を論理プロセスを使用す る方法でかつそのような範囲に非線形化することができ、その方法および範囲自 体をそれぞれ、必要に応じて、あるいは動的に変更することができるからである 。 前記の一例として、特定の母関数を使用する４ビット数または語の別の４ビッ ト数または語への線形写像用の１６個の数式を提示するＡ１ページ（付録２の付 録Ａ）のテーブルに注目する。この１６個の数式が、付録２の１０ページの最初 の数式に関して指摘したように構成されることに留意されたい。Ａ１ページで指 摘するように、本明細書で使用する線形性の概念によって、Ａ１ページの１６個 の数式のうちの任意の２つの数式の和が１６個の数式のうちの別の数式となるこ とが容易に検証される。Ａ１ページのこのテーブルは、Ａ８ページで説明するよ うに非線形化され、付録２のＡ９ページにその非線形化形で提示されている。具 体的には、この非線形化は、第１の方法によるものであり、すなわち、最初の数 式の集合（零数式を無視する）の３つの連続行と、最初の３行の和を表す行を使 用する。なお、列１中の最初の３つの非ゼロ数（１００１、０００１、００１０ ）のｍｏｄ２和は１０１０、すなわち、非ゼロ数式の第１１行中の値に等しい。 し ｍｏｄ２加算することによって非線形化される。さらに具体的には、ｘ₁は００ ０ Ａ９ページのテーブルに示したように、最初の数式に００１１をｍｏｄ２加算す 列３中の最初の値である）。行２、３、１１上の数式に対する同じ加算では、こ の４行に対する変換が実行される。同様に、非ゼロ数式の行５、６、７を加算し た場合、非ゼロ数式の行１５の数式が得られる。最後の非ゼロ行をＡ１ページに 示す。前記の４行は、行１、２、３、１１と同様に非線形化することができる。 しかし、この場合、適用される数式は実際上、次式であることに留意されたい。 付録２のＡ９ページの１６個の数式の集合の次の非線形化に関しては、検討で きる他の２組の３つの連続数式、具体的には８、９、１０と、１２、１３、１４ がテーブル中にある。しかし、行８、９、１０をｍｏｄ２加算すると、すでに使 用された行である非ゼロ数式の行３が与えられ、行１２、１３、１４のｍｏｄ２ 和では、すでの使用された別の行である行７が与えられる。したがって、３つの 連続行または３つの連続数式の２つの追加群が存在するが、どちらの３つの和も 、すでに非線形化されている行または数式となるので、これを使用することはで きない。 他の例として、本明細書の付録２のＡ４ページの１番上に記載したテーブルに 注目されたい。この線形数式の集合は、同じではあるが新しいベースに適用され （付録２のＡ３ページの１番下を参照）、前例と同じ数式の集合（数式１、２、 ３、５、６、７、１１、１５）を使用して非線形化されたときに、付録２のＡ１ １ページに記載した非線形数式の集合を与える母関数を使用する。 第３の例として、Ａ１１ページの１番下の近くに記載した例に注目されたい。 この非線形化数式はＡ１２ページに示されている。この例は、付録２のＡ１ペー ジに提示され、異なる基本、具体的には４つの連続（非ゼロ）数式１、２、３、 ４と、１、２、３の和、すなわち数式１１と、数式２、３、４の和、すなわち数 式１２と、３つの連続数式１３、１４、１５と、それらの和、すなわち数式８を 使用して非線形化された１５個の数式（零数式を含む）のテーブルの別の非線形 化の例である。４つの連続数式と、２つのｍｏｄ２和数式を非線形化するための 数式はもちろん、前記で与えられており、付録２の１０ページに記載されている 。具体的には、行１およびｑに１つ、行２および３に１つ、行４およびｑ＋１に １つの３つの異なる数式が使用される。行１を例にとると、列３にゼロが加算さ れ、 ２ページの非線形化数式の集合中の第１の非ゼロ数式が生成される。線形非ゼロ の行２の列１および２に加算すると、Ａ１２ページの数式の集合中の５番目の非 ゼロ数式が生成される。最後に、行４およびｑ＋１に第３の数式を使用すること たとえば、線形非ゼロ数式の行４の列１および２に加算すると、Ａ１２ページの 非線形化数式の集合中の非ゼロ数式の行２が生成される。もちろん、非線形化プ ロセスによってすべての６つの適用可能な行を修正しなければならない。したが って、この後者の例では、前の例での８つとは異なり１０個の数式が非線形化さ れ、もちろん、この結果得られる列１から列３への写像は、この２つの数式の集 合に関して全体的にかなり異なるものとなる。 最後に、非線形化数式は、最初の２列のそれぞれにオフセットをｍｏｄ２加算 することによって、さらに修正することができる。これはもちろん、このオフセ ットをそれ自体に加算することと等価であり、これはもちろん、０になり、した がって第３列中の数には影響を与えない。具体的な例として、第１７図は、前記 で説明し付録２のＡ１２ページに図示した、第１および第２列にオフセット０１ ０１を加算することによって修正された第３の例の数式の集合を提示するもので ある。 第１６図は、本出願の本発明による典型的暗号化・復号化装置のブロック図を 示す。第１６図で分かるように、最終的に、平文データ・ブロックまたは暗号文 データ・ブロック（どちらも長さｎビット）がメモリへのアドレスと並列して提 示され、データがそれぞれのデータ・ブロックの暗号化および復号化に対応する アドレスに記憶される読取り／書込みメモリの形の参照テーブルを使用すると好 都合である。そのために、メモリ・アドレス範囲が、操作すべきデータ・ブロッ クよりも１ビットだけ広くなるように、暗号化または復号化に必要なアドレス零 間（たとえば、ｎ＋１アドレス・ビット）の２倍のアドレス零間のメモリを使用 すると好都合である。このように、１ビットのメモリ・アドレスを使用して、動 作を暗号化動作とするか、それとも復号化動作とするかを指定することができる 。具体的な例を挙げると、メモリ・アドレスの最上位ビットは、復号プロセスを 示す０、または暗号化プロセスを示す１でよく、メモリのアドレス範囲の下半分 に復号データを記憶し、メモリの上部アドレス範囲に暗号化データを記憶するこ とができる。したがって、暗号化と復号化は共に、単一ビットを制御することに よって参照テーブルに応じて実行することができ、ｎビットのブロックの暗号化 も復号化も単一メモリ・サイクルで行うことができる。 暗号化および復号化用の写像を周期的または動的に、あるいはその周期的でか つ動的に変更すると仮定すると、参照テーブルの内容を修正するある方法を提示 することができる。これは、専用ハードウェアによって実行することができるが 、プログラム制御下で適当なプロセッサによってこれを行うと好都合である。と いうのは、暗号化方式および復号化方式の修正は通常、暗号化および復号化自体 を実施することよりもずっとまれにしか行われないからである。したがって、こ のような修正を暗号化および復号化自体と同じ速度で行う必要はない。したがっ て、第１６図に示した非線形動的換字ジェネレータは、それへの様々な入力に基 づく プログラム制御下で動作することができる。具体的には、暗号化用の数式は、そ れを定義する何らかの基本情報、一例を挙げると、ブロック換字ビット・サイズ （ｎ）、ｎ個の線形独立数の基底集合、母関数、非線形化を開始する線形集合の 開始数式、実行すべき非線形化関数の反復数が与えられた場合、暗号化用の数式 をプログラム制御下で生成することができる。 非線形化数式にオフセットを適用した後、列３中の各数またはブロックは、符 号化に割り当てられた参照テーブルの、それぞれの行の列１中のブロックに等し いアドレスの部分に記憶される。したがって、列１中の数またはブロックをアド レスとして適用したとき、メモリから読み取られる数は、それぞれの暗号化ブロ ックを表すその行の列３中の数である。テーブルの復号部分に関しては、このプ ロセスが反転され、その場合、列３中のブロックがメモリ・アドレス（より適切 には、アドレス部分、完全なアドレスはアドレス・ビット指定復号を含む）とし て使用され、そのようなアドレスに記憶されるデータは列１中のそれぞれのブロ ックである。したがって、復号時に、メモリは、暗号化ブロックによって定義さ れたアドレスから開始し、それぞれのアドレスに記憶されているデータは、関連 する平文ブロックに対応する出力として提供される。都合上、詳細な暗号化方法 および復号化方法を付録３に記載する。 暗号化プロセスおよび復号化プロセスを完全にプログラム制御下で実施できる ことは自明である。なぜなら、２つのプロセスは共に、ある種の（可変）開始情 報が与えられた場合、論理処理しか必要としないからである。しかし、プロセッ サが同じ暗号化数式および復号化数式を何度も再生成するので、暗号化および復 号化を実施する速度は、大幅に減少される。これに対して、参照テーブルを使用 すると、完全な暗号化数式および復号化数式の集合を一度に求めることができ、 暗号化または復号化すべきデータ・ブロックに関するその情報は、数式が変更さ れるまで連続的に単一のメモリ・サイクルで得ることができる。 ＩＩＩ．線形直交写像（linear orthomorphisms）の修正 本節では、前記の第ＩおよびＩＩ節で説明した線形直交写像に対するある種の 修正を提示する。 一般性を失わず、かつθ、すなわち加算識別を固定点として使用する場合、次 式のように最大長直交写像を数式の集合として書くことができる。 上式で、ｍ＝２ⁿ−１、Ｒ（ｘ_k-l）＝ｘ_kおよびＳ（ｘ_k-l）＝ｚ_kは３つの可 能な写像のうちの２つである。従来どおり、本出願人の暗号写像またはブロック 換字としてＳ（ｘ）を使用した。 線形直交写像の場合、θは、固定点でなければならず、極大である場合、代表 数式は、次式のように非常に簡単な形をとる。 線形バージョンを適切に修正することによって非線形直交写像を構築すること 算すると、次式が得られる。 アフィンである。さらに全体的に非線形であるには、数式の線形アレイを部分集 合に分割し、異なる方法で修正する必要がある。線形直交写像中のａ番目の行の 個別の数式 は次式になるように修正しなければならない。 上式で、最初の線形直交写像において、ｘ_c-lは左側の列の行ｃに現れ、ｘ_bは 、中央の列の行ｂに現れる。この場合、次式が成立する。 上式は、数式１２と同様に行ａ中の数式を変換するように適用される。 線形直交写像中の２ⁿ個の数式の集合全体がコラプチブル（corruptible）であ り、数式（１０）から、最小コラプチブル集合の候補は、３つの行または数式か ら成る。しかし、３つの数式のコラプチブル集合（corruptible set）を含む線 形直交写像は、極大ではないので、暗号には無用である。 それが表す置換に３サイクルを有することを示すことができる。 下記の分析は、前記の命題１を証明するものである。線形直交写像中の３つの 数式のコラプチブル集合 は、指数の行列で示すことができる。 非線形化（コラプション）後、行の順序が自明なので、次式のように可能な指 数行列は２つしかない。 左側の行列をとると、対応するコラプトされた数式は次式のとおりである。 指数ａおよびｂを含む任意の２つの数式を選択することができるが、数式ｃに は矛盾する３つの条件がある。下記では、そのような数式が線形アレイ中に存在 すると仮定する。数式の線形アレイは群なので、指数ｄ群には、最初の３つの指 数の和である下記の第４の数式が存在する。 線形アレイ中のこの４つの数式は、線形アレイ中の位数４の部分群から導出さ れるコセットを形成する。この部分群は、コセット中の４つの数式の１つを他の ３つ、たとえば、数式ａに加算して次式を得ることによって、得ることができる 。 数式１９を使用すると、この部分群は、次式のようになる。 最後の３つの数式は、線形アレイの正規化形（数式１９）に連続的に現れ、３ サイクルを形成する。他の指数行列を使用した場合、左側の列と中央の列を相互 交換し、なおかつ等性を維持することができ、同じ結果が得られる。 前記の命題は、ブロック・サイズｎの極大線形アレイで、任意のｎ個の連続行 が線形に独立しているという認識にも従うものである。位数４の部分群が線形に 独立な行を有することはできないので、アレイを極大にすることはできない。 次に、４つの行ａ、ｂ、ｃ、ｄのコセットを検討し、最初の３つの行を前述の ように修正すると、結果は次式のとおりである。 数式２４を線形バージョン（数式１１）と比較して、下記の混合変換を導出す ることができる。 ３つの連続行とその和がコラプチブル集合を構成した（付録ＩＩ、第３．２節 参照）。これは、任意の２つの非ゼロ行をとることに一般化される（付録ＩＶ、 第ＩＩ節参照）。 次式によって指定される第３の行ｃを求め、 次式によって指定される第４の行ｄを求める。 したがって、数式の線形直交写像アレイ中の任意に選択された２つの非ゼロ行 は、４つの数式の２つのコラプチブル集合を指定する。これらの集合のうちの第 ２の集合は、次式によって第３の行ｃを選択することによって指定される。 数式のこの集合を非線形直交写像の４数式セグメントに変換する。最初の４つの 数式が、位数４の部分群での相対補数であり、あるいは、そのような部分群から 導出されたコセットと等価であることは明らかである。前記の命題１の場合と同 様に、この部分群は、次式のように、４つの数式のうちの１つを４つの数式のそ れぞれ、たとえば行ａに加算することによって導出することができる。 線形アレイで連続している。同様の結果が第２のケースでも成立する。したがっ て、４つのコラプチブル数式を求めるプロセスは、２つの連続行を含む位数４の の形を有する。 形成することができる。 れる混合変換群は、Ｗ_k＝Ｌ_k∩Ｍ_kである。ある種の状況では、Ｗ_k＝｛θ｝であ り、建設的コラプションは不可能である。前記のことは、下記の第ＩＶ節でさら に詳しく説明する。 部分群のコセットでも相対補数でもないコラプチブル・セットがある。たとえ ば、コラプチブル・セットは、次式のように、４つの連続数式と、最初の３つの 数式および最後の３つの数式をとることによって生成される。 を使用してさらに２つの行を加算することができる。 この結果得られる８つの数式は、３つの連続行の１つの集合と２つの連続行の １つの集合を含む位数８の部分群から導出されるものとして容易に示すことがで きるコセットを構成する。 建設的コラプションは、非線形直交写像を形成するようにアセンブルできる非 線形セグメントを与えるが、このように得ることができない非線形セグメントが あるかどうかに関して問題が発生する。 命題２：一般に、建設的コラプションによって任意の極大長非線形直交写像を 線形（自己同型）直交写像から導出することができる。 前記の命題は、下記の分析によって証明される。一般性を失わずに、θを固定 点と仮定することができる。極大長非線形直交写像の正規化形はを数式１１ａに 示す。右側の列中のｎビット数は、次式のように、置換の新しい位数が線形直交 写像になるように置換される。 これは、ｚ_iの補線形独立集合に線形母関数、すなわち原子多項式を適用する ことによって多数の方法で実行することができる。したがって、ｕ_i＝ｚ_jである 。ここで、ｉ＝ｆ（ｊ）は前述の置換を表す。この同じ置換を、非線形直交写像 Ｓ（ｘ_k-1）＝ｚ_kを変更せずに数式１１ａ中の数式アレイに適用することができ る。しかし、｛ｕ_i｝置換はこの場合、線形直交写像を定義する。この正味結果 は、次式の形のｍ＝２ⁿ−１数式の二重集合である。 対応する混合変換は次式のとおりである。 前記の分析の主要な結果は、特殊な部分群を使用するコセット分割が、成分ご との非線形化の候補を見つけるための有効で系統だった手段であり、そのような 技法を使用した場合、非線形直交写像のどのクラスも見逃されないことである。 次節では、どんなサイズの成分をコラプトすべきかを判定する分析と、成分をど のようにして、暗号用の望ましい特性を有する非線形直交写像としてアセンブル すべきかを提示する。 ＩＶ．完全な非線形直交写像の構築 第ＩＩＩ節では、それ自体の中で非線形化することができる線形直交写像の成 分（数式のコラプチブル集合）を求めるにはどうすべきかを説明した。本節では 、成分を２ⁿ−１個の数式の完全な非線形直交写像としてアセンブルするにはど うすべきかを説明する。本節ではさらに良好な線形直交写像および良好な非線形 代入を構成するものについて説明する。一方の極端な例では、位数４のコセット を修正して、残りの２ⁿ−４個の数式を修正しないでおくことができる。他方の 極端な例では、すべての２ⁿ個の数式を単一の混合変換で修正することができる 。成分ごとの線形化もアフィン写像も十分ではない。任意の写像Ｓの場合、次式 を評価することができる。 Ｓがアフィン写像である場合、数式３９の和は、Ｓが線形である場合はすべて の対ｘ、ｙ、ｃ＝θに対してある種の固定数ｃとなる。したがって、非線形性の 自然な尺度は、Ｎ（ｘ，ｙ）の範囲および分布である。 命題３：極大長線形直交写像中の位数２^kの部分群の場合、対応する混合変換 群の位数Ｗ_kが２^2k-n≦｜Ｗ_k｜≦２^k-1となることを証明することができる。 位数は２^kである。Ｗ_k＝Ｌ_k∩Ｍ_kである。｜Ｗ_k｜＝２^kである場合、Ｌ_k＝Ｍ_kで ｜Ｗ_k｜≦２^k-1である。Ｌ_kおよびＭ_kはそれぞれ、ｋ個の線形独立数の集合を有 し、それらの集合はそれぞれ、｛ｘ₁，ｘ₂，．．．，ｘ_k｝εＬ_kおよび｛ｘ_k+1 ， ｘ_k+2，．．．，ｘ_2k｝εＭ_kで示される（これらの指数は、この場合、数式１ の線形独立数がある。したがって、２ｋ＞ｎである場合、｛ｘ₁，．．．，ｘ_k， ｘ_k+1，．．．，ｘ_2k｝には、相互に依存する２ｋ−ｎ個の数の部分集合がある 。一般性を失わずに、｛ｘ_k+1，ｘ_k+2，．．．，ｘ_n｝が｛ｘ₁，．．．，ｘ_k｝ から独立していると仮定することができる。残りの数｛ｘ_n+1，．．．，ｘ_2k｝ は｛ｘ₁，．．．，ｘ_k｝εＬ_kに依存しなければならない。相互に独立な２ｋ− ｎ個のそのような数があり、したがって、｛ｘ_n+1，．．．，ｘ_2k｝εＬ_k∩Ｍ_k である。 うことである。 位数２^kのコセットは、対応する混合変換群が位数２^k-1である場合「完全にコ ラプチブル」であると言われる。 る。前記の仮定および定義を用いた場合、コセット分割は次式の形をとる。 実際的な目的のために、コラプチブル集合への分割が望ましい。これらのコセッ トのそれぞれは、利用可能な同じ混合変換群を有する。 線形直交写像を表す数式の極大部分群は、連続ステップによって非線形直交写 像に変換することができる互いに素な部分集合に分割することができる（付録Ｉ Ｖ参照）。これは、完全にコラプチブルなコセットに一般化することができる。 建設的なコラプションの実際的な問題は、非線形化すべき線形直交写像アレイ 中の数式の集合のサイズをどのように選択すべきかと、矛盾なしで混合変換を割 あり、完全にコラプチブルである場合、混合変換集合の位数は｜Ｗ_k｜＝２^k-1で の数式にベクトル的に加算することによって得られる。このコセットは、Ｗ_k中 のいくつかまたはすべての混合変換を適用することによってコラプトすることが できる。ｗεＷ_kを１つしか使用しない場合、その結果、アフィン集合が得られ る。すべてのｗを使用しようとした場合、ｗを矛盾なしで割り当てるにはどうす つの小さなコセットを別々にコラプトすることができる。問題は、混合変換集合 の位数｜Ｗ_k-1｜が２^k-2であることであり、そのため、混合変換が適用される数 式の数の半分の混合変換しか得られないことである。ｋ＝２であり、コセットの 位数が４であるという限界のために、Ｗ₂＝｛θ，ｗ｝であり、したがって、す べての２^n-2−１個のコセットに適用できる混合変換は１つしかない。下記では 、 合を求め、その結果、この部分集合の左側の列と中央の列中の数をそれら自体の 列の全範囲にわたるようにする方法を提示する。 この方法は、「カット・アンド・トライ」法（付録ＩＩ、第５節参照）ではな く整然としたプロセスへの複数の混合変換の割当てを簡略化するものである。付 録ＩＶの１７−１７ページに、極大部分群に関する方法の概要が示されている。 スを一般化する。この方法は、極大部分群と同様に働く部分群を求めようとする ものである。 命題４：位数２^kの完全にコラプチブルな部分群が、極大線形直交写像を表す 完全な数式アレイの数式のｋ個の連続行を有することを証明することができる。 前記の命題は、下記の分析によって証明される。位数２^kの完全にコラプチブ 個の線形独立数式の極大集合を有する。Ｗ_kは、ｋ−１個の数の極大線形独立集 合を有する。完全な線形アレイ中の列ＬまたはＭから連続数の最大集合を含む集 合を求めることが望ましい。ｋ−１個のそのような数ｘ_a，ｘ_a+1，．．．ｘ_a+k- する。 ｋ−１個の線形独立数の集合中の連続数がｋ−１個よりも少ない場合、これら の数は、連続数のより小さな集合とすることができる。最大のそのような集合は 、ｘ_a，ｘ_a+1，．．．ｘ_a+ka-2であり、２番目に大きなそのような集合はｘ_b， ｘ_b+1，．．．，ｘ_b+kb-2であり、以下同様であり、最終的に、Ｗ_k中のｋ−１個 の独立数の集合が（ｋ_a−１）＋（ｋ_b−１）＋．．．＝ｋ−１によってアセンブ 集合を定義する。 ｘが線形に独立しているので、数式４２中のｋ_a＋ｋ_b＋．．．＞ｋ個の個別の 完全にコラプチブルな部分群は、非線形直交写像を導出するうえで有用である だけでなく、下記で示すように、より小さな部分群の構造にも影響を及ぼす。 命題５：位数２^kの完全にコラプチブルな部分群では（ｋ≧４）、位数２^k-1の 各部分群がコラプチブルであることを証明することができる。 前記の命題は、下記によって証明される。そのような完全にコラプチブルな部 である。連続行の連続的に小さくなるｋ組の系列がある。この系列の指数を表Ｉ に提示する。 ｋ≧４なので、少なくとも４つの連続ａ行、３つのｂ行、２つのｃ行がある。 ｋ−１行の連続する３つの集合 される。同様に、（ｂ，ａ＋２，ａ＋３，．．．，ａ＋ｋ−１）は、ｋ−２個の からすべての対をなくする必要がある。１つを除くすべてのａ、たとえば、ａな 以下同様である。この場合も、ｃ指数を含む連続行をなくするために、いくつか のそのような行が補数中に存在することになり、したがってその結果、３重和が 得られる。 ｎ≧５の場合、これは、位数２^n-2の部分群がコラプチブルであり、もちろん 、命題４によって、位数２^n-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-1中の数の対を再構成すると、 Ｌ_k-1×Ｍ_k-1×Ｒ_k中にコラプトされた数式がもたらされる。 すことができる。すなわち、次式が成立する。 したがって、ｕεｘ_a-1Ｌ_k-1およびｖεｘ_aＭ_k-1である場合（あるｘεＬ_k-1 したがって、数の任意の対ｕ，ｖ（ｕεｘ_a-1Ｌ_k-1およびｖεｘ_aＭ_k-1）の場 ｘ_k-2によって定義されるブロック・サイズ８極大長線形直交写像を検討する。 ８ビット２進数の完全な線形独立集合を｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ．Ｆ，Ｇ，Ｈ｝と する。この場合、各文字は、８ビット２進数を表し、具体的にはＡ＝Ｘ，Ｂ＝Ｘ₂ ，．．．．．，Ｈ＝Ｘ₈である。都合上、そして話を簡単にするため、表記法Ａ ると、直交写像を表す２⁸＝２５６個の数式または行が定義される。たとえば、 に示す。 暗号化に使用される直交写像はたとえば、行５のＳ（Ｄ）＝ＤＥである。話を ると次式が成立する。 してコセットを構築することができる。 割することができる。 および このコセット分割を使用する場合、別のコセット上で使用できる唯一の自明で ない混合変換はＢである。 やはり完全にコラプチブルな異なる部分群が得られる。 数式５３中の部分群とは異なり、この場合、次式のように、Ｌ₂⊂Ｒ₃およびＭ および を矛盾なしで使用することができる。表ＩＩを参照されたい。 縦座標は、数式５３の左側の列中の２進ブロックの行番号をリストし、横座標 は、数式５３の中央の列中の２進ブロックの行番号をリストしたものである。表 うちの一方の行を含むことに留意されたい。各列および各行を使用できるのは１ 度だけであり、表項目（行番号）を繰り返すことはできない。これが三次元表で ある場合は、各行、各列、各軸が１度しか使用できないことを意味する。 表ＩＩを使用して、建設的コラプションのパターンを選択することができる。 い。この場合、２つの混合変換を使用した。 他の手法は、識別変換を含め、すなわち、いくつかの行、たとえば、６／Θか にしておくことである。この場合、すべての混合変換が使用されているが、２つ の行６および１５５は未修正のままである。他の何らかのコセットの一部または その和、すなわち、行３を修正することができるので、この２行は後で変換する ことができる。 前記の方法は、非線形化プロセスを整然と実行できるように、任意のサイズの 部分群およびコセットに適用し、次いで、連続的に小さくなる部分群に適用する ことができる。線形アレイ中のすべての行を修正しなくても、通常、 となるようにし、かつ値を均一に分散することができる。 前記は、完全な非線形直交写像を構築するための一般的な技法および方法を提 示するものである。前記のｎ＝８の例は、具体的な数式を含む一般的な技法を例 示するために与えられている。下記の節では、暗号でブロック換字を実施するの に適した特定の非線形化技法について説明する。 Ｖ．部分群の入れ子系列 第１８図および第１９図を参照すると、第１の好ましい非線形化方法が提示さ れている。この方法は、部分群の入れ子系列を使用するものである。この方法の 特定のステップを説明する前に、付録ＩＶに提示した背景材料を特に参照して部 分群の入れ子系列について説明する。 付録ＩＶの第３節は、２ⁿ個の数式の線形アレイ中の数式の極大部分群から開 始することによる非線形化の概要を示すものである。Ｇ^n-1は、２^n-1個のそのよ うな部分群のうちの１つであり、｜Ｇ^n-1｜＝２^n-1である。すべてのそのような 選択することによって指定することができる。すべての極大部分群は、すべて から求めることができる。直交写像アレイＧⁿのこれらの極大部分群はすべて、 基本的に、同じ行間隔を有し、かつすべて同じ増分だけメンバー行の指数を変更 することによって他方の部分群から得ることができる点で、相互の像である（付 録ＩＶ、命題１参照）。したがって、数式のｎビット数の極大部分群も線形直交 写像アレイの極大部分群も、容易に求めることができ、かつ容易に処理すること ができる。 Ｇ^n-1＝Ｌ_n-1×Ｍ_n-1×Ｒ_n-1は、Ｌ_n-1、Ｍ_n-1、Ｒ_n-1がそれぞれ、左側、中 は補数である。混合変換の集合Ｗ_n-1＝Ｌ_n-1∩Ｍ_n-1は群であり、｜Ｗ_n-1｜＝２^n-2 である。Ｇ^n-1から、次式のような完全にコラプチブルな部分群の入れ子系列 と、 次式のような相対補数の同様な系列を構築することができる。 含む。 これらの部分群も、次式のような入れ子系列を形成する。 ｘ_i｝であり、これに対応してＷ₂＝｛θ，ｘ_i｝である。各１≦ｋ≦ｎ−２ごと に、次式が成立する。 線形化手順を下記に示す（かつ第１８図に図示する）。 ｋ＞１の場合はＷ_n-kにはなく、したがって、その後に続くコセットＧ^n-kでは使 用されない。 スを順次継続する。 あるいは、単にそのままにしておき、すなわち、ｗ＝θを適用することもできる 。 前記の方法は、簡単であるだけでなく、２^n-2−１個の自明でない混合変換を 使用するという利点も有する。また、少なくとも２ⁿ−４個の数式が変換される 。しかし、その結果得られる構造はある順序を保持する。Ｇ^n-1は、ｎ−１個の 連続行の単一の集合を有し、群構造のために、ｎ−２個の連続行の別の集合を有 する。したがって、命題４から、すなわち、ｎ−２個の行の集合を生成元として 使用し、あるいは、Ｇ^n-1中のｎ−１個の連続行の集合の最初の行または最後の 行を省略して、Ｇ^n-2を完全にコラプチブルな部分群として構築する３つの方法 がある。まず、２ⁿ−１個の極大部分群を選択し、それに続く各レベルで３つの 部分群を選択する必要がある。したがって、そのような入れ子系列の可能な総数 は（２ⁿ−１）（３^n-2）である。 その場合、 であり、建設的コラプションにもかかわらず、いくつかの線形部分群が残る。 前記の検討すべき点を考慮に入れ、特に第１９図を参照して、部分群の入れ子 系列を使用するための好ましい暗号化方法について説明する。この方法は、ｎビ ット２進数の２ⁿ個のｎビット平文ブロックのうちのどれかを、関連する固有の ｎビット２進数暗号化ブロックで置き換えることによって、データ・ブロックを 暗号化するように動作する。この方法は、第１６図に概略的に示したように、非 線形動的換字ジェネレータを使用して実施することができる。 第１９図を参照すると分かるように、第１の方法は、（１１ａ）の場合と同様 に、２ⁿ個の数式の第１の行列Ｇⁿ、すなわち、各数式が、左側の列上の２ⁿ個の ブロックのうちの１つと中央の列中の２ⁿビット数のうちの固有の１つをｍｏｄ ２加算して、右側の列の関連する固有のｎビット・ブロックを与えることを表す 、線形直交写像を求めるために使用される。２ⁿ個の数式の第１の行列中のすべ ての数式は、任意の数の数式のｍｏｄ２ベクトル和が、第１の行列中の１つの数 式 １０２で、ＦＩＲＳＴ行中のｎ−１個の連続数式を選択し、これらの連続数式と 識別数式のすべての和を求めて次式を得ることによって、ＦＩＲＳＴ行列の２^{n- 1} 個の数式の部分集合Ｇ^n-1が選択される。 上式で、ｓ＝２^n-1−１であり、Ｌ_n-1、Ｍ_n-1、Ｒ_n-1はそれぞれ、左側、中央 、 ＝２_n-2である。 数式の第１の行列を求める原則を付録ＩＩＩの第２節に提示する。ステップ１ ０２ないし１１０で、２ⁿ個の数式の第１の行列中の２ⁿ個の非零数式のうちの複 数の数式が、２ⁿ個の数式の第２の行列を形成するように修正される。数式は、 修正済みの数式が全体として、第１の行列の左側の列と同じではあるが順序の異 なる平文ブロックを、第１の行列の右側の列と同じ固有のｎビット・ブロックに 、未修正の数式の最初の順序で写像するように修正される。複数の数式は、修正 済み数式が、第２の行列中の他のどんな数の数式のｍｏｄ２和にもならないよう に修正される。２ⁿ−１個の非零数式の修正がステップ１０４ないし１０６で行 われる。 復的に適用される。ステップ１０８の反復回数は、ｎの値に依存する。ｎ＝８を 数式の第２の行列の左側の列中の２ⁿ個のｎビット数のうちの１つとしてユニー クに位置する暗号化すべき各平文ブロックが、関連する数式の中央の列中のブロ ックにｍｏｄ２加算され、関連する数式の右側の列中の暗号化ブロックが得られ る。 ステップ１１２は、最終的な暗号化ブロックを得るように働く。前記の第Ｉお よびＩＩ節で説明した前の暗号化方法の場合と同様に、第１９図に示した方法の ステップは、最大変換速度が得られるハードウェア回路を使用して実施すること が好ましい。しかし、プログラムされたマイクロプロセッサを使用して、第１９ 図に示した様々な方法ステップを実行することができる。 ＶＩ．異なる部分群のフィット済みコセット（fitted coset） 次に、第２０図および第２１図を参照して、本発明の第２の好ましい暗号化方 法について説明する。 第２０図の方法は、異なる部分群から、したがって、それぞれ異なるが、ジグ ゾー・パズルのようにはめ合わせることができる混合変換群によって、コセット を求めるものである。 第２０図および第２１図の方法は、異なる部分群からのフィット済みコセット を使用して、暗号化を実施する。最初に、この方法を概略的に説明し、次いで、 第２１図に関して詳細に説明する。 なるコセット分割と２つの異なる混合変換群とを含む位数２^2kの１つの部分群と 型であり、したがって、相互に同型である、２つのコセット分割である。それぞ ズｎに応じて、２つよりも多くのコセット分割に拡張することができる。２では なく、位数２^kの互いに素なある数ｃのコラプチブル部分群を選択した場合、Ｋ 下記は、ｎ＝８の場合の一例であり、極大長線形直交写像は、識別の他に２５ ５の数式または行を含む。 この例を第２０図と下記の表ＩＩＩに示す。第２０図は、ブロック・サイズｎ ＝８のブロック番号の２進数の極大長線形直交写像に関する多重コセット分割を 図示したものである。表３は、ブロック・サイズが８の場合の極大長線形直交写 像に関する１６行の４行コセットへの分割を示すものである。 選択する。各部分群は、２つの連続行と、それらの和と、識別行とを有する。各 部分群は、それ自体と、それぞれ、４つの数式から成る、６３個のコセットとか ら成る完全な線形アレイの固有のコセット分割を確立する。位数４の部分群は、 ４行Ｑコセットのそれぞれを、３つの方法で、それぞれ１６行の４つのコセット （表ＩＩＩ参照）。最後に、混合変換を適用して、建設的コラプション・プロセ スを完了することができる。 必要に応じて、線形アレイ中のすべての数式をこのように修正することができ る。この方法は、第Ｖ節の順序手法よりもある程度複雑ではあるが、数式９によ って測定した非線形性に関してより優れた結果を与えた。 次に、異なる部分群からなるフィット済みコセットを用いたデータ暗号化の好 ましい方法を第２１図を参照して具体的に説明する。上記の第Ｖ節で説明した方 法と同様に、この方法は、２ⁿ個の固有のｎビット２進数平文ブロックのうちの １つを、関連する固有のｎビット２進数暗号化ブロックで置き換えることによっ て暗号化を達成する。最初、ステップ２０２で、２ⁿ個の数式の第１の行列Ｇⁿが 求められる。この方法ステップは、第１９図のステップ１０２と同じものであり 、本明細書ではこれ以上詳しくは説明しない。 場合、各部分群およびコセットは、連続的に小さくなるコセットに分割される。 ステップ２１２で、選択されたコセットが、そのそれぞれの混合変換によって修 正される。この結果得られる２ⁿ個の数式の第２の行列は、非線形直交写像であ る。 最後に、ステップ２１４で、２ⁿ個の数式の第２の行列の左側の列中の２ⁿ個の ｎビット数のうちの１つとしてユニークに位置する暗号化すべき各平文ブロック が、関連する数式の中央の列中のブロックにｍｏｄ２加算され、関連する数式の 右側の列中の暗号化ブロックが得られる。最後のステップ２１４は、前述の方法 の暗号化ステップによるものであり、これについては詳しくは述べない。 第２２図は、ｎ＝８の暗号化に関する第２１図の方法を示す。最初、ステップ ３０２で、２５６個の数式の第１の行列Ｇ⁸が求められる。２５６個の数式の第 １の行列中のすべての数式は、任意の数の数式のｍｏｄ２ベクトル和も、第１の 行列中の１つの数式であることを特徴とする。２５６個の数式の集合のうちの１ たように順序付けることができる。しかし、これらの数式が一般的なｎビット・ システムを表すのに対して、第２２図の方法のステップ３０２によって生成され る数式は、８ビット・システムに対応する。したがって、Ｌ₈、Ｍ₈、Ｒ₈はそれ ぞれ、左側、中央、右側の列である。Ｇ⁸＝Ｌ₈ＸＭ₈ＸＲ₈である。 ステップ３０４ないし３１４は、２５６個の数式の第１の行列中の複数の非零 数式を、２５６個の数式の第２の行列形成するように修正する。これらの数式は 、修正済みの数式が全体として、対応する未修正数式の場合のように線形的では なく、暗号化ブロックに対して非線形的に平文ブロックを写像するように修正さ れる。複数の数式は、修正済みの数式が、数式の第２の行列中の他のどんな数の 数式のｍｏｄ２加算にもならないように修正される。 ステップ３０４で、位数４の互いに素な３つのコラプチブル部分群がＧ⁸から 識別される。ステップ３０６で、位数４の互いに素なコラプチブル部分群対から ４行の４つのコセットに分割される。次に、ステップ３１４で、４つのコセット のそれぞれが、それぞれ４行の４つのコセットに分割される。ステップ３１６で 、コセットは、上記の第ＩＩＩ節に示したようにそれぞれの混合変換によって変 換される。 最後に、ステップ３１８で、暗号化すべき左側の列中の各平文ブロックが、２ ５６個の数式の第２の行列の関連する数式の中央の列中の対応するブロックにｍ ｏｄ２加算され、右側の列中の暗号化ブロックが得られる。 前述の実施例の場合と同様に、第２１図および第２２図に示した方法は、上述 のブロック換字装置を使用して実施されるが、本明細書で述べたブロックの特定 の処理を実施するように修正される。この処理を実施するハード回線回路を提供 することが好ましい。しかし、プログラムされたコンピュータまたはマイクロプ ロセッサを使用することもできる。 ＶＩＩ．互いに素なコラプチブル部分群のコセット 次に、第２３図を参照して、データを暗号化するための第３の好ましい方法を 説明する。この方法は、互いに素なコラプチブル部分群のコセットを使用するも のである。最初に、この方法を一般的な数学的な観点から説明し、次いで、この 方法の特定のステップを図面に関して説明する。 識別行を除いて２つの部分群が互いに素である場合、それらの部分群も、互い に素な混合変換部分群を有する。位数４の部分群対を考察すると、対応するコセ ット対が共用する行は１つだけである。そのような互いに素なコセットの集合を アセンブルする場合、各コセットが、異なる混合変換によってコラプトされる。 このため、下記の２つの基本的な問題が発生する。 ａ．所与の線形直交写像でいくつのそのような互いに素なコラプチブル・コセ ットが見つかるか。 ｂ．対応する混合変換の集合にどんな群構造が存在するか。 にわたって一様な分布を有させるには、十分な数式をコラプトし、かつ頻繁に相 互に無効化することのない混合変換の集合を有する必要がある。 極大長線形直交写像数式アレイでは、それぞれ、同じ相対間隔を有する、ｋ個 の数式の２つの部分集合は、「相似」であると定義される。そのような２つの部 分集合中央の列は、ある整数１に関して下記の形式を有する。 極大部分群は、類似部分集合の例である。 前記の命題は、下記によって証明される。位数４のコラプチブル部分群は、次 式の形式を有する。 コセットは、部分群ではなく、部分群中の各行に行を加算して次式を得ることに よって生成される。 指数をある整数１だけシフトした場合、下記のような数式の類似集合が形成され る。 しかし、線形再帰関数によって生成される線形直交写像アレイの構造のために、 行ａ＋１を換算すると、次式のような新しいコラプチブル部分群が得られる。 指数の差ｋ−ｊだけ変位される。 次に、前記の概略的な説明を考慮に入れて、この方法を第２３図に関して説明 する。前述の第ＶおよびＶＩ節の方法と同様に、第２３図の方法は、関連する固 有のｎビット２進数暗号化ブロックで置き換えることによって、２ⁿ個の固有の ｎビット２進数平文ブロックの集合を暗号化するように働く。前述の方法と同様 に、暗号化は、ステップ４０２で、各数式が、左側の列中の２ⁿ個の平文ブロッ クのうちの１つを、中央の列中の２ⁿ個のｎビット数のうちの固有の１つとｍｏ ｄ２加算して、右側の列中の関連する固有のｎビット・ブロックを与えることを 表し、２ⁿ個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が第１の行列の１つの数式でもあることを特徴とする、線形直交写 像を表す２ⁿ個の数式の第１の行列Ｇⁿを求めることによって開始する。数式は、 零数式と、前記の数式１１ｂに示したように順序付けできる残りの２ⁿ−１個の 数式とを含む。ステップ４０４ないし４１４で、第１の行列中の２ⁿ−１個の非 零数式のうちの複数の数式が、２ⁿ−１個の数式の第２の行列を与えるように修 正される。 ステップ３０４で、位数４のコラプチブル部分群がＧⁿから選択される。位数 ４のそのような部分群は一般に、次式で表される。 ステップ３０６で、位数４のコラプチブル部分群にはない、指数ａによって表 される数式を選択することによって生成される。この数式が、コラプチブル部分 群にベクトル的に加算されて、次式によって表されるコセットが生成される。 ない場合は、ｍを除する整数１を選択する。 その後、ステップ３０８で、値ａ ｍｏｄ１、ｂ ｍｏｄ２、ｃ ｍｏｄ２、 ｄ ｍｏｄ１に関して値が求められる。ステップ３１０で、ステップ３０８で求 めた値のうちのどれかがが重複している場合、異なる指数の数式によってステッ プ３０６および３０８が反復される。重複のない値の集合が得られた後、ステッ プ３１２が実行され、ｍ／ｌ個の追加コセットが生成される。追加コセットは次 式の形式を有する。 ステップ３１４で、混合変換が対応するコセットに適用される。この混合変換 するコセットを建設的にコラプトするように適用され、そのため、２ⁿ個の数式 の第２の行列を生成する。 最後に、ステップ３１６で、暗号化すべき左側の列中の各平文ブロックが、２ⁿ 個の数式の第２の行列の関連する数式の中央の列中の対応するブロックにｍｏ ｄ２加算され、右側の列中の暗号化ブロックが得られる。最後のステップ３１６ は、前記で本発明の好ましい他の実施例に関して説明した最後のステップに類似 している。 第２３図で述べた様々なステップを実施するハード回線回路を提供することが 好ましい。しかし、プログラムされたコンピュータまたはマイクロプロセッサを 使用することもできる。 第２３図の方法の具体的な例として、数式５１中の直交写像を考察する。次式 混合変換はＡである。行７を使用して、次式のようにコセットを生成する。 だけ変位して次式を得る。 対応する部分群は、次式のように、行１２を他の３つに加算することによって 求めることができる。 る。 このプロセスは、より大きな位数の部分群に適用できるが、位数４のコセット と共に建設的コラプションに使用するのが特に容易である。手順は、下記のとお りである。位数４の任意のコラプチブル部分群を選択する。一般性を失わないよ うに、部分群は次式のようになる。 最初、ｍ＝２ⁿ−１が素数でない（すなわち、Ｍｅｒｓｅｎｎｅ素数でない） と仮定する。ｍを除するある整数ｌを選択し、前述の命題８の証明の場合と同様 に、これを指数のシフトとして使用する。その同じ証明の場合と同様に、部分群 中にない、ある指数ａを含む数式を選択する。この数式を数式７６中の各数式に ベクトル的に加算すると、次式のコセットが得られる。 次に、４つの値ａ ｍｏｄ ｌ、ｂ ｍｏｄ ｌ、ｃ ｍｏｄ ｌ、ｄ ｍｏ ｄ ｌを求める。重複がある場合は、このコセットを拒否して別のコセットを試 す。なぜなら、これらの指数の増分としてｌの倍数を使用することによって類似 の連続コセットを求めると、矛盾がもたらされるからである。たとえば、ａ≡ｂ ｍｏｄ ｌであると仮定する。その場合、ある整数ｇに関して、後に続くある コセットが前のコセットと同じ行を有するようにａ＝ｂ＋ｇｌとなる。次に、ａ セットを生成する。 る。 前記の命題は下記によって証明することができる。Ｗ∪θは群ではない。これ る。ｌ＝^2n-k｜ｌ−１である場合でも、この比率は奇数でなければならず、これ に対して２^kは、ｋ＞０の場合は偶数である。一般性を失わずに、ある関数ｇ ₁εＷであると仮定する。ｈｌ＞ｍである場合、ｈｌ≡ｃｌ ｍｏｄ ｍであり 、ｌ｜ｍなのでｃｌ＜ｍである。下付き文字が線形直交写像アレイ中の行の指数 で を得る。 さらに一般的には、すべての整数ｊに関して次式が成立する。 ではなく他のｘ_iεＷに適用することができる。これは、Ｗ∪θが群であること を意味し、これは命題に矛盾する。次に、３｜ｍであると仮定する。次式の可能 な和を考察する。 数式８０をもたらす同じ手順を使用する場合、次式が成立する。 したがって、同じ数式が得られる。したがって、これを使用して群を生成する ことはできない。 このことの実際的な結果は、２つの数式が同じコセット中にある場合、それら の和は他の位置にあるということである。これらの数式は、建設的コラプション 用の共通の混合変換、たとえばｗ_iを有する。この和は、数式７６の部分群中の ことに留意されたい。この場合、Ｓ’（ｘ）は、線形直交写像から得た最初の写 像であり、Ｓ（ｘ）は、建設的コラプションの後に結果として得られる写像であ り、和数式が他のコラプチブル・コセットのうちの１つ中にない場合、数式４か ら次式が成立する。 さらに、３つ組は線形になる。和数式は、他のコラプチブル・コセットにある 場合、あるｗ_j≠ｗ_iを混合変換として有し、そのため、次式が成立する。 異なるコセットから得た２つの数式を、それぞれの混合変換ｗ_iおよびｗ_jによ って加算する場合、和数式がコセット中にあるか、それとも最初のコセットのう ちの１つ中にあるか、それとも第３のコセット中にあるかに応じて、３つの可能 性がある。 ２つの数式、すなわち、コセットから得た数式と、どのコセットにもない数式 を加算する場合、前のケースと同様に、次式のような３つの可能性がある。 最後に、どちらも、どちらのコラプチブル・コセットにも含まれない、２つの 数式を加算する場合、その和がコセット中にあるか、それともないかに応じて、 次式のような２つの可能性がある。 残留線形性を最小限に抑えるには、前記から、２つの条件、すなわち、コセッ トに含まれない残りの数式の集合が、小さいことと、部分群を含まないことが必 要であることが明らかである。一例として、８ビット２進数に関する数式５１中 の同じ線形直交写像と、数式７２および７３中の部分群およびコセットを考察す る。 この場合も、行指数に増分としてｌ＝５を適用し、コセットの系列を生成する 。次式に留意されたい。 ｍ＝２ⁿ−１＝２５５＝５・５１なので、ｌ｜ｍであり、前記の行指数の集合 が、ｌ＝５だけ増分されたときに重なることがなく、すなわち、すべての整数ｉ 、ｊに関して７＋５_i≠５０＋５_jであり、他の対に関しても同じである。したが って、このプロセスによって、４つの数式のそれぞれの５１個のコセット、すな わち、建設的コラプションで修正すべき合計で２０４個の数式が生成される。命 令 わち、最初の２つの数式の中央の項の和は、コセット中にある。 これは、線形直交写像中の第１の非零行の中央の項である。 したがって、第１の数式が次式であるコセットとしてコセット５ｋを指定する と、 対応する混合変換を下記に示す。 したがって、加算識別を含めて、Ｗ＝｛θ，ｘ₁，ｘ₆，．．．，ｘ₂₅₁｝であ り、｜Ｗ｜＝５２である。ｍ＝２５５＝３・８５であるので、３｜ｍであり、ｘ 在する数のそのような３つ組に過ぎない。この例では、次式が成立する。 もちろん、異なる部分群からコセットを選択することができる。たとえば、ｍ ＝２５５＝１５・１７なので、同じ線形直交写像中でｌ＝１７を選択する。３つ の異なる部分から得た３つのコセット（下記に示す）を考察する。 すべての行指数が異なるｍｏｄ１７なので、増分ｌ＝１７を使用しても重なり はない。このプロセスによって、建設的コラプションの候補として３×１５＝４ ５個のコセットまたは１８０個の数式が生成される。混合変換の集合を下記に示 す。 他の多数の可能性がある。たとえば、数式５２中の位数８の部分群を使用する ことができる。この部分群のコセットは完全にコラプチブルであり、すなわち、 ４つの混合変換の群を有する。命題７を適用すると、次式のように、数式５３の ８つの数式のコセットを選択することができ、このうちの６つは非線形化するこ とができる。 増分ｌ＝１７を使用すると、次式から、それぞれ６行の互いに素な１５個の集 合を得ることができる。 行指数を７だけシフトすると、次式から、それぞれ６行の互いに素な１５個の 集合をさらに得ることができる。 この組合せは、非線形化用の１８０個の行または数式を与えるが、混合変換の 集合はもはや、加算３つ組から自由ではなく、その結果、混合変換間にある種の 群構造が生じる。 行指数をｍだけシフトする際に不連続な部分があるので、２ⁿ−１＝ｍが素数 であるとき、互いに素な部分群からコラプチブル・コセットを得るプロセスは、 わずかにより複雑になる。一例として、下記の母関数によって定義されるブロッ ク・サイズ７極大長線形直交写像を考察する。 数式５２の場合と同様に、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ｝を７ビット２進数 の任意の完全な線形独立集合とすることができる。前述のように、表記法ＡＢＣ を下記に示す。 位数４の典型的なコラプチブル部分群を下記に示す。 これから、下記のコセットを構築することができる。 増分間隔が可能である。この場合、次式が成立する。 これらの指数を５だけ変位すると、次式が得られる。 これらの指数をさらに１５だけ変位すると、次式が得られる。 これらの指数をさらに２０だけ変位すると、次式が得られる。 これらの指数をさらに８０だけ変位すると、次式が得られる。 最終的に１０だけ増分してさらに１ステップだけ進むことができる。 このプロセスによって、建設的なコラプション・プロセス用の互いに素な２７ 個のコセットまたは１２７行のうちの１０４行が生成された。前記の手順では、 指数０または３ｍｏｄ５のすべての行が使い尽くされた。したがって、他の異な る行指数を有するコラプチブル・コセットはもはや存在しない。しかし、指数１ ｍｏｄ５の１５行、指数２ｍｏｄ５の２行、指数４ｍｏｄ５の２行が残る。混合 変換は、各コセット中の最初の２行の中央の列中の数の和であり、すなわち、次 式が成立する。 したがって、混合変換の集合は、０≦ｋ≦２５の場合、Ｗ＝｛θ，ｘ_1+5k，ｘ₄ ｝であり、｜Ｗ｜＝２８である。この場合、命題９の条件が成立せず、すなわ れたい。 非線形プロセス用のコラプチブル・コセットを選択するための他の多数の方法 がある。異なる指数の混合コセットは、線形アレイ中のほぼすべての数式を含め る機構を提供することができるが、これは、混合変換の集合の構造に対して平衡 させなければならない。ｎビット数に関する直交写像の総数は不明である。 本明細書では、本発明の暗号化および復号化に関する好ましい実施例を開示し 説明したが、当業者には、本発明の趣旨および範囲から逸脱せずに本発明の態様 および詳細に様々な変更を加えられることが自明であろう。 ＶＩＩＩ．用語および記号の定義 すべての下記の定義は、ビットごとのｍｏｄ２加算（ＸＯＲｉｎｇ）演算を受 けるｎビット２進数と、このような数に関する全単射写像を対象とするものであ る。 これは線形と呼ばれることが多い。この場合、線形の語は、ｃ＝θであるケース 、すなわち、加算識別に使用される。 完全にコラプチブル：極大数の混合変換を含むコラプチブル・コセット。完全に コラプチブルなコセットの位数が２^kである場合、対応する混合変換の集合の位 数は２^k-1である。 建設的コラプション：線形数式アレイの２つの列中のブロックの順序を再構成し （第２図）、第３列を固定されたままにし、同時に、各行の等性を維持すること によって、線形直交写像を非線形直交写像に変換するプロセス。 コラプチブル集合：建設的コラプション・プロセスによって独立集合として非線 形化することができる数式の集合、通常はコセットまたは部分群。 号化または復号化を行うブロック換字装置またはＳボックス。 母関数：下記の形式の再帰関数。 ｎビット数の完全な線形独立集合に適用されたときに、数式１１中の線形直交 写像を定義する。これは、線形フィードバック・シフト・レジスタの母関数と同 ア体ＧＦ（２ⁿ）における原子多項式である。 １参照）。 混合変換が線形直交写像中の数式のコラプチブル集合にベクトル的にｍｏｄ２加 算されて、非線形直交写像が得られる。 。シフト：線形直交写像を表す数式のアレイ中のｎビット数の列間の変位。各列 は、同じ順序であるが、異なる開始点を有する（数式１１参照）。 相似集合：同じ相対間隔を有する線形アレイ中の数式の部分集合。 アレイ中の行または数式。 θ＝００．．．０：加算識別。 ＧＦ（２ⁿ）：２進係数を有する次数ｎの多項式のガロア体。

Claims (1)

1. 【特許請求の範囲】 １．２ⁿ個の固有のｎビット２進数平文ブロックのうちの１つを関連する固有 のｎビット２進数暗号化ブロックで置き換えることによる暗号化方法において、 （ａ）各数式が、左側の列中の２ⁿ個の平文ブロックのうちの１つのブロック に中央の列中の２ⁿ個のｎビット・ブロックのうちの固有の１つのブロックをｍ ｏｄ２加算して右側の列中の関連する固有のｎビット・ブロックを与えることを 表し、２ⁿ個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が第１の行列中の１つの数式でもあることを特徴とし、前記１つの 順序付けることができ、 上式で、ｍ＝２ⁿであり、Ｌ、Ｍ、Ｒがそれぞれ、左側、中央、右側の列であ り、Ｇⁿ＝Ｌ_nＸＭ_nＸＲ_nが数式の集合を表し、Ｇ^n-1が、Ｇⁿ中のｎ−１個の連続 数式によって生成されるＧⁿの部分群であり、かつ２^n-1個の数式の部分行列であ ^n-1中のｎ−２個の数式によって生成されるＧ^n-1の部分群であり、かつ２^n-2個 Ｇ^n-1が、識別数式を含むＧⁿの部分行列であり、残りの２^n-1−１個の数式が 、次式のように順序付けることができ、 べての残りの２^n-1個の数式であり、ｎ−２個の連続数式をＧ^n-1から選択してこ れらの数式と識別数式のすべての和を求めることによって選択されたＧ^n-1から 得 Ｇ^n-1から得たすべての残りの２^n-2個の数式であり、Ｇ³から得た識別数式と２ つの連続数式とそれらの和を含む２²＝４個の数式を含むＧ²が選択されるまで、 連 ４つの数式である、直交写像を表す２ⁿ個の数式の第１の行列Ｇⁿを求めるステッ プと、 （ｂ）２ⁿ個の数式の第１の行列中の２ⁿ−１個の非零数式のうちの複数の数式 を、非線形直交写像を表す２ⁿ個の数式の第２の行列を与えるように修正し、修 正済みの複数の数式が全体として、左側の列中の平文ブロックを右側の列中の固 有の暗号化ｎビット・ブロックに写像するが、各修正済み数式が未修正の第１の 集合中のどんな数の数式のｍｏｄ２和にもならないように非線形的に写像するよ うに、前記複数の数式が修正され、２ⁿ−１個の非零数式のうちの前記複数の数 式の前記修正が、 Ｗ_n-2中の２^n-3個の混合変換をＧ^n-1に適用し、 Ｗ_n-3中の２^n-4個の混合変換をＧ^n-2に適用し、 （ｃ）暗号化すべき左側の列中の各平文ブロックごとに、２ⁿ個の数式の第２ の行列の関連する数式に従って中央の列中の前記ブロックに関連する２ⁿ個のｎ ビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して、右側の列 中の暗号化ブロックを得るステップとを含むことを特徴とする方法。 とする請求項１に記載の方法。 とする請求項１に記載の方法。 ４．２ⁿ個の固有のｎビット２進数平文ブロックのうちの１つを関連する固有 のｎビット２進数暗号化ブロックで置き換えることによる暗号化方法において、 （ａ）各数式が、左側の列中の２ⁿ個の平文ブロックのうちの１つのブロック に中央の列中の２ⁿ個のｎビット・ブロックのうちの固有の１つのブロックをｍ ｏｄ２加算して右側の列中の関連する固有のｎビット・ブロックを与えることを 表し、２ⁿ個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が第１の行列中の１つの数式でもあることを特徴とし、前記１つの 順序付けることができ、 上式で、ｍ＝２ⁿであり、Ｌ_n、Ｍ_n、Ｒ_nがそれぞれ、左側、中央、右側の列で あり、Ｇⁿ＝Ｌ_nＸＭ_nＸＲ_nが数式の集合を表す、直交写像を表す２ⁿ個の数式の 第１の行列Ｇⁿを求めるステップと、 （ｂ）２ⁿ個の数式の第１の行列中の２ⁿ−１個の非零数式のうちの複数の数式 を、非線形直交写像を表す２ⁿ個の数式の第２の行列を与えるように修正し、修 正済みの複数の数式が全体として、左側の列中の平文ブロックを右側の列中の固 有の暗号化ｎビット・ブロックに写像するが、各修正済み数式が未修正の第１の 集合中のどんな数の数式のｍｏｄ２和にもならないように非線形的に写像するよ うに、前記複数の数式が修正され、２ⁿ−１個の非零数式のうちの前記複数の数 式の前記修正が、 数がｎ以下であるｋ個の連続数式のすべての組合せのｍｏｄ２和を求めることに 素な２つ以上のコラプチブル部分群をＧⁿから選択し、 ｎが奇数であるか、それとも偶数であるかに応じて、位数２^n-1または２^n-2の コセットに分割され、Ｑ_oのコセットが次に小さな部分群のコセットに分割され コセットが生成されることによって行われるステップと、 （ｃ）数式の第１の行列全体Ｇⁿを表すそのようなコセットの交項系列を選択 するステップと、 （ｄ）数式の第２の行列を生成するように、交項系列の各コセットを対応する 混合変換で修正するステップと、 （ｅ）暗号化すべき左側の列中の各平文ブロックごとに、２ⁿ個の数式の第２ の行列の関連する数式に従って中央の列中の前記ブロックに関連する２ⁿ個のｎ ビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して、右側の列 中の暗号化ブロックを得るステップとを含むことを特徴とする方法。 ５．２⁸個の固有のｎビット２進数平文ブロックのうちの１つを関連する固有 のｎビット２進数暗号化ブロックで置き換えることによる暗号化方法において、 （ａ）各数式が、左側の列中の２⁸個の平文ブロックのうちの１つのブロック に中央の列中の２⁸個の８ビット・ブロックのうちの固有の１つのブロックをｍ ｏｄ２加算して右側の列中の関連する固有の８ビット・ブロックを与えることを 表し、２⁸個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が第１の行列中の１つの数式でもあることを特徴とし、前記１つの のように順序付けることができ、 上式で、ｍ＝２⁸−１＝２５５であり、Ｌ₈、Ｍ₈、Ｒ₈がそれぞれ、左側、中央 、右側の列であり、Ｇ⁸＝Ｌ₈ＸＭ₈ＸＲ₈が数式の集合を表す、直交写像を表す２⁸ 個の数式の第１の行列Ｇ⁸を求めるステップと、 （ｂ）２⁸＝２５６個の数式の第１の行列中の２⁸−１＝２５５個の非零数式の うちの複数の数式を、非線形直交写像を表す２５６個の数式の第２の行列を与え るように修正し、修正済みの複数の数式が全体として、左側の列中の平文ブロッ クを右側の列中の固有の暗号化８ビット・ブロックに写像するが、各修正済み数 式が未修正の第１の集合中のどんな数の数式のｍｏｄ２和にもならないように非 線形的に写像するように、前記複数の数式が修正され、２５５個の非零数式のう ちの前記複数の数式の前記修正が、 前記コセットをそれぞれ１６行の４つのコセットに分割し、 前記４つのコセットのそれぞれを、それぞれ４行の４つのコセットに分割する ことによって行われるステップと、 （ｃ）数式の第１の行列全体Ｇⁿを表すそのようなコセットの交項系列を選択 するステップと、 （ｄ）数式の非線形化された第２の行列を求めるように、前記交項系列の各コ セットをその混合変換で修正するステップと、 （ｅ）暗号化すべき左側の列中の各平文ブロックごとに、２⁸個の数式の第２ の行列の関連する数式に従って中央の列中の前記ブロックに関連する２⁸個の８ ビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して、右側の列 中の暗号化ブロックを得るステップとを含むことを特徴とする方法。 ６．２ⁿ個の固有のｎビット２進数平文ブロックのうちの１つを関連する固有 のｎビット２進数暗号化ブロックで置き換えることによる暗号化方法において、 （ａ）各数式が、左側の列中の２ⁿ個の平文ブロックのうちの１つのブロック に中央の列中の２ⁿ個のｎビット・ブロックのうちの固有の１つのブロックをｍ ｏｄ２加算して右側の列中の関連する固有のｎビット・ブロックを与えることを 表し、２ⁿ個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が第１の行列中の１つの数式でもあることを特徴とし、前記１つの 順序付けることができ、 上式で、ｍ＝２ⁿ−１であり、ｍが素数ではなく、Ｌ_n、Ｍ_n、Ｒ_nがそれぞれ、 左側、中央、右側の列であり、Ｇⁿ＝Ｌ_nＸＭ_nＸＲ_nが数式の集合を表す、直交写 像を表す２ⁿ個の数式の第１の行列Ｇⁿを求めるステップと、 （ｂ）２ⁿ個の数式の第１の行列中の２ⁿ−１個の非零数式のうちの複数の数式 を、非線形直交写像を表す２ⁿ個の数式の第２の行列を与えるように修正し、修 正済みの複数の数式が全体として、左側の列中の平文ブロックを右側の列中の固 有の暗号化ｎビット・ブロックに写像するが、各修正済み数式が未修正の第１の 集合中のどんな数の数式のｍｏｄ２和にもならないように非線形的に写像するよ うに、前記複数の数式が修正され、２ⁿ−１個の非零数式のうちの前記複数の数 式の前記修正が、 （１）数式の第１の線形直交写像行列から得た２つの連続行を含むＧⁿから、 選択し、 _pで表される数式を選択し、前記コラプチブル部分群中の各数式に前記数式をベ ットを生成することによって、コセットを生成し、 （３）ｍを除する整数１を選択し、ａ ｍｏｄｌ、ｂ ｍｏｄｌ、ｃ ｍｏｄ ｌ、ｄ ｍｏｄｌの値を求め、 （４）前記値のうちのどれかが重複している場合、４つの異なる値が得られる までステップ（２）および（３）を繰り返し、 適用して前記追加コセットを建設的にコラプトし、２ⁿ個の数式の第２の行列を 生成することによって行われるステップと、 （ｃ）暗号化すべき左側の列中の各平文ブロックごとに、２ⁿ個の数式の第２ の行列の関連する数式に従って中央の列中の前記ブロックに関連する２ⁿ個のｎ ビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して、右側の列 中の暗号化ブロックを得るステップとを含むことを特徴とする方法。 ７．２ⁿ個の固有のｎビット２進数平文ブロックのうちの１つを関連する固有 のｎビット２進数暗号化ブロックで置き換えることによる暗号化方法において、 （ａ）各数式が、左側の列中の２ⁿ個の平文ブロックのうちの１つのブロック に中央の列中の２ⁿ個のｎビット・ブロックのうちの固有の１つのブロックをｍ ｏｄ２加算して右側の列中の関連する固有のｎビット・ブロックを与えることを 表し、２ⁿ個の数式の第１の行列中のすべての数式が、任意の数の数式のｍｏｄ ２ベクトル和が第１の行列中の１つの数式でもあることを特徴とし、前記１つの 順序付けることができ、 上式で、ｍ＝２^n-1であり、ｍが素数であり、Ｌ_n、Ｍ_n、Ｒ_nがそれぞれ、左側 、中央、右側の列であり、Ｇⁿ＝Ｌ_nＸＭ_nＸＲ_nが数式の集合を表す、直交写像を 表す２ⁿ個の数式の第１の行列Ｇⁿを求めるステップと、 （ｂ）２ⁿ個の数式の第１の行列中の２ⁿ−１個の非零数式のうちの複数の数式 を、非線形直交写像を表す２ⁿ個の数式の第２の行列を与えるように修正し、修 正済みの複数の数式が全体として、左側の列中の平文ブロックを右側の列中の固 有の暗号化ｎビット・ブロックに写像するが、各修正済み数式が未修正の第１の 集合中のどんな数の数式のｍｏｄ２和にもならないように非線形的に写像するよ うに、前記複数の数式が修正され、２ⁿ−１個の非零数式のうちの前記複数の数 式の前記修正が、 （１）数式の第１の線形直交写像行列から得た２つの連続行を含むＧⁿから、 選択し、 _pで表される数式を選択し、前記コラプチブル部分群中の各数式に前記数式をベ ットを生成することによって、コセットを生成し、 （３）整数ｌ＝５を選択して、ａ ｍｏｄ５、ｂ ｍｏｄ５、ｃ ｍｏｄ５、 ｄ ｍｏｄ５の値を求め、 （４）前記値のうちのどれかが重複している場合、４つの異なる値が得られる までステップ（２）および（３）を繰り返し、 （５）ｋ＝１，２，３，．．．の連続値をとって次式の形式のｍ／ｌ個の追加 コセットを生成し、 前に生成された数式を含むコセットが生成されるまでこの動作を継続し、 （６）最後の重複コセットを削除して、新しいコセットが生成されるまで連続 的に大きくなるｋの値を選択し、 （７）重なりのないコセットが生成されなくなるまでステップ９ｂ）（５）お よび（ｂ）（６）を繰り返し、 （８）ステップ（ｂ）（２）を繰り返して、使用済みの数式を含まない新しい コセットを見つけ、 （９）整数１ないし６を使用してステップ（ｂ）（３）を繰り返し、ｍｏｄ６ の値を求め、次いで、ステップ（ｂ）（４）、（ｂ）（５）、（ｂ）（６）、（ ｂ）（７）を繰り返し、 （１０）必要に応じて、共通の除数を有さない数を使用し、あるいは、異なる コセットが見つからなくなるまで、ステップ９ｂ）（９）を繰り返し、 を適用して前記追加コセットを建設的にコラプトし、２ⁿ個の数式の第２の行列 を生成することによって行われるステップと、 （ｃ）暗号化すべき左側の列中の各平文ブロックごとに、２ⁿ個の数式の第２ の行列の関連する数式に従って中央の列中の前記ブロックに関連する２ⁿ個のｎ ビット・ブロックのうちの固有の１つのブロックをｍｏｄ２加算して、右側の列 中の暗号化ブロックを得るステップとを含むことを特徴とする方法。 ８．それぞれ、第１の２進値が第２の２進値にｍｏｄ２加算されて第３の２進 値が生成されるブロック換字演算を定義する、数式の行を有し、前記数式の行が ある位数を有し、各２進値が、各列内で１度しか表されない、線形直交写像ブロ ック換字数式の集合を生成するステップと、 第１および第２の２進値の行順序を独立に再構成し、同時に、第３の固定値の 行順序を保持し、各行の等性を維持することによって、線形直交写像ブロック換 字数式を建設的にコラプトして非線形直交写像ブロック換字数式を生成するステ ップとを含むブロック換字方法。 ９．線形直交写像ブロック換字を建設的にコラプトする前記ステップが、 ブロック換字数式の部分群の入れ子系列を生成するステップと、 前記部分群の入れ子系列に対応する混合変換の入れ子系列を生成するステップ と、 すべての部分群が生成されるまで、前記混合変換の入れ子系列を前記部分群の 入れ子系列に連続的に適用するステップとを含むことを特徴とする請求項８に記 載の方法。 １０．線形直交写像ブロック換字を建設的にコラプトする前記ステップが、 線形直交写像ブロック換字数式の集合から互いに素な２つ以上のコラプチブル 部分群を選択するステップと、 前記部分群をコセットに分割するステップと、 前記線形直交写像ブロック換字数式の集合を表す前記コセットの系列を選択す るステップと、 前記選択されたコセットの系列に対応する混合変換の集合を生成するステップ と、 前記選択されたコセットの集合の各コセットを対応する混合変換によって修正 し、非線形直交写像ブロック換字数式の集合を生成するステップとを含むことを 特徴とする請求項８に記載の方法。 １１．前記線形直交写像ブロック換字数式の集合が、識別数式を含み、順次指 数１，．．．，２ⁿ−１で識別される識別数式の後に続くブロックを有する２ⁿ個 の数式行を含み、ｍ＝２ⁿ−１であり、ｍが素数ではなく、線形直交写像ブロッ ク換字を建設的にコラプトする前記ステップが、 ａ）前記線形直交写像ブロック換字数式の集合から４行のコラプチブル部分群 を選択するステップと、 ｂ）前記部分群にない数式を選択し、前記部分群の各行に前記数式をベクトル 的に加算して、指数ａ、ｂ、ｃ、ｄによって識別される行を有するコセットを生 成することによって、コセットを生成するステップと、 ｃ）ｍを除する数ｌを選択するステップと、 ｄ）ａ ｍｏｄｌ、ｂ ｍｏｄｌ、ｃ ｍｏｄｌ、ｄ ｍｏｄｌが重複を含む かどうか判定するステップと、 ｅ）ａ ｍｏｄｌ、ｂ ｍｏｄｌ、ｃ ｍｏｄｌ、ｄ ｍｏｄｌで重複が発生 した場合、前記コセットを拒否してステップａ）ないしｄ）を生成するステップ と、 ｆ）指数を量ｋｌだけシフトすることによってｍ／ｌ個の追加コセットを前記 コセットから生成するステップと（０＜ｋ＜ｍ／ｌ−１）、 ｇ）前記追加コセットに混合変換を適用して、前記非線形ブロック換字数式を 生成するステップとを含むことを特徴とする請求項８に記載の方法。 １２．前記線形直交写像ブロック換字数式の集合が、識別数式を含み、順次指 数１，．．．，２ⁿ−１で識別される識別数式の後に続くブロックを有する２ⁿ個 の数式行を含み、ｍ＝２ⁿ−１であり、ｍが素数ではなく、線形直交写像ブロッ ク換字を建設的にコラプトする前記ステップが、 ａ）前記線形直交写像ブロック換字数式の集合から４行のコラプチブル部分群 を選択するステップと、 ｂ）前記部分群にない数式を選択し、前記部分群の各行に前記数式をベクトル 的に加算して、指数ａ、ｂ、ｃ、ｄによって識別される行を有するコセットを生 成することによって、コセットを生成するステップと、 ｃ）数ｌ＝５を選択するステップと、 ｄ）ａ ｍｏｄｌ、ｂ ｍｏｄｌ、ｃ ｍｏｄｌ、ｄ ｍｏｄｌが重複を含む かどうか判定するステップと、 ｅ）ａ ｍｏｄｌ、ｂ ｍｏｄｌ、ｃ ｍｏｄｌ、ｄ ｍｏｄｌで重複が発生 した場合、前記コセットを拒否してステップａ）ないしｄ）を生成するステップ と、 ｆ）整数ｋの連続値にわたって指数を量ｋｌだけシフトし、重なりのあるコセ ット、すなわち、前に生成されたコセット中に存在する数式を含むコセットが生 成されるまでこの動作を継続することによって、前記コセットから追加コセット を生成するステップと、 ｇ）前に生成されたコセット中に存在する数式を含む前記コセットを破棄し、 ｈ）連続的に大きくなるｋの値を使用して追加コセットを生成し、 ｉ）重なりのあるコセットが生成されなくなるまでステップｇ）およびｈ）を 繰り返し、 ｊ）ステップｂ）を繰り返して、重なりのない新しいコセットを見つけ、 ｋ）ｌ＝６に関してステップｄ）を繰り返して、ｍｏｄ６の値を求め、ステッ プｅ）ないしｈ）を繰り返し、 ｌ）重なりのないコセットが生成されなくなるまで、共通の除数を有さないｌ の値を使用してステップｋ）を繰り返し、 ｍ）前記追加コセットに混合変換を適用して、前記非線形ブロック換字数式を 生成するステップとを含むことを特徴とする請求項８に記載の方法。