WaniCTF2023 writeup

分母の$840$は正の得点を取ったチーム数を表しています．

EZDORSA_Lv1 (529/840)

問題

$p=3,q=5,n=pq,e=65535$のとき， $$ m^e = 10 \pmod n $$ を満たす最小の$m$はいくつか．

解法

$m=1,2,3,\cdots$と順番に試していけばよいです． Pythonでは，mのe乗をnで割った余りはpow関数を使ってpow(m,e,n)で求められます．

1
2
3
4
5
6
7
8
9
p = 3
q = 5
n = p*q
e = 65535

for m in range(n):
    if pow(m,e,n) == 10:
        print(m)
        break

結果は$10$です．

$(p,q)=(3,5)$より$\phi(n)=(p-1)(q-1)=8$です． $e=65535=2^{16}+1$なので，$e$を$\phi(n)$で割った余りは$1$です．オイラーの定理より，$m^e=m \mod n$が成り立つことがわかります．

EZDORSA_Lv2 (251/840)

問題

$n,e,c$が与えられます．$c$は$m,e,n$によって計算されます． $$ c = 5^{100} m^e \pmod n $$

1
2
3
n = 25465155563758206895066841861765043433123515683929678836771513150236561026403556218533356199716126886534636140138011492220383199259698843686404371838391552265338889731646514381163372557117810929108511770402714925176885202763093259342499269455170147345039944516036024012941454077732406677284099700251496952610206410882558915139338028865987662513205888226312662854651278789627761068396974718364971326708407660719074895819282719926846208152543027213930660768288888225218585766787196064375064791353928495547610416240104448796600658154887110324794829898687050358437213471256328628898047810990674288648843902560125175884381
e = 7
c = 25698620825203955726406636922651025698352297732240406264195352419509234001004314759538513429877629840120788601561708588875481322614217122171252931383755532418804613411060596533561164202974971066750469395973334342059753025595923003869173026000225212644208274792300263293810627008900461621613776905408937385021630685411263655118479604274100095236252655616342234938221521847275384288728127863512191256713582669212904042760962348375314008470370142418921777238693948675063438713550567626953125

解法

$c$と$n$を眺めると$n \gg c$という特徴から，$5^{100}m^e<n$ではないかと予想をします． $m$を$5^{100}$で割って$e$乗根を取れば$m$が求められます．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes, isPrime
from gmpy2 import iroot

n = 25465155563758206895066841861765043433123515683929678836771513150236561026403556218533356199716126886534636140138011492220383199259698843686404371838391552265338889731646514381163372557117810929108511770402714925176885202763093259342499269455170147345039944516036024012941454077732406677284099700251496952610206410882558915139338028865987662513205888226312662854651278789627761068396974718364971326708407660719074895819282719926846208152543027213930660768288888225218585766787196064375064791353928495547610416240104448796600658154887110324794829898687050358437213471256328628898047810990674288648843902560125175884381
e = 7
c = 25698620825203955726406636922651025698352297732240406264195352419509234001004314759538513429877629840120788601561708588875481322614217122171252931383755532418804613411060596533561164202974971066750469395973334342059753025595923003869173026000225212644208274792300263293810627008900461621613776905408937385021630685411263655118479604274100095236252655616342234938221521847275384288728127863512191256713582669212904042760962348375314008470370142418921777238693948675063438713550567626953125


c//=pow(5,100,n)
c = iroot(c,e)[0]
print(long_to_bytes(c))

5**100=7888609052210118054117285652827862296732064351090230047702789306640625です．かなり小さいですね．

EZDORSA_Lv3 (233/840)

問題

RSA暗号です．ただし，$n=p_1p_2p_3p_4\cdots p_{100}$と$100$個の相異なる素数の積です．また，各素数$p_i$は$25$ビットである．

解答

$p_i$が小さいので素因数分解ができます．あとは，オイラーの定理を使って$\phi(n)$を求めればよいです．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes, isPrime
from gmpy2 import iroot

