crypto3

from random import *
from sympy import nextprime
from serct import flag
def Printprime(bits):
    A1=getprime(bits)
    A2=getprime(bits)
    c=randint(1,bits)
    B=(A1&(2**bits -1))>>c<<c
    temp=A1*A2
    print B
    print temp
    B1=(A1&(2**1024 -1))>>10<<10
    retrn A1,B1
p1,q1=Printprime(1024)
#B1=106672572720048882245660511958712758437546239973820056988685173758158387505232286222345308433971608941789148315811224011373367452106624375614858115402658270967073303108417429716363790098705093167287547128233883046603422138051729608392226373427044742935820547926346986700993433110025346422649463516306117492736
#temp1=18223408528938169563926297587705487122400521640144380302276492241065231360197061692156705171767387290791148541561476206560745923631684641131760019914136599820986994476711070781431006040501812087737193539402386241242517740267076091571026828269589016751672519420720282198833660352448501015746469864270887304810845950763013784529734523829259854050111750385439938542892934956015656186706709145463150202092953765596173302945107138213341531230951256986478565603356167357434402810865412234907275857841643625096319566068656995222254979424537359861594456585561427700014906151549675951595460571359557824293390454141212479211953
p2,q2=Printprime(1024)
#B2=91877168566039491657305870670623199089479881202304232943572017885574139886174920491635129611163469509914703088351415537136643846568888402564414425238913656847647811500708341665196970357054465257253155806724008810425186336247727840542478123737508362772116597089289402649681073921122899377392328647691871453184
#temp2=10752981800150852696615563967881183599965159757324046388359973939317020898441759042947405484639238309399736743934033107178433518473681342641181213615317215639871849837008763067553426720824753891424475137916504324486720764803530300240955353341899560507971266902592160865957525943891842840187409215141446461696280549372905972385938708196767232048124561700402455255379531118578921913216752577417339268065778869076797335588047205958424875533168419129102310280661151613698902457676601785179734346052695408018278262324802910968046484470735194722038791302419051610443221479467600861127174611095684288611709562448544247273209
s1=nextprime((q1!)%p1)
s2=nextprime((q2!)%p2)
N=s1*s2
e=0x10001
c=pow(flag,e,n)
'''
N=402578570588989011906570974065635937836078609932235040229555379679839344402431378637094396812095407833305090207407212999030856266457870166813619476187500056486139989534715354006264939545095618222505483434352481960643166460370364037889685327790334910772475718818257316134282259815647802558834005326533813682323692197154897833084645060766766206530892477886113760677908927345577239531704573351071636043686822034521516668710069458255874802928450423278843190165962415917958305925239507648246803381332359355415021339069241284375116735895430101301850196917182567902398283167486452437848411633833758460403705565382613658367
c=257219466169584626430317895847625453300903766165345929735330675689224900452052640693187275057781527958416216799173373604530220596162237821541564525255992497174490505760337958793285092180161001615733433429635155570988111639066535536344186373487468032512963711380368877832845219013378230192621831685917905614682144243446410642717728189211599904992797336342529661659885203669580272027538396825189492963272218286519957838724526284897979415278563773983550358918900302656283455164088875610481023867345293117711686899541264690484693138375715496362591852380643486782321366972801503945491161057276658293915561697253892732835
'''

分析PrintPrime可以得知，注释中的B和temp分别是A1高位和N，那么就可以利用coppersmith攻击得到原本的A1。
常见的已知p高位攻击是直接移位，而这题给移回来了，所以不能用之前的脚本，否则计算kbit = bits - hight_p.nbits()时得到的结果是0。
这里需要直接把B1给转成2进制，看看最后有多少个0，就是kbit的值。

>>> p=106672572720048882245660511958712758437546239973820056988685173758158387505232286222345308433971608941789148315811224011373367452106624375614858115402658270967073303108417429716363790098705093167287547128233883046603422138051729608392226373427044742935820547926346986700993433110025346422649463516306117492736
>>> bin(p)
'0b1001011111101000001000110001111100000101011001001110001101011010010010010101101110000111100101011101010010010110101100100000101101011111100001000001011110101101110010110011111101001000110011100010000011101100001101110010011011110000011110010010101111000101100111110100111010100000110000110100001110011000110100011000101111100010010001001111000110000110110001001111000010101000111101000001000010001100011101110111000101001101011111001001011110101011010010111101101110001101010110111001011111000011001011100010110101011101010011101011001001111001001000110110001011100001110000100110011001111111001000110000110100001111100000001111100101110111110100110010111011110100111101001110010100110001000010000101100111001110101000000111011100101110110111010111100100000111001011100011110011100100100000101010010101110010000010001000001010111100011101110101110110111011010101100111001000100100110001100110010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'

