x1ao
文章
13
分类
1
评论
0

Franklin-Reiter攻击

| CTF •
字数总计 10068 | 阅读时长 25分钟 | 阅读量 125

Franklin-Reiter

假设采用相同的密钥对加密了两条消息$M_1,M_2$，且满足$M_1=f(M_2) \space mod \space N$，其中f是公开的多项式。那么，如果e比较小，攻击者可以恢复$M_1,M_2$。

由于M同时是以下两个多项式的根：

$$\left\{\begin{array}{c}g_1(x)=f(x)^e-c_1\\g_2(x)=x^e-c_2\end{array}\right.$$

则容易知道$(x-M)$是两个多项式的公因式，对于$g_1,g_2$求gcd即可求得$(x-M)$。若$e$比较大的时候，使用$Half-GCD$算法。以下为其具体实现：

def pdivmod(u, v):
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    x = u.parent().gen()
    if u.degree() < v.degree():
        u, v = v, u
    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])
    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)
    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)
    g0 = e // x^(m//2)
    g1 = f // x^(m//2)
    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    if u.degree() < v.degree():
        u, v = v, u
    if v == 0:
        return u
    if u % v == 0:
        return v
    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u
    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1
    return pgcd(b1, r)

Coppersmith Short Pad 攻击

考虑某人发送消息时，总是在尾部加上一些随机的短 padding。如果一个人将相同的信息发送两次（padding 不同），攻击者可以恢复出明文。

(Short Pad攻击)设$N,e$是RSA公钥，N的长度为n。记$m:=\lfloor n/e^2 \rfloor$。现有不超过n-m长度的明文M。考虑$M_1=2^mM+r_1,M_2=2^mM+r_2$，其中$r_1,r_2$的长度小于m。

若给定$C_1,C_2$,攻击者可以高效恢复M。

具体方法：先获取两个明文间的差值$r_2-r_1$，即可将问题转化为Franklin-Reiter。

定义$g_1(x,y)=x^e-c_1,g_2(x,y)=(x+y)^e-c_2$，显然，当$y$取$r_2-r_1$时，这两个函数有公共根$M_1$。即$\Delta =r_2-r_1$是结式$h(y):=res_x(g_1,g_2) \in \mathbb{Z}_N[y]$的根，而h的次数最多为$e^2$，且$|\Delta|<2^m<N^{1/e^2}$，故$\Delta$是模$N$下$h$的一个小根，可通过Coppermith得到。

N = 147560516509868629649957267817803694619228124354925314885515791316324923003875671351329125757976834400817548677872819677080629134724723675686621779218525433371747881410084483453473659760099784521546880648108933073105493585486912907554888403159988949821983127882698445040267583800926823851843063207106149260879 
e = 3 
m = bytes_to_long(b'flag{helloworld-----coppersmith-----12345678987654321}') 
pad_len = 64 
r1, r2 = randint(1, 2^pad_len), randint(1, 2^pad_len) 
m1 = m*2^pad_len + r1 
m2 = m*2^pad_len + r2 hex(m1), hex(m2) # ('0x666c61677b68656c6c6f776f726c642d2d2d2d2d636f70706572736d6974682d2d2d2d2d31323334353637383938373635343332317d635c7d78ec6c46c1',  # '0x666c61677b68656c6c6f776f726c642d2d2d2d2d636f70706572736d6974682d2d2d2d2d31323334353637383938373635343332317d77c7f14335b18e42') 
c1 = m1^e % N 
c2 = m2^e % N 
c1, c2 # (77057136553039015345576133157090380102418815377448333969326628299945662107344154844516843296128733900775646701272736348442341286883691269830867415397962344570365589584535600359957784804498158166703138860397038324185900759267823714069270977153172175167575961150699995064783986678433355379166634628581965681262,  # 101183053419405872377139193010919487763144997264116191784647789473940757320310381966850439519064971456830390365119398489723885718983898828784700546999052289257567244587850027505752032025342196461503917841756933993292900851248827187660066705639801599238888852412027691932301724474472443995971243809491008598810) 
P.<x, y> = PolynomialRing(ZZ) 
g1 = P(x^e-c1) 
g2 = P((x+y)^e - c2) 
g1, g2 
# (x^3 - 77057136553039015345576133157090380102418815377448333969326628299945662107344154844516843296128733900775646701272736348442341286883691269830867415397962344570365589584535600359957784804498158166703138860397038324185900759267823714069270977153172175167575961150699995064783986678433355379166634628581965681262,  # x^3 + 3*x^2*y + 3*x*y^2 + y^3 - 101183053419405872377139193010919487763144997264116191784647789473940757320310381966850439519064971456830390365119398489723885718983898828784700546999052289257567244587850027505752032025342196461503917841756933993292900851248827187660066705639801599238888852412027691932301724474472443995971243809491008598810) 
h = g1.resultant(g2) 
T.<y> = PolynomialRing(Zmod(N)) 
f = T(h) 
f # y^9 + 75182765910768058555268088256316371637049578694921741439552307794339637364976989984328337089168121732653317686332833253235995838424100998825122384415255599310142916400141202016090918097567669637144543704029246065784493309543902486782501217700100677608044454098715354437714370412809558001429235664379020508235*y^6 + 18533785375769026176371012496341095528434803647999759395839390073023224410391193067227916238144090178926713046556681745938814430943500063346120852667252487069723256652008723192238389662577939132188033190632007028866765722537553392968908001416763541434424026670350458421930588954998208742211794585676993860570*y^3 + 89716595702761571341386136325448582633690897297078673713374589820351363397360398207112515590873043335841753334724604976847493641392102179516041783812773125897554071300116148305750690789037273322027697922080125074955511814868720753233463747250043976374499853180226171210820809061338875559480035291959318076344 
delta = f.small_roots(epsilon=1/30)[0] # 不设 epsilon 跑不出来结果

