• 参考文章：Coppersmith 相关攻击 - CTF Wiki

  • 参考文章：Franklin-Reiter相关消息攻击-CSDN博客

  • 参考论文：3-540-68339-9_1.pdf

  • 参考论文：33860001.pdf

  • 在网上看了很多博客文章，大部分的博客文章只记录了两个消息线性关系的这种情况，但是个人认为这只是Franklin-Reiter攻击的一种。消息相关攻击又不是只有线性相关，消息满足非线性相关的情况也是存在的，但是这种情况目前我没有翻到相关博客，希望能找到篇宝藏博客（看论文太累了）

前言与介绍

对于RSA加密相关攻击中，有一个Franklin-Reiter攻击，该攻击也被称为Related Message Attack（即相关消息攻击）。该攻击针对的具体是在RSA加密中什么情况下的一个攻击呢？通过阅读论文，总结了如下几种类型的攻击，从特殊情况到一般情况。

通过阅读论文，相关消息攻击一共分为以下几种情况，在这篇论文 3-540-68339-9_1.pdf 从特殊到一般情况研究，给出了一下三种情况，论文中使用：使用kk，表示消息mim_i的个数；使用ee表示RSA加密的公钥ee；使用pp表示消息直接满足的多项式，以及使用δ\delta表示该多项式的次数。

  • 先从k=2,e=3,δ=1k=2,e=3,\delta=1这种情况来考虑：

    • 其实也就是两个消息m1,m2m_1,m_2，满足一个一次多项式关系m1=p(m2)=am2+bm_1=p(m_2)=am_2+b
    • 并且已知下面式子中的c1,c2,n,ec_1,c_2,n,e，以及多项式pp的系数和常数项

    c1≡m1e mod( n)c2≡m2e mod( n)c_1\equiv m_1^{e}~mod(~n)\\c_2\equiv m_2^{e}~mod(~n)

    • 已知上述情况可以推导出使用f(x)=xe−c1 mod( n)f(x)=x^{e}-c_1~mod(~n)与f(p(x))=(ax+b)e−c2 mod( n)f(p(x))=(ax+b)^{e}-c_2~mod(~n)有最大公因式x−m1x-m_1，从而使用求最大公因式的方法可以求出m1m_1
    • 之后进一步探究了e的一般情况，得出结论：使用更高效的求最大公因式方法，可以使得对于ee在32bit大小的情况下这个攻击也是能实现的。

  • 再从k=2,e∈Z+,δ∈Z+k=2,e\in Z_+,\delta\in Z_+这种情况研究：

    • 也就是两个消息m1,m2m_1,m_2，满足一个δ\delta次的多项式关系m2=p(m1)=cδm1δ+cδ−1m1δ−1+...+c0m_2=p(m_1)=c_{\delta}m_1^{\delta}+c_{\delta-1}m_1^{\delta-1}+...+c_0
    • 并且已知下面式子中的c1,c2,n,ec_1,c_2,n,e，以及多项式pp的系数和常数项

    c1=m1e mod( n)c2=m2e mod( n)c_1=m_1^{e}~mod(~n)\\ c_2=m_2^{e}~mod(~n)

    • 已知上述情况可以推导出一般情况g(x)=gcd(f(x),f(p(x)))g(x)=gcd(f(x),f(p(x)))，则(x−m1)∣g(x)(x-m_1)|g(x)，特殊情况下g(x)=x−m1g(x)=x-m_1，还存在无解的情况，也就是当p(x)=xhq(xe)p(x)=x^{h}q(x^{e})，此时c1=c2h(q(c1))ec_1=c_2^{h}(q(c_1))^{e}

  • 之后继续讨论了k=2,e∈Z+,δ∈Z+k=2,e\in Z_+,\delta\in Z_+这种情况，此时多项式并不是类似于上一个显式的多项式，而是隐式多项式。

    • 也就是两个消息m1,m2m_1,m_2，满足一个的δ\delta次的多项式关系p(m1,m2)=0 mod( n)p(m_1,m_2)=0~mod(~n)，例如：p(m1,m2)=am12+bm22p(m1,m2)=am_1^{2}+bm_2^{2}这样的隐函数。
    • 并且已知下面式子中的c1,c2,n,ec_1,c_2,n,e，以及多项式pp的系数和常数项

    P1=p(m1,m2)=0 mod( n)P2=m1e−c1=0 mod( n)P3=m2e−c2=0 mod( n)P_1=p(m_1,m_2)=0~mod(~n)\\ P_2=m_1^{e}-c_1=0~mod(~n)\\ P_3=m_2^{e}-c_2=0~mod(~n)

    • 这个时候论文为了讨论算法的复杂度，就使用了结式和最大公因式的方法求解（具体求解方法我也没懂）。
    • 在讨论这种情况的最后论文作者还点名了结式和最大公因式的方法都可以归入Gröbner基这一通用框架中。

  • 论文最后讨论k∈Z+,e∈Z+,δ∈Z+k\in Z_+,e\in Z_+,\delta\in Z_+这一情况：

    • 也就是已知kk个消息m1,m2,...,mkm_1,m_2,...,m_k，满足一个δ\delta次的隐式多项式p(m1,m2,...,mk)p(m_1,m_2,...,m_k)
    • 并且已知下面式子中的c1,c2,...,ci,n,ec_1,c_2,...,c_i,n,e，以及多项式pp的系数和常数项

    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)\begin{array}{l} P_0(x_1,....,x_k)=p(x_1,...,x_k)=0~mod(~n)\\ P_1(x_1)=x_1^e-c_1=0~mod(~n)\\ P_2(x_2)=x_2^{e}-c_2=0~mod(~n)\\ ....\\ P_i(x_i)=x_i^{e}-c_i=0~mod(~n)\\ ....\\ P_k(x_k)=x_k^{e}-c_k=0~mod(~n) \end{array}

    • 这个时候直接使用Gröbner基一把梭，或者使用结式与gcd结合求解即可。

