RSACコードによる暗号化。 RSA、それは本当に簡単ですか？ 現代の形の暗号システムはいつ登場しましたか？

カットの下で、「悪い」RSA暗号パラメータを選択する例が説明されています。

「RSAのモジュラス（数値）の選択には注意が必要であることを強調しておく必要があります。 n）ネットワークの特派員ごとに。 この点で、次のことが言えます。 読者は、3つの量のうちの1つを知っていれば、それを独自に検証できます。 p, qまた φ（n）、RSA秘密鍵を簡単に見つけることができます…」。

このテキストを追加しましょう。 以下のチュートリアルの例で行われているように、RSA暗号モジュールの選択が失敗した場合、秘密鍵がなくてもテキストを復号化できます。 3つの名前付き数量のいずれも知らずに。

これを行うには、暗号モジュールによって暗号文を指定するだけで十分です。 n、公開鍵 e暗号化して、「キーレス読み取り」攻撃の3つのステップを実行します。 4番目の攻撃ステップの後、前のステップでソーステキストを受信したことが確認され、読み取ることができます。 それがいかに簡単かを示しましょう。

まず、前述のマニュアルの313-315ページから例を挙げましょう。

例

暗号化短い元のテキストメッセージ： RSA.
受信者は、特性を使用して暗号を設定します n = pq = 527、 どこ p = 17, q = 31と φ（n）=（р–1）（q – 1）= 480。 公開鍵として e互いに素な数が選択されます φ（n）, e = 7。 この数については、拡張ユークリッドアルゴリズムを使用して、整数が検出されます uと v、関係を満たす e∙u+φ（n）∙v = 1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v = 2、u = –137.

限り –137≡343（mod480）、 それから d = 343.

検査： 7∙343=2401≡1（mod480）.

テキストメッセージは、間隔に含まれる一連の数字として表示されます 。 この手紙のために R, Sと A 5ビットの2進数としてエンコードされます。 英語のアルファベットのこれらの文字のシリアル番号は、バイナリ表現で使用されます。

R = 18 10 =（10010）2, S = 19 10 =（10011）2,
A = 1 10 =（00001）2.

それで RSA =（100101001100001）2。 テキストを制限された長さのブロックに分割すると、2つのブロックの表現が得られます。 RSA =（100101001）、（100001）=（M 1 = 297、M 2 = 33）.

順次暗号化されたソーステキストのブロック M 1 \ u003d 297, M 2 \ u003d 33:
y 1 \ u003d E k（M 1）\ u003d M 1e≡2977（mod527）\ u003d 474.

ここで使用しました：

297 7 =（（297 2）3）297≡（mod527）=（200 3（mod527）297）（mod527）= 474,
y 2 \ u003d E k（M 2）\ u003d M 2e≡337（mod527）\ u003d 407.

元の暗号文と同様に、暗号文は2つのブロックの形式で取得されます。 y 1 = 474; y 2 = 407.

復号化一連のアクションのようです D k（y i）=（y i）d =（y i）343（mod 527）, i = 1,2.

べき乗の計算 d指数を数値の累乗の合計として事前に表すことで、実行する方が便利です。 2 、すなわち： 343=256+64+16+4+2+1 .

この指数表現を使用する d = 343、 我々が得る：

4742≡174（mod527）、
4744≡237（mod527）、
4748≡307（mod527）、
47416≡443（mod527）、
47432≡205（mod527）、
47464≡392（mod527）、
474128≡307（mod527）、
474256≡443（mod527）、
そして最後に 474 343（mod527）=（443∙392∙443∙237∙174∙474）（mod527）= 297.

値も同様に計算されます 407 343（mod527）= 33.

復号化されたメッセージの文字通りの表現に切り替えると、次のようになります。 RSA.

