RSA暗号を解いてみた

みなさんこんにちは！
スペースマーケットエンジニアのrayです。

家で使っているモニターがついにお亡くなりになりそうで、
点滅したり、突然紫っぽい画面になったりしています...

2020年10月購入なので、だいたい寿命は3〜4年のようです！
（ものによると思いますが...）

今回は、暗号解読の問題にチャレンジしてみました！

なぜやってみようと思ったのか

最近、サイバー攻撃系のニュースを見ることが多くなった気がするのですが、
私の職種はWebエンジニアですので、セキュリティ関連の知識が薄いなと思ったこと、
そしてインフラ系やバックエンドの勉強にもなると思い、少し覗いてみることにしました。

今回チャレンジした問題

カーネギーメロン大学が運営していて、セキュリティ系の問題が多く掲載されている
picoCTFというサイトの問題を解いてみます。（主に中高生向けのようです）

様々な分野があるようですが、今回は暗号分野の「Mind your Ps and Qs」というRSA暗号に関する問題を選択しました。

問題文

Description
In RSA, a small e value can be problematic, but what about N?

RSAにおいて、小さなeの値は問題を引き起こす可能性がありますが、Nはどうでしょうか？

Can you decrypt this?
Decrypt my super sick RSA:
c: 843044897663847841476319711639772861390329326681532977209935413827620909782846667
n: 1422450808944701344261903748621562998784243662042303391362692043823716783771691667
e: 65537

こちらを解読できますか？
私のとてもかっこいいRSAを解読してください

c:843044897663847841476319711639772861390329326681532977209935413827620909782846667
n:1422450808944701344261903748621562998784243662042303391362692043823716783771691667
e:65537

RSA暗号を解読する問題のようです。

RSA暗号について

RSA暗号は、公開鍵暗号方式の一種で、非常に広く使用されている暗号方式になります。電子メールの暗号化やデジタル署名、SSL/TLSによる通信の暗号化など、セキュアな通信やデータ保護に広く応用されています。

RSA暗号の作成・復号式は下記になります。

1: 2つの異なる素数pとqを選びます。
2: $n=p×q$を計算します。
3: $f=(p-1)×(q-1)$を計算します。
4: 素数eを選びます。
5: $d=e^{-1}(mod(f))$を計算します。

RSAを暗号化
6: $C=M^{e}mod(n)$で暗号Cを作成
RSAを復号化
7: $M=C^{d}mod(n)$で暗号Mを復号

※ modは、余りを表しております。（例：8 mod(3)は、8を3で割った余りなので、2になります。）

具体的な解法

RSAを復号するには、$M=C^{d}mod(n)$ という式を解いてあげれば良さそうです。
けれども、今回与えられた値は、cとnとeなので、dは分かりません。
dは、$e^{−1}(mod(f))$なので、fを求める必要がありそうです。
ですので、

1: fを求める
2: eとfで、dを求める
3: cとdとnで、M（答え）を求める

方法で進めて行きたいと思います。

1: fを求める

fは、$(p-1)×(q-1)$ですが、設問にはpとqの値はなく、cとnとeの情報しかないです。けれども、nは素数pとqをかけた値のようです。

n = 1422450808944701344261903748621562998784243662042303391362692043823716783771691667

素数同士ですので、素因数分解すれば良さそうです。
桁が非常に大きいので、PCパワーを借りましょう。

pythonのライブラリに、sympyというものがあるので使用してみます。

import sympy

n=1422450808944701344261903748621562998784243662042303391362692043823716783771691667
result = sympy.factorint(n)

print(result)

....反応が返ってきません
数値の桁数を少なくして試したところ問題なく動作したので、ちょっと桁数が大きすぎてtimeoutになってしまったようです。

さらに調べたところ、素因数分解をしてくれる 「factordb」 という便利なサイトがあったので、こちらを使わせていただきましょう（ありがとうございます!!）
結果は、

p = 2159947535959146091116171018558446546179
q = 658558036833541874645521278345168572231473

になりました！

試しに、検算をしましょう。

p = 2159947535959146091116171018558446546179
q = 658558036833541874645521278345168572231473
print(p * q)

1422450808944701344261903748621562998784243662042303391362692043823716783771691667

nと同じ値になりましたね！

続いて、fを求めましょう。fは、$(p-1)×(q-1)$ なので、

p = 2159947535959146091116171018558446546179
q = 658558036833541874645521278345168572231473
f = (p-1)*(q-1)
print(f)

1422450808944701344261903748621562998783582944057933890341955406374353056752914016

になりました！

2: eとfで、dを求める

dは、$e^{−1}(mod(f))$ のようです。

こちらの式について、少し掘り下げてみました。
RSA暗号は、$e×d ≡ 1(mod(f))$ を満たす必要があります。
これをモジュラ逆数と呼ぶそうです。

※ ≡は、左辺と右辺が同じ余りを持つ事を示します。（例：5×29 ≡ 1(mod 36)は、左辺と右辺ともに、36で割った余りが1になります。）

eの逆数をfで割った余りを求めると良さそうです。
指数演算を計算することができる、pythonのpow関数を使って、dを求めていきたいと思います。

d = pow(e,-1,f)
print(d)

975120122884150896343356420256053234758228648361853546720066993334766006694511009

こちらで、dを求めることができました。

また、pythonは暗号系のライブラリも充実しており、モジュラ逆数を求めてくれるinverseという便利な関数もあるようでした。

ライブラリをインストールします。

pip3 install pyrebase4

Crypto.Util.numberというライブラリのinverseという関数にeとfを渡してあげれば、dを求めることができます。

from Crypto.Util.number import inverse

d = inverse(e, f)

3: cとdとnで、M（答え）を求める

最後に、mを求めます。Mは、$C^{d}mod(n)$ のようです。
cとnは設問にあり、dは上記で値を得ることができました。
先程と同様にpow関数を使って、mを求めていきたいと思います。

m = pow(c,d,n)

13016382529449106065927291425342535437996222135352905256639555294957886055592061
b'picoCTF{sma11_N_n0_g0od_00264570}'

pow関数を実行したところ、文字列が現れました。
無事に暗号を解読することができたようです！

感想

RSA暗号はぼんやりと知っていましたが、計算式の実装に触れたことはなかったので、
普段何気なく使用している公開鍵や秘密鍵の仕組みを少しだけ覗いてみることができました！

最後に

スペースマーケットでは一緒に働く仲間を募集しています！
新しい技術に興味がある方も、手を上げればチャレンジできる環境だと思います。
カジュアルに話を聞きたいだけという方でも大歓迎ですので、ちょっとでも興味があれば
こちらからご応募をお待ちしております！