JP4094758B2

JP4094758B2 - デ―タ置換・分割方法および装置

Info

Publication number: JP4094758B2
Application number: JP01623899A
Authority: JP
Inventors: 広樹植田; 和麻呂青木
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 1999-01-25
Filing date: 1999-01-25
Publication date: 2008-06-04
Anticipated expiration: 2019-01-25
Also published as: JP2000214769A

Description

【０００１】
【発明の属する技術分野】
本発明は、特に暗号技術の分野で用いられるデータ置換処理および分割処理を効率的に行なうデータ置換・分割方法および装置とデータ置換・分割プログラムを記録した記録媒体に関するものである。
【０００２】
【従来の技術】
従来、データを秘匿するためにデータの暗号化が行われる。このデータの暗号化を行う暗号化技術には、共通鍵暗号方式と公開鍵暗号方式がある。
【０００３】
公開鍵暗号方式ではデータを暗号化する鍵と復号化する鍵が異なっており、通常は暗号化に用いる鍵を一般に公開し、復号化に用いる鍵は利用者が秘密に保持する。公開される暗号化に用いる鍵から復号化に用いる鍵を求めることは、現在の数学的理論および計算機の計算能力をもってしても現実的な時間には完了しないものと信じられている。
【０００４】
一方、共通鍵暗号方式では、データを暗号化する鍵と復号化する鍵とは同一である。高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。ブロック暗号の多くはFeistel network と呼ばれる構造をもつ。この構造では、２ｎビットの入力をｎビットに分割し左右に振り分け、右側のｎビットデータに対して関数ｆを作用させ、その出力を左側のｎビットデータと排他的論理和を取り、左右データを交換して同様の操作を繰り返すものである。この構造については、「Bruce Schneier,Applied Cryptography,2nd edition,John-Wiley and Sons,p.347,1996」に示されている。
【０００５】
また共通鍵暗号方式は、公開鍵暗号方式に比べて計算に必要な処理量が少なく、単位時間当たりで暗号処理できるデータ量は数十倍から数百倍多い。したがって高速な暗号処理が必要な場面においては共通鍵暗号方式がよく用いられる傾向にある。
【０００６】
共通鍵暗号方式には、上記に述べた高速性のみならず、その安全性も必要とされる。近年いくつかの共通鍵暗号アルゴリズムに対する解読法が提案されている。そのため新しく開発される共通鍵アルゴリズムはこのような解読法に対して常に安全が確保されるようにしなければならない。これらの解読法については、「Bruce Schneier,Applied Cryptography,2nd edition,John-Wiley and Sons,pp.285-293,1996 」に示されている。
【０００７】
これらの解読法を適用しづらくさせるような方法も研究されており、それらの方法を用いることにより共通鍵暗号アルゴリズムの安全性を高めることが期待できる。その方法の１つとして、基礎となる暗号アルゴリズムへの入力データと出力データとを攻撃者から守るために、暗号鍵から得られるある種の値と入力データおよび出力データとの排他的論理和を計算する手法がある。この方法については「Bruce Schneier,Applied Cryptography,2nd edition,John-Wiley and Sons,pp.366-367,1996 」に示されている。なお、近年、提案される共通鍵暗号アルゴリズムでは、この方法を用いて設計されているものが多い。
【０００８】
上記方法を用いて、暗号鍵から得られるある種の値と排他的論理和を取った入力データは、基礎となる暗号アルゴリズムの入力データとなる。上記Feistel network を用いる場合、この入力データを左右へ分割することが必要となる。最近設計される共通鍵暗号アルゴリズムには、ただ左右へ入力データを分割するだけでなく、置換処理を行なった後に左右へ入力データを分割することで安全性の向上を達成しようとしているものも存在する。そのような例としてＥ２暗号がある（神田他、「１２８ビットブロック暗号Ｅ２の提案」、信学技報ＩＳＥＣ 98-12を参照のこと）。Ｅ２暗号ではＢＰ関数と呼ばれる置換処理を定義し、その後Feistel network のために左右へ入力データを分割している。
【０００９】
【発明が解決しようとする課題】
しかしながら、このＢＰ関数を実装する場合、次のような問題点が指摘されていた。すなわち、ＢＰ関数ではバイト単位の置換処理が必要であるが、最近のＭＰＵで実装されているワード単位のレジスタではマスク処理やシフト処理を伴うため処理時間がかかる点、及び、メモリへ一度コピーしてから置換処理を行なえたとしても、メモリアクセスにかかる時間が大きくなり処理時間がかかる点である。これは、上記に示したような共通鍵暗号方式への高速性を満足させることを困難にするものである。
【００１０】
本発明は、このような背景のもとになされたものであり、ワード単位のレジスタを用いてＥ２暗号のＢＰ関数での置換およびFeistel network での左右への分割を高速に処理する。Ｅ２暗号では、基礎となる暗号処理部はバイト単位の処理が行なわれるため、例えば右側にあるデータの並びは必ずしも仕様に沿う必要はない。すなわち、内部にある暗号処理部の実装部が、変更されたバイト列に対応しておけばよい。
【００１１】
さらに、本発明では置換処理後に左右に分割されるバイトの組を、仕様とは異なる列順ではあるが正しく左右に組として分割する。近年のＭＰＵでは内蔵されるレジスタ２つを連結させて仮想的に１つのレジスタとみなし、シフト処理を行ない上位側あるいは下位側のデータをレジスタに格納する命令が実装される場合もあり、このような装置が利用可能な場合はさらに効果的である。
【００１２】
すなわち、本発明は共通鍵暗号方式における処理を高速に行い得るデータ置換・分割方法および装置とデータ置換・分割プログラムを記録した記録媒体を提供することを目的とする。
【００１３】
【課題を解決するための手段】
前述した目的を達成するために、本発明のうちで請求項１記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を
【数５】

