Coppersmith -- 相关消息攻击

NUS_CS2107-CTF

感谢：hash_hash

题目

from Crypto.Util.number import bytes_to_long, getPrime

FLAG = <REDACTED>

names = open("names.txt", "rb").read().split(b'\n')
body = open("mail.txt", "rb").read()

output = ""

p = getPrime(2048)
q = getPrime(2048)
e = 3

n = p * q
output += f'n = {n}\n'

def encrypt(m):
    m = bytes_to_long(mail)
    return pow(m, e, n)

for i in range(len(names)):
    assert len(names[i]) == 20, f"{names[i]} c" # 如果不是20个字节，就报错
    mail = b"Dear " + names[i] + b",\n\n"
    mail += body + b"\n\n"
    mail += FLAG
    mail += b"Best,\n Prof"
    assert len(mail) < 512 # 如果不到512个字节，就报错
    output += f'c{i + 1} = {encrypt(mail)}\n'

open("output.txt", "w").write(output)
'''
output:
n = 346086230149584219301828432507079633735346488934733801420030872222630395000281531140320826904487764046361060202180732645207351125450949432534812827775822476485177001094548125962882655540173197011111834840433003933720562053572062644257215031704470412589980587766956146714651062239812884816973340293331695667046020298163606289963668222955818727279891050383871535930077515201181667207278574091157314938662275167988844922674565207711794513085037219759743182408857740009096185277529633995373076217819725780989623657497480020584260211364027648795067733419161984699867668621607304165591612631349105778648136377081927235145936695851769303919087432272090915474434179649568885986572401810712380921156403677512066643265128781744916120160459894376123976190039591282340584157166793320203011494173723843454049009457205063612523312075401089419233355069210083180856265059157316900747839545171811963038578342753447003222675957352700759799584552589631799187011056934881199978491934269801219014260167290750489589338729801105512255809495426028283244147876879200638750471878794671487690656086146887927323564088490517619854027008910142059732240375119537500402697308892248577377035234224792688850174072120405510586660911849350333631341147534157442864641557
c1 = 156292650814813406061069216632783346112943830958917771741789672098768503306903868834394454408930045664877361617102870847959511790635432746593860076977789395570314397268008558447528262909693841366252627878588711873508503393307083788193504979362204908320776877595638859561397653896070616506254826182775243060375706715642045415868536471516647589255322554593279386634153504804045350045803272217074061221894816270508653956392143199846529790697936122516208858180532277152167028439448114017936075701599000858577232703373768213832234991978780106031556572105422633069636820348172457079731572681351189644196870161446906172692379794107408066818629790803988288375593831780485155718951289177295512615132668608577466621709307091984889790667255654012971416873021405406348299728665444885237082148346771719839813269688344674146634299378856957694297679812609629415083674777431716263153221621390218309202996685956366103168707462458829547649156587202343022720833848423969077561220169479490347669628804487263702560170733443642571504144804633093999944449422419271098271943563024775572484511651687487820762047984381645186799522962407741927539868351729046433495044305918254873548699149268898275868094083968393655534461737383334331515843041130206808270617620
c2 = 295234665560491826187534181013802793968848277190510286651143711031071290941522888350875537449687896742863326889297236066257949812980640273859355823246418644920242279276001584006540272460470905601593417858091782842179682815325268507664837439920005660908822044653276898656332552511324727760583365499388611845019545616915664475470124516464527096095045327307602786788830938912772303721074519055532479632860169844801898419499875558269250761390484207876154553661136620997357304500701499942342210904303397311431391911933796673756784083888072569428268934528777000751730355921392657999027123118267020404925671219044323149722998628157109317604856145358964403584104477785704351492738263701742093354359699153930356616082900973443900237769686553194560709123689341620030896721630929133241651052084632686735955237136028182047741394159554539145184336962369079848392551174383091504922936241683914178447778881128412246464059298075231670674533304782143600259607403786363588516858470606115900787505000999243690492372294887176959865362323804124212407132490668666551860807388192655920563534267685799686491016467272780369548445644370037664007068127514105566869883359308740941931676190586530507142842381663735433364896710102063464356835969151152080636836389
'''

exp Sage

from tqdm import tqdm
from Crypto.Util.number import *

