Hi％username％！ 今日は金曜日にちょっとした暗号があります。 2016年3月に、NISTから興味深い出版物が番号800-38G （pdf）で発行され、非常に興味深いタイトルのブロック暗号操作モードの推奨事項：Format-Preserving Encryptionのメソッドがあり、暗号化のデータ形式を変更しない2つのアルゴリズムが記述されています。 つまり、クレジットカード番号が1234-3456-4567-6678である場合、暗号化後も番号がそのまま残ります。 例：6243-1132-0738-9906。 そして、これは単純なxorではなく、AESがあり、一般にすべてが深刻です。 一般にFPEについて、特に実装の1つについて少し話しましょう。
はい、これはなんらかのトリックではありません。実際には、限られた入力値のセットからデータを暗号化および復号化できます。 もちろん、ここには落とし穴がありますが、問題は基本的に解決されています。 主なことは、結果の設計は、その基礎となる暗号アルゴリズムよりもクラッキングに対する耐性が低くならないことです。
そのため、たとえば0〜9の数字など、事前に定義された文字のセットがあり、それを超えたくはありません。 簡単にするために、彼らはこのソースセットのサイズに等しい数体系のベースについて話しています。 数字の場合、これは明らかに10です。ロシア語のアルファベットの場合、33、英語の26の場合です。文字自体は考慮されません。インデックスの配列のみを使用し、インデックスの代わりに元のセットのインデックスを置き換えます。 たとえば、文字列「habr」と入力セットとしてのロシア語のアルファベットの場合、結果は配列[22、0、1、17]になります。 それは簡単な部分でした。
Comrades BlackとRogawayは、形式を保持するいくつかの暗号化方法を考案しました。
最も単純なのはプレフィックス暗号です。 それを見てみましょう：
プレフィックス暗号
- AESのような堅牢なアルゴリズムで各インデックスを暗号化します。
- 暗号化された値をソートします。
- ソートされたリストを新しいインデックスリストとして使用します。
たとえば、4つの要素で構成されるセットを暗号化します。
ここでは、実際にどのように機能するかを示すために、 Wikipediaをコピーして貼り付けます
AESなどの各インデックスを暗号化します。 たとえば、
weight(0) = 0x56c644080098fc5570f2b329323dbf62 weight(1) = 0x08ee98c0d05e3dad3eb3d6236f23e7b7 weight(2) = 0x47d2e1bf72264fa01fb274465e56ba20 weight(3) = 0x077de40941c93774857961a8a772650d
[0,1,2,3]を重みで並べ替えると[3,1,2,0]になるため、コードは次のようになります。
F(0) = 3 F(1) = 1 F(2) = 2 F(3) = 0.
これは実用的なオプションであり、非常に簡単に実装できます。 しかし、大規模なセットの場合、これは長期間にわたって毎回生成されるため、他のアルゴリズムが発明されました。
サイクルウォーキング
セットのサイズが暗号化ブロックのサイズより小さくない場合、結果がセットのサイズと等しくなるまでループで暗号化を試みることができます。 ちなみにビットコインマイニングに非常に似ています。 しかし、ここで明らかなマイナスは予測不可能な速度であり、ブロックサイズに関連してセットが小さくなるほど、速度は低下します。
Feistel Networks
Black and Rogawayの説明では、これはサイクルウォーキングとほぼ同じです。Feistelのネットワークのみがセットのサイズと同じサイズで使用されています。
詳細を説明したいBPSアルゴリズムは、Feistelネットワークによって制限されたセットを暗号化するというアイデアをさらに発展させたものですが、そこではモジュールサイズの追加が使用されます。 したがって、ブルートフォースをする必要はなく、すべてが非常に美しく快適になります。 バイトを少し処理するだけです。
元のアルゴリズムでは、各段階でBE-> LEバイトを反転するなど、説明を無駄にするだけの重要なステップがないため、ここではすべてのデータを簡略化して示します。 行こう！
入力データ：
- セット内の要素の数。これは基数システムの基礎です
- キーはAES用です。 まだ微調整があり、タイプIVです。ただし、ここでは簡単にするために省略します。
- 暗号化のためのインデックスのセットであり、「プレーンテキスト」でもあります。 基数を指定して、1つのAESブロックに収まる必要があります
ここで最も重要でトリッキーな関数の1つは、インデックスの配列をバイトの配列にパックし、それをアンパックすることです。 セットのサイズは必ずしも1バイトに収まるとは限りません。その逆も同様です。サイズが許せば、インデックスをより厳密にパックすることでスペースを節約できます。
この関数はnumと呼ばれ、実際には非常に簡単に機能します。
BigInteger num(int[] X, int radix) { // 1. Let x = 0. BigInteger x = BigInteger.ZERO; // type conversion for readability BigInteger r = BigInteger.valueOf(radix); // 2. For i from 1 to LEN(X) for (int i = 0; i < X.length; i++) { // check the value of X[i] if (X[i] < 0 || X[i] >= radix) throw ... // let x = x * radix + X[i] x = x.multiply(r).add(BigInteger.valueOf(X[i])); } return x; }
つまり、インデックスに数値システムを掛けたものを、直感に追加します。 次に、標準ツールを使用してBigIntegerをバイト配列に変換し、必要に応じて必要なサイズにゼロを追加します。
この操作を
num(x, radix)
Feistel Network
設計はFeistelネットワークに基づいているため、初期セットを2つの半分に分割し、それぞれを個別に処理して、ラウンドの終わりに交換します。 これらの半分をAおよびBと呼びます。
たとえば、ベース（基数）4との組み合わせ[0 1 2 3]を暗号化します。
A = [0 1]
B = [2 3]
ステップでのBPSの簡略化されたラウンドを検討してください。
1）半分のBで作業します。バイトに変換します。 num（B、4）= [14]（2 + 3 * 4のため）ブロックサイズにゼロを追加すると、[0、0、0、0、0、0、0、0、0、0、0、0 、0、0、0、14]
2） AESのアイテム1のブロックを暗号化します。 たとえば、3B20D6CC035B63C8CFD53C15D477BBF8
3） 3B20D6CC035B73C8CFD53C15D477BBF8を数値に変換すると、78594961850022499408352439646346001400が得られます
4） Aの半分を数値num（A、4）に変換します0 + 1 * 4 = 4
5）ポイント4と3を追加すると、7859496185002249940835243964634600140 4が得られます
6）トリック。
6.1）次のラウンドでこの値を半分にするために、最初にその中に何桁あるかを計算し、基数を半分Aの要素の数に等しい累乗に上げます
4 ^ 2 = 16
6.2） 7859496185002249940835243964634600140 4を16 で割った残りを取得すると、 12が得られます
6.3） 12を基数4のインデックスの配列に変換すると、[0、3]（0 + 3 * 4）が得られます
7）半分を場所ごとに変更します[2、3] [0、3]
そしてさらに7回、合計8ラウンド
反対方向への移動はそれほど難しくありません。 BではなくAで始まる
1） 手順 1から3を繰り返して、 78594961850022499408352439646346001400を取得します
2） [0、3]を数字に変換しますが、これは12
3） 12から78594961850022499408352439646346001400を引くと 、負の数-78594961850022499408352439646346001388が得られ、モジュロ16は4になります。 はい、負の数もモジュロでとることができます、それは大丈夫です。
4） 4を[0、1]に変換します
場所で半分を変更すると、[0、1] [2、3]が得られます
すべて、私たちは正直に私たちのプレインテキストの半分を暗号化および解読し、多数の境界を越えませんでした。 同意して、これは非常に美しくエレガントな方法です。
ちなみに、標準は説明されていません。BPSドック （pdf）は、AESブロックサイズが1つのテキストを暗号化するのに十分でない場合にCBCのようなブロックをリンクする方法を説明しています。 真実は、xorの代わりに、モジュロ加算も使用され、要素単位でのみです。
クレジットカードについて。 カードの16桁すべてをこの方法で（もちろん10を基準にして）暗号化する必要はありません。 少なくとも、チェックボックスをタッチして、個別にカウントすることはできません。
さらに、カードには発行者の識別子（最初の6桁）があり、アカウント番号自体は最後の9桁です。 この方法で暗号化することは理にかなっています。
それだけです。 新しいNIST標準と互換性のあるこの Java コードは、アルゴリズムの学習に役立ちました。