Crypto

共模之谜

题目名称：共模之谜
题目描述：情报部门截获了两条来自同一来源的加密信息，它们使用了相同的RSA模数但不同的公钥指数。这种看似冗余的操作背后可能隐藏着严重的安全隐患。你能利用这一漏洞还原出原始情报吗？

题目给出了如下数据：

1
2
3
4
5
n =  52434676028442864513479128215013580182283012674942942342267825274916668125023466810480258585751372421292748168448504340890831865866538692974717102950393572887019518607310927816328323922713991044821625309344713196448648512424001395920800511116740568322697525090524941927457199617152790810652838307470708198191
e1 =  65535
e2 =  65537
c1 =  31521924348336802941777804619118889419878299906419071463959824967144080278171748396111541024836589397246436103266770875084999045862006933555188252327690337535968633887854737591285586725332567987630507078395008745655466830366884621022676739454737019137093537940861470289530663521973352477282432379221618425173
c2 =  36458358677472463740424671249382188611575270134299259491605236563200229724936493457180763895249374203908007428278380931503316461352600040412306743430776089418505336838252318935614227276154885340185203325582856170342370595170507594127231199036370588508651117489152775119699195183906973863975443599121572830617

提示：当同一明文 m在相同的模数 n下被两个互质的公钥指数 e1,e2加密时，攻击者可通过扩展欧几里得算法找到一组整数 s,t满足 s⋅e1+t⋅e2=1，进而直接计算 m

实际上这就是共模攻击。

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 gmpy2
from Crypto.Util.number import long_to_bytes

  
n = 52434676028442864513479128215013580182283012674942942342267825274916668125023466810480258585751372421292748168448504340890831865866538692974717102950393572887019518607310927816328323922713991044821625309344713196448648512424001395920800511116740568322697525090524941927457199617152790810652838307470708198191
e1 = 65535
e2 = 65537
c1 = 31521924348336802941777804619118889419878299906419071463959824967144080278171748396111541024836589397246436103266770875084999045862006933555188252327690337535968633887854737591285586725332567987630507078395008745655466830366884621022676739454737019137093537940861470289530663521973352477282432379221618425173
c2 = 36458358677472463740424671249382188611575270134299259491605236563200229724936493457180763895249374203908007428278380931503316461352600040412306743430776089418505336838252318935614227276154885340185203325582856170342370595170507594127231199036370588508651117489152775119699195183906973863975443599121572830617

  

g, s1, s2 = gmpy2.gcdext(e1, e2)
assert g == 1, "e1 and e2 不互质"

if s1 < 0:
    c1 = gmpy2.invert(c1, n)
    s1 = -s1
if s2 < 0:
    c2 = gmpy2.invert(c2, n)
    s2 = -s2

m_part1 = pow(c1, s1, n)
m_part2 = pow(c2, s2, n)
m = (m_part1 * m_part2) % n
print("结果",long_to_bytes(m).decode())

flag{528d82e8ad37e7aeca4c60d475dc056b}

三次方的陷阱

题目名称：三次方的陷阱
题目描述：在一次网络取证中，你发现攻击者留下了一条RSA加密的密文。据情报显示，加密者为了提升效率，使用了一个极小的公钥指数。然而，这种优化反而引入了致命漏洞。你能利用这一点还原出原始信息吗？

题目给出了如下数据：

1
2
3
n:121383870071311775359911942411789216597716521631089762926488206150018405982242606657064334331128377877618291611912838143522718043048975642123842910378536861304156503028830728263614462484834569011277782682653550833803057515742235247213351034112654400245411355170987970439052312230073603288646796930218863851531
e:3
c:2217344750798710450802454256530905633991914822718944829361939093715780428997238569636656782796294509135735606047120598053449689542122515721333911857696093436383317783079856772999993481426122938079821372867463989809098932628954263602024896175828059384261351520201111250580837

当 e=3且明文 m较短时（即 m^3<n），密文 c=m ^e mod n可能直接等于 m^3（未模 n溢出）。此时可直接对 c开三次方根得到 m。
计算 c的立方根（如使用 Python 的 gmpy2.iroot）,将得到的整数 m转换为字节串，即还原明文 flag

实际上就是低加密指数攻击：

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
def integer_nth_root(a,n):
    low = 0
    high = 1 << ((a.bit_length() + n -1) // n+1)
    while low + 1 < high:
        mid = (low+high) // 2
        mid_n = pow(mid,n)
        if mid_n == a:
            return mid, True
        if mid_n < a:
            low = mid
        else:
            high = mid
    return low, pow(low, n) == a


def int_to_bytes(i):
    if i == 0:
        return b"\x00"
    blen = (i.bit_length() +7) // 8
    return i.to_bytes(blen, byteorder='big')


n = 12138387***
e = 3
c = 221734475079871***
m_root, exact = integer_nth_root(c, e)

if exact:
    m_bytes = int_to_bytes(m_root)
    try:
        print("明文",m_bytes.decode())
    except Exception:
        print("只能以十六进制展示",m_bytes.hex)

else:
    print("不符合低指数开放")

flag{9955792527865472523f8b95be1a2718}