DownUnderCTF Crypto Write-Ups

I played DownUnderCTF as a member of Defenit, and solved all cryptography problems. 

rot-i

Ypw'zj zwufpp hwu txadjkcq dtbtyu kqkwxrbvu! Mbz cjzg kv IAJBO{ndldie_al_aqk_jjrnsxee}. Xzi utj gnn olkd qgq ftk ykaqe uei mbz ocrt qi ynlu, etrm mff'n wij bf wlny mjcj :).
 

The problem seems to imply a variant of rotation cipher. Now, it's reasonable to guess that "Mbz cjzg kv IAJBO" is actually "The flag is DUCTF". We subtract the alphabet order of each text to find that the "amount of rotation" changes by 1 each time. 

I changed all letters into lowercase, cleaned up some parts of the string, and wrote the following code.

t = 'ypw zj zwufpp hwu txadjkcq dtbtyu kqkwxrbvu! mbz cjzg kv iajbo{ndldie_al_aqk_jjrnsxee}. xzi utj gnn olkd qgq ftk ykaqe uei mbz ocrt qi ynlu, etrm mffn wij bf wlny mjcj :'
u = 'the flag is ductf'
v = 'mbz cjzg kv iajbo'
 
for i in range(0, 26):
    s = ""
    st = i
    for j in range(len(t)):
        if ord('a') <= ord(t[j]) <= ord('z'):
            cc = chr(ord('a') + (ord(t[j]) - ord('a') + st) % 26)
            s += cc
        else:
            s += t[j]
        st = st - 1
    print(s)

babyrsa

from Crypto.Util.number import bytes_to_long, getPrime
 
flag = open('flag.txt', 'rb').read().strip()
p, q = getPrime(1024), getPrime(1024)
n = p*q
e = 0x10001
s = pow(557*p - 127*q, n - p - q, n)
c = pow(bytes_to_long(flag), e, n)
print(f'n = {n}')
print(f's = {s}')
print(f'c = {c}')

The extra information we have here is $s$. Since $n-p-q = \phi(n) - 1$, we see that $s$ is the modular inverse of $557p - 127q$ $\pmod{n}$. Therefore, we may recover $557p-127q \equiv s^{-1} \pmod{n}$ with Extended Euclidean algorithm. Since $557p - 127q$ is between $0$ and $n$, we can just recover $557p-127q$. Since we already know $n = pq$, we can just solve a quadratic equation. I did it with a binary search.

n = 19574201286059123715221634877085223155972629451020572575626246458715199192950082143183900970133840359007922584516900405154928253156404028820410452946729670930374022025730036806358075325420793866358986719444785030579682635785758091517397518826225327945861556948820837789390500920096562699893770094581497500786817915616026940285194220703907757879335069896978124429681515117633335502362832425521219599726902327020044791308869970455616185847823063474157292399830070541968662959133724209945293515201291844650765335146840662879479678554559446535460674863857818111377905454946004143554616401168150446865964806314366426743287
s = 3737620488571314497417090205346622993399153545806108327860889306394326129600175543006901543011761797780057015381834670602598536525041405700999041351402341132165944655025231947620944792759658373970849932332556577226700342906965939940429619291540238435218958655907376220308160747457826709661045146370045811481759205791264522144828795638865497066922857401596416747229446467493237762035398880278951440472613839314827303657990772981353235597563642315346949041540358444800649606802434227470946957679458305736479634459353072326033223392515898946323827442647800803732869832414039987483103532294736136051838693397106408367097
c = 7000985606009752754441861235720582603834733127613290649448336518379922443691108836896703766316713029530466877153379023499681743990770084864966350162010821232666205770785101148479008355351759336287346355856788865821108805833681682634789677829987433936120195058542722765744907964994170091794684838166789470509159170062184723590372521926736663314174035152108646055156814533872908850156061945944033275433799625360972646646526892622394837096683592886825828549172814967424419459087181683325453243145295797505798955661717556202215878246001989162198550055315405304235478244266317677075034414773911739900576226293775140327580
e = 65537 
 
tt = inverse(s, n)
lef = 2 ** 1023
rig = 2 ** 1025
while lef <= rig:
    mid = (lef + rig) // 2
    p = mid 
    q = (557 * p - tt) // 127
    if p * q >= n:
        best = mid
        rig = mid - 1
    else:
        lef = mid + 1
p = best 
q = (557 * best - tt) // 127
phi = (p-1) * (q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)))

Extra Cool Block Chaining

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.strxor import strxor
from os import urandom
 
flag = open('./flag.txt', 'rb').read().strip()
KEY = urandom(16)
IV = urandom(16)
 
def encrypt(msg, key, iv):
    msg = pad(msg, 16)
    blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
    out = b''
    for i, block in enumerate(blocks):
        cipher = AES.new(key, AES.MODE_ECB)
        enc = cipher.encrypt(block)
        if i > 0:
            enc = strxor(enc, out[-16:])
        out += enc
    return strxor(out, iv*(i+1))
 
def decrypt(ct, key, iv):
    blocks = [ct[i:i+16] for i in range(0, len(ct), 16)]
    out = b''
    for i, block in enumerate(blocks):
        dec = strxor(block, iv)
        if i > 0:
            dec = strxor(dec, ct[(i-1)*16:i*16])
        cipher = AES.new(key, AES.MODE_ECB)
        dec = cipher.decrypt(dec)
        out += dec
    return out
 