pgcd = lambda g1, g2: g1.monic() if not g2 else pgcd(g2, g1%g2)
n = 346086230149584219301828432507079633735346488934733801420030872222630395000281531140320826904487764046361060202180732645207351125450949432534812827775822476485177001094548125962882655540173197011111834840433003933720562053572062644257215031704470412589980587766956146714651062239812884816973340293331695667046020298163606289963668222955818727279891050383871535930077515201181667207278574091157314938662275167988844922674565207711794513085037219759743182408857740009096185277529633995373076217819725780989623657497480020584260211364027648795067733419161984699867668621607304165591612631349105778648136377081927235145936695851769303919087432272090915474434179649568885986572401810712380921156403677512066643265128781744916120160459894376123976190039591282340584157166793320203011494173723843454049009457205063612523312075401089419233355069210083180856265059157316900747839545171811963038578342753447003222675957352700759799584552589631799187011056934881199978491934269801219014260167290750489589338729801105512255809495426028283244147876879200638750471878794671487690656086146887927323564088490517619854027008910142059732240375119537500402697308892248577377035234224792688850174072120405510586660911849350333631341147534157442864641557
c1 = 156292650814813406061069216632783346112943830958917771741789672098768503306903868834394454408930045664877361617102870847959511790635432746593860076977789395570314397268008558447528262909693841366252627878588711873508503393307083788193504979362204908320776877595638859561397653896070616506254826182775243060375706715642045415868536471516647589255322554593279386634153504804045350045803272217074061221894816270508653956392143199846529790697936122516208858180532277152167028439448114017936075701599000858577232703373768213832234991978780106031556572105422633069636820348172457079731572681351189644196870161446906172692379794107408066818629790803988288375593831780485155718951289177295512615132668608577466621709307091984889790667255654012971416873021405406348299728665444885237082148346771719839813269688344674146634299378856957694297679812609629415083674777431716263153221621390218309202996685956366103168707462458829547649156587202343022720833848423969077561220169479490347669628804487263702560170733443642571504144804633093999944449422419271098271943563024775572484511651687487820762047984381645186799522962407741927539868351729046433495044305918254873548699149268898275868094083968393655534461737383334331515843041130206808270617620
c2 = 295234665560491826187534181013802793968848277190510286651143711031071290941522888350875537449687896742863326889297236066257949812980640273859355823246418644920242279276001584006540272460470905601593417858091782842179682815325268507664837439920005660908822044653276898656332552511324727760583365499388611845019545616915664475470124516464527096095045327307602786788830938912772303721074519055532479632860169844801898419499875558269250761390484207876154553661136620997357304500701499942342210904303397311431391911933796673756784083888072569428268934528777000751730355921392657999027123118267020404925671219044323149722998628157109317604856145358964403584104477785704351492738263701742093354359699153930356616082900973443900237769686553194560709123689341620030896721630929133241651052084632686735955237136028182047741394159554539145184336962369079848392551174383091504922936241683914178447778881128412246464059298075231670674533304782143600259607403786363588516858470606115900787505000999243690492372294887176959865362323804124212407132490668666551860807388192655920563534267685799686491016467272780369548445644370037664007068127514105566869883359308740941931676190586530507142842381663735433364896710102063464356835969151152080636836389

PR.<x,y> = PolynomialRing(Zmod(n))
PRx.<x> = PolynomialRing(Zmod(n))
Z.<x,y> = PolynomialRing(ZZ)
for l in tqdm(range(100,500)):
    f1 = x^3-c1
    f2 = (x+2^(8*l)*y)^3-c2 # 字节串转换方式
    f1 = f1.change_ring(Z)
    f2 = f2.change_ring(Z)
    g = f2.resultant(f1).univariate_polynomial()
    g = PRx(g)
    g = g.monic()
    root = g.small_roots(X = 2^160, beta = 1, epsilon = 0.05)
    if root:
        delta = root[0]
        f1 = PRx(x^3-c1)
        f2 = PRx((x+2^(8*l)*delta)^3-c2)
        h = pgcd(f1, f2)
        co = list(h.coefficients()) # .coefficients() 系数
        flag = int(-co[0] * inverse(int(co[1]), n) % n)
        print(long_to_bytes(flag))
        break

推导

题目输出给出 $n$ , $c_1$ , $c_2$ 以及包含在加密代码中的 $e = 3$
由 $e = 3$ 推断出可以利用低公钥指数攻击其中有 Coppersmith定理 (LLL的一个应用-前置知识：格子)
题目给出的加密代码中这部分

for i in range(len(names)):
    assert len(names[i]) == 20, f"{names[i]} c" # 如果不是20个字节，就报错
    mail = b"Dear " + names[i] + b",\n\n"
    mail += body + b"\n\n"
    mail += FLAG
    mail += b"Best,\n Prof"
    assert len(mail) < 512 # 如果不到512个字节，就报错
    output += f'c{i + 1} = {encrypt(mail)}\n'

可以发现进入 encrypt 函数前只有 name 不一样，除此之外完全一致
于是对 $m_1 m_2$ 做差即可得到差异部分也就是两 name 的差
因此利用Coppersmith时可以列出如下关系

name_1 -> m_1

name_2 -> m_2

C_1 = m^e

C_2 = (m + 2^k \times (m_2 - m_1))^e

利用copper算 $m_2 - m_1$ 后面把这两多项式做 gcd 有共同因子 $m$ 即为明文

解释

