3

平文/鍵のペアで動作する特定の (対称または非対称) 暗号化アルゴリズムによって生成された特定の暗号文が、同じ暗号文を生成する別の平文/鍵のペアを見つけるのはどれくらい難しいですか?

そして、2 つの平文と鍵のペアが同じ暗号文につながることを 2 人で見つけるのはどれくらい難しいのでしょうか?

この質問につながったのは、上記の質問とは何の関係もない別の質問です。

暗号文と鍵があり、何らかの復号化ルーチンを使用して復号化したい場合、通常、ルーチンは鍵が正しかったかどうかを教えてくれます。しかし、それはどのようにそれを知っていますか？復号化が成功したことを示す、結果の平文で何らかのパターンを探しますか? パターンを含み、ルーチンによって「有効」と報告される別のキー結果が別の平文に存在するか?

回答とコメントに触発されたフォローアップの質問:

許可されたプレーンテキスト/キーのペアが次の (または両方の) 方法で制限されている場合:

1) 平文は鍵の KCV (Key check value) から始まります。

2) 平文は、平文とキーの組み合わせのハッシュ値で始まります

これにより、衝突検出が実行不可能になりますか? そのような平文/キーが存在することは明らかですか=

4

3 に答える 3

9

あなたの質問への答えは、あなたが言い表したように、衝突抵抗がまったくないということです。

対称的なケース 基になるブロック暗号のブロック長の倍数である長さのプレーン テキスト PT を取得したと仮定しましょう。ランダムな IV を生成し、キー K、CBC モード、パディングなしを使用してプレーン テキストを暗号化します。

同じ暗号文 CT を生成する平文 PT' と鍵 K' を生成するのは簡単です。K' をランダムに選択し、キー K' と IV を使用して CT を復号化すると、衝突する PT' が得られます。

パディングも使用すると、これは少し複雑になりますが、それでも可能です。PKCS#5/7 パディングを使用する場合は、復号化されたテキスト PT' の最後のオクテットが 0x01 になるようなキーが見つかるまでキーを生成し続けます。これには平均 128 回の試行が必要です。

このような衝突検出を不可能にするには、メッセージ認証コード (MAC) を使用する必要があります。

非対称ケース 同様のことが RSA 公開鍵暗号化にも当てはまります。パディングを使用せず (明らかに推奨されておらず、ほとんどの暗号化ライブラリでサポートされていない可能性さえあります)、公開鍵 (N,E) を使用して PT を CT に暗号化する場合は、単純に 2 番目の鍵ペア (N',E ',D') N' > N の場合、PT' = CT^D' (mod N) は (N',E') の下で CT に暗号化されます。

RSA 暗号化に PKCS#1 v1.5 パディングを使用している場合、RSA 秘密鍵操作後の最上位オクテットは 0x02 である必要があり、これは約 256 分の 1 の確率になります。さらに、最初の 0x00 値のオクテット高い確率 (約 0.97) で発生するインデックス 9 よりも早く発生する必要があります。したがって、平均して、同じビットサイズのランダムな RSA キー ペアを平均で 264 個生成する必要があります。

ただし、RSA-OAEP パディングを使用している場合、対応する公開鍵を使用して暗号文が生成されていない限り、秘密鍵の復号化は失敗することが保証されます。

于 2012-02-26T18:14:40.807 に答える
4

プレーンテキスト (長さn ) を暗号化する場合、2 n 個の一意の入力文字列があり、それぞれが一意の暗号文になる必要があります (そうしないと元に戻せません)。したがって、長さnのすべての可能な文字列は、有効な暗号文です。しかし、これはすべてのキーに当てはまります。したがって、任意の暗号文に対して、それを取得する方法は 2 kあり、それぞれに長さkの異なるキーがあります。

したがって、最初の質問に答えるには、非常に簡単です。任意のキーを選択して、暗号文を「復号化」するだけです。キーに一致する平文を取得します。

「ルーチンは通常、キーが正しかったかどうかを示します」という意味がわかりません。

于 2012-02-26T14:30:24.423 に答える
0

鍵の有効性を確認する簡単な方法の 1 つは、暗号化の前に既知の部分を平文に追加することです。復号化でそれが再現されない場合、それは正しいキーではありません。

既知の部分は定数であってはなりません。これはインスタントcribになるためです。しかし、それは例えば平文のハッシュである可能性があります。復号化されたテキストをハッシュしても同じハッシュ値が得られる場合、キーはおそらく正しいです (ハッシュの衝突を除いて)。

于 2012-02-26T15:11:53.787 に答える