flag_enc = encrypt(flag, KEY, IV).hex()
 
print('Welcome! You get 1 block of encryption and 1 block of decryption.')
print('Here is the ciphertext for some message you might like to read:', flag_enc)
 
try:
    pt = bytes.fromhex(input('Enter plaintext to encrypt (hex): '))
    pt = pt[:16] # only allow one block of encryption
    enc = encrypt(pt, KEY, IV)
    print(enc.hex())
except:
    print('Invalid plaintext! :(')
    exit()
 
try:
    ct = bytes.fromhex(input('Enter ciphertext to decrypt (hex): '))
    ct = ct[:16] # only allow one block of decryption
    dec = decrypt(ct, KEY, IV)
    print(dec.hex())
except:
    print('Invalid ciphertext! :(')
    exit()
 
print('Goodbye! :)')

Let's first consider what the encryption function is actually doing. Given a plaintext $P_1 P_2 \cdots P_n$, we are basically doing $C_i = E_K(P_i) \oplus C_{i-1}$ for each $i$, then XORing the $IV$ to all ciphertexts before returning. In other words, we are just sending $IV \oplus E_K(P_1), IV \oplus E_K(P_1) \oplus E_K(P_2)$, $\cdots , IV \oplus E_K(P_1) \oplus \cdots \oplus E_K(P_n)$. 

Now what we can do is ask for an encryption of a single block, and a decryption of a single block. 

Say we want to find $P_k$. To do so, we need to ask for a decryption of $IV \oplus E_K(P_k)$. How do we find that? 

Note that this is trivial for $k=1$. Assume $k \ge 2$. Now, by XORing the two consecutive results of the output, we can easily get $E_K(P_k)$. Therefore, we need to find a way to get $IV$. This looks like a time for encryption oracle. 

Note that if $P_1 = P_2$, our second output will be $IV \oplus E_K(P_1) \oplus E_K(P_2) = IV$. 

We want to use this to our benefit, but we can only ask for one block! It's okay, because we can abuse the padding. 

By asking for the encryption of b'\x10' * 16, we can make our padded plaintext of the form $P_1 P_1$. 

This enables us to get $IV$, and we can decrypt each block as we want. I did this manually, so code below is not perfect.

cc = 'Here is the ciphertext for some message you might like to read: '
print(conn.recvline())
T = conn.recvline()
print(T)
hxval = T[len(cc):-1]
hxval = hxval.decode()
print(len(hxval))
conn.send((b'\x10' * 16).hex() + "\n")
T = conn.recvline()
cc = "Enter plaintext to encrypt (hex): "
print(T)
IV = T[len(cc):-1]
print(IV)
IV = IV.decode()
IV = bytes.fromhex(IV)
IV = IV[-16:]
## change indexes to find different blocks (below)
conn.send((strxor(bytes.fromhex(hxval[160:192]), strxor(bytes.fromhex(hxval[128:160]), IV))).hex() + "\n") 
print(conn.recvline()) ## change hex -> bytes here

ceebc

#!/usr/bin/env python3
from os import urandom
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import constant_time
from cryptography.hazmat.backends import default_backend
 
backend = default_backend()
key = urandom(32)
solution_message = b'flagflagflagflag'
 
def CBC_MAC(key, message, iv):
    if len(message) != 16 or len(iv) != 16:
        raise ValueError('Only messages/IVs of size 16 are allowed!')
    cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=backend)
    enc = cipher.encryptor()
    return enc.update(message) + enc.finalize()
 
def sign(message, iv):
    return CBC_MAC(key, message, iv) + iv
 
def verify(message, signature):
    iv = signature[16:]
    computed_sig = sign(message, iv)
    return constant_time.bytes_eq(signature, computed_sig)
 
sample = b'cashcashcashcash'
print('Hey there, have a message {} and its signature {}!'.format(
      sample.decode('utf-8'), sign(sample, urandom(16)).hex()
      ))
 
received_message = input('Now give me your message: ').encode('utf-8')
try:
    received_signature = bytes.fromhex(input('Now the signature (in hex): '))
except ValueError:
    print('Signature was not in hex!')
    exit()
 
try:
    valid = verify(received_message, received_signature)
except ValueError as e:
    print(e)
    exit()
 
if valid:
    print('Signature valid!')
 
    if received_message == solution_message:
        print(open('flag.txt').read())
    else:
        print('Phew! Good thing the message isn\'t {}!'
              .format(solution_message.decode('utf-8')))
else:
    print('Invalid signature!')
 

We are given a signature of an known example message, and we have to forge a signature of a desired message.

The signature is given by $E_{K, IV}^{CBC} (P) || IV$ which is just $E_{K}^{ECB} (P \oplus IV) || IV$.

So we have $IV$, $E_{K}^{ECB}(P_{ex} \oplus IV)$, and $P_{ex}$. We want to forge a signature of $P_{flag}$. 

To do so, calculate $IV'$ such that $P_{ex} \oplus IV = P_{flag} \oplus IV'$. This can be easily done.

Then simply send $P_{K}^{ECB} (P_{ex} \oplus IV) || IV'$ as a signature. It's clear that this works. 

