Mathematics - Brainteasers Part 1

Adrien's Signs

"Adrien's been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?"

I did not find this one easy. However, I've thought we needed something we learnt through this course and the only thing that fits is the Legendre Symbol. So, for each int in the output we use Legendre Symbol and if it outputs 1 we add it to a string else we add 0. Then we convert the binary string to ASCII.

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext

# Decrypt


def decrypt_flag(ciphertext):
    b = ''
    for n in ciphertext:
        if pow(n, (p-1) // 2,p) == 1:
            b += '1'
        else:
            b += '0'
    return b

def decode_binary_string(s):
    return ''.join(chr(int(s[i*8:i*8+8],2)) for i in range(len(s)//8))

ciphertext = encrypt_flag(FLAG)
s = decrypt_flag(ciphertext)

print(decode_binary_string(s))

This will indeed print crypto{????????????????????}. So To get the flag, simply use the output.txt as ciphertext.

Modular Binomials

Rearrange the following equations to get the primes p,q

N = p*q c1 = (2*p + 3*q)**e1 mod N c2 = (5*p + 7*q)**e2 mod N

So, I remember doing something like this in a Cyptology course at DTU, but there does exists a much easier solution for factoring large numbers.

We can simply look up the factors in http://factordb.com

This of course only works if the number is in the database, but in this case it is.

So, I remember doing something like this in a Cyptology course at DTU, but there does exists a much easier solution for factoring large numbers.

We can simply look up the factors in http://factordb.com

This of course only works if the number is in the database, but in this case it is.