2021赣网杯题目收录

pukr

1. e1、e2不互素的共模攻击
2.多元coppersmith

pukr

题干：

1. ZnJvbSBzZWNyZXQgaW1wb3J0IGZsYWcKZnJvbSBDcnlwdG8uVXRpbC5udW1iZXIgaW1wb3J0ICoKCm0gPSBieXRlc190b19sb25nKGZsYWcpCgplMSA9IDY2NzQzMDEwNDg2NTI4OQplMiA9IDUzNzQwOTkzMDUyMzQyMQpwID0gZ2V0UHJpbWUoNTEyKQpxID0gZ2V0UHJpbWUoNTEyKQpuID0gcCpxCmMxID0gcG93KG0sIGUxLCBuKQpjMiA9IHBvdyhtLCBlMiwgbikKCnByaW50KGYnYzEgPSB7YzF9JykKcHJpbnQoZidjMiA9IHtjMn0nKQpwcmludChmJ24gPSB7bn0nKQoiIiIKYzEgPSA2NTkwMjY3ODU3MjcyNzcyNDE3OTE3NjQ5NjU3Mzk2ODk5NzE4MjcxMjA2MzMxNzA4MjI4OTEyMDQ1MzA5NDA2ODE5OTMyNTQxOTk4OTY4ODM4MjE3NzgwODUyOTA0MjMyMjIxNzg4NzMzNDAwNTA4NDUwNDc5NjM5NzIyMDgwNDg1NjE2NzI1NTE3NjQxNTY5MDIxNzM0ODI1MjEyNjA5NzgwOTEzMDE5NTIwODAyMDY5NDAyNjI1MDE5NDA0NzQ2MDU4MTE2NTAyNDE3ODM1ODQzNDMwNTQ5NTM2NDk4MzgzMDc1NjU1MjM3OTMzNTk4NTM5OTg3NjUyODkyMjA3NjAzMDU5NTIzMjY3OTA0Njk0MTMxMDc4NjYzNzI2MDc2NDk5MjQ5OTM3NTQyMTQ2NDUyOQpjMiA9IDg1ODA5NDAzNjc4MjUwMTUwMTUzMjkxNDcxMTg1OTk5ODA1ODcwODU4MTIzMDAxMjczMDM0MjEyNTgyODQ3NzMxODI1Mjk2ODkxMDE2ODEwODcxMzk3NTQ2MTM0MTE3MDEyMTk3NTk5NjUxNzI5NDAxNTkwOTgwMDIwMDI4MzgyODg0MDY4NTEzMjAxNzU4OTI2NDE2MTkyMjExODIxOTIyNTkzNjg2MjMyNDc1OTY3ODA4OTY0MDA2Nzg2MDc2NDYwMTYwNDI4NjM5MzUzMTUzNjU4MzIzMjA4MTE5NDUzMDU1MDcwMTk5MjQzMjk1MzMwNTIyODA0OTc0ODQ5MzMwOTI2NTAxMDkxNDMwNDE5Nzc1MTU1NjcwMjY0MzA2MjIyOTYyNDEzMjg5NjE2OTU3NTE5Cm4gPSA5MzAxMjM3OTk0OTU5NjY3OTg3NDAxMDgzNjUyMDk3MjQ2MzQzODE1NTE3NTk2MTI4MzI3Nzc0MzUxNDIwMzg3MTExNDMyOTAwODA0NDczNTUwMDcyNjQ0MDAxMjQ2NDAyOTE0NDIwNDgxMzQxMzkwOTMyMjM4OTU4NTk2NjMxMzQyNjYxMTQ4ODkyNzI5Mjg3NDMxOTYyODA2MzUyNjAwOTQwNTE0NDQzNjYwNTk5NjM4OTk4NTk3NzM0MDI4MDk4MzQ2OTgwMzQxMjExOTQ1ODE4NTA0NzQ3NTI1MzA1OTYzNjEyNjU1NTQ1MTU1NzM0ODE2OTUxNDk3NTI0OTcxMDkwMTg5OTUyNjk3NDI0NjEzOTU1OTczMDQ2MTU0MDY2MDk5MDM3NTAzNDY2OTA0Mjk1OQoiIiI=

复制代码

base64解码之后：

1. from secret import flag
   
2. from Crypto.Util.number import *
   
3. 
   
4. m = bytes_to_long(flag)
   
5. 
   
6. e1 = 667430104865289
   
7. e2 = 537409930523421
   
8. p = getPrime(512)
   
9. q = getPrime(512)
   
10. n = p*q
    
11. c1 = pow(m, e1, n)
    
12. c2 = pow(m, e2, n)
    
13. 
    
14. print(f'c1 = {c1}')
    
15. print(f'c2 = {c2}')
    
16. print(f'n = {n}')
    