T = conn.recvline()
cc = 'Hey there, have a message cashcashcashcash and its signature '
SIG = T[len(cc) : -2]
SIG = bytes.fromhex(SIG.decode())
INC = SIG[0:16]
IV = SIG[16:32]
ms = b'cashcashcashcash'
goal = "flagflagflagflag"
conn.send(goal + "\n")
TT = INC + bytexor(ms, bytexor(IV, goal.encode()))
conn.send(TT.hex() + "\n")
print(conn.recvline())
conn.send(TT.hex() + "\n")
print(bytes.fromhex(TT.hex()))
print(conn.recvline())
print(conn.recvline())

Hex Shift Cipher

from random import shuffle
from secret import secret_msg
 
ALPHABET = '0123456789abcdef'
 
class Cipher:
    def __init__(self, key):
        self.key = key
        self.n = len(self.key)
        self.s = 7
 
    def add(self, num1, num2):
        res = 0
        for i in range(4):
            res += (((num1 & 1) + (num2 & 1)) % 2) << i
            num1 >>= 1
            num2 >>= 1
        return res
 
    def encrypt(self, msg):
        key = self.key
        s = self.s
        ciphertext = ''
        for m_i in msg:
            c_i = key[self.add(key.index(m_i), s)]
            ciphertext += c_i
            s = key.index(m_i)
        return ciphertext
 
plaintext = b'The secret message is:'.hex() + secret_msg.hex()
 
key = list(ALPHABET)
shuffle(key)
 
cipher = Cipher(key)
ciphertext = cipher.encrypt(plaintext)
print(ciphertext)
 
# output:
# 85677bc8302bb20f3be728f99be0002ee88bc8fdc045b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a
 

It's simple to see that the 'add' function is just XOR. We will brute force the key by backtracking. 

Basically, with the known parts of the plaintext, we have pieces of information like $key(key^{-1}(m_i) \oplus s) = c_i$. 

If $key^{-1}(m_i)$ are known, then we can figure out $key^{-1}(c_i)$ and vice-versa.

If this information is contradictory to the previous assumption of our key, we can stop the backtracking.

If we have no idea on $key^{-1}(m_i)$ and $key^{-1}(c_i)$, we can brute force what their value will be. 

If we have the complete key, it's straightforward to decrypt the given output. Select those that can be cleanly decrypted.

Also, now we can obviously see what the "linear algebra solution" is. Seems like a lot of work to be honest...

My code seems to have a few buggy pieces, but it got the job done so I didn't bother to fix it.

def fr(x):
    if 0 <= x and x <= 9:
        return chr(ord('0') + x)
    return chr(ord('a') + x - 10)
 
def cv(x):
    if ord('0') <= ord(x) <= ord('9'):
        return ord(x) - ord('0')
    else:
        return ord(x) - ord('a') + 10
 
def finisher(key, s):
    ct = 'b80e1dd22bc8fcc0034dd809e8f77023fbc83cd02ec8fbb11cc02cdbb62837677bc8f2277eeaaaabb1188bc998087bef3bcf40683cd02eef48f44aaee805b8045453a546815639e6592c173e4994e044a9084ea4000049e1e7e9873fc90ab9e1d4437fc9836aa80423cc2198882a'
    pt = ""
    for i in range(len(ct)):
        ot = cv(ct[i])
        myidx = key.index(ot) ^ s
        m_i = key[myidx]
        pt += fr(m_i)
        s = myidx
    print(bytes.fromhex(pt))
 
def solve(key, s, res, cts, idx):
    if idx == len(res):
        # print("found", key, s)
        finisher(key, s)
        return
    p = cv(res[idx])
    q = cv(cts[idx])
    ## key[index(p) ^ s] == q
    if p in key:
        if key[key.index(p) ^ s] != -1 and key[key.index(p) ^ s] != q:
            return
        it = key.index(p) ^ s
        key[it] = q 
        solve(key, key.index(p), res, cts, idx+1)
        key[it] = -1
    if q in key:
        it = key.index(q) ^ s
        if key[it] != -1 and key[it] != p:
            return
        key[it] = p
        solve(key, key.index(p), res, cts, idx+1)
        key[it] = -1
    for i in range(0, 16):
        if key[i] == -1 and key[i ^ s] == -1:
            key[i] = p
            key[i ^ s] = q
            solve(key, key.index(p), res, cts, idx+1)
            key[i] = -1
            key[i ^ s] = -1
 
res = '54686520736563726574206d6573736167652069733a'
cts = '85677bc8302bb20f3be728f99be0002ee88bc8fdc045'
 
key = [-1] * 16
s = 7
solve(key, s, res, cts, 0)

Cosmic Rays

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from Crypto.Util.strxor import strxor
from os import urandom
 
flag = open('flag.txt', 'rb').read().strip()
flag = flag.lstrip(b'DUCTF{').rstrip(b'}')
assert len(flag) == 32
 
KEY = urandom(16)
 
def encrypt(msg, key, p0, c0):
    msg = pad(msg, 16)
    blocks = [msg[i:i+16] for i in range(0, len(msg), 16)]
 
    out = b''
 
    for p in blocks:
        c = strxor(p, c0)
        c = AES.new(key, AES.MODE_ECB).encrypt(c)
 
        out += strxor(p0, c)
 
        c0 = c
        p0 = p
 
    return out
 
msg = 'If Bruce Schneier multiplies two primes, the product is prime. On a completely unrelated note, the key used to encrypt this message is ' + KEY.hex()
ciphertext = encrypt(msg.encode(), KEY, flag[16:], flag[:16])
 
print('key = ' + KEY.hex())
print('ciphertext = ' + ciphertext.hex())

