一、原理

攻击条件

$$当A使用同一公钥对两个具有某种线性关系的M_1与M_2进行加密，并将加密后的消息C_1，C_2发送给B$$
$$M_1,M_2具有某种线性关系：M_1 \equiv f(M_2) \pmod N，其中f为一个线性函数$$
$$在具有较小错误概率下的情况下，其复杂度为O(e \log_2 N)$$

攻击原理

$$已知C_1 \equiv M_1^e \pmod N,且M_1 \equiv f(M_2) \pmod N$$
$$那么M_2是方程f(x)^e \equiv C_1 \pmod N的一个解，即M_2是方程f(x)^e-C_1在模N下的一个根$$
$$且M_2是x^e-C_2在模N意义下的一个根，那么x-M_2同时整除上述两个多项式$$
$$故可以求得两个多项式的最大公因子，若最大公因子是线性的，那么就求到了M_2$$

e=3时：最大公因子一定是线性的

二、例题

1、

题目

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")

51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741

13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967

12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170

18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142

14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720

解答

import libnum
n=51296885372346449295388453471330409021784141081351581975478435681552082076338697136130122011636685327781785488670769096434920591920054441921039812310126089859349902066456998315283909435249794317277620588552441456327265553018986591779396701680997794937951231970194353001576159809798153970829987274504038146741
a=13256631249970000274738888132534852767685499642889351632072622194777502848070957827974250425805779856662241409663031192870528911932663995606616763982320967
b=12614470377409090738391280373352373943201882741276992121990944593827605866548572392808272414120477304486154096358852845785437999246453926812759725932442170
c1=18617698095122597355752178584860764221736156139844401400942959000560180868595058572264330257490645079792321778926462300410653970722619332098601515399526245808718518153518824404167374361098424325296872587362792839831578589407441739040578339310283844080111189381106274103089079702496168766831316853664552253142
c2=14091361528414093900688440242152327115109256507133728799758289918462970724109343410464537203689727409590796472177295835710571700501895484300979622506298961999001641059179449655629481072402234965831697915939034769804437452528921599125823412464950939837343822566667533463393026895985173157447434429906021792720
e=17
import binascii
def franklinReiter(n,e,c1,c2,a,b):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (x)^e - c1
    g2 = (a*x+b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 
    return -gcd(g1, g2)[0]

m=franklinReiter(n,e,c1,c2,a,b)
print(libnum.n2s(int(m)))

flag{a593591a-3749-cc52-0c27-e897fac2c967}

思路

相关消息攻击，找到最大公因子。用辗转相除法求多项式的最大公因子

def gcd(g1, g2):
    while g2:
        g1, g2 = g2, g1 % g2  # 计算多项式 GCD
    return g1.monic()  # 返回常数项即 M2

通过反复取模来逐步缩小多项式的次数，直到g2为0，此时g1就是最大公因子
一个多项式的首项系数称为引导系数，g.monic()[0]返回g(x)除以引导系数后得到的常数项

2、NeepuSec CTF

题目

from Crypto.Util.number import *
from sympy import nextprime
import gmpy2
import random

def encode (p1,p2,e):
    not_hint = (p1 + 1) * (p2 + 1)
    S = gmpy2.invert(e, not_hint)
    not_p = S%(p1+1)
    return not_p

flag = b'Neepu{********************}'
flag = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = nextprime(random.randint(1,1000))
d = gmpy2.invert(e, (p-1)*(q-1))
c = pow(flag, e, n)
print(c)
print(n)

m = encode(p, q, e)
c1 = pow(m, 7, n)
c2 = pow(m+e, 7, n)
print(c1)
print(c2)

c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839746410486257998875782496654704288722251878269643040214139429715671
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
c1 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
c2 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119

解答1（爆破e）

from Crypto.Util.number import*
import gmpy2
from tqdm import trange
import binascii
c = 78543767285872349029076059073458316000847341792088805258173041942425687239313215276670106926320359777962661495032475004417723103701253550583245518206305422982968675291500865382213182669036827898932991063338163290845510339896689210314509493839746410486257998875782496654704288722251878269643040214139429715671
n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
c1 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
c2 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119

def franklin(n,e,c1,c2,a,b):
    PR.<x>=PolynomialRing(Zmod(n))
    g1=(x)^e-c1
    g2=(a*x+b)^e-c2
    def gcd(g1,g2):
        while g2:
            g1,g2=g2,g1%g2
        return g1.monic()
    return -gcd(g1,g2)[0]

for e in trange(1,1000):
    m_=franklin(n,7,c1,c2,1,e)
    if pow(m_,7,n)==c1:
        print(e,m_)
e=71
m_=129256555243625096140386916253259867206651269142565502540823654159666398099455456877012993395632742360829588042575108302297567291349420390228163587340859

for k in range(1,e):
    if (e*m_-1) % k ==0:
        p=(e*m_-1)//k-1
        if n%p ==0:
            q=n//p
            phi=(p-1)*(q-1)
            d=gmpy2.invert(e,phi)
            m=pow(c,d,n)
            flag=long_to_bytes(m)
            print(flag)

Neepu{Have-a-g00d-day12138}

思路

$$已知c_1 \equiv M^7 \pmod n,c_2 \equiv (M+e)^7 \pmod n，又e \in [1,1000)$$
$$那么可以对e爆破，再由相关信息攻击得到M，又M \equiv s \pmod {p+1},se \equiv 1 \pmod {p+1}$$
$$则eM \equiv 1 \pmod {p+1},则eM-1=k(p+1),又M <p+1,那么k<e$$
$$对k进行爆破，类似dp泄露，求到p和q后RSA解密即可$$

解答2（短填充攻击）

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.4)[0]  # find root < 2^kbits with factor >= n^0.4
    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]


