ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

ノリの悪い日記 https://www.port-k.com

陥没地帯 (265)

高校数学整数問題

$2006$ 年横浜市大の問題. 巨大な整数 (合成数) $N$ *1の素因数分解は, 現時点で実用化されている手段では非常に困難であるということにもとづいた $RSA$ 暗号 *2 に関して, もし, トーシェント関数の値 $\phi(N)$ を知ることができたら, 公開されている $N$ を素因数分解することは容易であるということを示す問題であろう.

【問】
f:id:noriharu-katakura:20211028094949j:plain

【解】
$(1)$ $(\mathrm{i})$
$N$ よりも小さい自然数で, $p$ の倍数の集合と $q$ の倍数の集合の和に含まれる要素である.

$(\mathrm{ii})$
$\phi(pq) = \phi(p)\phi(q)$

だから, $\phi(N) = (p-1)(q-1)$

$(2)$

$\phi(N) \\= pq -(p+q) +1 \\= N -(p+q) +1$

から, $p+ q = N-\phi(N)+1$

したがって, $p$ , $q$ を解にもつ $2$ 次方程式は,

$t^2 -\{N- \phi(N)+1\}t +N= 0$

である.

$(3)$

問 $(2)$ から, $p$ , $q$ は,

$t^2 -18426t + 84773093 = 0$

の $2$ 解である.

$\begin{eqnarray} D/4 &=& (9213)^2 -84773093\\ &=& 84879369-84773093\\ &=& 106276\\ &=& (326)^2 \end{eqnarray}$

したがって,

$t = 9213 \pm 326$

これから,

$(p,q) = (8887,9539)$ , $(9539, 8887)$
//

※ $RSA$ 暗号の原理とは, 以下のようになる.

$(1)$ $2$ つの素数 $p$ , $q$ から $N= pq$ とする.

$(2)$ $\phi(N)$ と互いに素な正の整数 $e$ をひとつ決め, $e$ と $N$ の双方を公開鍵とする. 巨大な $N$ の素因数分解は, 現時点で実用化されている手段では非常に困難である.

$(3)$ $\phi(N)$ と $e$ は互いに素なので, $ed \equiv 1 \pmod {\phi(N)}$ となる正の整数 $d$ が存在し (直前の記事参照), この $d$ を復号のための秘密鍵とする. なお, $d$ を実際に求める方法は, 記事 $(239)$ を参照.

$(4)$ 送り手は, $N$ より小さい正の整数 $a$ を送るために, 公開鍵を使って $a' \equiv a^e \pmod{N}$ を計算し, $a'$ を暗号として受け手に送る.

$(5)$ 受け手は, 秘密鍵 $d$ と $N$ により, $a \equiv (a')^d \pmod{N}$ として復号する.

証明が必要なのは, 最後の $a \equiv (a')^d \pmod{N}$ のところだけであるが, $a'$ と $N$ が互いに素であるとは限らないことに留意する.

【証明】
$\phi(N) = \phi(pq) = \phi(p)\phi(q)$ なので, $\phi(N) = (p-1)(q-1)$ となる.

$k$ を整数として, $ed = k(p-1)(q-1) +1$ とおくことができる. これから,

$ed-1 = k(p-1)(q-1)$

である. すると, $ed-1$ は, $p-1$ でも $q-1$ でも割り切れるので,

$ed \equiv 1 \pmod{p-1}$

および,

$ed \equiv 1 \pmod{q-1}$

となる. 最初の式から, $m$ を整数として,

$ed = m(p-1) +1$ とおけるが,

$a$ が $p$ と互いに素の場合は, フェルマーの小定理 (証明は記事 $(263)$ 参照) から,

$a^{p-1} \equiv 1 \pmod{p}$ なので,
$a^{ed} -a \equiv 0 \pmod{p}$ である.

$a$ が $p$ と互いに素でない場合, $p$ は素数なので, $a$ は $p$ の倍数となり, $a \equiv 0 \pmod{p}$ となる. すると, やはり, $a^{ed} - a \equiv 0 \pmod{p}$ がいえる.

同様にして, $a^{ed}-a \equiv 0 \pmod{q}$ もいえる.

以上から, $a^{ed} -a$ は $p$ でも $q$ でも割り切れるので, $pq$ でも割り切れる. したがって,

$a^{ed} -a \equiv 0 \pmod{pq}$

がいえ,

$(a')^d \equiv a \pmod{N}$

となる.//

*1:現在, 安全とされているのは, $2048 \ \mathrm{bit}$ , つまり $2$ つの素数の積からなる, $10$ 進法で $617$ 桁の合成数である.

*2: $1977$ 年にこの方法を提唱した $3$ 人の数学者 Rivest, Shamir, Adleman の頭文字を取って名付けられた.