与えられた2つの素数 $p=7$ と $q=19$ を用いて、公開鍵 $e$ と秘密鍵 $d$ を計算する問題です。

1. 問題の内容

与えられた2つの素数 $p=7$ と $q=19$ を用いて、公開鍵 $e$ と秘密鍵 $d$ を計算する問題です。

2. 解き方の手順

RSA暗号の鍵生成手順に従います。

ステップ1: $n$ を計算します。

$n$ は2つの素数 $p$ と $q$ の積です。

$n = p \times q$

$n = 7 \times 19 = 133$

ステップ2: $\phi(n)$ (オイラーの$\phi$関数) を計算します。

$\phi(n) = (p-1) \times (q-1)$

$\phi(n) = (7-1) \times (19-1) = 6 \times 18 = 108$

ステップ3: 公開鍵 $e$ を選択します。

$e$ は $1 < e < \phi(n)$ を満たし、$\phi(n)$ と互いに素である必要があります。

つまり、$e$ と $\phi(n)$ の最大公約数が1である必要があります。

$e$ は、例えば $5$ を選択できます（$5$ と $108$ は互いに素）。

$7$は108の約数ではないため、$e = 7$としても構いません.

解答は2桁で入力する必要があるため、$e = 7$とすると条件を満たさないため、他の数値を探します。

$e=13$の場合、$13$と$108$は互いに素です。

ステップ4: 秘密鍵 $d$ を計算します。

$d$ は $e \times d \equiv 1 \pmod{\phi(n)}$ を満たす必要があります。

つまり、$e \times d$ を $\phi(n)$ で割った余りが1になるような $d$ を求めます。

$13 \times d \equiv 1 \pmod{108}$

$13d = 108k + 1$ となる整数 $k$ を探します。

$d = (108k + 1) / 13$

$k=5$とすると $d = (108 \times 5 + 1)/13 = (540+1)/13 = 541/13 = 41.615...$

$k=8$とすると $d = (108 \times 8 + 1)/13 = (864+1)/13 = 865/13 = 66.538...$

$k=10$とすると $d = (108 \times 10 + 1)/13 = (1080+1)/13 = 1081/13 = 83.153...$

$k=13$とすると $d = (108 \times 13 + 1)/13 = (1404+1)/13 = 1405/13 = 108.076...$

$k=2$とすると $d = (108 \times 2 + 1)/13 = (216+1)/13 = 217/13 = 16.69...$

$k=16$とすると $d = (108 \times 16 + 1)/13 = (1728+1)/13 = 1729/13 = 133$

$13 \times 5 \pmod{108} = 65 \pmod{108} = 65 \neq 1$

拡張ユークリッドの互除法を使うと、

$108 = 13 \times 8 + 4$

$13 = 4 \times 3 + 1$

$1 = 13 - 4 \times 3 = 13 - (108 - 13 \times 8) \times 3 = 13 - 108 \times 3 + 13 \times 24 = 13 \times 25 - 108 \times 3$

よって、$13 \times 25 \equiv 1 \pmod{108}$

したがって、$d = 25$

$e = 13, d = 25, n = 133, \phi(n) = 108$

3. 最終的な答え

公開鍵 $e = 13$

秘密鍵 $d = 25$