のように代入するステップと、レジスタＴ₀の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₀′に代入し、レジスタＴ₂の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₂′に代入し、レジスタＴ₀′の値とレジスタＴ₂′の値との論理和をレジスタＴ₄に代入するステップと、レジスタＴ₁の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₁′に代入し、レジスタＴ₃の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₃′に代入し、レジスタＴ₁′の値とレジスタＴ₃′との論理和をレジスタＴ₅に代入するステップと、レジスタＴ₀の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₀″に代入し、レジスタＴ₂の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₂″に代入し、レジスタＴ₀″の値とレジスタＴ₂″との論理和をレジスタＴ₆に代入するステップと、レジスタＴ₁の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₁″に代入し、レジスタＴ₃の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₃″に代入し、レジスタＴ₁″の値とレジスタＴ₃″との論理和をレジスタＴ₇に代入するステップと、レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力するステップとを有することを要旨とする。
【００１４】
また、本発明の請求項２記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を
【数６】

のように代入するステップと、レジスタＴ₀の値とレジスタＴ₂の値を各々一方の方向にｋビットローテートするステップと、レジスタＴ₀とレジスタＴ₂を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₄とするステップと、レジスタＴ₁とレジスタＴ₃を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₅とするステップと、レジスタＴ₂とレジスタＴ₀を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₆とするステップと、レジスタＴ₃とレジスタＴ₁を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₇とするステップと、レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力するステップとを有することを要旨とする。
【００１５】
また、本発明の請求項３記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を
【数７】

のように代入する手段と、レジスタＴ₀の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₀′に代入し、レジスタＴ₂の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₂′に代入し、レジスタＴ₀′の値とレジスタＴ₂′との論理和をレジスタＴ₄に代入する手段と、レジスタＴ₁の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₁′に代入し、レジスタＴ₃の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₃′に代入し、レジスタＴ₁′の値とレジスタＴ₃′との論理和をレジスタＴ₅に代入する手段と、レジスタＴ₀の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₀″に代入し、レジスタＴ₂の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₂″に代入し、レジスタＴ₀″の値とレジスタＴ₂″との論理和をレジスタＴ₆に代入する手段と、レジスタＴ₁の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₁″に代入し、レジスタＴ₃の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₃″に代入し、レジスタＴ₁″の値とレジスタＴ₃″との論理和をレジスタＴ₇に代入する手段と、レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力する手段とを有することを要旨とする。
【００１６】
また、本発明の請求項４記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を
【数８】

