namdicul's blog

気ままに更新します. CTFについて勉強中です.

RSA暗号 ~まとめ~

お久しぶりです.

最近CTFの勉強をしていて, RSA暗号に触れる機会があったのでまとめておこうと思います. 出来るだけほかの人にもわかりやすく書いていこうと思います. 
昨年授業でRSA暗号については一通り習ったのですが, やはり1年も経つと忘れてましたね...これを機にもう一度覚えなおしていきたいと思います.

この記事を作るにあたって, 以下のサイトには大変お世話になりました. 本当にありがとうございました.
mathtrain.jp

tsujimotter.hatenablog.com

RSA暗号とは

RSA暗号とは, 公開鍵暗号方式を利用した暗号方法です. 暗号方式には共通鍵暗号方式と公開鍵暗号方式というものが存在します. RSA暗号ではそのうち公開鍵暗号方式を利用しているんですね.
RSA暗号を理解するには, 高校数学で1通り学ぶ初等整数論を理解している必要があります. 合同式を利用するので, 合同式を用いた計算は1通りできておいたほうが良いと思います. またフェルマーの小定理というものを途中で使用するのですが, これは大学の数学で学ぶことなので, 紹介はしますが証明まではしません. 詳しい証明が知りたい人は個人で調べてもらえるとありがたいです.

そもそも暗号化とは?

これは説明するまでもないと思いますが, 暗号化とはデータの内容を他人にはわからないようにするための方法です. 例えば, オンラインショッピングをするとき, クレジットカードのカード番号がそのままネットワーク上に流れてしまったらどうなるでしょうか. 当然そのデータが盗聴されてしまったらカードが不正利用されてしまい, 大変なことになってしまいますよね. そのため, 見られたくないデータをネットワークを通してやり取りする場合は, 暗号鍵を利用して暗号化をしなければいけません.
また暗号化したら, 復号化出来なければいけません. 暗号化したまま復号化出来なければ, もとのデータは利用できなくなってしまい,本末転倒ですね. なので, 復号鍵を利用して暗号化データをもとのデータに直してやる必要があります. もし暗号鍵と復号鍵が同じである場合は「共通鍵暗号方式」, 違う場合は「公開鍵暗号方式」といいます. つまり, RSA暗号では暗号鍵と復号鍵は別のものであるということです.

f:id:tomonori4565:20180514222943j:plain
f:id:tomonori4565:20180514222910j:plain

RSA暗号の仕組み

平文(暗号化する前のデータ)をP, 暗号文をCとします. また2つの暗号鍵(公開鍵なので他人に知られても大丈夫)をk, mとします. ここで, 平文 Pから暗号文 Cを得る暗号化方法は以下の通りです.


P^{k} \equiv C (mod ~ ~ m) ~~~ ... (1)

つづいて, 暗号文 Cから平文 Pを得る復号化方式は以下の通りです. ここで,  uとは復号鍵のことを指します. 復号鍵は秘密鍵なので, 他人に知られてはいけません.


 C^{u} \equiv P (mod ~ ~ m) ~~~ ... ~(2)


ここで(1), (2)から


P^{ku} \equiv P (mod ~ ~ m) ~~~ ... ~(3)

となります. つまり, (3)を満たすような復号鍵 uが存在すれば復号化することができます.
このあとも説明しますが, 実はこのような復号鍵は存在するのです. しかし, この復号鍵を公開鍵 k, mから計算して導出することは現実に難しいです(理論的に不可能ではないのですが, 計算する時間が膨大になってしまいます). つまり, 暗号文を復号するのは復号鍵 uを知っている人にしかできないという仕組みになっているのです.

RSA暗号の仕組み(さらに詳しく)

RSA暗号の公開鍵は2つ存在しますが( k, mの2つ), そのうち mは非常に大きい素数 p, qを用いて,


 m = pq ~~~