该代码的前两行导入了两个Python包。"tqdm "和 "Crypto.Util.number"。"tqdm "是一个为长期运行的循环提供进度条的包，而 "Crypto.Util.number "是一个提供与密码学有关的数学函数的包，如同余关系。
下一行定义了一个lambda函数 "pgcd"，它使用欧几里得算法计算两个多项式的最大公除数（GCD）。GCD的计算是递归的，直到其中一个多项式变成0，这时另一个多项式就是结果了。(这里的插曲是提到exgcd时八月发现了 OI Wiki 上的一个错误已经修正且对 OI Wiki 交pr)，文章后方有常规化代码。
$n$ 、 $c1$ 和 $c2$ ，为 'output.txt' 的线索。
下面定义了三个多项式环。 $PR$ ，变量为 $x$ 和 $y$ 的整数模， $PRx$ ，变量为 $x$ 的整数模，以及 $Z$ ，变量为 $x$ 和 $y$ 的整数模。变量 $n$ 用于指定多项式环的模数，它应该与代码中早期定义的 $n$ 值相匹配。
然后，"for "循环使用 "range "函数在100到499（包括）的数值范围内进行迭代。这个循环被 "tqdm "函数所包裹，以显示一个进度条。
在循环内部，两个多项式 $f1$ 和 $f2$ 分别定义为 $x^3-c1$ 和 $(x+2^{8*l}*y)^3-c2$ 。变量 $l$ 是循环索引，用于生成一个大的常数值 $2^{8*l}$ (字节串转换方式)，与变量 $y$ 相乘。"^"运算符表示指数化。
然后用 $Z$ 多项式环的 "change_ring "方法将两个多项式 $f1$ 和 $f2$ 转换为整数多项式。
$f1$ 和 $f2$ 的结果是用 "resultant "方法计算的，该方法返回其根为 $f1$ 和 $f2$ 的公共根的多项式。然后使用 "univariate_polynomial "方法将这个结果多项式转换为单变量多项式。
单变量多项式 $g$ 然后使用 "PRx "构造函数转换为 "PRx "多项式环中的多项式，并对其调用 "monic "方法以确保前导系数为1。
对 $g$ 调用 "small_roots "方法，参数为 $X=2^{160}$ , $beta=1$ , $epsilon=0.05$ 。这个方法可以找到所有绝对值小于 $2^{160}$ 的 $g$ 的根，其实部和虚部都在-beta和beta之间。"epsilon "参数是所需的根的精度。
如果发现任何根，第一个根被分配给 "delta"， $f1$ 和 $f2$ 被重新定义为 $PRx$ 多项式环的多项式。
然后使用 "pgcd "函数计算 $f1$ 和 $f2$ 的GCD，并将得到的多项式的系数提取到一个列表 $co$ 。
然后，通过取GCD多项式第一个系数的负值乘以以下各项的模逆值来计算flag(计算出明文后包含)。

“小根算法”（small root algorithm）

用于找到小的整数根的算法，称为“小根算法”（small root algorithm）。在这个算法中，有三个重要的参数：

X：代表要寻找的根的范围。在这个例子中， $X = 2^{160}$ ，表示我们要找到一个小于 $2^{160}$ 的整数根。

160 的来源是 $160 = P_{unkonw}$

beta：是一个参数，它与X的位数相关。在这个例子中， $beta = 1$ ，表示我们要找到一个大小小于 $X^{1\over {beta}}$ 的整数根。

epsilon：是一个参数，它控制了算法的准确性和效率。在这个例子中， $epsilon = 0.05$ ，表示我们要找到一个小于X的整数根，其大小不超过 $X^{0.05}$ 。

最后，root是算法返回的一个结果，表示找到的小整数根。

Lambda常规化

def pgcd(g1, g2):
    if not g2:
        return g1.monic()
    else:
        return pgcd(g2, g1 % g2)

为什么倒数第二行需要用第一个系数的负数×第二位的逆就是flag

f1 = PRx(x^3-c1)
f2 = PRx((x+2^(8*l)*delta)^3-c2)
h = pgcd(f1, f2)
print(h)
co = list(h.coefficients())
print(co)
flag = int(-co[0] * inverse(int(co[1]), n) % n)
print(long_to_bytes(flag))

在这段代码中，首先计算了一个小整数根delta，然后分别构造了两个多项式f1和f2，并计算了它们的最大公因数h。最后，通过一些计算得到了一个整数flag。

在这个算法中，flag的计算依赖于h的系数。具体地说，如果h的系数为[a, b, c, ...]，那么flag就等于-a * (b^-1) mod n，其中b^-1表示b的逆元素（即满足b * b^-1 = 1 mod n的数）。这个计算是基于多项式求最大公因数的性质推导得到的，具体证明过程可以参考相关的数学文献。

需要注意的是，这里的a和b都是模n意义下的整数，因此在计算过程中需要使用模运算和逆元素来确保计算的正确性。同时，由于b是h的次高项系数，因此必须保证b不为零，否则计算将无法进行。

LOV3