Clever Geek Handbook

RSA、それは簡単ですか？

前戯



読者の皆さん、こんにちは。

ほとんどの場合、ほとんどの人はRSA非対称暗号化アルゴリズムが何であるかを知っています。 実際、Runet全体、特にこのリソースでは、この問題に関する記事が非常に多いため、新しいことを言うことはほぼ不可能です。

まあ、そこに、ゴーリーで、あなたはまだ思い付くことができるので、すべてがずっと前に明らかになっています。 レシピは簡単です：

2つの素数PとQ

乗算して数Nを取得します。

任意のEを選択します

D = E -1 （mod（ P-1 ）（ Q-1 ））を見つけます。

暗号化の場合、メッセージMはNを法とするEの累乗になります。暗号文CをDの累乗を同じモジュロNに復号するには、すべての暗号プリミティブが準備されています。 取って使用しますよね？ 実際、そうではありません。 問題は、これは実際には暗号プリミティブにすぎず、現実の世界ではすべてが少し複雑であることです。



理論のビット



RSAを最も単純な形式で使用することが非常に推奨されない理由を理解するために、非対称暗号システムに提唱される次の要件に最初に注意します。

要件1：

現代の非対称暗号システムは、2つの平文M 1とM 2 、および1つの暗号文C bを持つ攻撃者が、2つの平文のどちらが暗号文Cに対応するかを0.5を超える確率で決定できない場合、安全であると見なすことができますb 。

RSAがこの要件を満たしているかどうかを確認しましょう。 したがって、攻撃者のマロリーがアリスとボブのやり取りを聞いているとします。 ある素晴らしい日、彼はボブがアリスに非常に重要な質問を公然と尋ね、その答えの知識がマロリーの好奇心を豊かにし、あるいは非常に楽しませるのを見ます。 アリスはこの個人的な質問に単調にボブに答えます。 彼女はボブの公開鍵で答えを暗号化し、暗号文を送信します。 次に、マロリーは暗号文を傍受し、YesまたはNoが暗号化されていると疑います。 アリスの答えを見つけるために必要なのは、ボブの公開鍵で「はい」という単語を暗号化することです。受信した暗号テキストが傍受したものと一致する場合、アリスは「はい」と答えたことを意味します。 「いいえ」でした



これからわか​​るように、RSAはやや手に負えませんが、まだあまり理想的ではありませんが、一般に信じられているほど信頼性が高くありません。 はい、もちろん、アリス自身は愚か者であると言うことができ、誰も彼女に単音節でこのような深刻な質問に答えるように頼んだことはありません。 それでは、暗号化における単音節回答の使用を今禁止しているものは何ですか？ もちろん違います。 すべてがそれほど悪くはありません。アルゴリズムが予測できないテキストにランダムな情報を追加すれば十分であり、陰湿なマロリーは無力になります。 実際、アルゴリズムによる処理後の回答「はい」が、たとえば「Da4FE6DA54」に変わることを予測することはできません。したがって、このメッセージを暗号化することはできず、傍受した暗号文と比較することはできません。



したがって、PGPでもSSLでも、RSAはすべてのマニフェストで、暗号化機能の入力に送信されるデータのみを暗号化しないと既に言えます。 アルゴリズムは、最初にランダムなビットセットを含むブロックをこのデータに追加します。 その後、結果が暗号化されます。 つまり いつもの代わりに

C = M E （mod N ）

私たちは現実に近づく

C =（M || Rand） E （mod N ）、

ここで、Randは乱数です。

この手法は、補充スキームと呼ばれます。 現在、アドオンスキームなしでRSAを使用することは、 標準に直接違反するため、それほど悪い形ではありません。



しかし、それはすべてとは程遠い。 暗号システムが上記で定式化された要件を満たしていても、実際の目的への適合性はまだ証明されていないと考えられています。 非対称アルゴリズムの安定性に関するもう1つの要件を定式化します。



要件2：

攻撃者が復号化ブラックボックスにアクセスできるようにします。 つまり 攻撃者の要求に応じて暗号化テキストを解読できます。 次に、攻撃者は2つの平文M 1およびM 2を作成します。 これらのテキストの1つが暗号化され、結果の暗号文C bが攻撃者に返されます。 攻撃者のタスクは、メッセージM 1とM 2のどちらが暗号文C bに対応するかを0.5より大きい確率で推測することです。 同時に、彼はC b以外のメッセージを解読するように要求するかもしれません（そうでなければゲームは意味をなしません）。 攻撃者が、たとえそのような優れた状況にあっても、どのソーステキストC bが0.5より大きい確率で対応するかを示すことができなければ、暗号システムは安定していると言われています。



上記に照らして、RSAの状況を見てみましょう。

