(57)【特許請求の範囲】
【請求項１】
入力された平文を暗号化して前記平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置であって、
前記平文のうちの特定の１桁を、前記平文の前記特定の１桁を除いた残りの各桁の数値、および前記平文と同時に入力された外部ツイークを用いて暗号化する単位ブロックツイーカブル暗号化手段と、
前記平文の前記暗号化された前記特定の１桁を含む各桁に対して予め決められた規則によって桁単位の置換を行うブロック置換手段と、
この単位ブロックツイーカブル暗号化手段およびブロック置換手段による処理を予め決められた回数繰り返させる暗号カウンタ更新手段と
を備えることを特徴とするフォーマット保存暗号化装置。
【請求項２】
前記単位ブロックツイーカブル暗号化手段が、
予め記憶された暗号鍵によって、前記平文の前記特定の１桁を除いた残りの各桁と前記外部ツイークとを結合した数値を暗号化して特定のビット数の出力値を出力するＡＥＳ暗号化部と、
前記ＡＥＳ暗号化部の出力値を用いて一時的暗号鍵を生成する一時的暗号鍵生成部と、
前記一時的暗号鍵を利用して前記平文の前記特定の１桁を暗号化するブロック暗号化部と
を備えることを特徴とする、請求項１に記載のフォーマット保存暗号化装置。
【請求項３】
前記ブロック暗号化部が、前記平文の前記特定の１桁をクヌースシャッフル（Knuth Shuffle）を用いて置換することによって暗号化するものであることを特徴とする、請求項２に記載のフォーマット保存暗号化装置。
【請求項４】
前記暗号化装置の前記ブロック置換手段が、前記平文の左端の１桁を除いた残りの各桁を１桁ずつ繰り上げ、前記平文の前記左端の１桁を右端とするものであることを特徴とする、請求項１に記載のフォーマット保存暗号化装置。
【請求項５】
請求項１ないし４のうちいずれか１項に記載のフォーマット保存暗号化装置から出力された暗号文を復号化して、前記暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置であって、
前記暗号文の、前記単位ブロックツイーカブル暗号化手段と同一位置の特定の１桁を、前記暗号文の前記特定の１桁を除いた残りの各桁の数値、および前記暗号文と同時に入力された前記暗号化装置と同一の外部ツイークを用いて復号化する単位ブロックツイーカブル復号化手段と、
前記暗号文の前記復号化された前記特定の１桁を含む各桁に対して前記ブロック置換手段とは逆の規則によって桁単位の置換を行うブロック逆置換手段と、
この単位ブロックツイーカブル復号化手段およびブロック逆置換手段による処理を前記暗号カウンタ更新手段と同一の回数繰り返させる復号カウンタ更新手段と
を備えることを特徴とするフォーマット保存復号化装置。
【請求項６】
前記単位ブロックツイーカブル復号化手段が、
予め記憶された復号鍵によって、前記暗号文の前記特定の１桁を除いた残りの各桁と前記外部ツイークとを結合した数値を復号化して特定のビット数の出力値を出力するＡＥＳ復号化部と、
前記ＡＥＳ復号化部の出力値を用いて一時的復号鍵を生成する一時的復号鍵生成部と、
前記一時的復号鍵を利用して前記暗号文の前記特定の１桁を復号化するブロック復号化部と
を備えることを特徴とする、請求項５に記載のフォーマット保存復号化装置。
【請求項７】
入力された平文を暗号化して前記平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置にあって、
前記平文のうちの特定の１桁を、前記平文の前記特定の１桁を除いた残りの各桁の数値、および前記平文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル暗号化手段が暗号化し、
前記平文の前記暗号化された前記特定の１桁を含む各桁に対して予め決められた規則によってブロック置換手段が桁単位の置換を行い、
この前記平文のうちの特定の１桁の暗号化および前記桁単位の置換の処理を暗号カウンタ更新手段が予め決められた回数繰り返させる
ことを特徴とするフォーマット保存暗号化方法。
【請求項８】
入力された暗号文を復号化して前記暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置にあって、
前記暗号文のうちの特定の１桁を、前記暗号文の前記特定の１桁を除いた残りの各桁の数値、および前記暗号文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル復号化手段が復号化し、
前記暗号文の前記復号化された前記特定の１桁を含む各桁に対して予め決められた規則によってブロック逆置換手段が桁単位の逆置換を行い、
この前記暗号文の特定の１桁の復号化および前記桁単位の逆置換の処理を復号カウンタ更新手段が予め決められた回数繰り返させる
ことを特徴とするフォーマット保存復号化方法。
【請求項９】
入力された平文を暗号化して前記平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置にあって、
前記フォーマット保存暗号化装置が備えるコンピュータに、
前記平文のうちの特定の１桁を、前記平文の前記特定の１桁を除いた残りの各桁の数値、および前記平文と同時に入力された外部ツイークを用いて暗号化する手順、
前記平文の前記暗号化された前記特定の１桁を含む各桁に対して予め決められた規則によって桁単位の置換を行う手順、
およびこの前記平文のうちの特定の１桁の暗号化および前記桁単位の置換の処理を予め決められた回数繰り返させる手順
を実行させることを特徴とするフォーマット保存暗号化プログラム。
【請求項１０】
入力された暗号文を復号化して前記暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置にあって、
前記フォーマット保存復号化装置が備えるコンピュータに、
前記暗号文のうちの特定の１桁を、前記暗号文の前記特定の１桁を除いた残りの各桁の数値、および前記暗号文と同時に入力された外部ツイークを用いて復号化する手順、
前記暗号文の前記復号化された前記特定の１桁を含む各桁に対して予め決められた規則によって桁単位の逆置換を行う手順、
およびこの前記暗号文の特定の１桁の復号化および前記桁単位の逆置換の処理を予め決められた回数繰り返させる手順
を実行させることを特徴とするフォーマット保存復号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はフォーマット保存暗号化装置、方法およびプログラム、復号化装置、方法およびプログラムに関し、特にメッセージ空間が非バイナリ空間、または通常のブロック暗号のブロック長より短いバイナリ空間である場合にも適用可能なフォーマット保存暗号化装置等に関する。
【背景技術】
【０００２】
ほとんど全ての企業は、コンピュータシステム上に業務で使用する大量の機密データを保持している。これらのデータは、業務上重要なデータであり、また個人情報保護という観点からも、外部に対して漏洩することは絶対にあってはならない。このため、新規に構築される業務システムについてはデータの暗号化が必須であるのはもちろんのこと、暗号化に対応していない既存の業務システムに対しても、データを暗号化して保持する機能を付加することが求められている。【０００３】
しかしながら、既存の業務システムでは、データ形式が予め定められている場合が多い。たとえばクレジットカード番号は、保護する必要性の高い重大な個人情報の最たる例の一つであるが、「１０進数１６桁」というデータ形式が予め定められている。既存の業務システムでは、その形式以外のデータはエラーとされて扱うことができない場合が多くある。電話番号、郵便番号、預金口座番号なども、これと同様である。【０００４】
そのため、平文とこれを暗号化した暗号文とでデータ形式が一致する暗号化方式が必要とされている。これをフォーマット保存暗号化という。同様に、暗号文と平文とでデータ形式が一致する復号化方式を、フォーマット保存復号化という。フォーマット保存暗号化／復号化を利用すれば、既存の業務システムに対して、変更を最小限に抑えつつデータの暗号化／復号化機能を付加することができる。【０００５】
通常の暗号化方式（ブロック暗号）では、メッセージ（平文と暗号文）は同一フォーマットのバイナリ（２進数）空間で表現される。たとえば、いずれも公知の暗号化方式であるＤＥＳのメッセージは６４ビット、ＡＥＳのメッセージは１２８ビットである。これに対してフォーマット保存暗号化では、たとえば「６４ビット以下のバイナリ空間」や「非バイナリ空間（たとえば１０進数や、２進数と１０進数の組み合わせなど）」のようなデータを取り扱う。【０００６】
このようなフォーマット保存暗号化について、たとえば以下のような各技術文献がある。非特許文献１は、フォーマット保存暗号化（Format-Preserving Encryption）の名称を世界的に広めた論文である。非特許文献２には、原理的にあらゆるメッセージ空間に対して安全なブロック暗号を実現しうる方式とされるクヌースシャッフル（Knuth Shuffle）、別名フィッシャー−イェーツシャッフル（Fisher-Yates Shuffle）が記載されているが、その計算量とメモリ量はメッセージ空間の線形オーダとなるため処理が膨大になりやすく、メッセージ空間のサイズが１００００を越える場合には適用困難である。【０００７】
非特許文献３には、メッセージが１０進数空間の場合に特化したブロック暗号について記載されている。非特許文献４には、非特許文献３の暗号方式に対する攻撃について記載されている。【０００８】
非特許文献５には、ｎビットのブロック暗号を用いてｎビット以下のバイナリ空間や非バイナリ空間のブロック暗号を実現する方法が記載されている。この非特許文献５に記載されている方法は、ターゲットとなるメッセージ空間の大きさが２ｎよりわずかに小さいときには効率よくかつ安全であるが、２ｎよりある程度小さくなると、効率もしくは安全性のいずれかが極端に低下するという問題がある。【０００９】
非特許文献６にも、非特許文献５と同様に、ファイステル（Feistel）型置換と呼ばれる置換処理をブロック暗号を用いて実現し、この置換処理を所定の回数平文に対して繰り返すことで暗号化を行うという方式が記載されている。また前述の非特許文献１にも、これと同様の方式が記載されている。【００１０】
図６は、非特許文献６に記載の暗号化方式の概要について示す説明図である。図６では、置換処理１サイクル分の処理について示している。ＡＥＳ暗号化部９０１は、Ｘｍ＋１，…，Ｘｄと、ラウンドカウンタｃｔｒ，外部ツイークｇｔ，平文桁数ｄを入力値として、これらをＡＥＳ暗号方式によって暗号化した値（１２８ビット）を出力する。剰余部９０２は、ＡＥＳ暗号化部９０１からの出力値をａ＾ｍ（ａのｍ乗）で除算した余りを出力する。加算部９０３は、Ｘ１，…，Ｘmと、剰余部９０２からの出力値を加算した値を出力する。そして、加算部９０３からの出力とＸｍ＋１，…，Ｘｄとを入れ替えて、１サイクル分の置換処理が終了する。これを所定の回数繰り返す。【００１１】
非特許文献７には、暗号化と復号にツイーク（tweak）と呼ばれる補助パラメータを用いるブロック暗号方式であるツイーカブルブロック暗号について記載されている。非特許文献８〜９には、このツイーカブルブロック暗号を利用して実現される様々なメッセージ空間でのブロック暗号について記載されている。これらの方式は、ツイーカブルブロック暗号が安全であれば、比較的効率よく高い安全性を保証することが可能である。【００１２】
また、ｎビットブロックのツイーカブルブロック暗号をｎビットブロック暗号から実現する方法についても記載されている。従って、非特許文献８に記載の方式で、ｎビットブロック暗号から２ｎビットブロック暗号を作る方式を得ることができ、また非特許文献９に記載の方式で、ｎビットブロック暗号からｎ＋１ビット以上のブロック暗号を作る方式を得ることができる。【００１３】
これら非特許文献８〜９に記載の方式によれば、パラメータによっては、非特許文献１および６などのようなファイステル型置換とブロック暗号を組み合わせた方式よりも、効率よく高い安全性をもったフォーマット保存暗号化を実現することが可能である。非特許文献１０〜１３については後述する。【００１４】
特許文献１には、データベースに格納されたデータをトラフィック解析から保護するという技術が記載されている。特許文献２には、データベースに格納されたデータのキャラクターセットを変更して難読化するという技術が記載されている。特許文献３〜４には、外部ツイーク（調整値）を利用したブロック暗号化方式が記載されており、上記非特許文献８〜９に対応する特許出願である。特許文献５には、ＭＰＥＧ４ファイルのフォーマットを維持しつつ暗号化を行うという技術が記載されている。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００９−０４８６３６号公報
【特許文献２】特開２０１０−１２９０８９号公報
【特許文献３】再特ＷＯ２００８０１８３０３号公報
【特許文献４】再特ＷＯ２００９１２８３７０号公報
【特許文献５】特表２００７−５１８２９４号公報
【非特許文献】
【００１６】
【非特許文献１】Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, Till Stegers: Format-Preserving Encryption. SAC 2009, pp. 295-312.
【非特許文献２】Fisher-Yates shuffle.、インターネット＜URL：http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle＞
【非特許文献３】L. Granboulan, E. Levieil, and G. Piret. Pseudorandom permutation families over Abelian groups. In Fast Software Encryption 2006, volume 4047 of LNCS, pages 57-77. Springer-Verlag, 2006.
【非特許文献４】Thomas Baigneres, Jacques Stern, Serge Vaudenay: Linear Cryptanalysis of Non Binary Ciphers. Selected Areas in Cryptography 2007: 184-211
【非特許文献５】Ciphers with Arbitrary Finite Domains. John Black and Phillip Rogaway. CT-RSA 2002, The Cryptographer's Track at the RSA Conference, 2002, San Jose, CA, USA, February 18-22, 2002, Proceedings. Lecture Notes in Computer Science 2271, pp. 114-130.
【非特許文献６】M. Bellare, P. Rogaway, T.Spies. Format-preserving Feistel-based Encryption Mode, NIST Submission、インターネット＜URL：http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf＞
【非特許文献７】M. Liskov, R. Rivest, D. Wagner, Tweakable Block Ciphers, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings. Lecture Notes in Computer Science 2442 Springer 2002, pp. 31-46.
【非特許文献８】Kazuhiko Minematsu: Beyond-Birthday-Bound Security Based on Tweakable Block Cipher. Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, February 22-25, 2009, Revised Selected Papers. Lecture Notes in Computer Science 5665, pp.308-326.
【非特許文献９】Kazuhiko Minematsu, Tetsu Iwata: Building Blockcipher from Tweakable Blockcipher: Extending FSE 2009 Proposal. Liqun Chen (Ed.): Cryptography and Coding - 13th IMA International Conference, IMACC 2011, Oxford, UK, December 12-15, 2011. Proceedings. Lecture Notes in Computer Science 7089 Springer 2011, pp. 391-412.
【非特許文献１０】L. Granboulan and T. Pornin. Perfect Block Ciphers with Small Blocks. Alex Biryukov (Ed.): Fast Software Encryption, 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, March 26-28, 2007, Revised Selected Papers. Lecture Notes in Computer Science 4593 Springer 2007, pp. 452-465.
【非特許文献１１】KATAN & amp; KTANTAN - A Family of Small and Efficient Hardware-Oriented Block Ciphers. C. D. Canni`ere and O. Dunkelman and M. Knezevi´c, Christophe Clavier, Kris Gaj (Eds.): Cryptographic Hardware and Embedded Systems - CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6-9, 2009, Proceedings. Lecture Notes in Computer Science 5747 Springer 2009. pp. 272-288.?
【非特許文献１２】Rivest, R. L. (1994). The RC5 Encryption Algorithm. In the Proceedings of the Second International Workshop on Fast Software Encryption (FSE) 1994, pp.86-96.
【非特許文献１３】SEA: a Scalable Encryption Algorithm for Small Embedded Applications F.-X. Standaert, G. Piret, N. Gershenfeld, and J.-J Quisquater. in the Proceedings of CARDIS 2006, LNCS, vol 3928, pp 222-236, Tarragona, Spain, April 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１７】
前述の通り、非特許文献８〜９（および特許文献３〜４）に記載の方式によれば、効率よく高い安全性をもったフォーマット保存暗号化を実現することは可能である。しかしながら、これらの方式は、ｎビットブロック暗号を用いてｎビットより大きいブロックサイズを実現するというものである。従って、全てのメッセージ空間に対して適用可能なものではない。【００１８】
特に、メッセージ空間が１０進数である場合や、ビットサイズがｎビット（典型的にはＡＥＳの１２８ビット）より小さい場合には適用できない。非特許文献５〜６に記載の方式は１０進数のメッセージ空間に対しても適用可能であるが、前述のように効率や安全性の面で問題がある。特許文献１〜５や非特許文献１〜１３に記載のその他の技術も、この問題を解決するものではない。【００１９】
本発明の目的は、メッセージ空間が非バイナリ空間、または通常のブロック暗号のブロック長より短いバイナリ空間である場合においても、入力の長さやキャラクタ集合などのフォーマットを保ったまま効率的かつ安全な暗号化／復号化を可能とするフォーマット保存暗号化装置、方法およびプログラム、復号化装置、方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２０】
上記目的を達成するため、本発明に係るフォーマット保存暗号化装置は、入力された平文を暗号化して平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置であって、平文のうちの特定の１桁を、平文の特定の１桁を除いた残りの各桁の数値、および平文と同時に入力された外部ツイークを用いて暗号化する単位ブロックツイーカブル暗号化手段と、平文の暗号化された特定の１桁を含む各桁に対して予め決められた規則によって桁単位の置換を行うブロック置換手段と、この単位ブロックツイーカブル暗号化手段およびブロック置換手段による処理を予め決められた回数繰り返させる暗号カウンタ更新手段とを備えることを特徴とする。【００２１】
上記目的を達成するため、本発明に係るフォーマット保存復号化装置は、請求項１ないし４のうちいずれか１項に記載のフォーマット保存暗号化装置から出力された暗号文を復号化して、暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置であって、暗号文の、単位ブロックツイーカブル暗号化手段と同一位置の特定の１桁を、暗号文の特定の１桁を除いた残りの各桁の数値、および暗号文と同時に入力された暗号化装置と同一の外部ツイークを用いて復号化する単位ブロックツイーカブル復号化手段と、暗号文の復号化された特定の１桁を含む各桁に対してブロック置換手段とは逆の規則によって桁単位の置換を行うブロック逆置換手段と、この単位ブロックツイーカブル復号化手段およびブロック逆置換手段による処理を暗号カウンタ更新手段と同一の回数繰り返させる復号カウンタ更新手段とを備えることを特徴とする。【００２２】
上記目的を達成するため、本発明に係るフォーマット保存暗号化方法は、入力された平文を暗号化して平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置にあって、平文の左端の１桁を、平文の左端の１桁を除いた残りの各桁の数値、および平文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル暗号化手段が暗号化し、平文の左端の１桁を除いた残りの各桁、および暗号化された平文の左端の１桁に対して予め決められた規則によってブロック置換手段が桁単位の置換を行い、この平文の左端の１桁の暗号化および桁単位の置換の処理をカウンタ更新手段が予め決められた回数繰り返させることを特徴とする。【００２３】
上記目的を達成するため、本発明に係るフォーマット保存復号化方法は、入力された暗号文を復号化して暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置にあって、暗号文の左端の１桁を、暗号文の左端の１桁を除いた残りの各桁の数値、および暗号文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル復号化手段が復号化し、暗号文の左端の１桁を除いた残りの各桁、および復号化された暗号文の左端の１桁に対して予め決められた規則によってブロック逆置換手段が桁単位の逆置換を行い、この暗号文の左端の１桁の復号化および桁単位の逆置換の処理をカウンタ更新手段が予め決められた回数繰り返させることを特徴とする。【００２４】
上記目的を達成するため、本発明に係るフォーマット保存暗号化プログラムは、入力された平文を暗号化して平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置にあって、フォーマット保存暗号化装置が備えるコンピュータに、平文の左端の１桁を、平文の左端の１桁を除いた残りの各桁の数値、および平文と同時に入力された外部ツイークを用いて暗号化する手順、平文の左端の１桁を除いた残りの各桁、および暗号化された平文の左端の１桁に対して予め決められた規則によって桁単位の置換を行う手順、およびこの平文の左端の１桁の暗号化および桁単位の置換の処理を予め決められた回数繰り返させる手順を実行させることを特徴とする。【００２５】
上記目的を達成するため、本発明に係るフォーマット保存復号化プログラムは、入力された暗号文を復号化して暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置にあって、フォーマット保存復号化装置が備えるコンピュータに、暗号文の左端の１桁を、暗号文の左端の１桁を除いた残りの各桁の数値、および暗号文と同時に入力された外部ツイークを用いて復号化する手順、暗号文の左端の１桁を除いた残りの各桁、および復号化された暗号文の左端の１桁に対して予め決められた規則によって桁単位の逆置換を行う手順、およびこの暗号文の左端の１桁の復号化および桁単位の逆置換の処理を予め決められた回数繰り返させる手順を実行させることを特徴とする。
【発明の効果】
【００２６】
本発明は、上述したように、平文の特定の１桁を暗号化してから各桁を入れ替える処理を繰り返すことによって暗号化を行い、この逆の処理で復号化を行うように構成したので、桁数に関わらず、また２進数以外であっても、効率的かつ安全な暗号化／復号化の処理が可能となる。【００２７】
これによって、メッセージ空間が非バイナリ空間、または通常のブロック暗号のブロック長より短いバイナリ空間である場合においても、入力の長さやキャラクタ集合などのフォーマットを保ったまま効率的かつ安全な暗号化／復号化が可能であるという優れた特徴を持つフォーマット保存暗号化装置、方法およびプログラム、復号化装置、方法およびプログラムを提供することができる。
【図面の簡単な説明】
【００２８】
【図１】本発明の実施形態に係る暗号化システムの構成について示す説明図である。
【図２】図１に示した単位ブロックツイーカブル暗号化手段の、より詳細な構成について示す説明図である。
【図３】図１に示したブロック置換手段によって行われる処理について示す説明図である。
【図４】図１で示した暗号化装置の動作について示すフローチャートである。
【図５】図１で示した復号化装置の動作について示すフローチャートである。
【図６】非特許文献６に記載の暗号化方式の概要について示す説明図である。
【発明を実施するための形態】
【００２９】
（実施形態）
以下、本発明の実施形態の構成について添付図１に基づいて説明する。
最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
本実施形態に係るフォーマット保存暗号化装置（暗号化装置１０）は、入力された平文を暗号化して平文と同一のデータ形式の暗号文を出力する暗号化装置である。
この暗号化装置１０は、平文のうちの特定の１桁を、平文の特定の１桁を除いた残りの各桁の数値、および平文と同時に入力された外部ツイークを用いて暗号化する単位ブロックツイーカブル暗号化手段１０１と、平文の暗号化された特定の１桁を含む各桁に対して予め決められた規則によって桁単位の置換を行うブロック置換手段１０２と、この単位ブロックツイーカブル暗号化手段およびブロック置換手段による処理を予め決められた回数繰り返させる暗号カウンタ更新手段１０３とを備える。
【００３０】
また、単位ブロックツイーカブル暗号化手段１０１は、予め記憶された暗号鍵によって、平文の特定の１桁を除いた残りの各桁と外部ツイークとを結合した数値を暗号化して特定のビット数の出力値を出力するＡＥＳ暗号化部１０１ａと、ＡＥＳ暗号化部の出力値を用いて一時的暗号鍵を生成する一時的暗号鍵生成部１０１ｂと、一時的暗号鍵を利用して平文の特定の１桁を暗号化するブロック暗号化部１０１ｃとを備える。
【００３１】
ここで、ブロック暗号化部１０１ｃが、平文の特定の１桁をクヌースシャッフル（Knuth Shuffle）を用いて置換することによって暗号化するものである。そして、ブロック置換手段１０２が、平文の左端の１桁を除いた残りの各桁を１桁ずつ繰り上げ、平文の左端の１桁を右端とするものである。
【００３２】
本実施形態に係るフォーマット保存復号化装置（復号化装置２０）は、暗号化装置１０から出力された暗号文を復号化して、暗号文と同一のデータ形式の平文を出力する復号化装置である。
この復号化装置２０は、暗号文の、単位ブロックツイーカブル暗号化手段１０１と同一位置の特定の１桁を、暗号文の特定の１桁を除いた残りの各桁の数値、および暗号文と同時に入力された暗号化装置と同一の外部ツイークを用いて復号化する単位ブロックツイーカブル復号化手段２０１と、暗号文の復号化された特定の１桁を含む各桁に対してブロック置換手段１０２とは逆の規則によって桁単位の置換を行うブロック逆置換手段２０２と、この単位ブロックツイーカブル復号化手段およびブロック逆置換手段による処理を暗号カウンタ更新手段と同一の回数繰り返させる復号カウンタ更新手段２０３とを備える。
【００３３】
また、単位ブロックツイーカブル復号化手段２０１が、予め記憶された復号鍵によって、暗号文の特定の１桁を除いた残りの各桁と外部ツイークとを結合した数値を復号化して特定のビット数の出力値を出力するＡＥＳ復号化部と、ＡＥＳ復号化部の出力値を用いて一時的復号鍵を生成する一時的復号鍵生成部と、一時的復号鍵を利用して暗号文の特定の１桁を復号化するブロック復号化部とを備える。
【００３４】
この構成を備えることにより、暗号化装置１０および復号化装置２０は、メッセージ空間が非バイナリ空間、または通常のブロック暗号のブロック長より短いバイナリ空間である場合においても、入力の長さやキャラクタ集合などのフォーマットを保ったまま効率的かつ安全な暗号化／復号化が可能となる。
以下、これをより詳細に説明する。
【００３５】
図１は、本発明の実施形態に係る暗号化システム１の構成について示す説明図である。暗号化システム１は、暗号化装置１０と復号化装置２０とによって構成される。暗号化装置１０は、入力された平文を暗号化して、暗号文を出力する。復号化装置２０は、入力された暗号文を復号化して、平文を出力する。
【００３６】
暗号化装置１０は、一般的なコンピュータ装置としての構成を備える。即ち、クライアント端末１０は、コンピュータプログラムを実行する主体となるプロセッサ１１と、データを記憶する記憶手段１２と、ユーザからの操作を受け付ける（典型的にはキーボードなどの）入力手段１３と、ユーザに処理結果を提示する（典型的にはディスプレイやプリンタなどの）出力手段１４とを備える。
【００３７】
復号化装置２０も同様に、一般的なコンピュータ装置としての構成を備える。即ち、暗号化装置１０と同様のプロセッサ２１と、記憶手段２２と、入力手段２３と、出力手段２４とを備える。これらの構成および動作については後述する。
【００３８】
（暗号化装置の構成）
プロセッサ１１は、暗号化プログラムが動作することにより、後述の単位ブロックツイーカブル暗号化手段１０１、ブロック置換手段１０２、およびカウンタ更新手段１０３の各々として動作する。また記憶手段１２には、暗号鍵１１１が予め記憶されている。
【００３９】
入力手段１３から、暗号化の対象となるａ進数ｄ桁の平文と、外部ツイークと、ラウンドカウンタの初期値＝１が入力される。ここでａ（ｉ）とメッセージ空間ＭＳＧには、以下の数１が成立する。即ち、メッセージ空間ＭＳＧはａ進数ｄ桁の空間である。
【００４０】
【数１】
0006007975.tif 000002
【００４１】
外部ツイークは、必要に応じてユーザが付加することができる。たとえば平文の桁数ｄの２進数表現、使用している秘密鍵のＩＤ、処理日時、暗号化装置１０のシリアル番号などを外部ツイークとして利用することができる。ただし、出力された暗号文を復号化する際に、暗号化処理時に使用した外部ツイークが一意に求められることが必要となる。この条件が満たせない場合には、外部ツイークを付加しないものとする。
【００４２】
単位ブロックツイーカブル暗号化手段１０１は、以上で入力されたａ進数ｄ桁のＸ＝（Ｘ［１］，…，Ｘ［ｄ］）、外部ツイーク、およびラウンドカウンタを入力として、Ｘ［１］を暗号化する。Ｘ［１］はａ進数１桁の数字を表す。ラウンドカウンタの値が初期値１である場合には、上記Ｘは平文に相当する。Ｘ［１］の暗号化には、以下の数２に示す、ａ進数１桁をブロックとしたツイーカブルブロック暗号の暗号化関数ＴＥを用いる。ここでＭは平文、Ｋは暗号鍵１１１、Ｔはツイークを表す。ＭおよびＣの取りうる空間は、いずれもａ進数１桁である。
【００４３】
【数２】
0006007975.tif 000003
【００４４】
より具体的には、単位ブロックツイーカブル暗号化手段１０１による暗号化は、外部ツイークをｇｔ、ラウンドカウンタをｃｔｒとすると、以下の数３に示す演算を行った後、（Ｖ，Ｘ［２］，…，Ｘ［ｄ］）を出力値とする。
【００４５】
【数３】
0006007975.tif 000004
【００４６】
即ち、単位ブロックツイーカブル暗号化手段１０１は、外部ツイークｇｔ、ラウンドカウンタｃｔｒ、および入力値の右ｄ−１桁（Ｘ［２］，…，Ｘ［ｄ］）をＴＥのツイークとしてＸ［１］を暗号化した結果の出力値Ｖを（Ｘ［２］，…，Ｘ［ｄ］）と連結し、これを出力値とする。
【００４７】
このＴＥは、一般的には以下の数４に示すように表すことができる。ここで、ＫｅｙＧｅｎは秘密鍵Ｋと（ｃｔｒ、ｇｔ、Ｘ［２］，…，Ｘ［ｄ］）を入力値として一時的鍵ＤＫを生成する関数であり、ＢｌｏｃｋＥｎｃはこの一時的鍵ＤＫを利用してＸ［１］を暗号化する関数である。
【００４８】
【数４】
0006007975.tif 000005
【００４９】
（ＡＥＳ暗号方式による単位ブロックツイーカブル暗号化手段）
以下、公知のＡＥＳ（Advanced Encryption Standard）暗号方式を利用して、ａ＝１０（即ち１０進数）であり、ラウンドカウンタ、外部ツイーク、Ｘ［１］，…，Ｘ［ｄ−１］を連結した系列が１２８ビット以下で表現可能な場合について、上記ＫｅｙＧｅｎおよびＢｌｏｃｋＥｎｃの実際の処理について考える。
【００５０】
図２は、図１に示した単位ブロックツイーカブル暗号化手段１０１の、より詳細な構成について示す説明図である。単位ブロックツイーカブル暗号化手段１０１は、鍵Ｋ（暗号鍵１１１）によって（ｃｔｒ、ｇｔ、Ｘ［２］，…，Ｘ［ｄ］）をＡＥＳ暗号方式によって暗号化するＡＥＳ暗号化部１０１ａと、ＡＥＳ暗号化部１０１ａの１２８ビット出力を用いて一時的鍵ＤＫを生成する一時的鍵生成部１０１ｂと、一時的鍵生成部１０１ｂから出力された一時的鍵ＤＫを利用してＸ［１］を暗号化するブロック暗号化部１０１ｃによって構成される。ＡＥＳ暗号化部１０１ａと一時的鍵生成部１０１ｂとが上記でいうＫｅｙＧｅｎに該当し、ブロック暗号化部１０１ｃがＢｌｏｃｋＥｎｃに該当する。
【００５１】
ＫｅｙＧｅｎは、ＡＥＳの１２８ビット出力を用いて、以下の数５に示すＤＫを生成する関数である。ただし、ｉ＝０，…，９について、Ｋ１０Ｋｅｙ［ｉ］は非負整数であり、かつ整数集合｛０，…，９｝上でほぼ一様に分布することが求められる。Ｋ１０Ｋｅｙ［０］は常に０である。
【００５２】
【数５】
0006007975.tif 000006
【００５３】
ＡＥＳの１２８ビット出力が一様乱数であると仮定すれば、上記のような分布のＫ１０Ｋｅｙ［ｉ］は、以下の数６に示す処理によって生成することが可能である。ここで、ＡＥＳの１２８ビット出力が実際に使うのは出力の前半の６４ビット、および最後尾の８ビットであるので、これらを各々Ｂ，Ｗとする。また、いずれも正の整数であるａおよびｂについてａ／ｂをａ÷ｂ、Ｗのｉビット目をＷ（ｉ）、第ｉ〜ｊ（i-th to j-th）ビット系列をＷ（ｉ，ｊ）とする。そして、バイナリ系列Ｂに対する数６の最初の演算は、Ｂを０〜２＾６４−１までの整数とみなした上での剰余算である。本明細書では、数式以外の行では「ＡのＢ乗」を「Ａ＾Ｂ」と表す。
【００５４】
【数６】
0006007975.tif 000007
【００５５】
ここで、βｉはＶ  ｍｏｄ  ８１の３進数展開、γｊはＶ  ｍｏｄ  ２５の５進数展開に相当する。このことと、１４１７５＝（３＾４）×（５＾２）×７であることと、中国人剰余定理（Chinese Reminder Theorem）とより、以下の数７に示すＶと（β１，…，β４，γ１，γ２，δ）は一対一対応となる。かつＷは、全ての２８通りの値をとりうるので、（Ｖ，Ｗ）と（Ｋ１０Ｋｅｙ［０］，…，Ｋ１０Ｋｅｙ［９］）は一対一対応となる。
【００５６】
【数７】
0006007975.tif 000008
【００５７】
このことより、（Ｖ，Ｗ）が数７に示す整数集合Ｚ上で一様乱数であるなら、Ｋ１０Ｋｅｙ［ｉ］の各要素は独立な一様乱数となる。ここで、ＡＥＳがランダム関数であるなら、ＢおよびＷは独立した一様乱数であり、Ｖと整数集合Ｚ上の一様乱数との平均距離は、以下の数８に示すように計算される。即ち、Ｋ１０Ｋｅｙは実用上問題ないほど一様乱数に近い。
【００５８】
【数８】
0006007975.tif 000009
【００５９】
次に、ブロック暗号化部１０１ｃ、即ちＢｌｏｃｋＥｎｃの実際の処理について考える。ＢｌｏｃｋＥｎｃは、上記のＫｅｙＧｅｎが出力したＤＫ＝（Ｋ１０Ｋｅｙ［０］，…，Ｋ１０Ｋｅｙ［９］）を鍵として、Ｚ１０＝整数集合｛０，…，９｝上での一様なランダム置換を実現する。ｘ∈Ｚ１０を入力、ＤＫ＝（Ｋ１０Ｋｅｙ［０］，…，Ｋ１０Ｋｅｙ［９］）を鍵とすると、ＢｌｏｃｋＥｎｃとしては以下の数９に示すクヌースシャッフル（Knuth Shuffle）、別名フィッシャー−イェーツシャッフル（Fisher-Yates Shuffle）と呼ばれる方法（非特許文献２）を利用することができる。
【００６０】
【数９】
0006007975.tif 000010
【００６１】
以上、ａ＝１０（即ち１０進数）の場合のＫｅｙＧｅｎおよびＢｌｏｃｋＥｎｃをＡＥＳによって構成する方法について説明した。ａが１０以外の値である場合には、ＤＫ＝（Ｋ１０Ｋｅｙ［０］，…，Ｋ１０Ｋｅｙ［ａ−１］）とし、Ｋ１０Ｋｅｙ［ｉ］が整数集合｛０，…，ｉ｝上でほぼ一様となるようにＫｅｙＧｅｎを構成し、さらに数９の９をａ−１に置換して実行すればよい。
【００６２】
ＫｅｙＧｅｎは、数６のように定義して実現することも可能ではあるが、よりシンプルには、たとえばＡＥＳ出力の十分長い所定長の部分系列Ｓｅｑ［ｉ］を利用して、以下の数１０のように表すこともできる。
【００６３】
【数１０】
0006007975.tif 000011
【００６４】
（ブロック置換手段）
図３は、図１に示したブロック置換手段１０２によって行われる処理について示す説明図である。ブロック置換手段１０２は、ｄ個のキャラクタ単位の置換（シャッフル）処理を行う。この置換処理は、例えば以下の数１１に示す左巡回シフトを用いてもよいし、これと逆方向に各データを置換する右巡回シフトを用いてもよい。但し、入出力が全く同じになる置換（identity permutation）は、安全性の観点上、用いるべきではない。
【００６５】
【数１１】
0006007975.tif 000012
【００６６】
カウンタ更新手段１０３は、入力されたラウンドカウンタ値を、予め与えられた値rと比較し、ラウンドカウンタ値＜ｒの場合には、このラウンドカウンタ値に１を加算し、ブロック置換手段１０２の出力であるａ進数ｄ桁の値を単位ブロックツイーカブル暗号化手段１０１に入力する。ラウンドカウンタ値＝ｒの場合には、ブロック置換手段１０２の出力値を暗号文として出力手段１４に出力する。
【００６７】
ここで、ラウンドカウンタ値＝ｒの場合のブロック置換手段１０２の動作は、暗号の安全性を左右するものではない。このため、ラウンドカウンタ値＝ｒの場合には、直前の単位ブロックツイーカブル暗号化手段１０１の出力をそのまま暗号文として出力するようにしてもよい。この場合は即ち、ブロック置換手段１０２の出力値に逆置換を適用して出力することに相当する。
【００６８】
図４は、図１で示した暗号化装置１０の動作について示すフローチャートである。入力手段１３を介して暗号化の対象となるａ進数ｄ桁の平文と、外部ツイークと、ラウンドカウンタの初期値＝１とが入力されると（ステップＳ１０１）、単位ブロックツイーカブル暗号化手段１０１は、Ｘ［１］に対して数３に示す暗号化の演算を行い、その出力値ＶをＸ［２］，…，Ｘ［ｄ］と連結して（Ｖ，Ｘ［２］，…，Ｘ［ｄ］）を出力する（ステップＳ１０２）。ここでＸ［１］は、以下の数１２の関係が成立する。
【００６９】
【数１２】
0006007975.tif 000013
【００７０】
続いて、ブロック置換手段１０２が、単位ブロックツイーカブル暗号化手段１０１から出力された（Ｖ，Ｘ［２］，…，Ｘ［ｄ］）に対して左巡回シフトもしくは右巡回シフトなどのようなブロック置換処理を行う（ステップＳ１０３）。
【００７１】
そして、カウンタ更新手段１０３は、ラウンドカウンタ値を予め与えられた値rと等しいか否かを判断する（ステップＳ１０４）。ラウンドカウンタ値＜ｒであれば、ラウンドカウンタ値を＋１加算して（ステップＳ１０５）ステップＳ１０２に戻る。ラウンドカウンタ値＝ｒであれば、ブロック置換手段１０２からの出力値を暗号文として出力手段１４に出力して（ステップＳ１０６）処理を終了する。
【００７２】
（復号化装置の構成）
図１に戻って、復号化装置２０のプロセッサ２１は、復号化プログラムが動作することにより、後述の単位ブロックツイーカブル復号化手段２０１、ブロック逆置換手段２０２、およびカウンタ更新手段２０３の各々として動作する。
【００７３】
また記憶手段２２には、復号鍵２１１が予め記憶されている。この復号鍵２１１は、暗号鍵１１１を用いて暗号化された暗号文を復号化できるものであれば何でもよい。たとえば、暗号鍵１１１が公開鍵暗号方式でいう秘密鍵であり、復号鍵２１１がこれに対応する公開鍵であってもよいし、これらの秘密鍵と公開鍵とを逆にしてもよい。また、暗号化装置１０と復号化装置２０とを同一のコンピュータとして、暗号鍵１１１と復号鍵２１１とを同一の共通鍵としてもよい。
【００７４】
単位ブロックツイーカブル復号化手段２０１およびブロック逆置換手段２０２は各々、暗号化装置１０の単位ブロックツイーカブル暗号化手段１０１およびブロック置換手段１０２の逆演算を行う。
【００７５】
入力手段２３から、復号化の対象となるａ進数ｄ桁の暗号文と、外部ツイークと、ラウンドカウンタの初期値＝１が入力される。ここでａ（ｉ）とメッセージ空間ＭＳＧには、前述の数１と同一の関係が成立する。即ち、メッセージ空間ＭＳＧはａ進数ｄ桁の空間である。
【００７６】
単位ブロックツイーカブル復号手段２０１は、単位ブロックツイーカブル暗号化手段１０１に対応した復号処理を行う。数２に示した暗号化関数ＴＥに対応する復号化関数をＴＤとすると（各記号の定義は数２と同一）、復号化関数ＴＤは以下の数１３のように示される。この数１３に示される関係が、全てのＫ，Ｔ，Ｃについて成立すればよい。
【００７７】
【数１３】
0006007975.tif 000014
【００７８】
図２で示したように、単位ブロックツイーカブル暗号化手段１０１の暗号化関数ＴＥが前述の数４で示したＫｅｙＧｅｎおよびＢｌｏｃｋＥｎｃで構成されている場合、単位ブロックツイーカブル復号手段２０１の復号化関数ＴＤもこれと同一のＫｅｙＧｅｎと、クヌースシャッフルの逆置換を行うＢｌｏｃｋＤｅｃとによって構成される。ＢｌｏｃｋＤｅｃの処理は、以下の数１４によって示される。
【００７９】
【数１４】
0006007975.tif 000015
【００８０】
ブロック逆置換手段２０２は、ｄ個のキャラクタ単位の置換（シャッフル）処理を行う。かつ、ブロック置換手段１０２の逆関数である。たとえば、ブロック置換手段１０２が左巡回シフトを用いている場合は、ブロック逆置換手段２０２は右巡回シフトを用いる。そして、カウンタ更新手段２０３の動作は、カウンタ更新手段１０３と同一である。
【００８１】
図５は、図１で示した復号化装置２０の動作について示すフローチャートである。入力手段２３を介して復号化の対象となる（暗号化装置１０から出力された）ａ進数ｄ桁の平文と、外部ツイークと、ラウンドカウンタの初期値＝１とが入力されると（ステップＳ２０１）、単位ブロックツイーカブル復号化手段２０１は、Ｘ［１］に対して図４のステップＳ１０１とは逆の復号化の演算を行い、その出力値ＶをＸ［２］，…，Ｘ［ｄ］と連結して（Ｖ，Ｘ［２］，…，Ｘ［ｄ］）を出力する（ステップＳ２０２）。
【００８２】
続いて、ブロック逆置換手段２０２が、単位ブロックツイーカブル復号化手段２０１から出力された（Ｖ，Ｘ［２］，…，Ｘ［ｄ］）に対してブロック置換手段１０２とは逆方向のブロック置換処理（即ちブロック逆置換処理）を行う（ステップＳ２０３）。
【００８３】
そして、カウンタ更新手段２０３は、ラウンドカウンタ値を予め与えられた値rと等しいか否かを判断する（ステップＳ２０４）。ラウンドカウンタ値＜ｒであれば、ラウンドカウンタ値を＋１加算して（ステップＳ２０５）ステップＳ２０２に戻る。ラウンドカウンタ値＝ｒであれば、ブロック置換手段２０２からの出力値を平文として出力手段２４に出力して（ステップＳ２０６）処理を終了する。
【００８４】
（実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。本実施形態に係るフォーマット保存暗号化方法は、入力された平文を暗号化して平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置１０にあって、平文の左端の１桁を、平文の左端の１桁を除いた残りの各桁の数値、および平文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル暗号化手段が暗号化し（図４・ステップＳ１０２）、平文の左端の１桁を除いた残りの各桁、および暗号化された平文の左端の１桁に対して予め決められた規則によってブロック置換手段が桁単位の置換を行い（図４・ステップＳ１０３）、この平文の左端の１桁の暗号化および桁単位の置換の処理をカウンタ更新手段が予め決められた回数繰り返させる（図４・ステップＳ１０４〜１０５）。
【００８５】
また、本実施形態に係るフォーマット保存復号化方法は、入力された暗号文を復号化して暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置２０にあって、暗号文の左端の１桁を、暗号文の左端の１桁を除いた残りの各桁の数値、および暗号文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル復号化手段が復号化し（図５・ステップＳ２０２）、暗号文の左端の１桁を除いた残りの各桁、および復号化された暗号文の左端の１桁に対して予め決められた規則によってブロック逆置換手段が桁単位の逆置換を行い（図５・ステップＳ２０３）、この暗号文の左端の１桁の復号化および桁単位の逆置換の処理をカウンタ更新手段が予め決められた回数繰り返させる（図５・ステップＳ２０４〜２０５）。
【００８６】
ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータであるフォーマット保存暗号化装置１０および復号化装置２０に実行させるようにしてもよい。本プログラムは、非一時的な記録媒体、例えば、ＤＶＤ、ＣＤ、フラッシュメモリ等に記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。
この動作により、本実施形態は以下のような効果を奏する。
【００８７】
本実施形態によれば、バイナリ空間に対して高い安全性をもって運用されているブロック暗号方式を利用して、桁数に関わらず、また２進数以外であっても、暗号化／復号化の処理が可能となる。
【００８８】
上記で説明した方式では、ｄ桁の平文のうち常に左端の１桁に対して残りのｄ−１桁をツイークの一部としたブロック暗号化を施しているため、常にラウンドごとの入力が左端の１桁へ影響を与える。このラウンド構造が逆関数を持つので、全体の処理もまた逆関数を持つ。即ち、数１で示したメッセージ空間ＭＳＧに対するブロック暗号を構成することができる。
【００８９】
この方式の安全性については、部品として用いているａ（ｉ）進数１桁をブロックとしたツイーカブル暗号化（ｉ＝１，…，ｄ）が安全であれば、これを２ｄ回繰り返すことにより、｜ＭＳＧ｜＾（ｄ／２）より十分小さい回数の選択平文攻撃に対して理論的に安全であることが証明される。さらにこの繰り返しを３ｄ回に増やせば、｜ＭＳＧ｜＾（ｄ／２）より十分小さい回数の選択暗号文攻撃に対しても理論的に安全であることが証明される。ここで、｜ＭＳＧ｜はメッセージ空間ＭＳＧの大きさである。
【００９０】
そして、ａ（ｉ）進数１桁をブロックとしたツイーカブルブロック暗号は、ａ（ｉ）が小さい場合、通常のブロック暗号とＺａ（ｉ）上のクヌースシャッフルとの組み合わせにより、理論的に安全に構成することが可能となる。
【００９１】
もちろん、単位ブロックツイーカブル暗号化手段１０１が、Ｘ［１］以外、即ち平文の１桁目以外の桁を暗号化するものであってもよく、またブロック置換手段１０２が左巡回シフトや右巡回シフト以外の法則によって各データを置換するものであってもよい。この場合も、単位ブロックツイーカブル復号化手段２０１およびブロック逆置換手段２０２は、各々単位ブロックツイーカブル暗号化手段１０１およびブロック置換手段１０２の逆処理を行うものである。
【００９２】
（実施形態の拡張１）
以上で説明した実施形態には、その趣旨を改変しない範囲でさまざまな拡張が考えられる。以下、これについて説明する。
ａ進数ｄ桁のメッセージ空間で、ａの値がある程度以上大きい場合には、ブロック暗号化部１０１ｃ、即ちＢｌｏｃｋＥｎｃの実際の処理としてクヌースシャッフルを利用すると効率が悪くなるので、現実的ではない。
【００９３】
このような場合には、たとえば非特許文献１０に記載された方式を用いることができる。また、特にａ＝２３２，２４８などの場合には、非特許文献１１に記載されたＫＡＴＡＮ、非特許文献１２に記載されたＲＣ５、非特許文献１３に記載されたＳＥＡなどのような、既存のブロック暗号の中でブロックサイズの小さい方式を利用するとよい。
【００９４】
これらの場合でも、ブロック暗号化部１０１ｃ（ＢｌｏｃｋＥｎｃ）の処理は一時的鍵生成部１０１ｂからの出力（ＫｅｙＧｅｎから出力された一時的鍵ＤＫ）を利用することには変わりはないが、ＡＥＳ暗号化部１０１ａからの出力をブロック暗号化部１０１ｃが要求する形式と分布の鍵に変換することが必要となる。非特許文献１０，１１，１３に記載された方法では、いずれも鍵はバイナリ形式であればよいので、一時的鍵生成部１０１ｂはＡＥＳ暗号化部１０１ａからの出力を適切な長さに短縮してブロック暗号化部１０１ｃに出力するようにすればよい。
【００９５】
また、ブロック暗号化部１０１ｃが１２８ビット以上の長さの鍵を必要とする場合には、一時的鍵生成部１０１ｂはＡＥＳ暗号化部１０１ａからの出力を公知技術であるＯＦＢ（Output Feedback Mode）によって拡張してブロック暗号化部１０１ｃに出力することもできる。さらに、外部ツイークの長さなどの条件から、ラウンドカウンタ、外部ツイーク、桁数ｄとＸ［１］，…，Ｘ［ｄ］を連結した系列が１２８ビット以上となる場合であれば、これも公知技術であるＣＢＣ−ＭＡＣなどの一般的な暗号利用モードを利用して一時的鍵生成部１０１ｂの入力長を拡張することもできる。
【００９６】
（実施形態の拡張２）
ａ進数ｄ桁のメッセージ空間で、桁ごとのａが等しくない場合もあり得る。たとえば、背景技術の欄で述べた「２進数と１０進数の組み合わせ」などのようなデータを扱う場合がこれに該当する。ここではｉ桁目（ｉ＝１，…，ｄ）のａの値をａ（ｉ）と表す。第ｊラウンド（ｊ＝１，…，ｄ）でＸ［１］のとりうる空間は以下の数１５で示される。
【００９７】
【数１５】
0006007975.tif 000016
【００９８】
このような場合、第ｊラウンドでのブロック暗号化部１０１ｃの処理で用いられるクヌースシャッフルの配列サイズやブロック暗号のブロックサイズも、数１５で示されるものと等しくなる。即ち、ラウンドごとにブロック暗号化部１０１ｃの処理は周期的に変わることとなるので、これに合わせてＡＥＳ暗号化部１０１ａおよび一時的鍵生成部１０１ｂの処理も周期的に変わる。
【００９９】
また、桁ごとのａ（ｉ）が等しくない場合でも、ラウンド数ｒが桁数ｄの整数倍となるようにすれば、ブロック置換手段１０２およびカウンタ更新手段１０３の処理自体は上記実施形態と同じでよい。ｒラウンド分の処理が終わった後で平文と暗号文とでフォーマットが一致する必要があり、ラウンド数ｒが桁数ｄの整数倍であるという条件でブロック置換手段１０２が左（ないしは右）巡回シフトを行えばこの条件は満たされる。これ以外の場合には、ラウンドカウンタがrのときのみブロック置換手段１０２において別の置換を適用する必要がある。
【０１００】
以上で説明した実施形態の拡張１および２のいずれについても、復号化装置２０は上記の暗号化装置１０の逆演算を行うものである。
【０１０１】
これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。
【０１０２】
上述した各々の実施形態について、その新規な技術内容の要点をまとめると、以下のようになる。なお、上記実施形態の一部または全部は、新規な技術として以下のようにまとめられるが、本発明は必ずしもこれに限定されるものではない。
【０１０３】
（付記１）  入力された平文を暗号化して前記平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置であって、
前記平文のうちの特定の１桁を、前記平文の前記特定の１桁を除いた残りの各桁の数値、および前記平文と同時に入力された外部ツイークを用いて暗号化する単位ブロックツイーカブル暗号化手段と、
前記平文の前記暗号化された前記特定の１桁を含む各桁に対して予め決められた規則によって桁単位の置換を行うブロック置換手段と、
この単位ブロックツイーカブル暗号化手段およびブロック置換手段による処理を予め決められた回数繰り返させる暗号カウンタ更新手段と
を備えることを特徴とするフォーマット保存暗号化装置。
【０１０４】
（付記２）  前記単位ブロックツイーカブル暗号化手段が、
予め記憶された暗号鍵によって、前記平文の前記特定の１桁を除いた残りの各桁と前記外部ツイークとを結合した数値を暗号化して特定のビット数の出力値を出力するＡＥＳ暗号化部と、
前記ＡＥＳ暗号化部の出力値を用いて一時的暗号鍵を生成する一時的暗号鍵生成部と、
前記一時的暗号鍵を利用して前記平文の前記特定の１桁を暗号化するブロック暗号化部と
を備えることを特徴とする、請求項１に記載のフォーマット保存暗号化装置。
【０１０５】
（付記３）  前記ブロック暗号化部が、前記平文の前記特定の１桁をクヌースシャッフル（Knuth Shuffle）を用いて置換することによって暗号化するものであることを特徴とする、請求項２に記載のフォーマット保存暗号化装置。
【０１０６】
（付記４）  前記ブロック置換手段が、前記平文の左端の１桁を除いた残りの各桁を１桁ずつ繰り上げ、前記平文の前記左端の１桁を右端とするものであることを特徴とする、請求項１に記載のフォーマット保存暗号化装置。
【０１０７】
（付記５）  請求項１ないし４のうちいずれか１項に記載のフォーマット保存暗号化装置から出力された暗号文を復号化して、前記暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置であって、
前記暗号文の、前記単位ブロックツイーカブル暗号化手段と同一位置の特定の１桁を、前記暗号文の前記特定の１桁を除いた残りの各桁の数値、および前記暗号文と同時に入力された前記暗号化装置と同一の外部ツイークを用いて復号化する単位ブロックツイーカブル復号化手段と、
前記暗号文の前記復号化された前記特定の１桁を含む各桁に対して前記ブロック置換手段とは逆の規則によって桁単位の置換を行うブロック逆置換手段と、
この単位ブロックツイーカブル復号化手段およびブロック逆置換手段による処理を前記暗号カウンタ更新手段と同一の回数繰り返させる復号カウンタ更新手段と
を備えることを特徴とするフォーマット保存復号化装置。
【０１０８】
（付記６）  前記単位ブロックツイーカブル復号化手段が、
予め記憶された復号鍵によって、前記暗号文の前記特定の１桁を除いた残りの各桁と前記外部ツイークとを結合した数値を復号化して特定のビット数の出力値を出力するＡＥＳ復号化部と、
前記ＡＥＳ復号化部の出力値を用いて一時的復号鍵を生成する一時的復号鍵生成部と、
前記一時的復号鍵を利用して前記暗号文の前記特定の１桁を復号化するブロック復号化部と
を備えることを特徴とする、請求項５に記載のフォーマット保存復号化装置。
【０１０９】
（付記７）  前記ブロック復号化部が、前記暗号文の前記特定の１桁をクヌースシャッフル（Knuth Shuffle）を用いて逆置換することによって復号化するものであることを特徴とする、請求項６に記載のフォーマット保存復号化装置。
【０１１０】
（付記８）  前記ブロック置換手段が、前記平文の右端の１桁を除いた残りの各桁を１桁ずつ繰り下げ、前記平文の前記右端の１桁を左端とするものであることを特徴とする、請求項５に記載のフォーマット保存復号化装置。
【０１１１】
（付記９）  入力された平文を暗号化して前記平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置にあって、
前記平文の左端の１桁を、前記平文の前記左端の１桁を除いた残りの各桁の数値、および前記平文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル暗号化手段が暗号化し、
前記平文の前記左端の１桁を除いた残りの各桁、および前記暗号化された前記平文の左端の１桁に対して予め決められた規則によってブロック置換手段が桁単位の置換を行い、
この前記平文の左端の１桁の暗号化および前記桁単位の置換の処理をカウンタ更新手段が予め決められた回数繰り返させる
ことを特徴とするフォーマット保存暗号化方法。
【０１１２】
（付記１０）  入力された暗号文を復号化して前記暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置にあって、
前記暗号文の左端の１桁を、前記暗号文の前記左端の１桁を除いた残りの各桁の数値、および前記暗号文と同時に入力された外部ツイークを用いて単位ブロックツイーカブル復号化手段が復号化し、
前記暗号文の前記左端の１桁を除いた残りの各桁、および前記復号化された前記暗号文の左端の１桁に対して予め決められた規則によってブロック逆置換手段が桁単位の逆置換を行い、
この前記暗号文の左端の１桁の復号化および前記桁単位の逆置換の処理をカウンタ更新手段が予め決められた回数繰り返させる
ことを特徴とするフォーマット保存復号化方法。
【０１１３】
（付記１１）  入力された平文を暗号化して前記平文と同一のデータ形式の暗号文を出力するフォーマット保存暗号化装置にあって、
前記フォーマット保存暗号化装置が備えるコンピュータに、
前記平文の左端の１桁を、前記平文の前記左端の１桁を除いた残りの各桁の数値、および前記平文と同時に入力された外部ツイークを用いて暗号化する手順、
前記平文の前記左端の１桁を除いた残りの各桁、および前記暗号化された前記平文の左端の１桁に対して予め決められた規則によって桁単位の置換を行う手順、
およびこの前記平文の左端の１桁の暗号化および前記桁単位の置換の処理を予め決められた回数繰り返させる手順
を実行させることを特徴とするフォーマット保存暗号化プログラム。
【０１１４】
（付記１２）  入力された暗号文を復号化して前記暗号文と同一のデータ形式の平文を出力するフォーマット保存復号化装置にあって、
前記フォーマット保存復号化装置が備えるコンピュータに、
前記暗号文の左端の１桁を、前記暗号文の前記左端の１桁を除いた残りの各桁の数値、および前記暗号文と同時に入力された外部ツイークを用いて復号化する手順、
前記暗号文の前記左端の１桁を除いた残りの各桁、および前記復号化された前記暗号文の左端の１桁に対して予め決められた規則によって桁単位の逆置換を行う手順、
およびこの前記暗号文の左端の１桁の復号化および前記桁単位の逆置換の処理を予め決められた回数繰り返させる手順
を実行させることを特徴とするフォーマット保存復号化プログラム。
【０１１５】
この出願は２０１２年４月２４日に出願された日本出願特願２０１２−０９８４０３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１１６】
本発明は、データ形式が予め定められている業務システムやデータベースなどにデータの暗号化／復号化機能を付加するという用途に対して、幅広く適用が可能である。前述のクレジットカード番号などの例以外にも、たとえばＲＦＩＤタグ（標準長９６ビット、ＡＥＳの１２８ビットより短い）のデータを暗号化するためにも有効である。
【符号の説明】
【０１１７】
１  暗号化システム
１０  暗号化装置
１１、２１  プロセッサ
１２、２２  記憶手段
１３、２３  入力手段
１４、２４  出力手段
２０  復号化装置
１０１  単位ブロックツイーカブル暗号化手段
１０１ａ  ＡＥＳ暗号化部
１０１ｂ  一時的鍵生成部
１０１ｃ  ブロック暗号化部
１０２  ブロック置換手段
１０３、２０３  カウンタ更新手段
１１１  暗号鍵
２０１  単位ブロックツイーカブル復号化手段
２０２  ブロック逆置換手段
２１１  復号鍵
【図１】
0006007975.tif 000017
【図２】
0006007975.tif 000018
【図３】
0006007975.tif 000019
【図４】
0006007975.tif 000020
【図５】
0006007975.tif 000021
【図６】
0006007975.tif 000022