Skip to content

Instantly share code, notes, and snippets.

@shilch
Created November 1, 2020 22:10
Show Gist options
  • Save shilch/43488fe4f8cddda25f953fb4ef53911f to your computer and use it in GitHub Desktop.
Save shilch/43488fe4f8cddda25f953fb4ef53911f to your computer and use it in GitHub Desktop.
Solution for Cyber Security Rumble CTF 2020 - Pady McPadface
#!/usr/bin/env python3
from pwn import *
n = 23946008544227658126007712372803958643232141489757386834260550742271224503035086875887914418064683964046938371640632153677880813529023769841157840969433316734058706481517878257755290676559343682013294580085557476138201639446709290119631383493940405818550255561589074538261117055296294434994144540224412018398452371792093095280080422459773487177339595746894989682038387107119249733105558301840478252766907821053044992141741079156669562032221433390029219634673005161989684970682781410366155504440886376453225497112165607897302209008685179791558898003720802478389914297472563728836647547791799771532020349546729665006643
def get_ciphertexts():
conn = remote('chal.cybersecurityrumble.de', 34187)
while (conn.recvline()) != b'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n':
pass
conn.recvline();
conn.recvline();
ciphertexts = []
while True:
try:
ciphertexts += [int(conn.recvline(), 10)]
except EOFError:
break
return ciphertexts
threshold = 20
ciphertexts = []
for i in range(0, threshold):
ciphertexts += [get_ciphertexts()]
# Source: https://rosettacode.org/wiki/Jacobi_symbol#Python
def jacobi(a, n):
if n <= 0:
raise ValueError("'n' must be a positive integer.")
if n % 2 == 0:
raise ValueError("'n' must be odd.")
a %= n
result = 1
while a != 0:
while a % 2 == 0:
a //= 2
n_mod_8 = n % 8
if n_mod_8 in (3, 5):
result = -result
a, n = n, a
if a % 4 == 3 and n % 4 == 3:
result = -result
a %= n
if n == 1:
return result
else:
return 0
bitstring = '0'
for i in range(0, len(ciphertexts[0])):
one = False
for t in range(0, threshold):
if jacobi(ciphertexts[t][i], n) == -1:
one = True
break
if one:
bitstring += '1'
else:
bitstring += '0'
def decode_binary_string(s):
return ''.join(chr(int(s[i*8:i*8+8],2)) for i in range(len(s)//8))
print(decode_binary_string(bitstring))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment