Crypto CTF 2019 writeup

roXen

题目

roXen
Relationship with a cryptographer!

The Girlfriend: All you ever care about is crypto! I am sick of it! It's me or crypto!

The Cryptographer boyfriend: You meant to say it's you XOR cryptography.

The Girlfriend: I am leaving you.

roXen.py

#!/usr/bin/env python

from Crypto.Util.number import *
from secret import exp, flag, nbit

assert exp & (exp + 1) == 0

def adlit(x):
    l = len(bin(x)[2:])
    return (2 ** l - 1) ^ x

nbit = 1024
l = [1023,1024,1025]
def genadlit(nbit):
    while True:
        p = getPrime(nbit)
        q = adlit(p) + 31337
        if isPrime(q):
            return p, q

p, q = genadlit(nbit)
e, n = exp, p * q

c = pow(bytes_to_long(flag), e, n)

print 'n =', hex(n)
print 'c =', hex(c)

output.txt

n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638fL
c = 0x2672cade2272f3024fd2d1984ea1b8e54809977e7a8c70a07e2560f39e6fcce0e292426e28df51492dec67d000d640f3e5b4c6c447845e70d1432a3c816a33da6a276b0baabd0111279c9f267a90333625425b1d73f1cdc254ded2ad54955914824fc99e65b3dea3e365cfb1dce6e025986b2485b6c13ca0ee73c2433cf0ca0265afe42cbf647b5c721a6e51514220bab8fcb9cff570a6922bceb12e9d61115357afe1705bda3c3f0b647ba37711c560b75841135198cc076d0a52c74f9802760c1f881887cc3e50b7e0ff36f0d9fa1bfc66dff717f032c066b555e315cb07e3df13774eaa70b18ea1bb3ea0fd1227d4bac84be2660552d3885c79815baef661L

题解

首先观察脚本发现adlit函数其实就是等式p+adlit(p)==2**l-1。这样就可以得到p+q=2**l-1+31337。
猜测l的值，计算n的位数，发现是2046位，猜测p和q都是1024位的值，即l = 1024。代入上一步，得到p+q=2**1024+31336。
输出给了n=p*q，这样我们有了关于p,q的二次等式，用sage求解。(或者其它方式)。
得到p,q之后，我们需要确定e的值，加密方法类似于RSA。但是要注意的是，题目中给出了e的一般形式满足assert exp & (exp + 1) == 0即exp = 2**k-1形式，但是没有保证e一定和phi(n)=(p-1)*(q-1)互质。所以我们需要自己推导解法。
假如(e)和(phi(n))互质，那么就有(g = gcd(e,phi(n)))，然后(ed=g mod phi(n))，然后我们有(c^d mod n = m^{ed} mod n = m^g mod n)。这里因为(m)是小整数（相对于(n)），另外(g)的值也不大，所以直接开(g)次方即可。

脚本

import gmpy2,string
from Crypto.Util.number import *

p = 91934396941118575436929554782758166784623142015203107928295225306949429527662253180027648166060067602233902389535868116051536080388999480377007211745229221564969130373120800620379012435790356909945473565305296926519232706950561924532325538399351352696805684504904629096892037592742285758390953849377910498739
q = 87834916545113015336000964296144306577174555879027549345134855850783246277838709952680829156347468418886211490335525241607253688425417142115840218894244902812798763051744684655923207165455737209507609386779708842318917975391900956941587572141475884466544826179681669143055208345737430546444402480246313669813
n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638f
c = 0x2672cade2272f3024fd2d1984ea1b8e54809977e7a8c70a07e2560f39e6fcce0e292426e28df51492dec67d000d640f3e5b4c6c447845e70d1432a3c816a33da6a276b0baabd0111279c9f267a90333625425b1d73f1cdc254ded2ad54955914824fc99e65b3dea3e365cfb1dce6e025986b2485b6c13ca0ee73c2433cf0ca0265afe42cbf647b5c721a6e51514220bab8fcb9cff570a6922bceb12e9d61115357afe1705bda3c3f0b647ba37711c560b75841135198cc076d0a52c74f9802760c1f881887cc3e50b7e0ff36f0d9fa1bfc66dff717f032c066b555e315cb07e3df13774eaa70b18ea1bb3ea0fd1227d4bac84be2660552d3885c79815baef661
assert p*q==n
phin = (p-1)*(q-1)

def solve(e):
    gcd = gmpy2.gcd(e, phin)
    try:
        d = gmpy2.invert(e//gcd,phin)
    except:
        return False
    m = gmpy2.powmod(c, d, n)
    m,is_valid = gmpy2.iroot(m,gcd)
    m = long_to_bytes(m)
    if b'CCTF' in m:
        print(m)
        print(gcd)
    return False

from tqdm import trange
estr = '1'
for i in trange(10000):
    e = int(estr*i+estr,2)
    solve(e)