Coppersmith 攻击定理

在一个**e阶的mod n多项式f (x)**中,如果有一个根小于n^1/e,就可以运用一个O (log n)的算法求出这些根。 这个定理可以应用于rsa算法。

试着构造关于m的同余式

bFJ31H.png

系数已知;进行sage运算

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
from Crypto.Util.number import *
from sympy import *
from sympy.polys.polyoptions import Flag

# 求flag
n = 128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1 = 96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2 = 9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585

sum = c1 + c2
pro = c1*c2
# sage
# R.<m> = Zmod(n)[]
# f = m^2 - sum*m + pro
# flag = f.smallroots(2^400)[0] #括号内的是根的边界,我们所求的根也就是m,这里hint已经给出了m.bit_length()<400
flag = 4242839043019782000788118887372132807371568279472499477998758466224002905442227156537788110520335652385855
print(long_to_bytes(flag))


明文存在线性关系攻击

攻击条件

Alice使用相同的N和e对两个相关的信息m1,m2进行加密,并将加密之后的结果c1,c2发送给Bob.并且m1,m2满足

m1 ≡ f(m2) mod N

其中f为一个线性函数,即f=a∗x+b

在具有较小错误概率的情况下,复杂度为O(elog2(N))

攻击原理

首先我们知道c1 ≡ m1 ^ e mod N,并且m1 ≡ f(m2) mod N,那么我们可以知道m2是f(x) ^ e≡ c1modN的一个解,即它是方程f(x) ^ e−c1在模N意义下的一个根.同样,m2是x ^ e模N意义下的一个根.所以说x−m2同时整除以上两个多项式.因此,我们可以求得两个多项式的最大公因子,如果最大公因子恰好是线性的话,那么我们就求得了m2.需要注意的是,在e=3的情况下,最大公因子一定是线性的.

当e=3,且f(x)=a∗x+b的情况下,经过推导我们可以得到:

1
m2≡(b/a)∗(c1+2∗a3∗c2−b3)/(c1−a3∗c2+2∗b3)

上面的式子中右边所有的参数都是已知的,所以可以求得对应的信息.

例题:SCTF RSA3

题目分析:加密方式是将明文加上用户的user-id进行加密(明文就存在了线性关系),而且还存在多组.我们选择模数相同的两个cipher.

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
import gmpy2
id1 = 1002
id2 = 2614

c1 = number_c1
c2 = number_c2
n = number_n

# 构造f(x) = a*x+b
a = 1
b = id1 - id2


def getmessage(a, b, c1, c2, n):
b3 = gmpy2.powmod(b, 3, n)
part1 = b * (c1 + 2 * c2 - b3) % n
part2 = a * (c1 - c2 + 2 * b3) % n
part2 = gmpy2.invert(part2, n)
return part1 * part2 % n


message = getmessage(a, b, c1, c2, n) - id2
message = hex(message)[2:]
if len(message) % 2 != 0:
message = '0' + message

print message.decode('hex')

2019强网杯-challenge5

明文c存在线性关系

题目:

1
2
3
4
5
6
n=0xf9526aad4d41c9b28f8bae279c7ef6b07d729d1f56e530219851f656ad521218815bdccb15167a25633a2f76969fccd3fe1ef379ded08d1a9c3307f680e952956d2b3d04cc50040efb30e40bf2562aae4b05b8ec0d5e0e0ea5fdc1b00b80dee9b6de1d77d41d8d040d3465c89133d9af23b1d43f57e70606e3433d35a47e2edL
e=3
m=random.getrandbits(512)
c=pow(m,e,n)=0x798841c574b7c88ce1430d4b02bac01fc9368c71a7966176b22f9dc2e0c2f6d4d5b8a9e10dbcaa4584e667ef1afd213b78c2bdc16ba5ab909c2de2fe5a7a5fa36a390bdccf794451cd9db8489ed7870efa4a4d7d1cacacfec92e81f6bb955a4ef5d71d80631c0726d22ec3d5b115de7ff42f22e67854b59ed816e06485ab523L
x=pow(m+1,e,n)=0xe92c4c99052fa3c4bb5e54477b0afe8e18da37255269f070ffa6824492a87153e428fa4ed839b7f3249966259a0c88641185594fc2fa4881cf32b7af5b18baa6f5200453ee80e38c74dbeb90f32118e4f33e636a808e44f27e09286d109ee8f41765ad64c7afea9775974d78a80e0977a37689c7f15a23a83a87b1f5bdbcdecL
long_to_bytes(m).encode('hex')=???

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import gmpy2
import functools

