coppersmith相关密码学

发表于 | 分类于

最近做题遇到了关于低位丢失（高位泄露）等题目，于是了解到了coppersmith算法。具体关于格密码的学习还未开始，仅仅会在github上找工具解题。格密码下学期做完毕业论文会开始学习。越来越觉得每个方向都是一个无底洞，学是永远也学不完的，永远在路上。

已知p高位

对RSA-Factoring with High Bits Known理解
这篇文章把原理讲解了，我只会用脚本，格基规约还在学习中…..
以这道CTF题目为例：

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
from Crypto.Util.number import *
import binascii
import gmpy2
flag = '*****************************************'
hex_flag=int(flag.encode("hex"),16)

p=getPrime(256)
q=getPrime(256)
n=p*q

e=getPrime(100)

c=pow(hex_flag,e,n)

p=((p>>60)<<60)

print("n=",hex(n))
print("p=",hex(p))
print("e=",hex(e))
print("c=",hex(c))
'''
('n=', '0x558477ce1d081f831cfa159290ee4fd14888422c216a16ad86e2b2d4335e3cb18ed0120a955f970b17b229a8e7d0ae1b6f0c40213ad0e127eba99ae0d8a82397L')
('p=', '0x8fbcbb7d1e9f393ee21b537d6e0bd2cf8629e315f4e356c1e000000000000000L')
('e=', '0xf7278179324b11fd83d08aa6fL')
('c=', '0x36e1c09ccad45cd63a0f07e704d3811c39d70cdfdad999d2df90255a76c58cf6fe99ac1ab1d5d99a4ce1a2ebdbfbc49ce72df2a0b90766ff84ab0ef62068d46bL')
'''

首先通过sage分解n：
在线运行sage

1
2
3
4
5
6
7
8
9
10
11
12
13
n = 0x558477ce1d081f831cfa159290ee4fd14888422c216a16ad86e2b2d4335e3cb18ed0120a955f970b17b229a8e7d0ae1b6f0c40213ad0e127eba99ae0d8a82397L
p_fake = 0x8fbcbb7d1e9f393ee21b537d6e0bd2cf8629e315f4e356c1e000000000000000L

pbits = 256
kbits = 60  #p失去的低位
pbar = p_fake & (2^pbits-2^kbits)
 
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
 
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
p= x0 + pbar
print(p)


这样就得到了p，接下来就是常规解题了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2
import binascii
# from sage import *

n = 0x558477ce1d081f831cfa159290ee4fd14888422c216a16ad86e2b2d4335e3cb18ed0120a955f970b17b229a8e7d0ae1b6f0c40213ad0e127eba99ae0d8a82397
p = 65014198595370482567008424566891688124621484545138665561606519358457336776131
e = 0xf7278179324b11fd83d08aa6f
c = 0x36e1c09ccad45cd63a0f07e704d3811c39d70cdfdad999d2df90255a76c58cf6fe99ac1ab1d5d99a4ce1a2ebdbfbc49ce72df2a0b90766ff84ab0ef62068d46b
pp = binascii.b2a_hex(long_to_bytes(p)).decode()
print(pp)
ppp = 0x8fbcbb7d1e9f393ee21b537d6e0bd2cf8629e315f4e356c1e7c5e22d8cff45c3
q = n // ppp
phi = (ppp-1)*(q-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

2021赣网杯crypto2

这道题涉及了三元copper，又学习了新的知识点。
题干：

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
from Crypto.Util.number import *
from random import randint, getrandbits
from sympy import nextprime
from secret import flag, secreteBitNum

hint = bytes_to_long((f'secreteBitNum = {secreteBitNum}').encode())
tmp_e = 65537
tmp_p = getPrime(int(512))
tmp_q = getPrime(int(512))
tmp_N = tmp_p * tmp_q
print(f'tmp_N = {tmp_N}')
print(pow(hint, tmp_e, tmp_N))
print(tmp_p >> 180)

target_bits = int(256)
prime = getPrime(target_bits)
s = randint(prime>>10, prime)
r = getrandbits(secreteBitNum)
t = (r*(s^2 + 2*s)) % prime
gifts = [3, 2]
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
leak1 = s >> (target_bits - ks[0])
leak2 = t >> (target_bits - ks[1])

p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
q = getPrime(p.bit_length())
N = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, N)

print(f'prime = {prime}')
print(f'c = {c}')
print(f'N = {N}')
print(f'leak1 = {leak1}')
print(f'leak2 = {leak2}')

