フェルマーの小定理を使ったRSA暗号の数学的な説明

本記事の内容

本記事はRSA暗号をフェルマーの小定理を使って数学的に解説しようという記事です。

本記事を読むに当たり、フェルマーの小定理について知っている必要があるため、以下の記事も合わせてご覧ください。

フェルマーの小定理の証明

...

for-spring.com

2023.07.09

ざっくりRSA暗号

数学的な話まず置いておいて、RSA暗号の外観をざっくりと述べます。

暗号？

“暗号”というと「秘密の文章を分かる人にだけ伝える」というようなニュアンスがあると思います。
数学における暗号もおおよそ同じような意味です。

暗号の起源は意外と古く、その歴史は古代ローマ時代にまで遡ります。
もちろん当時は国家機密を扱ったりと、ごく一部の人たちに対するだけのものでした。
情報社会の現在、暗号は我々の日常には欠かせないものとなっています。

少々ネタバラシすると、例えばTwitterやLINEやらのSNSを使うとき、自身のアカウントにログインしますが、平たくいえば、その時点でも実は数学が使われています。

(読み飛ばしてOK)

「数学って何の役に立つの？四則演算ができればそれでいいんじゃないの？」という質問を投げかける方がいます。
もちろん、それは大事な発想だと思います。
しかし、数学を少しかじった方ならおわかりだと思いますが、数学は至るところで活躍しています。
個人的に、先のような質問が出現するのは「数学はあまりにも世の中に役立ち過ぎているがゆえに、身近すぎるがゆえに、案外恩恵がわからないものなのかな」と思っています。
要するに「灯台下暗し」というやつです。

暗号のイメージ

まずはイメージから。

次のような法則を考えます。

要するに、アルファベットを一つずらすという法則です。
この法則を書いた紙と「$gdkkn$」と書かれた紙を読者のあなたに手渡ししました。
つまり、この法則とメッセージは筆者と読者のあなたのみが知っているということです。。
他の方が見れば「gdkkn？なんだそれ？」となるところを、あなたは先の法則を使って「ああ、$hello$ね」と分かるわけです。
この場合、メッセージを読み取るための「鍵」が法則が書かれた紙ということになります。
(※この方法は共通鍵暗号方式といいます。)

通常の暗号は、先の例のように同じ「鍵」を使って暗号化と復号化(元の文章に戻すこと)を行い、情報の送り手と受け手の間で安全な方法(極端に言えば手渡し)で事前に鍵を共有しておきます。
しかしながら、ネット通販などで顧客がネットショップ側に個人情報やクレジットカード番号やらを送るには、事前に鍵を安全な方法で共有することができません。

公開鍵暗号とその仕組み

先の問題を解決するために開発された方法が「公開鍵暗号」です。
この方法は、暗号化する「公開鍵」と復号する「秘密鍵」の２種類の鍵を用意して、暗号化のための公開鍵のみを知っていたとしても、暗号化された情報を復号できないようにしています。

では、どのように情報を送受信しているのか、ということを見てみましょう。

用意するものは「公開鍵」と「秘密鍵」の2つの鍵です。
公開鍵は誰でもかんたんに入手できるような、文字通り公開された鍵ですが、秘密鍵は1しかない大事な大事な鍵です。

流れはシンプルです。

1. 受信者が公開鍵を作る。
2. 送信者は受信者の公開鍵を取得する。
3. 暗号化したいメッセージを送信者が公開鍵を使って暗号化し、送信する。
4. 受信者が暗号化されたメッセージを受け取る。
5. 受信者は暗号文を秘密鍵で暗号化する前のメッセージに復号化する。

このように、受信者(秘密鍵を持っている人)のみが暗号を解くことができるという仕組みになっています。
秘密鍵は受信者が大切に保管して、公開鍵は誰でも手に入れら場所に公開されています。

これにより、ネットショップは公開鍵を「公開」し、顧客はそれを用いて個人情報を暗号化して送ることにすると、第三者に勝手に見られたり、盗まれる危険がありません。

