RSA-9 Coppersmith 相关攻击

Coppersmith 相关攻击

相关消息攻击

这里是针对一种特殊情况下的攻击。

Alice 将消息 $m_1$ 和 $m_2$ 使用同一组密钥进行加密，并且消息明文 $m_1, m_2$ 满足一组线性关系即 $m_2 \equiv f(m_1) \pmod n$ ​ 。$f$ 需要是线性关系，比如 $f(x) = ax+b$ 。攻击者在得到公钥，并截获了两组密文之后，可以计算出明文，该算法的复杂度为 $O(elog_2^2n)$ 。

有限域中多项式最大公因式提取

首先是需要会普通的多项式因式分解。

然后是需要会有限域中的多项式因式分解。

然后是需要通过辗转相除法求两个多项式的最大公因式。（即该公因式可以整除两者的所有因式。

Related Message Attack

攻击的原理如下：

首先已知条件为待加密的消息 $m_1, m_2$ 满足 $f(m_2) \equiv m_1 \pmod n$ ，Alice 对上述两则消息进行了加密 $c_1 \equiv m_1^e \pmod n, c_2 \equiv m_2^e \pmod n$ ，然后发送了消息。

此时有：

$$\because c_1 \equiv m_1^e \pmod n \\ \because c_2 \equiv m_2^e \pmod n \\ \because m_1 \equiv f(m_2) \equiv am_1+b \pmod n \\ \therefore c_1 \equiv f^e(m_2) \equiv (am_1+b)^e \pmod n \\$$

则对于方程 $f^e(x) - c_1 \equiv 0 \pmod n$​ 而言，很显然 $m_2$​ 是一个根。

而同时又有

$$c_2 \equiv m_2^e \pmod n$$

所以对于方程 $x^e -c_2 \equiv 0 \pmod n$ 而言，很显然 $m_2$ 也是一个根。

所以对于以下方程组

