Loading article…
暗号学において、フォーマット保持暗号化（FPE ）とは、出力（暗号文）が入力（平文）と同じフォーマットになるように暗号化することを指します。「フォーマット」の意味は様々です。通常、数字、アルファベット、英数字など、有限個の文字セットのみが使用されます。例えば、
このような有限領域の場合、および以下の議論の目的のために、暗号はN個の整数{0, ... , N −1 }の順列と同等であり、 Nは領域のサイズです。
FPEを使用する動機の一つは、明確に定義されたデータモデルを持つ既存のアプリケーションに暗号化を統合する際に生じる問題にあります。典型的な例としては、クレジットカード番号1234567812345670（16バイト長、数字のみ）が挙げられます。
データモデルを変更する必要があるアプリケーションに暗号化を追加することは、通常、フィールド長の制限やデータ型を変更する必要があるため、困難を伴う可能性があります。たとえば、一般的なブロック暗号の出力では、クレジットカード番号は16進数（例0x96a45cbcf9c2a9425cde9e274948cb67：34バイト、16進数）またはBase64値（例lqRcvPnCqUJc3p4nSUjLZw==：24バイト、英数字と特殊文字）に変換されます。これにより、クレジットカード番号が16桁の番号であることを想定している既存のアプリケーションは動作しなくなります。
単純な書式の問題を除けば、AES-128-CBCを使用すると、このクレジットカード番号は16進数値に暗号化される可能性があります0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02。無効な文字の生成やデータサイズの増加による問題に加え、暗号化アルゴリズムのCBCモードで暗号化されたデータは、復号化して再度暗号化する際に値も変化します。これは、暗号化アルゴリズムの初期化に使用され、暗号化値の一部として含まれる乱数シード値が、暗号化操作ごとに異なるためです。このため、CBCモードで暗号化されたデータを、データベース内の行を識別するための一意のキーとして使用することはできません。
FPEは、元のデータのフォーマットと長さを保持することで移行プロセスを簡素化し、既存のアプリケーションにおいて平文の値を暗号文に置き換えることを可能にする。
真にランダムな順列は理想的な FPE 暗号ですが、大規模なドメインでは真にランダムな順列を事前に生成して記憶しておくことは現実的ではありません。したがって、FPE の問題は、単一の値の計算時間が短い (理想的には定数であり、最も重要なのはO(N)より小さい) ように、秘密鍵から擬似ランダムな順列を生成することです。
nビットのブロック暗号は、厳密には集合{ 0, ..., 2 n -1 }上のFPEです。これらの標準サイズの集合（例えば、 DESの場合はn = 64 、 AESの場合はn = 128）のいずれかでFPEが必要な場合は、適切なサイズのブロック暗号を使用できます。
しかし、一般的な使用においては、ブロック暗号は、前述の初期化ベクトルを用いて、任意の長さのメッセージを暗号化できる動作モードで使用されます。このモードでは、ブロック暗号はFPEではありません。
暗号学の文献（以下の参考文献のほとんどを参照）では、「優れた」FPEの基準は、攻撃者がFPEを真のランダムな順列と区別できるかどうかである。攻撃者は、オラクルや既知の暗号文／平文ペアにアクセスできるかどうかによって、さまざまな種類の攻撃者が想定されている。
ここで挙げたほとんどの手法では、理想的な乱数関数の代わりに、よく知られたブロック暗号（ AESなど）が基本要素として用いられています。この手法の利点は、秘密鍵をアルゴリズムに容易に組み込めることです。以下の説明でAESについて言及している箇所は、他の優れたブロック暗号でも同様に機能します。
基となるブロック暗号のセキュリティと関連していることが証明できるFPEの実装は、暗号学者のジョン・ブラックとフィリップ・ロガウェイによる論文[ 1 ]で初めて試みられ、3つの方法が説明されました。彼らは、これらの各手法が、構築に使用されるブロック暗号と同等のセキュリティを持つことを証明しました。これは、AESアルゴリズムを使用してFPEアルゴリズムを作成する場合、結果として得られるFPEアルゴリズムはAESと同等のセキュリティを持つことを意味します。なぜなら、FPEアルゴリズムを破ることができる攻撃者は、AESアルゴリズムも破ることができるからです。したがって、AESが安全であれば、AESから構築されたFPEアルゴリズムも安全です。以下では、EはFPEアルゴリズムの構築に使用されるAES暗号化操作を表し、FはFPE暗号化操作を表します。
{0, ..., N -1}に対して FPE アルゴリズムを作成する簡単な方法の 1 つは、各整数に擬似乱数重みを割り当て、その重みでソートすることです。重みは、既存のブロック暗号を各整数に適用することによって定義されます。Black と Rogaway はこの手法を「プレフィックス暗号」と呼び、使用したブロック暗号と同等の性能であることが証明できることを示しました。
したがって、ドメイン {0,1,2,3} で FPE を作成するには、キーKが与えられた場合、各整数にAES( K ) を適用し、たとえば、
重み(0) = 0x56c644080098fc5570f2b329323dbf62 重み(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 重み(2) = 0x47d2e1bf72264fa01fb274465e56ba20 重み(3) = 0x077de40941c93774857961a8a772650d
[0,1,2,3] を重みでソートすると [3,1,2,0] になるので、暗号は
F (0) = 3、 F (1) = 1、 F (2) = 2、 F (3) = 0
この方法は、 Nの値が小さい場合にのみ有効です。Nの値が大きい場合、ルックアップテーブルのサイズと、テーブルを初期化するために必要な暗号化の回数が大きくなりすぎて、実用的ではありません。
擬似乱数順列Pのドメイン内に許容値の集合Mが存在する場合(例えばP はAES のようなブロック暗号である)、ブロック暗号を繰り返し適用して結果が ( M内の)許容値のいずれかになるまで繰り返すことにより、ブロック暗号から FPE アルゴリズムを作成できます。
CycleWalkingFPE(x) { P (x)がMの要素である場合はP (x) を返し、そうでない場合はCycleWalkingFPE( P (x)を返す} }再帰は必ず終了する。（Pは1対1対応であり、定義域は有限であるため、Pを繰り返し適用するとサイクルが形成される。したがって、 M内の点から開始すると、サイクルは最終的にM内で終了する。）
この方法の利点は、 Mの要素を連続する整数列 {0,..., N -1}にマッピングする必要がないことです。一方、 M がPの定義域よりもはるかに小さい場合、各操作で多くの反復が必要になる可能性があるという欠点があります。PがAES のような固定サイズのブロック暗号である場合、この方法はMのサイズに厳しい制約を課します。
例えば、アプリケーションが100ビットの値をAESで暗号化し、別の100ビットの値を生成するような処理を行いたい場合を考えてみましょう。この手法では、上位28ビットすべてが0になる値に到達するまでAES-128-ECB暗号化を適用できます。この処理には平均して2²⁸回の反復が必要です。
ファイステルネットワークを使用してFPEアルゴリズムを作成することも可能である。ファイステルネットワークは、各ラウンドのサブキー用の擬似乱数値のソースを必要とし、AESアルゴリズムの出力をこれらの擬似乱数値として使用できる。この方法を用いると、十分なラウンド数を使用すれば、結果として得られるファイステル構成は良好となる。[ 2 ]
AESとファイステルネットワークを用いてFPEアルゴリズムを実装する一つの方法は、ファイステルネットワークの左半分または右半分の長さに等しくなるように、AES出力の必要なビット数を使用することです。例えば、サブキーとして24ビットの値が必要な場合、AES出力の下位24ビットをこの値に使用することができます。
これにより、Feistel ネットワークの出力が入力のフォーマットを保持するとは限りませんが、サイクル ウォーキング テクニックと同様の方法で Feistel ネットワークを反復することで、フォーマットが保持されるようにすることができます。Feistel ネットワークへの入力のサイズを調整できるため、この反復が平均的に非常に速く終了する可能性が非常に高くなります。たとえば、クレジットカード番号の場合、16 桁のクレジットカード番号は10 15通りあり (冗長なチェック デジットを考慮すると)、10 15 ≈ 2 49.8であるため、50 ビット幅の Feistel ネットワークとサイクル ウォーキングを使用すると、平均的にかなり速く暗号化する FPE アルゴリズムが作成されます。
ソープシャッフルは、理想化されたカードシャッフルのようなもので、あるいは同等に、片面が1ビットである最大限に不均衡なファイステル暗号です。不均衡なファイステル暗号の方が、均衡なファイステル暗号よりも安全性を証明するのが容易です。[ 3 ]
ドメインサイズが2のべき乗であり、既存のブロック暗号のブロックサイズが小さい場合、Bellare、Rogawayによって説明されているように、VILモードを使用して新しい暗号を作成できます。[ 4 ]
ヘイスティ・プディング暗号は、独自の構造（既存のブロック暗号を基本要素として利用しない）を用いて、任意の有限の小さな領域を暗号化します。
NISTが検討対象として受け入れたAESのFFSEMモード（仕様[ 5 ]）は、上記で説明したブラックとロガウェイのファイステルネットワーク構成を使用し、ラウンド機能にはAESを使用しますが、1つのわずかな変更点があります。それは、単一のキーが使用され、各ラウンドでわずかに調整されることです。
2010年2月現在、FFSEMはMihir Bellare、Phillip Rogaway、Terence Spiesによって作成されたFFXモードに置き換えられています。（仕様、[ 6 ] [ 7 ] NISTブロック暗号モード開発、2010年）)
JPEG 2000規格では、マーカー コード (0xFF90 から 0xFFFF の範囲) は平文と暗号文に現れてはなりません。単純なモジュラ 0xFF90 の手法は、JPEG 2000 の暗号化問題を解決するために適用できません。たとえば、暗号文の単語 0x23FF と 0x9832 は有効ですが、それらを組み合わせた 0x23FF9832 はマーカー コード 0xFF98 が含まれるため無効になります。同様に、単純なサイクル ウォーキング 手法も、2 つの有効な暗号文ブロックを組み合わせると無効な暗号文になる可能性があるため、JPEG2000 の暗号化問題を解決するために適用できません。たとえば、最初の暗号文ブロックがバイト "...30FF" で終わり、2 番目の暗号文ブロックがバイト "9832..." で始まる場合、マーカー コード "0xFF98" が暗号文に現れます。
Hongjun WuとDi Maによる論文「JPEG2000のための効率的で安全な暗号化方式」[ 8 ]では、JPEG 2000のフォーマット保持暗号化のための2つのメカニズムが示されています。JPEG 2000のフォーマット保持暗号化を実行するには、暗号化と復号化でバイト「0xFF」を除外する手法を使用します。そして、1つのJPEG 2000暗号化メカニズムはストリーム暗号でモジュロn加算を実行し、もう1つのJPEG 2000暗号化メカニズムはブロック暗号でサイクルウォーキング技術を実行します。
いくつかのFPE（不偏暗号化）手法は、標準暗号の出力をnを法として暗号化対象データに加算し、結果を不偏にするための様々な方法を用いる。多くの手法に共通するnを法とする加算は、FPE問題に対する最も明白な解決策であり（そのため多くのケースで使用されている）、主な違いは使用される不偏補正メカニズムにある。
FIPS 74「連邦情報処理標準規格 1981 NBS データ暗号化標準の実装と使用に関するガイドライン」[ 9 ]の第 8 節では、モジュロ n 加算とそれに続くバイアス除去演算によってデータのフォーマットを保持する方法で DES 暗号化アルゴリズムを使用する方法が説明されています。この規格は 2005 年 5 月 19 日に廃止されたため、この手法は正式な標準としては時代遅れとみなされるべきです。
フォーマットを保持する暗号化のもう 1 つの初期のメカニズムは、ピーター・グートマンの「制限された範囲の値でデータを暗号化する」[ 10 ]であり、これもまた、結果を均一にするための調整を加えた任意の暗号に対してモジュロ n 加算を実行し、結果として得られる暗号化は、それが基づいている基盤となる暗号化アルゴリズムと同じくらい強力です。
Michael BrightwellとHarry Smithによる論文「データ型を保持する暗号化を使用してデータウェアハウスのセキュリティを強化する」[ 11 ]では、 DES暗号化アルゴリズムを平文の形式を保持する方法で使用する方法が説明されています。この手法は、ここで参照されている他のモジュロn手法のように、バイアス除去ステップを適用しないようです。
Mihir BellareとThomas Ristenpartによる論文「フォーマット保存型暗号化」[ 12 ]では、「ほぼバランスのとれた」Feistelネットワークを使用して安全なFPEアルゴリズムを作成する方法について説明しています。
Ulf Mattssonによる論文「データ型保存暗号化を使用したフォーマット制御暗号化」[ 13 ]では、FPEアルゴリズムを作成する他の方法が説明されています。
FPEアルゴリズムの一例としてFNR（Flexible Naor and Reingold）が挙げられる。[ 14 ]
NIST特別刊行物800-38G「ブロック暗号動作モードの推奨事項：フォーマット保持暗号化の方法」[ 15 ]では、FF1とFF3の2つの方法が規定されています。それぞれの提案の詳細については、NISTブロック暗号モード開発サイト[ 16 ]で特許情報やテストベクトル情報を含めて確認できます。FF1とFF3の両方についてサンプル値が利用可能です。[ 17 ]
別のモードもNISTのガイダンス草案に含まれていたが、最終版の公開前に削除された。
韓国もまた、FEA-1およびFEA-2というFPE規格を開発している。
FF1とFF3のオープンソース実装は、 C言語、 Go言語、 Java、 Node.js、 Python、 C#/.Net、 Rustで公開されています。