if __name__ == '__main__':
    c2 = 10186066785511829759164194803209819172224966119227668638413350199662683285189286077736537161204019147791799351066849945954518642600518196927152098131117402608793752080104402893792812059620726950782670809837962606250674588612783027976958719051829085903720655233948024280118985875980227528403883475592567727892
    c1 = 46182103994299145562022812023438495797686077104477472631494150222038404419414100727667171290098624214113241032861128455086601197239761085752413519627251290509474327611253599768650908336142621210005389246714504358370629231557080301516460985022782887233790302054696967900384601182742759555421864610431428746119
    n = 91995272927105081122659192011056020468305570748555849650309966887236871318156855318666540461669669247866754568189179687694315627673545298267458869140096224628114424176937828378360997230874932015701507629238213240839370628366083111028544554453150572165461450371411341485911677167168492357154684642531577228543
    e = 7
    diff = short_pad_attack(c1, c2, e, n)
    print("difference of two messages is %d" % diff)
    m1 = related_message_attack(c1, c2, diff, e, n)
    print("m1:", m1)
    print("m2:", m1 + diff)

学习中待补充

3、HongKe

题目

from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537

p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')

n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

解答（常规做法）

from Crypto.Util.number import *
import gmpy2

n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005
e=65537

def Franklin(n,e,c1,c2,a,b):
    PR.<x>=PolynomialRing(Zmod(n))
    g1=x^e-c1
    g2=(a*x+b)^e-c2
    def gcd(g1,g2):
        while g2:
            g1,g2=g2,g1%g2
        return g1.monic()
    return -gcd(g1,g2)[0]

m=Franklin(n2,e,c1,c2,-1,n1)
flag=long_to_bytes(int(m))
print(flag)

这里的e很大，常规方法会非常非常慢,一两个小时能出

解答(half-gcd)

from Crypto.Util.number import *
import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

e = 65537
n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

R.<x> = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (n1 - x)^e - c2

res = GCD(f,g)
print(long_to_bytes(int(-res.monic().coefficients()[0])))

CnHongKe{Fr4nkl1n_R31ter_4nd_gcD}

三、Half gcd

1、从gcd到half gcd

$$对于之前提到的多项式gcd，其实是进行了这样一个操作：$$
$$r_{-2}=A(x),r_{-1}=B(x)$$
$$r_i=r_{i-2}-q_ir_{i-1},其中q_i=r_{i-2} // r_{i-1}$$
$$\cdots$$
$$直到r_k=0$$
$$考虑将其写成一个线性变换：$$
$$\begin {pmatrix}
0&1 \
1&{-q_i}
\end {pmatrix}
\begin {pmatrix}
r_{i-2} \
r_{i-1}
\end {pmatrix}
=\begin {pmatrix}
r_{i-1} \
r_i
\end {pmatrix}$$
$$引入一个记号：$$
$$Q_i=\begin {pmatrix}
q_i&1 \
1&0
\end {pmatrix}
\qquad
则Q_i^{-1}=
\begin {pmatrix}
0&1 \
1&{-q_i}
\end {pmatrix}$$
那么：
$$\qquad Q_k^{-1} \cdots Q_1^{-1}Q_0^{-1} \begin {pmatrix}
A(x) \
B(x)
\end {pmatrix}=
\begin {pmatrix}
gcd(A(x),B(x)) \
0
\end {pmatrix}$$
记：
$$Q_k^{-1} \cdots Q_1^{-1}Q_0^{-1}=Q^{-1}，那么Q^{-1} \begin {pmatrix}
A \
B \end {pmatrix}=\begin {pmatrix}
C \
D \end {pmatrix}$$

我们规定：这个Q必须让C和D满足：
$$degC \geq \lceil {\frac{degA}{2}} \rceil >degD$$

$$也就是说：C的次数至少是A的次数的一半，D的次数严格小于A的次数的一半$$
$$那么D的次数就被限制在一个比较小的范围内$$
$$已知degC \geq 阈值 > degD,再做一次多项式带余除法：$$
$$C=G \cdot D+E \qquad(degE<degD)$$
$$于是得到了一对新的多项式(D,E)，最高次数小于\lceil \frac{degA}{2} \rceil -1，规模减半$$
$$那么我们可以递归的使用half-gcd来处理(D,E),得到另一矩阵。$$
$$最后将这些矩阵相乘即可得到目标矩阵$$

2、脚本

import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)
n = ？
PR.<x> = PolynomialRing(Zmod(n))
e = ？
c = ？
f = ？
g = ？
print(GCD(f, g))

参考

https://blog.csdn.net/XiongSiqi_blog/article/details/130978226
https://www.cnblogs.com/whx1003/p/16217087.html
https://github.com/rkm0959/Implementations/blob/main/Half_GCD/code.sage
感谢

Franklin-Reiter相关消息攻击