例を検討した後、マニュアルではRSAシステムの強度について説明しています。 RSA暗号係数（数値）を選択する際の注意の必要性 n）ネットワークの特派員ごとに。 暗号化システムの選択された特性の要件を無視することは容認できないことが指摘されています。 これらの要件の中で、残念ながら、与えられた例で違反が示されている要件は示されていません。

RSA暗号への攻撃

RSA暗号への攻撃の例を考えてみましょう。 A.P.の教科書「FundamentalsofCryptography」の313-315ページにある例のデータを使用してみましょう。 アルフェロフ、A.Yu。 ズボフ、A.S。 クズミン、A.V。 チェレムシュキン、モスクワ。 「ヘリオスARV」、2001年。

この例で選択されたシステムパラメータの失敗（許容できない）は、ソーステキストのキーレス読み取りの攻撃を実装する計算によって簡単に示されます。 このような攻撃の本質は次のとおりです。 RSA暗号の公開鍵が与えられます（ e = 7, n = 527）および暗号文。 この例では、暗号文は2つのブロックで表されます
y \ u003d（y 1 \ u003d 474、y 2 \ u003d 407）.

暗号化された各ブロックは個別に攻撃されます。最初に攻撃します y 1 = 474、復号化した後、別のブロックを攻撃します y 2 = 407.

次に、攻撃アルゴリズムの2つの連続するステップの結果を保存し、公開鍵を使用して一連の数値を使用して、暗号化を繰り返すことによって形成されます。 私, y 1 = y利用可能な暗号文。

暗号文攻撃アルゴリズムでは、次のステップ番号が決定されます j、そのため y i e j（mod n）=（y i e j–1（mod n））e（mod n）= y i, i> 1。 最後の関係から、力を上げると e値 （y i e j–1（mod n））それは最初のshifortextであることがわかります y i = y 1.

しかし、これは平文がこのステップで暗号化されたことを意味します。 画面上の計算機を使用した直接計算（それらの数は非常に少ない）によって、その値がわかります j、暗号化サイクルが値で終了する y 1そこからサイクルが開始されました。

最初のブロックへの攻撃 y 1 = 474暗号文。
ステップ1:＆nbsp 474 7（mod527）= 382;
ステップ2:＆nbsp 382 7（mod527）= 423;
ステップ3:＆nbsp 423 7（mod527）= 297;
ステップ4：＆nbspこの手順では、すでに見つかったソーステキストを暗号化しますが、攻撃者はソーステキストを知らないため、実行する必要があります。 攻撃の完了の兆候は、暗号文の初期値の一致です（ 474 ）および暗号化の4番目のステップの結果。 これはまさに偶然の一致です。

297 7（mod527）= 474最初の（最初の）暗号文ブロックを受け取りました。 最初のブロックへの攻撃は正常に完了しました y 1 = 474。 手順3の前の結果は平文です M 1 \ u003d 297.

n = 527 r = 297モジュロ n = 527。 このように書かれています y i \ u003d y 1 \ u003d 297。 べき剰余を形成します
（（（297 7（mod527））7（mod527））7（mod527））7 = 297.

2番目のブロックへの攻撃 y 2 = 407暗号文。
ステップ1:＆nbsp 407 7（mod527）= 16;
ステップ2:＆nbsp 16 7（mod527）= 101;
ステップ3:＆nbsp 101 7（mod527）= 33;
ステップ4:＆nbsp 33 7（mod527）= 407.

この場合も、3番目のステップで、ソーステキストブロックが取得されます（ M 2 \ u003d 33）、しかし攻撃者はこれを知らず、次の（4番目のステップ）を実行します。その結果は（ 407 ）最初の暗号文と一致します y 2 = 407.

本質的にモジュロ剰余のリング n = 527控除の短い処理サイクルを実装しました r = 33モジュロ n = 527。 このように書かれています y i \ u003d y 2 \ u003d 33.
べき剰余を形成します （（33 7（mod527））7（mod527））7（mod527）= 33.