"""
tmp_N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
N = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212
"""

首先分析题目流程：
第一部分如下：

1
2
3
4
5
6
7
8
hint = bytes_to_long((f'secreteBitNum = {secreteBitNum}').encode())
tmp_e = 65537
tmp_p = getPrime(int(512))
tmp_q = getPrime(int(512))
tmp_N = tmp_p * tmp_q
print(f'tmp_N = {tmp_N}')
print(pow(hint, tmp_e, tmp_N))
print(tmp_p >> 180)

已知n、c和p的高位，可以利用一元的coppersmith求出secreteBitNum。

1
2
3
4
5
6
7
8
9
10
11
ph = 4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
pp = ph << 180
print(pp)
N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
PR.<x> = PolynomialRing(Zmod(N))
f = x+pp
pl = f.small_roots(X=2^180,beta=0.4)[0]
print(pl)
p=pp+pl
print(p)
#p=7474218428506439131024561238447007658574698902527126414652353026654065729675401366440504060759323896095490193371294094265057254763085596066166150006638181

求出p后，就可以正常流程解出明文secreteBitNum了。

1
2
3
4
5
6
7
8
9
10
tmp_e = 65537
tmp_N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
tmp_p = 7474218428506439131024561238447007658574698902527126414652353026654065729675401366440504060759323896095490193371294094265057254763085596066166150006638181
tmp_q = tmp_N // tmp_p
phi = (tmp_q-1)*(tmp_p-1)
d = gmpy2.invert(tmp_e, phi)
c = 40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
m = pow(c,d,tmp_N)
print(long_to_bytes(m))
#b'secreteBitNum = 26'

得到secreteBitNum = 26后，继续分析题目第二部分。经过运算得出ks=[192, 170]

1
2
3
4
5
6
7
8
9
target_bits = int(256)
prime = getPrime(target_bits)
s = randint(prime>>10, prime)
r = getrandbits(secreteBitNum)
t = (r*(s^2 + 2*s)) % prime
gifts = [3, 2]
ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
leak1 = s >> (target_bits - ks[0])
leak2 = t >> (target_bits - ks[1])

这是一个三元的copper，使用脚本解出s，r，t。

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
import itertools
 
def small_roots(f, bounds, m=1, d=None):
        if not d:
                d = f.degree()
 
        R = f.base_ring()
        N = R.cardinality()
        
        f /= f.coefficients().pop(0)
        f = f.change_ring(ZZ)
 
        G = Sequence([], f.parent())
        for i in range(m+1):
                base = N^(m-i) * f^i
                for shifts in itertools.product(range(d), repeat=f.nvariables()):
                        g = base * prod(map(power, f.variables(), shifts))
                        G.append(g)
 
        B, monomials = G.coefficient_matrix()
        monomials = vector(monomials)
 
        factors = [monomial(*bounds) for monomial in monomials]
        for i, factor in enumerate(factors):
                B.rescale_col(i, factor)
 
        B = B.dense_matrix().LLL()
 
        B = B.change_ring(QQ)
        for i, factor in enumerate(factors):
                B.rescale_col(i, 1/factor)
 
        H = Sequence([], f.parent().change_ring(QQ))
        for h in filter(None, B*monomials):
                H.append(h)
                I = H.ideal()
                if I.dimension() == -1:
                        H.pop()
                elif I.dimension() == 0:
                        roots = []
                        for root in I.variety(ring=ZZ):
                                root = tuple(R(root[var]) for var in f.variables())
                                roots.append(root)
                        return roots
        return []
 
def trivariate():
        print('Trivariate')
        bounds = (1<<64, 1<<86, 1<<26)
        #roots = tuple(randrange(bound) for bound in bounds)
        R = Integers(prime)
        P.<sl, tl, r> = PolynomialRing(R)
        f = ((sh + sl)**2+2*(sh+sl))*r - (th + tl)
        print(small_roots(f, bounds,6))
 
if __name__ == '__main__':
        prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
        leak1 = 4392924728395269190263639346144303703257730516994610750658
        leak2 = 838456777370923849008096179359487752850229097203212
        sh = leak1 << 64
        th = leak2 << 86
        trivariate()
#[(2837580634489900859, 63360403616040741532234070, 29943235)]

继续分析第三部分，第三部分就是简单的RSA加解密。得到flag：

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

