Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

Harekaze mini CTF 2021 crypto writeup

official URL : Harekaze mini CTF 2021

終了後に解いて、3時間以内にcryptoは全完できたので自信になりました。全てのcryptoの問題について書けるのは久しぶりです。



writeup


ファイルなどは公式サイトからのDLをお願いします


first exam

kurenaif魔法学校の入学試験です。PythonでCrypto問を解く基礎を学んでください！

base64でencodeしたものをbytes_to_longして、さらに整数値keyとXORしており、その演算結果とkeyの値が渡されています。同じ値で2回XORすると元に戻る性質を使って、もう一度keyとXORしてlong_to_bytes → base64でdecodeでflagが復元されました。

import base64
from Crypto.Util.number import *
key = 407773567691797768945309646881381330143924911048532252374484400956007416406007936505301187512369384531883020224488253602523154102140950477859193
flag = 1392812161183976577227166142672085037819799462496681473937900208451109718213256601589927195482395914799893761610554140977947503369343069077952836
flag ^= key
print(base64.b64decode(long_to_bytes(flag)))


HarekazeCTF{OK_you_can_join_wizardry_school}



sage training

一緒にsageに入門しよう！

行列の演算を使ったRSAのようですね。

まず、2×2行列の2乗について考えます。

[ [a, b], [c, d] ] ^2 = [ [a*a + b*c, a*b + b*d], [c*a + d*c, c*b + d*d] ]

今回、対角成分はp, flagであり、それ以外は0となります。上記の例だと、b及びcが0となるので

[ [a, 0], [0, d] ] ^2 = [ [a*a + 0*0, a*0 + 0*d], [0*a + d*0, 0*0 + d*d] ] = [ [a*a, 0], [0, d*d] ]

と、対角成分だけが2乗されそれ以外の値は0になりました。同様に3乗, 4乗と計算しても同じ結果となるので、output.txtにある行列の対角成分は pe mod n, flage mod n となります。


前者(pe mod n)を使って素因数分解します。具体的には、この値はpの倍数かつnの倍数ではないことが分かっているので、gcdを取るとpの値が出てきます。

素因数分解ができたので秘密鍵dを求め、(flage)d mod nを計算すればflagとなります。SECCON CTF 2021 pppp のように行列をd乗して元通りにしても復元され、問題名よりこちらの方がより想定解なのかなと思っています。

from Crypto.Util.number import *
import math
c = [(94705679004463284733541288053549635663983624426348082883911423652044420589882644740030824857964094373277293351421545117172457918484063609288563394969114856228940330220982203798491227942337707868513380987219942847139213839127934175216087451584996193094098370176337671205679032479708240220775365041028562298045, 0), (0, 14243811671300968907609174458855708829741032120754409000357686908873126315334915231420353855815283498571171729689334442024813021199910238276500626386134036150649025606319036019223959715867658461585221634071508142818645594816357236002650041503442624594820852244903155433016041077813314542285538820574629698950)]
n = 123658273021758657244926229590842169697216202161458868027271307824674005278002104678607018762498569110790554844101479136721968081586766904446085438475258864812618061595487772978115460674609635002737826341845366713797429237465562629770189347062332559337703309881797723858775511801114681134013841432780549606609
e = 65537
p = math.gcd(c[0][0],n)
q = n//p
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c[1][1],d,n)
print(long_to_bytes(m))


HarekazeCTF{which_do_you_like_mage_or_sage?}



mulmulmulti-prime rsa

とっても安全なRSA暗号をより安全にするためにたくさん素数をかけました♥

Nが小さい素数がたくさんと、512bit素数2つの積となっています。この「小さい素数がたくさん」だけの総積はflagより大きいというのがミソでした。


まずNを素因数分解しようとfactorDBに投げると、397までの素数が1つずつと大きな合成数(=p×q)に分けることができます。そしてproblem.py内にプログラムでは使っていないのにcrt関数をimportしています。これが解法への誘導となっているとエスパーします。

ここで、素数の一つ7を例にとると、k = 2 mod 7 となる整数kについて、(k mod N) mod 7 も2となります。なんでかと言われるとなんとなく？となるのですごい方の証明を聞いてください…。

ゆえに、0~6をe乗した値を7で割った余りと0~6をe乗した値をNで割った余り(=暗号文c)をさらに7で割った余りは一致します。これを使うことで平文mを7で割った余りを特定することができます。これを素数2から397で同じことをして、中国剰余定理で平文を復元することができました。

from Crypto.Util.number import *
from sympy.ntheory.modular import crt
x = 397
num = 2
mod = []
val = []
c = 6444384937952479446360543800306726693252997452825552613901755375099255166714791921303820142603050845604453415771813934605436773362180219243666255359716995456217503120584807127945079526447091871683834669804927783277541340212953733681665967741288390917442432418885663222080013261671274096066346531406665749671823431928515791704387207382571496076159703188939522942673142857854899106254676400171188528066441584894129954980506317784944539407501773216256651827692873203651175
e = 65537
n = 13105434584967797009222723925714056612973229654650200307281518067540513311350491750775580308761120670043385919352137451528084580772272083564644136982142743585238409901075466075590932718136237274538943262152033321299508243379729042658808185056276914453786554308920681089647171956781340126500826872053436182017911021212882822071757885385543985492728290224139575551494811781675324350095354476279621406379090030101147754502075514438702852559140941288066281245455568260855730
while num <= x:
    if isPrime(num):
        mod.append(num)
    num += 1

for i in range(len(mod)):
    for j in range(mod[i]):
        if c%mod[i] == pow(j,e,mod[i]):
            val.append(j)
            break

m, MOD = crt(mod,val)
print(long_to_bytes(int(m)))


HarekazeCTF{Small_prime_numbers_give_a_large_amount_of_information}



lost key

秘密鍵も公開鍵も教えません。魔法学校に入門したならできますよね？

flagを1文字ずつRSAで暗号化していますが、公開鍵のNの方が未知です。しかしflag1文字のASCII値をe乗したものから暗号値を引くとNの倍数になります。これを分かっているflagの先頭12文字を利用して、Nの倍数を12個求めてgcdを取ると1024bitの値が出てきました。p, qは共に512bitであることから、この1024bitの値はNであると分かります。

以降は1回の暗号処理において平文が1byte分とかなり狭いので、平文をbrute forceすればflagが復元されます。

import math
from Crypto.Util.number import *

e = 65537
f = open("distfiles/output.txt")
a = f.readlines()
cs = eval(a[1][5:-1])
#print(type(cs))
flag_part = 'HarekazeCTF{'
ncandi = ord('H')**e - cs[0]
for i in range(1,len(flag_part)):
    ncandi = math.gcd(ncandi,ord(flag_part[i])**e - cs[i])

print('HarekazeCTF{',end="")
for i in range(len(flag_part),len(cs)):
    for j in range(128):
        if pow(j,e,ncandi) == cs[i]:
            print(chr(j),end="")
            break
print()


HarekazeCTF{Can_you_Recover_with0ut_the_public_4nd_pr1vate_keys!?}