最近セキュリティについて少し関心があり、公開鍵暗号方式を勉強しています。
公開鍵暗号方式を勉強する中でRSA暗号というものが出てきたので、自分の理解を深めるために実際にRSA暗号について具体的な計算をしながら理解していきます。
記載内容に誤りがある場合は恐れいりますがご指摘お願いします。
公開鍵方式概要
先ほども少し記載しましたが、RSA暗号とは公開鍵暗号方式で用いられる暗号のアルゴリズムの一つです。RSA暗号について説明する前に公開鍵暗号方式の概要について説明いたします。
公開鍵暗号方式については下記サイトをもとに私が理解した内容を書きます。
何個かサイトを参照したのですが、サイトによって表現のバラつき？があるように感じたため、もしかしたら内容に誤りがあるかもしれません。内容に誤りがある場合はご指摘お願いいたします。
まず初めにメッセージを送受信する人は秘密鍵と呼ばれる他の人には公開してはいけない鍵と、公開鍵と呼ばれる他の人に公開してもいい鍵を生成します。
ここで公開鍵で暗号化したものは暗号鍵でしか復号をすることが出来ないという特徴があります。
そして、鍵ペアを生成したら公開鍵をメッセージの送信者に共有します。
そして暗号化された文章を受信したメッセージ受信者は暗号鍵をつかって暗号文を復号します。(よく復号"化"と書かれている文章がありますが、厳密にいうと誤りです。復号化とはより)
次に悪意のある第三者が暗号文と公開鍵を盗んでしまった場合の事を考えてみます。
最初に記載しましたが、公開鍵は公開している鍵なので誰でも入手することが出来ます。
また、通信経路が盗聴されていれば暗号文を手に入れることも出来ます。
それぞれの人が持ってる鍵とできることをまとめたものが下記の図です。
RSA暗号について
前置きが長くなってしまいましたが、ここから本題のRSA暗号について書いていきます。
公開鍵方式について説明した際に公開鍵と秘密鍵という言葉が出てきましたが、この二つの鍵を生成し、暗号化/復号するためのアルゴリズムとなります。
具体的に言うと次の式を満たすe,d,nの生成します。(Wikipediaより)
暗号化:\begin{equation}c = m^e \mod n \end{equation}
復号：\begin{equation}m = c^d \mod n \end{equation}
ここで、mは暗号化したい平文、cは暗号化した暗号文、dを暗号鍵、e、nを公開鍵とします。
この式照明について興味がある方は下記サイトを参照してみてください。
実際に秘密鍵、公開鍵を作る手順
ここから先ではこれらのパラメータをどのようにして求めるかを記載していきます。(CTF 入門RSA暗号をベースに記述しています。)
- 任意の2つの素数p,qを選ぶ
- $n = pq$ とする
- $\phi(n) = (p-1)(q-1)$を求める
- $\phi(n)$と互いに素な値をe設定する。
- $d = e^{-1} mod \: \phi(n)$を求める
補足になりますが、鍵ペアを生成する際に注意しなければいけないことが何個かあるみたいです。近い値のpとqを使用してはいけない、eを大きくしすぎてはいけないなど。興味がある方は下記サイトを参照してみてください。
任意の2つの素数p,qを選ぶ
ここからは簡単な例で実際に暗号と復号の流れを確認していきます。
本来はp、qの値は大きくないといけないのですが、今回はp=5、q=11として計算していきたいと思います。
n=pqとする
ここはあまり書くことが無いですが、今回p=5、q=11を選択しているため、$n = pq = 55$となり、これが公開鍵の一つとなります。
$\phi(n) = (p-1)(q-1)$を求める
次に$\phi(n)$を求めるのですが、実際に値を求める前に簡単に$\phi(n)$について説明します。
$\phi(n)$はオイラーの$\phi$関数と呼ばれるもので1~nまでの整数でnと互いに素なものの数のことを言います。詳しく知りたい方は下記サイトを参照してください。
ここでなぜ(p-1)(q-1)を計算することでnと互いに素なものの数を求められるか自分なりの理解を書いていきます。先ほど計算の例ではp=5、q=11としましたが説明の都合上、ここではp = 3、q = 5として考えていきます。
このような計算ができる理由としてはpとqが互いに異なる素数なので、p,qの倍数が重ならないからです。
前置きが長くなりましたがここで本題に戻ってp = 5、q = 11の場合のファイ関数を求めると$\phi(55) = (5-1)(11-1) = 40$となります。
$\phi(n)$と互いに素な値をe設定する。
次にeの値を決めていきます。
通常は65537という値が一般的とのことですが、今回は手計算を実施するためe=7として計算します。ここで設定したeも公開鍵の一つとなります。
65537が一般的な理由については下記サイトを参照お願いします。
簡単に言うとコンピューターで計算するうえで都合がいい数字だからです。
$d = e^{-1} \mod \phi(n)$を求める
最後に秘密鍵dを求めていきます。
ここがmod初学者の私にとって理解するのが難しかったです。。。
参考にした文献では$d = e^{-1} \mod \phi(n)$を求めると書いてましたが、eの逆数のmodを求めるという事が理解が難しかったです。。。
ただ、合同式は両辺を掛け算可能なので、両辺にeをかけることで理解ができるようになりました。
$ed \equiv 1 \mod \phi(n)$を満たすdを求めていきます。具体的な数値を入れると
$7 d \equiv 1 \mod 40$となるので、7dを40で割って余りが1となるようなdを求めていきます。
7dを40で割って1余る数という事は下記のように置き換えることが出来ます。
\begin{equation}7d = 40x + 1 \end{equation}
※xは任意の整数
この形は一次不定方程式となり、ユークリッドの互除法を使うことで解を求めることをできます。導入の詳細は補足に書きますが、d = 23という値を導きました。
実際に暗号化、復号をする
これで暗号化に必要な公開鍵、秘密鍵を生成することが出来ました。
今回生成した公開鍵、秘密鍵は以下の通りです。
この値と(1)式を使って20という数字を暗号化していきます。(20という数字には意味はありませんが、n=55未満の数字を選定しています。)
(1)式に値を入れて計算したところ15という値が出てきました。
次にこの15という数字を(2)式を使って復号します。
元の数字の20という数字を取り出すことが出来ました。
まとめ
今回はRSA暗号について具体的な計算をしながら内容の理解をしました。今回はあくまで勉強のために簡単な秘密鍵を使いましたが、次回はpythonのライブラリを使って実践的なRSA暗号の動作を確認していきたいと思います。
↓次回記事
(補足)ユークリッドの互除法による秘密鍵dの導出
ユークリット互除法は高校生時代にやった気がするのですが、やり方を忘れてしまったので下記動画を見て復習しました。私と同じように忘れている方は下記動画を参照お願いします。。。
式(3)を変形すると下記のようになります。
\begin{equation}7d -40x = 1 \end{equation}
これをユークリッドの互除法を使うと下記のようになります。(表現が難しかったので、画像で書きました。。。)
余りが1になるまで実施したら余り＝という形に式を変形していきます。
\begin{equation}5 = 40 - 7 * 5 \end{equation}
\begin{equation}2 = 7 - 5 * 1 \end{equation}
\begin{equation}1 = 5 - 2 * 2 \end{equation}
(7)式に(6)式を代入すると以下のようになります。
\begin{equation}1 = 5 - 2 * (7-5*1) \nonumber \end{equation}
これを整理すると以下のようになります。
\begin{equation}1 = 3*5 -7*2 \end{equation}
次に(8)式に(5)式を代入します。
\begin{equation}1 = 3*(40-7*5) -7*2\nonumber \end{equation}
これを整理すると以下のようになります。
\begin{equation}1 = 3*40 -17*7 \end{equation}
(4)式と同じ形になるように(9)式を整理すると
\begin{equation}7*(-17)-40(-3) = 1 \end{equation}
となるため、(4)式と比較するとd=-17,x = -3という解の組み合わせを求めることが出来ました。
これでもいいかもしれないですが、dが負の値なのでこの方程式の一般解を求めていきます。(4)式から(10)式を引きます。すると以下のようになります。
\begin{equation}0 = 40(3+x) - 7(17+d) \nonumber \end{equation}
これを整理すると下記のようになります。
\begin{equation}7(17+d) = 40(3+x) \end{equation}
(11)式より7と49が互いに素なので17-dが40の倍数であるという事が分かります。
これを正の整数kを使って以下のように表すことが出来ます。
\begin{equation}17+d = 40k \nonumber \end{equation}
整理して下記一般解を得ることが出来ます。
\begin{equation}d = 40k -17 \end{equation}
導出が長くなりましたが、今回はk=1として、d=23としました。
また、今回の秘密鍵の導出とは関係ないですが、xの一般解についても求めていきます。
(11)式に(12)式を代入します。
\begin{equation}7*40k = 40(3+x) \nonumber \end{equation}
整理してxの一般解を求めることが出来ました。
\begin{equation}x = 7k-3 \nonumber \end{equation}
(補足)復号ができる仕組み
ここでは(1)式で暗号化したものが(2)式で復号できる理由を確認していきます。
（2)式に(1)式を代入して、下記式が成立するかを確認していきます。
\begin{equation}m = m^{ed} \mod n \end{equation}
ここでedは $ed \equiv 1 \mod \phi (n)$を満たすように設定したので、
$ed = \phi (n) k +1$ を満たすような正の整数kが存在することが分かる。
(d=e−1modϕ(n)を求めるを参照)
この式を(13)式に代入すると以下のようになる。
\begin{equation}m = m^{\phi(n)k+1} \mod n \nonumber \end{equation}
この式を少し整理すると下記のようになります。
\begin{equation}m = m \times (m^{\phi(n)})^k \mod n \end{equation}
ここで$m^{\phi(n)} \mod n$はオイラーの定理より
\begin{equation}m^{\phi(n)} \equiv 1 \mod n\end{equation}となります。
(14)式に(15)式を代入すると
\begin{equation} m \times (1)^k \mod n \end{equation}
となるため、mという値が復元できるという事が分かります。
(補足)RSA暗号の安全性について
ここでは自分が悪意のある第三者である場合に暗号化された文章を復号する場合について考えてみたいと思います。(ここの内容は自分なりの理解を書いているだけなので誤りがある可能性があります。もし、間違っている個所があればご指摘お願いします。)
(2)式より暗号文と秘密鍵dとnが分かれば暗号文を復号化することが出来ます。
nは公開鍵情報で入手できる情報であるため、当たり前のことではありますが秘密鍵dを求めれば暗号文を復号できることになります。
ここでは公開されている情報(e,n)が分かっている状況で秘密鍵dをどのようにして求めるかを考えていきます。
dを求めるためには下記の通りで、$\phi (n)$を求めることが必要です。
$\phi (n)$を求めるためには鍵生成する際に用いた素数のペアp,qを求める必要があります。
ここで$n=pq$なのでnの素因数分解を実施すれば秘密鍵dを求めることが出来そうです。
今回の例ではn = 55なので簡単に素因数分解が出来てしまって秘密鍵がばれてしまいます。
ここでｎの値を大きくしてn = 7860788454055865772880591325788540720239307336070977793860987994621983778070919566058194646641091024091611308310809994833637298391885151018077907450682171
としてみたいと思います。これの素因数分解をするのは人の手では無理ですね。
このように大きなnに対してはパソコンを使っても素因数分解をするのが難しいです。
このように素数のペアを作ってdを作るのは簡単だが、dから素数のペアを求めるのが難しいという事を利用して利便性と安全性を担保しています。
分かりにくくなってしまうかもしれませんが、味噌と出汁を入れるとおいしい味噌汁が出来が、味噌汁から味噌と出汁を取り出すのは難しいというようなイメージですかね？
(このように片方は簡単だが、もう片方が難しいというものを「落とし戸付き一方向性関数
」ともいうみたいです。)
.png)
0 件のコメント:
コメントを投稿