Easy Inverse

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

p = getPrime(1024)

bits = 100

from secret import flag

m = bytes_to_long(flag)

hints = [pow(m , -1 , p) , pow(m+1 , -2 , p)]

hints_leak = [(i>>bits)<<bits for i in hints]

print(f"hints_leak = {hints_leak}")

print(f"p = {p}")
1
2
hints_leak = [85087968263053094137295898122774543767340866981881221187161331084750073034946312830152243136278193786647624244148251203723569658586218694461676132129946283285260019766581705113083117435703613046652569700387032700058973716086805709015211156286694421133955852665288613854427446792388176324143130965816809357312, 67953886539653632038920058385569870493028907800417602912168795585718886827421928318645309932467687156357978972318120982952450752486408764973440214596668821879638339855067283580190400780442147570633516946031214900389229596583496212632439158451698379617020982467162469496186638155326522874702539730838171418624]
p = 149367731171762330066795353851009601282518104440514354255019642516361621316141660496793544426399496814814001546594935014194869175105734549520773678981277968609540316344934477111702229274792495581254158950178095767214664457685340626949087936752852111450053123667452643108823479540937730365562189323672637072001

题目十分简洁

首先题目给了两个hint Hint1 = m−1 mod  p

Hint2 = (m + 1)−2 mod  p

然后将两个Hint的低100位变为0

那么两式可以改写为 (Hint1leak + x) = m−1 mod  p

(Hint1leak + x)−1 = m mod  p

(Hint2leak + y) = (m + 1)−2 mod  p

(Hint2leak + y)−2 − 1 = m mod  p

接下来就是用二元cooper来解出x和y

这里我们不妨碍令 $$ \begin{cases} & A=Hint1_leak+x \\ & B=Hint2_leak+x \end{cases} $$ 这里可以看到 A−1 = m mod  p 这里是对两边同时取模反元素 (m + 1)2 = B−1 mod  p 将第一式带入二式中 (A−1 + 1)2 = B−1 mod  p

((A + 1)/A)2 = B−1 mod  p

(A + 1)2/A2 = B−1 mod  p

(A + 1)2 = B−1 * A2 mod  p

(A + 1)2 * B − A2 = 0 mod  p

由此我可以得到多项式

1
f = (hint2_leak + y) * (1 + hint1_leak + x)**2 - (hint1_leak + x)**2

接下来打个二元cooper即可

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
111
112
113
114
115
116
117
118
119
120
121
from Crypto.Util.number import *

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 []

hints_leak = [85087968263053094137295898122774543767340866981881221187161331084750073034946312830152243136278193786647624244148251203723569658586218694461676132129946283285260019766581705113083117435703613046652569700387032700058973716086805709015211156286694421133955852665288613854427446792388176324143130965816809357312, 67953886539653632038920058385569870493028907800417602912168795585718886827421928318645309932467687156357978972318120982952450752486408764973440214596668821879638339855067283580190400780442147570633516946031214900389229596583496212632439158451698379617020982467162469496186638155326522874702539730838171418624]

p = 149367731171762330066795353851009601282518104440514354255019642516361621316141660496793544426399496814814001546594935014194869175105734549520773678981277968609540316344934477111702229274792495581254158950178095767214664457685340626949087936752852111450053123667452643108823479540937730365562189323672637072001

hint1_leak, hint2_leak = hints_leak

bounds = (2**100, 2**100)

R.<x, y> = Zmod(p)[]

f = (hint2_leak + y) * (1 + hint1_leak + x)**2 - (hint1_leak + x)**2

roots = small_roots(f, bounds, m=5, d=4, )

if roots:

  x_val, y_val = roots[0]

  k1 = (hint1_leak + x_val) % p

  m = inverse_mod(int(k1), p)

  print(f"Flag: {long_to_bytes(m)}")

else:

  print("No roots found")

MTH211

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
from Crypto.Util.number import getPrime,isPrime,GCD,bytes_to_long

from secrets import flag

p = getPrime(256)

q = getPrime(256)

phi = (p-1)*(q-1)

g = getPrime(256)

n = p*q

e = 13

p1 = getPrime(28)

p2 = getPrime(28)

K = p1*p2

gift =pow(K,e,n)

print(f"gift={gift}")


K *= g #enough padding of the key to prevent boneh durfee attacks

assert GCD(K,phi) == 1

e = pow(K,-1,phi)

cipher = pow(bytes_to_long(flag),e,n)

print(f"n={n}")

print(f"cipher={cipher}")

print(f"e={e}")

print(f"g={g}")

'''

gift=9849116110348955789479010194217500434924628821283154420120653296317850482069813955763227679617407203690983933060408814831540731516918111919543171982943742

n=10192317563100435820324883212732654109601026477813807473477878848573139071076450236118688980932037415251346520514542138140609060252895351951720245780911857

cipher=5233505605717906572820704125698007884756899600546277154250677229608622104923213916257278306210268480306253062577662108243267456434157595354492257249291619

e=6680156158150988373642322463932951077800266014102151350333710885437380635984671611153081168925510577011108052179392804404171397616499204018327041380331715

g=79311846630906367242578569989060951934653320046283047846150092277845194835891

'''

分析代码，我们需要先求出K

直接用MITM算法来实现暴力搜索

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
from Crypto.Util.number import isPrime, inverse
import gmpy2
from tqdm import tqdm

def mitm_attack(gift, e, n, prime_bits=28):

    
    print("生成28位素数列表...")
    

    low = 2**(prime_bits-1)
    high = 2**prime_bits - 1
    

    
    # 使用gmpy2进行快速幂运算和模逆
    for p1 in tqdm(range(low, high + 1), desc="搜索p1"):
        if not isPrime(p1):
            continue
            
        try:
            # 计算 p1^{-e} mod n
            p1_inv = inverse(p1, n)
            p1_inv_e = pow(p1_inv, e, n)
            
            # 计算 temp = gift * p1^{-e} mod n
            temp = (gift * p1_inv_e) % n
            
            # 检查temp是否是某个素数的e次幂
            # 即求temp的e次根
            root, exact = gmpy2.iroot(temp, e)
            if exact and isPrime(root) and low <= root <= high:
                p2 = root
                K = p1 * p2
                print(f"找到p1 = {p1}")
                print(f"找到p2 = {p2}")
                print(f"K = {K}")
                return K, p1, p2
                
        except:
            continue
    
    return None


gift = 9849116110348955789479010194217500434924628821283154420120653296317850482069813955763227679617407203690983933060408814831540731516918111919543171982943742
e = 13
n = 10192317563100435820324883212732654109601026477813807473477878848573139071076450236118688980932037415251346520514542138140609060252895351951720245780911857

result = mitm_attack(gift, e, n)
if result:
    K, p1, p2 = result
    print(f"成功恢复K: {K}")
else:
    print("攻击失败")

得到K之后就简单了

题目中定义了

e = pow(K,-1,phi)

因此私钥d=K*d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import long_to_bytes

K = 39977278697417449

g = 79311846630906367242578569989060951934653320046283047846150092277845194835891

n = 10192317563100435820324883212732654109601026477813807473477878848573139071076450236118688980932037415251346520514542138140609060252895351951720245780911857

cipher = 5233505605717906572820704125698007884756899600546277154250677229608622104923213916257278306210268480306253062577662108243267456434157595354492257249291619

d = K * g

m = pow(cipher, d, n)

flag = long_to_bytes(m)

print(flag)