n = 22853745492099501680331664851090320356693194409008912025285744113835548896248217185831291330674631560895489397035632880512495471869393924928607517703027867997952256338572057344701745432226462452353867866296639971341288543996228186264749237402695216818617849365772782382922244491233481888238637900175603398017437566222189935795252157020184127789181937056800379848056404436489263973129205961926308919968863129747209990332443435222720181603813970833927388815341855668346125633604430285047377051152115484994149044131179539756676817864797135547696579371951953180363238381472700874666975466580602256195404619923451450273257882787750175913048168063212919624027302498230648845775927955852432398205465850252125246910345918941770675939776107116419037
e = 65537
c = 1357660325421905236173040941411359338802736250800006453031581109522066541737601274287649030380468751950238635436299480021037135774086215029644430055129816920963535754048879496768378328297643616038615858752932646595502076461279037451286883763676521826626519164192498162380913887982222099942381717597401448235443261041226997589294010823575492744373719750855298498634721551685392041038543683791451582869246173665336693939707987213605159100603271763053357945861234455083292258819529224561475560233877987367901524658639475366193596173475396592940122909195266605662802525380504108772561699333131036953048249731269239187358174358868432968163122096583278089556057323541680931742580937874598712243278738519121974022211539212142588629508573342020495
n2 = n

# Factorize n
ps = []
i = 1<<24
while n2 != 1:
    if n2 % i == 0:
        print(i)
        ps.append(i)
        n2 //= i
    else:
        i += 1


# Calculate phi(n)
phi = 1
for a in ps:
    phi *= a-1

# Calculate d
d = pow(e,-1,phi)

# Decrypt
m = pow(c,d,n)
print(m)
print(long_to_bytes(m))

pqqp (156/840)

問題

RSA暗号で，$e,n,c$の他に，$s=p^q+q^p \bmod n$が与えられる．

解答

実は，$s=p+q$であるので，$\phi(n)=(p-1)(q-1)=pq-(p+q)+1=n-s+1$となります．

なぜ成り立つのかというと(フェルマーの小定理$a^p \mod p = a$であることに注意)，$x = p^q+q^p$とすると，

$x \bmod p=q$である．
$x \bmod q=p$である．
これを満たす数は，整数$k$を用いて$x = p + q + kpq$と表される．

よって，$s=p+q$である．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes, isPrime
from gmpy2 import iroot

n = 31091873146151684702346697466440613735531637654275447575291598179592628060572504006592135492973043411815280891993199034777719870850799089897168085047048378272819058803065113379019008507510986769455940142811531136852870338791250795366205893855348781371512284111378891370478371411301254489215000780458922500687478483283322613251724695102723186321742517119591901360757969517310504966575430365399690954997486594218980759733095291730584373437650522970915694757258900454543353223174171853107240771137143529755378972874283257666907453865488035224546093536708315002894545985583989999371144395769770808331516837626499129978673
e = 65537
c = 8684906481438508573968896111659984335865272165432265041057101157430256966786557751789191602935468100847192376663008622284826181320172683198164506759845864516469802014329598451852239038384416618987741292207766327548154266633297700915040296215377667970132408099403332011754465837054374292852328207923589678536677872566937644721634580238023851454550310188983635594839900790613037364784226067124711011860626624755116537552485825032787844602819348195953433376940798931002512240466327027245293290482539610349984475078766298749218537656506613924572126356742596543967759702604297374075452829941316449560673537151923549844071
s = 352657755607663100038622776859029499529417617019439696287530095700910959137402713559381875825340037254723667371717152486958935653311880986170756144651263966436545612682410692937049160751729509952242950101025748701560375826993882594934424780117827552101647884709187711590428804826054603956840883672204048820926

phi = n - s + 1
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

fusion (67/840)

問題

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
from Crypto.PublicKey import RSA

RSAkeys = RSA.generate(2048)
p = RSAkeys.p
q = RSAkeys.q
n = RSAkeys.n
e = RSAkeys.e
m = b"FAKE{<REDACTED>}"
c = pow(int.from_bytes(m, "big"), e, n)

mask = int("55" * 128, 16)
r = p & mask
mask = mask << 1
r += q & mask

print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")
print(f"r = {r}")

解答

まず，0x55...55という数を考えます．これは，0b01010101...01010101という2進数で表されます．これを左に1ビットシフトすると，0b10101010...10101010となります．すなわち，$r$が表しているのは，

$p$の下から奇数ビット目だけを抜き出した数
$q$の下から偶数ビット目だけを抜き出した数

を足し算したものです．逆に言えば，$r$の下から奇数ビット目は$p$の下から奇数ビット目と一致し，$r$の下から偶数ビット目は$q$の下から偶数ビット目と一致します．