RSA暗号の開発によって、このような公開鍵暗号が一般的に使われるようになりました。

RSA暗号の原理

上記のことを数学で表現すると次のようになります。

1. 受信者が公開鍵を作る。
1. 十分大きな2つの素数$p,q\ (p\neq q)$を選び、$n=pq$として、$n$から$p$と$q$を計算することが実用上必要な時間にできない(例えば数百年とか)ようにする。
2. $e$と$\varphi(n)$が互いに素であるような$2$以上の整数$e$を求める。 ただし、
   $\varphi(n)=|\{i\in\mathbb{Z}|1\leq i\leq n, i$と$n$は互いに素$\}|$
   とします。
この決めた$e,n$を公開鍵と呼びます。
2. 送信者は受信者の公開鍵を取得する。
3. 暗号化したいメッセージを送信者が公開鍵を使って暗号化し、送信する。
$n$よりも小さい正の整数$A$を送るとします。
$A^\prime\equiv A^e\ ({\rm mod}\ n)$となる$A^\prime$を計算します($A^e$を$n$で割った余りが$A^\prime$)。
この$A^\prime$を暗号として受信者に送信します。
4. 受信者が暗号化されたメッセージを受け取る。
5. 受信者は暗号文を秘密鍵で暗号化する前のメッセージに復号化する。
$ed\equiv1\ ({\rm mod}\ \varphi(n))$を満たす正の整数$d$を求めます。
この$d$が暗号を復号化するための鍵、すなわち秘密鍵です。
すると、$A\equiv\left( A^\prime\right)^d\ ({\rm mod}\ n)$が成り立つため、$A$が分かる、ということです。

共通鍵暗号とその問題点

では、少し数学に踏み込んだ暗号の話をしましょう。

原始的な暗号

現代では様々な情報を通信します。
その場合、AmazonやらTwitterやら何やらと個人情報や保安上重要な情報は通信の当事者(送受信者)以外には理解できないように情報を伝える必要があります。

そのような情報伝達の方法を暗号といいます。

X	Y	X	Y	X	Y	X	Y	X	Y
あ	ろ	い	ね	う	の	え	ふ	お	す
か	う	き	む	く	り	け	れ	こ	ら
さ	き	し	る	す	に	せ	か	そ	や
た	ん	ち	わ	つ	こ	て	そ	と	よ
な	い	に	あ	ぬ	も	ね	お	の	は
は	え	ひ	さ	ふ	て	へ	ま	ほ	く
ま	ゆ	み	け	む	め	め	ひ	も	し
や	み			ゆ	せ			よ	ぬ
ら	を	り	た	る	な	れ	ほ	ろ	へ
わ	ち							を	と
ん	つ

この表は、「あいうえお$\cdots$」を並び替えた表です。
とりあえず濁点やら「っゃゅょ」は無視することにします。
なにか文があれば、それを平仮名で書き直し、上の表の規則に従ってX欄の文字をYの文字に置き換えれば、一見意味の分からない文になります。

例えば、

という文を、上記の表の規則によって変換してみれば、

となります。
このように意味が通らない文になります。

最初の「ひるはあめのあとはれます」を平文(ひらぶん)、変換後の「さなえろひはろよえほゆに」を暗号文と呼びます。

暗号文が与えられたらば、上記の表に従って平文に直す事もできます。
このように平文から暗号文を作ることを「暗号化」、暗号文から平文を作ることを平文の「復元(または復号化)」といいます。

ちなみに、送受信者以外の第三者が暗号を破って不正に情報を得ることを「解読」といいます。

共通鍵暗号

先の暗号の規則を使って、AさんとBさんが、他の人には分からないように、何かの情報をやり取りするとしましょう。

AさんがBさんに情報を伝えるとしたら、もちろん暗号文を送ることになるわけですが、Bさんがその暗号文を平文に復元するためには、Aさんと同じ上記の規則表を持っていなければなりません。