通过阅读另一篇论文，也就是这篇论文 33860001.pdf 会发现一个另一种情形下的相关消息攻击。

  • 该论文讨论的是另一种线性相关消息的攻击，即k∈Z+,e∈Z+,δ=1k\in Z_+,e\in Z_+,\delta=1这种情况。

    • 此时我们并不知道原消息mm，通过RSA加密后c=me mod(n)c=m^e~mod(n)，的密文。但是我们知道ee个线性相关的消息mi=aim+bi,i=0,1,...,e−1m_i=a_im+b_i,i=0,1,...,e-1，ci=mie mod( n)c_i=m_i^e~mod(~n)，以及线性相关多项式的系数ai、bia_i、b_i。
    • 所以列出式子就有如下：

    mi=pi(m)=aim+bici=mie mod( n)m_i=p_i(m)=a_im+b_i\\ c_i=m_i^e~mod(~n)

    • 这种情况使用线性代数的方法是可以求解的，但是从算法的角度上来看效率可能会更低，所以仍然要另辟蹊径。

疑问：这里其实我还是有个疑问，为什么Franklin-Reiter攻击在CTF Wiki中会被放在Coppersmith相关攻击这篇文章内容里面呢？（先不管这个问题，接下去看看）

两个消息线性关系

  • 该部分研究的就是第一个论文的第一种情况，即k=2,δ=1k=2,\delta=1而e∈Z+e\in Z+这一情况。

  • 接下来根据已知的数学条件，就需要来进行推导与分析了。下面先列出一些列的已知条件：

  • 首先就是RSA加密，可以得到如下这个条件：

c1≡m1e mod (n)c2≡m2e mod (n)c_1\equiv m_1^{e}~mod~(n)\\ c_2\equiv m_2^{e}~mod~(n)

  • 其次两个被加密的消息满足线性关系，则有如下条件，其中a、b是已知的：

