Pwnhub-Crypto-韩国欧巴

前言

近日有机会做了一次pwnhub的crypto，闲下来后做了一下记录

 

题目分析

题目很简短，如下

#!/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)
q = gmpy.next_prime(x**2*y + y**2*x)
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

这里我们摆出已知的几个式子



那么现在的想法很清楚：

1.利用已知的等式求出p和q
2.利用已知的等式进行代换，不需求出p和q，直接整体带入解密

这里我们选择走一步看一步，因为这样比较复杂的公式，我也没办法直接看出正解，只能步步为营

 

解题step1

首先从题目给的等式入手，这里的

is_prime(y)
is_prime(x+1)

均为bool值



式子中带有取余肯定是我们不希望看到的，于是我们从



我们可以发现这是式子中的最高次，那么我们能否利用2018方对其进行范围缩小？
尝试分析



为了方便后续描述，我们将等式右边的大数命名为num
通过简单运算发现

num>pow(2,2018)
num<pow(3,2018)

所以我们成功得到等式



即



我们进一步计算，得到



所以可以确定

y为素数
x+1为素数
k为整数

那么这就成了整数的抽象代数问题即如何利用上述条件得到x和y的关系



首先由x+1为素数，我们一定可以得到x为偶数
原因很简单，数字一共分为2种：2k和2k+1
2k一定不可能为素数，所以x+1为2k+1，那么x就是2k
所以x一定为偶数
不妨设x=2k
则得到



不难看出，显然有一个解为



所以一定有

x=2y

可以使条件成立
所以题目的已知公式可以推出p和q的关系为



即

 

解题step2

然后我们已知n的值，所以可以利用p*q=n去求n
但是由于这是一个三元方程



但是我们知道a和b应该是一个不大的数，所以我们可以暂时忽略，求一个y的近似值
于是乎，我们可以有



则p的近似值为

19758773482416975773513594727554854838261383456469757248975289414355380735280879485422339870304527397062948550174303008020919366147474933112054539960497455035338201515203147106735705140472387837291772737954077643308046956678940164319688649687874053450947563446714782140815873215100887989866701486767419287547227200825869331893787470348194603234016874968352188422840451629535806709831811012761153410419196032233502030396198424770210265894560281233572716876438572593

我们知道我们求出的p肯定是近似值，但是由于



这里的a很小，所以它只能改变低位的值，所以我们的p只是低位不准确
所以这里可以使用Coppersmith定理攻击去恢复不准确的低位
脚本如下

n=0x2ccce7ec66eee19f17522ba3b0a001f2668c6ab8d092001f0cd942fa84c23ab0234b5757448969faddd136fb4b07c0d7e6ad8f1b0e20d266e097abdd543bcfde62c14716df6e526c30df6018ca3ace1c8fb91b21940670bfecea64b859c47ce5a7a469d714c50598ed202a9a76b4eb5b8a275408697d80f4da5ef7a1b61be288738af57656e0fba938b571f1c8a06c59f60f0babe1edd3095621bb9125d7c71ca20286443dbf9ab721e230a7492e9f8e10f1b028065c8f12aac83502569dce5946264c0d1f18893e8f8f7489d548ec4254ee02a62b9acf313f2e1c8e28b563f242ed6613dce1a3dfd7d206d7b16e017e2dedbc5f80fbac85b78768abd4432da6c6e93e3e87a228cf332f69c0fd0613ccb76ee08de10bac7a6a42093259ca732254bfd38bc897872fae8e8dfef6498c66178e5006f9c69516967b089572bcc85b0af77273e269b679bb9d23119ee01004f005a36f58d50f1257d9b6024b3a4d560392ed03be731046866fbd268c3715164a19b17d52e6f349a9fc7a6bf15c1f21fd
p=0x83295d058b8d47fa5103ce9f7cb3b9e403d38a13a3443f1f62c371966bd0b325a96ec64d50e63aff662a6f3c4f06dd62f006eff0cbffff3733e9b0a0f1778f2bbe9dc9c2885bcb3c6846171b490c3e1b8bc04d94868d47c68618bd31976e8da90d29ca1b21ba1d29512bfc9b5c683d9b3d5bfaa16c3115a4879b12a4a1a218aaf50e0102473663282c2514814e3e67d255a7111ffd8ea4e60b10569183a5cbe39d1e25135ed004d6255e44daac0b7196efe58d1e1ea97b662582f56fe50a20e31
flag = False
for i in range(1,1024):
    p_fake = p + 2**i
    F.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    f = x - p_fake
    res = f.small_roots(X=2**i, beta=0.5)
    if res:
        for j in res:
            p_true = p_fake-j
            if n%p_true == 0:
                print p_true
                flag = True
                break
    if flag:
        break

即可得到p

19758773482416975773513594727554854838261383456469757248975289414355380735280879485422339870304527397062948550174303008020919366147474933112054539960497455035338201515203147106735705140472387837291772737954077643308046956678940164319688649687874053450947563446714782140815873215100887989866701486767419287547227200825869331893787470348194603234016874968352188422840451629535806709831811012761153410419196032233502030396198424770210265894560281233572716876438572799

 

解题step3

对于p的近似值恢复，也可以使用爆破方法，毕竟爆破量不是很大
爆破脚本如下

from Crypto.Util import number
import gmpy2
import gmpy
import libnum
import primefac
e = 0x10001
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612
n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
p = 9*(gmpy.root(n/54,6)[0])**3
for i in xrange(10000):
    if n%(p+i) == 0:
        p = p+i
        q = n/p
        phi = int((p-1)*(q-1))
        d = gmpy2.invert(e,phi)
        print libnum.n2s(pow(enc,d,n))
        break

也可以轻松得到flag

flag{e01c9eb8078ea9bbac035ea68021c070}