leak1 = 4392924728395269190263639346144303703257730516994610750658
leak2 = 838456777370923849008096179359487752850229097203212
sl, tl, r = (2837580634489900859, 63360403616040741532234070, 29943235)
sh = leak1 << 64
th = leak2 << 86
s = sh+sl
t = th+tl
p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
n = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
q = n // p
phi = (p-1)*(q-1)
e = 65537
d = gmpy2.invert(e, phi)
c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
m = pow(c,d,n)
print(long_to_bytes(m))
#b'flag{bc33c490-4b95-11ec-ad04-00155d9a1603}'

附上找到的coppersmith脚本，可用于1、2、3元copper，approximate_factor，boneh_durfee

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
import itertools
 
def small_roots(f, bounds, m=1, d=None):
        if not d:
                d = f.degree()
 
        R = f.base_ring()
        N = R.cardinality()
        
        f /= f.coefficients().pop(0)
        f = f.change_ring(ZZ)
 
        G = Sequence([], f.parent())
        for i in range(m+1):
                base = N^(m-i) * f^i
                for shifts in itertools.product(range(d), repeat=f.nvariables()):
                        g = base * prod(map(power, f.variables(), shifts))
                        G.append(g)
 
        B, monomials = G.coefficient_matrix()
        monomials = vector(monomials)
 
        factors = [monomial(*bounds) for monomial in monomials]
        for i, factor in enumerate(factors):
                B.rescale_col(i, factor)
 
        B = B.dense_matrix().LLL()
 
        B = B.change_ring(QQ)
        for i, factor in enumerate(factors):
                B.rescale_col(i, 1/factor)
 
        H = Sequence([], f.parent().change_ring(QQ))
        for h in filter(None, B*monomials):
                H.append(h)
                I = H.ideal()
                if I.dimension() == -1:
                        H.pop()
                elif I.dimension() == 0:
                        roots = []
                        for root in I.variety(ring=ZZ):
                                root = tuple(R(root[var]) for var in f.variables())
                                roots.append(root)
                        return roots
        return []
 
def univariate():
        print('Univariate')
        bounds = (floor(N^.3),)
        roots = tuple(randrange(bound) for bound in bounds)
        R = Integers(N)
        P.<x> = PolynomialRing(R, 1)
        monomials = [x, x^2, x^3]
        f = sum(randrange(N)*monomial for monomial in monomials)
        f -= f(*roots)
        print(small_roots(f, bounds, m=7))
 
def bivariate():
        print('Bivariate')
        bounds = (floor(N^.15), floor(N^.15))
        roots = tuple(randrange(bound) for bound in bounds)
        R = Integers(N)
        P.<x, y> = PolynomialRing(R)
        monomials = [x, y, x*y, x^2]
        f = sum(randrange(N)*monomial for monomial in monomials)
        f -= f(*roots)
        print(small_roots(f, bounds))
 
def trivariate():
        print('Trivariate')
        bounds = (floor(N^.12), floor(N^.12), floor(N^.12))
        roots = tuple(randrange(bound) for bound in bounds)
        R = Integers(N)
        P.<x, y, z> = PolynomialRing(R)
        monomials = [x, y, x*y, x*z, y*z]
        f = sum(randrange(N)*monomial for monomial in monomials)
        f -= f(*roots)
        print(small_roots(f, bounds))
 
def boneh_durfee():
        print('Boneh Durfee')
        bounds = (floor(N^.25), 2^1024)
        d = random_prime(bounds[0])
        e = inverse_mod(d, (p-1)*(q-1))
        roots = (e*d//((p-1)*(q-1)), (p+q)//2)
        R = Integers(e)
        P.<k, s> = PolynomialRing(R)
        f = 2*k*((N+1)//2 - s) + 1
        print(small_roots(f, bounds, m=3, d=4))
 
def approximate_factor():
        print('Approximate factor')
        bounds = (floor(N^.05), floor(N^.05))
        roots = tuple(randrange(bound) for bound in bounds)
        R = Integers(N)
        P = PolynomialRing(R, len(bounds), 'x')
        f = sum(randrange(2^128)*x for x in P.gens())
        f += p - f(*roots)
        print(small_roots(f, bounds, m=2, d=4))
 
if __name__ == '__main__':
        print('Generating primes')
        p = random_prime(2^1024)
        q = random_prime(2^1024)
        N = p*q
        univariate()
        bivariate()
        trivariate()
        boneh_durfee()
        approximate_factor()