攻撃の結果（元のテキスト M 1 \ u003d 297, M 2 \ u003d 33）は、指定された暗号文のトリプル暗号化によって取得されます。 暗号文を攻撃することで大きな成功を収めることは想像しがたいことです。

モジュールと他の暗号パラメータの選択についての議論を続けると、その暗号モジュールを追加することができます（ n = 527）一部のソーステキストでは、暗号化がまったく許可されていません。 この場合、公開鍵eの値の選択は大きな役割を果たしません。 モジュロを使用して選択した暗号ではまったく暗号化できないプレーンテキスト値があります n = 527.

与えられたeのどれも、数字で表されるプレーンテキストを暗号化することはできません
187 , 341 , 154 と 373 .

例（一部のソーステキストの値を暗号化できない）

ソーステキストを4つのブロックで表すようにします y =（y 1 = 154、y 2 = 187、y 3 = 341、y 4 = 373）。 出展者 e暗号の公開鍵は、オイラー関数を使用する任意の互いに素な数値にすることができます φ（n）=φ（527）= 480。 ただし、検討中のケースでは、公開鍵 e任意に設定できます。 確かに、 e = 2、4、7、9、17、111それから：

154 2（mod527）= 1;
154 4（mod527）= 1;
154 7（mod527）= 154;
154 9（mod527）= 154;
154 17（mod527）= 154;
154111（mod527）= 154;
187 2（mod527）= 187;
187 4（mod527）= 187;
187 7（mod527）= 187;
187 9（mod527）= 187;
187 17（mod527）= 187;
187 111（mod527）= 187;
341 2（mod527）= 341;
341 4（mod527）= 1;
341 7（mod527）= 341;
341 9（mod527）= 341;
341 17（mod527）= 341;
341 111（mod527）= 341;
373 2（mod527）= 1;
373 4（mod527）= 373;
373 7（mod527）= 373;
373 9（mod527）= 373;
373 17（mod527）= 373;
373 111（mod527）= 373.

検討した例から簡単な結論が得られます。 実際、暗号化プロセスパラメータの選択には非常に注意深く取り組む必要があり、そのようなパラメータの徹底的な予備分析を実行する必要があります。 これを行う方法は別の問題であり、この作業の枠組み内では考慮されていません。

使用されるキーの構造に応じて、暗号化方法は次のように分けられます。

  • 対称：許可されていない人は暗号化アルゴリズムを知っているかもしれませんが、秘密情報のごく一部は不明です。これは、メッセージの送信者と受信者で同じキーです。 例：DES、3DES、AES、Blowfish、Twofish、GOST 28147-89
  • 非対称暗号化：サードパーティは暗号化アルゴリズムを知っている可能性があり、場合によっては公開鍵を知っている可能性がありますが、受信者だけが知っている秘密鍵は知らない可能性があります。 公開鍵暗号システムは現在、さまざまなネットワークプロトコル、特にTLSプロトコルとその前身のSSL（HTTPSの基礎）、SSH、PGP、S /MIMEなどで広く使用されています。非対称暗号化を使用したロシアの標準- 。

現在、RSA公開鍵（アルゴリズムの作成者であるRivest、Shamir、Aldemanの略）に基づく非対称暗号化は、情報セキュリティ市場のほとんどの製品で使用されています。

その暗号の強さは、整数の除数の存在の問題を解決する必要があるため、大きな数を因数分解することの難しさ、つまり、公開鍵に基づいて秘密鍵を決定するタスクの非常に難しいことに基づいています。 最も暗号的に強力なシステムは、1024ビット以上の数値を使用します。

実用的な観点からRSAアルゴリズムを検討してください。

まず、公開鍵と秘密鍵を生成する必要があります。

  • 2つの大きな素数pとqを取ります。
  • qにpを掛けた結果としてnを定義しましょう（n = p * q）。
  • dと呼ぶ乱数を選びましょう。 この数は、乗算（p-1）*（q-1）の結果と互いに素でなければなりません（1以外の最大公約数はありません）。
  • 次の関係（e * d）mod（（p-1）*（q-1））=1が真である数eを定義しましょう。
  • 公開鍵を番号eとn、秘密を--dとnと呼びましょう。

