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