PlaidCTF 2013 Crypto100 Crypto Writeup

PlaidCTF2013 Crypto100 crypto

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

client.py running at 54.234.77.50:13797 or 54.235.50.140:13797.

``````import random
import math
# 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]) &lt;&gt; 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 * 2 #这里本来是左移，但是小于号会把后面的代码吃掉
l |= y &amp; 1
y = pow(y, 2, N)
return (m ^ l, y, L)
``````

slipper@bt:~/CTF/PlaidCTF2013/crypto/crypto\$ telnet 54.234.245.15 13797
Trying 54.234.245.15…
Connected to 54.234.245.15.
Escape character is ‘^]’.
Send 1 to encrypt, 2 to decrypt, 3 to get pubkey: 2
c: 15837612793129403265283574183712049320456923458239472034932056385412838712039129134628735129381029461924618321283
y:9814513402169859830244323256475260794157685719960610664145090689046057195658068793563354204675825739659584262283793774432920113344374182219623260691576508226597259307160898152603847317630021751538
L: 375
… Nice try…

y = y*y % N = 842376507373989895999086264722582537123368770490346950741353843138436241343024669185370422253938355914800459068857695521295261389627915740380085077620094827672888542982036568692912342891435425038793
L = 375 + 1 = 376

slipper@bt:~/CTF/PlaidCTF2013/crypto/crypto\$ telnet 54.234.245.15 13797
Trying 54.234.245.15…
Connected to 54.234.245.15.
Escape character is ‘^]’.
Send 1 to encrypt, 2 to decrypt, 3 to get pubkey: 2
c: 0
y: 84237650737398989599908626472258253712336877049034695074135384313843624134302466918537042225393835591480045906885769552295261389627915740380085077620094827672888542982036568692912342891435425038793
L: 376
Here you go!
101686897114606056715237168431190820000470796857828910395983438187233021385241214426095996035820483704909967063880