ユークリッドの互除法とRSA暗号

上野竜生です。今回はユークリッドの互除法との関連テーマとしてRSA暗号を紹介します。
情報Iが試験に加わることを意識して情報的な背景の説明を長めにいれているのでさっさと数学的問題を解きたい人は「問題（再掲）」の段落まで読み飛ばしてください。

暗号の例

コンピュータは数値を扱うので，数値xを暗号化する関数f(x)を用意します。
Aさんが数値xをBさんに伝えるときに暗号化（f(x)を計算）し，その結果をBさんに伝えます。
Bさんはf(x)に対応した復号関数（＝暗号解読関数）g(x)をあらかじめ伝えておき暗号化されたものを関数gに代入して元の数値xを得ます

ところが暗号化ということなのでセキュリティ面が重要です。g(x)の計算内容が漏れる心配は少ないのですがf(x)の計算内容とその結果は漏れます。そこから第三者がg(x)を簡単に求められないような工夫がいるのです。

暗号の例１

数値Xを暗号化して数値Yを作る。

XからYに暗号化する手順(#)：Xに3を加えたものをYとする。

これで元のXを暗号化したつもりだったが手順(#)と，暗号化した後の数値Yが20であることが漏れてしまったとする。
手順(#)とY=20からもとのXを求めることはできるか？

この例１だと簡単にできますね。(#)の逆算が「Yから3をひく」とすぐにわかるのでX=17とバレてしまい，暗号化の意味が薄れてしまいます。

暗号の例２

2桁の数値Xを暗号化して数値Yを作る。

XからYに暗号化する手順(##)：Xを7倍し，101で割った余りをYとする。

これで元のXを暗号化したつもりだったが手順(##)と，暗号化した後の数値Yが20であることが漏れてしまったとする。
手順(##)とY=20からもとのXを求めることはできるか？

例１よりは少し難しいですがこれも割と簡単にできます。
不定方程式7X=101m+20の1つの解はX=75,m=5
となり，X=75とバレてしまいます。やってることはユークリッドの互除法なので数字が大きくなっても計算時間はそれほど爆発的には増加しません。

一般にこのような方法で絶対にバレない暗号は不可能です。（X=1から順番に当てはまればいつかバレる）ですが，暗号化する時間に比べて暗号を解く時間が膨大であれば現実的にバレないことになります。その方法の1つがRSA暗号です。

暗号の例３

2桁の数値Xを暗号化して数値Yを作る。

XからYに暗号化する手順(###)：Xを59乗し，115で割った余りをYとする。

これで元のXを暗号化したつもりだったが手順(###)と，暗号化した後の数値Yが20であることが漏れてしまったとする。
手順(###)とY=20からもとのXを求めることはできるか？

どうでしょう？例えばX=12を暗号化するのは59乗を正確に計算しなくても余りをたどるだけなので現実的に求められますが逆にY=20からXを復元するのは相当時間がかかりそうですよね？
X=10から順番に暗号化してみてY=20になるものを求めれば理論上は出せます。なので絶対にバレないわけではないですが現実的には難しいです。
実はこの問題を解読する一番のポイントは「素因数分解の計算が膨大な時間を要する」ことです。素因数分解さえ出来てしまえばそこからの解読は比較的容易にできます。これを実際にやってみましょう。

問題（再掲）

次のフェルマーの小定理を認めます：

数学に興味のある人ならフェルマーの小定理の結果を知っている，もしくは練習問題で証明させられたことがあると思います。この証明も高校範囲でやれますがここでは省略します。

115で割った余りを考えるので5で割った余りと23で割った余りを考える。
フェルマーの小定理よりnが5の倍数でないとき
n⁴を5で割った余りは1
つまりkを自然数として
n^4kを5で割った余りは1
n^4k+1を5で割った余りはaを5で割った余りと等しい・・・①

①はnが5の倍数のときも成り立つので①はすべての整数nについて成り立つ。

同様にするとすべての整数nについて
n^22k+1を23で割った余りはnを23で割った余りと等しい・・・②

4と22の最小公倍数が44であることに注意すると①②より
n^44k+1を5で割った余り,23で割った余りはnを5で割った余り,23で割った余りとそれぞれ等しい

つまり
n^44k+1を115で割った余りはnを115で割った余りと等しい
さらにnが2桁（114以下であること）を用いると
n^44k+1を115で割った余りはnである。

ここからの方針はnの59乗の余りがわかっているのでそれをさらにm乗して(44k+1)乗の形にすればいいのです。・・③
結果を先に言ってしまうと
\( (n^{59})^3=n^{177}=n^{44\cdot 4 +1} \)
なので(nの59乗)を3乗したものを115で割った余りが求めるnの値になるということです。
では「3乗」をどのようにして求めたかというとここでユークリッドの互除法が使えます。

③を式で表すと
59m=44k+1となる整数(m,k)を求めればよい。

不定方程式 59m-44k=1 の1つの解がm=3,k=4だからm乗，つまり3乗すればいい。

このとき
\( (n^{59})^3=n^{177}=n^{44\cdot 4 +1} \)
115で割った余りで考えるとnの59乗を115で割った余りが20。
nは2桁の整数だから
20の3乗を115で割った余りが求めるnである。
8000÷115=69あまり65　よりn=65　（答）

まとめと共通テスト出題可能性

コンピュータの暗号では問題文中の「115」の部分が膨大な桁数になります。そのときに素因数分解まで出来てしまえばそこから先はコンピュータにかかれば桁数が増えても短時間で処理できる内容なのですが，素因数分解が爆発的時間を要するため実質的に暗号の解読が不能となっています。
このように難しい数学を理解すると暗号などに役立つので数学に強い人は大学以降たくさん勉強して研究してみるといいでしょう。

この問題を共通テストの時間（大問1題15分～20分）の分量にすることはかなり難しいです。ただ，こういう題材の一部分を切り取って出題することは不可能とまでは言い切れないですし，2025年からは情報が入試科目に加わるため出題したいというのが本音でしょう。

内容は難しいですが出題を工夫して出される可能性があるのであらかじめ理解しておくと万が一出題された時に時間短縮になります。