## ke▒ = 0▒9d0fe1920ca▒85e3851b162b8cc9▒5
## ci▒her▒ext = ed5dd65ef5ac36e886830cf006359b300▒1▒▒7▒▒▒▒▒▒c▒▒▒▒▒a▒▒▒▒▒8▒▒▒▒▒▒▒d6▒▒▒▒▒7▒▒▒▒b▒▒▒▒2▒▒▒▒▒▒▒▒▒f▒d▒0▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒6▒▒▒▒▒▒▒▒▒▒▒▒▒f▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒d▒▒b▒▒▒a▒▒▒▒▒e▒▒c▒▒▒▒▒2▒▒▒▒▒▒▒▒▒▒0▒▒3▒0c▒▒f▒▒▒▒▒▒▒▒▒▒▒▒1▒▒7▒▒▒▒▒▒▒▒▒▒▒▒▒1e▒▒0▒0▒▒▒▒▒9▒▒c▒▒e▒▒2▒▒4▒▒▒▒7▒▒▒▒▒0▒▒▒▒▒4▒▒▒▒▒▒▒▒f▒▒▒7▒▒▒▒▒e▒b▒▒9▒▒▒▒4▒f▒▒1▒c▒▒6▒0a▒3a0e6▒d7▒975d▒1cde66e41791b▒780988c9b8329


 

Let's analyze the encryption process first. Given the padded message $P_1 P_2 \cdots P_n$, we see that $C_i = E_K(P_i \oplus C_{i-1})$, and the $i$th output block is $O_i = C_i \oplus P_{i-1}$. Since the key bytes and the latter parts of the output are quite known, we will start by figuring them all out. There are five unknowns in the hex data of the key and the final block (32 hex digits) of the output. We brute-force all $2^{20}$ combinations. How do we verify correctness? Since $C_n = O_n \oplus P_{n-1} = E_K(P_n \oplus C_{n-1})$, we see that $O_{n-1} = C_{n-1} \oplus P_{n-2} = D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. We know partial outputs of $O_{n-1}$, so we compare the known values of $O_{n-1}$ and $D_K(O_n \oplus P_{n-1}) \oplus P_n \oplus P_{n-2}$. Turns out that this is enough to uniquely determine all five unknowns. 

Now that we know all plaintext data, key, and the final block of output, we can use the above formula to completely decide the output value. Now we can work on finding $P_0$ and $C_0$. We may find $C_2 = O_2 \oplus P_1$. Then $C_1 = D_K(C_2) \oplus P_2$, $C_0 = D_K(C_1) \oplus P_1$. Now to find $P_0$, we use $P_0 = O_1 \oplus C_1$. This solves the problem. Unfortunately, my code is a bit dirty. You can still see all the key ideas.

## part 1 : brute force to find the key and final 32 bytes of output
def solve(KEY):
    msg = 'If Bruce Schneier multiplies two primes, the product is prime. On a completely unrelated note, the key used to encrypt this message is ' + KEY
    msg = msg.encode()
    msg = pad(msg, 16)
    CV = ctxt[-32:]
    for i in range(0, 16):
        for j in range(0, 16):
            CVV = CV[0:4] + cc[i] + CV[5:18] + cc[j] + CV[19:]
            c_n = bytes.fromhex(CVV)
            c_n_1 = AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(strxor(c_n, msg[-32:-16]))
            c_n_1 = strxor(c_n_1, msg[-16:])
            c_n_1 = strxor(c_n_1, msg[-48:-32])
            found_c = False
            tt = c_n_1.hex()
            for k in range(0, 32):
                if ctxt[-64+k] != '▒' and ctxt[-64+k] != tt[k]:
                    found_c = True
                    break
            if found_c == False:
                print("found!", KEY, i, j)
 
for i in range(0, 16):
    for j in range(0, 16):
        for k in range(0, 16):
            KEY = key0 + cc[i] + key1 + cc[j] + key2 + cc[k] + key3
            solve(KEY)
 
## part 2 : recover entire output
KEY = '0b9d0fe1920ca685e3851b162b8cc9e5'
## change the final 32 hex data of 'ciphertext' accordingly 
 
for i in range(1, 10):
    if i == 1:
        CVV = ctxt[-32*i : ]
    else:
        CVV = ctxt[-32*i : -32*(i-1)]
    c_n = bytes.fromhex(CVV)
    print(len(c_n))
    print(len(msg[-16*(i+1):-16*i]))
    c_n_1 = AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(strxor(c_n, msg[-16*(i+1):-16*i]))
    if i == 1:
        c_n_1 = strxor(c_n_1, msg[-16*i:])
    else:
        c_n_1 = strxor(c_n_1, msg[-16*i:-16*(i-1)])
    c_n_1 = strxor(c_n_1, msg[-16*(i+2):-16*(i+1)])
    ctxt = ctxt[0:-32*(i+1)] + c_n_1.hex() + ctxt[-32*i:]
 
## part 3 : recover answer
ctxt = 'ed5dd65ef5ac36e886830cf006359b300112c744b0aac58207aea28e804ec6abd6e5c397d1d4bd6f42539db06aff5de0a45d08c7dee9da217412bb6edcdab75f3096f135f702fdda23b764c1bfde3b103a1fe35ed6c0b03d2e1a8badb6c04e330c0dff963317506a110a742feea43cf2ed1e8e0f0f5e33993c8ee28200461ad755fca0ebd654e6962862f31270f414eab7c9076140feb15c1e690a83a0e60d75975d21cde66e41791b8780988c9b8329'
c_2 = strxor(bytes.fromhex(ctxt[32:64]), msg[0:16])
c_1 = strxor(AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(c_2), msg[16:32])
c_0 = strxor(AES.new(bytes.fromhex(KEY), AES.MODE_ECB).decrypt(c_1), msg[0:16])
p_0 = strxor(bytes.fromhex(ctxt[0:32]), c_1)
print(c_0 + p_0)

 

