angstromctf 2022 | strike slip fault

#angstromctf_2022

#!/usr/local/bin/python3

from Crypto.Util.number import getStrongPrime, long_to_bytes, bytes_to_long, inverse
from secrets import randbelow, token_bytes

print("Welcome to my super secret service! (under construction)")

BITS = 4096

p = getStrongPrime(BITS//2)
q = getStrongPrime(BITS//2)
n = p*q
phi = (p-1)*(q-1)
e = 65537

flag = [REDACTED]
m = bytes_to_long(flag+token_bytes(BITS//8 - len(flag) - 1))
c = pow(m,e,n)

print("Making sure nothing was tampered with...")
print("n =", n)
print("e =", e)
print("c =", c)

d = inverse(e, phi)
bits = list(range(d.bit_length()))
for i in range(3):
    d ^= 1 << bits.pop(randbelow(len(bits))) # these cosmic rays man...

ans = long_to_bytes(pow(c,d,n))
if ans.startswith(flag):
    print("Check passed!")
print(f"Check failed, {ans} does not start with the flag.")

RSA で $d$ を3bit反転した $d'$ で計算した $c^{d'} \mod n$ が与えられている

$4096^3$ 通りを試すのはちょっと無謀なので計算量を落としたい

$d = d' + x + y + z$ と置いて

$c^{de} = c = c^{ed'}c^{ex}c^{ey}c^{ez}$

ちょっと移行すると

$cc^{-ez} = c^{ed'}c^{ex}c^{ey}$

で左辺は4096通り、右辺は $4096^{2}$ 通り探索すればよくなる。これは中間一致攻撃

from Crypto.Util.number import inverse
from tqdm import tqdm
from params import n, e, c, X

# n = 9140340882689212730155359971373341589904937359852235546702672536655369530553420817381813451218687545319568507382977116565519837404970637995988344068147791
# e = 65537
# c = 4530348442227714695937382276878124701963832958634069180852344049055731475733769964307235079655416444577915629709061776163449283675137687690435963926176856
# X = 8100268220717673416373349525694679267700126627049675234084489168227309228802179438062093639297797848716548182691013801542535338654860628521791670913302729

powTable = {}
s = c
for i in range(4096):
    powTable[i] = pow(s, e, n)
    if i != 0:
        powTable[-i] = inverse(pow(s, e, n), n)
    s = s*s % n


table = {}
for z in range(4096):
    table[c * powTable[z] % n] = z
    table[c * powTable[-z] % n] = -z

Xe = pow(X, e, n)
for x in tqdm(range(4096)):
    for y in range(4096):
        key = Xe * powTable[x] * powTable[y] % n
        if key in table:
            print(x, y, table[key])

        key = Xe * powTable[-x] * powTable[y] % n
        if key in table:
            print(-x, y, table[key])

        key = Xe * powTable[x] * powTable[-y] % n
        if key in table:
            print(x, -y, table[key])

        key = Xe * powTable[-x] * powTable[-y] % n
        if key in table:
            print(-x, -y, table[key])

実際にはpythonに待ちきれずgoでやったがバグらせた。絶対にpythonを素直に実行したほうがはやい

package main

import (
    "fmt"
    "math/big"
)

func main() {
    n := new(big.Int)
    e := new(big.Int)
    c := new(big.Int)
    X := new(big.Int)

    n.SetString("900070490622067320191637256322689412527951600989690014040742293402515652299807355416973524079799412242303695005849373445039400849591465597575071172369743191868426614517714438100741689051321511330353068870085391955380005924193452388879170080569217611534666723431228876665400462326676136834184598097637612462138913958737759322989904101853151206852072163254977079626441345648695044414743061561749348880019607938930572091154083635100263637181513759943165217032366307235262290149121982361740356299744695043277615922872281013512722579789196565526621382570308445038543830946971870143416647314522450656476380450926273955034941922166822345239863969969054173792809511555294506499479460733800203789975490744756171199513541914459052812970878813532508200185561086389173320140400837553390150640118664644728326976956623287728071670363574828765499081630098395101207132121557269428414754204021602411843144222862499913321787608802795431375613453451646357431858538087082423774836125541442108814662883958785416540932102786177408197877642161771714550028264013960050526390792232071691880271991611403599658754594252925331797512039370218705211962522382739680885820067113131946086305783275655204391316332325661610449937310593926456756974934432806107508584687", 10)
    e.SetString("65537", 10)
    c.SetString("785019041003063094605338644855048946920785904799316056061128856210648574008947823318103541165223596391441869599653542367469582749735833238881174760706303204193239490503494128261465176354669635814736470937192039240288549501040533102957388190144367063971050093258087028919607189745941929361743460532173075128757057170184845810592063392093611909588608434601111240804241210939629912198253922278311726074613374311364714503593835714701261515902458295964850200883428876941854713297600424159346665228238295844165261930957085099153766532230753418227132506795445835713828219025117217211988132423808868878491252074351084194298227654253015597086572860607173699553442586206642744564518363534136736457282374055689877416438808797889637908338960048452523853477755423540348739016013753910186174575168439451877576061110984631119994270572126858635951627682166569924669328090525845842805274374629938562576743743090674720310052196389604757172761607674745732712177986201837422518542301831341463977319044721933558836609327149863674429302791872305204502140781352055289953107204260973578971800635948027688728015052061073091633479965577903274852755170355267952134264963602557305761624298274953157061326235764865240265336589063356964395136173662984407099988044", 10)
    X.SetString("784489495468571109188813786300065792718466941891375680339680351099906992092012560622281058901481727608379436770643947838100771097034892479863481490964248079249669296187843197169750557078786466278275964330125707642098911532401415621220564291264622868120255692617763734589658308195032367552288658029713803414153308230989853931719073087377045697246190167528501235784599767435435479382688081561215923317719065187481162082910362911693891787580869264399492382017064836439602369480530884508688679256921858031150693828003732997950661087455735621987017130348755705453530925223908593242261849676095667813588011485469728022001359052535870910922385435137849112885019667187440155895192524594115470778334811290150212306541138741981251647545986252665548280686115765451310014589430484377208218967136804793899474823151213719973491773729390712970430895406374203215090879858983542038156263274198939484594210891072898901932455586305212317876649964005624668249093581581590248481973955436791111965066836328296129781747876496609671461779327195328566384940114730509066327061361661012265500671925361784324886555148904937254720230266131270822088948094566521296278606491802254922695137862484728209835577814044486208934290655283891593577693247329177789703073925", 10)

    powTable := make(map[int]*big.Int)
    s := new(big.Int)
    s.Set(c)
    for i := 0; i < 4096; i++ {
        powTable[i] = new(big.Int)
        powTable[i].Exp(s, e, n)

        if i != 0 {
            powTable[-i] = new(big.Int)
            powTable[-i].Exp(s, e, n)
            powTable[-i].ModInverse(powTable[-i], n)
        }

        s.Mul(s, s)
        s.Mod(s, n)
    }

    table := make(map[string]int)
    for z := 0; z < 4096; z++ {
        s.Set(c)
        s.Mul(s, powTable[z])
        s.Mod(s, n)
        table[s.String()] = z

        s.Set(c)
        s.Mul(s, powTable[-z])
        s.Mod(s, n)
        table[s.String()] = -z
    }

    Xe := new(big.Int)
    Xe.Exp(X, e, n)

    key := new(big.Int)

    for x := 0; x < 4096; x++ {
        fmt.Printf("progress: %d/%d\n", x, 4096)
        for y := 0; y < 4096; y++ {

            for kx := range []int{-1, 1} {
                for ky := range []int{-1, 1} {
                    key.Mul(Xe, powTable[kx*x])
                    key.Mul(key, powTable[ky*y])
                    key.Mod(key, n)

                    if z, exist := table[key.String()]; exist {
                        fmt.Printf("%d %d %d\n", kx*x, ky*y, z)
                        return
                    }
                }
            }
        }
    }
}