17. """
    
18. c1 = 65902678572727724179176496573968997182712063317082289120453094068199325419989688382177808529042322217887334005084504796397220804856167255176415690217348252126097809130195208020694026250194047460581165024178358434305495364983830756552379335985399876528922076030595232679046941310786637260764992499375421464529
    
19. c2 = 85809403678250150153291471185999805870858123001273034212582847731825296891016810871397546134117012197599651729401590980020028382884068513201758926416192211821922593686232475967808964006786076460160428639353153658323208119453055070199243295330522804974849330926501091430419775155670264306222962413289616957519
    
20. n = 93012379949596679874010836520972463438155175961283277743514203871114329008044735500726440012464029144204813413909322389585966313426611488927292874319628063526009405144436605996389985977340280983469803412119458185047475253059636126555451557348169514975249710901899526974246139559730461540660990375034669042959
    
21. """

复制代码

​​​

1. import gmpy2
   
2. from Crypto.Util.number import *
   
3. 
   
4. c1 = 65902678572727724179176496573968997182712063317082289120453094068199325419989688382177808529042322217887334005084504796397220804856167255176415690217348252126097809130195208020694026250194047460581165024178358434305495364983830756552379335985399876528922076030595232679046941310786637260764992499375421464529
   
5. c2 = 85809403678250150153291471185999805870858123001273034212582847731825296891016810871397546134117012197599651729401590980020028382884068513201758926416192211821922593686232475967808964006786076460160428639353153658323208119453055070199243295330522804974849330926501091430419775155670264306222962413289616957519
   
6. n = 93012379949596679874010836520972463438155175961283277743514203871114329008044735500726440012464029144204813413909322389585966313426611488927292874319628063526009405144436605996389985977340280983469803412119458185047475253059636126555451557348169514975249710901899526974246139559730461540660990375034669042959
   
7. 
   
8. e1 = 667430104865289
   
9. e2 = 537409930523421
   
10. 
    
11. g = gmpy2.gcd(e1, e2)
    
12. print(g)
    
13. # g = 3
    
