RSA暗号の概要

　「RSA 暗号」は、暗号文を作る時の手法のひとつです。
　1978年にマサチューセッツ工科大の数学者３名によって発明されました。
　（以下、聞きかじりです。）

　「RSA 暗号」では、暗号化と解読に３つの数値を使います。
　暗号化に使う２つの数値を知っていれば、だれでも暗号文を作れますが、残り一つの数値を知らないとその暗号文を解読できないのが特徴です。( 不思議 … )

例えば、イギリス諜報本部が RSA暗号を使っていたとします。
ある時、配下のスパイ全員に「暗号化用数値は 6887 と 17」と指令。
配下のスパイ達は皆、諜報本部向けの暗号文を同じ方法で作れます。
ところが、配下のスパイの中に某敵国の２重スパイが…
やがてその２重スパイは 007 が作成した暗号文を傍受…
でもその暗号文は解読できません。( 残り一つの数値を知らないから.)

暗号文の作成手順

(1) あ～んの各文字に数値を割り付けた表を作成します。

    あ-00　か-05　さ-10　…　は-25　…　や-35　ら-41　わ-45　ん-50
    い-01　き-06　し-11　…　ひ-26　…　　-36　り-41　　-46　”-51
    う-02　く-07　す-12　…　ふ-27　…　ゆ-37　る-42　　-47　゜-52
    え-03　け-08　せ-13　…　へ-28　…　　-38　れ-43　　-48　、-53
    お-04　こ-09　そ-14　…　ほ-29　…　よ-39　ろ-44　を-49　。-54

(2) 暗号化する前の文を数値に置き換えます。

    お --> 04
    は --> 25
    よ --> 39
    う --> 02

(3) 暗号化、解読に使う数値を３つ決めます。

    ここでは、17, 53, 77 を使う事にします。

(4) (2) の数値を次の式で変換します。

    ( 04 の 17乗 ) ÷ 77 の余り ---> 16
    ( 25 の 17乗 ) ÷ 77 の余り ---> 09
    ( 39 の 17乗 ) ÷ 77 の余り ---> 30
    ( 02 の 17乗 ) ÷ 77 の余り ---> 18

    16 09 30 18 が暗号文になります。

※ サンプル・プログラムの「暗号化」で変換できます。

暗号文の解読手順

(5) 暗号文の各数値を次の式で順に再変換します。
    ( 16 の 53乗 ) ÷ 77 の余り ---> 04
    ( 09 の 53乗 ) ÷ 77 の余り ---> 25
    ( 30 の 53乗 ) ÷ 77 の余り ---> 39
    ( 18 の 53乗 ) ÷ 77 の余り ---> 02
※ サンプル・プログラムの「解読」で変換できます。

(6) (5) で求まった数値を (1) の表に基づき文字にします。
    04 --> お
    25 --> は
    39 --> よ
    02 --> う

３つの数値の決め方

暗号作成、解読に使う３つの数字は、実はある約束に従って決めます。

(1) まず、２つの素数（これは何でも良い）を決めます。

ここでは 7 と 11 にします。
そして 7･11 ( 77 ) を「公開鍵ｎ」と呼びます。

(2) 次に 0 より大きくて (7-1)･(11-1) より小さい素数(これも何でも良い)を決めます。

ここでは 17 にします。
そして、この 17 を「公開鍵ｅ」と呼びます。

(3) 17･A + (7-1)･(11-1)･B = 1 を満たす正の整数 A を求めます。

この A を「秘密鍵ｄ」と呼びます。
これを計算するのは少し面倒です。
何とか計算しますと A = 53, B = -15 が求まります。

※ サンプル・プログラムの「秘密鍵」で計算できます。

(4) (1) で決めた 77, (2) で決めた 17, (3) で求めた 53 が３つの数値です。

77, 17 は、それぞれ「公開鍵ｎ」「公開鍵ｅ」と呼び、暗号文を作成する人に通知します。
53 は、「秘密鍵ｄ」と呼び、暗号文を解読する人だけの秘密にしておきます。

補足

公開鍵の桁数が小さいと簡単に見破られる為、実際には１００桁位の数値を使うそうです。

「RSA暗号」、「拡張ユークリットの互除法」のキーワードで web 検索しますと、詳細を知る事ができます。