RSA暗号に関する2つの問題が出題されています。 (1) $-13e + (p-1)(q-1) = 1$ という条件から、$ed \mod (p-1)(q-1) = 1$を満たす自然数 $d$ ($1 < d < (p-1)(q-1)$) を求め、その2進数表示を計算します。ここで、$p=5$, $q=11$, $e=3$です。 (2) $m^e \mod n = 13$ となる自然数 $m$ ($0 < m < n$) を、高速指数演算を用いて計算します。ここで、$n=pq=5 \times 11 = 55$ であり、$e=3$です。

1. 問題の内容

RSA暗号に関する2つの問題が出題されています。

(1) $-13e + (p-1)(q-1) = 1$ という条件から、$ed \mod (p-1)(q-1) = 1$を満たす自然数 $d$ ($1 < d < (p-1)(q-1)$) を求め、その2進数表示を計算します。ここで、$p=5$, $q=11$, $e=3$です。

(2) $m^e \mod n = 13$ となる自然数 $m$ ($0 < m < n$) を、高速指数演算を用いて計算します。ここで、$n=pq=5 \times 11 = 55$ であり、$e=3$です。

2. 解き方の手順

(1)

まず、$(p-1)(q-1)$を計算します。

$(p-1)(q-1) = (5-1)(11-1) = 4 \times 10 = 40$

次に、$-13e + (p-1)(q-1) = 1$ に $e=3$ と $(p-1)(q-1) = 40$を代入します。

$-13 \times 3 + 40 = -39 + 40 = 1$

したがって、

$ed \mod 40 = 1$

$-13e + (p-1)(q-1) = 1$　を書き換えると、 $-13e - 1 = -(p-1)(q-1)$

$-13e - 1 = -40$

$-13 \times 3 - 1 = -40$

$1 = 40 + (-13) \times 3$

$1 = 40 - 39$

ここで、$ed \mod 40 = 1$　から，$3d \mod 40 = 1$ となる $d$ を探すことになります。

$3d = 1 + 40k$ となる整数 $k$ を探すことになります。

$k = 2$のとき、$3d = 1 + 40 \times 2 = 81$

$d = 81/3 = 27$

$d = 27$　は $1 < d < (p-1)(q-1) = 40$ を満たします。

$d = 27$ の2進数表示は、$27 = 16 + 8 + 2 + 1 = 2^4 + 2^3 + 2^1 + 2^0$なので、11011 です。

(2)

$m^3 \mod 55 = 13$ となる $m$ を探します。

$n=55=5 \times 11$ であるので、

$m^3 \equiv 13 \pmod{5}$　かつ　$m^3 \equiv 13 \pmod{11}$ を満たす必要があります。

$m^3 \equiv 13 \equiv 3 \pmod{5}$

$m=0,1,2,3,4$ について、$m^3 \pmod{5}$ を計算すると、

$0^3 \equiv 0 \pmod{5}$

$1^3 \equiv 1 \pmod{5}$

$2^3 \equiv 8 \equiv 3 \pmod{5}$

$3^3 \equiv 27 \equiv 2 \pmod{5}$

$4^3 \equiv 64 \equiv 4 \pmod{5}$

よって、$m \equiv 2 \pmod{5}$

$m^3 \equiv 13 \equiv 2 \pmod{11}$

$m=0,1,2,3,4,5,6,7,8,9,10$ について、$m^3 \pmod{11}$ を計算すると、

$0^3 \equiv 0 \pmod{11}$

$1^3 \equiv 1 \pmod{11}$

$2^3 \equiv 8 \pmod{11}$

$3^3 \equiv 27 \equiv 5 \pmod{11}$

$4^3 \equiv 64 \equiv 9 \pmod{11}$

$5^3 \equiv 125 \equiv 4 \pmod{11}$

$6^3 \equiv 216 \equiv 7 \pmod{11}$

$7^3 \equiv 343 \equiv 2 \pmod{11}$

$8^3 \equiv 512 \equiv 6 \pmod{11}$

$9^3 \equiv 729 \equiv 3 \pmod{11}$

$10^3 \equiv 1000 \equiv 10 \pmod{11}$

よって、$m \equiv 7 \pmod{11}$

$m \equiv 2 \pmod{5}$　かつ $m \equiv 7 \pmod{11}$

$m = 5k + 2 \equiv 7 \pmod{11}$

$5k \equiv 5 \pmod{11}$

$k \equiv 1 \pmod{11}$

$k = 11j + 1$

$m = 5(11j + 1) + 2 = 55j + 5 + 2 = 55j + 7$

$m \equiv 7 \pmod{55}$

したがって、$m = 7$

3. 最終的な答え

(1) $d = 27$、2進数表示は 11011

(2) $m = 7$