

roXen

题目如下：

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

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)

n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638fL
c = 0x2672cade2272f3024fd2d1984ea1b8e54809977e7a8c70a07e2560f39e6fcce0e292426e28df51492dec67d000d640f3e5b4c6c447845e70d1432a3c816a33da6a276b0baabd0111279c9f267a90333625425b1d73f1cdc254ded2ad54955914824fc99e65b3dea3e365cfb1dce6e025986b2485b6c13ca0ee73c2433cf0ca0265afe42cbf647b5c721a6e51514220bab8fcb9cff570a6922bceb12e9d61115357afe1705bda3c3f0b647ba37711c560b75841135198cc076d0a52c74f9802760c1f881887cc3e50b7e0ff36f0d9fa1bfc66dff717f032c066b555e315cb07e3df13774eaa70b18ea1bb3ea0fd1227d4bac84be2660552d3885c79815baef661L

分析：

对于 $$ r=2^l-1 $$

$$ bin(2^{l)=100...00,故bin(2}l-1)=0111...11,xorp则将p中的1处变为0,0变为1 $$

因此 $$ p+adlit(p)=2^l-1 $$ 故 $$ p+q=2^l+31336 $$ 又由于 $$ phi=(p-1)(q-1)=n+1-(p+q)=n-2^l-31335 $$ 根据n为2046bit，因此猜测p为1024bit，q为1022bit，故 l=1024

推出

phi=8075050082948443349212340895390914595911667800472259304754411169066015177591933999426560842475863558771524178567197246061634705069273801684590339376649250275207876158732481939003115606742710400986721591279999826858150876137968993463656776832026731671417714759299940616065017786507499266738676453484280827236471905007897632221975348632278251045611984449962700114930252797604739054532124376815862307463077788325020496718875218389610118666406158621953023266468407185280651586416979516647636599642220645492470810795894389242387553997198008284230298061886510125108409348391328833263239270165044948668605098432639974697256

然后就是e的值不确定，没有其他的思路选择爆破

因为exp & (exp + 1) == 0，故 $$ exp=2^k-1 $$ 解密脚本如下：

import libnum
from Crypto.Util.number import long_to_bytes
import gmpy2
phi = 8075050082948443349212340895390914595911667800472259304754411169066015177591933999426560842475863558771524178567197246061634705069273801684590339376649250275207876158732481939003115606742710400986721591279999826858150876137968993463656776832026731671417714759299940616065017786507499266738676453484280827236471905007897632221975348632278251045611984449962700114930252797604739054532124376815862307463077788325020496718875218389610118666406158621953023266468407185280651586416979516647636599642220645492470810795894389242387553997198008284230298061886510125108409348391328833263239270165044948668605098432639974697256
c = 0x2672cade2272f3024fd2d1984ea1b8e54809977e7a8c70a07e2560f39e6fcce0e292426e28df51492dec67d000d640f3e5b4c6c447845e70d1432a3c816a33da6a276b0baabd0111279c9f267a90333625425b1d73f1cdc254ded2ad54955914824fc99e65b3dea3e365cfb1dce6e025986b2485b6c13ca0ee73c2433cf0ca0265afe42cbf647b5c721a6e51514220bab8fcb9cff570a6922bceb12e9d61115357afe1705bda3c3f0b647ba37711c560b75841135198cc076d0a52c74f9802760c1f881887cc3e50b7e0ff36f0d9fa1bfc66dff717f032c066b555e315cb07e3df13774eaa70b18ea1bb3ea0fd1227d4bac84be2660552d3885c79815baef661
n = 0x3ff77ad8783e006b6a2c9857f2f13a9d896297558e7c986c491e30c1a920512a0bad9f07c5569cf998fc35a3071de9d8b0f5ada4f8767b828e35044abce5dcf88f80d1c0a0b682605cce776a184e1bcb8118790fff92dc519d24f998a9c04faf43c434bef6c0fa39a3db7452dc07ccfced9271799f37d91d56b5f21c51651d6a9a41ee5a8af17a2f945fac2b1a0ea98bc70ef0f3e37371c9c7b6f90d3d811212fc80e0abcd5bbefe0c6edb3ca6845ded90677ccd8ff4de2c747b37265fc1250ba9aa89b4fd2bdfb4b4b72a7ff5b5ee67e81fd25027b6cb49db610ec60a05016e125ce0848f2c32bff33eed415a6d227262b338b0d1f3803d83977341c0d3638f
k = 1
while True:
    k += 1
    e = 2 ** k - 1
    gcd = gmpy2.gcd(e, phi)
    e2 = e // gcd
    d = gmpy2.invert(e2, phi//gcd)
    m = pow(c, d, n)
    p, judge = gmpy2.iroot(m, gcd)
    plaintext = long_to_bytes(p)
    if 'CTF' in plaintext and judge:
        print plaintext
        break
#CCTF{it5_3a5y_l1k3_5uNd4y_MOrn1N9}