公開鍵（e、n）を使用してデータを暗号化するには、次のものが必要です。

  • 暗号文をブロックに分割します。各ブロックは、数値M（i）= 0,1,2 ...、n-1（つまり、n-1までのみ）として表すことができます。
  • 式C（i）=（M（I）^ e）mod nに従って、数列M（i）と見なされるテキストを暗号化します。

秘密鍵（d、n）を使用してこのデータを復号化するには、次の計算を実行する必要があります。M（i）=（C（i）^ d）modn。 その結果、元のテキストを表す一連の数値M（i）が取得されます。

次の例は、RSA暗号化アルゴリズムを明確に示しています。

RSAアルゴリズムを使用して、メッセージ「CAB」を暗号化および復号化してみましょう。 簡単にするために、小さな数を取りましょう-これは計算を短くします。

  • p=3とq=11を選びましょう。
  • n = 3 * 11=33と定義しましょう。
  • （p-1）*（q-1）=20を見つけます。 したがって、dは、たとえば3に等しくなります（d = 3）。
  • 次の式に従って数値eを選択します：（e * 3）mod 20=1。 したがって、eは、たとえば7：（e = 7）に等しくなります。
  • 暗号化されたメッセージを0から32の範囲の数字のシーケンスとして表現しましょう（n-1で終わることを忘れないでください）。 文字A=1、B = 2、C=3。

次に、公開鍵（7.33）を使用してメッセージを暗号化します。

C1 =（3 ^ 7）mod 33 = 2187 mod 33 = 9;
C2 =（1 ^ 7）mod 33 = 1 mod 33 = 1;
C3 =（2 ^ 7）mod 33 = 128 mod 33 = 29;

次に、秘密鍵（3.33）を使用してデータを復号化します。

M1 =（9 ^ 3）mod 33 = 729 mod 33 = 3（C）;
M2 =（1 ^ 3）mod 33 = 1 mod 33 = 1（A）;
M3 =（29 ^ 3）mod 33 = 24389 mod 33 = 2（B）;

データが復号化されました！

はじめに3

主要部分5

1創作の歴史5

2アルゴリズムの説明5

2.1キーの生成6

2.2暗号化と復号化6

2.3使用例7

結論9

使用済みソースのリスト10

序章

暗号化は、通常の文章を変更するための特別なシステムであり、このシステムを知っている限られた数の人々だけがテキストを理解できるようにするために使用されます。

暗号化は、数学的方法を使用して情報を保護する科学です。

最新の暗号化には次のものが含まれます。

    対称暗号システム;

    非対称暗号システム;

    電子デジタル署名（EDS）システム。

    ハッシュ関数;

    キー管理;

    隠された情報を取得する。

    量子暗号。

対称暗号化-アルゴリズムは対称と呼ばれ、同じ（送信者と受信者だけが知っている）秘密鍵が暗号化と復号化に使用されます。

一般的な対称暗号化アルゴリズム：

    AES（Advanced Encryption Standard）-アメリカの暗号化標準。

    GOST28147-89-国内データ暗号化標準。

    DES（eng。Data Encryption Standard）-AESまでの米国のデータ暗号化標準。

    3DES（トリプルDES、トリプルDES）;

    IDEA（英語国際データ暗号化アルゴリズム）;

    SEED-韓国のデータ暗号化規格。

    椿は日本での使用が認定された暗号です。

    XTEAは、実装が最も簡単なアルゴリズムです。

非対称暗号化アルゴリズムは、主に対称暗号システムの主な欠点である鍵の管理と配布の複雑さを排除するように設計されています。