m1=am2+bm1≡am2+b mod (n)\begin{array}{l} m_1 = am_2+b\\ m_1 \equiv am_2+b~mod~(n) \end{array}

e为3的情况

  • 对于一般的情况现在我们还不清楚，先采用解剖麻雀的方法，取一个e=3的情况对这个条件进行研究看看。先将题目已知列出来，从该攻击针对的情况，可以得到这三个基础的式子，其中c1、c2、a、b是已知的，三个方程两个未知数，一般都是可以解出方程的：

c1≡m13 mod (n)c2≡m23 mod (n)m1=a∗m2+b\begin{array}{l} c_1 \equiv m_1^{3}~mod~(n)\\ c_2 \equiv m_2^{3}~mod~(n)\\ m_1 = a*m_2+b \end{array}

  • 那么接下来就来推导一下这个式子，推导式子的过程中有比较灵活的代换以及因式分解，但是要记住一点代换的目的就是为了降幂，与解方程一样：

    • 首先由c1≡m13 mod (n)c_1\equiv m_1^{3}~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)c_2\equiv m_2^{3}~mod~(n)，两边先同时乘上a3a^{3}，再同时减去b3b^{3}可以得到：

    a3c2−b3≡(am2)3−b3≡(am2−b)∗[(am2)2+am2b+b2]         (2)a^{3}c_2-b^{3}\equiv (am_2)^{3}-b^{3}\equiv (am_2-b)*[(am_2)^2+am_2b+b^2]~~~~~~~~~(2)

    • 使用(1)式-(2)式可以得到一个(3)式：

    \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)\Rightarrow c_1-a^{3}c_2+2b^{3}\equiv3b[(am_2)^{2}+(am_2)b+b^{2}]~mod~(n)~~~~~~~(3)

    • 这个时候就要回到(2)式，代换立方差的那一部分公式[(am2)2+(am2)b+b2][(am_2)^{2}+(am_2)b+b^{2}]，这样就可以得到：

    c1−a3c2+2b3≡3ba3c2−b3am2−b mod (n)c_1-a^{3}c_2+2b^{3}\equiv3b\frac{a^{3}c_2-b^{3}}{am_2-b}~mod~(n)

    • 最后将(am2−b)(am_2-b)移动到左边：

    (am2−b)≡3ba3c2−b3c1−a3c2+2b3 mod (n)(am_2-b)\equiv3b\frac{a^{3}c_2-b^{3}}{c_1-a^{3}c_2+2b^{3}}~mod~(n)

    • 最终就得到：

    m2≡3ba3c2−b3a∗(c1−a3c2+2b3)+ba=ba(c1+2a3c2−b3c1−a3c2+2b2) mod (n)m_2\equiv3b\frac{a^{3}c_2-b^{3}}{a*(c_1-a^{3}c_2+2b^{3})}+\frac{b}{a}=\frac{b}{a}(\frac{c_1+2a^{3}c_2-b^{3}}{c_1-a^{3}c_2+2b^{2}})~mod~(n)

e为任意的情况

  • 按照上面的推导方法，最终可以得到一般情况：

m2=e∗ba(aec2−bec1−aec2+(e−1)be+1) mod( n)m_2 = e*\frac{b}{a}(\frac{a^{e}c_2-b^{e}}{c_1-a^{e}c_2+(e-1)b^{e}}+1)~mod(~n)

  • 现在其实我们可以明确的一点是，如果两个相同的公钥e加密两个明文m1,m2，得到c1,c2，这两个明文其中可以先解出m2，然后根据线性关系，其实还可以解出m1。那这就相当于明文可以被破解了，这种其实属于代数可解。

  • 既然该式子是代数可解，那么为什么不使用公式法直接求m2呢？是因为这样套公式计算确实比较复杂，当e很大的时候可能精度会损失，以及计算效率低。

另辟蹊径之求最大公因式