impECCable

#!/usr/bin/env python3.8
 
import ecdsa
import random
import hashlib
 
Curve = ecdsa.NIST384p
G = Curve.generator
n = Curve.order
 
flag = open('flag.txt', 'r').read().strip()
auth_msg = b'I know alll of your secrets!'
 
def inv(z, n=n):
    return pow(z, -1, n)
 
def gen_keypair():
    d = random.randint(1, n-1)
    Q = d*G
    return d, Q
 
def sign(msg, d):
    x = int(hashlib.sha1(int.to_bytes(d, 48, byteorder='big')).hexdigest(), 16) % 2**25
    while True:
        k1 = (random.getrandbits(340) << 25) + x
        k2 = (random.getrandbits(340) << 25) + x
        r1 = (k1*G).x()
        r2 = (k2*G).y()
        if r1 != 0 or r2 != 0:
            break
    h = int(hashlib.sha384(msg).hexdigest(), 16)
    s = inv(k1)*(h*r1 - r2*d) % n
    return (r1, r2, s)
 
def verify(msg, Q, sig):
    if any(x < 1 or x >= n for x in sig):
        return False
    r1, r2, s = sig
    h = int(hashlib.sha384(msg).hexdigest(), 16)
    v1 = h*r1*inv(s)
    v2 = r2*inv(s)
    x1 = (v1*G + (-v2 % n)*Q).x()
    return (x1 - r1) % n == 0
 
def menu():
    m = '''Here are your options:
    [S]ign a message
    [V]erify a signature
    [P]ublic Key
    [Q]uit'''
    print(m)
    choice = input()[0].lower()
    if choice == 's':
        print('Enter your message (hex):')
        msg = bytes.fromhex(input())
        if len(msg) >= 8:            
            print('Message too long!')
            exit()
        sig = sign(msg, d)
        print(' '.join(map(str, sig)))
    elif choice == 'v':
        print('Enter your message (hex):')
        msg = bytes.fromhex(input())
        print('Enter your signature:')
        sig = [int(x) for x in input().split()]
        if verify(msg, Q, sig):
            if msg == auth_msg:
                print('Hello there authenticated user! Here is your flag:', flag)
                exit()
            else:
                print('Verified!')
        else:
            print('Invalid Signature!')
    elif choice == 'p':
        print(Q.x(), Q.y())
    else:
        print('Oh ok then... Bye!')
        exit()
 
d, Q = gen_keypair()
 
print('Welcome to my impECCable signing service.')
for _ in range(11):
    menu()
 

So we have to forge a signature. Let's try that by finding the private key $d$. 

Let's take a look at the signature scheme. $x$, while unknown, is always fixed for each signature.

$h$ is a hash of the message, so we know this value too. We are also given $r_1, r_2, s$ as a result of the signature.

So let's take a look at the last equation $s \equiv k_1^{-1} \cdot (hr_1 - dr_2) \pmod{n}$. 

We already know $r_1, r_2, s, h$, so the unknowns are $k_1$ and $d$. Note that $d$ is also always fixed.

Also, note that $k_1 = small \cdot 2^{25} + x$, where $small$ is around $2^{340}$, far less than $n$.

Taking this into account, we can rewrite our equation as follows: $$ k_1 s \equiv hr_1 - dr_2 \pmod{n}$$ $$ (small \cdot 2^{25} + x) s \equiv hr_1 - dr_2 \pmod{n}$$ $$ - 2^{-25}s^{-1} r_2 d + 2^{-25}s^{-1} hr_1 \equiv small + x \cdot 2^{-25} \pmod{n}$$ This starts to look like a hidden number problem! But the $x$ variable seems like a problem. 

It doesn't matter, since there are 10 such equations, and we can subtract two of them to get 9 (or more?) equations without $x$. 

Now it resolves into solving $A_i x + B_i \equiv small \pmod{n}$ for some known $A_i, B_i$. I'm sure there are many ways to solve this, but the method I enjoy is to use LLL + Babai's Closest Vector Algorithm. Check the implementation below. For details, ask in comments :)

def rhexc():
    t = random.randrange(0, 16)
    if t <= 9:
        return chr(ord('0') + t)
    if t >= 10:
        return chr(ord('a') + t - 10)
 
conn.recvline()
msgs = []
h = []
r1 = []
r2 = []
s = []
for i in range(0, 10):
    conn.recvline()
    conn.recvline()
    conn.recvline()
    conn.recvline()
    conn.recvline()
    conn.send("S\n")
    conn.recvline()
    msg = rhexc() + rhexc() + rhexc() + rhexc()
    msgs.append(bytes.fromhex(msg))
    hh = int(hashlib.sha384(bytes.fromhex(msg)).hexdigest(), 16)
    h.append(hh)
    conn.send(msg + "\n")
    T = conn.recvline().split()
    r1.append(int(T[0].decode()))
    r2.append(int(T[1].decode()))
    s.append(int(T[2].decode()))
 
f = open("data.txt", "w")
 
