はじめに

手動で秘密鍵を求めるための手順をエントリーします。
最初はOpen-SSLを使って説明する予定でしたが、最小長(32bit)でも膨大な計算量になるためもっと簡単な数値を使って説明しようと思います。

秘密鍵の条件

パラメータ	型	式	概要
modulus	INTEGER	n = pxq	公開鍵(その１)
publicExponent	INTEGER	e = 13 (=0x01101)	公開鍵(その２)
privateExponent	INTEGER	d ≡ e^(-1) mod (p-1)x(q-1)	秘密鍵
prime1	INTEGER	p	秘密鍵生成時に作られるランダムな素数(その1)
prime2	INTEGER	q	秘密鍵生成時に作られるランダムな素数(その2)

RSAの秘密鍵を求めるには以下の法則があります。

RSA暗号では、ed ≡ 1 mod (p - 1)(q - 1) となる正整数 d を求める必要がある(これが秘密鍵になる)
e は(p - 1)(q - 1)と互いに素になる値で(p - 1)(q - 1)より小さい値である事
e と(p - 1)(q - 1)が互いに素ならば ed ≡ 1 mod (p - 1)(q - 1) となる d は必ず存在する
+d はユークリッド互除法の応用で計算可能

今回の値は

p = 29  ← 秘密鍵に必要なランダムな素数(その1) 
q = 103 ← 秘密鍵に必要なランダムな素数(その2) 
e = 13 ← 固定値

n = p * q ← 2987
l = (p-1) * (q-1) ← 2856

とします。

ユーグリッド互除法とは

ユーグリッド互除法とは２つの自然数の最大公約数を求める手法の一つです。
この手法を使って l と e の値が「互いに素」かどうかを調べる事ができます。
「互いに素」と言うのは、2値の最大公約数が 1 であるということです(お互い素数って事です)

下記のコードは「ユーグリッド互除法」のアルゴルをＣ言語に置き換えたものです。
これ使えば最大公約数が求まります。

// 最大公約数を求める(l >= e)
int gcd(int e, int l)
{
    return (e==0)? l : gcd( l%e, e);
}

int main(){
    int p = 29;
    int q = 103;
    int e = 13;
    int l = (p-1)*(q-1); // 2856

    printf("gcd(e, l)=%d", gcd(e, l));
}

「gcd(e, l) = 1」であることを確認出来ました。

次に「ed = 1 (mod l)」を満たす d を求めます。
これは「拡張ユークリッド互除法」で求める事ができます。

拡張ユーグリッド互除法とは

拡張ユークリッド互除法とは、整数 e, l の最大公約数を gcd(e, l) と表すときに、ユークリッドの互除法を用いて、ex + ly = gcd(e, l) の解となる整数 x, y の組を見つける方法です。

つまり秘密鍵を作るには「gcd(e, l) = 1」なので「拡張ユーグリッド互除法」を使って、 ex + ly = 1 の x と y を求めろと言うことです。
ここで決まった x が d になります。
もし「 x < 0 」の場合は、 x に l を足した値が d になります(これを加法的逆元と言います)

拡張ユーグリッド互除法(手動)

(l ≧ e) の場合 gcd(e, l) = 1 を求める過程において

    2856 - (219 x 13) = 9
      13 - (  1 x  9) = 4
       9 - (  2 x  4) = 1

ここで上から2番目の式にある 9 の値に着目してみましょう。
よく見ると 9 は 2856 - (219 x 13) と置き換えられる事に気づきませんか？

    13 - ( 1 x  9) = 4
    13 - ( 1 x (2856 - (219 x 13)) ) = 4  ← 2856 - (219 x 13) を 9 に代入
    13 + -2856 + (219 x 13)   = 4         ← ()を外す
    (13 * 220 ) + (2856 * -1) = 4         ← ex + ly = r の形にする

この方法により ex + ly = r の形に出来る事が分かりました。
後はこれを ex + ly = 1 になるまで繰り返せば完了です。

回数	l	e	r	ex + ly = c
1回目	2856	13	9	(13 * -219) + (2856 * 1) = 9
2回目	13	9	4	(13 * 220) + (2856 * -1) = 4
3回目	9	4	1	(13 * -659) + (2856 * 3) = 1

最終的に (13 * -659) + (2856 * 3) = 1 となりました。
xは-659で(x < 0) なので、x=-659 に l=2856 を足した値が d になります。
計算をすると d の値は 2856 + -659 = 2197 です。
なので公開鍵、秘密鍵それぞれの値は以下の様になります。

公開鍵その1(e)：13
公開鍵その2(n)：2987
秘密鍵(d)：2197

拡張ユーグリッド互除法(C言語)

#include <stdio.h>

// 拡張ユークリッド互除法
int extendedGCD(int a, int b, int *x, int *y) {
    // ベースケース
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    // 再帰的に呼び出す
    int x1, y1;
    int gcd = extendedGCD(b, a % b, &x1, &y1);

    // x, yを更新
    *x = y1;
    *y = x1 - (a / b) * y1;

    return gcd;
}

int main() {
    int a = 2856; // l
    int b = 13; // e

    int x, y;
    int gcd = extendedGCD(a, b, &x, &y);

    printf("最大公約数 (GCD): %d\n", gcd);
    printf("整数係数 (x, y): %d, %d\n", x, y);

    return 0;
}

暗号化と復号

暗号化と復号の方法についてはこちらのサイトを参考にさせていただきました。(リンク先の説明の方が分かりやすいかも)
RSA暗号で「ふっかつのじゅもん」を作る(1) - Pashango’s Blog

当初、検証にはC言語を使う予定でしたが暗号・復号を行うには物凄い桁の数値を扱うため
桁あふれなどの考えるべき処理が多すぎて実際の検証には不向きだと言う事に気づき、同じ様にpython を使ってみる事にしました。

結果 pythonは相当な桁に耐える事ができる上に組み込み関数との併用で簡単に暗号・復号の検証が行えました。
Python凄い！

暗号化

暗号化は「x^e mod n」とするだけです、さっそく暗号化してみましょう

e=13	# 公開鍵 その1
n=2987	# 公開鍵 その2

org = [13,16,246,21,65,32]

crp = [pow(x, e, n) for x in org]
print (crp)

#crp => [2242, 1238, 2525, 997, 1997, 831]

復号

復号は「x^d mod n」するだけです。

n=2987	# 公開鍵 その1
d=2197	# 秘密鍵

print([pow(x, d, n) for x in crp])

#[13, 16, 246, 21, 65, 32]

おー凄い！ちゃんと復号が出来ました。

まとめ

拡張ユーグリッド互除法については、充分分かりやすい説明が出来たかなと思います。

しかし、 d ≡ e^(-1) mod (l) が ed ≡ 1 mod (l) と同等なのかがいまだに分からないままで、更に d を求める為の方式が ex + ly = 1 になるかが分からず消化不良となりました。
フェルマーとかオイラーとかの定理を参考にしたのですが全く分かりませんでした。
この辺の事を小学生でも理解できる説明をしていただける方がいればぜひコメントください。