2

入力として4バイトを受け取り、これに対して可逆線形変換を実行し、それを4バイトとして返す関数を作成する必要があります。

しかし、待ってください。それだけではありません。分散型である必要があるため、入力の1バイトを変更すると、4つの出力バイトすべてに影響するはずです。

問題：

  • 乗算を使用する場合、ストレージを介してバイトとして変更された後は元に戻せません（そしてバイトとして保持する必要があります）
  • 私が加算を使用する場合、それは可逆的で分配的ではありえません

1つの解決策：256 ^ 4の長さのバイトの配列を作成し、それを1対1のマッピングで埋めることができますが、これは機能しますが、問題があります。これは、サイズ256^8のグラフを検索する必要があることを意味します。すべての値について空き番号を検索する必要があります（分散度は64 * 64バイト配列に基づいてsudoランダムである必要があることに注意してください）。このソリューションには、8GBのRAMが必要になるというマイナーな問題もあり（笑）、このソリューションは意味がありません。

入力のドメインは出力のドメインと同じです。すべての入力には一意の出力があります。つまり、1対1のマッピングです。「1つの解決策」で述べたように、これは非常に可能であり、より小さなドメイン（256のみ）が問題となっているときにその方法を使用しました。事実、数値が大きくなるにつれて、その方法は非常に非効率的になり、デルタの欠陥がO(n^5)あり、オメガはO(n^8)メモリ使用量において同様の不自由さを持っていました。

私はそれを行うための賢い方法があるかどうか疑問に思いました。一言で言えば、それはドメインの1対1のマッピングです（4バイトまたは256 ^ 4）。ああ、そしてN + 1のような単純なものは使用できないので、sudoランダムであるが逆変換のために再作成可能なバイト値の64*64配列をキーオフする必要があります。

4

9 に答える 9

4

編集！実際に線形変換が必要な場合、それは不可能です。数学的な解決策は次のとおりです。

4 バイト がa_1, a_2, a_3, a_4あります。これを 4 つのコンポーネントを持つベクトルと見なします。それぞれのコンポーネントは 256 を法とする数値です。線形変換は、要素が 256 を法とする数値でもaある 4x4 行列です。条件は 2 つあります。 M:

  1. からMaを推測できますa(これはMが可逆行列であることを意味します)。
  2. aとa'が 1 つの座標で異なる場合、MaとはすべてのMa'座標で異なる必要があります。

条件 (2) は少しトリッキーですが、これが意味することです。Mは線形変換なので、

M( a- a) = Ma-Ma'

左側では、aとa'は 1 つの座標で異なるため、a-aはゼロでない座標が 1 つだけあります。右側では、MaとMa'はすべての座標で異なる必要があるため、Ma-はすべての座標が非ゼロでMa'なければなりません。

そのため、行列Mはゼロ以外の座標を 1 つ持つベクトルからすべての非ゼロ座標を持つベクトルを取らなければなりません。したがって、 のすべてのエントリが非ゼロ除数 mod 256 である必要があるだけですM。つまり、奇数である必要があります。

M条件 (1) に戻ると、可逆であるとはどういう意味ですか? mod 256 と考えているので、その行列式が可逆 mod 256 である必要があります。つまり、その行列式は奇数でなければなりません。

したがって、行列式が奇数である mod 256 の奇数エントリを持つ 4x4 マトリックスが必要です。しかし、これは不可能です！なんで？行列式は、エントリのさまざまな積を合計することによって計算されます。4x4 行列の場合、4 つあります。= 24 の異なる加数であり、奇数エントリの積であるそれぞれが奇数です。しかし、24 個の奇数の合計は偶数なので、そのような行列の行列式は偶数でなければなりません!

于 2009-01-21T18:08:41.947 に答える
4

バランスのとれたブロック ミキサーはまさにあなたが探しているものです。

誰かわかったね？

于 2009-01-21T16:43:42.230 に答える
2

あなたの質問を理解できるかどうかはわかりませんが、あなたがやろうとしていることは理解できたと思います。

ビット単位の排他的論理和はあなたの友達です。

R = A XOR Bの場合、R XOR AはBを返し、RXORBはAを返します。したがって、結果と入力の1つがわかっていると仮定すると、これは可逆的な変換です。

于 2009-01-21T16:36:35.410 に答える
2

私が理解しているあなたの要件は次のとおりです。

  1. をバイトBのスペースとします。1 対 1 (つまり、1 対 1) の function が必要f: B^4 -> B^4です。
  2. 単一の入力バイトを変更すると、すべての出力バイトが変更されます。

これが私がこれまでに持っている最も簡単な解決策です。より良い解決策を考え続けていたので、しばらく投稿を避けていましたが、何も考えていませんでした.

まず、g: B -> B1 バイトを受け取って 1 バイトを返す関数が必要です。この関数には 2 つのプロパティが必要です。g(x) は可逆で、x^g(x) は可逆です。[注: ^ は XOR 演算子です。] そのような g であればどれでもかまいませんが、後で特定のものを定義します。

