(57)【特許請求の範囲】
【請求項１】
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、
各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数１】
0004094758.tif 000007
のように代入するステップと、
レジスタＴ0 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ0 ′に代入し、レジスタＴ2 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ2 ′に代入し、レジスタＴ0 ′の値とレジスタＴ2 ′の値との論理和をレジスタＴ4 に代入するステップと、
レジスタＴ1 の値と（２2k−１）との論理積を取ったデータをレジスタＴ1 ′に代入し、レジスタＴ3 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ3 ′に代入し、レジスタＴ1 ′の値とレジスタＴ3 ′との論理和をレジスタＴ5 に代入するステップと、
レジスタＴ0 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ0 ″に代入し、レジスタＴ2 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ2 ″に代入し、レジスタＴ0 ″の値とレジスタＴ2 ″との論理和をレジスタＴ6 に代入するステップと、
レジスタＴ1 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ1 ″に代入し、レジスタＴ3 の値と（２2k−１）との論理積を取ったデータをレジスタＴ3 ″に代入し、レジスタＴ1 ″の値とレジスタＴ3 ″との論理和をレジスタＴ7 に代入するステップと、
レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力するステップと
を有することを特徴とするデータ置換・分割方法。
【請求項２】
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、
各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数２】
0004094758.tif 000008
のように代入するステップと、
レジスタＴ0 の値とレジスタＴ2 の値を各々一方の方向にｋビットローテートするステップと、
レジスタＴ0 とレジスタＴ2 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ4 とするステップと、
レジスタＴ1 とレジスタＴ3 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ5 とするステップと、
レジスタＴ2 とレジスタＴ0 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ6 とするステップと、
レジスタＴ3 とレジスタＴ1 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ7 とするステップと、
レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力するステップと
を有することを特徴とするデータ置換・分割方法。
【請求項３】
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、
各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数３】
0004094758.tif 000009
のように代入する手段と、
レジスタＴ0 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ0 ′に代入し、レジスタＴ2 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ2 ′に代入し、レジスタＴ0 ′の値とレジスタＴ2 ′との論理和をレジスタＴ4 に代入する手段と、
レジスタＴ1 の値と（２2k−１）との論理積を取ったデータをレジスタＴ1 ′に代入し、レジスタＴ3 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ3 ′に代入し、レジスタＴ1 ′の値とレジスタＴ3 ′との論理和をレジスタＴ5 に代入する手段と、
レジスタＴ0 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ0 ″に代入し、レジスタＴ2 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ2 ″に代入し、レジスタＴ0 ″の値とレジスタＴ2 ″との論理和をレジスタＴ6 に代入する手段と、
レジスタＴ1 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ1 ″に代入し、レジスタＴ3 の値と（２2k−１）との論理積を取ったデータをレジスタＴ3 ″に代入し、レジスタＴ1 ″の値とレジスタＴ3 ″との論理和をレジスタＴ7 に代入する手段と、
レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力する手段と
を有することを特徴とするデータ置換・分割装置。
【請求項４】
ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、
各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数４】
0004094758.tif 000010
のように代入する手段と、
レジスタＴ0 の値とレジスタＴ2 の値を各々一方の方向にｋビットローテートする手段と、
レジスタＴ0 とレジスタＴ2 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ4 とする手段と、
レジスタＴ1 とレジスタＴ3 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ5 とする手段と、
レジスタＴ2 とレジスタＴ0 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ6 とする手段と、
レジスタＴ3 とレジスタＴ1 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ7 とする手段と、
レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力する手段と
を有することを特徴とするデータ置換・分割装置。
【請求項５】
前記レジスタＴi とレジスタＴj とを連結し８ｋビット長のレジスタとみなし、一方または他方に２ｋビットシフトした後の一方端または他方端から４ｋビットをレジスタＴk とする手段と、
この手段のうちいくつかを、レジスタＴi の値と（２2k−１）との論理積を取ったデータをレジスタＴi ′に代入し、レジスタＴj の値と（２4k−２2k）との論理積を取ったデータをレジスタＴj ′に代入し、レジスタＴi ′の値とレジスタＴj ′の値との論理和をレジスタＴk に代入する手段と
を有することを特徴とする請求項４記載のデータ置換・分割装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、特に暗号技術の分野で用いられるデータ置換処理および分割処理を効率的に行なうデータ置換・分割方法および装置とデータ置換・分割プログラムを記録した記録媒体に関するものである。
【０００２】
【従来の技術】
従来、データを秘匿するためにデータの暗号化が行われる。このデータの暗号化を行う暗号化技術には、共通鍵暗号方式と公開鍵暗号方式がある。
【０００３】
公開鍵暗号方式ではデータを暗号化する鍵と復号化する鍵が異なっており、通常は暗号化に用いる鍵を一般に公開し、復号化に用いる鍵は利用者が秘密に保持する。公開される暗号化に用いる鍵から復号化に用いる鍵を求めることは、現在の数学的理論および計算機の計算能力をもってしても現実的な時間には完了しないものと信じられている。
【０００４】
一方、共通鍵暗号方式では、データを暗号化する鍵と復号化する鍵とは同一である。高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。ブロック暗号の多くは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｝（０≦ｊ≦３）を
【数５】
0004094758.tif 000002
のように代入するステップと、レジスタＴ0 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ0 ′に代入し、レジスタＴ2 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ2 ′に代入し、レジスタＴ0 ′の値とレジスタＴ2 ′の値との論理和をレジスタＴ4 に代入するステップと、レジスタＴ1 の値と（２2k−１）との論理積を取ったデータをレジスタＴ1 ′に代入し、レジスタＴ3 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ3 ′に代入し、レジスタＴ1 ′の値とレジスタＴ3 ′との論理和をレジスタＴ5 に代入するステップと、レジスタＴ0 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ0 ″に代入し、レジスタＴ2 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ2 ″に代入し、レジスタＴ0 ″の値とレジスタＴ2 ″との論理和をレジスタＴ6 に代入するステップと、レジスタＴ1 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ1 ″に代入し、レジスタＴ3 の値と（２2k−１）との論理積を取ったデータをレジスタＴ3 ″に代入し、レジスタＴ1 ″の値とレジスタＴ3 ″との論理和をレジスタＴ7 に代入するステップと、レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力するステップとを有することを要旨とする。
【００１４】
また、本発明の請求項２記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割方法であって、各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数６】
0004094758.tif 000003
のように代入するステップと、レジスタＴ0 の値とレジスタＴ2 の値を各々一方の方向にｋビットローテートするステップと、レジスタＴ0 とレジスタＴ2 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ4 とするステップと、レジスタＴ1 とレジスタＴ3 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ5 とするステップと、レジスタＴ2 とレジスタＴ0 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ6 とするステップと、レジスタＴ3 とレジスタＴ1 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ7 とするステップと、レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力するステップとを有することを要旨とする。
【００１５】
また、本発明の請求項３記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数７】
0004094758.tif 000004
のように代入する手段と、レジスタＴ0 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ0 ′に代入し、レジスタＴ2 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ2 ′に代入し、レジスタＴ0 ′の値とレジスタＴ2 ′との論理和をレジスタＴ4 に代入する手段と、レジスタＴ1 の値と（２2k−１）との論理積を取ったデータをレジスタＴ1 ′に代入し、レジスタＴ3 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ3 ′に代入し、レジスタＴ1 ′の値とレジスタＴ3 ′との論理和をレジスタＴ5 に代入する手段と、レジスタＴ0 の値と（２4k−２3k＋２k −１）との論理積を取ったデータをレジスタＴ0 ″に代入し、レジスタＴ2 の値と（２3k−２k ）との論理積を取ったデータをレジスタＴ2 ″に代入し、レジスタＴ0 ″の値とレジスタＴ2 ″との論理和をレジスタＴ6 に代入する手段と、レジスタＴ1 の値と（２4k−２2k）との論理積を取ったデータをレジスタＴ1 ″に代入し、レジスタＴ3 の値と（２2k−１）との論理積を取ったデータをレジスタＴ3 ″に代入し、レジスタＴ1 ″の値とレジスタＴ3 ″との論理和をレジスタＴ7 に代入する手段と、レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力する手段とを有することを要旨とする。
【００１６】
また、本発明の請求項４記載の発明は、ｋを整数とし、４ｋビット長のレジスタを具備し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を集合｛ａ4(i+j mod 4)+j｝（０≦ｉ≦１，０≦ｊ≦３）と集合｛ａ4(i+j mod 4)+j｝（２≦ｉ≦３，０≦ｊ≦３）とに置換し分割するデータ置換・分割装置であって、各０≦ｉ≦３において、レジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を
【数８】
0004094758.tif 000005
のように代入する手段と、レジスタＴ0 の値とレジスタＴ2 の値を各々一方の方向にｋビットローテートする手段と、レジスタＴ0 とレジスタＴ2 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ4 とする手段と、レジスタＴ1 とレジスタＴ3 を連結し８ｋビット長のレジスタとみなし、一方に２ｋビットシフトした後の一方端から４ｋビットをレジスタＴ5 とする手段と、レジスタＴ2 とレジスタＴ0 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ6 とする手段と、レジスタＴ3 とレジスタＴ1 を連結し８ｋビット長のレジスタとみなし、他方に２ｋビットシフトした後の他方端から４ｋビットをレジスタＴ7 とする手段と、レジスタＴ4 ，レジスタＴ5 とレジスタＴ6 ，レジスタＴ7 とを２つのグループとして出力する手段とを有することを要旨とする。
【００１７】
また、本発明の請求項５記載の発明は、前記レジスタＴi とレジスタＴj とを連結し８ｋビット長のレジスタとみなし、一方または他方に２ｋビットシフトした後の一方端または他方端から４ｋビットをレジスタＴk とする手段と、この手段のうちいくつかを、レジスタＴi の値と（２2k−１）との論理積を取ったデータをレジスタＴi ′に代入し、レジスタＴj の値と（２4k−２2k）との論理積を取ったデータをレジスタＴj ′に代入し、レジスタＴi ′の値とレジスタＴj ′の値との論理和をレジスタＴk に代入する手段とを有することを要旨とする。
【００２０】
すなわち、本発明では、ｋを整数とし、４ｋビット長のレジスタをレジスタＴi と表し、１６個のｋビットデータ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）をＢＰ関数への入力とし、各０≦ｉ≦３においてレジスタＴi に｛ａ4i+j｝（０≦ｊ≦３）を、
【数９】
0004094758.tif 000006
のように代入する。
【００２１】
以後、この形式で代入されていることを
Ｔi ＝［ａ4i+0  ａ4i+1  ａ4i+2  ａ4i+3］
のように記述する。
【００２２】
ここで集合［Ｌ］と集合［Ｒ］を、
【数１０】
［Ｌ］＝｛ａ4(i+j mod 4)+j｜０≦ｉ≦１，０≦ｊ≦３｝
＝｛ａ0 ，ａ3 ，ａ4 ，ａ5 ，ａ9 ，ａ10，ａ14，ａ15｝
［Ｒ］＝｛ａ4(i+j mod 4)+j｜２≦ｉ≦３，０≦ｊ≦３｝
＝｛ａ1 ，ａ2 ，ａ6 ，ａ7 ，ａ8 ，ａ11，ａ12，ａ13｝
とそれぞれ定義しておく。
【００２３】
レジスタＴ0 とレジスタＴ2 のデータ並びは、両端に集合［Ｌ］または集合  ［Ｒ］に属するデータが配置され、中央の２つに集合［Ｒ］または集合［Ｌ］に属するデータが配置されている。
【００２４】
このままの配置では、シフト命令を用いてのデータの分離は困難であるため、レジスタＴ1 またはレジスタＴ3 のように、一方、例えば右側または他方、すなわち左側に集合［Ｌ］または集合［Ｒ］のデータをまとめる。そのため、まずレジスタＴ0 とレジスタＴ2 を一方方向に、すなわち右周りにｋビットローテートさせる。
【００２５】
結果として以下のようにデータが配置される。
【００２６】
Ｔ0 ＝［ａ3   ａ0   ａ1   ａ2 ］
Ｔ1 ＝［ａ4   ａ5   ａ6   ａ7 ］
Ｔ2 ＝［ａ11  ａ8   ａ9   ａ10］
Ｔ3 ＝［ａ12  ａ13  ａ14  ａ15］
これによりレジスタＴi （０≦ｉ≦１）の上位２ｋビットには集合［Ｌ］に属するデータが配置され、下位２ｋビットには集合［Ｒ］に属するデータが配置される。また、レジスタＴi （２≦ｉ≦３）の上位２ｋビットには集合［Ｒ］に属するデータが配置され、下位２ｋビットには集合［Ｌ］に属するデータが配置される。
【００２７】
次に、レジスタＴ0 とレジスタＴ2 を連結し８ｋビット長のレジスタとみなし、右に２ｋビットシフトした後の右から４ｋビットをレジスタＴ4 とし、レジスタＴ1 とレジスタＴ3 を連結し８ｋビット長のレジスタとみなし、右に２ｋビットシフトした後の右から４ｋビットをレジスタＴ5 とする。
【００２８】
すなわち、
Ｔ4 ＝［ａ1   ａ2   ａ11  ａ8 ］
Ｔ5 ＝［ａ6   ａ7   ａ12  ａ13］
であって、これより、レジスタＴi （４≦ｉ≦５）は集合［Ｒ］に属するデータを過不足なく保持している。
【００２９】
同様に、レジスタＴ2 とレジスタＴ0 を連結し８ｋビット長のレジスタとみなし、左に２ｋビットシフトした後の左から４ｋビットをレジスタＴ6 とし、レジスタＴ3 とレジスタＴ1 を連結し８ｋビット長のレジスタとみなし、左に２ｋビットシフトした後の左から４ｋビットをレジスタＴ7 とする。
【００３０】
すなわち
Ｔ6 ＝［ａ9   ａ10  ａ3   ａ0 ］
Ｔ7 ＝［ａ14  ａ15  ａ4   ａ5 ］
であり、これより、レジスタＴi （６≦ｉ≦７）は集合［Ｌ］に属するデータを過不足なく保持している。
【００３１】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態について説明する。
【００３２】
図１は本発明の一実施の形態に係るデータ置換・分割装置の構成を示すブロック図である。
【００３３】
図１に示すように、制御部１は本実施形態の処理における各処理部および処理器等のコントロールを行なうものである。データ記憶部１１には予め入力データ｛ａ4i+j｝（０≦ｉ≦３，０≦ｊ≦３）を格納し、処理終了時には出力データを格納する。算術演算部１３ではレジスタが具備され、ローテートやシフト処理が行なえる。
【００３４】
図２および図３はＥ２暗号におけるＢＰ関数のデータの置換処理を図示したものである。図２では、出力データの先頭４バイトが置換処理によってどのように構成されているのかを示している。図３では、この処理による集合［Ｌ］の要素を示している。
【００３５】
図４では、本実施形態を実行することによってレジスタＴ6 およびレジスタＴ7 に格納されるデータの並びを示している。図３と比較することによりレジスタＴ6 およびレジスタＴ7 には集合［Ｌ］の要素がすべて含まれており、ＢＰ関数およびFeistel network の左右への振り分けが行なわれていることが判る。
【００３６】
ここで請求項２，５，７に記載のローテートおよびシフトを用いる手法を選択した場合には、レジスタＴ6 およびレジスタＴ7 内のデータ並びは右２バイトと左２バイトが入れ替わる形になる。すなわち、図４で示されているレジスタＴ4 のデータ列［ａ9   ａ10  ａ3   ａ0 ］は［ａ3   ａ0   ａ9   ａ10］となる。しかしながら集合［Ｌ］の要素としては過不足なく、よって目的は達成される。
【００３７】
上述したように、本実施形態により、Ｅ２暗号の仕様において、ＢＰ関数の入出力を左からそれぞれ４バイトずつまとめてレジスタに代入するならば、入力の１つのレジスタにある４バイトは、出力の４つのレジスタに１バイトずつ代入されていることになる。これにより、１つのレジスタに対して演算を行ない、その結果を１つのレジスタに格納するような、ＭＰＵにある多くの命令では、１つの演算命令に対して１バイトしか処理できない。
【００３８】
従って、ＢＰ関数を実装するには１６個の命令が最低限必要となる。実際には、マスク処理や論理和処理などで１６以上の命令が必要である。
【００３９】
なお、レジスタの各バイトを直接入命令に用いた場合には１６命令で済む場合も考えられるが、一部のＭＰＵではその構造上ペナルティが発生し、通常の１６命令分以上の処理時間がかかることが判る。
【００４０】
さらに、入力データを一旦メモリに書き込んだ後に、ＢＰ関数の置換を考慮してバイト単位にデータを読み込む方法もあるが、近年のＭＰＵではメモリへのアクセスにはペナルティが発生する場合が多く、また上記と同様に構造上のペナルティが発生する場合もあり、やはり１６命令分以上の処理時間がかかることが判る。
【００４１】
本実施形態により、Ｅ２暗号のＢＰ部分はローテート命令２つと２つのレジスタを連結したものを右または左にシフトし、右または左の該当データをレジスタに代入する命令４つで構成できる。後半の処理を行なう命令は、例えばIntel 80386 以降のＭＰＵでは標準搭載されている命令であり、その実装には問題がない。従って、既存方法より高速にＢＰ関数を実行できる。
【００４２】
また、具体的にこの命令が実装されていないＭＰＵではマスク命令２つと論理和命令１つで代用することができる。すなわち、ローテート後のレジスタＴ0 とレジスタＴ2 を連結し８ｋビット長のレジスタとみなし、右に２ｋビットシフトした後の右から４ｋビットをレジスタＴ5 とする手段においては、レジスタＴ0 と（２2k−１）との論理積を取ったデータをレジスタＴ0 ′に代入し、レジスタＴ2 と（２4k−２2k）との論理積を取ったデータをレジスタＴ2 ′に代入し、レジスタＴ0 ′とレジスタＴ2 ′との論理和をレジスタＴ4 に代入すればよい。
【００４３】
すなわち、
Ｔ0 ′＝［０  ０  ａ1   ａ2 ］
Ｔ2 ′＝［ａ11  ａ8   ０  ０］
Ｔ4   ＝［ａ11  ａ8   ａ1   ａ2 ］
となる。
【００４４】
この場合でも、ローテート命令２つを合わせて全体で１４命令で記述できるため、既存方法より高速にＢＰ関数を実行できる。
【００４５】
なお、この場合のレジスタＴ4 は、前述のレジスタＴ4 の保持する値と比較すると、上位２つの値と下位２つの値が入れ違いとなっている点が異なる。しかしレジスタＴ4 が保持する値はａ1 ，ａ2 ，ａ8 ，ａ11の４つであることに変わりはなく、従ってレジスタＴ4 とレジスタＴ5 とで集合［Ｒ］の値を過不足なく保持していることが保証される。
【００４６】
以上のように本実施形態は、暗号技術で用いられるデータ置換処理および分割処理に関して、特にＥ２暗号のＢＰ関数部の高速な実装を満足することができる。
【００４７】
また、このようなＥ２暗号のＢＰ関数等におけるデータ置換・分割演算は上述したデータ置換・分割プログラムにより実現され、該プログラムは記録媒体に記録して提供される。このようなデータ置換・分割プログラムが記録された記録媒体を利用して、そのデータ置換・分割プログラムの流通性を高めることができる。
【００４８】
【発明の効果】
以上のように本発明は、共通鍵暗号方式におけるデータ置換処理および分割処理に関し、処理を高速に行い得る等の効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るデータ置換・分割装置の一実施形態の概略の構成を示すブロック図である。
【図２】Ｅ２暗号のＢＰ関数部の置換処理を説明する図である。
【図３】ＢＰ関数の出力データの一部を示した図である。
【図４】レジスタＴ4 とレジスタＴ5 の出力データを示した図である。
【符号の説明】
１  制御部
１１  データ記憶部
１３  算術演算部
１３ａ  レジスタ群
【図１】
0004094758.tif 000011
【図２】
0004094758.tif 000012
【図３】
0004094758.tif 000013
【図４】
0004094758.tif 000014