Day 08

Attachment:

from Crypto.Util.number import getPrime, bytes_to_long
from secret import FLAG

def rotate(s):
    return s[1:] + s[:1]

p = getPrime(256)
g = 2

print('p: ', p)
for _ in range(len(FLAG)):
    x = bytes_to_long(FLAG.encode())
    h = pow(g, x, p)
    print('leak: ', h)
    FLAG = rotate(FLAG)

p:  105891552782768273485439811488443354235545023673195353053856843893816480862271
leak:  74834831693148489075053741970537349864361072646438063822128523522624111096404
leak:  94637262384206414487913618520407895315549149001067603290715492338419957063638
leak:  26119415647812686814124878968032828750956202141747974248626227495752618826310
leak:  4679774184271053791528196045893972569586759227111353536533198888487507918565
leak:  18247264710550364407701539407739806326963229364366084285259750379893601861765
leak:  57915316904508068959154652733100932636576891111709785240327600448742235657223
leak:  48726379408397107751482798948037834170753506073391626907440435722452593080790
leak:  23985113650578780235980433910057970681859494895610853985857472866552793069375
leak:  79231016211481853602891211467430186947199626871048819648312025046281485147965
leak:  1741002057862179063516105232753064091765321308410446556962767548042727938590
leak:  45723548930603031191234669145592632467258468694483505689072179691228438466667
leak:  58359671511194341930052508512801343119287048085288142869480583778613556216586
leak:  36424897628935082604512568766716569943269039796337573854278402880102811617963
leak:  74124749341279711257845847090110538409556405630352757105373182076739304300759
leak:  66309699088883552645305984224828051437638962884903042514430099711503266344026
leak:  3162806651485565481013375199103880408462676315825209573632289159416883750178
leak:  38582718538740737041784799604514668813686704870272183643601445048856770639975
leak:  60816150467494956825800367310063997854145812297158134406617773585762215516843
leak:  12353526085228982771214476339845069964525380861405349768474892062968628975241
leak:  105582281937486445268146775233874434792742700624750876452894760571703935174919
leak:  13238662997179930853908762356537888264584682314391321882412877512234731316348
leak:  75875040959123636492014257513993145046661183624855640826292741601485403285328
leak:  12149947150174642792165286320748309835337741992502616190760701133669565860666
leak:  38650263185329843052214216132708910216830022007692554045491912295950867554552
leak:  92561547647296020081423003558701351791204280991353765906671600253604516771598
leak:  41349557324733447344437570514434312589869408427300508224464407246422794992797
leak:  86385180739170312287865404316483035605934760491085055759657242983443484861082
leak:  39348401982172687025128116440936094277482944374061555213943911942008513049037
leak:  58273481812023054183980778217247474508696785731672888895966172242039774561634
leak:  69932445711823749013619544296257448424270930795659726110506648765574551496961
leak:  11196151841801624492550269516119227591456953234837751240484968196644961160377
leak:  26041577455573938646072969268840197244828691423833869416465901173451675328995

The challenge:

1. Generates a 256-bit prime p
2. Uses generator g = 2
3. For each character in the FLAG (32 characters total):
   • Converts the entire FLAG string to a long integer x
   • Computes h = 2^x mod p
   • Prints h as a "leak"
   • Rotates the FLAG string (moves first character to the end)

Let the FLAG be bytes: \(b_0, b_1, \cdots b_{n-1}\) where n = 32, the integer representation is:

\(x_1 = b_0 \times 256^{n-1} + b_1 \times 256^{n-2} + \cdots + b_{n-1}\)

After rotation:

\(x_2 = b_1 \times 256^{n-1} + b_2 \times 256^{n-2} + \cdots + b_{n-1} \times 256 + b_0\)

Therefore:

\(x_2 = 256x_1 - b_0(256^n-1)\)

We are given:

\(h_i = 2^{x_i} \bmod p\)

So

\(h_{i+1} = 2^{x_{i+1}} \bmod p = 2^{256x_i-b_i(256^n-1)} \bmod p = h_i^{256}\times2^{-b_i(256^n-1)} \bmod p\)

Since \(b_i\) is a byte (0-255), we can brute force it. Attack script:

import math

# Parse the data from out.txt
p = 105891552782768273485439811488443354235545023673195353053856843893816480862271
leaks = [
    74834831693148489075053741970537349864361072646438063822128523522624111096404,
    94637262384206414487913618520407895315549149001067603290715492338419957063638,
    26119415647812686814124878968032828750956202141747974248626227495752618826310,
    4679774184271053791528196045893972569586759227111353536533198888487507918565,
    18247264710550364407701539407739806326963229364366084285259750379893601861765,
    57915316904508068959154652733100932636576891111709785240327600448742235657223,
    48726379408397107751482798948037834170753506073391626907440435722452593080790,
    23985113650578780235980433910057970681859494895610853985857472866552793069375,
    79231016211481853602891211467430186947199626871048819648312025046281485147965,
    1741002057862179063516105232753064091765321308410446556962767548042727938590,
    45723548930603031191234669145592632467258468694483505689072179691228438466667,
    58359671511194341930052508512801343119287048085288142869480583778613556216586,
    36424897628935082604512568766716569943269039796337573854278402880102811617963,
    74124749341279711257845847090110538409556405630352757105373182076739304300759,
    66309699088883552645305984224828051437638962884903042514430099711503266344026,
    3162806651485565481013375199103880408462676315825209573632289159416883750178,
    38582718538740737041784799604514668813686704870272183643601445048856770639975,
    60816150467494956825800367310063997854145812297158134406617773585762215516843,
    12353526085228982771214476339845069964525380861405349768474892062968628975241,
    105582281937486445268146775233874434792742700624750876452894760571703935174919,
    13238662997179930853908762356537888264584682314391321882412877512234731316348,
    75875040959123636492014257513993145046661183624855640826292741601485403285328,
    12149947150174642792165286320748309835337741992502616190760701133669565860666,
    38650263185329843052214216132708910216830022007692554045491912295950867554552,
    92561547647296020081423003558701351791204280991353765906671600253604516771598,
    41349557324733447344437570514434312589869408427300508224464407246422794992797,
    86385180739170312287865404316483035605934760491085055759657242983443484861082,
    39348401982172687025128116440936094277482944374061555213943911942008513049037,
    58273481812023054183980778217247474508696785731672888895966172242039774561634,
    69932445711823749013619544296257448424270930795659726110506648765574551496961,
    11196151841801624492550269516119227591456953234837751240484968196644961160377,
    26041577455573938646072969268840197244828691423833869416465901173451675328995
]

