伊伊伊伊伊伊伊伊伊伊

RSA 暗号の仕組み
むらかみ村上せんずい仙瑞伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊伊§1．はじめにs を考える。この s の互いに素の条件は，証明の最整数の単元 (数学A) の発展的な内容として，合同後の方の式⑶で使う。また，それぞれ p−1，q−1式と素数を用いた RSA 暗号の解説を行った。このを考える理由は，後ほど出てくるフェルマーの小定

RSA 暗号とは現代のネットワークセキュリティに理を使うためである。

欠かせない暗号技術で整数の性質が使われている。

受信者 B は，送信者Aに自然数 n と s を伝え (こ暗号の仕組みは極めてシンプルである。また，生徒の n と s の数は公開しているので第三者にみられての整数問題に対する興味づけのために格好の材料でもかまわない)，A が用意した値 a を s 乗して n でもある。ただ，暗号の仕組みの証明はいろいろな書割った余りの値 b を B に伝えるように願える。この

籍で紹介されているが，きわめて専門的で複雑であとき，送信者Aのデータ a に対してる。しかし，証明の核心部分だけみればきわめてシa≡b (mod n)

ンプルで，積の合同式の性質，不定方程式の整数解が成り立っている。またこの操作を暗号化という。と解をもつための条件，フェルマーの小定理の 3 つ

次に暗号化された値 b を受信者 B が受け取り，こだけであり，青チャートでも解説されている。合同

こである条件を満たす自然数  を考え， 乗して n式を理解するにはちょうどよい教材の内容となる。

で割った余りが送信者Aの元データ a となり，元デ

このレポートでは私が考えたシンプルな教科書の発ータを受け取ることができる。

展的レベルでおさまる証明を紹介する。

つまり，b ≡(a)≡a (mod n)§2．証明に必要な 3 つの整数の性質と定理
1.

a≡b (mod n)  ac≡bc (mod n)2.

p が素数， が p の倍数でないとき， ≡1 (mod p) (フェルマーの小定理)

3. a と b が互いに素であるならば，不定方程式a+b=1 は整数解をもつ。
この 3 つの条件だけで RSA 暗号の仕組みを証明できる。

§3．RSA 暗号の仕組みと証明
送信者Aから受信者 B にデータを送信するとき，第三者にデータが盗まれる可能性がある。だから暗号化してデータを送る必要がある。暗号化の仕組みは次のとおりである。
まず受信者 B が，2 つの素数 p，q を用意して (こが成り立つ ，つまり，a≡a (mod n)…… ⑴を満たす  を求めればよい。
さて，受信者 B はどのようにして自然数  (これを復号鍵という) を見つけるのだろうか。この  のみつけ方であるが，p，q が素数のとき，任意の自然数 a， に対して，a ≡a (mod n)…… ⑵が成り立つことを利用する。まずこれを証明する。
 が p，q と互いに素のとき
 は n= pq と互いに素，フェルマーの小定理よりa ≡1 (mod p)すなわち (a )≡1(mod p)
よってa ≡1 (mod p)

また，p と q を入れ替えても同様のことがいえての 2 つの素数は秘密にしないといけない)，自然数a ≡1 (mod q)

n= pq と，( p−1) かつ (q−1) と互いに素な自然数

つまり，a −1 は，p の倍数でもあり，q の17倍数でもあるから，a −1 は n= pq で割いに素な自然数の 1 つ s=11 をつくり，送信者 Aり切れるので，a ≡1 (mod n) がいえる。

さんにAさんの誕生日を 11 乗して 9853 で割った余

よって，(aa a  

りを B さんに伝えるようにいう。これを式で表すと，) ≡1 (mod n)，

831≡8752 (mod 9853)≡1 (modn) となり，両辺に a をかけて 

≡a (mod n)

つまり，B さんは 8752 をAさんから受け取る。

a が p の倍数であり，q と互いに素のときすなわち (a )≡1

ここで B さんは，⑶を利用して，

a≡1 (mod q)

フェルマーの小定理より
(mod q)

不定方程式

11−9628=1を解く。この解は n を整数とすると，

 

≡1 (mod q)

=9628n+6127，=11n+7 を得るので， とし両辺を  乗して a をかけても，て =6127 を選び，A さんから受け取った 8752a ≡a (mod q) が成り立つ。ここで，を 6127 乗して 9853 で割った余りを考える。すると，

よってaa −a は，a が p の倍数でもあるので，p の倍数であり，q の倍数でもある。

831 を得て，A さんの誕生日が 8 月 31 日であることがわかる。式で表せば，8752≡831 (mod 9853)

よって，n= pq でも割り切れるのでa 

≡a (mod n)となる。

a が p かつ q の倍数のとき

さて，この一連の流れで，どこで秘密性が保たれ一般に，s が m の倍数であるとき，任意の自然数ているかというと，実は最初に考えた 2 つの素数 pu に対して，s ≡s (mod m) が成り立つ。と q である。この 2 つの素数は公開せず，受信者 B

