胖哈勃之 LHY

Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python

import gmpy
from Crypto.Util.number import *
from secret import x, y, flag

assert gmpy.is_prime(y) ** 2016 + gmpy.is_prime(x+1) ** 2017 + ((x**2 - 1)**2 % (2*x*y - 1) + 2) ** 2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

p = gmpy.next_prime(x**3 + y**3) #(x+y)**3-3xy(x+y)
q = gmpy.next_prime(x**2*y + y**2*x) #xy(x+y)
n = p * q
phi = (p-1)*(q-1)
d = gmpy.invert(0x10001, phi)
enc = pow(bytes_to_long(flag), 0x10001, n)
print 'n =', n
print 'enc =', enc

# n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
# enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612

Solve

由于

1
1+1+2**2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

所以 x+1y 都是质数,(x**2 - 1)**2 % (2*x*y - 1)==0

根据数学推理或者大胆瞎猜得到 x=2y ,然后代入生成p和q,以pq==n 为条件爆破y即可。

来自 官方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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#!/usr/bin/env python

# Show that if 4ab - 1 divides (4a**2 - 1)**2, then a = b.
# suppose y be a large prime and x + 1 is another large prime.

import gmpy
from Crypto.Util.number import *

# from this condition with help of previous fact we can deduce that:
# ==> we take 2a = x and b = y, so: 2xy - 1 | (x**2 - 1)**2 ==> x = 2y

# assert gmpy.is_prime(y) + gmpy.is_prime(x+1) + ((x**2 - 1)**2 % (2*x*y - 1) + 2) ** 2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146 = 1 + 1 + 2 ** 2018

# so we have x = 2y

# p = gmpy.next_prime(x**3 + y**3) # ==> p = gmpy.next_prime(8*y**3 + y**3) = gmpy.next_prime(9*y**3)
# q = gmpy.next_prime(x**2*y + y**2*x) # ==> q = gmpy.next_prime(4*y**2*y + y**2*(2y)) = gmpy.next_prime(6*y**3)
# n = p * q # ==> n = p * q ~= (9*y**3) * (6*y**3) = 54*y**6
# So we can factor n with knowing n ~= 54*y**6

n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612

# now we calculate the 5th root of n//45 to find the y:

def iroot(k, n):
UB = 1
while pow(UB, k) < n:
UB *= 2
LB = UB / 2
while UB - LB > 1:
M = (LB + UB) // 2
midToK = pow(M, k)
if midToK < n:
LB = M
elif n < midToK:
UB = M
else:
return M
if pow(UB, k) == n:
return UB
else:
return LB

y = iroot(6, n // 54)

while True:
if gmpy.is_prime(y):
if gmpy.next_prime(9*y**3) * gmpy.next_prime(6*y**3) == n:
print 'Found:', 'y =', y
break
else:
y += 1

x = 2*y
p = gmpy.next_prime(x**3 + y**3)
q = gmpy.next_prime(x**2*y + y**2*x)
n = p * q
phi = (p-1)*(q-1)
d = gmpy.invert(0x10001, phi)
flag = long_to_bytes(pow(enc, d, n))
print 'flag =', flag

没有gmpy库,稍微改了下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import *
n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612
y = gmpy2.iroot( n // 54,6)[0]
print "near:",y
for i in range(0x10000):
k=y+i
if gmpy2.is_prime(k):
if gmpy2.next_prime(9*y**3) * gmpy2.next_prime(6*y**3) == n:
print 'Found: offset=%d y=%d'%(i,k)
break
x ,y= 2*k,k
p = gmpy2.next_prime(x**3 + y**3)
q = gmpy2.next_prime(x**2*y + y**2*x)
n = p * q
phi = (p-1)*(q-1)
d = gmpy2.invert(0x10001, phi)
flag = long_to_bytes(pow(enc, d, n))
print 'flag =', flag
# near: 12996881452793504643693526905573881980920361170852213106754463438614382317225798822548048130268953176983864771790449810537027331620960357639880338702048953
# Found: offset=0 y=12996881452793504643693526905573881980920361170852213106754463438614382317225798822548048130268953176983864771790449810537027331620960357639880338702048953
# flag = flag{e01c9eb8078ea9bbac035ea68021c070}

队友Mads推出x=2y 了,可惜没进一步试下。他在博客写了 推理过程 ,可能不太严谨,但巧妙假设变量关系来消元的思路值得学习。