Ricerca CTF-RSALCG

task.py

from Crypto.Util.number import getPrime, getRandomNBitInteger  
import os  
  
FLAG = os.getenv("FLAG", "RicSec{*** REDACTED ***}").encode()  
  
def RSALCG(a, b, n):  
    e = 65537  
  s = getRandomNBitInteger(1024) % n  
    while True:  
        s = (a * s + b) % n  
        yield pow(s, e, n)  
  
def encrypt(rand, msg):  
    assert len(msg) < 128  
  m = int.from_bytes(msg, 'big')  
    return int.to_bytes(m ^ next(rand), 128, 'big')  
  
if __name__ == '__main__':  
    n = getPrime(512) * getPrime(512)  
    a = getRandomNBitInteger(1024)  
    b = getRandomNBitInteger(1024)  
    rand = RSALCG(a, b, n)  
    print(f"{a = }")  
    print(f"{b = }")  
    print(f"{n = }")  
    print(encrypt(rand, b"The quick brown fox jumps over the lazy dog").hex())  
    print(encrypt(rand, FLAG).hex())  
    print(encrypt(rand, b"https://translate.google.com/?sl=it&tl=en&text=ricerca").hex())

在RSALCG函数中可以得到三个等式：

$$s_1≡as+b(mod \space n)$$$$s_2≡as_1+b(mod \space n)$$$$s_3≡as_2+b(mod \space n)$$

由于$s_3≡(a*(as_1+b)+b)(mod \space n)$，是一个关于$s_1$的一次函数，很像Franklin-Reiter攻击只是这里的e很大。

我的解答

from Crypto.Util.number import *
from gmpy2 import *

def pdivmod(u, v):
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    x = u.parent().gen()
    if u.degree() < v.degree():
        u, v = v, u
    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])
    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)
    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)
    g0 = e // x^(m//2)
    g1 = f // x^(m//2)
    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    if u.degree() < v.degree():
        u, v = v, u
    if v == 0:
        return u
    if u % v == 0:
        return v
    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u
    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1
    return pgcd(b1, r)

a = 120729645934467728263454579095572520275606452119935776405452611793157729812018086453732564784232778500514658482997575637723965401345000800120589930910877609589501347306602880136096021940643356939249632650422554376147747280447845719923565004318154492585184467107472622945523184307608304770785533462613707434372
b = 103563095982490531479950286084701136328109495619129470515338108190377998766343034629373963710535028007626655471746428891631216081815743758712169208143916635046914663316205512656638962440419576549457413100478821332017020439910417042309358219284570615421191854055430863710750537025556849567816812354874718307939
n = 104550029838660015456942477451846252359737559379359834146301198628443914068507086955400756824324163806955928669931933794108054158682425162273459172066466856641927058801334625187613102647557082708310019518150596665096155603922860193744960544588154563123669941241768617110454701719921882991585965937552831538061
s1=0x0756db20f8f1281320c980f1256470cd926142d620b9d5d4cfbbcf0736416deb4ce9f3dc2bfc9d74c4e533ceff339470785a3991f114b12d167eaf863ff9795e97a1c1e170fa05b6197c2f92cdadc01a63be7f3e660c22116e34e3df6e02360ac05dea546cc2063f438337d6aab4f8de24b5171b24f7eb14e746c15a327d6d95
s2=0x532e408171756ba06ac89cfc8c8f2e2a1b8ebb577e66665399d597ce904781adde7cd18b5b824332300a86da190681c00a7203c09c0c33841ab13ef129c7537b00e5f9f9ebf48efe5e6d6ce66a1d60dc4f9c6683b4c30cde673434148728e4e05474353aeea7652e51911fcd33a0cb137bc596cd6f1c3af07b30daa5a5a4cd34
s3=0x03355cd0c1fef28a894ce327e927328239b9a0f37c69af24e6c940cb45e1532bd5bdb38a8d97ad377d84dd1c7ffcbf115b1b7f55302fb4549b5f58075ba2b924b4184e3c5766e029a65e90321e0a5c2d5e123410f9c69e3dff2e02704035fa936c0891bacfc26253fec23c47c671a2787f93630661c10deedd6e657b7582ccfd
c1=s1 ^^ bytes_to_long(b"The quick brown fox jumps over the lazy dog")
c3=s3 ^^ bytes_to_long(b"https://translate.google.com/?sl=it&tl=en&text=ricerca")
e=65537
P.<s> = PolynomialRing(Zmod(n))
g1 = s**e - c1
g2 = ((s*a + b)*a + b)**e - c3
r=pgcd(g1, g2)
s=int(-r.monic().constant_coefficient())
print(long_to_bytes((int(pow(int((s*a + b) % n), e, n)) ^^ s2)))

参考链接：https://www.ruanx.net/rsa-attack-survey/

文章作者： x1ao
本文链接：
版权声明： 本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 x1ao！
CTF Crypto
喜欢就支持一下吧