n = len(leaks)  # FLAG length = 32

def mod_inverse(a, m):
    # Extended Euclidean Algorithm
    def egcd(a, b):
        if b == 0:
            return (1, 0, a)
        else:
            x, y, g = egcd(b, a % b)
            return (y, x - (a // b) * y, g)

    x, y, g = egcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % m

def mod_pow(a, b, m):
    return pow(a, b, m)

# Compute: R_i = h_i^{256} * h_{i+1}^{-1} mod p
# This should equal 2^{b_i * (256^n - 1)} mod p
print("Computing R_i = h_i^{256} * h_{i+1}^{-1} mod p")
print("This should equal 2^{b_i * (256^n - 1)} mod p")
print()

R_values = []
for i in range(n-1):
    h_i_pow_256 = mod_pow(leaks[i], 256, p)
    h_i1_inv = mod_inverse(leaks[i+1], p)
    R_i = (h_i_pow_256 * h_i1_inv) % p
    R_values.append(R_i)
    print(f"R_{i} = {R_i}")

print("\n" + "="*80)
print("Now, note that R_i = 2^{b_i * (256^n - 1)} mod p")
print(f"Where n = {n}, so 256^n - 1 = 256^{n} - 1")
print()

# Compute K = 256^n - 1
K = pow(256, n) - 1
print(f"K = 256^{n} - 1 = {K}")
print()

# So we have: R_i = 2^{b_i * K} mod p = (2^K)^{b_i} mod p
# Let's compute base = 2^K mod p
base = mod_pow(2, K, p)
print(f"base = 2^K mod p = {base}")
print()

# Now we need to find b_i such that base^{b_i} mod p = R_i
# Since b_i are bytes (0-255), we can brute force!
print("Brute forcing b_i values (0-255) for all R_i:")
possible_b = []
for i, R_i in enumerate(R_values):
    found = False
    for b in range(256):
        if mod_pow(base, b, p) == R_i:
            print(f"  R_{i:2d}: found b={b:3d} (chr='{chr(b) if 32 <= b < 127 else ' '}')")
            possible_b.append(b)
            found = True
            break
    if not found:
        print(f"  R_{i}: No b found in range 0-255")
        possible_b.append(None)

print("\nAll possible bytes:", possible_b)
flag_chars = ''.join(chr(b) if b is not None and 32 <= b < 127 else '?' for b in possible_b)
print("As characters:", flag_chars)
print("Length:", len(flag_chars))

# We have n-1 bytes from the ratios, we need the last byte
# The FLAG has length n = 32, and we have bytes b0 through b30 from the ratios
# We need b31. We can get it from the fact that the rotation wraps around.

# Let's try to reconstruct the full flag
# We have: b0, b1, ..., b30 from the ratios
# We need b31. We can use the relationship for the last rotation:
# h_{31} = 2^{x_{31}} where x_{31} is FLAG rotated 31 times
# This should give us b31

print("\n" + "="*80)
print("Attempting to recover the full flag...")

# We have bytes b0..b30, let's try to find b31
# From the rotation formula: x_{i+1} = 256 * x_i - b_i * (256^n - 1)
# We know all b_i for i=0..30, and we know h_0 = 2^{x_0}
# We can try to compute x_0 from h_0 by solving discrete log, but that's hard
# Instead, let's use the fact that we have h_31 and the relationship should hold

# Actually, we have a cyclic relationship. After n rotations, we're back to the original:
# x_n = x_0
# So: x_n = 256^n * x_0 - (sum_{i=0}^{n-1} b_i * 256^{n-1-i}) * (256^n - 1) / (256 - 1)
# This is getting complex...

# Simpler: We have the bytes in order from the ratios: b0, b1, ..., b30
# The flag should be: b0 b1 ... b30 b31
# And from the rotation, b31 should be such that when we compute R_31 = h_31^{256} * h_0^{-1} mod p
# we get base^{b31}

# Compute R_31 (wrapping around)
h_31_pow_256 = mod_pow(leaks[31], 256, p)
h_0_inv = mod_inverse(leaks[0], p)
R_31 = (h_31_pow_256 * h_0_inv) % p
print(f"R_31 = {R_31}")

# Find b31
found_b31 = None
for b in range(256):
    if mod_pow(base, b, p) == R_31:
        found_b31 = b
        print(f"Found b31 = {b} (chr='{chr(b) if 32 <= b < 127 else ' '}')")
        break

if found_b31 is not None:
    full_bytes = possible_b + [found_b31]
    flag = ''.join(chr(b) if b is not None and 32 <= b < 127 else '?' for b in full_bytes)
    print(f"\nFull flag ({len(flag)} chars): {flag}")
else:
    print("Could not find b31")

NOTE: this attack is done by DeepSeek.