•  19-08-2019
  •  | 
  •  

質問

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

しかし、まだまだあります。分配的でなければならないため、入力の1バイトを変更すると、4つの出力バイトすべてに影響するはずです。

問題：

  • 乗算を使用する場合、ストレージを介して255としてバイトとして変更された後、元に戻すことはできません（その必要性はバイトのままである必要があります）
  • 追加を使用する場合、元に戻すことも分配することもできません

1つのソリューション： 256 ^ 4の長さのバイトの配列を作成し、1対1のマッピングで埋めることができますが、問題があります。つまり、検索する必要があるため、サイズ256 ^ 8のグラフを検索する必要があります。すべての値に無料の数字を使用します（分布は、バイトの64 * 64配列に基づいてsudoランダムにする必要があります）。このソリューションには、8GBのRAMが必要であるというマイナー（笑）問題もあるため、このソリューションはナンセンスです。

入力のドメインは出力のドメインと同じです。すべての入力には一意の出力、つまり1対1のマッピングがあります。 <！> quot; one solution <！> quot;で述べたように、これは非常に可能であり、小さなドメイン（わずか256）が問題になったときにその方法を使用しました。事実、数値が大きくなるとメソッドが非常に非効率になるため、デルタの欠陥はO(n^5)であり、オメガはO(n^8)であり、メモリの使用量も同様でした。

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

役に立ちましたか？

解決

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

  1. バイトスペースをBにします。 1対1の（したがって、）関数f: B^4 -> B^4が必要です。
  2. 単一の入力バイトを変更すると、すべての出力バイトが変更されます。

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

さて、まず第一に、1バイトを受け取り、1バイトを返す関数g: B -> Bが必要です。この関数には2つのプロパティが必要です。g（x）は可逆で、x ^ g（x）は可逆です。 [注：^はXOR演算子です。]そのようなgでも実行できますが、後で特定のgを定義します。

このようなagが与えられた場合、f（a、b、c、d）=（a ^ b ^ c ^ d、g（a）^ b ^ c ^ d、a ^ g（b）^ cでfを定義します^ 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 ^ constも変更されます。同様に、aが変化するとg（a）も変化するため、g（a）^ constも変化します。 （aがgの最初のプロパティによるものである場合、g（a）が変化するという事実。そうでない場合、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のような関数とします。この関数gの2つの望ましい特性、すなわち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つの目的のプロパティを満たし、四半期間に相互作用がないため、gも同様です。

他のヒント

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

誰が知っていましたか

編集！実際に線形変換が必要な場合、不可能は不可能です。以下がその解決策です：

4バイトのa_1, a_2, a_3, a_4があります。これは、4つのコンポーネントを持つベクトル a と見なされます。各コンポーネントは256のmodです。線形変換は要素も256のmodである4x4マトリックスMだけです。次の2つの条件があります。

  1. a' <=> から、 <=> を推測できます（これは、<=>が可逆マトリックスであることを意味します） 。
  2. 単一の座標で <=> と <=> が異なる場合、<=> <=> および<=> < strong> <=> はすべての座標が異なる必要があります。

条件（2）は少し複雑ですが、これが意味することです。 <=>は線形変換であるため、次のことを知っています

  

<=>（ <=> - <=> ）= <=> <=> -<=> <=>

左側では、 <=> と <=> は単一の座標で異なるため、 <=> - < => には、ゼロ以外の座標が1つだけあります。右側では、<=> <=> と<=> <=> は座標ごとに異なる必要があるため、<=> <=> -<=> <=> には、ゼロ以外のすべての座標が必要です。

したがって、行列<=>は、単一の非ゼロ座標を持つベクトルから、すべての非ゼロ座標を持つベクトルを取る必要があります。したがって、<=>のすべてのエントリが、 non-zero-divisor mod 256である、つまり奇数である必要があります。

条件（1）に戻って、<=>が可逆的であるとはどういう意味ですか？ 256 modを検討しているので、その行列式を256 modに変換する必要があります。つまり、その決定要因は奇数でなければなりません。

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

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

Bitwise Exclusive Orはあなたの友達です。

R = A XOR Bの場合、R XOR AはBを返し、R XOR BはAを返します。したがって、結果と入力の1つを知っていると仮定すると、可逆変換になります。

あなたがやろうとしていることを理解していると仮定すると、暗号をブロックすると思います仕事をします。
ブロック暗号はビットのブロック（128など）を受け取り、同じサイズの異なるブロックに可逆的にマッピングします。

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

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

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

例：

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

中国剰余定理を正しく覚えていて、何年も見ていない場合、aはbxから回復可能です。簡単な方法さえあるかもしれません。

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

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

<！> quot; linear <！> quot;の意味変換？ 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はすべてのバイトと影響の結果であるため）その他すべて）。

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

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

ビットを再マッピングできます。入力に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バイトすべてに影響するなど、可逆的な変換ができるとは思いませんが、証拠はありません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top