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 = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
p_fake = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479

pbits = p_fake.nbits()
kbits = 300  #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)

低位失去100位：

1
2
3
4
5
6
7
8
9
10
11
n = 132298777672085547096511087266255066285502135020124093900452138262993155381766816424955849796168059204379325075568094431259877923353664926875986223020472585645919414821322880213299188157427622804140996898685564075484754918339670099806186873974594139182324884620018780943630196754736972805036038798946726414009
p_fake = 9707529668721508094878754383636813058761407528950189013789315732447048631740849315894253576415843631107370002912949379757275

pbits = p_fake.nbits()
print(pbits)
kbits = 100  # p失去的低位
pbar = p_fake << 100
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2 ^ 100, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.3
print(x0 + pbar)

题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537

hint1 = p >> 724
hint2 = q % (2 ** 265)
ct = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(ct)

exp：

给了𝑝p的高位和𝑞q的低位，简单变形

𝑛 ≡ 𝑝𝑙∗𝑞𝑙(mod2 *** 265)*

𝑝𝑙 ≡ 𝑛∗𝑞𝑙−1(mod2 ** 265)

这样就得到𝑝p的低位，直接coppersmith求解，再爆破几位即可。

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 long_to_bytes

h1 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
h2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 0x10001

mod = 1<<265
pl = n*inverse_mod(h2, mod) % mod
pbar = (h1 << 724) + pl

PR.<x> = PolynomialRing(Zmod(n))

for i in range(64):
    f = pbar + (x*mod*64) + (i<<265)
    print(f)
    f = f.monic()
    print(f)
    print('--------------')
    pp = f.small_roots(X=2^453, beta=0.4)
    if pp: break

p = int(pbar + (pp[0]<<271) + (i<<265))
q = n // p
d = inverse_mod(e, (p-1)*(q-1))
print(long_to_bytes(power_mod(c, d, n)))

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的低位已知时,可以考虑使用部分私钥泄露atack.

攻击原理

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

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