すべての非対称暗号アルゴリズムの基本は、秘密鍵を知らなくても平文を復元するという計算の複雑さです。

非対称暗号化アルゴリズムの例：

    ディフィーヘルマン;

    RSA-Rivest、Shamir、Adelman-短時間で多数を因数分解するタスクの複雑さに基づいています。

    DSA-デジタル署名アルゴリズム、米国標準。

    GOST R 34.10-94、2001、RF規格。

このエッセイでは、非対称暗号暗号化アルゴリズムであるRSAアルゴリズムについて詳しく検討します。

主要部分

RSAアルゴリズム（Rivest、Shamir、およびAdlemanの略）は、大整数因数分解問題の計算の複雑さに基づく公開鍵暗号アルゴリズムです。 RSA暗号システムは、暗号化とデジタル署名の両方に適した最初のシステムでした。

    創造の歴史

1976年11月に発行されたWhitfieldDiffieとMartinHellmanの記事「暗号化の新しい方向性」は、公開鍵暗号化の基礎を築くことによって暗号化システムに革命をもたらしました。 その後開発されたDiffie-Hellmanアルゴリズムにより、2者は安全でない通信チャネルを使用して共有秘密鍵を取得できました。 ただし、このアルゴリズムでは認証の問題は解決されませんでした。 追加の資金がなければ、ユーザーは共有秘密鍵を誰と正確に生成したのかを確信できませんでした。

この論文を研究した後、マサチューセッツ工科大学（MIT）の3人の科学者Ronald Linn Rivest、Adi Shamir、Leonard Adlemanは、ホイットフィールドディフィーとマーティンヘルマンの公開鍵暗号システムのモデルを可能にする数学関数の発見に着手しました。 40以上の可能性に取り組んだ後、彼らは大きな素数を見つけるのがいかに簡単で、2つの大きな素数の積を因数分解するのがどれほど難しいかという違いに基づいてアルゴリズムを見つけることができました。これは後にRSAとして知られるようになりました。 システムは、その作成者の名前の最初の文字にちなんで名付けられました。

    アルゴリズムの説明

非対称アルゴリズムの最初のステップは、公開鍵と秘密鍵のペアを作成し、公開鍵を「世界中に」配布することです。

      キーの作成

RSAアルゴリズムの場合、キー生成ステージは次の操作で構成されます。

この数はオープン指数と呼ばれます

      暗号化と復号化

送信者が受信者にメッセージを送信したいとします。

メッセージは、0からの範囲の整数です。 。 図1に、RSAアルゴリズムの図を示します。

図1-RSAアルゴリズムのスキーム

送信者アルゴリズム：

レシーバーアルゴリズム：

RSAスキームの基礎となる式（1）および（2）は、セットの相互に逆の変換を定義します。

      使用例

表1に、RSAアルゴリズムの使用例を示します。 送信者は暗号化されたメッセージ「111111」を送信し、受信者は秘密鍵を使用してメッセージを復号化しました。

表1-RSAアルゴリズムの段階的実行

操作の説明

運転結果

キー生成

2つの素数を選択してください

モジュラスを計算する

オイラー関数を計算する

公開出展者を選ぶ

秘密の指数を計算する

暗号化

暗号化するテキストを選択

暗号文を計算する

復号化

元のメッセージを計算する

結論

この要約では、RSA非対称暗号化アルゴリズムが詳細に検討されました。 その作成の歴史が説明され、キーを作成するためのアルゴリズム、暗号化および復号化が説明されました。 RSAアルゴリズムの実際の使用例も示されています。

使用されたソースのリスト

    セメノフYu.A. インターネットプロトコル//M.: Prospekt、2011年。-114ページ。

    Belyaev A.V. 情報保護の方法と手段//ChFSPbGTU、2010年。-142p。

    VenboM.現代の暗号。 理論と実践//M.: Williams、2005.-768p。

    シュナイアーB.応用暗号。 プロトコル、アルゴリズム、原文// M .: Triumph、2002.-816p。

    RSAアルゴリズム//インターネットリソース：http：//ru.wikipedia.org/wiki/Rsa