暗号を作ったり、平文に復元したりするための情報を「鍵」と呼びますが、この場合は暗号を送り人と受け取る人が共通の鍵を共有していなければならないわけです。

このような、送受信者で同じ鍵を持ち、その鍵で暗号化及び復号化をする暗号のことを「公開鍵暗号」といいます。

公開鍵暗号の弱点(問題点)

原始的(古典的とも言えるかな？)な暗号はシンプルな発想ですが、規則表を持っていないことには暗号文を復元できないわけですので、高い安全性を持っているような気がします。

実際、先の例で言えば、規則表のパターン数は$50!-1$個ですから、
$$\begin{eqnarray} &&30414093201713378043612608166064768844377641568960512000000000000-1\\ &=&30414093201713378043612608166064768844377641568960511999999999999 \end{eqnarray}$$
パターンあります。

しかしながら、実はこの公開鍵暗号には安全上、2つの問題が存在します。

$50!-1$を日本の数の単位で…

3不可思議414那由多932阿僧祇171那由多3378極436載1260正8166澗647溝6884穰4377杼6415垓6896京511兆9999億9999万9999

問題その１「共通鍵を知らなくても解読されやすい」

共通鍵を知らなくても解読されやすいということです。
「え？さっきエラい大きいパターン数があるって言ったじゃないか」と思うかもしれません。
確かにそうなのですが、暗号を解読するにあたって表の全てを解読する必要がないので、「暗号を解読する」という目的に対してはさほど気にすることではないのです。

もう少し詳しく言えば、「さなえろひはろよえほゆに」くらいの文を1解送るだけであれば問題は無いのですが、送る情報量が増えると問題が生じます。
それは「あいうえお」が普通の文章の中で現れる頻度が違うからです。

先の文でも「え、ろ」が2解現れて他の文字は1回だけです。
ちなみに、英語の文章は「e」という文字が一番多く現れることはよく知られています。
故に、少し長い文章をこの方法で送れば、第三者がそれを傍受した場合、多く現れる文字は何であるかをいくつか調べて、それを一般的に多く現れる文字で置き換えるということができます。
そして、少しでも意味のある部分ができたら、それを手がかりにして、もっと調べる、というように芋づる式に暗号が破られてしまいます。

問題その２「共通鍵を送らなければならないこと」

もう一つは、「共通鍵を共有すしなければならないこと」です。
例えば、国家機密をやり取りするため、共通鍵を1つの国からもう一方の国に運ぶというよなことになれば、その共通鍵を運ぶ仮定でそれを盗もうとする人も現れてくるかもしれません。

この手の情報を送るのは非常に危険なのです。

公開鍵暗号

共通鍵暗号には以下の2つの問題がありました。

• 問題その１　「共通鍵を知らなくても解読されやすい」
• 問題その２　「共通鍵を送らなければならないこと」

これらの問題のうち、その１に対しては、暗号の強度が強ければ問題は無いわけですが、共通鍵暗号の場合、交通鍵の傍受という問題が常にあります。

そこで登場したのが、公開鍵を使った暗号です。
この、公開鍵を使った暗号方式を公開鍵暗号といいます。

共通鍵暗号はダメ？

共通鍵暗号は現在でも使われています。
共通鍵暗号の方が公開鍵暗号よりも通信速度が早いので、共通鍵暗号でも、暗号自体の強度が高ければ、共通鍵を一旦公開鍵暗号で伝えて、それから共通鍵暗号を使うということは、実は一般的です。

ちょっとだけ歴史

1976年にディフィー(Diffie)さんとヘルマン(Hellman)さんは、第三者が傍受する可能性のある通信経路を想定して鍵を共有するDH鍵共有という考え方を初めて提唱しました。

DH鍵共有は、暗号そのものではないのですが、1977年には、リヴェスト(Rivest)さん、シャミル(Shamir)さん、エイルドマン(Adelman)さんによって現在広く使われている公開鍵暗号の一つであるRSA暗号が考案されました。

RSA暗号の歴史

公開鍵暗号