この問題は，次の性質を使います．

「$p$の下位$x$ビットと$q$の下位$x$ビットの積」の下位$x$ビットは，$n$の下位$x$ビットと一致する．

これを$x=1,2,3,\dots$と繰り返すことで，$p,q$を求めることができます．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import bytes_to_long, getPrime, long_to_bytes, isPrime
from gmpy2 import iroot

n = 27827431791848080510562137781647062324705519074578573542080709104213290885384138112622589204213039784586739531100900121818773231746353628701496871262808779177634066307811340728596967443136248066021733132197733950698309054408992256119278475934840426097782450035074949407003770020982281271016621089217842433829236239812065860591373247969334485969558679735740571326071758317172261557282013095697983483074361658192130930535327572516432407351968014347094777815311598324897654188279810868213771660240365442631965923595072542164009330360016248531635617943805455233362064406931834698027641363345541747316319322362708173430359
e = 65537
c = 887926220667968890879323993322751057453505329282464121192166661668652988472392200833617263356802400786530829198630338132461040854817240045862231163192066406864853778440878582265466417227185832620254137042793856626244988925048088111119004607890025763414508753895225492623193311559922084796417413460281461365304057774060057555727153509262542834065135887011058656162069317322056106544821682305831737729496650051318517028889255487115139500943568231274002663378391765162497239270806776752479703679390618212766047550742574483461059727193901578391568568448774297557525118817107928003001667639915132073895805521242644001132
r = 163104269992791295067767008325597264071947458742400688173529362951284000168497975807685789656545622164680196654779928766806798485048740155505566331845589263626813345997348999250857394231703013905659296268991584448212774337704919390397516784976219511463415022562211148136000912563325229529692182027300627232945

mask = int("55" * 128, 16)

pm = r & mask
qm = r & (mask << 1)

# 下の桁から，掛け算した結果がnの下位ビットと一致するかを確認する
for i in range(1024):
    s = i+1
    if i%2==0:
        # pがわかっている，qがわからない
        q2 = qm | (1 << i)
        n2 = pm * q2
        if bin(n2)[-s:] == bin(n)[-s:]:
            qm |= (1 << i)
    else:
        # pがわからない，qがわかっている
        p2 = pm | (1 << i)
        n2 = p2 * qm
        if bin(n2)[-s:] == bin(n)[-s:]:
            pm |= (1 << i)
    #print(i, bin(pm*qm)[-s:], bin(n)[-s:])

assert pm*qm == n

d = pow(e, -1, (pm-1)*(qm-1))
m = pow(c, d, n)
print(long_to_bytes(m))

DSA? (36/840)

問題

色々計算しているが，必要なのは次の情報． $$ \begin{aligned} y &= g^x \mod p \\ k &= m^{-1} \mod q \\ s &= k^{-1}(h+xr) \mod q \end{aligned} $$ サーバーに接続すると，ランダムな$x$が生成され，$p,q,g,y,h,r,s$が得られる．ここで，$p,q,g,h,r$は固定である．

解答

$k$の値も固定だから， $$ \begin{aligned} s &= k^{-1}(h+xr) \mod q \\ &= (m^{-1})^{-1}(h+xr) \mod q \\ &= m(h+xr) \mod q \\ &= mh + mxr \mod q \end{aligned} $$ 異なる$x_1,x_2,x_3$に対する値を$s_1,s_2,s_3$とすると， $$ \begin{aligned} s_1 &= mh + mx_1r \mod q \\ s_2 &= mh + mx_2r \mod q \\ s_3 &= mh + mx_3r \mod q \\ s_1 - s_2 &= m(x_1 - x_2)r \mod q \\ s_2 - s_3 &= m(x_2 - x_3)r \mod q \\ (s_1 - s_2)r^{-1} &= m(x_1 - x_2) \mod q \\ (s_2 - s_3)r^{-1} &= m(x_2 - x_3) \mod q \end{aligned} $$

$\rm{GCD}((s_1 - s_2)r^{-1}, (s_2 - s_3)r^{-1})$を計算すると，$m$が求まります．求まらないこともあります．

Guess (59/840)

問題

数列$(1,2,3,\cdots,10^4)$の順列$(P_1,P_2,\cdots,P_{10^4})$が用意されていて，サーバーに接続して数列$(a_1,a_2,\cdots,a_{n})$を入力すると，$P_{a_1},P_{a_2},\cdots,P_{a_{n}}$をランダムに並べ替えたものが返ってくる．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import os
import random