def getM2(a,b,c1,c2,n):
a3 = pow(a,3,n)
b3 = pow(b,3,n)
first = c1-a3*c2+2*b3
first = first % n
second = 3*b*(a3*c2-b3)
second = second % n
third = second*gmpy2.invert(first,n)
third = third % n
fourth = (third+b)*gmpy2.invert(a,n)
return fourth % n
a=1
b=-1
padding2=b
n=0xf9526aad4d41c9b28f8bae279c7ef6b07d729d1f56e530219851f656ad521218815bdccb15167a25633a2f76969fccd3fe1ef379ded08d1a9c3307f680e952956d2b3d04cc50040efb30e40bf2562aae4b05b8ec0d5e0e0ea5fdc1b00b80dee9b6de1d77d41d8d040d3465c89133d9af23b1d43f57e70606e3433d35a47e2ed
c1=0x798841c574b7c88ce1430d4b02bac01fc9368c71a7966176b22f9dc2e0c2f6d4d5b8a9e10dbcaa4584e667ef1afd213b78c2bdc16ba5ab909c2de2fe5a7a5fa36a390bdccf794451cd9db8489ed7870efa4a4d7d1cacacfec92e81f6bb955a4ef5d71d80631c0726d22ec3d5b115de7ff42f22e67854b59ed816e06485ab523
c2=0xe92c4c99052fa3c4bb5e54477b0afe8e18da37255269f070ffa6824492a87153e428fa4ed839b7f3249966259a0c88641185594fc2fa4881cf32b7af5b18baa6f5200453ee80e38c74dbeb90f32118e4f33e636a808e44f27e09286d109ee8f41765ad64c7afea9775974d78a80e0977a37689c7f15a23a83a87b1f5bdbcdec
m = getM2(a,b,c1,c2,n)-padding2
print (m)

Known High Bits Message Attack / Stereotyped Messages

明文部分位攻击

攻击条件

普通的RSA解密模型如下:

c ≡ m ^ d mod N

并且假设我们知道消息m的大部分m0,从而m=m0+x,x即为待求消息.那么我们可以通过该方法进行消息恢复.这里待求的x其实就是满足Coppersmith约束的多项式的根.

攻击原理

我们构造多项式f(x) = (m+x)^e - c,其在模N条件下的根即为与m的差距.

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
load("coppersmith.sage")
N = #N的值
e = #e的值
m = #m的大概值
c = #c的值
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = (m + x)^e - c
dd = f.degree()
beta = 1
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) //XX是根的上界,根据所知的m的位数进行调整
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = 0x2519834a6cc3bf25d078caefc5358e41c726a7a56270e425e21515d1b195b248b82f4189a0b621694586bb254e27010ee4376a849bb373e5e3f2eb622e3e7804d18ddb897463f3516b431e7fc65ec41c42edf736d5940c3139d1e374aed1fc3b70737125e1f540b541a9c671f4bf0ded798d727211116eb8b86cdd6a29aefcc7
e = 3
m = randrange(n)
c = pow(m, e, n)
beta = 1
epsilon = beta^2/7
nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))

mbar = 0xb11ffc4ce423c77035280f1c575696327901daac8a83c057c453973ee5f4e508455648886441c0f3393fe4c922ef1c3a6249c12d21a000000000000000000
c = 0x1f6f6a8e61f7b5ad8bef738f4376a96724192d8da1e3689dec7ce5d1df615e0910803317f9bafb6671ffe722e0292ce76cca399f2af1952dd31a61b37019da9cf27f82c3ecd4befc03c557efe1a5a29f9bb73c0239f62ed951955718ac0eaa3f60a4c415ef064ea33bbd61abe127c6fc808c0edb034c52c45bd20a219317fb75
print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))

PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n1
print (mbar + x0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = 131889193322687215946601811511407251196213571687093913054335139712633125177496800529685285401802802683116451016274353008428347997732857844896393358010946452397522017632024075459908859131965234835870443110233375074265933004741459359128684375786221535003839961829770182916778717973782408036072622166388614214899
c = 11188201757361363141578235564807411583085091933389381887827791551369738717117549969067660372214366275040055647621817803877495473068767571465521881010707873686036336475554105314475193676388608812872218943728455841652208711802376453034141883236142677345880594246879967378770573385522326039206400578260353074379
from Crypto.Util.number import *
part = 724544392969230558511482768252916758716788586090548475884579 #part m
F = Zmod(n)
x = PolynomialRing(F, 'x').gen()
f = ((part << 64) + x) ** 5 - c

xx = f.small_roots(X = 2 ** 64)[0]
flag = (part << 64) + xx

print(flag)

print(long_to_bytes(flag))

Factoring with High Bits Known

p/q高位攻击

攻击条件

当我们知道一个公钥中模数N的一个因子的较高位时,就有一定的几率来分解N.

攻击原理

我们在RSAatac过程中需要进行模数N的分解,当已知其中一个大素数q的部分位时,可以构造函数f(x) = x-q',该式在模q条件下的根即为q’与q之间可能的差距.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
load("coppersmith.sage")
N = #N的值
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
qbar = #q的近似值
f = x - qbar
beta = 0.5
dd = f.degree()
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

//注意必须满足q>=N^beta,所以这里令beta=0.5,保证两个因数中必有一个满足条件
//XX是f(x) = q'+x在模q意义下的根的上界,自然我们可以选择调整它,这里也表明了我们已知的q’与因数q之间可能的差距

sage:

1
2
3
4
5
6
7
8
9
10
11
12
n = 0x5894f869d1aecee379e2cb60ff7314d18dbd383e0c9f32e7f7b4dc8bd47535d4f3512ce6a23b0251049346fede745d116ba8d27bcc4d7c18cfbd86c7d065841788fcd600d5b3ac5f6bb1e111f265994e550369ddd86e20f615606bf21169636d153b6dfee4472b5a3cb111d0779d02d9861cc724d389eb2c07a71a7b3941da7dL
p_fake = 0x5d33504b4e3bd2ffb628b5c447c4a7152a9f37dc4bcc8f376f64000fa96eb97c0af445e3b2c03926a4aa4542918c601000000000000000000000000000000000

pbits = p_fake.nbits()
kbits = 128 #p失去的低位
pbar = p_fake & (2^pbits-2^kbits)
print ("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))

PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.3
print (x0 + pbar)

Boneh and Durfee Attack

低私钥攻击:将d的范围从维纳atac的N^(0.25)扩大到了N^(0.292)

攻击条件

当d较小时,满足d<N^(0.292)时,我们可以利用该atac,比维纳atac效率高一些.

Partial Key Exposure Attack

攻击条件

若e较小,且d的低位已知时,可以考虑使用部分私钥泄露atac.

攻击原理

部分私钥泄露atac的原理同前面提到的明文高位泄露以及模数部分泄露原理相同.

sage:

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
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()

f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)

def find_p(d0, kbits, e, n):
X = var('X')

for k in xrange(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p:
return p


if __name__ == '__main__':
n = number_n
e = 3
d = number_d

beta = 0.5
epsilon = beta^2/7

nbits = n.nbits()
kbits = floor(nbits*(beta^2+epsilon))
d0 = d & (2^kbits-1)
print "lower %d bits (of %d bits) is given" % (kbits, nbits)

p = find_p(d0, kbits, e, n)
print "found p: %d" % p
q = n//p
print d
print inverse_mod(e, (p-1)*(q-1))

Basic Broadcast Attack

低加密指数广播攻击

攻击条件

如果一个用户使用同一个加密指数 e 加密了同一个密文,并发送给了其他 e 个用户。那么就会产生广播atac。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//本题e = 3,有3组n,c
from struct import pack,unpack
import zlib
import gmpy

def my_parse_number(number):
string = "%x" % number
erg = []
while string != '':
erg = erg + [chr(int(string[:2], 16))]
string = string[2:]
return ''.join(erg)
def extended_gcd(a, b):
x,y = 0, 1
lastx, lasty = 1, 0
while b:
a, (q, b) = b, divmod(a,b)
x, lastx = lastx-q*x, x
y, lasty = lasty-q*y, y
return (lastx, lasty, a)
def chinese_remainder_theorem(items):
N = 1
for a, n in items:
N *= n
result = 0
for a, n in items:
m = N//n
r, s, d = extended_gcd(n, m)
if d != 1:
N=N/n
continue
result += a*s*m
return result % N, N

sessions=[{"c": 0x25e206422ea328f1b295dd121970b874b002789b2419a57584b2f1a682a36312a45efe22bb68694b9c9dfdc63c4f10b746a4a2893b29f918d90cb5129d52e66babf7f8516c44cd33ee27d2cf2968e0002ab2b711387d8f111315bd23d3f92073634ed6e57fa9b56d14104f75336f46c6dd43fbac810a6337a7ad3f60890873b, "e": 3, "n":0x5797fdb74bcea6788212fb2c32c5d98d308c617f893d1f375d0e611b424d5656df4465772e278c25e7d1d5fd73b0fdfdac4a786a11403d239a2f84dc77a46c1108219eed98567605ab29ffdeef10594863bb49d45d41c1f3925d6a33bb34205321ab03d906e2d89c2153e76f2ad185bac9fb26099910dd19cf3be35ec7e01df5},
{"c":0x448f88bec6795e11b06a7810faf617931bc6d99d1628cafecff1e933154ce575caaf752c3daf50b288ad7759ea8133f7dc9ca42a1b950eb8d538f98e00a4f3ad6bb0d6a9ad5d042d6db710c060bb72aa13065986d8dfb800409c08e4cdee471bc7ef31a6e3e2027ecb8ea9fb9b19440c5272fecf04aefdf2dbeafd994589c09f , "e": 3, "n":0x50998a3cf7f86a3044fe3c1fda2f6df7050383833279ebdbfe943f83faae3ada1bb6e684e48efd0487056849d47552d8052144364a72324b038ea73812960015c678c4e903e25515d874d1435761f20d1d6a066d2b70651c051dc157d2183d91ed6e7ae25d4adb0ce04833b816f96c5fd718c687474cacca6ad1dcc85db07e89 },
{"c":0xc9ddbb9478d0b64086091aac64efd51eb37b5067feb380995d39a917c0c927b26902f06dc449b53d80cd59c5d912fb5a5f45b223278919ae1ce449f4db7afbc252f16247129ea68dc6011093da6b11356591a9e8c0e10057e9d733712a6e0caafc462e9b2d07fb2aa3a451403a7f84de3504a60e72872df20bc244a0f1c837b , "e": 3, "n":0x15ed9002077c66e48a6fc80ce744f16b87e237ddd9a4efb4ffa2f9f89d09af382dddfc259dbf932728c23757957638f3ec9327fc0eaf3fd5d72b91c714798ca1459dfdf6c7505eb6e39f26624431239b6daa7bbaa6c5aad3dc3bf6b377923781ab5c221c195115d39c477c0561d5c769c17583c5b66d5f21f6683cea2670215b }]
data = []
for session in sessions:
e=session['e']
n=session['n']
msg=session['c']
data = data + [(msg, n)]
print ("Please wait, performing CRT")
x, n = chinese_remainder_theorem(data)
e=session['e']
realnum = gmpy.mpz(x).root(e)[0].digits()
print (my_parse_number(int(realnum)).encode("UTF-8").hex())



import gmpy
import gmpy2
def modinv(a, m):
return int(gmpy2.invert(a, m))
def chinese_remainder(n, a):
sum = 0
prod = reduce(lambda a, b: a * b, n)
for n_i, a_i in zip(n, a):
p = prod / n_i
sum += a_i * modinv(p, n_i) * p
me = int(sum % prod)
return gmpy.mpz(me).root(len(n))[0]
ns = given_ns
cs = given_cs
m = chinese_remainder(ns, cs)
print m