Plaid CTF 2013 - cyrpto (crypto 100)

A pretty simple problem:

One of us devised a new cryptosystem! Can you break it? running at

import random
# bleh, figuring out how to decrypt stuff is hard...
# good thing there's a service running at 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)
    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 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:


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


Problem Solved

Show Comments