のように代入する手段と、レジスタＴ₀の値とレジスタＴ₂の値を各々一方の方向にｋビットローテートする手段と、レジスタＴ₀とレジスタＴ₂を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₄とする手段と、レジスタＴ₁とレジスタＴ₃を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₅とする手段と、レジスタＴ₂とレジスタＴ₀を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₆とする手段と、レジスタＴ₃とレジスタＴ₁を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₇とする手段と、レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力する手段とを有することを要旨とする。
【００１７】
また、本発明の請求項５記載の発明は、前記レジスタＴ_iとレジスタＴ_jとを連結し８ｋビット長のレジスタとみなし、一方または他方に２ｋビットシフトした後の一方端または他方端から４ｋビットをレジスタＴ_kとする手段と、この手段のうちいくつかを、レジスタＴ_iの値と（２^2k−１）との論理積を取ったデータをレジスタＴ_i′に代入し、レジスタＴ_jの値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ_j′に代入し、レジスタＴ_i′の値とレジスタＴ_j′の値との論理和をレジスタＴ_kに代入する手段とを有することを要旨とする。
【００２０】
すなわち、本発明では、ｋを整数とし、４ｋビット長のレジスタをレジスタＴ_iと表し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）をＢＰ関数への入力とし、各０≦ｉ≦３においてレジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を、
【数９】

