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]) <> 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 & 1
        y = pow(y, 2, N)
    return (m ^ l, y, L)

加密的过程大致如下:
生成随机数y,取y的二进制表示的最后一位。
然后令y = y*y % N,不停的迭代下去。最后得到由y%1构成的一个串,长度为L,表示成数字就是l。
最后返回密文m^l, 最后一次迭代得到的r和整个串的长度L。
如果考虑直接解密,因为不知道密钥,只能尝试将r开方。
当N是质数时,开方至少会得到两个解。而N是两个模4余3的质数之积时,开方会有四个解。
二进制串的长度L是375,这说明要解密375次才能得到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是否是698145134021698598302443232564752607941576857199606106641450906890460571956580687935633542046758257396595842622837937744732920113344374182219623260691576508226597259307160898152603847317630021751538。只要不是这个值都可以解密。
所以只需再进行一次迭代,便可以让解密程序按照我们的想法运行。
也就是
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

因为解密的密文是0,所以返回的明文正是用y解密(开方)376次得到的l。
这个l是376位,比我们需要的l长了一位。
也就是说我们用来解密的l = l » 1 = 50843448557303028357618584215595410000235398428914455197991719093616510692620607213047998017910241852454983531940
将其与m异或,得到45254887930239273167431232764821063317056202877996423494141119054532192953084223271331941921852046201353001849981
再用inttostr(),得到 “KEY{Cyprus_keylength(cm)_STILL_BEST_KEY_FORMAT}:”