task.py1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#!/usr/bin/env python
from Crypto.Util.number import *
from secret import FLAG,BIT
def genkey(bit):
while True:
p = getPrime(bit)
q = (2 ** bit - 1) ^ p + 65537
if isPrime(q):
return p, q
p, q = genkey(BIT)
m = bytes_to_long(flag)
e = 65537
n = p*q
c = pow(m,e,n)
print('n={}'.format(n))
print('c={}'.format(c))
#n=7772032347449135823378220332275440993540311268448333999104955932478564127911903406653058819764738253486720397879672764388694000771405819957057863950453851364451924517697547937666368408217911472655460552229194417053614032700684618244535892388408163789233729235322427060659037127722296126914934811062890693445333579231298411670177246830067908917781430587062195304269374876255855264856219488896495236456732142288991759222315207358866038667591630902141900715954462530027896528684147458995266239039054895859149945968620353933341415087063996651037681752709224486183823035542105003329794626718013206267196812545606103321821
#c=2082303370386500999739407038433364384531268495285382462393864784029350314174833975697290115374382446746560936195242108283558410023998631974392437760920681553607338859157019178565294055755787756920003102506579335103169629546410439497570201554568266074421781047420687173530441469299976286281709526307661219925667082812294328343298836241624597491473793807687939912877432920934022304415340311930199467500833755390490763679081685821950332292303679223444816832000945972744492944044912168217765156110058474974887372388032286968936052010531850687361328326741707441938740295431353926037925950161386891437897990887861853097318
一开始神仙一样，看着各路wp不知道怎么变成p+q=2^1024 -1 - 65537
后面我吐了发现+优先级比xor高…
不好意思这道题真的奇奇怪怪，算是把官方wp看懂了
就一个知识点
因为python中+优先级比xor高，所以
(2 bit - 1) ^ p + 65537
等于(2 bit - 1) ^ (p + 65537)
wp第三行是两边加上q，即右边先xor再加q，而在python中会继续先加q，运算会错误
至于第三行怎么变成第四行：
2^bit-1是0b11111111….. 全是1
与一个数q异或，相当于对这个按位取反，再加q，就每一位都是1，也即第三行右边等于2^bit-1
至于bit最先盲猜1024，因为bit位影响了p和q的位数，当然wp中可以遍历：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#!/usr/bin/env python
from Crypto.Util.number import *
import sympy
e = 65537
n=7772032347449135823378220332275440993540311268448333999104955932478564127911903406653058819764738253486720397879672764388694000771405819957057863950453851364451924517697547937666368408217911472655460552229194417053614032700684618244535892388408163789233729235322427060659037127722296126914934811062890693445333579231298411670177246830067908917781430587062195304269374876255855264856219488896495236456732142288991759222315207358866038667591630902141900715954462530027896528684147458995266239039054895859149945968620353933341415087063996651037681752709224486183823035542105003329794626718013206267196812545606103321821
c=2082303370386500999739407038433364384531268495285382462393864784029350314174833975697290115374382446746560936195242108283558410023998631974392437760920681553607338859157019178565294055755787756920003102506579335103169629546410439497570201554568266074421781047420687173530441469299976286281709526307661219925667082812294328343298836241624597491473793807687939912877432920934022304415340311930199467500833755390490763679081685821950332292303679223444816832000945972744492944044912168217765156110058474974887372388032286968936052010531850687361328326741707441938740295431353926037925950161386891437897990887861853097318
p = sympy.symbols('p')
q = sympy.symbols('q')
for i in range(1000,1050):
res = sympy.solve([p*q-n, p+q-2**i+65538], (p, q))
if len(res)>1:
print(i)
print(res)
break
#1024
#[(72356988033940122419862865191878675238242016880080962265441973140379691886394220688072110362559413510402072754902898224503345853278372546073863042457429691363311481477269645152325782001930391869045739370961356170148607063612137861483639965888231664404355083617264515197675631111636979987271638724116276090949, 107412325452291468353067653887023798123555681014149695007988108017352983919106742444636366959848122510718041124968495133155443915536044076418984388182044433014456411947595840123976437599315702250407343581123649598689543618730325019990273144652595572758995427067321783042271614826842736317563717605507947980729), (107412325452291468353067653887023798123555681014149695007988108017352983919106742444636366959848122510718041124968495133155443915536044076418984388182044433014456411947595840123976437599315702250407343581123649598689543618730325019990273144652595572758995427067321783042271614826842736317563717605507947980729, 72356988033940122419862865191878675238242016880080962265441973140379691886394220688072110362559413510402072754902898224503345853278372546073863042457429691363311481477269645152325782001930391869045739370961356170148607063612137861483639965888231664404355083617264515197675631111636979987271638724116276090949)]
p = res[0][0]
q = res[0][1]
phin = (p-1)*(q-1)
d = int(inverse(e,phin))
#d = long(inverse(e,phin)) wp脚本用python2才有的long，py3会报错，py3只有int改成int
m = pow(c,d,n)
print(long_to_bytes(m))
#b'flag{8edf268a85202e540aaa070ac8ff63d2}'
用sympy.solve解方程，学到了学到了，还不用装新的库