したがって、攻撃者には2つのメッセージM 1とM 2があります。 暗号文と同様に

C b = M 1 E （mod N ）。

彼は、2つのテキストのどちらがC bに特に対応するかを示す必要があります。 これを行うために、彼は次のことができます。 公開鍵Eを知っていれば、彼はメッセージを作成できます

C '= 2 E * C b （mod N ）。

次に、復号化する「ブラックボックス」にメッセージC 'を復号化するように依頼します。 そして、彼を助けるための簡単な算術。 私たちが持っています：

M '= C' D （mod N ）= 2 ED * M 1 ED （mod N ）= 2 * M 1 （mod N ）。

つまり M '/ 2を計算すると、攻撃者はM 1を見ることになります。 これは、この例ではメッセージM 1が暗号化されていることを彼が理解することを意味します。



この問題を解消し、回路を補完するのに役立ちます。 今や彼らは、追加情報が絶対にランダムで予測不可能であることだけでなく、要求しています。 ただし、暗号化機能の結果として暗号文が取得されたのか、それとも攻撃者によってモデル化されたのかを判断するのに役立つ追加のブロックも必要です。 さらに、暗号化されたデータが復号化されたデータの代わりにモデル化されていることが発見された場合、攻撃者にはデータが実際の暗号文と一致しないというメッセージが表示されます。



このような補足スキームの実装は難しい作業のように思えますが、暗号化には既にデータの整合性を監視するための既製のツールがあります。 もちろん、これらはハッシュ関数です。 最新のアドオンスキームはすべて、真正性のために復号化されたデータの検証としてハッシュ関数を使用するという考えに基づいて実装されています。



RSAは、データの署名と暗号化に2つの異なるアドオンスキームを使用します。 文書に署名するために実装されたスキームは、RSA-PSS（確率的署名スキーム）または確率的署名スキームと呼ばれます。 暗号化に使用されるスキームは、RSA-OAEP（最適な非対称暗号化パディング）または最適化された非対称暗号化パディングであり、OAEPを例として使用し、RSAでのメッセージ暗号化が実際にどのように発生するかを検討します。



RSA-OAEP



したがって、RSA-OAEPのメッセージを完全に暗号化するには、次のようにします。

  1. ハッシュ関数の結果の合計長がRSAキーの長さを超えないように、2つのハッシュ関数G（x）およびH（x）が選択されます。
  2. ビットlのランダムな文字列が生成されます。 文字列の長さは、ハッシュ関数H（x）の結果の長さと等しくなければなりません。
  3. メッセージMは、kビットのブロックに分割されます。 次に、各受信ブロックmに（nk）個のゼロが追加されます。 ここで、nはハッシュ関数G（x）の長さです。
  4. 次のビットセットが決定されます。{m || 0 （nk） ⊕G（l）} || {l⊕H（m || 0 （nk） ⊕G（l））}
  5. 結果のビットは整数M 1として表されます
  6. 暗号文は次の式で得られます：C = M 1 E （mod N ）


復号化プロセスは次のとおりです。

  1. 式M 1 = C D （mod N ）でM 1を見つける
  2. 結果のビットのセットでは、左側の部分が切り取られます。 ある意味では、左部分は数M 1の左nビットで、nはハッシュ関数G（x）の長さです。 これらのビットをTで示します。T= {m || 0 （nk） ⊕G（l）}であることに注意してください。 他のすべてのビットは正しい部分です。
  3. H（T）= H（m || 0 （nk） ⊕G（l））
  4. H（T）がわかれば、lが得られます。 l⊕H（T）はブロックの右側です。
  5. lを計算した後、T⊕G（l）からmを見つけます。 T = {m || 0 （nk） ⊕G（l）}
  6. mが（nk）ゼロで終わる場合、メッセージは正しく暗号化されます。 そうでない場合、これは暗号文が正しくないことを意味し、したがって攻撃者によって改ざんされている可能性が高いです。


おわりに



つまり RSAは、大きな数を法とする累乗だけではありません。 また、冗長データを追加することで、情報の保護を強化できます。 あなたは尋ねることができます：なぜこれがすべて必要なのですか？ そのような状況は、攻撃者が復号化アルゴリズムにアクセスしたときに本当に起こりますか？ まったく別の機会に、なんらかの形で言われました：トラブルが発生する可能性がある場合、それは確実に発生します。 アドオンスキームを使用するようになった今、これはもはや迷惑とは見なされなくなります。



upd：暗号をブログに転送しました。

upd2：

文献と参考文献：

1. N.ファーガソン、B。シュナイアー「Practical Cryptography」

2. N.スマート「暗号化」

3. RSA-OAEP仕様（pdf）


More articles:


All Articles