各暗号化サイクルでのRSA暗号システムは、次の式に従って、整数と見なされる長さsize（n）のバイナリ平文ブロックmを変換します。c= me（mod n）。

この場合、n = pq , ここで、pとqは大容量のランダムな素数であり、モジュラスとキーの形成後に破壊されます。 公開鍵は、eとnの数字のペアで構成されます . サブキーeは、範囲1から十分に大きい数として選択されます。< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. さらに、方程式xe +yφ（n）= 1を整数x、yで解くと、d = x、つまり ed = 1（j（n））。 この場合、すべてのmについて、関係m ed = m（n） , したがって、dの知識により、暗号文を復号化できます。

情報を安全に保護するために、公開鍵システムには次の2つの要件があります。

1.ソーステキストの変換では、公開鍵に基づく回復を除外する必要があります。

2.公開鍵から秘密鍵を導出することも、計算上実現不可能でなければなりません。 この場合、暗号を解読する複雑さ（操作の数）の正確に低い推定値が望ましいです。

公開鍵暗号化アルゴリズムは、現代の情報システムで広く使用されています。

簡単な例を使用して、RSA暗号システムの構築を検討してください。

1. p=3およびq=11を選択します。

2. n=3∙11=33を定義します。

3. j（n）=（p – 1）（q – 1）=20を見つけます。

5. 7d = 1（mod 20）を満たす数dを選択します。

d = 3（mod 20）であることが簡単にわかります。

A = 1、B = 2、C = 3、...、Z = 26の対応を使用して、暗号化されたメッセージを整数のシーケンスとして表します。size（n）=6なので , 次に、暗号システムは、ブロックと見なされるラテンアルファベットの文字を暗号化できます。公開鍵（e、n）=（7、33）を公開し、秘密通信システムの他の参加者を招待して、アドレスに送信されるメッセージを暗号化します。このメッセージをCABとします。 , これは、選択したエンコーディングで（3、1、2）の形式を取ります。送信者は、各ブロックを暗号化し、暗号化されたメッセージを次のアドレスに送信する必要があります。

RSA（C）= RSA（3）= 3 7 = 2187 = 9（mod 33）;
RSA（A）= RSA（1）= 1 7 = 1（mod 33）;
RSA（B）= RSA（1）= 2 7 = 128 = 29（mod 33）。

暗号化されたメッセージ（9、1、29）を受信すると、秘密鍵（d、n）=（3、33）に基づいてメッセージを復号化し、各ブロックをd=3の累乗にします。

9 3 = 729 = 3（mod 33）;
1 3 = 1（mod 33）;
29 3 = 24389 = 2（mod 33）。

この例では、力ずくで秘密鍵を見つけるのは簡単です。 実際には、これは不可能です。 現在、次のsize（n）の値が実際の使用に推奨されています :


・512〜768ビット-個人用。

・1024ビット-商用情報用。

・2048ビット - 機密情報について。

RSAアルゴリズムの実装例は、リスト18.1および18.2（コンパイラー-Delphi、FreePascal）に示されています。

リスト18.1 PascalでのRSAアルゴリズムの実装例

プログラムRsa;
（$ APPTYPEコンソール）
（$ IFDEF FPC）
（$ MODE DELPHI）
（$ ENDIF）

SysUtils、uBigNumberを使用します。

//乱数ジェネレータ

vart：バイトの配列;
var pos：整数;
var cbox：バイトの配列=
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

プロシージャInicMyRandom;
var i：整数;
vars：string;
始める
WriteLn（"ジェネレータを初期化するためのテキストを入力してください
乱数（最大256文字）： "）;
ReadLn（s）;
i：= 1;
一方（私は<=255) and (i<=Length(s)) do

関連記事