Plaid CTF 2013 - cyrpto (crypto 100)

A pretty simple problem:

cyrpto
100
crypto
One of us devised a new cryptosystem! Can you break it?
client.py running at 54.234.245.15:13797.

client.py:

import random
# bleh, figuring out how to decrypt stuff is hard...
# good thing there's a service running at 54.234.245.15 port 13797

ciphertext = (19139950631257094109974817512950844945236146526899325826152393111265339856332117664760030665587057736341341088217L, 698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538L, 375)
pubkey = 914036124605072095896498645040317110444677693681625101303036515307269256964695517984683462742136579499746530214988587637694496516580350919995355407744891125814950650516684386468562425056693756001673L

def numbits(k):
    if k == 1:
        return 1
    return int(math.ceil(math.log(k,2))) + (1 if k % 2 == 0 else 0)

def strtoint(s):
	if len(s) == 0:
		return 0
	if len(s) == 1:
		return ord(s[0])
	return (ord(s[0]) << (8 * len(s[1:]))) | strtoint(s[1:])

def inttostr(s):
	if s == 0:
		return ""
	c = chr(s & 0xFF)
	return inttostr(s >> 8) + c

def encrypt(m, N):
    L = numbits(m)
    random.seed()
    r = random.randint(2, N-1)
    x = pow(r, 2, N)
    y = x
    l = 0
    for k in range(0, L):
        l = l << 1
        l |= y & 1
        y = pow(y, 2, N)
    return (m ^ l, y, L)

When connecting to the server it will prompt you if you want to encrypt, decrypt or get the public key. If you try and send the ciphertext in client.py it will respond “… Nice try..”
The encryption/decryption works when trying other encrypted values, so it’s probably only checking for the exact cipher text.

Well looking at the algorithm, it’s doing key expansion, and just XORing the plaintext with the expanded value.. and there’s no checks on original length of the message. so we can just extend the message… lets go with 8 bits since the original message is most likely a string..

(c,y,L) = (19139950631257094109974817512950844945236146526899325826152393111265339856332117664760030665587057736341341088217L, 698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538L, 375)
N = 914036124605072095896498645040317110444677693681625101303036515307269256964695517984683462742136579499746530214988587637694496516580350919995355407744891125814950650516684386468562425056693756001673L

L = L+8
for k in range(375, L):
    c = c <<< 1
    y = pow(y, 2, N)

print c
print y
print L

Taking the output from this and sending it to the server we get back:

11585251310141253930862395587794192209166387936767084414500126477960241395989561157460977131994123827546368473595209

So then we can use the inttostr function so helpfully provided, we get back:

KEY{Cyprus_keylength(cm)_STILL_BEST_KEY_FORMAT}I

Problem Solved