ANSWER = list(range(10**4))
random.shuffle(ANSWER)
CHANCE = 15


def peep():
    global CHANCE
    if CHANCE <= 0:
        print("You ran out of CHANCE. Bye!")
        exit(1)
    CHANCE -= 1

    index = map(int, input("Index (space-separated)> ").split(" "))
    result = [ANSWER[i] for i in index]
    random.shuffle(result)

    return result


def guess():
    guess = input("Guess the numbers> ").split(" ")
    guess = list(map(int, guess))
    if guess == ANSWER:
        flag = os.getenv("FLAG", "FAKE{REDACTED}")
        print(flag)
    else:
        print("Incorrect")


def main():
    menu = """
    1: peep
    2: guess""".strip()
    while True:
        choice = int(input("> "))
        if choice == 1:
            result = peep()
            print(result)
        elif choice == 2:
            guess()
        else:
            print("Invalid choice")
            break

解答

入力を，$(0,1,1,2,2,2)$のように異なる個数にすれば，並べ替えられたものを返されても元の数列がわかる．これを複数回に分けて行えば良い．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from pwn import *

io = remote('guess-mis.wanictf.org', 50018)#, level='debug')
A= [0]*(10**4)
N = 1000
for i in range(0,10000,N):
    print(i)
    io.recvuntil(b'> ')
    io.sendline(b'1')
    io.recvuntil(b'> ')
    s = ""
    for j in range(0,N):
        for _ in range(j+1):
            s += (str(i+j)+" ")
    io.sendline(s.encode())
    p = io.recvline().decode()
    # pから`[,]`を取り除く
    p = p[1:-2]
    p = p.replace(",","")
    q = list(map(int,p.split()))
    # j+1個あったものをi+jに格納する
    d = dict()
    for a in q:
        d [a] = d.get(a,0) + 1
    for k,v in d.items():
        A[i+v-1] = k


io.recvuntil(b'> ')
io.sendline(b'2')
s = ""
for a in A:
    s += (str(a)+" ")
io.sendline(s.encode())
io.interactive()

range_xor (40/840)

問題

整数列Aの任意の要素$a_i(0\leq a_i\leq 1000,i=1,2…N)$に対して操作$f$を次のように定める

$i$番目の要素を$\text{min}(a_i, 1000-a_i)$に置き換える

操作$f$を好きな回数行った後の整数列$B={b_1,b_2…b_N}$に対して $X = b_1 \oplus b_2 \oplus … \oplus b_N$ とするとき、$X$を最小にするような整数列$B$の種類数を $10^9+7$で割った余りをFLAGとする。

解答

$X$としてありうる数は，せいぜい$2^{10}=1024$個しかないため，

$\text{dp}[i][j] \coloneqq$ $i$番目までの数に操作を行ってそれらのXORが$j$である通り数

という動的計画法を考えることができる．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# include <iostream>
# include <map>
# include <vector>

using namespace std;

int main(){
    int N = 1000;
    vector<int> A;
    for(int i = 0; i < N; i++){
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }
    vector<vector<long>> dp(N+1, vector<long>(1024, 0));
    constexpr long mod = 1000000007L;
    dp[0][0] = 1;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < 1024; j++){
            dp[i+1][j^A[i]] += dp[i][j];
            dp[i+1][j^A[i]] %= mod;
            if(A[i] != min(1000-A[i],A[i])){
                dp[i+1][j^(1000-A[i])] += dp[i][j];
                dp[i+1][j^(1000-A[i])] %= mod;
            }
        }
    }
    long ans = 0;
    for(int i = 0; i < 1024; i++){
        if(dp[N][i] != 0){
            ans = dp[N][i];
            break;
        }
    }
    cout << ans << endl;
}

感想

EZDORSA_Lv1 1:59 5位
EZDORSA_Lv2 5:38 2位
EZDORSA_Lv3 9:41 2位
pqqp 29:48 7位
fusion 52:07 2位
DSA? 1:59:26 2位
Crypto全完 1:59:26 2位

Crypto全完でしたが，first bloodは一つもありませんでした．こういうチャンスは滅多にないと思うので悔しいです．

数学チックな問題が多くて楽しかったです．