のように代入する。
【００２１】
以後、この形式で代入されていることを
Ｔ_i＝［ａ_4i+0 ａ_4i+1 ａ_4i+2 ａ_4i+3］
のように記述する。
【００２２】
ここで集合［Ｌ］と集合［Ｒ］を、
【数１０】
［Ｌ］＝｛ａ_{4(i+j mod 4)+j}｜０≦ｉ≦１，０≦ｊ≦３｝
＝｛ａ₀，ａ₃，ａ₄，ａ₅，ａ₉，ａ₁₀，ａ₁₄，ａ₁₅｝
［Ｒ］＝｛ａ_{4(i+j mod 4)+j}｜２≦ｉ≦３，０≦ｊ≦３｝
＝｛ａ₁，ａ₂，ａ₆，ａ₇，ａ₈，ａ₁₁，ａ₁₂，ａ₁₃｝
とそれぞれ定義しておく。
【００２３】
レジスタＴ₀とレジスタＴ₂のデータ並びは、両端に集合［Ｌ］または集合［Ｒ］に属するデータが配置され、中央の２つに集合［Ｒ］または集合［Ｌ］に属するデータが配置されている。
【００２４】
このままの配置では、シフト命令を用いてのデータの分離は困難であるため、レジスタＴ₁またはレジスタＴ₃のように、一方、例えば右側または他方、すなわち左側に集合［Ｌ］または集合［Ｒ］のデータをまとめる。そのため、まずレジスタＴ₀とレジスタＴ₂を一方方向に、すなわち右周りにｋビットローテートさせる。
【００２５】
結果として以下のようにデータが配置される。
【００２６】
Ｔ₀＝［ａ₃ ａ₀ ａ₁ ａ₂］
Ｔ₁＝［ａ₄ ａ₅ ａ₆ ａ₇］
Ｔ₂＝［ａ₁₁ ａ₈ ａ₉ ａ₁₀］
Ｔ₃＝［ａ₁₂ ａ₁₃ ａ₁₄ ａ₁₅］
これによりレジスタＴ_i（０≦ｉ≦１）の上位２ｋビットには集合［Ｌ］に属するデータが配置され、下位２ｋビットには集合［Ｒ］に属するデータが配置される。また、レジスタＴ_i（２≦ｉ≦３）の上位２ｋビットには集合［Ｒ］に属するデータが配置され、下位２ｋビットには集合［Ｌ］に属するデータが配置される。
【００２７】
次に、レジスタＴ₀とレジスタＴ₂を連結し８ｋビット長のレジスタとみなし、右に２ｋビットシフトした後の右から４ｋビットをレジスタＴ₄とし、レジスタＴ₁とレジスタＴ₃を連結し８ｋビット長のレジスタとみなし、右に２ｋビットシフトした後の右から４ｋビットをレジスタＴ₅とする。
【００２８】
すなわち、
Ｔ₄＝［ａ₁ ａ₂ ａ₁₁ ａ₈］
Ｔ₅＝［ａ₆ ａ₇ ａ₁₂ ａ₁₃］
であって、これより、レジスタＴ_i（４≦ｉ≦５）は集合［Ｒ］に属するデータを過不足なく保持している。
【００２９】
同様に、レジスタＴ₂とレジスタＴ₀を連結し８ｋビット長のレジスタとみなし、左に２ｋビットシフトした後の左から４ｋビットをレジスタＴ₆とし、レジスタＴ₃とレジスタＴ₁を連結し８ｋビット長のレジスタとみなし、左に２ｋビットシフトした後の左から４ｋビットをレジスタＴ₇とする。
【００３０】
すなわち
Ｔ₆＝［ａ₉ ａ₁₀ ａ₃ ａ₀］
Ｔ₇＝［ａ₁₄ ａ₁₅ ａ₄ ａ₅］
であり、これより、レジスタＴ_i（６≦ｉ≦７）は集合［Ｌ］に属するデータを過不足なく保持している。
【００３１】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態について説明する。
【００３２】
図１は本発明の一実施の形態に係るデータ置換・分割装置の構成を示すブロック図である。
【００３３】
図１に示すように、制御部１は本実施形態の処理における各処理部および処理器等のコントロールを行なうものである。データ記憶部１１には予め入力データ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を格納し、処理終了時には出力データを格納する。算術演算部１３ではレジスタが具備され、ローテートやシフト処理が行なえる。
【００３４】
図２および図３はＥ２暗号におけるＢＰ関数のデータの置換処理を図示したものである。図２では、出力データの先頭４バイトが置換処理によってどのように構成されているのかを示している。図３では、この処理による集合［Ｌ］の要素を示している。
【００３５】
図４では、本実施形態を実行することによってレジスタＴ₆およびレジスタＴ₇に格納されるデータの並びを示している。図３と比較することによりレジスタＴ₆およびレジスタＴ₇には集合［Ｌ］の要素がすべて含まれており、ＢＰ関数およびFeistel network の左右への振り分けが行なわれていることが判る。
【００３６】
ここで請求項２，５，７に記載のローテートおよびシフトを用いる手法を選択した場合には、レジスタＴ₆およびレジスタＴ₇内のデータ並びは右２バイトと左２バイトが入れ替わる形になる。すなわち、図４で示されているレジスタＴ₄のデータ列［ａ₉ ａ₁₀ ａ₃ ａ₀］は［ａ₃ ａ₀ ａ₉ ａ₁₀］となる。しかしながら集合［Ｌ］の要素としては過不足なく、よって目的は達成される。
【００３７】
上述したように、本実施形態により、Ｅ２暗号の仕様において、ＢＰ関数の入出力を左からそれぞれ４バイトずつまとめてレジスタに代入するならば、入力の１つのレジスタにある４バイトは、出力の４つのレジスタに１バイトずつ代入されていることになる。これにより、１つのレジスタに対して演算を行ない、その結果を１つのレジスタに格納するような、ＭＰＵにある多くの命令では、１つの演算命令に対して１バイトしか処理できない。
【００３８】
従って、ＢＰ関数を実装するには１６個の命令が最低限必要となる。実際には、マスク処理や論理和処理などで１６以上の命令が必要である。
【００３９】
なお、レジスタの各バイトを直接入命令に用いた場合には１６命令で済む場合も考えられるが、一部のＭＰＵではその構造上ペナルティが発生し、通常の１６命令分以上の処理時間がかかることが判る。
【００４０】
さらに、入力データを一旦メモリに書き込んだ後に、ＢＰ関数の置換を考慮してバイト単位にデータを読み込む方法もあるが、近年のＭＰＵではメモリへのアクセスにはペナルティが発生する場合が多く、また上記と同様に構造上のペナルティが発生する場合もあり、やはり１６命令分以上の処理時間がかかることが判る。
【００４１】
本実施形態により、Ｅ２暗号のＢＰ部分はローテート命令２つと２つのレジスタを連結したものを右または左にシフトし、右または左の該当データをレジスタに代入する命令４つで構成できる。後半の処理を行なう命令は、例えばIntel 80386 以降のＭＰＵでは標準搭載されている命令であり、その実装には問題がない。従って、既存方法より高速にＢＰ関数を実行できる。
【００４２】
また、具体的にこの命令が実装されていないＭＰＵではマスク命令２つと論理和命令１つで代用することができる。すなわち、ローテート後のレジスタＴ₀とレジスタＴ₂を連結し８ｋビット長のレジスタとみなし、右に２ｋビットシフトした後の右から４ｋビットをレジスタＴ₅とする手段においては、レジスタＴ₀と（２^2k−１）との論理積を取ったデータをレジスタＴ₀′に代入し、レジスタＴ₂と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₂′に代入し、レジスタＴ₀′とレジスタＴ₂′との論理和をレジスタＴ₄に代入すればよい。
【００４３】
すなわち、
Ｔ₀′＝［００ａ₁ ａ₂］
Ｔ₂′＝［ａ₁₁ ａ₈ ００］
Ｔ₄ ＝［ａ₁₁ ａ₈ ａ₁ ａ₂］
となる。
【００４４】
この場合でも、ローテート命令２つを合わせて全体で１４命令で記述できるため、既存方法より高速にＢＰ関数を実行できる。
【００４５】
なお、この場合のレジスタＴ₄は、前述のレジスタＴ₄の保持する値と比較すると、上位２つの値と下位２つの値が入れ違いとなっている点が異なる。しかしレジスタＴ₄が保持する値はａ₁，ａ₂，ａ₈，ａ₁₁の４つであることに変わりはなく、従ってレジスタＴ₄とレジスタＴ₅とで集合［Ｒ］の値を過不足なく保持していることが保証される。
【００４６】
以上のように本実施形態は、暗号技術で用いられるデータ置換処理および分割処理に関して、特にＥ２暗号のＢＰ関数部の高速な実装を満足することができる。
【００４７】
また、このようなＥ２暗号のＢＰ関数等におけるデータ置換・分割演算は上述したデータ置換・分割プログラムにより実現され、該プログラムは記録媒体に記録して提供される。このようなデータ置換・分割プログラムが記録された記録媒体を利用して、そのデータ置換・分割プログラムの流通性を高めることができる。
【００４８】
【発明の効果】
以上のように本発明は、共通鍵暗号方式におけるデータ置換処理および分割処理に関し、処理を高速に行い得る等の効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るデータ置換・分割装置の一実施形態の概略の構成を示すブロック図である。
【図２】Ｅ２暗号のＢＰ関数部の置換処理を説明する図である。
【図３】ＢＰ関数の出力データの一部を示した図である。
【図４】レジスタＴ₄とレジスタＴ₅の出力データを示した図である。
【符号の説明】
１制御部
１１データ記憶部
１３算術演算部
１３ａレジスタ群