def goprint(t, s):
    f.write(s + " = [")
    for i in range(len(t)):
        f.write(str(t[i]))
        if i != len(t) - 1:
            f.write(", ")
    f.write("]")
 
goprint(h, "h")
f.write("\n")
goprint(r1, "r1")
f.write("\n")
goprint(r2, "r2")
f.write("\n")
goprint(s, "s")
f.write("\n")
f.close()
print("DONE")
 
a = int(input())
b = int(input())
c = int(input())
 
conn.recvline()
conn.recvline()
conn.recvline()
conn.recvline()
conn.recvline()

import hashlib
import random
 
def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small  
 
def sign(msg, d):
    x = int(hashlib.sha1(int.to_bytes((int)(d), 48, byteorder='big')).hexdigest(), 16) % 2**25
    while True:
        k1 = (random.getrandbits(340) << 25) + x
        k2 = (random.getrandbits(340) << 25) + x
        r1 = (k1*G).xy()[0]
        r1 = (int)(r1)
        r2 = (k2*G).xy()[1]
        r2 = (int)(r2)
        if r1 != 0 or r2 != 0:
            break
    r1 = (int)(r1)
    r2 = (int)(r2)
    d = (int)(d)
    h = int(hashlib.sha384(msg).hexdigest(), 16)
    s = ((int)(inverse_mod(k1, n)*(h*r1 - r2*d))) % n
    return (r1, r2, s)
 
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF
E = EllipticCurve(GF(p), [-3, 0xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF])
n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
G = E(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7, 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f)
 
M = Matrix(ZZ, 10, 10)
 
h = [233731106310751937192664573894149799156520678027609284447669359448796436322955092470459836110792934841120158122984, 24811003402020297682803985280385324059294547276381651936828219428316450314628727089306406877936309521585868406250470, 17531688510937980482168807263229017380075873963160377208275450719528636667269895679466032893594537651522283322716674, 36047996617843056294579056584530136441992332560008111725661742840889647330983212663288175229441011598065500536724651, 11272134849660563344197668625651398585469230739650422640053316031881717853156318362750855003467577550566014131759397, 12921752283394782997197083154961040846567875585176615600282439213271258534634490795163442206145433928804694064497184, 23550485659661088231333360400047313315118168135461773986636400711616230052409480901284050511344421804458290935165361, 28496735302713412781192449440072502796901684384799422985608472930590031587697602766375490458840116389733463012282962, 8277886329528032187549731002807594806536689677333903394331300955320330584538612138873925253500020691928232999586476, 15008843981182040291480007346492436282071178418873478338505839724866567471088415321631607204728733513138973751666571]
r1 = [12579209808189312915327132001276994446255172328500500695944989889711062858983163741271309992272077550124869505655381, 751327735728556148057917754296484320013694567443429719964844556884059843931387861716234725405209534287623519155458, 5371112946404190387697534646035651694165960225187891433236446686273017304702714837212569297073575677253044266881569, 331352105137929972597744016411888049220372925675806096677491319577734959841100142754252499792455324441192018313181, 7888617807239874165986404317109270600428296541740743307263264541916487472897668559357227416927514439026859501878365, 27761407228814320863611585879580881526756177120011066949498954824121650008685326439038329973891388684478285112725357, 27729723957967183136564649593980227227433733353902657860894937180736101915856597513173881921545820999053402276812094, 7364956988030862701298496872632133592704536625686657579967644830046483396779789062671782387408609718000755429523017, 37812330351370334405023218191363149079167490389863184907107776623417575732769914373075308521813667861691959707092667, 2624169019517838564518311384425555195298893854856387163253094963173848316296091845329567038393753791750586302201087]
r2 = [3362705797849617878647365660985990566049333116696565173083098561696239463413527201559140422082923583525045722549763, 14145060354523589059216194767137578723898667342472872089321140612118830294396552192914912108964170720929305735415873, 29896158881994803685845271456929722092964179790028911234436030397936425532648870182944208462169501559557896423331008, 28295713529327846754165290558634286334350103809603649440117629677663367232344783261643275422157945835517134018581552, 9832320742110221576843735934134914437015558355201552824473334305115758409450236891997901207964296770834208882940712, 4863643686082209193655332852839008988042953344444353171052414901807831698624799620686397115822220675031235649084871, 2172376087957939144239533590664428657297700738539681962241559027660276255529486815550264413927604748955534219627695, 39270978975994145259001854586943865848306851245548202584185719889584304215280317078715908462808066433518126930812549, 34215025679986052889776564064620447574359162481440315252719789122933592974697130074626618888824626087631554900691781, 31458354800313627611820028529141092961133175220661883156536844963568120403379640053999048076879854251402929920752081]
s = [17925111440396892739033187521377597454621431410987251376820936783063824269472232155851393375468659283009982667848669, 21853582586273412881491430100511011448648027948649700911052731210656190304335253416414001734385549707694334614279337, 19106220304410988776781688031238993716481941836023244437887325024470240140203226637806963202138139801315239237169074, 17507801404065436507268995586301878815717284846882572361951752925726533505019428040074124887812030279468394962880645, 4900819118697444872055280551871388610242725910301521205805242844252676607768719405815620318563132591329844695620900, 28480294438694078949495111903243339194235498093230054160772397254022021764455096010558032230371482379081669589216030, 25703610354773191595397225912857234424274497331129500961893925842562869928957637655440191485239263057624366236967535, 25089230670220425716164780435793841951903552099807404714502656133071929486670807789632806166532377757560189053522629, 38581148690570764731827681277745747604768765690301001244659037510529992367464486509918486337349511386868684709829501, 33302053638667654050592244700225839457979855163938098516151926858754963517053234739223403629384061080926568390283532]
 
