Zenn
👻

新米エンジニアでも出来るCTF超入門

2023/12/17に公開
#
CTF
idea

はじめに

CTF Advent Calendar 2023の17日目です。

近年、競プロの規模が大きくなり初中級者向けの記事や本が充実してきましたが、CTFの方は相変わらず記事が少ないです。
CTF勢が増えるように、CTFのはじめの一歩となるような超初心者向けの解説記事を書いていきたいと思います。
今回は、picoCTFの解説記事を書きます。
※picoCTFにつていはこちらの動画で紹介されていますので、よかったら見てください。

想定読者

  • CTFに興味があるけど、どうやって始めればよいのか分からない人

前提条件

  • atcoderのB問題程度が解ける程度の実装力がある
  • CTFに興味がある

問題

Mind your Ps and Qs

Cryptography（暗号）のMind your Ps and Qsの解説をします。

問題文は以下です。

In RSA, a small e value can be problematic, but what about N? Can you decrypt this? values

訳

RSAでは、eの値が小さいと問題になることがあるが、Nではどうだろう？これを復号できるか？

ファイルが与えられているので、中身を見ると以下のようになっています。

Decrypt my super sick RSA:
c: 861270243527190895777142537838333832920579264010533029282104230006461420086153423
n: 1311097532562595991877980619849724606784164430105441327897358800116889057763413423
e: 65537

解説

RSAとは?

公開鍵暗号の一つで、大きな数の素因数分解を高速に行うことが難しいことを前提とした暗号方式です。

RSAの暗号化と復号化は以下の式で表現することができます。

暗号文 = 平文^E mod N
平文 = 暗号文^D mod N

平文を得るにはDとNの両方が分かれば良いということになります。
つまり、現在与えられているCとnとEからDとNを求める問題と言い換えることができます。

RSAの計算式

RSAの計算式について簡単に説明していきます。

1.Nを求める

素数p,qを用意する。

N = p × q

2.Lを求める

lcmは最小公倍数のことです。
Lはp-1とq-1の最小公倍数。

L = lcm(p-1,q-1)

3.Eを求める

gcdは最大公約数のことです。
EとLとの最大公約数は1。

1 < E < L
gcd(E,L) = 1

4.Dを求める

1 < D < L
E × D mod L = 1

pとqを求める

ますは、を求めましょう。
pとqはNを素因数分解をすれば求めることができるので、factordbを利用して、求めます。

pとqは以下の数字であることが分かりました。

p: 1955175890537890492055221842734816092141
q: 670577792467509699665091201633524389157003

Lを求める

Lはp-1とq-1の最小公倍数なので、簡単に求めることができます。
Lは655548766281297995938990309924862303391745948568541640153600826846706399279082140と分かりました。

def gcd(a, b) -> int:
    """
    最大公約数を求める
    Args:
        a:
        b:

    Returns:aとbの最大公約数

    """
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b) -> int:
    """
    最小公倍数を求める
    Args:
        a:
        b:
    Returns:aとbの最小公倍数
    """
    return a * b // gcd.gcd(a, b)


a, b = map(int, input().split())
print(lcm(a-1, b-1))

$ 1955175890537890492055221842734816092141 670577792467509699665091201633524389157003
> 655548766281297995938990309924862303391745948568541640153600826846706399279082140

Dを求める

Dを求めるには自前で実装すると少々面倒くさいですが、Pythonだとinverseというメソッドを使うと簡単に求めることができます。
Dは693529123416505412979446025120625035374876994645029007711823240743237277989774953ということが分かりました。

from Crypto.Util.number import inverse

e = 65537
l = 655548766281297995938990309924862303391745948568541640153600826846706399279082140

d = inverse(e, l)
print(d)
> 693529123416505412979446025120625035374876994645029007711823240743237277989774953

平文を求める

DとNを求めることができたので、これで平文を求めることができます。
long_to_bytesで自然数をバイト文字列に変換することができます。

from Crypto.Util.number import long_to_bytes

c = 861270243527190895777142537838333832920579264010533029282104230006461420086153423
n = 1311097532562595991877980619849724606784164430105441327897358800116889057763413423
d = 693529123416505412979446025120625035374876994645029007711823240743237277989774953

print(long_to_bytes(pow(c, d, n)))

参考文献

Discussion