可以得知最后有130位。利用脚本得到原本的A1，也就是p1，得到p1后就可以计算出q1

hight_p = 106672572720048882245660511958712758437546239973820056988685173758158387505232286222345308433971608941789148315811224011373367452106624375614858115402658270967073303108417429716363790098705093167287547128233883046603422138051729608392226373427044742935820547926346986700993433110025346422649463516306117492736
n = 18223408528938169563926297587705487122400521640144380302276492241065231360197061692156705171767387290791148541561476206560745923631684641131760019914136599820986994476711070781431006040501812087737193539402386241242517740267076091571026828269589016751672519420720282198833660352448501015746469864270887304810845950763013784529734523829259854050111750385439938542892934956015656186706709145463150202092953765596173302945107138213341531230951256986478565603356167357434402810865412234907275857841643625096319566068656995222254979424537359861594456585561427700014906151549675951595460571359557824293390454141212479211953
PR.<x> = PolynomialRing(Zmod(n))
f = x + hight_p
x0 = f.small_roots(X=2^130, beta=0.4)[0]
print("x: %s" %hex(int(x0)))
p = hight_p+x0
print("p: ", int(p))
q=(int(p)&(2**1024 -1))>>10<<10
print("q: ", int(q))
# x: 0xd174e59b2ccf39cef6bc3bbb98c529db
# p: 106672572720048882245660511958712758437546239973820056988685173758158387505232286222345308433971608941789148315811224011373367452106624375614858115402658270967073303108417429716363790098705093167287547128233883046603422138051729608392226373427044742935820547926346986701271848724546016167104265505521615055323
# q: 106672572720048882245660511958712758437546239973820056988685173758158387505232286222345308433971608941789148315811224011373367452106624375614858115402658270967073303108417429716363790098705093167287547128233883046603422138051729608392226373427044742935820547926346986701271848724546016167104265505521615054848

同理可得p2，q2：

x: 0x48d87b37cdbc02bd8bde90e45420261b
p: 91877168566039491657305870670623199089479881202304232943572017885574139886174920491635129611163469509914703088351415537136643846568888402564414425238913656847647811500708341665196970357054465257253155806724008810425186336247727840542478123737508362772116597089289402649777902372098458748457875593766253897243
q: 91877168566039491657305870670623199089479881202304232943572017885574139886174920491635129611163469509914703088351415537136643846568888402564414425238913656847647811500708341665196970357054465257253155806724008810425186336247727840542478123737508362772116597089289402649777902372098458748457875593766253896704

接着到第二步，可以看到题目中有用到阶乘，所以联想到wilson定理：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )
于是我们就可以通过invert函数，一步步将A推成B，这样就可以很快的解除p，q的值，得到flag

s1 = p1-1
for i in range(q1+1, p1, 1):
    s1 = s1 * inverse(i, p1) % p1
s2 = p2-1
for i in range(q2+1, p2, 1):
    s2 = s2 * inverse(i, p2) % p2
s1=nextprime(s1)
s2=nextprime(s2)
N=s1*s2

然后就是正常的RSA解密

N=402578570588989011906570974065635937836078609932235040229555379679839344402431378637094396812095407833305090207407212999030856266457870166813619476187500056486139989534715354006264939545095618222505483434352481960643166460370364037889685327790334910772475718818257316134282259815647802558834005326533813682323692197154897833084645060766766206530892477886113760677908927345577239531704573351071636043686822034521516668710069458255874802928450423278843190165962415917958305925239507648246803381332359355415021339069241284375116735895430101301850196917182567902398283167486452437848411633833758460403705565382613658367
p = s1
q = N // p
c=257219466169584626430317895847625453300903766165345929735330675689224900452052640693187275057781527958416216799173373604530220596162237821541564525255992497174490505760337958793285092180161001615733433429635155570988111639066535536344186373487468032512963711380368877832845219013378230192621831685917905614682144243446410642717728189211599904992797336342529661659885203669580272027538396825189492963272218286519957838724526284897979415278563773983550358918900302656283455164088875610481023867345293117711686899541264690484693138375715496362591852380643486782321366972801503945491161057276658293915561697253892732835
e=0x10001
d = inverse(e, (p-1)*(q-1))
m = pow(c, d, N)
print(long_to_bytes(m))