(57)【要約】【課題】  十分なメモリ容量を確保できない環境下において、効率良く換字置換演算を行う。【解決手段】  ビット列格納部１１にビット列ＳＰを格納しておく。ここで、ビット列ＳＰは、循環シフトによって何れかの換字関数ｓｊ（ｘ）と同値となる関数ｓ（ｘ）を８個配列した関数ＳＰ（ｘ）に、ｘの取り得る値を代入したものである。そして、換字置換処理の際、ビット列抽出部１４において、このビット列格納部１１からビット列ＳＰを抽出し、６４ビット循環シフト部１５において、抽出したビット列全体を循環シフトし、何れかのｓｊ（ｘｊ）を８個配列したビット列ＳＰｊ（ｘｊ）を算出する。その後、算出されたビット列ＳＰｊ（ｘｊ）を用い、入力データ列（ｘ１,ｘ２,…,ｘｎ）の換字置換結果であるデータ列（ｙ１,ｙ２,…,ｙｍ）が求められる。【選択図】        図１
2005128166.tif 000002
【特許請求の範囲】
【請求項１】
ｉ＝１,２,…,ｍとし、ｊ＝１,２,…,ｎとし、環Ｒ上の置換行列のｉ行ｊ列要素をｐijとし、Ｒ→Ｒの換字関数をｓｊ（ｘ）とした場合における、Ｒ上の換字置換
【数１】
2005128166.tif 000015
によって、入力データ列（ｘ１,ｘ２,…,ｘｎ）からデータ列（ｙ１,ｙ２,…,ｙｍ）を求める換字置換装置であって、
循環シフトによって何れかの上記換字関数ｓｊ（ｘ）と同値となる関数をｓ（ｘ）とし、この関数ｓ（ｘ）を複数個配列した関数をＳＰ（ｘ）とし、この関数ＳＰ（ｘ）にｘの取り得る値を代入したビット列をＳＰとした場合における、当該ビット列ＳＰを格納するビット列格納手段と、
上記ビット列格納手段から上記ビット列ＳＰの少なくとも一部を抽出するビット列抽出手段と、
上記ビット列抽出手段において抽出されたビット列全体を循環シフトし、何れかの上記換字関数ｓｊ（ｘ）に入力データｘｊを代入した結果ｓｊ（ｘｊ）を複数個配列したビット列ＳＰｊ（ｘｊ）を算出する循環シフト手段と、
を有することを特徴とする換字置換装置。
【請求項２】
請求項１記載の換字置換装置であって、
上記関数ｓ（ｘ）は、
何れかの換字関数ｓｋ（ｘ）である、
ことを特徴とする換字置換装置。
【請求項３】
請求項１或いは２記載の換字置換装置であって、
上記ビット列抽出手段は、
いずれかの入力データｘｐに対応するビット列ＳＰ（ｘｐ）を抽出する手段である、
ことを特徴とする換字置換装置。
【請求項４】
請求項１から３の何れかに記載の換字置換装置であって、
上記ビット列格納手段に格納された上記ビット列ＳＰは、
１種類の上記関数ｓ（ｘ）にｘの取り得る値を代入した結果のみから構成されたビット列である、
ことを特徴とする換字置換装置。
【請求項５】
ｉ＝１,２,…,ｍとし、ｊ＝１,２,…,ｎとし、環Ｒ上の置換行列のｉ行ｊ列要素をｐijとし、Ｒ→Ｒの換字関数をｓｊ（ｘ）とした場合における、Ｒ上の換字置換
【数２】
2005128166.tif 000016
によって、入力データ列（ｘ１,ｘ２,…,ｘｎ）からデータ列（ｙ１,ｙ２,…,ｙｍ）を求める換字置換方法であって、
循環シフトによって何れかの上記換字関数ｓｊ（ｘ）と同値となる関数をｓ（ｘ）とし、この関数ｓ（ｘ）を複数個配列した関数をＳＰ（ｘ）とし、この関数ＳＰ（ｘ）にｘの取り得る値を代入したビット列をＳＰとした場合における、当該ビット列ＳＰをメモリに格納しておき、
上記メモリから上記ビット列ＳＰの少なくとも一部を抽出する手順と、
抽出されたビット列全体を循環シフトし、何れかの上記換字関数ｓｊ（ｘ）に入力データｘｊを代入した結果ｓｊ（ｘｊ）を複数個配列したビット列ＳＰｊ（ｘｊ）を算出する手順と、
をコンピュータにおいて実行する、
ことを特徴とする換字置換方法。
【請求項６】
請求項１から４の何れかに記載の換字置換装置としてコンピュータを機能させるための換字置換プログラム。
【請求項７】
請求項６記載の換字置換プログラムを格納したコンピュータ読取り可能な換字置換記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、主に暗号技術で用いられる換字置換処理に関し、特に、事前計算された値を用いて計算の効率化をはかった換字置換装置、換字置換方法、換字置換プログラム及び換字置換記録媒体に関する。
【背景技術】
【０００２】
データを秘匿するためには暗号化技術が有効である。暗号化の方法は共通鍵暗号と公開鍵暗号がある。共通鍵暗号では、暗号作成側と暗号復号側で同一の鍵を用い、この鍵は秘密に管理されている。一方、公開鍵暗号では暗号文作成のための鍵と暗号文復号の鍵は異なっており、暗号文作成のための鍵を公開しても、復号のための鍵は現実的な時間内に求まらないと広く信じられている。なお、処理速度の観点からは共通鍵暗号の方が有効である。
高速かつ安全な共通鍵暗号を作成するために、暗号化対象のデータを適当な長さのブロックに分割し、そのブロック毎に暗号化する方法をブロック暗号と呼ぶ。この様な暗号方式の代表としてＡＥＳ暗号があり、その構成は、例えば、非特許文献１に示されている。
【０００３】
このＡＥＳ暗号を含め、多くの共通鍵暗号は換字（substitution）と、置換（permutation）の組み合わせから構成されている。換字置換はかなり広い概念であるが、近年ソフトウェア実装の要請から、
【数３】
2005128166.tif 000003
という形の換字置換が多く用いられている。
【０００４】
なお、ここでの演算は全て環Ｒ上で行う。またｓｊ（ｘ）（ｊ＝１,２,…,ｎ）は、Ｒ→Ｒの換字関数（Ｓ箱：S-box）であり、Ｐは、
【数４】
2005128166.tif 000004
と表される置換行列である。つまり、換字関数による演算を換字と考え、置換行列との積を置換と考える。
【０００５】
式（１）に示される換字置換は、非特許文献２で定義されているＳＨＡＲＫ暗号でも使われている。さらにこの非特許文献２には、
【数５】
2005128166.tif 000005
で示される関数ＳＰｊの出力値を計算し、その事前計算結果をメモリ等に格納しておくことにより、式（１）を効率的に計算する方法も示されている。
【０００６】
また、現実のブロック暗号に用いられている換字置換には、式（１）に示したような一般的に記述される｛ｐｉｊ｝,ｓｊ（ｘ）ではなく、これらの値が制限された形で構成されているものも多い。例えば、Ｅ２暗号（例えば、非特許文献３参照。）や、Ｃａｍｅｌｌｉａ暗号（例えば、非特許文献４参照。）では、ｐｉｊ∈｛０,１｝であり、さらにｓｊ（ｘ）の間に簡単な数学的な関係が存在する。実際、Ｃａｍｅｌｌｉａ暗号では、Ｒ＝ＧＦ（２８）,ｎ＝ｍ＝８であり、
【数６】
2005128166.tif 000006
ｓ2（ｘ）＝ｓ5（ｘ）
ｓ3（ｘ）＝ｓ6（ｘ）            …(5)
ｓ4（ｘ）＝ｓ7（ｘ）
ｓ8（ｘ）＝ｓ1（ｘ）
となっている。
【０００７】
非特許文献４では、このような特殊な性質を持つＣａｍｅｌｌｉａ暗号について、式（３）に示した一般的な方法よりも効率良く式（１）を計算する方法が紹介されている。以下、６４ビットプロセッサを用い、この非特許文献４の方法を実現する場合について説明する。
この方法では、ｊ＝１,２,３,４、ｘ＝（００００００００）２〜（１１１１１１１１）２についてｓｊ（ｘ）の出力値を事前計算しておき、その演算結果ｓｊを８要素分配列した８ＫＢ（＝８バイト（６４ビット）×２５６×４）のビット列（表）
ＳＰｊ＝（ｓｊ,ｓｊ,ｓｊ,ｓｊ,ｓｊ,ｓｊ,ｓｊ,ｓｊ）…(6)
をメモリに格納しておく。そして、換字置換処理の際、この式（６）の表を参照し、入力データ列（ｘ１,ｘ２,…,ｘ８）に対応するＳＰｊの値を式（５）に適用し、さらに式（２）及び行列（４）を適用することにより、この入力データ列（ｘ１,ｘ２,…,ｘ８）の換字置換結果（ｙ１,ｙ２,…,ｙ８）を算出する。以下に、この演算に必要な処理回数及び表の大きさを示す。
表参照回数          ８
排他的論理和回数    ７
論理積回数          ８
表の大きさ（ＫＢ）  ８
【０００８】
次に、３２ビットプロセッサを用い、この非特許文献４の方法を実現する場合について説明する。
この場合、ｊ＝１,２,３,４、ｘ＝（００００００００）２〜（１１１１１１１１）２についてｓｊ（ｘ）の出力値を事前計算しておき、その演算結果ｓｊを以下のように配置した４ＫＢ（＝４バイト（３２ビット）×２５６×４）の表をメモリに格納しておく。
【０００９】
ＳＰ１１１０＝（ｓ１,ｓ１,ｓ１,０）
ＳＰ０２２２＝（０,ｓ２,ｓ２,ｓ２）        …(7)
ＳＰ３０３３＝（ｓ３,０,ｓ３,ｓ３）
ＳＰ４４０４＝（ｓ４,ｓ４,０,ｓ４）
そして、換字置換処理の際、この式（７）の表を参照して非特許文献５に示された
【数７】
2005128166.tif 000007
を計算し、入力データ列（ｘ１,ｘ２,…,ｘ８）の換字置換結果（ｙ１,ｙ２,…,ｙ８）を算出する。なお、ＳＰ１１１０（ｘ８）は、（ｓ１（ｘ８）,ｓ１（ｘ８）,ｓ１（ｘ８）,０）を示し、その演算値は、事前計算された式（７）の表から抽出されるものである。その他のＳＰ０２２２（ｘ５）等についても同様である。また、「≫８」は、ＧＦ（２８）をＧＦ（２）８と同一視した場合における８ビット右循環シフトを表す。
【００１０】
以下に、この式（８）の演算に必要な処理回数及び表の大きさを示す。
表参照回数                          ８
排他的論理和回数                    ８
３２ビットデータ循環シフト回数      １
表の大きさ（ＫＢ）                  ４
【非特許文献１】Specification for the ADVANCED ENCRYPTION STANDARD(AES),Federal Information Processing Standards Publication 197
【非特許文献２】V. Rijmen, et al. : ”The Cipher SHARK,” Fast Software Encryption-Third International Workshop, Lecture Notes in Computer Science 1039, pp. 99-111, Springer-Verlag, 1996
【非特許文献３】M. Kanda, et al: ”E2-A New 128-Bit Block Cipher,” IEICE Transactions on Fundamentals, Vol. E83-A, No. 1, pp. 48-59, 2000
【非特許文献４】K. Aoki, et al: ”The 128-Bit Block Cipher Camellia,” IEICE Transactions on Fundamentals, Vol. E85-A, No. 1, pp. 11-24, 2002
【非特許文献５】青木和麻呂，他６名，「１２８ビットブロック暗号Ｃａｍｅｌｌｉａの実装評価」、電子情報通信学会技術研究報告，電子情報通信学会，２０００年９月２９日，ＩＳＥＣ２０００‐７３，ｐ.１３１〜１３８
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかし、非特許文献５に示す方法は、メモリに格納すべき表のサイズが大きく、十分なメモリ容量を確保できない場合には適用できないという問題点がある。
本発明はこのような点に鑑みてなされたものであり、十分なメモリ容量を確保できない場合でも、効率良く換字置換演算を行うことが可能な換字置換装置を提供することを目的とする。
また、本発明の他の目的は、十分なメモリ容量を確保できない場合でも、効率良く換字置換演算を行うことが可能な換字置換方法を提供することである。
【００１２】
さらに、本発明の他の目的は、十分なメモリ容量を確保できない場合でも、効率良く換字置換演算を行うことが可能な機能をコンピュータに実行させるための換字置換プログラムを提供することである。
また、本発明の他の目的は、十分なメモリ容量を確保できない場合でも、効率良く換字置換演算を行うことが可能な機能をコンピュータに実行させるための換字置換プログラムを格納した換字置換記録媒体を提供することである。
【課題を解決するための手段】
【００１３】
この発明では上記課題を解決するために、メモリにビット列ＳＰを格納しておく。ここで、ビット列ＳＰは、循環シフトによって何れかの換字関数ｓｊ（ｘ）と同値となる関数ｓ（ｘ）を複数個配列した関数ＳＰ（ｘ）に、ｘの取り得る値を代入したものである。そして、換字置換処理の際、メモリからこのビット列ＳＰを抽出し、抽出したビット列全体を循環シフトし、何れかの換字関数ｓｊ（ｘ）に入力データｘｊを代入した結果ｓｊ（ｘｊ）を複数個配列したビット列ＳＰｊ（ｘｊ）を算出する。
算出されたビット列ＳＰｊ（ｘｊ）は、例えば、非特許文献４の方法に適用され、これにより、入力データ列（ｘ１,ｘ２,…,ｘｎ）から、その換字置換結果であるデータ列（ｙ１,ｙ２,…,ｙｍ）が求められる。
【００１４】
ここで、抽出したビット列を循環シフトして換字置換演算に必要なビット列ＳＰｊを算出することができるため、メモリに格納すべきビット列ＳＰｊの数を低減させることができる。
また、この関数ｓ（ｘ）は、それ自体の循環シフトによって何れかの換字関数ｓｊ（ｘ）と同値となる（ｓｊ（ｘ）＝ｓ（ｘ）≪ｒ）。この場合、関数ｓ（ｘ）を複数個配列したビット列ＳＰ＝（ｓ（ｘ）, ｓ（ｘ）,…,ｓ（ｘ））全体を、同ビット、同方向に循環シフトした結果は、この換字関数ｓｊ（ｘ）を同数個配列したビット列ＳＰｊ＝（ｓｊ（ｘ）, ｓｊ（ｘ）,…,ｓｊ（ｘ））と同値となるという性質がある（（ｓｊ（ｘ）, ｓｊ（ｘ）,…,ｓｊ（ｘ））＝（ｓ（ｘ）, ｓ（ｘ）,…,ｓ（ｘ））≪ｒ）。そのため、換字置換演算に必要なビット列ＳＰｊを算出する際、関数ｓ（ｘ）から換字関数ｓｊ（ｘ）を算出し、算出した換字関数ｓｊ（ｘ）を複数個配列してビット列ＳＰｊを生成するといった煩雑な処理を行うことなく、単に、ビット列ＳＰ全体を循環シフトするのみでビット列ＳＰｊを生成することができる。
【００１５】
なお、「≪ｒ」はｒビットの左循環シフトを表し、「≫ｒ」はｒビットの右循環シフトを表す。ここではＧＦ（２α）をＧＦ（２）αと同一視している。
【発明の効果】
【００１６】
上述のように、本発明では、メモリに格納すべきビット列ＳＰｊの数を低減させることができるため、十分なメモリ容量を確保できない場合でも、非特許文献４の方法等を用いて効率良く換字置換演算を行うことができる。
また、単に、ビット列ＳＰ全体を循環シフトするのみでビット列ＳＰｊを生成できるため、ビット列ＳＰｊの生成に必要な論理演算数も少なく、効率的な換字置換演算を実現できる。
【発明を実施するための最良の形態】
【００１７】
以下、この発明の実施の形態を図面を参照して説明する。
〔第１の実施の形態〕
まず、本発明の第１の実施の形態について説明する。
本形態は、６４ビットプロセッサにおいて行われるＣａｍｅｌｌｉａ暗号の換字置換処理に本発明を適用する例である。
図１は、本形態における換字置換装置１０の機能構成を例示した図、図２は、ビット列格納部１１に格納される表２０のデータ構成を例示した図、図３は、換字置換装置１０のハードウェア構成を例示した図である。また、図４は、本形態における換字置換方法を説明するためのフローチャートである。以下、これらの図を用いて、この例の換字置換装置１０の構成及び処理手順について説明する。
【００１８】
＜ハードウェア構成＞
図３に例示するように、この例の換字置換装置１０は、６４ビットのＣＰＵ（Central Processing Unit）１０ａ、ＲＯＭ（Read Only Memory）１０ｂ、ＲＡＭ（Random Access Memory）１０ｃ、換字置換プログラムを格納したＲＡＭ等のプログラムメモリ１０ｄ、インタフェースである入力部１０ｅ及び出力部１０ｆを有しており、バス１０ｇにおいて相互に通信可能なように接続されている。そして、ＣＰＵ１０ａは、プログラムメモリ１０ｄに格納された換字置換プログラムを読み出し、それに従った処理を実行することによって、以下に示す各処理機能を実現する。
【００１９】
＜前提＞
換字置換装置１０は、環Ｒ上の換字置換
【数８】
2005128166.tif 000008
によって、入力データ列（ｘ１,ｘ２,…,ｘｎ）からデータ列（ｙ１,ｙ２,…,ｙｍ）を求める装置である。なお、ｐij（ｉ＝１,２,…,ｍ、ｊ＝１,２,…,ｎ）は、Ｒ上の置換行列Ｐのｉ行ｊ列要素を示し、ｓｊ（ｘ）は、Ｒ→Ｒの換字関数（Ｓ箱：S-box）を示す。
ここではＣａｍｅｌｌｉａ暗号の換字置換処理を例にとるため、Ｒ＝ＧＦ（２８）、ｎ＝ｍ＝８であり、置換行列は、
【数９】
2005128166.tif 000009
である。
また、Ｃａｍｅｌｌｉａ暗号の場合、換字関数間には、
ｓ2（ｘ）＝ｓ5（ｘ）＝ｓ1（ｘ）≪１
ｓ3（ｘ）＝ｓ6（ｘ）＝ｓ1（ｘ）≫１         …(10)
ｓ4（ｘ）＝ｓ7（ｘ）＝ｓ1（ｘ≪１）
ｓ8（ｘ）＝ｓ1（ｘ）
の関係がある。
【００２０】
＜前処理＞
まず、前処理として、事前計算したビット列ＳＰをビット列格納部１１に格納する。ここで、ビット列ＳＰは、循環シフトによって何れかの換字関数ｓｊ（ｘ）と同値となる関数をｓ（ｘ）とし、この関数ｓ（ｘ）を複数個配列した関数をＳＰ（ｘ）とし、この関数ＳＰ（ｘ）にｘの取り得る値を代入したビット列である。この例では、換字関数ｓ１（ｘ）を関数ｓ（ｘ）とする。
また、図２に例示するように、この例では、この関数ｓ（ｘ）を８要素配列した関数をＳＰ（ｘ）（＝（ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）））としている。そして、この関数ＳＰ（ｘ）にｘ＝（００００００００）２,（０００００００１）２,…,（１１１１１１１１）２をそれぞれ代入した２５６要素のビット列２２
SP((00000000)2)=(s((00000000)2),…,s((00000000)2))
SP((00000001)2)=(s((00000001)2),…,s((00000001)2))
…
SP((11111111)2)=(s((11111111)2),…,s((11111111)2))
をＳＰとし、表２０を構成している。
【００２１】
また、これらの各ビット列ＳＰ（（００００００００）２）,ＳＰ（（０００００００１）２）,…,ＳＰ（（１１１１１１１１）２）は、各代入値ｘ＝（００００００００）２,（０００００００１）２,…,（１１１１１１１１）２とそれぞれ対応付けられている。この例の場合、各代入値ｘに対応するビット列格納部１１のアドレス２１（Ｈ（ｘ））に、ｘの代入結果である各ビット列ＳＰ（（００００００００）２）,ＳＰ（（０００００００１）２）,…,ＳＰ（（１１１１１１１１）２）を格納することにより、この対応付けを行っている。
【００２２】
なお、ｓ（ｘ）の代入結果は８ビットであるため、それが８要素配列されたＳＰ（ｘ）の各代入結果は６４（８×８）ビット＝８バイトとなる。また、表２０は、このＳＰ（ｘ）への代入結果が２５６要素集合したものである。よって、この表２０の大きさ（データサイズ）は２ＫＢ（＝８バイト×２５６）である。
また、置換行列格納部１６には、置換行列
【数１０】
2005128166.tif 000010
が格納される。この例では式（９）に示す置換行列Ｐを格納しておく。
【００２３】
＜換字置換処理＞
本形態において換字置換処理を行う場合、まずデータ列入力部１２において、換字置換処理の対象となる入力データ列（ｘ１,ｘ２,…,ｘ８）の入力を受け付ける（ステップＳ１）。入力されたデータｘ４,ｘ７は８ビット循環シフト部１３へ送られ、その他のデータ列（ｘ１,ｘ２,ｘ３,ｘ５,ｘ６,ｘ８）はビット列抽出部１４に送られる。
【００２４】
８ビット循環シフト部１３は、送られた８ビットのデータｘ４,ｘ７に対し、それぞれ１ビットの左循環シフト（ｘ４≪１,ｘ７≪１）を行う（ステップＳ２）。つまり、例えばｘ４の各ビットがａｂｃｄｅｆｊｈである場合、このビット列がｂｃｄｅｆｊｈａとなるように、各ビットを左に１ビット循環させる。そして、これらの１ビットの左循環シフト結果（ｘ４≪１,ｘ７≪１）はビット列抽出部１４に送られる。
ビット列抽出部１４は、ビット列格納部１１を参照し、送られたデータ列（ｘ１,ｘ２,ｘ３,ｘ５,ｘ６,ｘ８）及び左循環シフト結果（ｘ４≪１,ｘ７≪１）に対応付けられているアドレス２１に格納されたビット列ＳＰ（ｘ１）,ＳＰ（ｘ２）,ＳＰ（ｘ３）,ＳＰ（ｘ５）,ＳＰ（ｘ６）,ＳＰ（ｘ８）及びＳＰ（ｘ４≪１）,ＳＰ（ｘ７≪１）を抽出する（ステップＳ３）。
【００２５】
ここでビット列抽出部１４で抽出されたＳＰ（ｘ１）はＳＰ１（ｘ１）として、ＳＰ（ｘ８）はＳＰ８（ｘ８）として、ＳＰ（ｘ４≪１）はＳＰ４（ｘ４）として、ＳＰ（ｘ７≪１）はＳＰ７（ｘ７）として、それぞれ論理積演算部１７に送られる。なお、ＳＰｊ（α）は、換字関数ｓｊ（ｘ）にデータαを代入した結果ｓｊ（α）を８個配列したビット列（ｓｊ（α）,ｓｊ（α）,ｓｊ（α）,ｓｊ（α）,ｓｊ（α）,ｓｊ（α）,ｓｊ（α）,ｓｊ（α））を示す。また、上述のような置き換え（ＳＰ１（ｘ１）←ＳＰ（ｘ１）、ＳＰ８（ｘ８）←ＳＰ（ｘ８）等）ができるのは、この例では、換字関数ｓ１（ｘ）を関数ｓ（ｘ）としており、さらに式（１０）の関係が成立していることに基づく。
【００２６】
また、ビット列抽出部１４で抽出されたその他のＳＰ（ｘ２）,ＳＰ（ｘ３）,ＳＰ（ｘ５）,ＳＰ（ｘ６）は、それぞれ６４ビット循環シフト部１５に送られる。
６４ビット循環シフト部１５（「循環シフト手段」に相当）は、送られたビット列ＳＰ（ｘ２）全体を左に１ビットだけ循環シフトし（ＳＰ（ｘ２）≪１）、換字関数ｓ２（ｘ）に入力データｘ２を代入した結果ｓ２（ｘ２）を８個配列したビット列ＳＰ２（ｘ２）を算出する。ここで、ビット列ＳＰ（ｘ２）全体を左に１ビットだけ循環シフトするとビット列ＳＰ２（ｘ２）となる理由を説明する。
【００２７】
例えばｓ（ｘ２）の各ビットがａｂｃｄｅｆｊｈである場合、ＳＰ（ｘ２）は（ａｂｃｄｅｆｊｈａｂｃｄｅｆｊｈ…ａｂｃｄｅｆｊｈ）となり、ＳＰ（ｘ２）全体を左に１ビットだけ循環シフト（ＳＰ（ｘ２）≪１）した結果は、
（ｂｃｄｅｆｊｈａｂｃｄｅｆｊｈ…ａｂｃｄｅｆｊｈａ）…(11)
となる。
また、前述のように、この例ではｓ（ｘ）＝ｓ１（ｘ）としており、さらに式（１０）より、ｓ2（ｘ２）＝ｓ1（ｘ２）≪１＝ｓ（ｘ２）≪１が成立する。そのため、ｓ2（ｘ２）は、ｓ（ｘ２）を左に１ビットだけ循環シフトした結果（ｓ（ｘ２）≪１）と同じｂｃｄｅｆｊｈａとなる。そして、ｓ2（ｘ２）を８個配列したビット列ＳＰ２（ｘ２）は、（ｂｃｄｅｆｊｈａｂｃｄｅｆｊｈ…ａｂｃｄｅｆｊｈａ）となり、上述の（１１）と等しくなる。これは、ビット列ＳＰ（ｘ２）全体を左に１ビットだけ循環シフトした結果（ＳＰ（ｘ２）≪１）が、ｓ２（ｘ２）を８個配列したビット列ＳＰ２（ｘ２）と等しくなることを意味している。
【００２８】
同様に、６４ビット循環シフト部１５は、送られたビット列ＳＰ（ｘ５）全体を左に１ビットだけ循環シフトし（ＳＰ（ｘ５）≪１）、またＳＰ（ｘ３）全体及びＳＰ（ｘ６）全体をそれぞれ右に１ビットだけ循環シフトし（ＳＰ（ｘ３）≫１, ＳＰ（ｘ６）≫１）、ビット列ＳＰ５（ｘ５）, ＳＰ３（ｘ３）, ＳＰ６（ｘ６）を算出する（ステップＳ４）。そして、６４ビット循環シフト部１５で算出されたビット列ＳＰ２（ｘ２）,ＳＰ３（ｘ３）,ＳＰ５（ｘ５）,ＳＰ６（ｘ６）は論理積演算部１７に送られる。
【００２９】
論理積演算部１７は、送られたＳＰｊ（ｘｊ）に対し、置換行列格納部１６から、置換行列Ｐのｊ列要素
【数１１】
2005128166.tif 000011
を算出する（ステップＳ５）。算出された論理積ＳＰｊ（ｘｊ）・Ｐｊ（ｊ＝１，２，…，８）は、排他的論理和演算部１８に送られ、そこで、これらの論理積ＳＰｊ（ｘｊ）・Ｐｊの排他的論理和
【数１２】
2005128166.tif 000012
が求められ（ステップＳ６）、その演算結果のデータ列（ｙ１,ｙ２,…,ｙ８）が換字置換結果として出力される（ステップＳ７）。
【００３０】
＜計算コスト・表の大きさ＞
以上説明したように、本形態では、ステップＳ２において、８ビットデータの循環シフトを２回行い、ステップＳ３において、ビット列格納部１１の表２０を８回参照している。また、ステップＳ４において、６４ビットデータの循環シフトを４回行い、ステップＳ５において、論理積ＳＰｊ（ｘｊ）・Ｐｊ（ｊ＝１，２，…，８）を８回行い、ステップＳ６において、排他的論理和を７回行っている。また、前述のように表２０の大きさは２ＫＢである。
【００３１】
表参照回数                        ８
排他的論理和回数                  ７
６４ビットデータ循環シフト回数    ４
８ビットデータ循環シフト回数      ２
論理積回数                        ８
表の大きさ（ＫＢ）                ２
このように、本形態では、計算コストをさほど増加させることなく、表の大きさを従来の４分の１にすることができた。
【００３２】
〔第２の実施の形態〕
次に、本発明の第２の実施の形態について説明する。
本形態は、３２ビットプロセッサにおいて行われるＣａｍｅｌｌｉａ暗号の換字置換処理に本発明を適用する例である。
図５は、本形態における換字置換装置１００の機能構成を例示した図、図６は、ビット列格納部１１１に格納される表１３０のデータ構成を例示した図、図７は、本形態における換字置換方法を説明するためのフローチャートである。以下、これらの図を用いて、この例の換字置換装置１００の構成及び処理手順について説明する。なお、以下では第１の実施の形態との相違点を中心に説明を行い、第１の実施の形態と共通する事項については説明を省略する。
【００３３】
＜ハードウェア構成＞
３２ビットのＣＰＵを用いる以外は、第１の実施の形態と同様である。
＜前処理＞
第１の実施の形態と同様、事前計算したビット列ＳＰをビット列格納部１１１に格納する。ただし、この例では、関数ｓ（ｘ）を４要素配列した関数をＳＰ（ｘ）（＝（ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）,ｓ（ｘ）））とし、この関数ＳＰ（ｘ）にｘ＝（００００００００）２,（０００００００１）２,…,（１１１１１１１１）２をそれぞれ代入した２５６要素のビット列１３２
SP((00000000)2)=(s((00000000)2),…,s((00000000)2))
SP((00000001)2)=(s((00000001)2),…,s((00000001)2))
…
SP((11111111)2)=(s((11111111)2),…,s((11111111)2))
をＳＰとし、表１３０を構成している（図６）。
【００３４】
また、第１の実施の形態と同様、この例でも各代入値ｘに対応するビット列格納部１１１のアドレス１３１（Ｈ（ｘ））に、ｘの代入結果である各ビット列ＳＰ（（００００００００）２）,ＳＰ（（０００００００１）２）,…,ＳＰ（（１１１１１１１１）２）を格納することにより、各ビット列ＳＰと各代入値ｘとの対応付けを行っている。
なお、ｓ（ｘ）の代入結果は８ビットであるため、それが４要素配列されたＳＰ（ｘ）の各代入結果は３２（８×４）ビット＝４バイトとなる。また、表１３０は、このＳＰ（ｘ）への代入結果が２５６要素集合したものである。よって、この表１３０の大きさ（データサイズ）は１ＫＢ（＝４バイト×２５６）である。
また、定数格納部１１６には、ｊ＝１,８に対応付けられた定数（ｆｆｆｆｆｆ００）１６,ｊ＝２,５に対応付けられた定数（００ｆｆｆｆｆｆ）１６,ｊ＝３,６に対応付けられた定数（ｆｆ００ｆｆｆｆ）１６,ｊ＝４,７に対応付けられた定数（ｆｆｆｆ００ｆｆ）１６が格納される。
【００３５】
＜換字置換処理＞
本形態において換字置換処理を行う場合、まずデータ列入力部１１２において、換字置換処理の対象となる入力データ列（ｘ１,ｘ２,…,ｘ８）の入力を受け付ける（ステップＳ１１）。入力されたデータｘ４,ｘ７は８ビット循環シフト部１１３へ送られ、その他のデータ列（ｘ１,ｘ２,ｘ３,ｘ５,ｘ６,ｘ８）はビット列抽出部１１４に送られる。
８ビット循環シフト部１１３は、送られた８ビットのデータｘ４,ｘ７に対し、それぞれ１ビットの左循環シフト（ｘ４≪１,ｘ７≪１）を行い（ステップＳ１２）、その演算結果をビット列抽出部１１４に送る。
【００３６】
ビット列抽出部１１４は、ビット列格納部１１１を参照し、送られたデータ列（ｘ１,ｘ２,ｘ３,ｘ５,ｘ６,ｘ８）及び左循環シフト結果（ｘ４≪１,ｘ７≪１）に対応付けられているアドレス１３１に格納されたビット列ＳＰ（ｘ１）,ＳＰ（ｘ２）,ＳＰ（ｘ３）,ＳＰ（ｘ５）,ＳＰ（ｘ６）,ＳＰ（ｘ８）及びＳＰ（ｘ４≪１）,ＳＰ（ｘ７≪１）を抽出する（ステップＳ１３）。このビット列抽出部１１４で抽出されたＳＰ（ｘ１）、ＳＰ（ｘ８）、ＳＰ（ｘ４≪１）、ＳＰ（ｘ７≪１）は、それぞれ論理積演算部１１７に送られ、その他のＳＰ（ｘ２）,ＳＰ（ｘ３）,ＳＰ（ｘ５）,ＳＰ（ｘ６）は、それぞれ３２ビット循環シフト部１１５に送られる。
【００３７】
３２ビット循環シフト部１１５（「循環シフト手段」に相当）は、送られたビット列ＳＰ（ｘ２）全体及びＳＰ（ｘ５）全体を左に１ビットだけ循環シフトし（ＳＰ（ｘ２）≪１,ＳＰ（ｘ５）≪１）、ＳＰ（ｘ３）全体及びＳＰ（ｘ６）全体をそれぞれ右に１ビットだけ循環シフトする（ＳＰ（ｘ３）≫１, ＳＰ（ｘ６）≫１）（ステップＳ１４）。そして、これらの演算結果は、論理積演算部１１７に送られる。なお、ＳＰ（ｘ２）≪１は、換字関数ｓ２（ｘ）に入力データｘ２を代入した結果ｓ２（ｘ２）を４個配列したビット列に相当する。同様に、ＳＰ（ｘ５）≪１はｓ５（ｘ５）を４個配列したビット列に相当し、ＳＰ（ｘ３）≫１, はｓ３（ｘ３）を４個配列したビット列に相当し、ＳＰ（ｘ６）≫１はｓ６（ｘ６）を４個配列したビット列に相当する。
【００３８】
論理積演算部１１７は、送られたＳＰ（ｘｊ）（ｊ＝１,８）、ＳＰ（ｘｊ）≪１（ｊ＝２,５）、ＳＰ（ｘｊ）≫１（ｊ＝３,６）及びＳＰ（ｘｊ≪１）（ｊ＝４,７）のｊにそれぞれ対応する定数（（ｆｆｆｆｆｆ００）１６等）を定数格納部１１６から抽出し、抽出した定数とＳＰ（ｘｊ）との論理積を以下のように計算する（ステップＳ１５）。
ＳＰ１１１０（ｘ１）←ＳＰ（ｘ１）＆（ｆｆｆｆｆｆ００）１６
ＳＰ０２２２（ｘ２）←ＳＰ（ｘ２）≪１＆（００ｆｆｆｆｆｆ）１６
ＳＰ３０３３（ｘ３）←ＳＰ（ｘ３）≫１＆（ｆｆ００ｆｆｆｆ）１６
ＳＰ４４０４（ｘ４）←ＳＰ（ｘ４≪１）＆（ｆｆｆｆ００ｆｆ）１６
ＳＰ０２２２（ｘ５）←ＳＰ（ｘ５）≪１＆（００ｆｆｆｆｆｆ）１６
ＳＰ３０３３（ｘ６）←ＳＰ（ｘ６）≫１＆（ｆｆ００ｆｆｆｆ）１６
ＳＰ４４０４（ｘ７）←ＳＰ（ｘ７≪１）＆（ｆｆｆｆ００ｆｆ）１６
ＳＰ１１１０（ｘ８）←ＳＰ（ｘ８）＆（ｆｆｆｆｆｆ００）１６  
論理積演算部１１７での演算結果ＳＰ１１１０（ｘ１），ＳＰ０２２２（ｘ２），ＳＰ３０３３（ｘ３），ＳＰ４４０４（ｘ４），ＳＰ０２２２（ｘ５），ＳＰ３０３３（ｘ６），ＳＰ４４０４（ｘ７），ＳＰ１１１０（ｘ８）は、排他的論理和演算部１１８に送られ、排他的論理和演算部１１８は、以下の排他的論理和演算によりＤとＵを求める（ステップＳ１６）。
【００３９】
【数１３】
2005128166.tif 000013
算出されたＤは排他的論理和演算部１２０に送られ、Ｕは３２ビット循環シフト部１１９及び排他的論理和演算部１２０に送られる。３２ビット循環シフト部１１９は、送られたＵを右に８ビット循環シフトして（Ｕ≫８）排他的論理和演算部１２０に送り（ステップＳ１７）、排他的論理和演算部１２０は、以下の演算によりデータ列（ｙ１,ｙ２,…,ｙ８）を算出し（ステップＳ１８）、そのデータ列（ｙ１,ｙ２,…,ｙ８）を換字置換結果として出力する（ステップＳ１９）。
【００４０】
【数１４】
2005128166.tif 000014
＜計算コスト・表の大きさ＞
以上説明したように、本形態では、ステップＳ１２において、８ビットデータの循環シフトを２回行い、ステップＳ１３において、ビット列格納部１１１の表１３０を８回参照している。また、３２ビットデータの循環シフトを、ステップＳ１４において４回行い、ステップＳ１７において１回行っている。さらに、スステップＳ１５において論理積を８回行い、排他的論理和をステップＳ１６において６回、ステップＳ１８において２回行っている。また、前述のように表１３０の大きさは１ＫＢである。
【００４１】
表参照回数                        ８
排他的論理和回数                  ８
３２ビットデータ循環シフト回数    ５
８ビットデータ循環シフト回数      ２
論理積回数                        ８
表の大きさ（ＫＢ）                １
このように、本形態では、計算コストをさほど増加させることなく、表の大きさを従来の４分の１にすることができた。
【００４２】
なお、本発明は上述の各実施の形態に限定されるものではない。例えば、上述の各実施の形態はＣａｍｅｌｌｉａ暗号への適用例であるため、Ｒ＝ＧＦ（２８）、ｎ＝ｍ＝８とし、置換行列Ｐを式（９）とし、換字関数間に式（１０）の関係があることとしたが、特にこれに限定されるものではなく、例えば、ＲとしてＧＦ（２）のその他の拡大体を用い、ｎ,ｍとしてその他の数を適用し、置換行列Ｐを各要素が∈｛０，１｝であるその他の行列を用いてもよく、換字関数としてｓｊ（ｘ）＝ｓ（ｅ（ｘ））≪ｔ（ｅは簡単に計算可能な関数）の関係を満たすものを用いてもよい。また、循環シフトを行う必要がない、或いは効率が悪い場合には、この循環シフトの代わりに、通常のシフト、加算、排他的論理和、論理和等を組み合わせた演算を行うこととしてもよい。
【００４３】
また、上述の各実施の形態では、１種類の関数ｓ（ｘ）にｘの取り得る値を代入した結果のみから構成されたビット列（ＳＰ）をビット列格納部に格納しておくこととしたが、複数の関数ｓ（ｘ）にｘの取り得る値を代入した結果から構成されたビット列（ＳＰ）をビット列格納部に格納しておき、これらを用いて換字置換処理を行ってもよい。
さらに、上述の各実施の形態では、関数ｓ（ｘ）として換字関数ｓ１（ｘ）を用いたが、関数ｓ（ｘ）としてその他の換字関数を用いてもよく、また、換字関数以外の関数を関数ｓ（ｘ）としてもよい。
【００４４】
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラム（換字変換プログラム）によって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００４５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体（換字変換記録媒体）に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００４６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００４７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００４８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００４９】
この発明により換字置換演算に必要な表の大きさを大幅に削減できるため（例えば、３２ビット語長環境では１／４）、携帯電話等の省メモリ環境でも、演算速度をそれほど落すことなく換字置換を実装できる。
【図面の簡単な説明】
【００５０】
【図１】第１の実施の形態における換字置換装置の機能構成を例示した図。
【図２】第１の実施の形態のビット列格納部に格納される表のデータ構成を例示した図。
【図３】換字置換装置のハードウェア構成を例示した図。
【図４】第１の実施の形態の換字置換方法を説明するためのフローチャート。
【図５】第２の実施の形態における換字置換装置の機能構成を例示した図。
【図６】第２の実施の形態のビット列格納部に格納される表のデータ構成を例示した図。
【図７】第２の実施の形態の換字置換方法を説明するためのフローチャート。
【符号の説明】
【００５１】
１０,１００  換字置換装置
１１,１１１  ビット列格納部
１４,１１４  ビット抽出部
１５  ６４ビット循環シフト部
１１５,１１９  ３２ビット循環シフト部
【図１】
2005128166.tif 000017
【図２】
2005128166.tif 000018
【図３】
2005128166.tif 000019
【図４】
2005128166.tif 000020
【図５】
2005128166.tif 000021
【図６】
2005128166.tif 000022
【図７】
2005128166.tif 000023