HSCTF 7 (2020) Writeup

CTF_Writeup

2020年6/1 ~ 6/6に開催されたHSCTF 7 にm1z0r3として参加しました。Crypto問はあと1問で全完だったので悔しかったです..

自分が解いたCrypto問題のWriteupを書きます。

Chonky E

問題文をみると、AlleyはRSA、JasonはSchmidt-Samoaという暗号化手法でメッセージを暗号化を行った。ただし、2人とも同じ素数の組（p, q）を用いているとのこと。

解法

明らかにAlleyが使用した公開鍵eの値が大きいため、wiener's attackによって秘密鍵dは直ぐに計算できる。

問題は次のJasonが使用したSchmidt-Samoa暗号を破ること。

Schmidt-Samoa暗号は次のように鍵生成、暗号化、復号を行う。

  • 鍵生成

$$ N = p^2*q\\ d = N^{-1} \;mod \;lcm(p-1,q-1) $$

  • 暗号化

$$ c = m^N\;mod\;N $$

  • 復号

$$ m = c^d\;mod\;pq $$

したがって、復号するためにはp, qを求める必要がある。

d, e, Nが分かってるので、ここから素因数分解する方法があるんじゃないかと考えて調べてみると、次の記事を見つけた。

https://www.di-mgt.com.au/rsa_factorize_n.html

ここにあるとおりに実装をするとp, qの組が得られる。あとは上に示した通りにSchmidt-Samoa暗号の復号を行う。

#solver.py
from RSAwienerHacker import *
from Crypto.Util.number import *
import random
e = 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717
n = 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313
c_j = 16267540901004879123859424672087486188548628828063789528428674467464407443871599865993337555869530486241139138650641838377419734897801380883629894166353225288006148210453677023750688175192317241440457768788267270422857060534261674538755743244831152470995124962736526978165448560149498403762447372653982922113772190234143253450918953235222315161964539311032659628670417496174123483045439359846360048774164337257829398345686635091862306204455687347443958931441225500856408331795261329035072585605404416473987280037959184981453888701567175803979981461050532113072292714696752692872526424122826696681194705563391161137426703690900733706866842363055967856443765215723398555522126909749236759332964873221973970368877565410624895160438695006432021529071866881905134494489266801004903504121740435965696128048690741210812963902631391765192187570107372453917327060678806282122942318369245760773848604249664378721970318257356486696764545 

d = hack_RSA(e, n)
print(d)

## calc p,q from e, n, d
k = e*d - 1
Is_Finish = False
while True:
    t = k
    g = random.randint(2, n-1)
    #t= k
    while t%2 == 0: 
        t = t//2
        x = pow(g, t, n)
        y = GCD(x-1, n)
        if x > 1 and  y > 1:
            print("Finish!")
            q = y
            p = n//q
            Is_Finish = True
            break
    if Is_Finish:
        break
print("p: {}".format(p))
print("q: {}".format(q))

n_j = pow(p,2)*q
phi = (p-1)*(q-1)
d_j = inverse(n_j, phi)
m = pow(c_j, d_j, p*q)
print(long_to_bytes(m))

Flag: flag{remarkably_superb_acronym}

Randomization 1

アセンブラを読むと、Guess してほしい数字は前の数字をprev_numとすると 0x25*prev_num+0x41)&0xff

とわかるので、その計算をするようにコードを書く。

#solver.py
from pwn import *
#nc crypto.hsctf.com 6001

io = remote("crypto.hsctf.com", 6001)

def Guess(prev_num):
    print(io.recvuntil("Guess my number:"))
    next_num = (0x25*prev_num+0x41)&0xff
    print("next_num: {}".format(next_num))
    io.sendline(str(next_num))
    return next_num


print(io.recvuntil("free number:"))
free_num = int(io.recvline())
print("free_num: {}".format(free_num))
prev_num = free_num
for _ in range(10):
    prev_num = Guess(prev_num)

print(io.recvall())

Flag: flag{l1n34r_c0n6ru3n714l_63n3r470r_f41lur3_4b3bcd43}

Randomization 2

次は計算が0x5DEECE66D*prev_num+0xB)&0xffffffffffffffffになっただけなので、この部分だけRandomization 1のスクリプトから変えればよい。

#solver.py
from pwn import *

io = remote("crypto.hsctf.com", 6002)

def Guess(prev_num):
    print(io.recvuntil("Guess my number:"))
    next_num = (0x5DEECE66D*prev_num+0xB)&0xffffffffffffffff
    print("next_num: {}".format(next_num))
    io.sendline(str(next_num))
    return next_num

print(io.recvuntil("free numbers\n"))

free_num_1 = int(io.recvline())
free_num_2 = int(io.recvline())
print("free_num_1: {}".format(free_num_1))
print("free_num_2: {}".format(free_num_2))

prev_num = free_num_2
for _ in range(10):
    prev_num = Guess(prev_num)

print(io.recvall())

Flag: flag{1n53cur3_r4nd0m_46b8861b}

Extremely Complex Challenge

楕円曲線暗号の問題。まずは与えられたp = 404993569381, b = 54575449882, 生成元となる点 (g_x, g_y) = (391109997465, 167359562362)の情報から、y2 = x3 + ax + b における a の値を求める。ここは単純に a = (g_y^2 - g_x^3 - b)g_x^-1 mod p を計算する。

これによって楕円曲線の式が求まるが、ここから公開鍵 (209038982304, 168517698208)を使ってどうやって秘密鍵を求められるのか？

楕円曲線上における公開鍵は生成元Gよりx倍された点 (xG)を示しており、通常であればこの (xG)からxの値を求めることはできない（楕円曲線上の離散対数問題）。

しかし今回は数字が小さいため、SageMathを用いて次のように簡単に解くことができる。

#solver.sage.py
from sage.all_cmdline import *
from Crypto.Util.number import *

p= 404993569381
b = 54575449882
g_x = 209038982304
g_y = 168517698208
# Calc a
a = ((pow(g_y, 2, p)  - pow(g_x, 3, p) - b  )* inverse(g_x, p))%p
print("a: {}".format(a))
#a = 316508952642

# Calc d
R=Zmod(p)
E=EllipticCurve(R, [a,b])

Pk = E(g_x, g_y)
G= E(391109997465, 167359562362)

d = G.discrete_log(Pk)
print("flag{{{}}}".format(d))

Flag: flag{17683067357}

その他

Affina and the Quadratics は暗号文をみて 「Affine_is_interestingじゃね？」と思ってリートにして入力したら通ってしまいました。これどうやるんだろう。。26 character charsetってアルファベットじゃないのかな。。