公開鍵暗号とは、平文を暗号化するのと、暗号文から平文に復元するのに、別々の鍵を使う方式です。

大事な点としては、

• 大事な点①：暗号化に必要な公開鍵は誰が見ても良い
• 大事な点②：暗号を復元するのには、余分な情報(秘密鍵)が必要になる

です。

故に、受信者が送信者から情報をもらいたいと言うときには、まず、受信者が送信者に公開鍵を伝えます。
そして、送信者が公開鍵を使って暗号文を作り、受信者に伝えます。
受信者は自分だけが持っている秘密鍵を使って暗号を復元し、それによって送信者からの情報を得ます。
ここで、受信者は秘密鍵を誰にも伝える必要がないので、暗号の安全性が高まるのです。

さて、公開鍵は誰が見ても良いわけですから、公開鍵から秘密鍵が分かってしまうと暗号になりません。
このように平文Xから暗号文Yを作るとき、YからXへ戻すことが、余分な情報を持っていないと非常に難しい仮定を不可逆過程といいます。

RSA暗号とフェルマーの小定理 (※ここから数学が入ってきます)

RSA暗号は、公開鍵暗号の一種で、大きい整数の素因数分解の困難さによりセキュリティを担保する暗号です。

数学を使って暗号化するので、平仮名に適当に番号をつけ、文字を整数に変換します。
例えば、次のように規則を決めたとしましょう。

あ	1	い	2	う	3	え	4	お	5
か	6	き	7	く	8	け	9	こ	10
さ	11	し	12	す	13	せ	14	そ	15
た	16	ち	17	つ	18	て	19	と	20
				っ	23
な	26	に	27	ぬ	28	ね	29	の	30
は	31	ひ	32	ふ	33	へ	34	ほ	35
ま	36	み	37	む	38	め	39	も	40
や	41			ゆ	43			よ	45
ゃ	46			ゅ	48			ょ	50
ら	51	り	52	る	53	れ	54	ろ	55
わ	56	を	57	ん	58	゛	59	゜	60
。	61	、	62	空白	63

この表により、文章は整数の列になります。
例えば、共通鍵暗号でも扱った例「ひるはあめのあとはれます。」という文であれば、
$$32,\ 53,\ 31,\ 01(=1),\ 39,\ 30,\ 01,\ 20,\ 31,\ 54,\ 36,\ 13,\ 61$$
となります。

ここで、これらの2桁ずつの数字をそれぞれのままで暗号化したとしても、結局出力は高々100個程度しかありません。
これは、結局のところ並べ替えの暗号と同じことになってしまいます。
したがって、これらの数字を「そのまんま使う」ということはしません。

そこで、数字の区切り方を変えてみます。
今、2桁ずつで区切るという方法ですが、それを3桁ずつに直してみます(※実際は600桁くらいに分け直して使うのですが、ここでは原理を説明するだけですので3桁にします)。
すると、
$$325,\ 331,\ 013(=13),\ 930,\ 012,\ 031,\ 543,\ 613,\ 610$$
となります。
ただし、最後は半端に2桁になってしまったので、$0$を追加しています。

RSA暗号の暗号化・復元

RSA暗号では、先の
$$325,\ 331,\ 013(=13),\ 930,\ 012,\ 031,\ 543,\ 613,\ 610$$
という暗号を次のように暗号化及び復元します。

暗号化・復元の為に用意するもの

2つの素数$p,q$、例えば$p=23$、$q=47$を選び、
$$n=pq$$
で定めます。
ここでは、$n=pq=23\times47=1081$です。

実際には

実際には、300桁くらいの非常に大きい素数を2つ扱います。

$n$で割った余りを使うので、ここでは3桁の数を暗号化するために、$n$は4桁以上の数でなければなりません。

$(p-1)(q-1)$(ここでは$(23-1)(47-1)=22\cdot46$)と互いに素な整数、例えば$e=3$を選びます。

実は、これで暗号化するために必要な情報は全てで揃っているのです。
ここで、$n$と$e$が公開鍵で、$23$と$47$が秘密鍵です。