となります. 先ほど復号鍵は秘密鍵なので知られてはいけないといいましたが, 実はこの p, qも他人に知られてはいけません. ここもポイントなのですが, こうすることによってRSA暗号の安全性と信頼性が担保されることになるのです(のちに詳しく説明します).


さてここから, なぜRSA暗号がうまく機能するのか説明していこうと思います.

復号鍵の一意存在性

ここでオイラーの定理 というものを使用します. オイラーの定理このサイトを利用して説明を省略しようと思います.

オイラーの定理を使用すると,  P, mは互いに素なので,


 P^{\varphi(m) \cdot v} \equiv 1 (mod ~ ~ m) ~~~ ... ~(4)

となります( vは整数).
(4)を少し変形します. 両辺に Pをかけると,


 P^{\varphi(m) \cdot v + 1} \equiv P (mod ~ ~ m) ~~~ ... ~(5)

となります. ここで(3)と指数部を比較してみましょう. すると,


 k \cdot u = \varphi(m) \cdot v + 1 ~~~ ... ~(6)

となります.
細かいですが, さらに変形して,


 k \cdot u -  \varphi(m) \cdot v = 1 ~~~ ... ~(7)

さて, ここまで色々な式変形をしてきましたが, ここで知りたいことはタイトルにもあるように「復号鍵が一意に存在するか」ということです. つまり(7)を満たすような整数 u, vが存在すればOKです.


ここで高校数学を思い出しましょう. 以下の定理, 覚えているでしょうか.

「一次不定方程式の整数解」

 a, bを互いに素な整数としたとき,  au + bv = 1を満たすような整数解 u, vが存在する.

これを(7)に適用してみましょう. いま k, \varphi(m)が互いに素であるならば, (7)を満たすような整数 u, vが存在します. 整数 kは何を選んでもよいので, 素数を選んでしまえばOKそうですね.
このことから復号鍵は一意に存在することが示せました.


(補足)少し複雑な説明は省略してしまいましたが,  u, vは複数の解をもちます. そのうち,  uが正となるものを選んであげてください.


他人が復号鍵を計算することの困難性

復号鍵が一意に存在することはわかりましたが, もし k, mから復号鍵が生成できてしまったらどうでしょう. 暗号化する意味がなくなってしまいますよね. ここでは, 復号鍵も持たない他人が復号鍵を生成することができるのかということを説明していきたいと思います.

もう一度(7)の式を見てみましょう.( k, mは既知なのでということを忘れないでください). もし \varphi(m)が計算できてしまったら復号鍵が生成できてしまいます. でも, すでに mは既知だから,  \varphi(m)は簡単に計算できてしまうんじゃないの?と思う方もいるかもしれません.



ここで少し前に説明したことを思い出してほしいのです.

RSA暗号の公開鍵は2つ存在しますが( k, mの2つ), そのうち mは非常に大きい素数 p, qを用いて,


 m = pq

となります.

そして,  \varphi(m)は以下のように計算することができます.


\varphi(m) = (p - 1)(q - 1) ~~~ ... ~(8)

もし仮に p, qの値を事前に知っていないのならば,  m素因数分解しなければなりません. しかし,  p, qは非常に大きな素数なので, 素因数分解するには膨大な時間がかかってしまうのです. なので先ほども言いましたが,  p, qは他人に知られてはいけないのです. ここがミソなんです.


すなわち, 暗号化したデータを復号化できるのは,

  • 復号鍵 uを保持している人(つまり p, qの値を知っている人)

に限られてくるのです.



このようにしてRSA暗号の安全性を担保することができるのです.


まとめ

分かりやすかったでしょうか. RSA暗号は美しい数学的性質をうまく利用した暗号化方式であることがわかりましたね.
しかし, 今後量子コンピュータなどが登場した場合,  mを簡単に素因数分解できてしまう可能性も否めません. 時代に即した暗号化方式を適用する必要がありますね.