从一题目中学习RSA——Franklin-Reiter相关消息攻击

Franklin-Reiter相关消息攻击原理

如果两个信息之间存在已知的固定差异（线性关系）

并且在相同的模数n下进行RSA加密，那么就有可能恢复出这两个消息

现在假设有两个明文消息m1，m2并有以下关系（a，b已知）：

加密后有

又因为

所以我们构建如下多项式

当x=m2时都有P(x)=Q(x)=0

届时我们通过辗转相除法计算两个多项式的最大公因式，这个公因式最后一定包含m2并且是一次项的，由模运算的性质可知其模N也一定是0，就此我们计算出了m2，同时m1也出来了

具体题目

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
import random
from Crypto.Util.number import *
while 1:
    delta = getPrime(1024)
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    if delta<N:
        break
flag = b'flag{xxxxxxxxxxxxx}'
e = getPrime(10)
m = bytes_to_long(flag)
t1 = random.randint(0,255)
t2 = random.randint(0,255)
assert (t1 != t2)
m1 = m + t1 * delta
m2 = m + t2 * delta
c1 = pow(m1, e, N)
c2 = pow(m2, e, N)
print("e = ", e)
print("c1 = ", c1)
print("c2 = ", c2)
print("N = ", N)
print("delta = ", delta)

'''
e =  683
c1 =  56853945083742777151835031127085909289912817644412648006229138906930565421892378967519263900695394136817683446007470305162870097813202468748688129362479266925957012681301414819970269973650684451738803658589294058625694805490606063729675884839653992735321514315629212636876171499519363523608999887425726764249
c2 =  89525609620932397106566856236086132400485172135214174799072934348236088959961943962724231813882442035846313820099772671290019212756417758068415966039157070499263567121772463544541730483766001321510822285099385342314147217002453558227066228845624286511538065701168003387942898754314450759220468473833228762416
N =  147146340154745985154200417058618375509429599847435251644724920667387711123859666574574555771448231548273485628643446732044692508506300681049465249342648733075298434604272203349484744618070620447136333438842371753842299030085718481197229655334445095544366125552367692411589662686093931538970765914004878579967
delta =  93400488537789082145777768934799642730988732687780405889371778084733689728835104694467426911976028935748405411688535952655119354582508139665395171450775071909328192306339433470956958987928467659858731316115874663323404280639312245482055741486933758398266423824044429533774224701791874211606968507262504865993
'''

生成t1，t2两个随机0~255的随机整数扰动因子，后面将明文进行两次加密输出c1，c2

不难发现对于两个信息m1，m2有如下线性关系

那么，如果两个信息之间存在已知的固定差异f(x)=ax+b这种线性关系，并且在相同的模数n下进行RSA加密，那么就有可能恢复出这两个消息——Franklin-Reiter相关消息攻击

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 multiprocessing import Pool
import libnum

def franklinReiter(n, e, delta, c1, c2, t1, t2):
    R.<X> = Zmod(n)[]
    f1 = (X + t1 * delta)^e - c1
    f2 = (X + t2 * delta)^e - c2
    return Integer(n - (compositeModulusGCD(f1, f2)).coefficients()[0])

def compositeModulusGCD(a, b):
    if b == 0:
        return a.monic()
    else:
        return compositeModulusGCD(b, a % b)

def check_combination(args):
    t1, t2, N, e, delta, c1, c2 = args
    m = franklinReiter(N, e, delta, c1, c2, t1, t2)
    if b'flag' in libnum.n2s(int(m)):
        return (t1, t2, m, libnum.n2s(int(m)))
    return None

e = 683
c1 = 56853945083742777151835031127085909289912817644412648006229138906930565421892378967519263900695394136817683446007470305162870097813202468748688129362479266925957012681301414819970269973650684451738803658589294058625694805490606063729675884839653992735321514315629212636876171499519363523608999887425726764249
c2 = 89525609620932397106566856236086132400485172135214174799072934348236088959961943962724231813882442035846313820099772671290019212756417758068415966039157070499263567121772463544541730483766001321510822285099385342314147217002453558227066228845624286511538065701168003387942898754314450759220468473833228762416
N = 147146340154745985154200417058618375509429599847435251644724920667387711123859666574574555771448231548273485628643446732044692508506300681049465249342648733075298434604272203349484744618070620447136333438842371753842299030085718481197229655334445095544366125552367692411589662686093931538970765914004878579967
delta = 93400488537789082145777768934799642730988732687780405889371778084733689728835104694467426911976028935748405411688535952655119354582508139665395171450775071909328192306339433470956958987928467659858731316115874663323404280639312245482055741486933758398266423824044429533774224701791874211606968507262504865993

if __name__ == '__main__':
    with Pool() as pool:
        args = [(t1, t2, N, e, delta, c1, c2) for t1 in range(256) for t2 in range(256)]
        results = pool.map(check_combination, args)

        for result in results:
            if result is not None:
                t1, t2, m, flag_bytes = result
                print(f"找到解密的 m 值: {m}")
                print(f"flag找到: {flag_bytes}")
                break

这里使用sagemath的并行计算，CPU和内存直接拉满了，出题人真狠啊