JP3736731B2 - 置換処理装置およびそのプログラム記録媒体 - Google Patents
置換処理装置およびそのプログラム記録媒体 Download PDFInfo
- Publication number
- JP3736731B2 JP3736731B2 JP2000044529A JP2000044529A JP3736731B2 JP 3736731 B2 JP3736731 B2 JP 3736731B2 JP 2000044529 A JP2000044529 A JP 2000044529A JP 2000044529 A JP2000044529 A JP 2000044529A JP 3736731 B2 JP3736731 B2 JP 3736731B2
- Authority
- JP
- Japan
- Prior art keywords
- exclusive
- result
- rotation
- byte
- output
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Lifetime
Links
Images
Landscapes
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Description
【０００１】
【発明の属する技術分野】
この発明は、主に暗号技術で用いられ、特に、秘密鍵の制御のもとでデータをブロック単位で暗号化または復号を行う共通鍵暗号方式に用いられ、第一の非線形変換Ｓ−線形変換Ｐ−第二の非線形変換Ｓが行われる装置または非線形変換Ｓ−線形変換Ｐが行われる装置に適する置換処理装置に関する。
【０００２】
【従来の技術】
データを秘匿するためには暗号化技術が有効である。暗号化の方式には共通鍵暗号と公開鍵暗号があり、暗号化と復号で同一の秘密鍵を用いる方式を共通鍵暗号、暗号化と復号とで異なる鍵を用いる方式を公開鍵暗号と呼ぶ。処理速度の観点からは共通鍵暗号の方が有利である。
高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。このような暗号方式の一方式として、Ｓ−Ｐ−Ｓ構造を利用して置換処理における安全性を高めたＥ２暗号（例えば、文献「神田ら：“１２８ビットブロック暗号Ｅ２の提案”、電子情報通信学会情報セキュリティ研究会ＩＳＥＣ９８−１２」）がある。
【０００３】
図１６はＥ２暗号で利用されている置換処理を表したものである。このなかのＰ関数処理は、第１のＳ関数処理と合わせて、行列表現ｚ′＝Ｐ・ｚ＝Ｐ・ｓ（ｘ）として、
【０００４】
【数２４】
のように表され、
【０００５】
【数２５】
【０００６】
という処理が行われる。ここで、ｓ（ｘ）はｘを入力として第１のＳ関数を構成するｓ−ｂｏｘによる非線形変換された値を表している。
この第１のＳ関数処理と｛０，１｝要素からなる行列Ｐで表現される置換処理（Ｐ関数処理）との合成処理に対する高速な実現方法はいくつか考えられており、例えば文献「青木ら：“Ｅ２のソフトウェァ実装、”１９９９年暗号と情報セキュリティシンポジウムＳＣＩＳ９９−Ｆ１−２．２」にその実現方法が記載されている。
例えば、３２ビットプロセッサー上での実装例として、以下の４個の３２ビット参照テーブル
【０００７】
【数２６】
を準備した時、上記のＳ関数処理とＰ関数処理の合成処理は以下のように書き直すことができる。
【０００８】
【数２７】
【０００９】
ここで、＞＞ｙは下ｙバイトの論理シフト、＜＜ｙは上ｙバイトの論理シフトである。上記行列中の縦線、横線は左辺の行列Ｐ・Ｓ（ｘ）と右辺のＳ１（・）〜Ｓ４（・）よりなる行列との関係を分かり易くするために記入したものであって特別の意味はない。
このとき、図１７に示すように、第１のＳ関数処理とＰ関数処理との合成処理では、ｘのあらゆる値に対して参照可能なテーブルＳ１（・）〜Ｓ４（・）、つまり４ＫＢのメモリ（Ｓ１（・）〜Ｓ４（・）のテーブルは各々１ＫＢのメモリが必要）を使用し、演算処理としてはｘ1〜ｘ8によるテーブル参照８回、排他的論理和１１回、シフト演算４回を必要とする。また、この文献中には特に記載されていないが、実際の実装においては、これらの演算処理の他に途中データのメモリ退避が１回必要となることに注意されたい。
別の実装例では、上記のＳ１（・）〜Ｓ４（・）のテーブルの他に以下の４個の３２ビット参照テーブル
【００１０】
【数２８】
を準備することにより、上記の置換処理は以下のように書き直すことができる。
【００１１】
【数２９】
【００１２】
このとき、第１のＳ関数処理とＰ関数処理との合成処理では、８ＫＢのメモリ（Ｓ１（・）〜Ｓ８（・）のテーブルは各々１ＫＢのメモリが必要）を使用し、演算処理としては図１８に示すようにテーブル参照１２回、排他的論理和１１回を必要とする。
以上説明したように、Ｅ２暗号で利用されている第１のＳ関数処理とＰ関数処理との合成処理での高速実装方法は、メモリを４〜８ＫＢも利用しているわりにはテーブル参照、排他的論理和、シフト演算などの処理量が大きく、必ずしも高速なものであるとはいえない。そのうえ、メモリ使用量に制限があるとき、さらに処理量が急増すると予想される。
【００１３】
【発明が解決しようとする課題】
この発明の目的は、少なくともＳ−Ｐ構造を有する置換処理において、実装の多様性を持たせたＰ関数を実現することによって、置換処理での安全性を同じにしながら、様々な実装環境に応じた最適な実装、特に、Ｓ関数処理と、｛０，１｝要素からなる行列Ｐで表現される置換処理（Ｐ関数処理）との合成処理における高速実装を可能とするような置換処理装置を提供することを目的とする。
【００１４】
【課題を解決するための手段】
この発明では、上記の目的を達成するための置換処理装置において、Ｓ関数処理（非線形変換処理）と、行列Ｐで表現される置換処理（Ｐ関数処理：線形変換処理）との合成処理を以下のように書き直すことが可能となるような構造にすることによって、様々な実装環境に応じた柔軟な高速実装が可能となる。
【００１５】
【数３０】
【００１６】
ここで、＜＜＜ｙは上にｙバイトのローテーション、Ｓ１（・）〜Ｓ８（・）のテーブルは参照テーブルを表す。なお、ｙ＜０のときは下に｜ｙ｜バイトローテーションを表すものとする。
【００１７】
【作用】
この発明によれば、Ｓ関数処理と、行列Ｐで表現される置換処理（Ｐ関数処理）との合成処理における高速実装方法として少なくとも、（１）８ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和８回、ローテーション１回の演算処理、（２）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１０回、ローテーション４回または５回の演算処理、（３）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、の３種類を実現することができる。なお、（２）の実装方法のときには、４ＫＢのメモリを使用したテーブル参照の代わりに、２５６Ｂのメモリを使用したテーブル参照と６回のシフト演算によっても実現可能であり、このときテーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回または５回の演算処理となる。また、特に｛Ｓ１（・），Ｓ２（・），Ｓ３（・），Ｓ４（・）｝＝｛Ｓ５（・），Ｓ６（・），Ｓ７（・），Ｓ８（・）｝を満たすのであれば、（１）の実装方法の時にはさらに４ＫＢのメモリ使用量を削減可能であり、使用メモリは４ＫＢとなる（他の演算処理量は変化しない）。
【００１８】
これによって、Ｅ２暗号で使われていた置換処理よりも高速で、かつ柔軟な実装が可能となる置換処理装置を提供できる。さらに、合成処理そのものは同じでありながら、（１）の実装方法はＰＣ向き、（２）は３２ビットＣＰＵを備えたハイエンドＩＣカード向き、（３）は８ビットＣＰＵを備えたローエンドＩＣカード向きというように多様な実装環境に応じて最適かつ柔軟な実装が可能となる。
【００１９】
【発明の実施の形態】
実施例１
以下、この発明の実施例１を、図面を用いて説明する。
図１は、この発明の実施例１を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００２０】
【数３１】
という処理が行なわれ、行列表現ｚ′＝Ｐ・ｚ＝Ｐ・ｓ（ｘ）として、
【００２１】
【数３２】
のように表される。これは、
【００２２】
【数３３】
とすると、
【００２３】
【数３４】
であるから、
【００２４】
【数３５】
【００２５】
と表すことができる。
まず、４ＫＢのテーブルを利用したときの実装法について述べる。ここで用意するテーブルは以下の３２ビット参照テーブルの４個であり、各テーブルが１ＫＢのメモリ量を使用する。
【００２６】
【数３６】
上記のＳ関数処理とＰ関数処理との合成処理は以下のように書き換えることができる。
【００２７】
【数３７】
【００２８】
したがって、このような処理を行う処理図は図２に示すようになる。つまりｘ1，ｘ2，ｘ3，ｘ4でそれぞれテーブルＳ１，Ｓ２，Ｓ３，Ｓ４を参照してＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）を求め、これらの排他的論理和を回路１１，１２，１３で求め、またｘ5，ｘ6，ｘ7，ｘ8でそれぞれテーブルＳ２，Ｓ３，Ｓ４，Ｓ１を参照してＳ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）を求め、これらの排他的論理和を回路１４，１５，１６により求め、この排他的論理和演算結果Ｕ2と前記排他的論理和演算結果Ｕ1との排他的論理和が回路１７でとられてｚ1′，ｚ2′，ｚ3′，ｚ4′として出力され、また回路１６よりの排他的論理和演算結果Ｕ2に対し、上１バイトローテーションが回路１８で行われ、回路１７の出力と回路１９で排他的論理和演算が行われてｚ5′，ｚ6′，ｚ7′，ｚ8′が得られる。
【００２９】
この変換処理はコンピュータにより行わせることもできる。例えば、図３に示すように、ＣＰＵよりなる制御部２１はプログラムメモリ２２に格納されたプログラムを読出し、解読実行し、図４に示す処理を行う。つまり入力部２３を通じてデータｘ1〜ｘ8を取込んで記憶部２４に一時記憶し（ステップ１）、その各データｘ1〜ｘ8を順次取出して、テーブルメモリ２５内の対応するテーブルを参照し（ステップ２）、参照結果を記憶部２４に一時格納する（ステップ３）。つまりこの例では参照結果Ｓ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4），Ｓ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）が記憶部２４に格納される。
【００３０】
記憶部２４からＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）を取出し、これらの排他的論理和演算を制御部２１の演算部２６で行い（ステップ４）、その演算結果Ｕ1を記憶部２４に一時格納し、また記憶部２４からＳ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）を取出し、演算部２６でこれらの排他的論理和演算を行い（ステップ５）、その演算結果Ｕ2と、前記演算結果Ｕ1との排他的論理和演算を演算部２６で行う（ステップ６−１）と共に、制御部２１のローテーション部２７で演算結果Ｕ2に対し、下１バイトローテーションを行い（ステップ６−２）、このローテーションの結果とステップ６の排他的論理和演算の結果との排他的論理和演算を演算部２６で行う（ステップ７）。このステップ４の演算結果Ｕ1をｚ1′，ｚ2′，ｚ3′，ｚ4′として、またステップ８の演算結果をｚ5′，ｚ6′，ｚ7′，ｚ8′として出力部２８より出力する（ステップ８）。
【００３１】
以上の置換処理ではテーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、ローテーション回路１８への入力が別の排他的論理和回路１７への（一方の）入力となっている場合にはそのローテーションと排他的論理和は並列処理が可能である。故に、図２中の点線部の処理は並列処理を考慮すると２演算で処理が完了する。
次に、もう１つの４ＫＢメモリを利用したときの実装法について述べる。ここで用意するテーブルは以下の３２ビット参照テーブルの４個であり、各テーブルが１ＫＢのメモリ量を使用する。
【００３２】
【数３８】
このとき、第１のＳ関数処理とＰ関数処理との合成処理は以下のように書き換えることができる。
【００３３】
【数３９】
【００３４】
したがって、このような処理を行う処理は図５のようになる。つまり入力データｘ1，ｘ2，ｘ3，ｘ4でテーブルＳ６，Ｓ７，Ｓ８，Ｓ５がそれぞれ参照してＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）が出力され、これらは回路３１，３２，３３により排他的論理和演算が行われ、その演算結果Ａが回路３３から出力される。また入力データｘ5，ｘ6，ｘ7，ｘ8によりテーブルＳ５，Ｓ６，Ｓ７，Ｓ８がそれぞれ参照され、Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）が出力され、これらが回路３４，３５，３６により排他的論理和演算が行われ、その演算結果Ｂが回路３６から出力される。演算結果Ａは回路３７により下に１バイトローテーションされると共に回路３８で演算結果Ｂと排他的論理和演算される。この演算結果Ｃは回路３９により上に１バイトローテーションされると共に回路３７の出力との排他的論理和演算が回路４１で行われる。その演算結果Ｄは回路４２で上に２バイトローテーションされると共に回路３９の出力と排他的論理和演算が回路４３で行われる。その演算結果Ｅは回路４４で下に１バイトローテーションされると共に回路４２の出力と排他的論理和演算が回路４５で行われる。回路４５の出力Ｆがｚ1′，ｚ2′，ｚ3′，ｚ4′として、回路４４の出力がｚ5′，ｚ6′，ｚ7′，ｚ8′として出力される。
【００３５】
この置換処理をコンピュータにより行うには、図３中のテーブルメモリ２５にテーブルＳ１，Ｓ２，Ｓ３，Ｓ４の代りにＳ５，Ｓ６，Ｓ７，Ｓ８を設け、図６に示すようにステップ１でデータｘ1〜ｘ8を取込み記憶部２４に格納し、ステップ２で各データｘiを対応するテーブルを参照してＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4），Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を求め、ステップ３でこれらを記憶部２４に記憶する。ステップ４でＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）を取出し、これらの排他的論理和演算を演算部２６で行い、その結果Ａを記憶部２４に格納する。ステップ５でＳ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を取出し、これらの排他的論理和演算を演算部２６で行う。ステップ６−１でその結果Ｂをローテーション部２７により下に１バイトローテーションし、ステップ６−２で演算結果Ａと演算結果Ｂとの排他的論理和演算を行い、その演算結果Ｃをステップ７−１で上に１バイトローテーションし、同時にステップ７−２で演算結果Ｃとステップ６−１のローテーションの結果との排他的論理和演算を行う。その演算結果Ｄをステップ８−１で上に２バイトローテーションすると共に、ステップ７−１のローテーションの結果と演算結果Ｄと排他的論理和演算をステップ８−２で行う。この演算結果Ｅをステップ９−１で下に１バイトローテーションすると共にステップ９−２で、ステップ８−１のローテーション結果と演算結果Ｅとの排他的論理和演算を行い、ステップ９−１，９−２の各結果をステップ１０で出力する。
【００３６】
図５、図６に示した置換処理によればテーブル参照８回、排他的論理和１０回、ローテーション４回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図５中の点線部の処理は４演算で処理が完了する。
さらに、Ｓ５（ｘ）からＳ８（ｘ）はｓ（ｘ）とシフト処理によって実現可能である。つまり、ｘにより８ビットテーブルを参照してｓ（ｘ）を求め、ｓ（ｘ）を４行目の要素とする４要素の縦行列を論理シフトする。この論理シフトはＳ５（ｘ）が上３バイトシフトで実現され、またＳ６（ｘ）が上２バイトシフト、Ｓ７（ｘ）が上１バイトシフトで実現される。このことから、図５の処理においてＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）はそれぞれｓ（ｘ1）と上２バイトシフト、ｓ（ｘ2）と上１バイトシフト、ｓ（ｘ3），ｓ（ｘ4）と上３バイトシフトで実現できることがわかる。同様のことがＳ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）についてもいえるので、図５の処理のテーブル参照はｓ（ｘ）を得るテーブル参照と６回のシフトでも実現できることになる。このとき、使用するテーブルサイズは２５６Ｂとなる。
【００３７】
最後に、２５６Ｂのテーブルを利用したときの実装法について述べる。ここで利用するテーブルはもともとのｓ−ｂｏｘそのものである。この実施例の説明に示したＰ行列中の２つの行を取出し、対応する要素が一致しないものの数、いわゆるハミング重みの差が最小となるような順に演算を行う。このとき、上記のＰ関数処理は、
【００３８】
【数４０】
【００３９】
ここで、ｚi＝Ｓ（Ｘi），（ｉ＝１，…，８）であることを考慮すると、Ｓ関数処理とＰ関数処理との合成処理はテーブル参照８回、排他的論理和２５回で構成可能であることがわかる。
以上に述べた結果をまとめると、本実施例では、
（１）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和８回、ローテーション１回の演算処理、
（２）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１０回、ローテーション４回の演算処理、
（３）２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回の演算処理、
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。ちなみに、Ｅ２暗号での青木らの文献の結果によれば、Ｅ２暗号での高速実装結果は、
Ａ）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１１回、シフト演算４回の演算処理（このほかにデータのメモリ退避１回）、
Ｂ）８ＫＢのメモリを使用したときにはテーブル参照１２回、排他的論理和１１回の演算処理、
Ｃ）２５６Ｂのメモリを使用したときの実装法について記述なし
である。ここで、テーブル参照は排他的論理和やシフト、ローテーションなどと比較して極めて低速な処理であることに注意。したがって、この実施例の置換処理のほうが、Ｅ２暗号で使われていた置換処理よりも高速で、かつ様々な実装環境に応じた柔軟な実装が可能となる。
実施例２
以下、この発明の実施例２を、図面を用いて説明する。
【００４０】
図７は、この発明の実施例２を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００４１】
【数４１】
という処理が行なわれ、行列表現ｚ′＝Ｐ・ｚ＝Ｐ・ｓ（ｘ）として、
【００４２】
【数４２】
のように表される。これは、
【００４３】
【数４３】
とすると、
【００４４】
【数４４】
【００４５】
と表すことができる。
この式による置換処理は実施例の対応する式との比較から、図２に示した構成と同様に構成できる。つまり図８に示すように、図２に対し、入力データｘ1〜ｘ8中のｘ5，ｘ6，ｘ7，ｘ8によるテーブルの参照がそれぞれＳ４，Ｓ１，Ｓ２，Ｓ３である点と、ローテーション回路１８で下に１バイトローテーションを行う点が異なる。またこの場合も図４に示した処理手順と同様にしてコンピュータにより処理できることも容易に理解できよう。
同様に、下記の４ＫＢメモリを用いることもできる。
【００４６】
【数４５】
【００４７】
この場合の置換処理の構成は図９に示すように、図５に示した構成とほぼ同様である。ただ入力データｘ1〜ｘ8中のｘ1，ｘ2，ｘ3，ｘ4による参照がそれぞれＳ８，Ｓ５，Ｓ６，Ｓ７である点と、回路３７で上に１バイトローテーションする点と、回路３９で下に１バイトローテーションする点と、回路４４で上に１バイトローテーションする点が異なる。またこの場合も図６に示した処理手順と同様にしてコンピュータにより処理できることも容易に理解されよう。
【００４８】
従ってこの実施例においても実施例１と同様に、
（１）４ＫＢのメモリを使用したとき図８から、テーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は２演算で処理が完了する。
（２）４ＫＢのメモリを使用したとき、図９から、テーブル参照８回、排他的論理和１０回、ローテーション４回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は４演算で処理が完了する。
（３）図９におけるテーブル参照は、実施例１で説明したのと同様の理由によりテーブル参照８回とシフト６回で実現できる。したがって、２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回の演算処理でも実現可能である。
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。
【００４９】
実施例３
以下、この発明の実施例３を、図面を用いて説明する。
図１０は、この発明の実施例３を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００５０】
【数４６】
という処理が行なわれ、行列表現ｚ′＝Ｐ・ｚ＝Ｐ・ｓ（ｘ）として、
【００５１】
【数４７】
のように表される。これは、
【００５２】
【数４８】
とすると、
【００５３】
【数４９】
【００５４】
と表すことができる。
この実施例においても、実施例１と同様の考え方により、４ＫＢメモリを使用した場合、図１１に示すように実施例１の図２に示した構成と同様に構成することができ、４ＫＢメモリのテーブルの参照で表わした式と、実施例２の対応する式との差から、図８に示した構成に対し、回路１８で上に１バイトローテーションを行うようにした点を異ならせればよい。またこの置換処理を図４に示した手順とほぼ同様にコンピュータにより処理させることもできることは容易に理解できよう。
【００５５】
４ＫＢメモリを使用した別の場合は、図１２に示すように実施例１の図５に示した構成と同様に構成することができる。ただ入力データｘ1〜ｘ6中のｘ1，ｘ2，ｘ3，ｘ4によりそれぞれテーブルＳ５，Ｓ６，Ｓ７，Ｓ８を参照する点、回路３７で上に１バイトローテーションを行う点、回路３９で下に１バイトローテーションを行う点、回路４２で上に１バイトローテーションを行う点、回路４４で上に１バイトローテーションを行う点、更に回路４５の演算結果Ｆを回路４６で下に２バイトローテーションを行って出力する点が図５と異なる。またこの場合も図６に示した処理手順に順じて同様にコンピュータにより置換処理を行うこともできることは容易に理解できよう。
【００５６】
以上より
（１）４ＫＢのメモリを使用したとき図１１から、テーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は２演算で処理が完了する。
（２）４ＫＢのメモリを使用したとき、図１２から、テーブル参照８回、排他的論理和１０回、ローテーション５回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は５演算で処理が完了する。
（３）図１２におけるテーブル参照は、実施例１で説明したのと同様の理由によりテーブル参照８回とシフト６回で実現できる。したがって、２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション５回の演算処理でも実現可能である。
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。
【００５７】
実施例４
以下、この発明の実施例４を、図面を用いて説明する。
図１３は、この発明の実施例４を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００５８】
【数５０】
という処理が行なわれ、行列表現ｚ′＝Ｐ・ｚ＝Ｐ・ｓ（ｘ）として、
【００５９】
【数５１】
のように表される。これは、
【００６０】
【数５２】
とすると、
【００６１】
【数５３】
【００６２】
と表すことができる。
この実施例においても、実施例１と同様の考え方により、４ＫＢメモリを用いた場合、この３２ビットテーブルで表現した式を、実施例１の場合と比較すれば直ちに理解されるように、図１４に示すように、図２中の回路１８を下に１バイトローテーションに変更すればよい。またこの置換処理を図４に示した手順と同様にコンピュータにより行うこともできる。
【００６３】
４ＫＢメモリを用いた別の場合、図１５に示すように図５に示した構成と同様に構成できる。ただ入力データｘ1〜ｘ8中のｘ1，ｘ2，ｘ3，ｘ4によりそれぞれテーブルＳ５，Ｓ６，Ｓ７，Ｓ８を参照する点、回路４２で下に１バイトローテーションを行う点、回路４５の演算結果Ｆを回路４６で上に２バイトローテーションを行って出力する点が図２と異なる。またこの場合も、図６に示した処理手順とほぼ同様にコンピュータにより処理を行うこともできる。
【００６４】
以上より
（１）４ＫＢのメモリを使用したとき図１４から、テーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は２演算で処理が完了する。
（２）４ＫＢのメモリを使用したとき、図１５から、テーブル参照８回、排他的論理和１０回、ローテーション５回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は５演算で処理が完了する。
（３）図１５におけるテーブル参照は、実施例１で説明したのと同様の理由によりテーブル参照８回とシフト６回で実現できる。したがって、２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション５回の演算処理でも実現可能である。
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。
【００６５】
【発明の効果】
以上、詳細に説明したように、この発明によれば、Ｓ−Ｐ構造を用いた置換処理装置において、Ｓ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理を、
【００６６】
【数５４】
【００６７】
（ただし、＜＜＜ｙは上ｙバイトのローテーション、Ｓ１（・）〜Ｓ８（・）のテーブルは３２ビット参照テーブルを表す。なお、ｙ＜０のときは下｜ｙ｜バイトのローテーションを表すものとする。）
のように書き直すことが可能となるような構造にすることによって、少なくとも（１）８ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和８回、ローテーション１回の演算処理、（２）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１０回、ローテーション４回または５回の演算処理、（３）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、の３種類の高速実装方法が提供できる。なお、実施例のように、（２）の実装方法のときには、４ＫＢのメモリを使用したテーブル参照の代わりに、２５６Ｂのメモリを使用したテーブル参照と６回のシフト演算によっても実現可能であり、このときテーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回または５回の演算処理となる。また、特に｛Ｓ１（・），Ｓ２（・），Ｓ３（・），Ｓ４（・）｝＝｛Ｓ５（・），Ｓ６（・），Ｓ７（・），Ｓ８（・）｝を満たすのであれば、（１）の実装方法の時にはさらに４ＫＢのメモリ使用量を削減可能であり、使用メモリは４ＫＢとなる（他の演算処理量は変化しない）。これによって、Ｅ２暗号で使われていた置換処理よりも高速で、かつ合成処理そのものは同じでありながら、（１）の実装方法はＰＣ向き、（２）は３２ビットＣＰＵを備えたハイエンドＩＣカード向き、（３）は８ビットＣＰＵを備えたローエンドＩＣカード向きというように多様な実装環境に応じて最適かつ柔軟な実装が可能となる置換処理装置を提供できる。
【図面の簡単な説明】
【図１】この発明の実施例１における置換処理装置における処理を表す図。
【図２】実施例１における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図３】実施例１をコンピュータにより処理する場合の構成を示す図。
【図４】実施例１をコンピュータにより処理する場合の処理手順の例を示す流れ図。
【図５】実施例１における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図６】実施例１の装置を４ＫＢメモリを用いてコンピュータにより処理をする場合の処理手順の例を示す流れ図。
【図７】この発明の実施例２における置換処理装置における処理を表す図。
【図８】実施例２における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図９】実施例２における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図１０】この発明の実施例３における置換処理装置における処理を表す図。
【図１１】実施例３における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図１２】実施例３における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図１３】実施例４における置換処理装置における処理を表す図。
【図１４】実施例４における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図１５】実施例４における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図１６】Ｅ２暗号の置換処理を表す図。
【図１７】Ｅ２暗号での第１のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における高速な処理例を表す図。
【図１８】Ｅ２暗号での第１のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における別の高速な処理例を表す図。
【発明の属する技術分野】
この発明は、主に暗号技術で用いられ、特に、秘密鍵の制御のもとでデータをブロック単位で暗号化または復号を行う共通鍵暗号方式に用いられ、第一の非線形変換Ｓ−線形変換Ｐ−第二の非線形変換Ｓが行われる装置または非線形変換Ｓ−線形変換Ｐが行われる装置に適する置換処理装置に関する。
【０００２】
【従来の技術】
データを秘匿するためには暗号化技術が有効である。暗号化の方式には共通鍵暗号と公開鍵暗号があり、暗号化と復号で同一の秘密鍵を用いる方式を共通鍵暗号、暗号化と復号とで異なる鍵を用いる方式を公開鍵暗号と呼ぶ。処理速度の観点からは共通鍵暗号の方が有利である。
高速かつ安全な共通鍵暗号を構成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。このような暗号方式の一方式として、Ｓ−Ｐ−Ｓ構造を利用して置換処理における安全性を高めたＥ２暗号（例えば、文献「神田ら：“１２８ビットブロック暗号Ｅ２の提案”、電子情報通信学会情報セキュリティ研究会ＩＳＥＣ９８−１２」）がある。
【０００３】
図１６はＥ２暗号で利用されている置換処理を表したものである。このなかのＰ関数処理は、第１のＳ関数処理と合わせて、行列表現ｚ′＝Ｐ・ｚ＝Ｐ・ｓ（ｘ）として、
【０００４】
【数２４】
【０００５】
【数２５】
という処理が行われる。ここで、ｓ（ｘ）はｘを入力として第１のＳ関数を構成するｓ−ｂｏｘによる非線形変換された値を表している。
この第１のＳ関数処理と｛０，１｝要素からなる行列Ｐで表現される置換処理（Ｐ関数処理）との合成処理に対する高速な実現方法はいくつか考えられており、例えば文献「青木ら：“Ｅ２のソフトウェァ実装、”１９９９年暗号と情報セキュリティシンポジウムＳＣＩＳ９９−Ｆ１−２．２」にその実現方法が記載されている。
例えば、３２ビットプロセッサー上での実装例として、以下の４個の３２ビット参照テーブル
【０００７】
【数２６】
【０００８】
【数２７】
ここで、＞＞ｙは下ｙバイトの論理シフト、＜＜ｙは上ｙバイトの論理シフトである。上記行列中の縦線、横線は左辺の行列Ｐ・Ｓ（ｘ）と右辺のＳ１（・）〜Ｓ４（・）よりなる行列との関係を分かり易くするために記入したものであって特別の意味はない。
このとき、図１７に示すように、第１のＳ関数処理とＰ関数処理との合成処理では、ｘのあらゆる値に対して参照可能なテーブルＳ１（・）〜Ｓ４（・）、つまり４ＫＢのメモリ（Ｓ１（・）〜Ｓ４（・）のテーブルは各々１ＫＢのメモリが必要）を使用し、演算処理としてはｘ1〜ｘ8によるテーブル参照８回、排他的論理和１１回、シフト演算４回を必要とする。また、この文献中には特に記載されていないが、実際の実装においては、これらの演算処理の他に途中データのメモリ退避が１回必要となることに注意されたい。
別の実装例では、上記のＳ１（・）〜Ｓ４（・）のテーブルの他に以下の４個の３２ビット参照テーブル
【００１０】
【数２８】
【００１１】
【数２９】
このとき、第１のＳ関数処理とＰ関数処理との合成処理では、８ＫＢのメモリ（Ｓ１（・）〜Ｓ８（・）のテーブルは各々１ＫＢのメモリが必要）を使用し、演算処理としては図１８に示すようにテーブル参照１２回、排他的論理和１１回を必要とする。
以上説明したように、Ｅ２暗号で利用されている第１のＳ関数処理とＰ関数処理との合成処理での高速実装方法は、メモリを４〜８ＫＢも利用しているわりにはテーブル参照、排他的論理和、シフト演算などの処理量が大きく、必ずしも高速なものであるとはいえない。そのうえ、メモリ使用量に制限があるとき、さらに処理量が急増すると予想される。
【００１３】
【発明が解決しようとする課題】
この発明の目的は、少なくともＳ−Ｐ構造を有する置換処理において、実装の多様性を持たせたＰ関数を実現することによって、置換処理での安全性を同じにしながら、様々な実装環境に応じた最適な実装、特に、Ｓ関数処理と、｛０，１｝要素からなる行列Ｐで表現される置換処理（Ｐ関数処理）との合成処理における高速実装を可能とするような置換処理装置を提供することを目的とする。
【００１４】
【課題を解決するための手段】
この発明では、上記の目的を達成するための置換処理装置において、Ｓ関数処理（非線形変換処理）と、行列Ｐで表現される置換処理（Ｐ関数処理：線形変換処理）との合成処理を以下のように書き直すことが可能となるような構造にすることによって、様々な実装環境に応じた柔軟な高速実装が可能となる。
【００１５】
【数３０】
ここで、＜＜＜ｙは上にｙバイトのローテーション、Ｓ１（・）〜Ｓ８（・）のテーブルは参照テーブルを表す。なお、ｙ＜０のときは下に｜ｙ｜バイトローテーションを表すものとする。
【００１７】
【作用】
この発明によれば、Ｓ関数処理と、行列Ｐで表現される置換処理（Ｐ関数処理）との合成処理における高速実装方法として少なくとも、（１）８ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和８回、ローテーション１回の演算処理、（２）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１０回、ローテーション４回または５回の演算処理、（３）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、の３種類を実現することができる。なお、（２）の実装方法のときには、４ＫＢのメモリを使用したテーブル参照の代わりに、２５６Ｂのメモリを使用したテーブル参照と６回のシフト演算によっても実現可能であり、このときテーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回または５回の演算処理となる。また、特に｛Ｓ１（・），Ｓ２（・），Ｓ３（・），Ｓ４（・）｝＝｛Ｓ５（・），Ｓ６（・），Ｓ７（・），Ｓ８（・）｝を満たすのであれば、（１）の実装方法の時にはさらに４ＫＢのメモリ使用量を削減可能であり、使用メモリは４ＫＢとなる（他の演算処理量は変化しない）。
【００１８】
これによって、Ｅ２暗号で使われていた置換処理よりも高速で、かつ柔軟な実装が可能となる置換処理装置を提供できる。さらに、合成処理そのものは同じでありながら、（１）の実装方法はＰＣ向き、（２）は３２ビットＣＰＵを備えたハイエンドＩＣカード向き、（３）は８ビットＣＰＵを備えたローエンドＩＣカード向きというように多様な実装環境に応じて最適かつ柔軟な実装が可能となる。
【００１９】
【発明の実施の形態】
実施例１
以下、この発明の実施例１を、図面を用いて説明する。
図１は、この発明の実施例１を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００２０】
【数３１】
【００２１】
【数３２】
【００２２】
【数３３】
【００２３】
【数３４】
【００２４】
【数３５】
と表すことができる。
まず、４ＫＢのテーブルを利用したときの実装法について述べる。ここで用意するテーブルは以下の３２ビット参照テーブルの４個であり、各テーブルが１ＫＢのメモリ量を使用する。
【００２６】
【数３６】
【００２７】
【数３７】
したがって、このような処理を行う処理図は図２に示すようになる。つまりｘ1，ｘ2，ｘ3，ｘ4でそれぞれテーブルＳ１，Ｓ２，Ｓ３，Ｓ４を参照してＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）を求め、これらの排他的論理和を回路１１，１２，１３で求め、またｘ5，ｘ6，ｘ7，ｘ8でそれぞれテーブルＳ２，Ｓ３，Ｓ４，Ｓ１を参照してＳ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）を求め、これらの排他的論理和を回路１４，１５，１６により求め、この排他的論理和演算結果Ｕ2と前記排他的論理和演算結果Ｕ1との排他的論理和が回路１７でとられてｚ1′，ｚ2′，ｚ3′，ｚ4′として出力され、また回路１６よりの排他的論理和演算結果Ｕ2に対し、上１バイトローテーションが回路１８で行われ、回路１７の出力と回路１９で排他的論理和演算が行われてｚ5′，ｚ6′，ｚ7′，ｚ8′が得られる。
【００２９】
この変換処理はコンピュータにより行わせることもできる。例えば、図３に示すように、ＣＰＵよりなる制御部２１はプログラムメモリ２２に格納されたプログラムを読出し、解読実行し、図４に示す処理を行う。つまり入力部２３を通じてデータｘ1〜ｘ8を取込んで記憶部２４に一時記憶し（ステップ１）、その各データｘ1〜ｘ8を順次取出して、テーブルメモリ２５内の対応するテーブルを参照し（ステップ２）、参照結果を記憶部２４に一時格納する（ステップ３）。つまりこの例では参照結果Ｓ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4），Ｓ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）が記憶部２４に格納される。
【００３０】
記憶部２４からＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）を取出し、これらの排他的論理和演算を制御部２１の演算部２６で行い（ステップ４）、その演算結果Ｕ1を記憶部２４に一時格納し、また記憶部２４からＳ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）を取出し、演算部２６でこれらの排他的論理和演算を行い（ステップ５）、その演算結果Ｕ2と、前記演算結果Ｕ1との排他的論理和演算を演算部２６で行う（ステップ６−１）と共に、制御部２１のローテーション部２７で演算結果Ｕ2に対し、下１バイトローテーションを行い（ステップ６−２）、このローテーションの結果とステップ６の排他的論理和演算の結果との排他的論理和演算を演算部２６で行う（ステップ７）。このステップ４の演算結果Ｕ1をｚ1′，ｚ2′，ｚ3′，ｚ4′として、またステップ８の演算結果をｚ5′，ｚ6′，ｚ7′，ｚ8′として出力部２８より出力する（ステップ８）。
【００３１】
以上の置換処理ではテーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、ローテーション回路１８への入力が別の排他的論理和回路１７への（一方の）入力となっている場合にはそのローテーションと排他的論理和は並列処理が可能である。故に、図２中の点線部の処理は並列処理を考慮すると２演算で処理が完了する。
次に、もう１つの４ＫＢメモリを利用したときの実装法について述べる。ここで用意するテーブルは以下の３２ビット参照テーブルの４個であり、各テーブルが１ＫＢのメモリ量を使用する。
【００３２】
【数３８】
【００３３】
【数３９】
したがって、このような処理を行う処理は図５のようになる。つまり入力データｘ1，ｘ2，ｘ3，ｘ4でテーブルＳ６，Ｓ７，Ｓ８，Ｓ５がそれぞれ参照してＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）が出力され、これらは回路３１，３２，３３により排他的論理和演算が行われ、その演算結果Ａが回路３３から出力される。また入力データｘ5，ｘ6，ｘ7，ｘ8によりテーブルＳ５，Ｓ６，Ｓ７，Ｓ８がそれぞれ参照され、Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）が出力され、これらが回路３４，３５，３６により排他的論理和演算が行われ、その演算結果Ｂが回路３６から出力される。演算結果Ａは回路３７により下に１バイトローテーションされると共に回路３８で演算結果Ｂと排他的論理和演算される。この演算結果Ｃは回路３９により上に１バイトローテーションされると共に回路３７の出力との排他的論理和演算が回路４１で行われる。その演算結果Ｄは回路４２で上に２バイトローテーションされると共に回路３９の出力と排他的論理和演算が回路４３で行われる。その演算結果Ｅは回路４４で下に１バイトローテーションされると共に回路４２の出力と排他的論理和演算が回路４５で行われる。回路４５の出力Ｆがｚ1′，ｚ2′，ｚ3′，ｚ4′として、回路４４の出力がｚ5′，ｚ6′，ｚ7′，ｚ8′として出力される。
【００３５】
この置換処理をコンピュータにより行うには、図３中のテーブルメモリ２５にテーブルＳ１，Ｓ２，Ｓ３，Ｓ４の代りにＳ５，Ｓ６，Ｓ７，Ｓ８を設け、図６に示すようにステップ１でデータｘ1〜ｘ8を取込み記憶部２４に格納し、ステップ２で各データｘiを対応するテーブルを参照してＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4），Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を求め、ステップ３でこれらを記憶部２４に記憶する。ステップ４でＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）を取出し、これらの排他的論理和演算を演算部２６で行い、その結果Ａを記憶部２４に格納する。ステップ５でＳ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を取出し、これらの排他的論理和演算を演算部２６で行う。ステップ６−１でその結果Ｂをローテーション部２７により下に１バイトローテーションし、ステップ６−２で演算結果Ａと演算結果Ｂとの排他的論理和演算を行い、その演算結果Ｃをステップ７−１で上に１バイトローテーションし、同時にステップ７−２で演算結果Ｃとステップ６−１のローテーションの結果との排他的論理和演算を行う。その演算結果Ｄをステップ８−１で上に２バイトローテーションすると共に、ステップ７−１のローテーションの結果と演算結果Ｄと排他的論理和演算をステップ８−２で行う。この演算結果Ｅをステップ９−１で下に１バイトローテーションすると共にステップ９−２で、ステップ８−１のローテーション結果と演算結果Ｅとの排他的論理和演算を行い、ステップ９−１，９−２の各結果をステップ１０で出力する。
【００３６】
図５、図６に示した置換処理によればテーブル参照８回、排他的論理和１０回、ローテーション４回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図５中の点線部の処理は４演算で処理が完了する。
さらに、Ｓ５（ｘ）からＳ８（ｘ）はｓ（ｘ）とシフト処理によって実現可能である。つまり、ｘにより８ビットテーブルを参照してｓ（ｘ）を求め、ｓ（ｘ）を４行目の要素とする４要素の縦行列を論理シフトする。この論理シフトはＳ５（ｘ）が上３バイトシフトで実現され、またＳ６（ｘ）が上２バイトシフト、Ｓ７（ｘ）が上１バイトシフトで実現される。このことから、図５の処理においてＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）はそれぞれｓ（ｘ1）と上２バイトシフト、ｓ（ｘ2）と上１バイトシフト、ｓ（ｘ3），ｓ（ｘ4）と上３バイトシフトで実現できることがわかる。同様のことがＳ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）についてもいえるので、図５の処理のテーブル参照はｓ（ｘ）を得るテーブル参照と６回のシフトでも実現できることになる。このとき、使用するテーブルサイズは２５６Ｂとなる。
【００３７】
最後に、２５６Ｂのテーブルを利用したときの実装法について述べる。ここで利用するテーブルはもともとのｓ−ｂｏｘそのものである。この実施例の説明に示したＰ行列中の２つの行を取出し、対応する要素が一致しないものの数、いわゆるハミング重みの差が最小となるような順に演算を行う。このとき、上記のＰ関数処理は、
【００３８】
【数４０】
ここで、ｚi＝Ｓ（Ｘi），（ｉ＝１，…，８）であることを考慮すると、Ｓ関数処理とＰ関数処理との合成処理はテーブル参照８回、排他的論理和２５回で構成可能であることがわかる。
以上に述べた結果をまとめると、本実施例では、
（１）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和８回、ローテーション１回の演算処理、
（２）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１０回、ローテーション４回の演算処理、
（３）２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回の演算処理、
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。ちなみに、Ｅ２暗号での青木らの文献の結果によれば、Ｅ２暗号での高速実装結果は、
Ａ）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１１回、シフト演算４回の演算処理（このほかにデータのメモリ退避１回）、
Ｂ）８ＫＢのメモリを使用したときにはテーブル参照１２回、排他的論理和１１回の演算処理、
Ｃ）２５６Ｂのメモリを使用したときの実装法について記述なし
である。ここで、テーブル参照は排他的論理和やシフト、ローテーションなどと比較して極めて低速な処理であることに注意。したがって、この実施例の置換処理のほうが、Ｅ２暗号で使われていた置換処理よりも高速で、かつ様々な実装環境に応じた柔軟な実装が可能となる。
実施例２
以下、この発明の実施例２を、図面を用いて説明する。
【００４０】
図７は、この発明の実施例２を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００４１】
【数４１】
【００４２】
【数４２】
【００４３】
【数４３】
【００４４】
【数４４】
と表すことができる。
この式による置換処理は実施例の対応する式との比較から、図２に示した構成と同様に構成できる。つまり図８に示すように、図２に対し、入力データｘ1〜ｘ8中のｘ5，ｘ6，ｘ7，ｘ8によるテーブルの参照がそれぞれＳ４，Ｓ１，Ｓ２，Ｓ３である点と、ローテーション回路１８で下に１バイトローテーションを行う点が異なる。またこの場合も図４に示した処理手順と同様にしてコンピュータにより処理できることも容易に理解できよう。
同様に、下記の４ＫＢメモリを用いることもできる。
【００４６】
【数４５】
この場合の置換処理の構成は図９に示すように、図５に示した構成とほぼ同様である。ただ入力データｘ1〜ｘ8中のｘ1，ｘ2，ｘ3，ｘ4による参照がそれぞれＳ８，Ｓ５，Ｓ６，Ｓ７である点と、回路３７で上に１バイトローテーションする点と、回路３９で下に１バイトローテーションする点と、回路４４で上に１バイトローテーションする点が異なる。またこの場合も図６に示した処理手順と同様にしてコンピュータにより処理できることも容易に理解されよう。
【００４８】
従ってこの実施例においても実施例１と同様に、
（１）４ＫＢのメモリを使用したとき図８から、テーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は２演算で処理が完了する。
（２）４ＫＢのメモリを使用したとき、図９から、テーブル参照８回、排他的論理和１０回、ローテーション４回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は４演算で処理が完了する。
（３）図９におけるテーブル参照は、実施例１で説明したのと同様の理由によりテーブル参照８回とシフト６回で実現できる。したがって、２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回の演算処理でも実現可能である。
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。
【００４９】
実施例３
以下、この発明の実施例３を、図面を用いて説明する。
図１０は、この発明の実施例３を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００５０】
【数４６】
【００５１】
【数４７】
【００５２】
【数４８】
【００５３】
【数４９】
と表すことができる。
この実施例においても、実施例１と同様の考え方により、４ＫＢメモリを使用した場合、図１１に示すように実施例１の図２に示した構成と同様に構成することができ、４ＫＢメモリのテーブルの参照で表わした式と、実施例２の対応する式との差から、図８に示した構成に対し、回路１８で上に１バイトローテーションを行うようにした点を異ならせればよい。またこの置換処理を図４に示した手順とほぼ同様にコンピュータにより処理させることもできることは容易に理解できよう。
【００５５】
４ＫＢメモリを使用した別の場合は、図１２に示すように実施例１の図５に示した構成と同様に構成することができる。ただ入力データｘ1〜ｘ6中のｘ1，ｘ2，ｘ3，ｘ4によりそれぞれテーブルＳ５，Ｓ６，Ｓ７，Ｓ８を参照する点、回路３７で上に１バイトローテーションを行う点、回路３９で下に１バイトローテーションを行う点、回路４２で上に１バイトローテーションを行う点、回路４４で上に１バイトローテーションを行う点、更に回路４５の演算結果Ｆを回路４６で下に２バイトローテーションを行って出力する点が図５と異なる。またこの場合も図６に示した処理手順に順じて同様にコンピュータにより置換処理を行うこともできることは容易に理解できよう。
【００５６】
以上より
（１）４ＫＢのメモリを使用したとき図１１から、テーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は２演算で処理が完了する。
（２）４ＫＢのメモリを使用したとき、図１２から、テーブル参照８回、排他的論理和１０回、ローテーション５回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は５演算で処理が完了する。
（３）図１２におけるテーブル参照は、実施例１で説明したのと同様の理由によりテーブル参照８回とシフト６回で実現できる。したがって、２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション５回の演算処理でも実現可能である。
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。
【００５７】
実施例４
以下、この発明の実施例４を、図面を用いて説明する。
図１３は、この発明の実施例４を示す置換処理装置におけるＳ関数処理とＰ関数処理との合成処理を抜き出して示したものである。この合成処理は、
【００５８】
【数５０】
【００５９】
【数５１】
【００６０】
【数５２】
【００６１】
【数５３】
と表すことができる。
この実施例においても、実施例１と同様の考え方により、４ＫＢメモリを用いた場合、この３２ビットテーブルで表現した式を、実施例１の場合と比較すれば直ちに理解されるように、図１４に示すように、図２中の回路１８を下に１バイトローテーションに変更すればよい。またこの置換処理を図４に示した手順と同様にコンピュータにより行うこともできる。
【００６３】
４ＫＢメモリを用いた別の場合、図１５に示すように図５に示した構成と同様に構成できる。ただ入力データｘ1〜ｘ8中のｘ1，ｘ2，ｘ3，ｘ4によりそれぞれテーブルＳ５，Ｓ６，Ｓ７，Ｓ８を参照する点、回路４２で下に１バイトローテーションを行う点、回路４５の演算結果Ｆを回路４６で上に２バイトローテーションを行って出力する点が図２と異なる。またこの場合も、図６に示した処理手順とほぼ同様にコンピュータにより処理を行うこともできる。
【００６４】
以上より
（１）４ＫＢのメモリを使用したとき図１４から、テーブル参照８回、排他的論理和８回、ローテーション１回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は２演算で処理が完了する。
（２）４ＫＢのメモリを使用したとき、図１５から、テーブル参照８回、排他的論理和１０回、ローテーション５回で構成可能であることがわかる。なお、前述したようにローテーションと排他的論理和は並列処理が可能であることを考慮すると、図中の点線部の処理は５演算で処理が完了する。
（３）図１５におけるテーブル参照は、実施例１で説明したのと同様の理由によりテーブル参照８回とシフト６回で実現できる。したがって、２５６Ｂのメモリを使用したとき、テーブル参照８回、シフト６回、排他的論理和１０回、ローテーション５回の演算処理でも実現可能である。
（４）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、
の４種類の高速実装方法が提供できる。
【００６５】
【発明の効果】
以上、詳細に説明したように、この発明によれば、Ｓ−Ｐ構造を用いた置換処理装置において、Ｓ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理を、
【００６６】
【数５４】
（ただし、＜＜＜ｙは上ｙバイトのローテーション、Ｓ１（・）〜Ｓ８（・）のテーブルは３２ビット参照テーブルを表す。なお、ｙ＜０のときは下｜ｙ｜バイトのローテーションを表すものとする。）
のように書き直すことが可能となるような構造にすることによって、少なくとも（１）８ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和８回、ローテーション１回の演算処理、（２）４ＫＢのメモリを使用したときにはテーブル参照８回、排他的論理和１０回、ローテーション４回または５回の演算処理、（３）２５６Ｂのメモリを使用したときにはテーブル参照８回、排他的論理和２５回の演算処理、の３種類の高速実装方法が提供できる。なお、実施例のように、（２）の実装方法のときには、４ＫＢのメモリを使用したテーブル参照の代わりに、２５６Ｂのメモリを使用したテーブル参照と６回のシフト演算によっても実現可能であり、このときテーブル参照８回、シフト６回、排他的論理和１０回、ローテーション４回または５回の演算処理となる。また、特に｛Ｓ１（・），Ｓ２（・），Ｓ３（・），Ｓ４（・）｝＝｛Ｓ５（・），Ｓ６（・），Ｓ７（・），Ｓ８（・）｝を満たすのであれば、（１）の実装方法の時にはさらに４ＫＢのメモリ使用量を削減可能であり、使用メモリは４ＫＢとなる（他の演算処理量は変化しない）。これによって、Ｅ２暗号で使われていた置換処理よりも高速で、かつ合成処理そのものは同じでありながら、（１）の実装方法はＰＣ向き、（２）は３２ビットＣＰＵを備えたハイエンドＩＣカード向き、（３）は８ビットＣＰＵを備えたローエンドＩＣカード向きというように多様な実装環境に応じて最適かつ柔軟な実装が可能となる置換処理装置を提供できる。
【図面の簡単な説明】
【図１】この発明の実施例１における置換処理装置における処理を表す図。
【図２】実施例１における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図３】実施例１をコンピュータにより処理する場合の構成を示す図。
【図４】実施例１をコンピュータにより処理する場合の処理手順の例を示す流れ図。
【図５】実施例１における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図６】実施例１の装置を４ＫＢメモリを用いてコンピュータにより処理をする場合の処理手順の例を示す流れ図。
【図７】この発明の実施例２における置換処理装置における処理を表す図。
【図８】実施例２における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図９】実施例２における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図１０】この発明の実施例３における置換処理装置における処理を表す図。
【図１１】実施例３における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図１２】実施例３における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図１３】実施例４における置換処理装置における処理を表す図。
【図１４】実施例４における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときの処理を表す図。
【図１５】実施例４における置換処理装置中のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における４ＫＢのメモリを使用したときのもう１つの処理を表す図。
【図１６】Ｅ２暗号の置換処理を表す図。
【図１７】Ｅ２暗号での第１のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における高速な処理例を表す図。
【図１８】Ｅ２暗号での第１のＳ関数処理と行列Ｐで表現される置換（Ｐ関数処理）との合成処理における別の高速な処理例を表す図。
Claims (9)
- 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行う置換処理装置において、
上記非線形変換と上記線形変換の合成処理が
ただし、Ｓｊ（・）（ｊ＝１，２，…，８）はｘi（ｉ＝１，２，…，８）により３２ビットテーブルを参照してＳｊ（ｘi）を出力すること、<<<ｙはｙ＞０の場合、上ｙバイトローテーション、ｙ＜０の場合は下｜ｙ｜バイトローテーションを表わす。
Ｓ１（・），Ｓ２（・），…，Ｓ８（・）の各参照テーブルと、
上記参照テーブルを上記入力データにより参照する手段と、
上記参照テーブルの参照出力に対し排他的論理和演算を行う演算手段と、
排他的論理和演算に対しローテーションを施すローテーション手段と、
を具備し、
上記テーブル参照手段はｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8によりそれぞれＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4），Ｓ４（ｘ5），Ｓ１（ｘ6），Ｓ２（ｘ7），Ｓ３（ｘ8）を出力する手段であり、
上記排他的論理和演算手段は、上記Ｓ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）の排他的論理和演算を行って結果Ｕ1を得る手段と、上記Ｓ４（ｘ5），Ｓ１（ｘ6），Ｓ２（ｘ7），Ｓ３（ｘ8）の排他的論理和演算を行って結果Ｕ2を得る手段と、上記Ｕ1とＵ2の排他的論理和演算を行って結果Ｕ3を得る手段と、上記Ｕ3と上記ローテーション手段の出力の排他的論理和演算を行って結果Ｕ4を得る手段とよりなり、
上記ローテーション手段は上記Ｕ2を下に１バイトローテーションする手段であり、
上記Ｕ3，Ｕ4を置換処理結果ｚ1′，ｚ2′，…，ｚ8′として出力することを特徴とする置換処理装置。 - 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行う置換処理装置において、
上記非線形変換と上記線形変換の合成処理が
ただし、Ｓｊ（・）（ｊ＝１，２，…，８）はｘi（ｉ＝１，２，…，８）により３２ビットテーブルを参照してＳｊ（ｘi）を出力すること、<<<ｙはｙ＞０の場合、上ｙバイトローテーション、ｙ＜０の場合は下｜ｙ｜バイトローテーションを表わす。
Ｓ１（・），Ｓ２（・），…，Ｓ８（・）の各参照テーブルと、
上記参照テーブルを上記入力データにより参照する手段と、
上記参照テーブルの参照出力に対し排他的論理和演算を行う演算手段と、
排他的論理和演算に対しローテーションを施すローテーション手段と、
を具備し、
上記テーブル参照手段はｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8によりそれぞれＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4），Ｓ４（ｘ5），Ｓ１（ｘ6），Ｓ２（ｘ7），Ｓ３（ｘ8）を出力する手段であり、
上記排他的論理和演算手段は、上記Ｓ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）の排他的論理和演算を行って結果Ｕ1を得る手段と、上記Ｓ４（ｘ5），Ｓ１（ｘ6），Ｓ２（ｘ7），Ｓ３（ｘ8）の排他的論理和演算を行って結果Ｕ2を得る手段と、上記Ｕ1とＵ2の排他的論理和演算を行って結果Ｕ3を得る手段と、上記Ｕ3と上記ローテーション手段の出力の排他的論理和演算を行って結果Ｕ4を得る手段とよりなり、
上記ローテーション手段は上記Ｕ2を上に１バイトローテーションする手段であり、
上記Ｕ3，Ｕ4を置換処理結果ｚ1′，ｚ2′，…，ｚ8′として出力することを特徴とする置換処理装置。 - 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行う置換処理装置において、
上記非線形変換と上記線形変換の合成処理が
ただし、Ｓｊ（・）（ｊ＝１，２，…，８）はｘi（ｉ＝１，２，…，８）により３２ビットテーブルを参照してＳｊ（ｘi）を出力すること、<<<ｙはｙ＞０の場合、上ｙバイトローテーション、ｙ＜０の場合は下｜ｙ｜バイトローテーションを表わす。
Ｓ１（・），Ｓ２（・），…，Ｓ８（・）の各参照テーブルと、
上記参照テーブルを上記入力データにより参照する手段と、
上記参照テーブルの参照出力に対し排他的論理和演算を行う演算手段と、
排他的論理和演算に対しローテーションを施すローテーション手段と、
を具備し、
上記テーブル参照手段はｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8によりそれぞれＳ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4），Ｓ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）を出力する手段であり、
上記排他的論理和演算手段は、上記Ｓ１（ｘ1），Ｓ２（ｘ2），Ｓ３（ｘ3），Ｓ４（ｘ4）の排他的論理和演算を行って結果Ｕ1を得る手段と、上記Ｓ２（ｘ5），Ｓ３（ｘ6），Ｓ４（ｘ7），Ｓ１（ｘ8）の排他的論理和演算を行って結果Ｕ2を得る手段と、上記Ｕ1とＵ2の排他的論理和演算を行って結果Ｕ3を得る手段と、上記Ｕ3と上記ローテーション手段の出力の排他的論理和演算を行って結果Ｕ4を得る手段とよりなり、
上記ローテーション手段は上記Ｕ2を下に１バイトローテーションする手段であり、
上記Ｕ3，Ｕ4を置換処理結果ｚ1′，ｚ2′，…，ｚ8′として出力することを特徴とする置換処理装置。 - 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行って出力データｚ1′，ｚ2′，…，ｚ8′を得る置換処理装置において、
構成ベクトルが
構成ベクトルが
構成ベクトルが
構成ベクトルが
ｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8により上記テーブルを参照してＳ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4），Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を出力するテーブル参照手段と、
上記Ｓ６（ｘ1），Ｓ７（ｘ2），Ｓ８（ｘ3），Ｓ５（ｘ4）の排他的論理和演算を行って結果Ａを得る手段と、
上記Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）の排他的論理和演算を行って結果Ｂを得る手段と、
ＡとＢの排他的論理和演算を行ってＣを得る手段と、
Ａを下に１バイトローテーションする手段と、
そのローテーションの結果とＣとの排他的論理和演算を行って結果Ｄを得る手段と、
Ｃを上に１バイトローテーションする手段と、
そのローテーションの結果とＤとの排他的論理和演算を行って結果Ｅを得る手段と、
Ｄを上に２バイトローテーションする手段と、
そのローテーションの結果とＥとの排他的論理和演算を行って結果Ｆを得る手段と、
Ｅを下に１バイトローテーションを行って結果Ｇを得る手段と、
を具備し、上記ＦとＧを出力ｚ1′，ｚ2′，…，ｚ8′とすることを特徴とする置換処理装置。 - 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行って出力データｚ1′，ｚ2′，…，ｚ8′を得る置換処理装置において、
構成ベクトルが
構成ベクトルが
構成ベクトルが
構成ベクトルが
ｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8により上記テーブルを参照してＳ８（ｘ1），Ｓ５（ｘ2），Ｓ６（ｘ3），Ｓ７（ｘ4），Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を出力するテーブル参照手段と、
上記Ｓ８（ｘ1），Ｓ５（ｘ2），Ｓ６（ｘ3），Ｓ７（ｘ4）の排他的論理和演算を行なって結果Ａを得る手段と、
上記Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）の排他的論理和演算を行って結果Ｂを得る手段と、
ＡとＢの排他的論理和演算を行ってＣを得る手段と、
Ａを上に１バイトローテーションする手段と、
そのローテーションの結果とＣとの排他的論理和演算を行って結果Ｄを得る手段と、
Ｃを下に１バイトローテーションする手段と、
そのローテーションの結果とＤとの排他的論理和演算を行って結果Ｅを得る手段と、
Ｄを上に２バイトローテーションする手段と、
そのローテーションの結果とＥとの排他的論理和演算を行って結果Ｆを得る手段と、
Ｅを上に１バイトローテーションを行って結果Ｇを得る手段と、
を具備し、上記ＦとＧを出力ｚ1′，ｚ2′，…，ｚ8′とすることを特徴とする置換処理装置。 - 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行って出力データｚ1′，ｚ2′，…，ｚ8′を得る置換処理装置において、
構成ベクトルが
構成ベクトルが
構成ベクトルが
構成ベクトルが
ｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8により上記テーブルを参照してＳ５（ｘ1），Ｓ６（ｘ2），Ｓ７（ｘ3），Ｓ８（ｘ4），Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を出力するテーブル参照手段と、
上記Ｓ５（ｘ1），Ｓ６（ｘ2），Ｓ７（ｘ3），Ｓ８（ｘ4）の排他的論理和演算を行って結果Ａを得る手段と、
上記Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）の排他的論理和演算を行って結果Ｂを得る手段と、
ＡとＢの排他的論理和演算を行ってＣを得る手段と、
Ａを上に１バイトローテーションする手段と、
そのローテーションの結果とＣとの排他的論理和演算を行って結果Ｄを得る手段と、
Ｃを下に１バイトローテーションする手段と、
そのローテーションの結果とＤとの排他的論理和演算を行って結果Ｅを得る手段と、
Ｄを上に１バイトローテーションする手段と、
そのローテーションの結果とＥとの排他的論理和演算を行って結果Ｆを得る手段と、
Ｅを上に１バイトローテーションを行って結果Ｇを得る手段と、
Ｆを下に２バイトローテーションしてＨを得る手段と、
を具備し、上記ＨとＧを出力ｚ1′，ｚ2′，…，ｚ8′とすることを特徴とする置換処理装置。 - 入力データｘ1，ｘ2，…，ｘ8に対し、非線形変換と線形変換とを行って出力データｚ1′，ｚ2′，…，ｚ8′を得る置換処理装置において、
構成ベクトルが
構成ベクトルが
構成ベクトルが
構成ベクトルが
ｘ1，ｘ2，ｘ3，ｘ4，ｘ5，ｘ6，ｘ7，ｘ8により上記テーブルを参照してＳ５（ｘ1），Ｓ６（ｘ2），Ｓ７（ｘ3），Ｓ８（ｘ4），Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）を出力するテーブル参照手段と、
上記Ｓ５（ｘ1），Ｓ６（ｘ2），Ｓ７（ｘ3），Ｓ８（ｘ4）の排他的論理和演算を行なって結果Ａを得る手段と、
上記Ｓ５（ｘ5），Ｓ６（ｘ6），Ｓ７（ｘ7），Ｓ８（ｘ8）の排他的論理和演算を行って結果Ｂを得る手段と、
ＡとＢの排他的論理和演算を行ってＣを得る手段と、
Ａを下に１バイトローテーションする手段と、
そのローテーションの結果とＣとの排他的論理和演算を行って結果Ｄを得る手段と、
Ｃを上に１バイトローテーションする手段と、
そのローテーションの結果とＤとの排他的論理和演算を行って結果Ｅを得る手段と、
Ｄを下に１バイトローテーションする手段と、
そのローテーションの結果とＥとの排他的論理和演算を行って結果Ｆを得る手段と、
Ｅを下に１バイトローテーションを行って結果Ｇを得る手段と、
Ｆを上に２バイトローテーションして結果Ｈを得る手段と、
を具備し、上記ＨとＧを出力ｚ1′，ｚ2′，…，ｚ8′とすることを特徴とする置換処理装置。 - 請求項４から７の何れかに記載の置換処理装置おいて、
Ｓ５（ｘ）からＳ８（ｘ）で表されている３２ビットテーブルが、ｘにより参照され、ｓ（ｘ）を出力する８ビットテーブルと、ｓ（ｘ）を１要素とする４要素縦行列を論理シフトするシフト手段との組み合わせにより実現されていることを特徴とする置換処理装置。 - 請求項１から８の何れかに記載の置換処理装置としてコンピュータを機能させるためのプログラムを記録したコンピュータ読取り可能なプログラム記録媒体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000044529A JP3736731B2 (ja) | 2000-02-22 | 2000-02-22 | 置換処理装置およびそのプログラム記録媒体 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2000044529A JP3736731B2 (ja) | 2000-02-22 | 2000-02-22 | 置換処理装置およびそのプログラム記録媒体 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2001236017A JP2001236017A (ja) | 2001-08-31 |
| JP3736731B2 true JP3736731B2 (ja) | 2006-01-18 |
Family
ID=18567268
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2000044529A Expired - Lifetime JP3736731B2 (ja) | 2000-02-22 | 2000-02-22 | 置換処理装置およびそのプログラム記録媒体 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3736731B2 (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP4527960B2 (ja) * | 2003-10-22 | 2010-08-18 | 日本電信電話株式会社 | 換字置換装置、換字置換方法、換字置換プログラム及び換字置換記録媒体 |
| WO2007148665A1 (ja) * | 2006-06-23 | 2007-12-27 | Panasonic Corporation | 暗号処理装置、データ変換方法、データ変換プログラム、記録媒体及び集積回路 |
-
2000
- 2000-02-22 JP JP2000044529A patent/JP3736731B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2001236017A (ja) | 2001-08-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| USRE44594E1 (en) | Method and circuit for data encryption/decryption | |
| US20060093136A1 (en) | Implementation of a switch-box using a subfield method | |
| JP2000162965A (ja) | 暗復号装置及び記憶媒体 | |
| US7606368B2 (en) | Method and apparatus for data encryption | |
| JPH06236148A (ja) | Ａｎｓｉ ｘ３．９２データ暗号化アルゴリズム標準のパフォーマンスを強化したデータ暗号化アルゴリズムを実行するデータ処理システム | |
| JPH1055135A (ja) | プログラマブルな論理素子／装置を用いた暗号化／復号化装置および方法 | |
| TW200830327A (en) | System and method for encrypting data | |
| WO2021129470A1 (zh) | 基于多项式完全同态的二进制数据加密系统及方法 | |
| CN116647328B (zh) | 一种新型psp结构的轻量级分组密码实现方法及系统 | |
| JP2000305453A (ja) | 暗号化装置，復号装置，および暗号化・復号装置 | |
| CN108063760B (zh) | 一种分组加密的方法及其系统、分组解密的方法 | |
| US20070064933A1 (en) | Method of symmetric key data encryption | |
| CN114124359A (zh) | 保留格式加密数据的方法、装置、电子设备及存储介质 | |
| JP3736731B2 (ja) | 置換処理装置およびそのプログラム記録媒体 | |
| CN112564890B (zh) | 一种加速sm4算法的方法、装置、处理器及电子设备 | |
| JP4479703B2 (ja) | 通信システムと管理装置 | |
| JP4395527B2 (ja) | 情報処理装置 | |
| JP4857230B2 (ja) | 疑似乱数生成装置及びそれを用いた暗号化処理装置 | |
| JP2008205753A (ja) | 信号処理装置 | |
| ES2293665T3 (es) | Metodo para la conversion criptografica de bloques de entrada de l bits de informacion de datos digitales en bloques de salida de l bits. | |
| JP4912797B2 (ja) | 暗号装置及び復号装置及び暗号方法及び復号方法及びプログラム | |
| JP2021047371A (ja) | 情報処理装置、情報処理方法及びプログラム | |
| JP4094758B2 (ja) | デ―タ置換・分割方法および装置 | |
| JP4644053B2 (ja) | 暗号化装置及び方法、復号化装置及び方法 | |
| Farmani et al. | A high performance hardware implementation image encryption with AES algorithm |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A132 Effective date: 20041116 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050114 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050419 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050511 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20051004 |
|
| RD03 | Notification of appointment of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7423 Effective date: 20051020 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20051020 |
|
| R150 | Certificate of patent or registration of utility model |
Ref document number: 3736731 Country of ref document: JP Free format text: JAPANESE INTERMEDIATE CODE: R150 Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091104 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101104 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101104 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111104 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111104 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121104 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121104 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131104 Year of fee payment: 8 |
|
| S531 | Written request for registration of change of domicile |
Free format text: JAPANESE INTERMEDIATE CODE: R313531 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| EXPY | Cancellation because of completion of term |