PlaidCTF 2013 WriteUp - cyrpto

The tasks provides the python code of an encryption algorithm and the ciphertext of the flag with its encryption information (see below).
An according decryption service is running on a given server.
The decryption service asks for a ciphertext c as well as a special value of encryption information y which is used for generating the XOR-key and the length L (in bits).
Sadly the server will not decrypt any ciphertext using the provided encryption information of the flag.

The given python code is shown below.

import math
import random
# bleh, figuring out how to decrypt stuff is hard...
# good thing there's a service running at wherever the problem description says

ciphertext = \
(19139950631257094109974817512950844945236146526899325826152393111265339856332117664760030665587057736341341088217L, 698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842
622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538L, 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
    print "orig y:", y
    for k in range(0, L):

        l = l << 1
        l |= y & 1
        y = pow(y, 2, N)

    return (m ^ l, y, L)

A glance at the encoding-algorithm shows that two things happen in the for-loop.
Firstly the momentary XOR-key (l) gets left shifted and enlengthened by an additional bit depending on the value of y.
Secondly a new value for y is computed.

So we left shift the ciphertext of the flag and calculate a new value for y. For the sake of completeness we adjust the new bit according to the new l.

Here's the script:

import math

ciphertext = (19139950631257094109974817512950844945236146526899325826152393111265339856332117664760030665587057736341341088217L, 698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842
622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538L, 375)
pubkey = 914036124605072095896498645040317110444677693681625101303036515307269256964695517984683462742136579499746530214988587637694496516580350919995355407744891125814950650516684386468562425056693756001673L

y=ciphertext[1]
c=ciphertext[0]

#shift the ciphertext
c = c << 1
#we don't need to change the new LSB because it gets shifted back before decoding
#but its the correct way to do it
c |= y & 1
#calculate next value for y
y = pow(y, 2, pubkey)

print "c=",c
print "y=",y
print "L=",ciphertext[2]+1

The decoding algorithm gets feeded with our new values for c, y and L (=L+1) and will receive a left shifted ciphertext and an y which will produce a left shifted key.
Thus it will answer with a left shifted cleartext encoded as an int.

Before parsing this int to a string we shift our additional bit back to where it came from.
Otherwise we would encounter a problem during the bytewise operation in inttostr():

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

#  - shift back
#  - decode to string
#  - and print
print inttostr(90509775860478546334862465529642126634112405755992846988282238109064385906168446542663883843704092402706003699962 >> 1)

The flag is

Cyprus_keylength(cm)_STILL_BEST_KEY_FORMAT