iv = inverse_mod(2 ** 25, n)
 
for i in range(0, 9):
    M[0, i] = (((inverse_mod(s[i+1], n) * r2[i+1] - inverse_mod(s[0], n) * r2[0]) * iv) % n) * n
    M[i+1, i] = n * n
M[0, 9] = 1
 
Target = [0] * 10
for i in range(0, 9):
    Target[i] = (((inverse_mod(s[i+1], n) * r1[i+1] * h[i+1] - inverse_mod(s[0], n) * r1[0] * h[0]) * iv) % n) * n
Target[9] = 2 ** 383
 
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
print(TT[9]) ## d
 
sec = b'I know alll of your secrets!'
X = sign(sec, TT[9])
print(X[0])
print(X[1])
print(X[2])

LSB || MSB Calculation Game

#!/usr/bin/env python3
from os import urandom
from random import randint
 
print('Welcome! As you may know, guessing is one of the most important skills in CTFs and in life in general. This game is designed to train your guessing skills so that you\'ll be able to solve any CTF challenge after enough practice. Good luck!\n')
 
class LCG:
    M = 937954372991277727569919570466170502903005281412586514689603
    a = randint(2, M-1)
    c = randint(2, M-1)
    print(f'M = {M}')
    print(f'a = {a}')
    trunc = 20
 
    def __init__(self, x0):
        self.x = x0
 
    def next(self):
        self.x = (self.a * self.x + self.c) % self.M
        return ((self.x % 2**self.trunc) << self.trunc) + (self.x >> (self.M.bit_length() - self.trunc))
 
NUM_GUESSES = 5 # higher chances of winning!!
rng = LCG(int(urandom(25).hex(), 16))
wins = 0
 
for r in range(1, 24):
    try:
        num = rng.next()
        print('Round ' + str(r) + '. What\'s the lucky number? ')
        guesses = [int(guess) for guess in input().split(' ')[:NUM_GUESSES]]
        if any(guess == num for guess in guesses):
            print('Nice guess! The number was', num)
            wins += 1
        else:
            print('Unlucky! The number was', num)
    except ValueError:
        print('Please enter your three numbers separated by spaces next time! e.g. 123 1337 999')
        exit()
 
if wins > 10:
    print('YOU WIN! Your guessing skills are superb. Here\'s the flag:', open('flag.txt', 'r').read().strip())
else:
    print('Better luck next time :(')
 

This is yet another LCG breaking with lattices :) Basically we are given 20 LSB and 20 MSB of each number.

We can such number as $2^{180} \cdot a_i + 2^{20} \cdot small + b_i$, where $a_i, b_i$ are known and $small$ is around $2^{160}$. 

We know $a$, but we do not know $c$. Denote the 0th number as $x$. Then our next numbers will be $ax+c$, $a^2x+(a+1)c$, $\cdots$ $, a^n x + (a^{n-1} + \cdots + 1)c$. Therefore, our goal here is to solve the set of equations $$ a^k x + (a^{k-1} + \cdots + 1) c \equiv 2^{180} a_k + 2^{20} \cdot small + b_k \pmod{m} $$ $$ 2^{-20} a^k x + 2^{-20}(a^{k-1} + \cdots + 1) c - 2^{-20}(2^{180} a_k + b_k) \equiv small \pmod{m}$$ for each $k$. This is yet another hidden number problem, so we can set up a similar procedure as the above problem. However, the bounds are kinda tight, so we have to optimize a little bit. Refer to the following code, and leave comments if there are parts you don't understand. 

print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
print(conn.recvline())
 
num = []
for i in range(1, 24):
    if i <= 12:
        conn.recvline()
        conn.send("0\n")
        T = conn.recvline()
        cc = 'Unlucky! The number was '
        T = T[len(cc):-1]
        T = T.decode()
        num.append(int(T))
    if i == 12:
        print(num)
    if i >= 13:
        conn.recvline()
        x = int(input())
        conn.send(str(x) + " " + str(x) + "\n")
        conn.recvline()
print(conn.recvline())

def Babai_closest_vector(M, G, target):
        small = target
        for _ in range(1):
            for i in reversed(range(M.nrows())):
                c = ((small * G[i]) / (G[i] * G[i])).round()
                small -=  M[i] * c
        return target - small  
 
n = 937954372991277727569919570466170502903005281412586514689603
a = 340191373049582240414926177838297382326391494482892283959227
num = [766060457621, 362859134107, 54864930141, 719063617319, 570095548300, 385643485103, 400992666914, 1095280053170, 105685083393, 701621243850, 981672150015, 408709955639]
 
low = []
upp = []
for x in num:
    low.append(x >> 20)
    upp.append(x % (2 ** 20))
 
mult_1 = [a]
mult_2 = [1]
 
for i in range(1, 12):
    mult_1.append((a * mult_1[i-1]) % n)
    mult_2.append((a * mult_2[i-1] + 1) % n)
 
M = Matrix(ZZ, 14, 14)
iv = inverse_mod(2 ** 20, n)
 
for i in range(0, 12):
    M[0, i] = ((int)(mult_1[i] * iv % n)) * n
M[0, 12] = 1
 
