JP4094758B2 - Data replacement / division method and apparatus - Google Patents

Description

のように代入するステップと、レジスタＴ₀ の値と（２^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）との論理積を取ったデータをレジスタＴ₂ ′に代入し、レジスタＴ₀ ′とレジスタＴ₂ ′との論理和をレジスタＴ₄ に代入すればよい。
【００４３】
すなわち、
Ｔ₀ ′＝［０ ０ ａ₁ ａ₂ ］
Ｔ₂ ′＝［ａ₁₁ ａ₈ ０ ０］
Ｔ₄ ＝［ａ₁₁ ａ₈ ａ₁ ａ₂ ］
となる。
【００４４】
この場合でも、ローテート命令２つを合わせて全体で１４命令で記述できるため、既存方法より高速にＢＰ関数を実行できる。
【００４５】
なお、この場合のレジスタＴ₄ は、前述のレジスタＴ₄ の保持する値と比較すると、上位２つの値と下位２つの値が入れ違いとなっている点が異なる。しかしレジスタＴ₄ が保持する値はａ₁ ，ａ₂ ，ａ₈ ，ａ₁₁の４つであることに変わりはなく、従ってレジスタＴ₄ とレジスタＴ₅ とで集合［Ｒ］の値を過不足なく保持していることが保証される。
【００４６】
以上のように本実施形態は、暗号技術で用いられるデータ置換処理および分割処理に関して、特にＥ２暗号のＢＰ関数部の高速な実装を満足することができる。
【００４７】
また、このようなＥ２暗号のＢＰ関数等におけるデータ置換・分割演算は上述したデータ置換・分割プログラムにより実現され、該プログラムは記録媒体に記録して提供される。このようなデータ置換・分割プログラムが記録された記録媒体を利用して、そのデータ置換・分割プログラムの流通性を高めることができる。
【００４８】
【発明の効果】
以上のように本発明は、共通鍵暗号方式におけるデータ置換処理および分割処理に関し、処理を高速に行い得る等の効果を奏する。
【図面の簡単な説明】
【図１】本発明に係るデータ置換・分割装置の一実施形態の概略の構成を示すブロック図である。
【図２】Ｅ２暗号のＢＰ関数部の置換処理を説明する図である。
【図３】ＢＰ関数の出力データの一部を示した図である。
【図４】レジスタＴ₄ とレジスタＴ₅ の出力データを示した図である。
【符号の説明】
１ 制御部
１１ データ記憶部
１３ 算術演算部
１３ａ レジスタ群[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a data replacement / division method and apparatus for efficiently performing data replacement processing and division processing, particularly used in the field of encryption technology, and a recording medium on which a data replacement / division program is recorded.
[0002]
[Prior art]
Conventionally, data encryption is performed to conceal data. Encryption techniques for encrypting this data include a common key cryptosystem and a public key cryptosystem.
[0003]
In the public key cryptosystem, a key for encrypting data is different from a key for decrypting data. Normally, a key used for encryption is made public, and a key used for decryption is kept secret by the user. It is believed that obtaining a key to be used for decryption from a public key to be used for encryption will not be completed in a realistic time even with the current mathematical theory and computer computing power.
[0004]
On the other hand, in the common key cryptosystem, a key for encrypting data and a key for decrypting data are the same. In order to construct a high-speed and secure common key cipher, a method of dividing data to be encrypted into blocks of an appropriate length and encrypting each block is called a block cipher. Many block ciphers have a structure called Feistel network. In this structure, the 2n-bit input is divided into n bits and distributed to the left and right, the function f is applied to the right n-bit data, the output is exclusive ORed with the left n-bit data, And the same operation is repeated. This structure is shown in “Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, p. 347, 1996”.
[0005]
In addition, the common key cryptosystem requires less computation than the public key cryptosystem, and the amount of data that can be cryptographically processed per unit time is several tens to several hundred times greater. Therefore, the common key cryptosystem tends to be often used in situations where high-speed cryptographic processing is required.
[0006]
The common key cryptosystem requires not only the high speed described above but also its security. In recent years, cryptanalysis methods for several common key encryption algorithms have been proposed. Therefore, newly developed common key algorithms must always be secure against such cryptanalysis. These cryptanalysis methods are described in “Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp. 285-293, 1996”.
[0007]
Methods that make it difficult to apply these cryptanalysis methods have been studied, and it can be expected that the security of the common key encryption algorithm will be enhanced by using these methods. As one of the methods, in order to protect the input data and output data to the underlying encryption algorithm from an attacker, an exclusive OR of a certain value obtained from the encryption key and the input data and output data is performed. There is a method to calculate. This method is described in “Bruce Schneier, Applied Cryptography, 2nd edition, John-Wiley and Sons, pp. 366-367, 1996”. In recent years, many of the proposed common key encryption algorithms are designed using this method.
[0008]
The input data obtained by taking an exclusive OR with a certain value obtained from the encryption key using the above method becomes the input data of the underlying encryption algorithm. When using the Feistel network, it is necessary to divide this input data into left and right. Some recently designed common key encryption algorithms not only divide input data left and right, but also attempt to improve security by dividing input data left and right after performing replacement processing. To do. An example of this is the E2 cipher (see Kanda et al., “Proposal of 128-bit block cipher E2”, IEICE Technical Report ISEC 98-12). In the E2 cipher, a replacement process called a BP function is defined, and then the input data is divided into left and right for the Feistel network.
[0009]
[Problems to be solved by the invention]
However, when this BP function is implemented, the following problems have been pointed out. In other words, the BP function requires byte-by-byte replacement processing, but the word-unit register implemented in recent MPUs requires processing time because it involves mask processing and shift processing, and is copied to the memory once. Even if the replacement process can be performed after that, the time required for memory access increases and the processing time takes longer. This makes it difficult to satisfy the high speed to the common key cryptosystem as described above.
[0010]
The present invention has been made based on such a background, and uses a register in units of words to perform high-speed processing such as replacement with the BP function of E2 encryption and division into left and right in the Feistel network. In the E2 cipher, since the basic cryptographic processing unit performs processing in units of bytes, for example, the arrangement of data on the right side does not necessarily conform to the specification. That is, the internal implementation of the cryptographic processing unit may correspond to the changed byte string.
[0011]
Furthermore, in the present invention, a set of bytes that are divided to the left and right after the replacement processing is correctly divided into a set to the left and right, although in a column order different from the specification. In recent MPUs, two built-in registers are concatenated and virtually regarded as one register, and an instruction to perform shift processing and store upper or lower data in the register may be implemented. It is even more effective if a simple device is available.
[0012]
That is, an object of the present invention is to provide a data replacement / division method and apparatus capable of performing high-speed processing in the common key cryptosystem and a recording medium on which the data replacement / division program is recorded.
[0013]
[Means for Solving the Problems]
In order to achieve the above-mentioned object, the invention according to claim 1 of the present invention is such that k is an integer, a register of 4 kbit length is provided, and 16 kbit data {a _{4i + j} } (0 .Ltoreq.i.ltoreq.3, 0.ltoreq.j.ltoreq.3) and set {a.sub.4 _{(i + j mod 4) + j} } (0.ltoreq.i.ltoreq.1, 0.ltoreq.j.ltoreq.3) and set {a.sub.4 _{(i + j mod 4). ) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3) is a data replacement / division method for dividing and substituting {a _{4i + j} } in register T _i for each 0 ≦ i ≦ 3 (0 ≦ j ≦ 3) [number 5] the

And the data obtained by ANDing the value of the register T ₀ and (2 ^3k −2 ^k ) is substituted into the register T ₀ ′, and the value of the register T ₂ and (2 ^4k −2 ^3k Substituting data obtained by ANDing with +2 ^k −1) into the register T ₂ ′, substituting the logical sum of the value of the register T ₀ ′ and the value of the register T ₂ ′ into the register T ₄ , Data obtained by logical product of the value of T ₁ and (2 ^2k −1) is substituted into the register T ₁ ′, and data obtained by logical product of the value of the register T ₃ and (2 ^4k −2 ^2k ) is obtained. Substituting into the register T ₃ ′, substituting the logical sum of the value of the register T ₁ ′ and the register T ₃ ′ into the register T ₅ , and the value of the register T ₀ (2 ^4k −2 ^3k +2 ^k −1) The data obtained by ANDing is substituted into the register T ₀ ″, and the logical product of the value of the register T ₂ and (2 ^3k −2 ^k ) is calculated. The Tsu data "is substituted into the register T _0" register T ₂ comprising the steps of substituting the logical sum of the values and registers T ₂ "of the register T _6, the value of the register T ₁ (2 ^4k -2 ^2k) the data ANDing "is substituted into the data by taking the logical product of the value of the register T ₃ and the (2 ^2k -1) register T _3" register T ₁ of the and substituted into the register T ₁ " And substituting the logical sum of the value of T and the register T ₃ ″ into the register T ₇ , and outputting the register T ₄ , the register T ₅ , the register T ₆ , and the register T ₇ as two groups. The gist.
[0014]
According to the second aspect of the present invention, k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦) 3) into the set {a _{4 (i + j mod 4) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and the set {a _{4 (i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3), and a data replacement / division method in which {a _{4i + j} } (0 ≦ j ≦ 3) is _assigned to the register T _i for each 0 ≦ i ≦ 3. Equation 6]

Considers the steps to assign as the steps of k-bit rotation in each one direction the values of the register T ₂ of the register T _0, connecting the register T ₀ and the register T ₂ and register 8k bits long, steps and, regarded as the register T ₁ and connecting the register T ₃ 8k bit length of the register, one end after 2k bits shifted while the 4k bit registers T ₄ from one end after 2k bits shifted Meanwhile the step of the steps of a 4k-bit registers T _5, regarded as the register T ₂ and the register T ₀ connecting the 8k bit length of the register, a 4k-bit registers T ₆ from the other end after 2k bit shifted to the other from If, regarded as the register T ₃ and the register T ₁ connects the 8k bit length of the register, 4k bits from the other end after 2k bit shifted to the other The method comprising the register T _7, register T _4, register T ₅ and the register T _6, and summarized in that a step of outputting a register T ₇ as two groups.
[0015]
According to a third aspect of the present invention, k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦) 3) into the set {a _{4 (i + j mod 4) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and the set {a _{4 (i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3), and replaces and divides the data into a register T _i with {a _{4i + j} } (0 ≦ j ≦ 3) in each 0 ≦ i ≦ 3. Equation 7]

And the data obtained by ANDing the value of the register T _{0 and} the value of the register T ₀ and (2 ^3k −2 ^k ) is substituted into the register T ₀ ′, and the value of the register T ₂ and (2 ^4k −2 ^3k And a means for substituting the logical product of +2 ^k −1) into the register T ₂ ′, substituting the logical sum of the value of the register T ₀ ′ and the register T ₂ ′ into the register T ₄ , and the register T ₁ The data obtained by ANDing the value of and the value of (2 ^2k −1) is substituted into the register T ₁ ′, and the data obtained by calculating the logical product of the value of the register T ₃ and (2 ^4k −2 ^2k ) ₃ 'and the means for substituting the logical sum of the value of the register T ₁ ' and the register T ₃ 'into the register T ₅ and the value of the register T ₀ and (2 ^4k -2 ^3k +2 ^k -1) The data obtained by the logical product is substituted into the register T ₀ ″, and the data obtained by ^performing the logical product of the value of the register T ₂ and (2 ^3k −2 ^k ) is registered. "Substituted into the register T _0" Star T ₂ logical product means for substituting the logical sum of the values and registers T ₂ "of the register T _6, the value of the register T ₁ and (2 ^4k -2 ^2k) "substituted, the data obtained by ANDing the value of the register T ₃ and the (2 ^2k -1) register T _3" register T ₁ data took substituted into the value a register of the register T ₁ " The gist is to have means for substituting the logical sum of T ₃ ″ into the register T ₇ and means for outputting the registers T ₄ , T ₅ , T ₆ , and T ₇ as two groups.
[0016]
According to a fourth aspect of the present invention, k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦) 3) into the set {a _{4 (i + j mod 4) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and the set {a _{4 (i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3), and replaces and divides the data into a register T _i with {a _{4i + j} } (0 ≦ j ≦ 3) in each 0 ≦ i ≦ 3. (Equation 8)

A means for substituting, a means for rotating the value of the register T _{0 and} the value of the register T ₂ in one direction, respectively, and a register T ₀ and the register T ₂ are concatenated and regarded as an 8 k-bit register. Meanwhile means for the 4k bit registers T ₄ from one end after 2k bits shifted, regarded as the register T ₁ and the register T ₃ connected 8k bit length of the register, one end after 2k bits shifted one It means for the 4k bit registers T ₅ from deemed register T ₂ and the register T ₀ connecting the 8k bit length of the register, means for the 4k bit registers T ₆ from the other end after 2k bit shifted to the other The register T ₃ and the register T ₁ are concatenated to be regarded as an 8 k-bit register, and after shifting by 2 k bits to the other, 4 k bits from the other end are used as the register T _7. The gist is to have a stage and means for outputting the registers T ₄ , T ₅ , T ₆ and T ₇ as two groups.
[0017]
In the invention according to claim 5 of the present invention, the register T _i and the register T _j are concatenated to be regarded as an 8 k-bit register, and 4 k from one end or the other end after being shifted to one or the other by 2 k bits. A means for setting a bit as a register T _k, and some of these means are assigned to a register T _i ′ by substituting data obtained by ANDing the value of the register T _i with (2 ^2k −1), and register T _j ^Is obtained by substituting the data obtained by the logical product of the value of and the value of (2 ^4k -2 ^2k ) into the register T _j ′ and substituting the logical sum of the value of the register T _i ′ and the value of the register T _j ′ into the register T _k . It has a gist to have.
[0020]
That is, in the present invention, k is an integer, a 4 k-bit register is represented as a register T _i, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦ 3) is represented by BP. The input to the function is {a _{4i + j} } (0 ≦ j ≦ 3) in the register T _i for each 0 ≦ i ≦ 3.
[Equation 9]

Substitute as follows.
[0021]
Hereinafter, T _i = [a _{4i + 0} a _{4i + 1} a _{4i + 2} a _{4i + 3} ] is assigned in this form.
Write like this.
[0022]
Here, the set [L] and the set [R] are
[Expression 10 ]
[L] = {a _{4 (i + j mod 4) + j} | 0 ≦ i ≦ 1, 0 ≦ j ≦ 3}
_{= {A 0, a 3,} a 4, a 5, a 9, a 10, a 14, a 15}
[R] = {a _{4 (i + j mod 4) + j} | 2 ≦ i ≦ 3, 0 ≦ j ≦ 3}
_{= {A 1, a 2,} a 6, a 7, a 8, a 11, a 12, a 13}
And define them respectively.
[0023]
In the data arrangement of the register T ₀ and the register T ₂ , data belonging to the set [L] or the set [R] is arranged at both ends, and data belonging to the set [R] or the set [L] is arranged in the center two. ing.
[0024]
In this arrangement, since it is difficult to separate data using a shift instruction, the set [L] or the set [R] on one side, for example, the right side or the other side, that is, the left side, like the register T ₁ or the register T ₃ . Summarize the data. Therefore, first, the register T ₀ and the register T ₂ are rotated k bits in one direction, that is, clockwise.
[0025]
As a result, data is arranged as follows.
[0026]
T ₀ = [a ₃ a ₀ a ₁ a ₂ ]
T ₁ = [a ₄ a ₅ a ₆ a ₇ ]
T ₂ = [a ₁₁ a ₈ a ₉ a ₁₀ ]
T ₃ = [a ₁₂ a ₁₃ a ₁₄ a ₁₅ ]
Thus, data belonging to the set [L] is arranged in the upper 2k bits of the register T _i (0 ≦ i ≦ 1), and data belonging to the set [R] is arranged in the lower 2k bits. Further, data belonging to the set [R] is arranged in the upper 2k bits of the register T _i (2 ≦ i ≦ 3), and data belonging to the set [L] is arranged in the lower 2k bits.
[0027]
Next, register T ₀ and register T ₂ are concatenated and regarded as an 8 k-bit register, and after shifting 2 k bits to the right, 4 k bits from the right are used as register T _4, and registers T ₁ and T ₃ are concatenated to 8 k. It is regarded as a register having a bit length, and 4 k bits from the right after shifting to the right by 2 k bits are set as a register T ₅ .
[0028]
That is,
T ₄ = [a ₁ a ₂ a ₁₁ a ₈ ]
T ₅ = [a ₆ a ₇ a ₁₂ a ₁₃ ]
Thus, the register T _i (4 ≦ i ≦ 5) holds the data belonging to the set [R] without excess or deficiency.
[0029]
Similarly, register T ₂ and register T ₀ are concatenated and regarded as an 8 k-bit register, and after shifting 2 k bits to the left, 4 k bits from the left are set as register T _6, and registers T ₃ and T ₁ are concatenated to 8 k. It is regarded as a register having a bit length, and 4 k bits from the left after shifting 2 k bits to the left are set as a register T ₇ .
[0030]
That is, T ₆ = [a ₉ a ₁₀ a ₃ a ₀ ]
T ₇ = [a ₁₄ a ₁₅ a ₄ a ₅ ]
Thus, the register T _i (6 ≦ i ≦ 7) holds the data belonging to the set [L] without excess or deficiency.
[0031]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[0032]
FIG. 1 is a block diagram showing a configuration of a data replacement / division apparatus according to an embodiment of the present invention.
[0033]
As shown in FIG. 1, the control unit 1 controls each processing unit and processor in the processing of the present embodiment. The data storage unit 11 stores input data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦ 3) in advance, and stores output data at the end of processing. The arithmetic operation unit 13 includes a register and can perform rotation and shift processing.
[0034]
2 and 3 illustrate the BP function data replacement process in the E2 cipher. FIG. 2 shows how the first 4 bytes of the output data are configured by the replacement process. FIG. 3 shows elements of the set [L] by this processing.
[0035]
FIG. 4 shows an arrangement of data stored in the register T ₆ and the register T ₇ by executing this embodiment. By comparing with FIG. 3, it can be seen that the register T ₆ and the register T ₇ include all elements of the set [L], and the BP function and the Feistel network are distributed to the left and right.
[0036]
Here, when the method using the rotation and shift described in claims 2, 5, and 7 is selected, the right 2 bytes and the left 2 bytes are interchanged in the data arrangement in the registers T ₆ and T ₇ . That is, the data string of the register T ₄ shown in FIG. _{4 [a 9 a 10 a 3} a 0] becomes _{[a 3 a 0 a 9 a} 10]. However, there are no excess or deficiency as elements of the set [L], and the object is achieved.
[0037]
As described above, according to this embodiment, in the E2 cipher specification, if 4 bytes each of input and output of the BP function are collectively assigned to the register, 4 bytes in one input register are output. One byte is assigned to each of the four registers. Thus, many instructions in the MPU that perform an operation on one register and store the result in one register can process only one byte for one operation instruction.
[0038]
Therefore, a minimum of 16 instructions are required to implement the BP function. Actually, 16 or more instructions are required for mask processing or logical sum processing.
[0039]
If each byte of the register is used as a direct input instruction, 16 instructions may be sufficient. However, some MPUs have a penalty due to their structure, and processing time longer than the normal 16 instructions is required. I understand that.
[0040]
In addition, there is a method of reading input data in bytes after the input data is once written in the memory, considering the replacement of the BP function. However, in recent MPUs, there is often a penalty for accessing the memory. Similar to the above, a structural penalty may occur, and it is understood that a processing time of 16 instructions or more is required.
[0041]
According to the present embodiment, the BP portion of the E2 cipher can be composed of four instructions that shift two or more rotate instructions and two registers connected to the right or left and assign the right or left corresponding data to the registers. The instruction for performing the latter half of the process is, for example, a standard instruction in an MPU after Intel 80386, and there is no problem in its implementation. Therefore, the BP function can be executed faster than the existing method.
[0042]
Also, in an MPU in which this instruction is not specifically implemented, two mask instructions and one OR instruction can be substituted. That is, connecting the register T ₀ and the register T ₂ of the post-rotation deemed register 8k bits long, right after 2k-bit shift to the right in the means for the 4k bits register T _5, the register T ₀ ( The data obtained by ANDing 2 ^2k −1) is assigned to register T ₀ ′, and the data obtained by ANDing register T ₂ and (2 ^4k −2 ^2k ) is assigned to register T ₂ ′. A logical sum of the register T ₀ ′ and the register T ₂ ′ may be substituted into the register T ₄ .
[0043]
That is,
T ₀ ′ = [0 0 a ₁ a ₂ ]
T ₂ ′ = [a ₁₁ a ₈ 0 0]
T ₄ = [a ₁₁ a ₈ a ₁ a ₂ ]
It becomes.
[0044]
Even in this case, since two rotate instructions can be combined and described in a total of 14 instructions, the BP function can be executed faster than the existing method.
[0045]
In this case, the register T ₄ is different from the value held by the register T ₄ in that the upper two values and the lower two values are misplaced. However, the value held by the register T ₄ is still _four, a ₁ , a ₂ , a ₈ , and a ₁₁ , and therefore the set [R] is excessive or insufficient between the register T ₄ and the register T _5. Is guaranteed to hold
[0046]
As described above, the present embodiment can satisfy the high-speed mounting of the BP function part of the E2 cipher particularly with respect to the data replacement process and the division process used in the cryptographic technique.
[0047]
Further, such data replacement / division calculation in the E2 encryption BP function or the like is realized by the above-described data replacement / division program, which is provided by being recorded on a recording medium. By using a recording medium in which such a data replacement / division program is recorded, it is possible to improve the distribution of the data replacement / division program.
[0048]
【The invention's effect】
As described above, the present invention has effects such as high-speed processing regarding the data replacement processing and the division processing in the common key cryptosystem.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a schematic configuration of an embodiment of a data replacement / division apparatus according to the present invention.
FIG. 2 is a diagram illustrating a replacement process of a BP function part of E2 encryption.
FIG. 3 is a diagram showing a part of output data of a BP function.
FIG. 4 is a diagram showing output data of a register T ₄ and a register T ₅ .
[Explanation of symbols]
1 Control Unit 11 Data Storage Unit 13 Arithmetic Operation Unit 13a Register Group

Claims (5)

k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦ 3) is set {a _{4 (i + j mod 4 ) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and set {a4 _{(i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3) A data replacement / division method for
At each 0 ≦ i ≦ 3, {a _{4i + j} } (0 ≦ j ≦ 3) is _stored in the register T _i.

The step of substituting
Data obtained by ANDing the value of the register T ₀ and (2 ^3k −2 ^k ) is substituted into the register T ₀ ′, and the logic of the value of the register T ₂ and (2 ^4k −2 ^3k +2 ^k −1) is assigned. Substituting the product data into register T ₂ 'and substituting the logical sum of the value of register T ₀ ' and the value of register T ₂ 'into register T ₄ ;
Data obtained by ANDing the value of the register T ₁ and (2 ^2k −1) is substituted into the register T ₁ ′, and data obtained by calculating the logical product of the value of the register T ₃ and (2 ^4k −2 ^2k ). Substituting into the register T ₃ ′, and substituting the logical sum of the value of the register T ₁ ′ and the register T ₃ ′ into the register T ₅ ;
Data obtained by ANDing the value of the register T ₀ and (2 ^4k −2 ^3k +2 ^k −1) is substituted into the register T ₀ ″, and the logic of the value of the register T ₂ and (2 ^3k −2 ^k ) Substituting the product data into register T ₂ ″ and substituting the logical sum of the value of register T ₀ ″ and register T ₂ ″ into register T ₆ ;
Data obtained by ANDing the value of the register T ₁ and (2 ^4k −2 ^2k ) is assigned to the register T ₁ ″, and data obtained by calculating the logical product of the value of the register T ₃ and (2 ^2k −1). Substituting into register T ₃ ″ and substituting the logical sum of the value of register T ₁ ″ and register T ₃ ″ into register T ₇ ;
A data replacement / division method comprising: a step of outputting the register T ₄ , the register T ₅ and the register T ₆ , and the register T ₇ as two groups. k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦ 3) is set {a _{4 (i + j mod 4 ) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and set {a4 _{(i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3) A data replacement / division method for
At each 0 ≦ i ≦ 3, {a _{4i + j} } (0 ≦ j ≦ 3) is _stored in the register T _i.

The step of substituting
Rotating the value of register T _{0 and} the value of register T ₂ by k bits each in one direction;
Register T ₀ and register T ₂ are regarded as a register of 8 k bits length, and after shifting by 2 k bits to one, 4 k bits from one end are set as register T ₄ ;
Register T ₁ and register T ₃ are concatenated and regarded as an 8 k-bit register, and after shifting 2 k bits to one, set 4 k bits from one end to register T ₅ ;
Concatenating the register T ₂ and the register T ₀ to be regarded as an 8 k-bit register, and shifting the other 2 k bits to 4 k bits from the other end to make the register T ₆ ;
Concatenating register T ₃ and register T ₁ and assuming that the register is 8 k bits long, shifting 2 k bits to the other, and setting 4 k bits from the other end to register T ₇ ;
A data replacement / division method comprising: a step of outputting the register T ₄ , the register T ₅ and the register T ₆ , and the register T ₇ as two groups. k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦ 3) is set {a _{4 (i + j mod 4 ) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and set {a4 _{(i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3) A data replacement / splitting device that performs
At each 0 ≦ i ≦ 3, {a _{4i + j} } (0 ≦ j ≦ 3) is _stored in the register T _i.

Means to assign like
Data obtained by ANDing the value of the register T ₀ and (2 ^3k −2 ^k ) is substituted into the register T ₀ ′, and the logic of the value of the register T ₂ and (2 ^4k −2 ^3k +2 ^k −1) is assigned. Means for substituting the product data into the register T ₂ ′ and substituting the logical sum of the value of the register T ₀ ′ and the register T ₂ ′ into the register T ₄ ;
Data obtained by ANDing the value of the register T ₁ and (2 ^2k −1) is substituted into the register T ₁ ′, and data obtained by calculating the logical product of the value of the register T ₃ and (2 ^4k −2 ^2k ). means' substituted into the register T ₁ 'register T ₃ substitutes a logical OR between the value and the register T _3' of the register T ₅ a,
Data obtained by ANDing the value of the register T ₀ and (2 ^4k −2 ^3k +2 ^k −1) is substituted into the register T ₀ ″, and the logic of the value of the register T ₂ and (2 ^3k −2 ^k ) Means for substituting the product data into register T ₂ ″ and substituting the logical sum of the value of register T ₀ ″ and register T ₂ ″ into register T ₆ ;
Data obtained by ANDing the value of the register T ₁ and (2 ^4k −2 ^2k ) is assigned to the register T ₁ ″, and data obtained by calculating the logical product of the value of the register T ₃ and (2 ^2k −1). means "substituted into the register T _1" register T ₃ substitutes a logical OR between the value and the register T ₃ "in the register T ₇ and
A data replacing / dividing device comprising: a register T ₄ , a register T ₅ and a register T ₆ , and a means for outputting the register T ₇ as two groups. k is an integer, a 4 k-bit register is provided, and 16 k-bit data {a _{4i + j} } (0 ≦ i ≦ 3, 0 ≦ j ≦ 3) is set {a _{4 (i + j mod 4 ) + j} } (0 ≦ i ≦ 1, 0 ≦ j ≦ 3) and set {a4 _{(i + j mod 4) + j} } (2 ≦ i ≦ 3, 0 ≦ j ≦ 3) A data replacement / splitting device that performs
At each 0 ≦ i ≦ 3, {a _{4i + j} } (0 ≦ j ≦ 3) is _stored in the register T _i.

Means to assign like
Means for rotating the value of register T _{0 and} the value of register T ₂ in one direction each by k bits;
Means for concatenating the register T ₀ and the register T ₂ to be regarded as an 8 k-bit register, shifting 4 k bits to one and setting ₄ k bits from one end to the register T ₄ ;
Means for concatenating the register T ₁ and the register T ₃ to be regarded as a register of 8 k bits and shifting the register ₁ to 2 k bits to 4 k bits from one end of the register T ₅ as a register T ₅ ;
Means for concatenating the register T ₂ and the register T ₀ and assuming that the register is 8 k bits long and shifting the other end by 2 k bits to set 4 k bits from the other end to the register T ₆ ;
Means for concatenating register T ₃ and register T ₁ to be regarded as an 8 k-bit register, shifting 4 k bits to the other, and setting 4 k bits from the other end to register T ₇ ;
A data replacing / dividing device comprising: a register T ₄ , a register T ₅ and a register T ₆ , and a means for outputting the register T ₇ as two groups. Means for concatenating the register T _i and the register T _j to be regarded as an 8 k-bit register, shifting 4 k bits to one or the other and shifting 4 k bits from one end or the other end to the register T _k ;
For some of these means, data obtained by ANDing the value of the register T _i and (2 ^2k −1) is substituted into the register T _i ′, and the value of the register T _j and (2 ^4k −2 ^2k ) the data ANDing 'is substituted into the register T _i' register T _j between, characterized in that the logical sum of the values of the register T _j 'of and a means for substituting in the register T _k The data replacement / division apparatus according to claim 4.

Images