14. l, x, y = gmpy2.gcdext(e1//3, e2//3)
    
15. print(x, y)
    
16. 
    
17. m = pow(c1, x, n)*pow(c2, y, n) % n
    
18. m = gmpy2.iroot(m, 3)
    
19. m = 56006392793429430154056421945568912277006938354753284086685860659829848328383664134484234657728574333
    
20. print(long_to_bytes(m))

复制代码

pukr

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

1. from Crypto.Util.number import *
   
2. from random import randint, getrandbits
   
3. from sympy import nextprime
   
4. from secret import flag, secreteBitNum
   
5. 
   
6. hint = bytes_to_long((f'secreteBitNum = {secreteBitNum}').encode())
   
7. tmp_e = 65537
   
8. tmp_p = getPrime(int(512))
   
9. tmp_q = getPrime(int(512))
   
10. tmp_N = tmp_p * tmp_q
    
11. print(f'tmp_N = {tmp_N}')
    
12. print(pow(hint, tmp_e, tmp_N))
    
13. print(tmp_p >> 180)
    
14. 
    
15. target_bits = int(256)
    
16. prime = getPrime(target_bits)
    
17. s = randint(prime>>10, prime)
    
18. r = getrandbits(secreteBitNum)
    
19. t = (r*(s^2 + 2*s)) % prime
    
20. gifts = [3, 2]
    
21. ks = [floor(target_bits * (gift / (gift + 1))) for gift in gifts]
    
22. leak1 = s >> (target_bits - ks[0])
    
23. leak2 = t >> (target_bits - ks[1])
    
24. 
    
25. p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
    
26. q = getPrime(p.bit_length())
    
27. N = p*q
    
28. e = 65537
    
29. m = bytes_to_long(flag)
    
30. c = pow(m, e, N)
    
31. 
    
32. print(f'prime = {prime}')
    
33. print(f'c = {c}')
    
34. print(f'N = {N}')
    
35. print(f'leak1 = {leak1}')
    
36. print(f'leak2 = {leak2}')
    
37. 
    
38. """
    
39. tmp_N = 67275889677378946734903321404206582364153218707836044936581311977721676158433934674861722018390091292542128885311842688233567992017423854706617140651934525455990460080562308585391373661331461122947028205118969966760791488914164391921330229025670176008518053339148134137770309365614255463111202481834705060173
    
40. 40399377632586118650556149454962332599993544072289982576457293479237148938553095258299197606759611718110458893982875730643146645623512300513916266262798465380752083932871857821720398540072426424439422364690204675516506456125988918985863308292449915493404572808822346197667419207669315093927318993921905479596
    
41. 4877155090632997781879191807827231697420271396210537080241322765167927413977000532975047982026915056
    
42. prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
    
43. c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
    
44. N = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
    
45. leak1 = 4392924728395269190263639346144303703257730516994610750658
    
46. leak2 = 838456777370923849008096179359487752850229097203212
    
47. """

复制代码

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

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

复制代码

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

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

复制代码

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

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

复制代码

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

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

复制代码

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

1. import itertools
   
2. 
   
3. def small_roots(f, bounds, m=1, d=None):
   
4.         if not d:
   
5.                 d = f.degree()
   
6. 
   
7.         R = f.base_ring()
   
8.         N = R.cardinality()
   
9.         
   
10.         f /= f.coefficients().pop(0)
    
11.         f = f.change_ring(ZZ)
    
12. 
    
13.         G = Sequence([], f.parent())
    
14.         for i in range(m+1):
    
15.                 base = N^(m-i) * f^i
    
16.                 for shifts in itertools.product(range(d), repeat=f.nvariables()):
    
17.                         g = base * prod(map(power, f.variables(), shifts))
    
18.                         G.append(g)
    
19. 
    
20.         B, monomials = G.coefficient_matrix()
    
21.         monomials = vector(monomials)
    
22. 
    
23.         factors = [monomial(*bounds) for monomial in monomials]
    
24.         for i, factor in enumerate(factors):
    
25.                 B.rescale_col(i, factor)
    
26. 
    
27.         B = B.dense_matrix().LLL()
    
28. 
    
29.         B = B.change_ring(QQ)
    
30.         for i, factor in enumerate(factors):
    
31.                 B.rescale_col(i, 1/factor)
    
32. 
    
33.         H = Sequence([], f.parent().change_ring(QQ))
    
34.         for h in filter(None, B*monomials):
    
35.                 H.append(h)
    
36.                 I = H.ideal()
    
37.                 if I.dimension() == -1:
    
38.                         H.pop()
    
39.                 elif I.dimension() == 0:
    
40.                         roots = []
    
41.                         for root in I.variety(ring=ZZ):
    
42.                                 root = tuple(R(root[var]) for var in f.variables())
    
43.                                 roots.append(root)
    
44.                         return roots
    
45.         return []
    
46. 
    
47. def trivariate():
    
48.         print('Trivariate')
    
49.         bounds = (1<<64, 1<<86, 1<<26)
    
50.         #roots = tuple(randrange(bound) for bound in bounds)
    
51.         R = Integers(prime)
    
52.         P.<sl, tl, r> = PolynomialRing(R)
    
53.         f = ((sh + sl)**2+2*(sh+sl))*r - (th + tl)
    
54.         print(small_roots(f, bounds,6))
    
55. 
    
56. if __name__ == '__main__':
    
57.         prime = 82321753209337659641812698792368753307257174920293482309329229017641186204037
    
58.         leak1 = 4392924728395269190263639346144303703257730516994610750658
    
59.         leak2 = 838456777370923849008096179359487752850229097203212
    
60.         sh = leak1 << 64
    
61.         th = leak2 << 86
    
62.         trivariate()
    
63. #[(2837580634489900859, 63360403616040741532234070, 29943235)]

复制代码

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

1. import gmpy2
   
2. from Crypto.Util.number import *
   
3. from sympy import nextprime
   
4. 
   
5. leak1 = 4392924728395269190263639346144303703257730516994610750658
   
6. leak2 = 838456777370923849008096179359487752850229097203212
   
7. sl, tl, r = (2837580634489900859, 63360403616040741532234070, 29943235)
   
8. sh = leak1 << 64
   
9. th = leak2 << 86
   
10. s = sh+sl
    
11. t = th+tl
    
12. p = nextprime((s*(nextprime(s) * nextprime(r) + t)))
    
13. n = 43941665823196509154346632368475246193489316520677500866461851257383928558997955146720003171553041820199105630143274308184375615057136594812756966125202091119439909980006181740220827474838356621605513939553184451557022029987518161532780360148932769025277495283357745880781214097057768654158857096614016596756958574010574773
    
14. q = n // p
    
15. phi = (p-1)*(q-1)
    
16. e = 65537
    
17. d = gmpy2.invert(e, phi)
    
18. c = 4327179356609269294409009935591795772603625779675971467878490086808144060225614005300908314649047950861015994603326121468330956776913366179511247457747179889685304469999218104955814145411915021238933150884498316563808220329632240175418452382843973948334446343545955570063628905102384071000832724697885872043017030707897928
    
19. m = pow(c,d,n)
    
20. print(long_to_bytes(m))
    
21. #b'flag{bc33c490-4b95-11ec-ad04-00155d9a1603}'

复制代码

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

1. import itertools
   
2. 
   
3. def small_roots(f, bounds, m=1, d=None):
   
4.         if not d:
   
5.                 d = f.degree()
   
6. 
   
7.         R = f.base_ring()
   
8.         N = R.cardinality()
   
9.         
   
10.         f /= f.coefficients().pop(0)
    
11.         f = f.change_ring(ZZ)
    
12. 
    
13.         G = Sequence([], f.parent())
    
14.         for i in range(m+1):
    
15.                 base = N^(m-i) * f^i
    
16.                 for shifts in itertools.product(range(d), repeat=f.nvariables()):
    
17.                         g = base * prod(map(power, f.variables(), shifts))
    
18.                         G.append(g)
    
19. 
    
20.         B, monomials = G.coefficient_matrix()
    
21.         monomials = vector(monomials)
    
22. 
    
23.         factors = [monomial(*bounds) for monomial in monomials]
    
24.         for i, factor in enumerate(factors):
    
25.                 B.rescale_col(i, factor)
    
26. 
    
27.         B = B.dense_matrix().LLL()
    
28. 
    
29.         B = B.change_ring(QQ)
    
30.         for i, factor in enumerate(factors):
    
31.                 B.rescale_col(i, 1/factor)
    
32. 
    
33.         H = Sequence([], f.parent().change_ring(QQ))
    
34.         for h in filter(None, B*monomials):
    
35.                 H.append(h)
    
36.                 I = H.ideal()
    
37.                 if I.dimension() == -1:
    
38.                         H.pop()
    
39.                 elif I.dimension() == 0:
    
40.                         roots = []
    
41.                         for root in I.variety(ring=ZZ):
    
42.                                 root = tuple(R(root[var]) for var in f.variables())
    
43.                                 roots.append(root)
    
44.                         return roots
    
45.         return []
    
46. 
    
47. def univariate():
    
48.         print('Univariate')
    
49.         bounds = (floor(N^.3),)
    
50.         roots = tuple(randrange(bound) for bound in bounds)
    
51.         R = Integers(N)
    
52.         P.<x> = PolynomialRing(R, 1)
    
53.         monomials = [x, x^2, x^3]
    
54.         f = sum(randrange(N)*monomial for monomial in monomials)
    
55.         f -= f(*roots)
    
56.         print(small_roots(f, bounds, m=7))
    
57. 
    
58. def bivariate():
    
59.         print('Bivariate')
    
60.         bounds = (floor(N^.15), floor(N^.15))
    
61.         roots = tuple(randrange(bound) for bound in bounds)
    
62.         R = Integers(N)
    
63.         P.<x, y> = PolynomialRing(R)
    
64.         monomials = [x, y, x*y, x^2]
    
65.         f = sum(randrange(N)*monomial for monomial in monomials)
    
66.         f -= f(*roots)
    
67.         print(small_roots(f, bounds))
    
68. 
    
69. def trivariate():
    
70.         print('Trivariate')
    
71.         bounds = (floor(N^.12), floor(N^.12), floor(N^.12))
    
72.         roots = tuple(randrange(bound) for bound in bounds)
    
73.         R = Integers(N)
    
74.         P.<x, y, z> = PolynomialRing(R)
    
75.         monomials = [x, y, x*y, x*z, y*z]
    
76.         f = sum(randrange(N)*monomial for monomial in monomials)
    
77.         f -= f(*roots)
    
78.         print(small_roots(f, bounds))
    
79. 
    
80. def boneh_durfee():
    
81.         print('Boneh Durfee')
    
82.         bounds = (floor(N^.25), 2^1024)
    
83.         d = random_prime(bounds[0])
    
84.         e = inverse_mod(d, (p-1)*(q-1))
    
85.         roots = (e*d//((p-1)*(q-1)), (p+q)//2)
    
86.         R = Integers(e)
    
87.         P.<k, s> = PolynomialRing(R)
    
88.         f = 2*k*((N+1)//2 - s) + 1
    
89.         print(small_roots(f, bounds, m=3, d=4))
    
90. 
    
91. def approximate_factor():
    
92.         print('Approximate factor')
    
93.         bounds = (floor(N^.05), floor(N^.05))
    
94.         roots = tuple(randrange(bound) for bound in bounds)
    
95.         R = Integers(N)
    
96.         P = PolynomialRing(R, len(bounds), 'x')
    
97.         f = sum(randrange(2^128)*x for x in P.gens())
    
98.         f += p - f(*roots)
    
99.         print(small_roots(f, bounds, m=2, d=4))
    
100. 
     
101. if __name__ == '__main__':
     
102.         print('Generating primes')
     
103.         p = random_prime(2^1024)
     
104.         q = random_prime(2^1024)
     
105.         N = p*q
     
106.         univariate()
     
107.         bivariate()
     
108.         trivariate()
     
109.         boneh_durfee()
     
110.         approximate_factor()

复制代码