Claims

ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、
各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を

のように代入するステップと、
レジスタＴ₀の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₀′に代入し、レジスタＴ₂の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₂′に代入し、レジスタＴ₀′の値とレジスタＴ₂′の値との論理和をレジスタＴ₄に代入するステップと、
レジスタＴ₁の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₁′に代入し、レジスタＴ₃の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₃′に代入し、レジスタＴ₁′の値とレジスタＴ₃′との論理和をレジスタＴ₅に代入するステップと、
レジスタＴ₀の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₀″に代入し、レジスタＴ₂の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₂″に代入し、レジスタＴ₀″の値とレジスタＴ₂″との論理和をレジスタＴ₆に代入するステップと、
レジスタＴ₁の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₁″に代入し、レジスタＴ₃の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₃″に代入し、レジスタＴ₁″の値とレジスタＴ₃″との論理和をレジスタＴ₇に代入するステップと、
レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力するステップと
を有することを特徴とするデータ置換・分割方法。
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、
各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を

のように代入するステップと、
レジスタＴ₀の値とレジスタＴ₂の値を各々一方の方向にｋビットローテートするステップと、
レジスタＴ₀とレジスタＴ₂を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₄とするステップと、
レジスタＴ₁とレジスタＴ₃を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₅とするステップと、
レジスタＴ₂とレジスタＴ₀を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₆とするステップと、
レジスタＴ₃とレジスタＴ₁を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₇とするステップと、
レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力するステップと
を有することを特徴とするデータ置換・分割方法。
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、
各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を