$$\left\{\begin{aligned}x^e - c_2 \equiv 0 \pmod n \\f^e(x) - c_1 \equiv 0 \pmod n \\\end{aligned}\right.$$

多项式 $(x-m_2)$ 都可以被提取出来。则可以通过对上述方程求解“最大公因子”，如果求解出来的最大公因式刚好是线性关系，则就成功得到了 $m_2$ 。

e = 3

特别地，在加密指数 $e=3$ 时，得到的一定是线性关系，这里可以对 $e=3$ 时进行一个推导。

首先是已知条件

$$c_1 \equiv m_1^3 \pmod n \\ c_2 \equiv m_2^3 \pmod n$$

已知明文消息之间存在线性关系，不妨设为：

$$m_1 \equiv am_2+b \pmod n$$

于是将 $(5)$ 带入 $(4)$ 有

$$c_1 \equiv (am_2+b)^3 \pmod n \\$$

然后我们将 $(6)$ 用立方公式打开有

$$c_1 \equiv (am_2+b)^3 \equiv a^3m_2^3+3a^2m_2^2b+3am_2b^2+b^3 \pmod n$$

然后再构造一个立方差

$$(am_2)^3-b^3 \equiv (am_2-b)(a^2m_2^2+am_2b+b^2) \pmod n$$

然后再将 $(7)$ 加上 $2b^3$ 再减去 $2b^3$ 以构造出 $(8)$ 中的部分 $(a^2m_2^2+am_2b+b^2)$ ，如下

$$a^3m_2^3+(-2b^3+2b^3)+3a^2m_2^2b+3am_2b^2+b^3 \\ \to (a^3m_2^3-2b^3)+3a^2m_2^2b+3am_2b^2+3b^3 \\ \to (a^3m_2^3-2b^3)+3b(a^2m_2^2+am_2b+b^2) \\ \equiv (am_2+b)^3 \equiv c_1 \pmod n$$

于是将 $(9)$ 再推一步，有

$$3b(a^2m_2^2+am_2b+b^2) \equiv c_1 + 2b^3 - a^3m_2^3 \pmod n$$

再联立 $(10) (8)$​ 可以得到

$$3b \times ((am_2)^3-b^3) \equiv (am_2-b)(c_1 + 2b^3 - a^3m_2^3) \pmod n \\ \because m_2^3 \equiv c_2 \pmod n \\ \therefore 3b \times (a^3c_2 - b^3) \equiv (am_2-b)(c_1+2b^3-a^3c_2) \pmod n$$

进而有

$$am_2-b \equiv \frac{3a^3bc_2-3b^4}{c_1+2b^3-a^3c_2} \pmod n \\ \to am_2 \equiv \frac{3a^3bc_2-3b^4}{c_1+2b^3-a^3c_2} + b \pmod n \\ \to m_2 \equiv (\frac{3a^3bc_2-3b^4}{c_1+2b^3-a^3c_2} + b) \times a^{-1} \pmod n \\ \equiv \frac{2a^3bc_2-b^4+bc_1}{ac_1+2ab^3-a^4c_2} \pmod n \\ \equiv (2a^3bc_2-b^4+bc_1) \times (ac_1+2ab^3-a^4c_2) ^ {-1} \pmod n$$

于是可以看到，等式右侧都是已知量，也就是我们可以求出 $m_2$ 。

再通过 $m_1 = am_2+b$ 可以求得 $m_1$ 。

更详细的过程，请参阅 paper。

例题

题目

试试相关消息吧

from secret import flag
import gmpy2
from Crypto.Util.number import getPrime, bytes_to_long
import random

p = getPrime(512)
q = getPrime(512)

n = p*q
e = 3

m = bytes_to_long(flag)

def en_crypt():
	a = random.randint(3, 114514)
	b = random.randint(114514, 1919810)
	m1 = a*m+b
	c = pow(m1, e, n)

	return c

c1 = en_crypt()
c2 = en_crypt()

print(n, e, c1, c2)

""" 
a=25559
b=1566263

a=40151
b=937702

n = 64251612718279874565135020724854186361791729597228580167602105663226169159430951649721404826104528375562597752438885799141986215791754045688464304397534285262363580948552185708203713698019391481402237962550584051662093127969076324334044234935857849587697668707259333680258908049423029158969023734969842028647
e = 3
c1 = 30559216332337868545447806299022489927424567299112260780479082036302197406127739887364810408971834533248410786862155083860678776202183791511127042474252179883865656395530687380927344115629381668893546215466847690886837144020669102311045303541563748487264474487865506199490613972693026406251709793742610355059
c2 = 25412688969352528525206249630700404238095437690372261688965615775917569492949109498775926735063889604659138332044590870715584072477604254500090604140151155575455043442799519141808635769064834862014762708841956603999266448677329840050007777755932559705318532263571967634446562945609652435261910316209461561779
"""

题解

这个一看，通过一个加密函数，每次在需要加密的消息中随机出两个参数 $a, b$​ 对明文进行变形，然后再计算出来了两个密文。这一看就是相关消息攻击呀！并且还是 $e=3$ 这种简单的情形。

只是这里需要稍微注意一下：

$$\because m1_1 = a_1m_1+b_1 \\ \because m1_2 = a_2m_2+b_2 \\ \therefore m1_1 \equiv a_1m_1+b_1 \pmod n, m1_2 \equiv a_2m_2+b_2 \pmod n \\ \therefore m1_1 \equiv a_1a_2^{-1}(m1_2-b_2)+b_1 \pmod n$$

也就是说， $a = a_1a_2^{-1}$ ， $b = b_1-a_1a_2^{-1}b_2$​ 。​

解密脚本如下：

import gmpy2
from Crypto.Util.number import getPrime, long_to_bytes

a1=25559
b1=1566263

a2=40151
b2=937702

n = 64251612718279874565135020724854186361791729597228580167602105663226169159430951649721404826104528375562597752438885799141986215791754045688464304397534285262363580948552185708203713698019391481402237962550584051662093127969076324334044234935857849587697668707259333680258908049423029158969023734969842028647
e = 3
c1 = 30559216332337868545447806299022489927424567299112260780479082036302197406127739887364810408971834533248410786862155083860678776202183791511127042474252179883865656395530687380927344115629381668893546215466847690886837144020669102311045303541563748487264474487865506199490613972693026406251709793742610355059
c2 = 25412688969352528525206249630700404238095437690372261688965615775917569492949109498775926735063889604659138332044590870715584072477604254500090604140151155575455043442799519141808635769064834862014762708841956603999266448677329840050007777755932559705318532263571967634446562945609652435261910316209461561779

a = a1*gmpy2.invert(a2, n)
b = b1 - a1*gmpy2.invert(a2, n)*b2

m_2 = (2*pow(a,3,n)*b*c2-pow(b,4,n)+b*c1)*gmpy2.invert(a*c1+2*a*pow(b,3,n)-pow(a,4,n)*c2, n)
m_1 = (a * m_2 + b) % n

assert (m_1 - b1)*gmpy2.invert(a1, n) % n == (m_2 - b2)*gmpy2.invert(a2, n) % n
m1 = (m_2 - b2)*gmpy2.invert(a2, n) % n

flag = long_to_bytes(m1)
print(flag)
# b'flag{baby_RSA_Related_Message_Attack_with_little_e}'

短填充攻击

目前很多 RSA 题目都会进行填充，即在待加密明文的之后再拼接一定的 padding。

如果填充内容过短会怎样呢？

事实上，考虑到前面 Related Message Attack 中的情况，就是 b 会很小，以至于根就会很小。

题目

就是给了 server.py 文件，还有个流量分析的文件，然后还有就是一个公钥文件。

# server.py
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2, random
from secret import m, flag

assert m[-38:] == flag
assert flag[:5] == b'flag{'
assert flag[-1:] == b'}'


pubkey = RSA.importKey(open('rsakey.pub', 'rb').read())
n, e = pubkey.n, pubkey.e


def addPadding(s):
    todo = -len(s) % 8
    return s + long_to_bytes(random.getrandbits(todo * 8))


def encryptMsg(m):
    msg = addPadding(m)
    assert len(msg) % 8 == 0

    return gmpy2.powmod(bytes_to_long(msg), e, n)

if __name__ == "__main__":
    username = input('Hello, I am the server.\nPlease tell me your name:').strip()

    print(f'Hello, {username}! Your ciphertext is {encryptMsg(m)}')

分析

拿到题目之后，本还想吐槽出题人加了个流量分析在里面，需要从流量中去寻找密文，对于我们这种不会流量分析的就又多了一层额外的难度，但后面发现也许这个也是有理由的。

但这次运气比较好，我还是找到了密文。

题目给的 Python 脚本中，给出了公钥 (e,n) ，按照题目中的方式打开公钥文件可以发现模数 $n$ 是相当安全的，只是公钥 $e=7$ 太小了，第一感觉就会觉得这里应该是有些问题的，只是暂时还不知如何利用。然后是在作为一个服务端，当用户发起请求时就会用同一组公钥加密相同的明文，只是在明文后面会随机填充部分字段后，再加密，而后将密文发送给用户。

然后，就还是先看看流量中有什么蛛丝马迹没。

用 wireshark 打开流量包。（瞎看了半天还是没找到蛛丝马痕。

然后二话不说，只能直接 Ctrl+F 大法进行全局搜索，如下图所示，只是要注意，下拉框选择 字符串 不然搜不到。

然后你就会发现这个玩意了，然后再搜，还会再发现一个 Bob。这里或许就是出题人不想直接告诉我们密文有两个吧，通过流量的方式，有可能别人就只搜了一个密文就关闭 wireshark。

（要不是我运气好，我就关了 wireshark 了。或许这就是出题人要加个流量分析，而不是直接给两个密文的原因？

你会发现还有一组密文是 bob 的

然后右键中间栏中的 data 字段，选择 “复制 -> 值””

然后可以写一段 python 将 16 进制的流量数据转化为字符串（有可能wireshark可以直接复制字符串，但我不会用。

def get_cipher(data):
    return "".join(map(lambda x: chr(int(x, 16)), data.split(":")))

然后大概就是这样，就能得到两组密文

密文如下

c1 = 207745134179372733555510206619693253104579843394896629739037329373112962626246001660692996105153219118802888232147542928402067843843528586661320609669764821619654148259323979346482619518127693134276997096465301242211338219230471535362522814373937363157952621289752500159789059618277078792730676938098151778724478618510442014061057398587899271302933994977686954557140792181120737121774640968270568182678321489463357386240195482174580855571460603588887113368877542370808084357842481355072918452814741564939655765498035870034623573615277107259501397135275787715228937905326258102800307298720705403841763666842176243959137647629868288744563301081604801635616954497347143042211051515138964208862089552048752128912810909730479659450966735343696566762894334249104817494914722566979492521404452789748171845406174662299522224640406957367515731398609433619859550730046552804426613174272338408295496475455377327126232203966170727191424458552984898420495331422888174501682405492889556485885498653026394829501033795561393942827468916484256939660461234831948497296037001984268948594694380490331513700030501310813656424424549981824937813623457529801230191235415350842735918693953674061739761952989693408739389294218794993885245118233185798993030811

c2 = 226199888918448644756982227968746328321985116022301858554198443672166664046511192215268564345898426376094090283902459640110441636420726770010000770994806563185277269200465979320365589893377418069091918532090442396603886751603663167305733566867710881487792435263851954036765024355077627565776101657845285994047225127259478223888842725657697619882058952675576467950522546405944727325816748748400930757072151974753803411875075825410215662132323783283622907642504349895222420194846774972358784353404930471430363282533597528847457511272893938256828008761907527515772662467469811929535936626565593800263948227574689518705440414368634213587105988741446978367368641973256822769215908784220309789734449328751828411012817796805182907296099522060377249696752489510340595152805018457215119257756500416362241433542631282380670560802965990054464183825706649810872267539076088793023183611390929368000088538174212497557317021558232130649505658714311457845634746833717519922531826151283006638342214774466523934632839617828984102088907011083393633695252458688340500110194100303563736683350582103762865754280928068416609493507422758397519930389697891015054896887103350205876203508540259064385048758693455947681367170495861484799223471818419141809766082

拿到密文后，再来细细思考，进行加密前，服务端会将明文进行随机填充，使得最后的明文位数为 $8$​ 的倍数，同时可以发现填充的部分只有很少一部分。然后进行加密。目前已知的：

$c_1, c_2,n,e$ ，满足 $(m+r_1)^e \equiv c_1 \pmod n$ , $(m+r_2)^e \equiv c_2 \pmod n$ 。

可疑的地方有：

1. $e$ 比较小，值得怀疑。
2. 给了两组密文 $c_1, c_2$ ，来源与同一组明文，填充了很少一部分不一样，即 $c_1, c_2$ 之间应该是有某种联系的。

于是可以换着组合词去搜索，比如 RSA little e padding attack ，会得到一些可能相关的攻击方法。比如，这里

虽然啃全英文的描述有些吃力（有能力的朋友完全可以直接看这个，甚至看对应的 paper），但可以再搜索这些攻击方法的名字，一般都会有中文的解释或者比较好用的轮子可以直接利用。比如此时，我们可以再去搜索关键词 Coppersmith's attack 看看它需要的条件是否和我们这里一致。

可以搜到很多，甚至还有这个攻击类型，出一个系列的：地址。

于是可以搜到很多相关的轮子，再一看确实和我们想要的差不多。coppersmiths_short_pad_attack.sage

上面 GitHub 那位，也是copy 的某位日本的站的地址，这个日本人的站，也挺不错的。

可以看到，轮子中需要的也正好就是我们知道的 $c_1, c_2,n,e$ ，同时搜索的资料中也表明了这个方法就是本题的考点。

answer

于是，问题就迎刃而解了：

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

m = long_to_bytes(related_message_attack(c1, c2, short_pad_attack(c1, c2, e, n), e, n))
# b'You are so good at Coppersmith! Here is flag: flag{congratulations_let#s_hacK_4_fun}E\x1cTA'

最后

这两个连起来还是有点意思的，整个做题的过程还是很满足的，一些探索并记录吧。