これをまとめれば

今回の場合、$1081$という整数が与えられると、$1081=23\times47$と容易に素因数分解できてしまいます(実際に手計算でできなくとも計算機を使えば一瞬)。
しかしながら、$n$が2つの300桁くらいの素数の積の場合、現在分かっている方法では、その2つの素数を見つけるのに天文学的な時間が必要なので、2つの素数$p$及び$q$が秘密鍵の役割を果たせるわけです。

これが、この節の冒頭に述べた「大きい整数の素因数分解が困難であることがセキュリティを担保している」ことの意味です。

故に、将来的に非常に大きい整数を素数の積で表す方法が見つかってしまうと、RSA暗号は使えなくなってしまいます。

これらの情報を使って、次のように暗号化及び復元を行います。

暗号化

公開鍵と秘密鍵に必要な情報として、2つの素数$p$及び$q$、$n=pq$、$(p-1)(q-1)$と互いに素な素数$e$がありました。
これらをどう使って暗号化するのか、という話をします。

暗号化自体は一瞬です。

復元の準備

$L={\rm lcm}(p-1,q-1)$とします。
$e$は$(p-1)(q-1)$と互いに素なので、$L$とも互いに素です。

ここで、次の事実を使います。

定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その6を御覧ください。

定理1.から、
$$(\exists d,k\in\mathbb{Z})\ {\rm s.t.}\ de-kL=1\tag{1}$$
です。

この$d$はユークリッドの互除法から求める事ができます(後で実際にやってみる)。

定理2.の証明は【代数学の基礎シリーズ】初等整数論編 その4を御覧ください。

等式(1)は
$$de-kL=1\Longleftrightarrow(d+L)e-(k+e)L=1$$
と変形できるわけですから、$d,k>0$としてOKです。

先の$p=23$、$q=47$、$e=3$とした場合、実際に$d$を求めてみます。
$$L={\rm lcm}(p-1,q-1)={\rm lcm}(22,46)=506$$
ですから、ユークリッドの互除法を使うことで
$$\begin{eqnarray} 506&=&3\times 168+2,\\ 3&=&2\times1+1 \end{eqnarray}$$
であるから、
$$1=3-2=3-\left( 506-3\times168\right)=3\times169-506$$
となります。
したがって、$d=169$となります。

復元

今の状況を確認しておくと、受信者が作成した公開鍵$n$及び$e$を使って送信者は$f(x)$という暗号を受信者に送っている、という状況です。

そして、受信者が$f(x)$という暗号を受信している、という状態です。
では、この暗号$f(x)$をどう復元するのか、という話をします。

定理3.の証明

$de-kL=1$から、$de=1+kL$です。
故に、
$$x^{de}=x^{1+kL}=x\cdot x^{kL}$$
です。

ここでフェルマーの小定理を使います。

フェルマーの小定理の証明は【代数学の基礎シリーズ】初等整数論編 その24をご覧ください。

秘密鍵の1つである$p$を法として考えると、$p\not\mid x$であればフェルマーの小定理から、
$$x^{p-1}\equiv 1\ ({\rm mod}\ p)$$
です。
$L={\rm lcm}(p-1,q-1)$ですから$p-1\mid L$であるので、
$$x^{kL}\equiv1\ ({\rm mod}\ p)$$
です。
したがって、
$$x^{de}\equiv x\ ({\rm mod}\ p)$$
です。

$p\mid x$であれば、$x^{de}\equiv x\ ({\rm mod}\ p)$です。

したがって、全ての$x$に対して$x^{de}\equiv x\ ({\rm mod}\ p)$です。

一方で、$q-1\mid L$でもあるから、
$$x^{de}\equiv x\ ({\rm mod}\ q)$$
も成り立ちます。

$\gcd(p,q)=1$であるから、
$$f(x)^d\equiv x^{de}\equiv x\ ({\rm mod}\ n)$$
ということがわかります。

