ASIS CTF 2022
Binned
“People binned to the same public ID have no real-world connection to one another.”
#!/usr/bin/env python3
from Crypto.Util.number import *
from gensafeprime import *
from flag import flag
def keygen(nbit):
p, q = [generate(nbit) for _ in range(2)]
return (p, q)
def encrypt(m, pubkey):
return pow(pubkey + 1, m, pubkey ** 3)
p, q = keygen(512)
n = p * q
flag = bytes_to_long(flag)
enc = encrypt(flag, n)
print(f'pubkey = {n}')
print(f'enc = {enc}')
"""
pubkey = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160
"""
Solve:
\[enc \equiv (n+1)^m \ (mod \ n^3)\]Taking the binomial mod n^3 eliminates all terms with factors divisible by n^3, leaving just:
\[enc = {^mC_2} \cdot n^2 + mn + 1\]Now there are two approaches. The first is to solve this quadratic:
\[enc = \frac{m!}{2 (m-2)!} \cdot n^2 + mn + 1\] \[enc = \frac{m(m-1)(m-2!)}{2(m-2!)} \cdot n^2 + m n + 1\] \[enc = \frac{m(m-1)}{2} \cdot n^2 + mn + 1\]from Crypto.Util.number import long_to_bytes
n = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160
m = var('m')
f = m*(m-1)/2 * n**2 + m * n + 1
f -= enc
m = f.roots()[1][0]
print(long_to_bytes(int(m)))
The second approach is to take mod n^2 on both sides, removing the mC2 n^2 term:
\[enc = {^mC_2} \cdot n^2 + mn + 1\] \[enc \equiv m n + 1 \ (mod \ n^2)\] \[enc - 1 \equiv mn \ (mod \ n^2)\]Then we can ignore mod n^2 on RHS because mn < n^2
\[(enc - 1) \ (mod \ n^2) = mn\] \[m = \frac{(enc - 1) \ (mod \ n^2)}{n}\]from Crypto.Util.number import long_to_bytes
n = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160
m = ((enc - 1) % (n ** 2)) // n
print(long_to_bytes(m))
Mindseat
“Cryptography Mindset: Be Unpredictable, build robust and stable applications where you’ll handle every situation that user can face or predict.”
#!/usr/bin/env python3
from Crypto.Util.number import *
from secret import params, flag
def keygen(nbit, k): # Pubkey function
_p = 1
while True:
p, q = [_p + (getRandomNBitInteger(nbit - k) << k) for _ in '01']
if isPrime(p) and isPrime(q):
while True:
s = getRandomRange(2, p * q)
if pow(s, (p - 1) // 2, p) * pow(s, (q - 1) // 2, q) == (p - 1) * (q - 1):
pubkey = p * q, s
return pubkey
def encrypt(pubkey, m):
n, s = pubkey
r = getRandomRange(2, n)
return pow(s, m, n) * pow(r, 2 ** k, n) % n
flag = flag.lstrip(b'ASIS{').rstrip(b'}')
nbit, k = params
PUBKEYS = [keygen(nbit, k) for _ in range(4)]
flag = [bytes_to_long(flag[i*8:i*8 + 8]) for i in range(4)]
ENCS = [encrypt(PUBKEYS[_], flag[_]) for _ in range(4)]
print(f'PUBKEYS = {PUBKEYS}')
print(f'ENCS = {ENCS}')
"""
PUBKEYS = [(10342840547250370454282840290754052390564265157174829726645242904324433774727630591803186632486959590968595230902808369991240437077297674551123187830095873, 5179654005441544601140101875149402241567866059199512232495766031194848985776186595289740052214499657697650832860279375151687044465018028876445070588827777), (6015512135462554031390611730578383462516861987731833360559070749140159284050335604168414434218196369921956160353365713819898567416920672209509202941444097, 2116441415129068001049624780654272734931672052541246678702416144768611225693039503554945326959705314527114860312641379671935648337975482830939466425225421), (6396980904648302374999086102690071222661654639262566535518341836426544747072554109709902085144158785649143907600058913175220229111171441332366557866622977, 1760317994074087854211747561546045780795134924237097786412713825282874589650448491771874326890983429137451463523250670379970999252639812107914977960011738), (9158217300815233129401608406766983222991414185115152402477702381950519098200234724856258589693986849049556254969769863821366592458050807400542885348638721, 6564146847894132872802575925374338252984765675686108816080170162797938388434600448954826704720292576935713424103133182090390089661059813982670332877677256)]
ENCS = [4595268033054096192076432659360373235610019564489694608733743330870893803828258295069937060360520598446948290913045781945314108935153236291467160667601985, 3390637292181370684803039833768819598968576813582112632809296088618666221278429695211004046274005776653775480723833818255766663573061866194380012311184611, 5197599582013327040903216369733466147938613487439777125659892779696104407398257678982801768761973934713675657188014051286238194316997970299887749668838196, 5093835186720390391696398671365109925058893544530286148616117890366909889206952477053316867658405460457795493886317792695055944930027477761411273933822112]
"""
First step is to approximate k:
\[p = x\cdot 2^k+1\]>>> n = 10342840547250370454282840290754052390564265157174829726645242904324433774727630591803186632486959590968595230902808369991240437077297674551123187830095873
>>> bin(n)
'0b11000101011110101100000001100010100010000010100111001101011001111111011011100010010101101000110111011011010011001100001100000001110001010001011011101110100111110001001000010100101101001100010011011100110101000011111000011000100101000110001101000000000000011100001010001111110101100000100011111100111011110000000100010100101111110101111010110001110001100100001001101000111100110100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001'
>>> len('00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001')
134
n is 512 bits, so p and q are 256 bits.
Next we factor n with Coppersmith’s method:
n = 10342840547250370454282840290754052390564265157174829726645242904324433774727630591803186632486959590968595230902808369991240437077297674551123187830095873
PR.<x> = PolynomialRing(Zmod(n))
f = x * 2**134 + 1
x = f.monic().small_roots(X=2**(256 - 134), beta=0.4)[0]
p = int(f(x))
q = n//p
assert p*q == n
Now we have a discrete log problem to solve:
def encrypt(pubkey, m):
n, s = pubkey
r = getRandomRange(2, n)
return pow(s, m, n) * pow(r, 2 ** k, n) % n
We can solve in similar fashion to https://connor-mccartney.github.io/cryptography/diffie-hellman/logloglog-Angstrom-CTF-2022:
\[enc \equiv s^m \cdot r^{2^k} \ (mod \ p)\] \[{enc}^{\frac{p-1}{2^k}} \equiv ({s}^{\frac{p-1}{2^k}})^m \cdot (r^{2^k\cdot \frac{p-1}{2^k}}) \ (mod \ p)\] \[{enc}^{\frac{p-1}{2^k}} \equiv ({s}^{\frac{p-1}{2^k}})^m \cdot r^{p-1} \ (mod \ p)\] \[{enc}^{\frac{p-1}{2^k}} \equiv ({s}^{\frac{p-1}{2^k}})^m \ (mod \ p)\](The r^(p-1) disappears because of Fermat’s Little Theorem)
from sympy.ntheory.residue_ntheory import _discrete_log_pohlig_hellman
from Crypto.Util.number import long_to_bytes
enc = 4595268033054096192076432659360373235610019564489694608733743330870893803828258295069937060360520598446948290913045781945314108935153236291467160667601985
s = 5179654005441544601140101875149402241567866059199512232495766031194848985776186595289740052214499657697650832860279375151687044465018028876445070588827777
p = 95553042292789874700903619680433024548766742921219411688127033417325711720449
_s = pow(s, (p-1)//2**134, p)
_enc = pow(enc, (p-1)//2**134, p)
m = _discrete_log_pohlig_hellman(p, _enc, _s)
print(long_to_bytes(m))
Now repeat for the other sections:
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.residue_ntheory import _discrete_log_pohlig_hellman
PUBKEYS = [(10342840547250370454282840290754052390564265157174829726645242904324433774727630591803186632486959590968595230902808369991240437077297674551123187830095873, 5179654005441544601140101875149402241567866059199512232495766031194848985776186595289740052214499657697650832860279375151687044465018028876445070588827777), (6015512135462554031390611730578383462516861987731833360559070749140159284050335604168414434218196369921956160353365713819898567416920672209509202941444097, 2116441415129068001049624780654272734931672052541246678702416144768611225693039503554945326959705314527114860312641379671935648337975482830939466425225421), (6396980904648302374999086102690071222661654639262566535518341836426544747072554109709902085144158785649143907600058913175220229111171441332366557866622977, 1760317994074087854211747561546045780795134924237097786412713825282874589650448491771874326890983429137451463523250670379970999252639812107914977960011738), (9158217300815233129401608406766983222991414185115152402477702381950519098200234724856258589693986849049556254969769863821366592458050807400542885348638721, 6564146847894132872802575925374338252984765675686108816080170162797938388434600448954826704720292576935713424103133182090390089661059813982670332877677256)]
ENCS = [4595268033054096192076432659360373235610019564489694608733743330870893803828258295069937060360520598446948290913045781945314108935153236291467160667601985, 3390637292181370684803039833768819598968576813582112632809296088618666221278429695211004046274005776653775480723833818255766663573061866194380012311184611, 5197599582013327040903216369733466147938613487439777125659892779696104407398257678982801768761973934713675657188014051286238194316997970299887749668838196, 5093835186720390391696398671365109925058893544530286148616117890366909889206952477053316867658405460457795493886317792695055944930027477761411273933822112]
flag = b""
for (n, s), enc in zip(PUBKEYS, ENCS):
PR.<x> = PolynomialRing(Zmod(n))
f = 1 + x * 2**133
x = f.monic().small_roots(X=2**128, beta=0.4)[0]
p = int(f(x))
_s = pow(s, (p-1)//2**134, p)
_enc = pow(enc, (p-1)//2**134, p)
m = _discrete_log_pohlig_hellman(p, _enc, _s)
flag += long_to_bytes(m)
print(flag)
Mariana
“Mariana works in the areas of cryptography and security. But some flaws exists in her work!”
#!/usr/bin/env python3
from Crypto.Util.number import *
import sys
from flag import flag
def die(*args):
pr(*args)
quit()
def pr(*args):
s = " ".join(map(str, args))
sys.stdout.write(s + "\n")
sys.stdout.flush()
def sc():
return sys.stdin.buffer.readline()
def main():
border = "|"
pr(border*72)
pr(border, "Welcome to MARIANA cryptography battle, the mission is solving super", border)
pr(border, "hard special DLP problem in real world, are you ready to fight? ", border)
pr(border*72)
NBIT = 32
STEP = 40
pr(border, "In each step solve the given equation and send the solution for x. ", border)
c = 1
while c <= STEP:
nbit = NBIT * c
p = getPrime(nbit)
g = getRandomRange(3, p)
pr(border, f'p = {p}')
pr(border, f'g = {g}')
pr(border, 'Send the solution x = ')
ans = sc()
try:
x = int(ans)
except:
die(border, 'Given number is not integer!')
if x >= p:
die(border, "Kidding me!? Your solution must be smaller than p :P")
if (pow(g, x, p) - x) % p == 0:
if c == STEP:
die(border, f"Congratz! the flag is: {flag}")
else:
pr(border, "Good job, try to solve the next level!")
c += 1
else:
die(border, "Try harder and smarter to find the solution!")
if __name__ == '__main__':
main()
We have to solve:
\[g^x = x \ (mod \ p)\]Euler’s totient theorem states that when a is coprime to N,
\[a^{\phi(N)} \equiv 1 \ (mod \ N)\]For prime N, we have:
\[a^{p-1} \equiv 1 \ (mod \ p)\]Now the trick is to send x=1-p
\[g^{x} \equiv g^{1 - p} \equiv g^{-(p-1)} \equiv ({g^{p-1}})^{-1} \equiv (1)^{-1} \equiv 1 \equiv 1-p\ \equiv x \ (mod\ p)\]Alternative solution:
\[g^x \equiv x \ (mod \ p)\] \[g \equiv x^{x^{-1} \ (mod\ p-1)} \ (mod \ p)\] \[\text{Let}\ x^{-1} \ (mod\ p-1) = 1\] \[\text{Then } x \equiv 1 \ (mod\ p-1) \text{ and } x \equiv g\ (mod\ p )\]These can be solved with CRT (mod p(p-1)), then you can subtract p(p-1) to pass the check x<p.
x = crt([1, g], [p-1, p]) - p*(p-1)