for i in range(0, 12):
    M[1, i] = ((int)(mult_2[i] * iv % n)) * n
M[1, 13] = 1
 
for i in range(0, 12):
    M[i+2, i] = n * n
 
Target = [0] * 14
for i in range(0, 12):
    Target[i] = (((2 ** 160) * upp[i] + iv * low[i]) % n + (2 ** 159)) * n
Target[12] = n // 2
Target[13] = n // 2
               
M = M.LLL()
GG = M.gram_schmidt()[0]
Target = vector(Target)
TT = Babai_closest_vector(M, GG, Target)
x = TT[12]
c = TT[13]
 
for i in range(1, 24):
    x = (a * x + c) % n
    if i <= 12:
        print(x % (2 **  20) == low[i-1])
        print((x >> 180) == upp[i-1])
    if i >= 13:
        print( ((x % (2 ** 20)) << 20) + (x >> 180)) 

l337crypt

from Crypto.Util.number import getPrime, bytes_to_long
from random import randint
 
flag = open('flag.txt', 'rb').read().strip()
 
p, q = getPrime(1337), getPrime(1337)
n = p*q
 
D = (1*3*3*7)^(1+3+3+7)
hint = int(D*sqrt(p) + D*sqrt(q))
 
x = randint(1337, n)
while 1337:
    lp = legendre_symbol(x, p)
    lq = legendre_symbol(x, q)
    if lp * lq > 0 and lp + lq < 0:
        break
    x = randint(1337, n)
 
m = map(int, bin(bytes_to_long(flag))[2:])
c = []
for b in m:
    while 1337:
        r = randint(1337, n)
        if gcd(r, n) == 1:
            break
    c.append((pow(x, 1337 + b, n) * pow(r, 1337+1337, n)) % n)
 
print(f'hint = {hint}', f'D = {D}', f'n = {n}', f'c = {c}', sep='\n')
 

We assume that $p<q$ in the following analysis. It's easy to see that it doesn't matter.

First, the obvious part. Since $x$ is a quadratic non-residue modulo $p$ and $q$, we easily see that the appended value in the ciphertext is a quadratic residue modulo $n$ if and only if $b=1$. This can be determined with legendre symbols if we know the factorization of $n$.

The only hint here is the bounds on $D(\sqrt{p} + \sqrt{q})$. With this bound, we can easily manipulate the inequalities to get a bound on $p+q$, so eventually a bound on $q$ using quadratic equations and the knowledge of $n$.

Now this is a good time to use coppersmith's attack. Assume that we derived $L \le q \le R$. 

Set $f(x) = x + L$, set a bound $X = R - L$, then perform sage's small_roots() algorithm.

However, like rbtree wrote in the coppersmith attack tutorial (Korean, check the blog) we need to carefully select $\beta$ and $\epsilon$. 

We are working with $q$, so $\beta = 0.5$ is fine. Doing some calculations, we see that $n$ is around 2674 bits and $R-L$ is around 600 bits. 

We do some math and find $\epsilon = 0.02$ to be sufficient. This provides a slow, yet guaranteed solution in sage. Full code is below. 

## kth root of n, (integer rounded) using binary search
def kthp(n, k):
    lef = 1
    rig = 2
    while rig ** k < n:
        rig = rig << 1
    while lef <= rig:
        mid = (lef + rig) // 2
        if mid ** k >= n:
            best = mid
            rig = mid - 1
        else:
            lef = mid + 1
    return best        
 
hint = 49380072119923666878249192613131592074839617141388577115293351423167399196342955381916004805107462372075198711094652660372962743330048982663144511583693085794844754920667876917018671057410534100394910738732436580386544489904637
D = 15515568475732467854453889
n = 6337195756161323755030821007055513472030952196189528055855325889406457327105118920711415415264657259037549360570438684177448730672113983949019501534456306880443480045757556693491657382839313528872206247714019569057234809244745178637139314783799705976807860096251357543835678457306901513720623505353691449216464755029227364954566851544050983088509816181294050114090489118245225264446360947782705558298586215673137402419393055466097552149369002210996708260599901728735979196557443301850639382966378922196935480476418239903494619475397129088135961432456212959427154766737697387874383258702208776154403167756944619240167487825357079536617150547060929824469887270443261440975473300946304087345552321787097829023298865763114083681766490064879774973163395320826072815425507105417077348332650202626344592023021273
 
## hint / D <= sqrt(p) + sqrt(q) <= (hint + 1) / D
X = (hint * hint) // (D * D) - 2 * kthp(n, 2)
Y = (hint * hint + 2 * hint + 1) // (D * D) - 2 * kthp(n, 2)
X = int(X)
Y = int(Y)
## small p + q = Y
lr = (X + kthp(X * X - 4 * n, 2)) // 2
sm = (Y + kthp(Y * Y - 4 * n, 2)) // 2
 
sm = int(sm)
lr = int(lr)
df = sm-lr
assert df >= 0
print((int)(df).bit_length())
 
K = Zmod(n)
P.<x> = PolynomialRing(K, implementation='NTL')
f = x + lr
 
T = f.small_roots(X = 2**600, beta=0.5, epsilon = 0.02)
print(T) ## T[0] + lr is a factor of n
 
for x in c:
    if pow(x, (p-1) // 2, p) == 1 and pow(x, (q-1) // 2, q) == 1:
        s += '1'
    else:
        s += '0'
 
s = int(s, 2)
print(long_to_bytes(s))