D^3CTF 2019 Crypto - Bivariate

1_task.py

from Crypto.Util import number
from secret import flag


nbit = 2048
e = 65537
p, q = number.getPrime(nbit//2), number.getPrime(nbit//2)
N = p * q
# N = 14871564779966647807710849781121809500530440168369963349377308901197803285619192987578333699960518148494391309500400834350235413916348349010881665475977014169857261456941575247369669695635975745695575650462258077595438693774208161879743121708431280489461785510815948783248837512615935739967100669884173960286905400419242769064214933385513190550471038684908409622471877199803893311107924150701348854249849421334035898230235882198863268374514022152610016824606857371732440610675267450448242632453712201631459133353269072394064023713666664658865870871502133929488104208880638866505781463327231845911539701761429945199541
l1, l2 = 100, 100
p0 = p&(2**(nbit//2-l2)-2**l1)
# p0 = 93385850998419806174049821342856149427082987334425681956871304674634743567844955346128006085283641074162399679349182002128091067590249803205616695850883274351928707097239994493908105710864142808452971773223255135164048699463079830049487024639301210894514331106512472593919901696
m = number.bytes_to_long(flag)
c = pow(m, e, N)
# c = 10454161721500904078992990976733131069703631969164229863956393961269190401053020275634570877979698850005750862147678060904860509659355430144733503676627208292541612517531160872405773586990460044525314537677972415841413442483929478441608647504336185702487234699787687463858266964770551618932386007590754132375184778058693275899627070257884705091097462215548526642324684522680388107010393353653970424278925961391520615121067095359413480310502790289446122606204408660390408947923596563466836485315027821916632985986635152691252060088613642635348350678106653474205916811230590997464683001041515569655426333726479796858651

2_exp.py

#!/usr/local/bin/sage -python
from sage.all import *
from Crypto.Util import number


e = 65537
# Different parameters for each team
N = 25399834187127560616377324812370548757173195169284556539872162671604871757452519233282907652108434123327408232947024502947915469579832631518239713332708158521036624588639774579662120326998800812927107933947317391745532955703923875523455993069144280051980899548298224204528982165205045875719337496741603728894563425753482396643748308742142056199938874535481990266115881794524511870310147791476658785663480386016318423184949506222892970169272928863915576974799698888006120205995339986478217351786809420314719374045082657371833464063781814506611011452446528527462394775717822053092264531338371314173056147348383691680693
p0 = 30690030687084539848565053327051629412800894538161597167514375082994946489553604097019123037407008578841050511681185164485110466633420466757540466128269516646299876490352434485844798968491360926923292898157483131799018230610798513878098851525346305237410921640772048609630748672
c = 12215848338373611558115949433223015085106664261456759740008576780433664311999065884357511436672200411146812837497888539079073728643162343495653837366446647675991233150748362505889407215372364638732322069514000168398707821424920609513270834826504932951735086417988920562947118230641305207450705273726733677352838552674136015841963687736367142321138217717812691901752141988569116003461283484769042020988308040283665089094946070393711544634846189363488826570509957947993818778767480702125261100905756351392967073213998362037988847449832496253118455528796006257134060681199708012092728874586714503285151480895621186504268

PR = PolynomialRing(Zmod(N), names='x,y')
x, y = PR.gens()
pol = 2**924 * x + y + p0

def bivariate(pol, XX, YY, kk=4):
    N = pol.parent().characteristic()

    f = pol.change_ring(ZZ)
    PR,(x,y) = f.parent().objgens()

    idx = [ (k-i, i) for k in range(kk+1) for i in range(k+1) ]
    monomials = map(lambda t: PR( x**t[0]*y**t[1] ), idx)
    # collect the shift-polynomials
    g = []
    for h,i in idx:
        if h == 0:
            g.append( y**h * x**i * N )
        else:
            g.append( y**(h-1) * x**i * f )

    # construct lattice basis
    M = Matrix(ZZ, len(g))
    for row in range( M.nrows() ):
        for col in range( M.ncols() ):
            h,i = idx[col]
            M[row,col] = g[row][h,i] * XX**h * YY**i

    # LLL
    B = M.LLL()

    PX = PolynomialRing(ZZ, 'xs')
    xs = PX.gen()
    PY = PolynomialRing(ZZ, 'ys')
    ys = PY.gen()

    # Transform LLL-reduced vectors to polynomials
    H = [ ( i, PR(0) ) for i in range( B.nrows() ) ]
    H = dict(H)
    for i in range( B.nrows() ):
        for j in range( B.ncols() ):
            H[i] += PR( (monomials[j]*B[i,j]) / monomials[j](XX, YY) )

    # Find the root
    poly1 = H[0].resultant(H[1], y).subs(x=xs)
    poly2 = H[0].resultant(H[2], y).subs(x=xs)
    poly = gcd(poly1, poly2)
    x_root = poly.roots()[0][0]
    
    poly1 = H[0].resultant(H[1], x).subs(y=ys)
    poly2 = H[0].resultant(H[2], x).subs(y=ys)
    poly = gcd(poly1, poly2)
    y_root = poly.roots()[0][0]

    return x_root, y_root

x, y = bivariate(pol, 2**100, 2**100)
p = 2**924 * x + y + p0
q = N//p
assert p*q==N, 'factoring failed'
d = inverse_mod( e, lcm(p-1,q-1) )
m = power_mod(c, d, N)
print 'flag: ' + number.long_to_bytes(m)

3_wp.md

In the task.py, we are given the middle bits of p, which divides an 2048-bit RSA modulus N. The unknown bits are located in two blocks, each of which is 100 bits in length.

This small roots problem can be solved by lattice techniques.

At Asiacrypt 2008, Herrmann and May proposed an algorithm to solve multivariate linear equations modulo an unknown divisor p of a known composite integer N [1].

They use the shift-polynomials with positive integers m,t,
$$ g_{k, i}(x_1, x_2) := x_2^i f^k(x_1, x_2) N^{max{t-k, 0}}. $$

To maximize solvable root bounds, they select as many helpful polynomials as possible. The parameter $\tau = t/m$ was optimized to $1−\sqrt{1-\beta}$ .

But here we are more interested in the speed; find the roots by constructing a lower dimensional lattices.

A hint is also hided in the topic description. Compared to the definition of Coppersmith method in the Wikipedia, we can easily find a related research [2] by googling "Coppersmith in the Wild".

Based on their implementation details, we can construct a lattice with the coefficient vectors of the set of polynomials $$ G:={y^h x^i f^j N^l | j + l = 1,0 \leq h + i + j \leq k} $$

and solve for solutions in a shorter time.

给出 RSA 其中一素数的中间位, 可以得到一个二元一次方程, 典型的 coppersmith method.

对于求解一个多元线性同余式的 small roots, 最先由 Herrmann 和 May 在 Asiacrypt 2008 提出具体解法.

为了最大化可解根的上界, 他们选择了尽可能多的helpful多项式, 这也意味着高阶的格基.

但是在解题时, 我们对速度更感兴趣.

题目描述中藏有 hint, 与维基中Coppersmith method的定义对比，可以发现多了 “Coppersmith in the Wild”.

根据论文的实现细节，我们可以使用多项式集合的系数向量构造一个低维的格基 $$ G:={y^h x^i f^j N^l | j + l = 1,0 \leq h + i + j \leq k} $$ 并在更短的时间内解决问题. (以上渣翻)

两个月前出的题, 在收到选手的 wp 后, 才发现 11 月上旬 github 上有相关的代码实现了该方案. 另外, 0ops的师傅的三变量解法也很好, 感谢.