よって，a は n= pq の倍数であるので，は秘密にしておかないといけない。送信者Aに 2 つ 

≡a (mod n) が成り立つ。の素数の積 n= pq を公開して伝えるので，第 3 者

以上からより，式⑵が証明された。

は n を 2 つの素数に素因数分解すれば暗号が解読でa複号化をするための自然数  の値は，⑴を満たす
 であるが，証明した式⑵を利用して，きるとわかっているのであるが，実際に使われている 2 つの素数は 200 桁で，2 つの素数の積 n は 400a=a 桁，この 400 桁の自然数を 2 つの素数の積に分解すを満たす  の値を求めればよい。

ることは，現代の一般のコンピューターでは一生かつまり，かるらしい。だから，ネットで検索してすぐに出てs=( p−1)(q−1)+1

くるような 2 つの素数ではセキュリティが守られなが成り立ち，つまり，不定方程式s−( p−1)(q−1)=1い。そうした現在のコンピューターの性能事情を利…… ⑶用した暗号システムが RSA 暗号なのである。逆に，を満たす  の値を求めればよいのである。この不定

2 つの巨大な素数がわかっていると，積 pq は計算方程式が解をもつための条件は， の係数 s と  のすることは簡単にできる。積は簡単だが，素因数分係数 ( p−1)(q−1) が互いに素である必要がある。

解は難しい。そうした計算事情を活用しているので最初に s を ( p−1) かつ (q−1) と互いに素であるよある。だからあるセキュリティ会社では，巨大な素うにしたのもこのためである。

数一覧表を厳重に金庫に保管している。素数はネッ以上で RSA 暗号の仕組みが解説できたので，次は具体的な数字で本当に成り立つか考えてみる。

§4．誕生日をあてよう
たとえば，送信者Aさんの誕生日 8 月 31 日をa=831 と表すことにする。受信者 B さんは，2 つの素数 p=59 と q=167 を用意して，n=59⋅167=9853 と p−1=58 と q−1=166 に互

18

トワーク社会の財産なのである。
もし素数の規則性がわかってしまうかコンピュー
ターの性能が飛躍的にのびると，素数一覧表を作ることができる。そうすると簡単に巨大な自然数 n を2 つの素数に分解できるようになり，現在のセキュリティシステムが一気に崩壊してしまうという危険性もはらんでいる。それが現在の暗号システムなのである。素数の規則性の発見やコンピューターの性能の向上は誰もが望んでいることだが，それができてしまうとセキュリティシステムが崩壊する。なん[5673215567942] と入力して，Shift+Enter キーをとも矛盾にみちた悩ましい問題なのである。

押すと簡単に，2×13×157×5813×239087 と表示される。

§5．WOLFRAM CLOUD を活用する
最後に WOLFRAM CLOUD を紹介する。最近

ちなみに家庭用コンピューターで簡単に計算できる数字は RSA 暗号で用いてはいけない。

までは，
Mathematica といえば高価な数学ソフトであったが，時代の流れからか，Web 上でかなりの計算をフリーで利用することができる。今回，§4．

§6．最後に最近，大学での純粋数学分野が直接社会に役立たないという理由で予算が削られていくという話をよの計算は，すべてhttps://ja.wolframalpha.com/にアクセスして行った。

く聞く。よく考えてみていただきたい。この RSA
暗号の仕組みは，フェルマーの小定理という名前か

たとえば，不定方程式 11−9628=1 を解くのらもわかるようにフェルマーが生きた時代 (1600 年

も，ページの入力フォームに式 11−9628=1 と代前半) の純粋数学分野が，1980 年に応用され暗号入力して，Shift+Enter キーを押すだけである。

システムとして開発された。つまり，直接社会に役Mathematica で計算するときは Shift キーを忘れ立たなさそうにみえる素数の性質などが約 400 年経てはいけないことに注意する。また，8752 を 6127ってネットワーク時代に応用され欠かせないものと乗して 9853 で割った余りを計算するときは，入力なったというのである。つまり，いまは直接役に立フォームに Mod [8752，9853] と入力して Shiftたないかもしれないがいつどこでそれが応用される+Enter キーを押すだけで，瞬時に 831 と計算してかわからないという可能性も残しているのである。

の計算結果も興味があるの目先のことばかり考えるのではなく，基礎研究も大であれば，入力フォームに 8752ˆ6127 と入力して事であるということを RSA 暗号の仕組みを解説す

Shift+Enter キーを押す。すると，巨大な数字のるときは生徒に説いている。実は私が RSA 暗号の計算結果が現れる。自然数 5673215567942 の素因数授業を行うに当たってこのことが一番いいたかった分解の結果を求めたければ，FactorIntegerことである。

くれる。単純に 8752

19