定理3.の証明終わり

確認しておくと、

• $x$を暗号化したもの：$f(x)$
• 定理3.で導いたもの：$x$

となっているわけですから、まさに復元できています。

実際にやってみる

暗号化

今の状況では、平文は複数の3桁の数からできています。
その各々に対して$x^e=x^3$を$n=pq=1081$で割った余りが暗号化された文$f(x)$です。

定理3.から、$f(x)^d=f(x)^{169}$を$n=1081$で割った余りを考えれば$x$に戻ります(復元)。
ここで、$e$から$d$を求めるためには、$p-1$と$q-1$が分かる必要があったわけですので、$p$と$q$を求めることが非常に難しければ、$p$及び$q$は秘密鍵とみなせるわけです。

では、
$$325,\ 331,\ 013(=13),\ 930,\ 012,\ 031,\ 543,\ 613,\ 610\tag{2}$$
という平文について考えてみます。

(2)を暗号化すると次になります。
$$970,\ 384,\ 35,\ 34,\ 647,\ 604,\ 421,\ 431,\ 187\tag{3}$$
これらの数から平文を復元するためには、例えば
$$y\equiv970^{169}\ ({\rm mod}\ 1081)$$
という合同方程式を解かねばなりません。

とても手計算でできるような代物ではありませんので計算付ソフトウェア等を使うことになります。
エクセルでもできます。

復元

(3)を復元するのもよいのですが、もう平文が分かっている状態ですので、別の暗号化されたものを復元してみます。

$$250,\ 384,\ 922,\ 476$$

結局$y\equiv 250^{169}\ ({\rm mod}\ 1081)$などを計算する必要がありますが、エクセルなどで計算すると、

• $y\equiv 250^{169}\ ({\rm mod}\ 1081)$のとき、$y\equiv 11\ ({\rm mod}\ 1081)$
• $y\equiv 384^{169}\ ({\rm mod}\ 1081)$のとき、$y\equiv 331\ ({\rm mod}\ 1081)$
• $y\equiv 922^{169}\ ({\rm mod}\ 1081)$のとき、$y\equiv 315\ ({\rm mod}\ 1081)$
• $y\equiv 476^{169}\ ({\rm mod}\ 1081)$のとき、$y\equiv 400\ ({\rm mod}\ 1081)$

となります。
結果を列挙すれば、
$$011,\ 331,\ 315,\ 400$$
となります。
これを2桁ずつに分け直せば
$$01,\ 13,\ 31,\ 31,\ 54$$
となります。

では、最後に整数と平仮名の対応表を確認しましょう。

あ	1	い	2	う	3	え	4	お	5
か	6	き	7	く	8	け	9	こ	10
さ	11	し	12	す	13	せ	14	そ	15
た	16	ち	17	つ	18	て	19	と	20
				っ	23
な	26	に	27	ぬ	28	ね	29	の	30
は	31	ひ	32	ふ	33	へ	34	ほ	35
ま	36	み	37	む	38	め	39	も	40
や	41			ゆ	43			よ	45
ゃ	46			ゅ	48			ょ	50
ら	51	り	52	る	53	れ	54	ろ	55
わ	56	を	57	ん	58	゛	59	゜	60
。	61	、	62	空白	63

すると、答えは「あすははれ」となります。

皆様のコメントをください！

夏は夏で電気代がかかります。
大学や会社に行けば、特に電気代はかからないのですが、家で作業していたりすると電気代がかさみますよね。

何か、電気代を節約し、かつ部屋を涼しくする方法は無いものか…と思っています。
ご存知であればぜひ教えてください…

結

今回は、フェルマーの小定理を使ったRSA暗号を数学的に説明しました。

フェルマーの小定理は暗号化、復号化に直接的に役に立っているというより、復元をする際の根幹の理論に使われています。

ただ、フェルマーの小定理のおかげで現在我々は安心して(?)個人情報を暗号化して、Amazonやら何やらを利用できているのです。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！

初等整数論について、以下の書籍をオススメします！