前言与介绍
对于RSA
加密相关攻击中,有一个Franklin-Reiter攻击
,该攻击也被称为Related Message Attack
(即相关消息攻击)。该攻击针对的具体是在RSA
加密中什么情况下的一个攻击呢?通过阅读论文,总结了如下几种类型的攻击,从特殊情况到一般情况。
通过阅读论文,相关消息攻击一共分为以下几种情况,在这篇论文 3-540-68339-9_1.pdf 从特殊到一般情况研究,给出了一下三种情况,论文中使用:使用k,表示消息mi的个数;使用e表示RSA加密的公钥e;使用p表示消息直接满足的多项式,以及使用δ表示该多项式的次数。
-
先从k=2,e=3,δ=1这种情况来考虑:
- 其实也就是两个消息m1,m2,满足一个一次多项式关系m1=p(m2)=am2+b
- 并且已知下面式子中的c1,c2,n,e,以及多项式p的系数和常数项
c1≡m1e mod( n)c2≡m2e mod( n)
- 已知上述情况可以推导出使用f(x)=xe−c1 mod( n)与f(p(x))=(ax+b)e−c2 mod( n)有最大公因式x−m1,从而使用求最大公因式的方法可以求出m1
- 之后进一步探究了
e
的一般情况,得出结论:使用更高效的求最大公因式
方法,可以使得对于e在32bit
大小的情况下这个攻击也是能实现的。
-
再从k=2,e∈Z+,δ∈Z+这种情况研究:
- 也就是两个消息m1,m2,满足一个δ次的多项式关系m2=p(m1)=cδm1δ+cδ−1m1δ−1+...+c0
- 并且已知下面式子中的c1,c2,n,e,以及多项式p的系数和常数项
c1=m1e mod( n)c2=m2e mod( n)
- 已知上述情况可以推导出一般情况g(x)=gcd(f(x),f(p(x))),则(x−m1)∣g(x),特殊情况下g(x)=x−m1,还存在无解的情况,也就是当p(x)=xhq(xe),此时c1=c2h(q(c1))e
-
之后继续讨论了k=2,e∈Z+,δ∈Z+这种情况,此时多项式并不是类似于上一个显式的多项式,而是隐式多项式。
- 也就是两个消息m1,m2,满足一个的δ次的多项式关系p(m1,m2)=0 mod( n),例如:p(m1,m2)=am12+bm22这样的隐函数。
- 并且已知下面式子中的c1,c2,n,e,以及多项式p的系数和常数项
P1=p(m1,m2)=0 mod( n)P2=m1e−c1=0 mod( n)P3=m2e−c2=0 mod( n)
- 这个时候论文为了讨论算法的复杂度,就使用了
结式
和最大公因式
的方法求解(具体求解方法我也没懂)。
- 在讨论这种情况的最后论文作者还点名了
结式
和最大公因式
的方法都可以归入Gröbner基
这一通用框架中。
-
论文最后讨论k∈Z+,e∈Z+,δ∈Z+这一情况:
- 也就是已知k个消息m1,m2,...,mk,满足一个δ次的隐式多项式p(m1,m2,...,mk)
- 并且已知下面式子中的c1,c2,...,ci,n,e,以及多项式p的系数和常数项
P0(x1,....,xk)=p(x1,...,xk)=0 mod( n)P1(x1)=x1e−c1=0 mod( n)P2(x2)=x2e−c2=0 mod( n)....Pi(xi)=xie−ci=0 mod( n)....Pk(xk)=xke−ck=0 mod( n)
- 这个时候直接使用
Gröbner基
一把梭,或者使用结式
与gcd
结合求解即可。
通过阅读另一篇论文,也就是这篇论文 33860001.pdf 会发现一个另一种情形下的相关消息攻击。
疑问:这里其实我还是有个疑问,为什么Franklin-Reiter攻击
在CTF Wiki
中会被放在Coppersmith相关攻击
这篇文章内容里面呢?(先不管这个问题,接下去看看)
两个消息线性关系
-
该部分研究的就是第一个论文的第一种情况,即k=2,δ=1而e∈Z+这一情况。
-
接下来根据已知的数学条件,就需要来进行推导与分析了。下面先列出一些列的已知条件:
-
首先就是RSA
加密,可以得到如下这个条件:
c1≡m1e mod (n)c2≡m2e mod (n)
- 其次两个被加密的消息满足线性关系,则有如下条件,其中
a
、b
是已知的:
m1=am2+bm1≡am2+b mod (n)
e为3的情况
- 对于一般的情况现在我们还不清楚,先采用解剖麻雀的方法,取一个
e=3
的情况对这个条件进行研究看看。先将题目已知列出来,从该攻击针对的情况,可以得到这三个基础的式子,其中c1、c2、a、b
是已知的,三个方程两个未知数,一般都是可以解出方程的:
c1≡m13 mod (n)c2≡m23 mod (n)m1=a∗m2+b
-
那么接下来就来推导一下这个式子,推导式子的过程中有比较灵活的代换
以及因式分解
,但是要记住一点代换的目的就是为了降幂,与解方程一样:
- 首先由c1≡m13 mod (n),可以得到:
\begin{align*}
c_1&\equiv (a*m_2+b)^{3}\\
&\equiv (am_2)^{3}+3(am_2)^{2}b+3(am_2)b^{2}+b^{3}\\
&\equiv (am_2)^{3}-2b^{3}+3b[(am_2)^{2}+(am_2)b+b^{2}]~mod~(n)~~~~~~~~~(1)
\end{align*}
- 其次由c2≡m23 mod (n),两边先同时乘上a3,再同时减去b3可以得到:
a3c2−b3≡(am2)3−b3≡(am2−b)∗[(am2)2+am2b+b2] (2)
\begin{align*}
c_1-a^{3}c_2+b^{3}&\equiv (am_2)^{3}-2b^{3}+3b[(am_2)^{2}+(am_2)b+b^{2}]-(am_2-b)*[(am_2)^2+am_2b+b^2]\\
&\equiv (am_2)^{3}-b^{3} -(am_2-b)*[(am_2)^2+am_2b+b^2]+ 3b[(am_2)^{2}+(am_2)b+b^{2}] - b^{3}\\
&\equiv 3b[(am_2)^{2}+(am_2)b+b^{2}] - b^{3}~mod~(n)
\end{align*}
⇒c1−a3c2+2b3≡3b[(am2)2+(am2)b+b2] mod (n) (3)
- 这个时候就要回到
(2)
式,代换立方差的那一部分公式[(am2)2+(am2)b+b2],这样就可以得到:
c1−a3c2+2b3≡3bam2−ba3c2−b3 mod (n)
- 最后将(am2−b)移动到左边:
(am2−b)≡3bc1−a3c2+2b3a3c2−b3 mod (n)
m2≡3ba∗(c1−a3c2+2b3)a3c2−b3+ab=ab(c1−a3c2+2b2c1+2a3c2−b3) mod (n)
e为任意的情况
m2=e∗ab(c1−aec2+(e−1)beaec2−be+1) mod( n)
-
现在其实我们可以明确的一点是,如果两个相同的公钥e
加密两个明文m1,m2
,得到c1,c2
,这两个明文其中可以先解出m2
,然后根据线性关系,其实还可以解出m1
。那这就相当于明文可以被破解了,这种其实属于代数可解。
-
既然该式子是代数可解,那么为什么不使用公式法直接求m2
呢?是因为这样套公式计算确实比较复杂,当e
很大的时候可能精度会损失,以及计算效率低。
另辟蹊径之求最大公因式
推导
此时其实就需要另辟蹊径了。通过研究这个式子就会发现:
-
多项式f(x)=xe−c1 mod( n)=0的一个解为x=m2,所以该多项式可以因式分解成f(x)=(x−m2)g1(x)
-
而另一个多项式f(p(x))=(ax+b)e mod( n)=0的一个解也为x=m2,所以该多项式可以因式分解成f(p(x))=(x−m2)g2(x)
-
所以gcd(f(x),f(p(x)))=(x−m2),此时就将使用公式求解转换成求两个多项式的最大公因式,这样可以避免除法并且可以提高计算效率。
对于编写求解最大公因式的算法,其实用Sagemath是最方便的,所以这里就直接使用Sagemath求解最大公因式。这里给出几个SageMath
求解最大公因式的几个代码。以及加快求解最大公因式的方法Half-gcd
的代码以及算法推导公式。
代码1——普通多项式gcd
- 代码一,使用
Sagemath
编写多项式gcd
算法:
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.Util.number import * n= a= c1= c2= e =
def Franklin(n,e,a,b,c1,c2): """ n: 模数 e: 指数 a: 线性关系中am+b中的a b: 线性关系中am+b中的b c1: f = x^e - c1 中的c1,也就是没有被线性变换过的加密密文 c2: 线性变换过的加密密文 return value: int->m """ PR.<x> = PolynomialRing(Zmod(n)) f = x^e - c1 g = (a*x+b)^e - c2 while f: g,f = f,g % f g = g.monic() m = g.constant_coefficient() if m > 0: return int(n-m) else: return int(m) m = Franklin(n,e,a,b,c1,c2) print(long_to_bytes(m))
|
代码2——多项式Half-gcd
进入正题:
代码3——Sagemath一把梭
- 代码三,使用
sagemath
其实没有快速计算gcd
的方法,但是sagemath
中有内置的PARI/GP
库(也是一个常用于数学的编程语言),所以可以将Sagemath中的PolynomialRing()
这个多项式先转换为PARI/GP
内置多项式类型。
- 之后再使用
PARI/GP
内置的gcd
快速求解两个多项式的最大公因式,而PARI/GP
内置的快速求解两个多项式的最大公因式的方法其实就是使用的Half-gcd
。代码如下:
1 2 3 4 5 6 7 8 9 10
| PR.<x> = PolynomialRing(Zmod(n)) f = g =
G = PR(f._pari_with_name('x').gcd(g._pari_with_name('x')))
f_pari = f._pari_with_name('x') g_pari = g._pari_with_name('x') G = f_pari.gcd(g_pari)
|
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
| from Crypto.Util.number import * n = a = b = c1 = c2 = e =
def Franklin(n,e,a,b,c1,c2): """ n: 模数 e: 指数 a: 线性关系中am+b中的a b: 线性关系中am+b中的b c1: f = x^e - c1 中的c1,也就是没有被线性变换过的加密密文 c2: 线性变换过的加密密文 return value: int->m """ PR.<x> = PolynomialRing(Zmod(n)) f = x^e - c1 g = (a*x+b)^e - c2 G = PR(f._pari_with_name('x').gcd(g._pari_with_name('x'))) print(G) G = G.monic() print(G) m = G.constant_coefficient() return int(m) m = Franklin(n,e,a,b,c1,c2) print(m) print(long_to_bytes(int(m))) print(n-m) print(long_to_bytes(int(n-m)))
|
例题
例题1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| from secret import flag from Crypto.Util.number import *
m1 = bytes_to_long(flag) N = getPrime(512)*getPrime(512) e = 17
c1 = pow(m1, e, N)
a = getRandomNBitInteger(512) b = getRandomNBitInteger(512) m2 = a * m1 + b c2 = pow(m2, e, N)
print(N, a, b, c1, c2, sep="\n")
""" n=51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741 a=13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967 b=12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170 c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142 c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720 """
|
此题是一个比较典型的相关消息攻击,通过题目附件的代码有如下已知条件:
m2=am1+bc1=m117 mod( n)c2=m217 mod( n)
由m1、m2的线性关系可以带入c2=m217 mod( n)就可以得到如下式子:
c2=(am1+b)17 mod( n)
由前面的另辟蹊径就能知道,多项式f(x)=x17−c1 mod( n)与多项式g(x)=(ax+b)17−c2 mod( n)有公因式(x−m1)。
从而将问题转变为求解这两个多项式的最大公因式,即可得到原来的明文m1,思路已经有了,现在直接编写exp即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| from Crypto.Util.number import * n=51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741 a=13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967 b=12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170 c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142 c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720 e = 17
PR.<x> = PolynomialRing(Zmod(n)) f = x^e - c1 g = (a*x+b)^e - c2 while f: g,f = f,g % f print(g) g = g.monic() print(g)
m = g.constant_coefficient() print(long_to_bytes(int(n-m)))
|
例题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 uuid from Crypto.Util.number import * flag = b'flag{' + str(uuid.uuid4()).encode() + b'}' m1 = bytes_to_long(flag) N = getPrime(512)*getPrime(512) e = 65537
c1 = pow(m1, e, N)
a = getRandomNBitInteger(512) b = getRandomNBitInteger(512) m2 = a * m1 + b c2 = pow(m2, e, N) print("n =",N) print("a =",a) print("b =",b) print("c1 =",c1) print("c2 =",c2)
""" n = 59861917324226967486215648256894012851495145204497486380891167740615801374063455379673715500954583547144532511038617630076588124328491649811856993314542460125128961468483743038573111414419166480096592264420724034747983484148465064161457578180902917692815465155951262833991421445819783698766048087026362827177 a = 8912027245219554871633263198357534861260151492942640613543674312789184411070375687173938678863885846785442731416745232377239461392819384805757821014008997 b = 9082019118159490199184118787363903212978739183503144824083405972098784434747374470051472810662991934944899511831981983317873229914591770162089271570548898 c1 = 13829716726154552626808370709385622815070337340315816233387666503855034657492722518838631908542319087651252784674601561198457938726403898164944489259977862308799162509306623034533701622307267177872660177001435552253633489217686479650060107252554076305263872524702049994229524235844714514276932861812294412208 c2 = 12344340068962283228603202053643543482434797000939385457621435796626275462396259806353278281512262932359248462422732215649437185890052207218476381335849291479672021635844167181113351805907880675672544417067152443404516325590447421944842581421615420605120177863329347579906535387550917852112995890140027254347 """
|
思路大致是和例题1一样的,但是这题如果使用例题1的exp需要跑很久的。原因:e太大了,导致多项式次数和系数的比较大,使得计算所花费的时间和算力都非常多
此时就需要对辗转相除法进行算法上的优化,所以引入了一个新的辗转相除法,也就是Half-gcd
算法。下面主要讲解的就是这个算法的具体过程以及算法实现的具体代码。
这里就贴一个Half-gcd
的论文,Half-gcd
的详细过程放在代码2那边讲解,那边也贴个论文:(PDF) Half-GCD and fast rational recovery
- 这里给出一个
Sagemath
自带的快速计算两个多项式最大公因式的方法:
1
| f._pari_with_name('x').gcd(g._pari_with_name('x'))
|
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 39
| from Crypto.Util.number import * n = 59861917324226967486215648256894012851495145204497486380891167740615801374063455379673715500954583547144532511038617630076588124328491649811856993314542460125128961468483743038573111414419166480096592264420724034747983484148465064161457578180902917692815465155951262833991421445819783698766048087026362827177 a = 8912027245219554871633263198357534861260151492942640613543674312789184411070375687173938678863885846785442731416745232377239461392819384805757821014008997 b = 9082019118159490199184118787363903212978739183503144824083405972098784434747374470051472810662991934944899511831981983317873229914591770162089271570548898 c1 = 13829716726154552626808370709385622815070337340315816233387666503855034657492722518838631908542319087651252784674601561198457938726403898164944489259977862308799162509306623034533701622307267177872660177001435552253633489217686479650060107252554076305263872524702049994229524235844714514276932861812294412208 c2 = 12344340068962283228603202053643543482434797000939385457621435796626275462396259806353278281512262932359248462422732215649437185890052207218476381335849291479672021635844167181113351805907880675672544417067152443404516325590447421944842581421615420605120177863329347579906535387550917852112995890140027254347 e = 65537
def Franklin(n,e,a,b,c1,c2): """ n: 模数 e: 指数 a: 线性关系中am+b中的a b: 线性关系中am+b中的b c1: f = x^e - c1 中的c1,也就是没有被线性变换过的加密密文 c2: 线性变换过的加密密文 return value: int->m """ PR.<x> = PolynomialRing(Zmod(n)) f = x^e - c1 g = (a*x+b)^e - c2 G = PR(f._pari_with_name('x').gcd(g._pari_with_name('x'))) print(G) G = G.monic() print(G) m = G.constant_coefficient() return int(m) m = Franklin(n,e,a,b,c1,c2) print(m) print(long_to_bytes(int(m))) print(n-m) print(long_to_bytes(int(n-m))) """ 59861917324226967486215648256894012851495145204497486380891167740615801374063455379673715500954583547144532511038617630076588124328491649811856993314542460125128961468483743038573111414419166480096592264420668028355190078995842814841648310810119551192062039646311316624372659583573767360517334407327685140012 b'U?\x06\xf5\x0e\xa7\x87zS\xa4\x188l\x80\x11\xb3+\x857v\x00\x1a\xb8\xe6J\x03\x89\x99)Q\x1aA\xf5i\x80@\xe5\xde\xa7I\xcf\x06-K\x08\xca\xb7\xa5\xf4\xd6\xb1mGP\x06\xfd\xbb\xaf\xb7 M\x99\xf0Ir\xefg\xb9\xf9WkA#Y>"\xd6U48h\x1f\x7f\x18~\x84\xff\xc1e\n\x7f\xc3\xf0\xe6n\xfa\x17\xec\xf1\xd5\xdd\x08\xeb9T]x\x1f=\xb7\xb9\xc8\x9e\x1f\x94@=\xd5\xc3\xa4l)_\x81\xdd\xe9\xde,' 56006392793405152622249319809267370783366500753425509639946209618761862246016338248713679698677687165 b'flag{4eebce90-3a9f-4ba4-a75a-a434b915037c}' """
|
例题3
想法
前面三个例题都是关于直线的线性关系,那么如果是其他线性关系是不是也能这样直接gcd
求出结果呢?带着这个疑问来探究探究,如果探究出来了目前就不把题目放在这里了,直接把这题当做题目出出来。(斜眼笑)
两个消息非线性关系
多个消息多项式关系
多个消息多个线性关系