CTF

この記事は、SYSKEN Advent Calendar 2022 12月22日の記事です。

はじめに

こんにちは、Mizuhaです。
~~アドベントカレンダーがあることをしっかり忘れてました。~~
今回初めてアドベントカレンダーの記事を書くので何を書こうか迷ったのですが、
今年先輩に進めて頂いて挑戦したCTFで学んだことについて書くことにしました。

CTFとはなにか

まず、CTFとはCapture The Flagの略です。情報セキュリティの様々な知識や手段を使って隠されたFlagを見つけて得点を稼ぐ競技です。

CTFの競技形式は大きく分けて攻防戦型と問題出力型の２つがあります。
攻防戦型はAttack-Defence、問題出力型はJeopardyと呼ばれます。

Jeopardyの問題のジャンルは、
・Web
・Pwn
・Reversing
・Crypt
・Forensics
・Misc
…などがあります。

今回は、Cryptのジャンルの一部を紹介していきたいと思います。

RSA暗号

RSA暗号の基礎を紹介していきます。
RSA暗号とは、大きな数の素因数分解が困難であることを利用した公開鍵暗号方式の暗号です。
公開鍵暗号方式は暗号鍵と復号鍵が別々の暗号方式なので暗号鍵は他者に見られても問題がありません。
暗号鍵は誰にでも公開されて使われるため、公開鍵と呼ばれ、そこから公開鍵暗号方式と呼ばれます。

RSA暗号の暗号化は、

暗号文＝平文^e mod N -(1)

つまり、平文をe乗してNの値で割った余りが暗号文です。
このeとNの組を公開鍵と呼びます。

逆に、RSA暗号の復号化は、

平文＝暗号文^d mod N -(2)

つまり、暗号文をd乗してNの値で割った余りが平文です。
このdとNの組を復号鍵(秘密鍵)と呼びます。

N,e,dの求め方
N：大きめの素数二つを掛け算したもの
N=p×q
e：(p-1)×(q-1)=L とした時、eとLの最大公倍数が１となるeを探す
d：e×d mod L=1 が成り立つｄを求める

ここで、実際に問題を解いてみましょう。

Mind your Ps and Qs

問題文：
In RSA, a small e value can be problematic, but what about N? Can you decrypt this?
valueファイルが配布されます。

values:
Decrypt my super sick RSA:
c: 964354128913912393938480857590969826308054462950561875638492039363373779803642185
n: 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e: 65537

ここでは、cを暗号文、mを平文とします。
Nが出ていないのでNを因数分解して、p,qを出します。

p=2434792384523484381583634042478415057961
q=650809615742055581459820253356987396346063

p,qがでたので(2)式を使ってプログラムで解きます。