このような ag が与えられると、f(a,b,c,d) = (a^b^c^d, g(a)^b^c^d, a^g(b)^c^d, a^b^g(c)^d)。要件を確認しましょう。

  1. リバーシブル: はい。最初の 2 つの出力バイトを XOR すると、a^g(a) が得られますが、g の 2 番目のプロパティによって、a を復元できます。b と c についても同様です。最初のバイトを (a^b^c) で XOR することにより、a、b、および c を取得した後に d を復元できます。
  2. 配布：はい。b、c、および d が固定されているとします。次に、関数は f(a,b,c,d) = (a^const, g(a)^const, a^const, a^const) の形式を取ります。a が変更された場合、a^const も変更されます。同様に、a が変化すると g(a) も変化し、g(a)^const も変化します。(a が変化する場合に g(a) が変化するという事実は、g の最初の特性によるものです。変化しなければ、g(x) は可逆ではありません。) 同じことが b と c にも当てはまります。d の場合、f(a,b,c,d) = (d^const, d^const, d^const, d^const) であるため、さらに簡単です。したがって、d が変更されると、すべてのバイトが変更されます。

最後に、そのような関数 g を構築します。T を 2 ビット値のスペースとしh : T -> T、h(0) = 0、h(1) = 2、h(2) = 3、および h(3) = 1 となる関数とします。この関数には次の 2 つがあります。 g の望ましい特性、つまり h(x) は可逆であり、x^h(x) も可逆です。(後者については、0^h(0) = 0、1^h(1) = 3、2^h(2) = 1、および 3^h(3) = 2 であることを確認してください。) g(x) を計算し、x を 2 ビットの 4 つのグループに分割し、各四半期の h を別々に取得します。h は 2 つの必要なプロパティを満たし、4 分の 1 の間に相互作用がないため、g も同様です。

于 2009-01-21T18:07:21.123 に答える
1

あなたがやろうとしていることを理解したと仮定すると、どのブロック暗号でもうまくいくと思います。
ブロック暗号は、ビットのブロック (たとえば 128) を取り、それらを同じサイズの別のブロックに可逆的にマップします。

さらに、OFB モードを使用している場合は、ブロック暗号を使用して疑似乱数ビットの無限ストリームを生成できます。これらのビットをビット ストリームと XOR すると、任意の長さのデータを変換できます。

于 2009-01-21T17:16:24.377 に答える
0

すべてのバイトを 32 ビットの数値に固定してから、1、2、または 3 ずつ shl または shr (左シフトまたは右シフト) を実行します。次に、それをバイトに分割します (バリアント レコードを使用できます)。これにより、各バイトから隣接するバイトにビットが移動します。

ここには多くの良い提案 (XOR など) があります。それらを組み合わせることをお勧めします。

于 2009-01-21T17:58:40.843 に答える
0

ビットを再マップできます。入力に ​​ii 、出力に oo を使用しましょう。

oo[0] = (ii[0] & 0xC0) | (ii[1] & 0x30) | (ii[2] & 0x0C) | (ii[3] | 0x03)
oo[1] = (ii[0] & 0x30) | (ii[1] & 0x0C) | (ii[2] & 0x03) | (ii[3] | 0xC0)
oo[2] = (ii[0] & 0x0C) | (ii[1] & 0x03) | (ii[2] & 0xC0) | (ii[3] | 0x30)
oo[3] = (ii[0] & 0x03) | (ii[1] & 0xC0) | (ii[2] & 0x30) | (ii[3] | 0x0C)

線形ではありませんが、入力の 1 バイトを大幅に変更すると、出力のすべてのバイトに影響します。入力の 1 ビットを変更すると、出力の 4 バイトすべてに影響するような可逆的な変換はできないと思いますが、証拠はありません。

于 2009-01-21T17:59:28.737 に答える
0

うまくいくかもしれないし、うまくいかないかもしれないアイデアを捨てるつもりです。

素数係数が奇数の線形関数 mod 256 のセットを使用します。

例えば：

b0 = 3 * a0 + 5 * a1 + 7 * a2 + 11 * a3;
b1 = 13 * a0 + 17 * a1 + 19 * a2 + 23 * a3;

中国の剰余定理を正しく覚えていて、何年も見ていない場合、斧は bx から回復可能です。手っ取り早い方法もあるかもしれません。

これは可逆的な変換だと思います。af(x) mod 256 = f(ax) および f(x) + f(y) mod 256 = f(x + y) という点で線形です。明らかに、1 つの入力バイトを変更すると、すべての出力バイトが変更されます。

だから、中国の剰余定理を調べて、これが機能するかどうかを確認してください.

于 2009-01-21T17:23:43.507 に答える
0

「線形」変換とはどういう意味ですか? O(n)、または f(c * (a+b)) = c * f(a) + c * f(b) の関数 f?

簡単なアプローチは回転するビットシフトです (これが上記の数学の定義を満たすかどうかはわかりません)。リバーシブルで、すべてのバイトを変更できます。ただし、これでは、すべてのバイトが変更されることは強制されません。

編集:私の解決策は次のとおりです。

b0 = (a0 ^ a1 ^ a2 ^ a3)
b1 = a1 + b0 ( mod 256)
b2 = a2 + b0 ( mod 256)
b3 = a3 + b0 ( mod 256)

それは可逆的であり（最初のバイトを他のバイトから減算し、最初の3つの結果のバイトをXORします）、1ビットの変更はすべてのバイトを変更します（b0はすべてのバイトの結果であり、他のすべてに影響を与えるため） .

于 2009-01-21T17:15:17.797 に答える