RSA-Rabin_attack

基础形态

e=2, p,q已知且满足%4=3。此时我们可以通过rabin算法解出四个明文，再判断哪个正确

源码：

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

flag = b'NSSCTF{******}'

p = getPrime(256)
q = getPrime(256)

assert p%4 == 3 and q%4 == 3

n = p*q
e = 2
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614
'''

e非常小，但c不是完全平方数，因此不能用低加密指数攻击
同时e和ϕ也不互素e和\phi也不互素，因此求不出逆元
已知p≡q≡3(mod4)p \equiv q \equiv 3 \pmod 4, 且e=2，满足rabin算法

加密：

c≡m2(modn)c \equiv m^2 \pmod n

解密：求解

m2≡c(modn)m^2 \equiv c \pmod n

∵p,q∣n\because p,q|n
∴m2=kn+c=kpq+c\therefore m^2 = kn + c = kpq + c

{m2≡c(modp)m2≡c(modq)\begin{cases} m^2 \equiv c \pmod p\\ m^2 \equiv c \pmod q \end{cases}

∴c是模p的二次剩余\therefore c是模p的二次剩余
由二次剩余+欧拉准则知

cp−12≡1(modp)c^\frac{p-1}{2} \equiv 1 \pmod p

∴m2≡c≡c∗cp−12≡cp+12(modp)\therefore m^2 \equiv c \equiv c*c^\frac{p-1}{2} \equiv c^\frac{p+1}{2} \pmod p

∵m2=kp+cp+12\because m^2 = kp + c^\frac{p+1}{2}
∴m=k12p+cp+14\therefore m = k^\frac{1}{2} p+ c^\frac{p+1}{4}
开方得：

{m1≡cp+14(modp)m2≡p−cp+14(modp)\begin{cases} m_1 \equiv c^\frac{p+1}{4} \pmod p\\ m_2 \equiv p-c^\frac{p+1}{4} \pmod p \end{cases}

同理，c是模q的二次剩余

{m3≡cq+14(modq)m4≡1−cq+14(modq)\begin{cases} m_3 \equiv c^\frac{q+1}{4} \pmod q\\ m_4 \equiv 1-c^\frac{q+1}{4} \pmod q \end{cases}

运用中国剩余定理，将模p和模q组合起来得到n，对应的x就是m

{m1+m3m1+m4m2+m3m2+m4\begin{cases} m_1 + m_3\\ m_1 + m_4\\ m_2 + m_3\\ m_2 + m_4 \end{cases}

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

p = 67711062621608175960173275013534737889372437946924512522469843485353704013203
q = 91200252033239924238625443698357031288749612243099728355449192607988117291739
e = 2
c = 5251890478898826530186837207902117236305266861227697352434308106457554098811792713226801824100629792962861125855696719512180887415808454466978721678349614

def rabin_attack(c, n, p, q):
    c1 = pow(c, (p+1)//4, p)
    c2 = pow(c, (q+1)//4, q)
    cp1 = p - c1
    cp2 = q - c2
    
    t1 = inverse(q, p)
    t2 = inverse(p, q)
    
    m1 = (q*t1*c1 + p*t2*c2) % n
    m2 = (q*t1*c1 + p*t2*cp2) % n
    m3 = (q*t1*cp1 + p*t2*c2) % n
    m4 = (q*t1*cp1 + p*t2*cp2) % n
    
    return m1,m2,m3,m4

ms = rabin_attack(c, p*q, p, q)

for m in ms:
    print(long_to_bytes(m))

高阶形态

此时e不再只是2，而是更大的数，但仍满足p≡q≡3(mod4)p \equiv q \equiv 3 \pmod 4

源码：

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


flag=b"BaseCTF{}"
m = bytes_to_long(flag)

p = getPrime(512)
q = getPrime(512)
assert p%4==3 and q%4==3
n = p*q
e = 4

c = pow(m,e,n)
print("p=",p)
print("q=",q)
print("n=",n)
print("c=",c)
print("e=",e)
"""
p= 8531212975719216550108614256955774722172741885676113601617182716356239301381951899737237219659253655889636684200345109462928796329670321336864298557778843
q= 7443256287912111739335729314443559886458007838130371799255078565502662459436043455787869631999073617967343884377537828940738213460508765519478956421282871
n= 63500004625039456439237191267891267558404574431112995926594213383621331385226487443753506088788203040258384788149958095020759745138424276657604371402824844725005596890673468964961037168078105356669148960568974603581485045691990626520286184874115519591663033533771400334558853058140717812903874350138362098253
c= 51452608438757130697131508192775727191605112918772187364577097224326062184288501602000700342623122861398852536963355962672293705131887315354242193416090384360837672258861475017098419459125395949090523474744886423754439919504732741712693909507972791203801494594878447921609420574365853676576693694677914169353
e= 4
"""

e=4，需要进行两次rabin才能得到m，再将模p模q运用中国剩余定理组合起来

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
40
41
42
43
44
45
46
47
48
49
50
from Crypto.Util.number import long_to_bytes, inverse
import math

# 给定的参数
p = 8531212975719216550108614256955774722172741885676113601617182716356239301381951899737237219659253655889636684200345109462928796329670321336864298557778843
q = 7443256287912111739335729314443559886458007838130371799255078565502662459436043455787869631999073617967343884377537828940738213460508765519478956421282871
n = 63500004625039456439237191267891267558404574431112995926594213383621331385226487443753506088788203040258384788149958095020759745138424276657604371402824844725005596890673468964961037168078105356669148960568974603581485045691990626520286184874115519591663033533771400334558853058140717812903874350138362098253
c = 51452608438757130697131508192775727191605112918772187364577097224326062184288501602000700342623122861398852536963355962672293705131887315354242193416090384360837672258861475017098419459125395949090523474744886423754439919504732741712693909507972791203801494594878447921609420574365853676576693694677914169353
e = 4

# Rabin 解密函数，返回模 p 和模 q 的解
def rabin(c):
    m1 = pow(c, (p + 1) // 4, p)
    m2 = p - m1
    m3 = pow(c, (q + 1) // 4, q)
    m4 = q - m3
    return m1, m2, m3, m4

# 中国剩余定理合成函数
def CRT(m_p, m_q):
    n = p*q
    t1 = inverse(q, p)
    t2 = inverse(p, q)
    x = (m_p*q*t1 + m_q*p*t2) % n
    return x

# 解密过程
cs = [c]
lge = math.log(e, 2)
for _ in range(int(lge)):  # 遍历以 log2(e) 为次数的循环
    t = set()
    for c2 in cs:
        m1, m2, m3, m4 = rabin(c2)
        # 使用 CRT 将模 p 和模 q 的解合成模 n 的解
        candidates = [
            CRT(m1, m3),
            CRT(m1, m4),
            CRT(m2, m3),
            CRT(m2, m4)
        ]
        for candidate in candidates:
            t.add(candidate)
    cs = list(t)

# 检查每个候选解是否正确
for i in cs:
    flag = long_to_bytes(i)
    if b'BaseCTF' in flag:
        print(flag)

珍贵手稿