のように代入する手段と、
レジスタＴ₀の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₀′に代入し、レジスタＴ₂の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₂′に代入し、レジスタＴ₀′の値とレジスタＴ₂′との論理和をレジスタＴ₄に代入する手段と、
レジスタＴ₁の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₁′に代入し、レジスタＴ₃の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₃′に代入し、レジスタＴ₁′の値とレジスタＴ₃′との論理和をレジスタＴ₅に代入する手段と、
レジスタＴ₀の値と（２^4k−２^3k＋２^k−１）との論理積を取ったデータをレジスタＴ₀″に代入し、レジスタＴ₂の値と（２^3k−２^k）との論理積を取ったデータをレジスタＴ₂″に代入し、レジスタＴ₀″の値とレジスタＴ₂″との論理和をレジスタＴ₆に代入する手段と、
レジスタＴ₁の値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ₁″に代入し、レジスタＴ₃の値と（２^2k−１）との論理積を取ったデータをレジスタＴ₃″に代入し、レジスタＴ₁″の値とレジスタＴ₃″との論理和をレジスタＴ₇に代入する手段と、
レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力する手段と
を有することを特徴とするデータ置換・分割装置。
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ_4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ_{4(i+j mod 4)+j}｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ_{4(i+j mod 4)+j}｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、
各０≦ｉ≦３において、レジスタＴ_iに｛ａ_4i+j｝（０≦ｊ≦３）を

のように代入する手段と、
レジスタＴ₀の値とレジスタＴ₂の値を各々一方の方向にｋビットローテートする手段と、
レジスタＴ₀とレジスタＴ₂を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₄とする手段と、
レジスタＴ₁とレジスタＴ₃を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ₅とする手段と、
レジスタＴ₂とレジスタＴ₀を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₆とする手段と、
レジスタＴ₃とレジスタＴ₁を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ₇とする手段と、
レジスタＴ₄，レジスタＴ₅とレジスタＴ₆，レジスタＴ₇とを２つのグループとして出力する手段と
を有することを特徴とするデータ置換・分割装置。
前記レジスタＴ_iとレジスタＴ_jとを連結し８ｋビット長のレジスタとみなし、一方または他方に２ｋビットシフトした後の一方端または他方端から４ｋビットをレジスタＴ_kとする手段と、
この手段のうちいくつかを、レジスタＴ_iの値と（２^2k−１）との論理積を取ったデータをレジスタＴ_i′に代入し、レジスタＴ_jの値と（２^4k−２^2k）との論理積を取ったデータをレジスタＴ_j′に代入し、レジスタＴ_i′の値とレジスタＴ_j′の値との論理和をレジスタＴ_kに代入する手段と
を有することを特徴とする請求項４記載のデータ置換・分割装置。