推导

此时其实就需要另辟蹊径了。通过研究这个式子就会发现:

  • 多项式f(x)=xe−c1 mod( n)=0f(x)=x^{e}-c_1~mod(~n)=0的一个解为x=m2x=m_2，所以该多项式可以因式分解成f(x)=(x−m2)g1(x)f(x)=(x-m_2)g_1(x)

  • 而另一个多项式f(p(x))=(ax+b)e mod( n)=0f(p(x))=(ax+b)^{e}~mod(~n)=0的一个解也为x=m2x=m_2，所以该多项式可以因式分解成f(p(x))=(x−m2)g2(x)f(p(x))=(x-m_2)g_2(x)

  • 所以gcd(f(x),f(p(x)))=(x−m2)gcd(f(x),f(p(x)))=(x-m_2)，此时就将使用公式求解转换成求两个多项式的最大公因式，这样可以避免除法并且可以提高计算效率。

对于编写求解最大公因式的算法，其实用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)) # 创建一个模n下的多项式环,环的名称为PR,该环的变量为x
    f = x^e - c1 
    g = (a*x+b)^e - c2
    while f:
        g,f = f,g % f
    g = g.monic() # 将g转换为首一多项式,也就是该多项式次数最高次这一项系数为1的多项式
    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)) # 创建一个模n下的多项式环,环的名称为PR,该环的变量为x
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)) # 创建一个模n下的多项式环,环的名称为PR,该环的变量为x
    f = x^e - c1 
    g = (a*x+b)^e - c2
    G = PR(f._pari_with_name('x').gcd(g._pari_with_name('x'))) # PR()将求得的公因式转换到PR环上
    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)\begin{array}{l} m_2=am_1+b\\ c_1=m_1^{17}~mod(~n)\\ c_2=m_2^{17}~mod(~n) \end{array}

由m1、m2m_1、m_2的线性关系可以带入c2=m217 mod( n)c_2=m_2^{17}~mod(~n)就可以得到如下式子：

c2=(am1+b)17 mod( n)c_2=(am_1+b)^{17}~mod(~n)

由前面的另辟蹊径就能知道，多项式f(x)=x17−c1 mod( n)f(x)=x^{17}-c_1~mod(~n)与多项式g(x)=(ax+b)17−c2 mod( n)g(x)=(ax+b)^{17}-c_2~mod(~n)有公因式(x−m1)(x-m_1)。

从而将问题转变为求解这两个多项式的最大公因式，即可得到原来的明文m1m_1，思路已经有了，现在直接编写exp即可。

  • 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)) # 创建一个模n下的多项式环,环的名称为PR,该环的变量为x
f = x^e - c1 
g = (a*x+b)^e - c2
while f:
    g,f = f,g % f   # 使用辗转相除法求得多项式最大公因式
print(g)
g = g.monic() # 将g转换为首一多项式,也就是该多项式次数最高次这一项系数为1的多项式
print(g)
# 提取该多项式的常数项,但是发现常数项不是负数,所以该数其实并不是真正的m,而n-m才是真正的m
m = g.constant_coefficient() 
print(long_to_bytes(int(n-m)))
# b'flag{a593591a-3749-cc52-0c27-e897fac2c967}'

例题2

  • 接下来稍微修改一下例题1，将e=17，替换成e=65537

  • 题目附件如下：

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'))
  • 完整的exp如下：
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)) # 创建一个模n下的多项式环,环的名称为PR,该环的变量为x
    f = x^e - c1 
    g = (a*x+b)^e - c2
    G = PR(f._pari_with_name('x').gcd(g._pari_with_name('x'))) # PR()将求得的公因式转换到PR环上
    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求出结果呢？带着这个疑问来探究探究，如果探究出来了目前就不把题目放在这里了，直接把这题当做题目出出来。（斜眼笑）

两个消息非线性关系

多个消息多项式关系

多个消息多个线性关系