RSAアルゴリズムはどのように計算されますか？

RSAは公開鍵暗号化用の暗号システムであり、特にインターネットなどの安全でないネットワークを介して送信される場合に、機密情報を保護するために広く使用されています。

RSAアルゴリズムは、最も一般的な非対称鍵暗号化アルゴリズムであり、大きな素数を検出して乗算するだけで、それらの積を因数分解するのは複雑であるという数学的事実に依存しています。秘密鍵と公開鍵の両方が必要です。

RSAアルゴリズムの例

この手順の例を見て、概念を学びましょう。読みやすくするために、アルゴリズムの手順とともにサンプル値を書き込むことができます。

• 2つの大きな素数PとQを選択します

  P =47、Q=17とします

• N =PxQを計算する

  N =7 x 17=119です。

• （P -1）x（Q – 1）

  の要素にならないように、公開鍵（つまり、暗号化鍵）Eを選択します。

  • （7-1）x（17 -1）=6 x 16 =96

    を見つけましょう

  • 96の因数は2、2、2、2、2、および3です（96 =2 x 2 x 2 x 2 x 2 x 3であるため）。

  • したがって、Eの因子が2と3にならないようにEを選択できます。Eを4（因子として2があるため）、15（因子として3があるため）、6（因子として3があるため）として選択することはできません。要因として2と3の両方があります。

  • Eを5として選択しましょう（2と3を考慮しない他の数値にすることもできます）。

• 次の式を含む秘密鍵（つまり、復号化鍵）Dを選択します。

  （D x E）mod（P – 1）x（Q – 1）=1

  • 方程式のE、P、Qの値を代入してみましょう。

  • （D x 5）mod（7 – 1）x（17 – 1）=1です。

  • つまり、（D x 5）mod（6）x（16）=1です。

  • つまり、（D x 5）mod（96）=1

  • いくつかの計算の後、D =77とします。その場合、次のようになります。（77 x 5）mod（96）=385 mod 96=1これは私たちが望んでいたことです。

• 暗号化の場合、次のようにプレーンテキスト（PT）から暗号文（CT）を計算します。

  CT =PT ^E mod N

  プレーンテキスト10を暗号化するとします。次に、

  CT =10 ⁵ mod 119 =100000 mod 119=40。

• CTを暗号文として受信者に送信します。

  暗号文として40を受信者に送信します。

• 復号化の場合、暗号文（CT）からプレーンテキスト（PT）を次のように計算します。

  PT =CT ^D mod N

  次のことを実行します：

  PT =CT ^D mod N

  つまり、

  PT =40 ⁷⁷ mod 119 =10、これはstep5の元の平文でした。