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)$ 。
有限域中多项式最大公因式提取 首先是需要会普通的多项式因式分解。
然后是需要会有限域中的多项式因式分解。
然后是需要通过辗转相除法求两个多项式的最大公因式。(即该公因式可以整除两者的所有因式。
攻击的原理如下:
首先已知条件为待加密的消息 $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$ ,然后发送了消息。
此时有:
则对于方程 $f^e(x) - c_1 \equiv 0 \pmod n$ 而言,很显然 $m_2$ 是一个根。
而同时又有
所以对于方程 $x^e -c_2 \equiv 0 \pmod n$ 而言,很显然 $m_2$ 也是一个根。
所以对于以下方程组
多项式 $(x-m_2)$ 都可以被提取出来。则可以通过对上述方程求解“最大公因子”,如果求解出来的最大公因式刚好是线性关系,则就成功得到了 $m_2$ 。
e = 3 特别地,在加密指数 $e=3$ 时,得到的一定是线性关系,这里可以对 $e=3$ 时进行一个推导。
首先是已知条件
已知明文消息之间存在线性关系,不妨设为:
于是将 $(5)$ 带入 $(4)$ 有
然后我们将 $(6)$ 用立方公式打开有
然后再构造一个立方差
然后再将 $(7)$ 加上 $2b^3$ 再减去 $2b^3$ 以构造出 $(8)$ 中的部分 $(a^2m_2^2+am_2b+b^2)$ ,如下
于是将 $(9)$ 再推一步,有
再联立 $(10) (8)$ 可以得到
进而有
于是可以看到,等式右侧都是已知量,也就是我们可以求出 $m_2$ 。
再通过 $m_1 = am_2+b$ 可以求得 $m_1$ 。
更详细的过程,请参阅 paper 。
例题 题目
试试相关消息吧
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 from secret import flagimport gmpy2from Crypto.Util.number import getPrime, bytes_to_longimport randomp = 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$ 这种简单的情形。
只是这里需要稍微注意一下:
也就是说, $a = a_1a_2^{-1}$ , $b = b_1-a_1a_2^{-1}b_2$ 。
解密脚本如下:
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 import gmpy2from Crypto.Util.number import getPrime, long_to_bytesa1=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) % nm1 = (m_2 - b2)*gmpy2.invert(a2, n) % n flag = long_to_bytes(m1) print (flag)
短填充攻击 目前很多 RSA 题目都会进行填充,即在待加密明文的之后再拼接一定的 padding。
如果填充内容过短会怎样呢?
事实上,考虑到前面 Related Message Attack
中的情况,就是 b
会很小,以至于根就会很小。
题目 就是给了 server.py
文件,还有个流量分析的文件 ,然后还有就是一个公钥文件 。
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 from Crypto.PublicKey import RSAfrom Crypto.Util.number import *import gmpy2, randomfrom secret import m, flagassert m[-38 :] == flagassert 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可以直接复制字符串,但我不会用。
1 2 def get_cipher (data ): return "" .join(map (lambda x: chr (int (x, 16 )), data.split(":" )))
然后大概就是这样,就能得到两组密文
密文如下
1 2 3 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$ 。
可疑的地方有:
$e$ 比较小,值得怀疑。
给了两组密文 $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 于是,问题就迎刃而解了:
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 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 ] 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))
最后 这两个连起来还是有点意思的,整个做题的过程还是很满足的,一些探索并记录吧。