a ctfer on the load

1
from Crypto.Util.number import *
2
import decimal
3
m=long_to_bytes("?????")
4
p=getPrime(1024)
5
while True:
6
    q=getPrime(1024)
7
    if p>q:
8
        break
9
n=p*q
10
e="?????"
11
d=inverse(e,(p-1)*(q-1))
12
c=pow(m,e,n)
13
decimal.getcontext().prec = 1024
14
P=decimal.Decimal(p)
15
Q=decimal.Decimal(q)
16
leak=decimal.Decimal((3*P*P-1)/(3*P*Q))
17
print("c =",c)
18
print("leak =",leak)
19
print("d =",d)

1
c = 7908369000608075306226552240713890041649799894903074579356627811865842237315201153498579205223600526520994811661608630888045462921547166872107507948062717836952855804806976414887413729060431265217539895710936669089248515746191716161194996469977577048602427553584286064475300979649416171469313168995504717602670924606819204605601860560767900702512753735554900344201907921239415885901489708576066483012272256175573658509614344875077232108364134161997767814675830320630271209201503987787921279932886374846298269125068817280777403718279754392091441050281244934594776307137448975055247018414699621410668188864774860026941
2

3
leak = 1.396995694831414203476063690838730308815841662737318558906107823553922718340982125801595368449608188770051881765292978548960520326036779130167518285237817101541807766017642530065080930654694948943506714268685400709580398894902693407016988670394423892586264077247263710263220932577837642377245651448838665854362532801659965471421937839336237670710012298796758992931116659292915200628873553198226185187089027680973673618973869464164460226697625936493428822424637497370197316811245879504779934098600596822159243994319583651080005054538419168988020562590543262648544970376255020489363894055887067948343768399654357738592577280906555896933717091837896978973488220368081406433117367524537063718421897982643644320078600517763936883820416362057895941185749296170109172249907094176821124345672294602380784325702476105763209165109703429326132417850746805701054961710623030742187505484821961670922386999933202645522248608323217011522889282323071281405301772218220381951540118124201599862330377374571641729649420917168701463539034702411
4

5
d = 16306054997613721520756151430779642117683661431522665108784419231044104572118893098180652730976905729602478591047033305251624752030036736271198006715513694904231940253554804069707679445942892410812386221633728427239116007373836662495075237456279818311659331982404534490546781763464409713789636372508503902598331950861474527128323735250673137355260113147338636761737748874105625008482750923429512271416511835596944209137554445130949731646669691366003832655082535985891463876904334888009751956386994969339847254470145428608062575606120441725590059524749595027078238962391188809496875025237129899849787699468205026040721
6

7
from Crypto.Util.number import *
8

9
cf = continued_fraction(leak)
10
convers = cf.convergents()
11
for pkd in convers:
12
    # possible k, d
13
    pp, pq = pkd.as_integer_ratio()
14
    pp=int(pp)
15
    if pp.bit_length()==1024 and isPrime(pp):
16
        flag=long_to_bytes(int(pow(c,d,pp)))
17
        if b'flag' in flag:
18
            print(flag)
19
            break

1
from Crypto.Util.number import *
2
from secret import FLAG,x,y
3

4
f0= bytes_to_long(FLAG[:len(FLAG)//2].encode())
5
f1= bytes_to_long(FLAG[len(FLAG)//2:].encode())
6

7
n= int()
8
c= int()
9
gift1= int()
10
gift2= int()
11

12

13
m=getPrime(1876)
14
p=getPrime(1024)
15
q=getPrime(1024)
16
print(p,q)
17
n=p*q
18
e=65537
19
c=pow(m,e,n)
20
print('n=',n)
21
print('c=',c)
22
print('gift1=',1293023064232431070902426583269468463*x**2-105279230912868770223946474836383391725923*y**2)
23
print('gift2=',(p**7+q**13)&(2**777-1))
24

25
assert (x*f0+y*f1)%m <2**99

1
from Crypto.Util.number import *
2
from gmpy2 import *
3
from sage.all import *
4
from sympy.core.intfunc import iroot
5
from sympy.solvers.diophantine.diophantine import diop_DN
6

7
n= int(18443962106578943927922829208562388331564422618353954662348987125496135728205879853444693999188714508145409575298801277623433658530589571956301880815632542860363148763704636874275223979061507756787642735086825973011622866458454405794279633717255674221895468734500735123736684346340314680683830866884050311047424068122453972745273167956795195575475691048908906061023817574695902603984554911326264947716547564759877947888574515784489778380086664649338093680740990860192640619047071160362288611331225632270531304525264824445326394068892806774552310748255977040249822464839809344521107040968321810533993659358229305320413)
8
c= int(8176283809770578639445916571748890916863681496488338436815389781344271720445865752568007651231910205530735296305471880971422173915403956857863330698931559658909826642456860761540607878553228782799635976463090037022164739976302533892173751687781100980039065722082091714141141136171701360981540040678479802206949078162548124224838019262997441233919136963696523351831737708850863538007579105976954619102728135600542584651031405327214877358323388674864043740117718200022790892542634633918493245432384562983429810936975869853596007429259749282607844407676244954057886824475948603911174707176467261179324130051317766768127)
9
gift1= int(1293023064232431070902426583269468463)
10
gift2= int(26161714402997656593966327522661504448812191236385246127313450633226841096347099194721417620572738092514050785292503472019045698167235604357096118735431692892202119807587271344465029467089266358735895706496467947787464475365718387614)
11

12
x = diop_DN(105279230912868770223946474836383391725923//1293023064232431070902426583269468463,gift1//1293023064232431070902426583269468463)[0][0]
13
yy=(1293023064232431070902426583269468463*x**2-gift1)//105279230912868770223946474836383391725923
14
y=iroot(yy,2)[0]
15
print(x)
16
print(y)
17
x=int(x)
18
y=int(y)
19
p = 110321094976129707319520600986374898031772388334195419291797204096276942296698733990367680023948047820442401228783658911134388494335281166694315709721180388295015528680094263090624783953349710316927409137594927749594230788983109047830897067234559148509079478238626283574442539878131266374870841191635047394681
20
q = 167184364065364685056497190415155636144720644950725295920271367595483444357416641085807605674441141156570389367370149531967480290218274897524375212202875627325755457975276196034582673268786547482587150378645612877166485244134843695743056623756823734183252667243967918491196265305063449882555425959453836272773
21
m=pow(c,inverse(65537,(p-1)*(q-1)),n)
22
W=2**100
23
M = Matrix(ZZ, [
24
            [1, 0, x * W],
25
            [0, 1, y * W],
26
            [0, 0, m * W]
27
        ])
28
L=M.LLL()
29
for row in L:
30
    try:
31
        r0 = abs(row[0])
32
        r1 = abs(row[1])
33
        r2 = abs(row[2])
34

35
        p1 = long_to_bytes(r0)
36
        p2 = long_to_bytes(r1)
37
        p3=long_to_bytes(r2)
38

39
        print(p1)
40
        print(p2)
41
        print(p3)
42
    except Exception:
43
        continue

1
from __future__ import print_function
2
import time
3

4
############################################
5
# Config
6
##########################################
7

8
"""
9
Setting debug to true will display more informations
10
about the lattice, the bounds, the vectors...
11
"""
12
debug = True
13

14
"""
15
Setting strict to true will stop the algorithm (and
16
return (-1, -1)) if we don't have a correct
17
upperbound on the determinant. Note that this
18
doesn't necesseraly mean that no solutions
19
will be found since the theoretical upperbound is
20
usualy far away from actual results. That is why
21
you should probably use `strict = False`
22
"""
23
strict = False
24

25
"""
26
This is experimental, but has provided remarkable results
27
so far. It tries to reduce the lattice as much as it can
28
while keeping its efficiency. I see no reason not to use
29
this option, but if things don't work, you should try
30
disabling it
31
"""
32
helpful_only = True
33
dimension_min = 7 # stop removing if lattice reaches that dimension
34

35
############################################
36
# Functions
37
##########################################
38

39
# display stats on helpful vectors
40
def helpful_vectors(BB, modulus):
41
    nothelpful = 0
42
    for ii in range(BB.dimensions()[0]):
43
        if BB[ii,ii] >= modulus:
44
            nothelpful += 1
45

46
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
47

48
# display matrix picture with 0 and X
49
def matrix_overview(BB, bound):
50
    for ii in range(BB.dimensions()[0]):
51
        a = ('%02d ' % ii)
52
        for jj in range(BB.dimensions()[1]):
53
            a += '0' if BB[ii,jj] == 0 else 'X'
54
            if BB.dimensions()[0] < 60:
55
                a += ' '
56
        if BB[ii, ii] >= bound:
57
            a += '~'
58
        print(a)
59

60
# tries to remove unhelpful vectors
61
# we start at current = n-1 (last vector)
62
def remove_unhelpful(BB, monomials, bound, current):
63
    # end of our recursive function
64
    if current == -1 or BB.dimensions()[0] <= dimension_min:
65
        return BB
66

67
    # we start by checking from the end
68
    for ii in range(current, -1, -1):
69
        # if it is unhelpful:
70
        if BB[ii, ii] >= bound:
71
            affected_vectors = 0
72
            affected_vector_index = 0
73
            # let's check if it affects other vectors
74
            for jj in range(ii + 1, BB.dimensions()[0]):
75
                # if another vector is affected:
76
                # we increase the count
77
                if BB[jj, ii] != 0:
78
                    affected_vectors += 1
79
                    affected_vector_index = jj
80

81
            # level:0
82
            # if no other vectors end up affected
83
            # we remove it
84
            if affected_vectors == 0:
85
                print("* removing unhelpful vector", ii)
86
                BB = BB.delete_columns([ii])
87
                BB = BB.delete_rows([ii])
88
                monomials.pop(ii)
89
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
90
                return BB
91

92
            # level:1
93
            # if just one was affected we check
94
            # if it is affecting someone else
95
            elif affected_vectors == 1:
96
                affected_deeper = True
97
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
98
                    # if it is affecting even one vector
99
                    # we give up on this one
100
                    if BB[kk, affected_vector_index] != 0:
101
                        affected_deeper = False
102
                # remove both it if no other vector was affected and
103
                # this helpful vector is not helpful enough
104
                # compared to our unhelpful one
105
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
106
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
107
                    BB = BB.delete_columns([affected_vector_index, ii])
108
                    BB = BB.delete_rows([affected_vector_index, ii])
109
                    monomials.pop(affected_vector_index)
110
                    monomials.pop(ii)
111
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
112
                    return BB
113
    # nothing happened
114
    return BB
115

116
"""
117
Returns:
118
* 0,0   if it fails
119
* -1,-1 if `strict=true`, and determinant doesn't bound
120
* x0,y0 the solutions of `pol`
121
"""
122
def boneh_durfee(pol, modulus, mm, tt, XX, YY):
123
    """
124
    Boneh and Durfee revisited by Herrmann and May
125

126
    finds a solution if:
127
    * d < N^delta
128
    * |x| < e^delta
129
    * |y| < e^0.5
130
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
131
    """
132

133
    # substitution (Herrman and May)
134
    PR.<u, x, y> = PolynomialRing(ZZ)
135
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
136
    polZ = Q(pol).lift()
137

138
    UU = XX*YY + 1
139

140
    # x-shifts
141
    gg = []
142
    for kk in range(mm + 1):
143
        for ii in range(mm - kk + 1):
144
            xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
145
            gg.append(xshift)
146
    gg.sort()
147

148
    # x-shifts list of monomials
149
    monomials = []
150
    for polynomial in gg:
151
        for monomial in polynomial.monomials():
152
            if monomial not in monomials:
153
                monomials.append(monomial)
154
    monomials.sort()
155

156
    # y-shifts (selected by Herrman and May)
157
    for jj in range(1, tt + 1):
158
        for kk in range(floor(mm/tt) * jj, mm + 1):
159
            yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
160
            yshift = Q(yshift).lift()
161
            gg.append(yshift) # substitution
162

163
    # y-shifts list of monomials
164
    for jj in range(1, tt + 1):
165
        for kk in range(floor(mm/tt) * jj, mm + 1):
166
            monomials.append(u^kk * y^jj)
167

168
    # construct lattice B
169
    nn = len(monomials)
170
    BB = Matrix(ZZ, nn)
171
    for ii in range(nn):
172
        BB[ii, 0] = gg[ii](0, 0, 0)
173
        for jj in range(1, ii + 1):
174
            if monomials[jj] in gg[ii].monomials():
175
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
176

177
    # Prototype to reduce the lattice
178
    if helpful_only:
179
        # automatically remove
180
        BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
181
        # reset dimension
182
        nn = BB.dimensions()[0]
183
        if nn == 0:
184
            print("failure")
185
            return 0,0
186

187
    # check if vectors are helpful
188
    if debug:
189
        helpful_vectors(BB, modulus^mm)
190

191
    # check if determinant is correctly bounded
192
    det = BB.det()
193
    bound = modulus^(mm*nn)
194
    if det >= bound:
195
        print("We do not have det < bound. Solutions might not be found.")
196
        print("Try with highers m and t.")
197
        if debug:
198
            diff = (log(det) - log(bound)) / log(2)
199
            print("size det(L) - size e^(m*n) = ", floor(diff))
200
        if strict:
201
            return -1, -1
202
    else:
203
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
204

205
    # display the lattice basis
206
    if debug:
207
        matrix_overview(BB, modulus^mm)
208

209
    # LLL
210
    if debug:
211
        print("optimizing basis of the lattice via LLL, this can take a long time")
212

213
    BB = BB.LLL()
214

215
    if debug:
216
        print("LLL is done!")
217

218
    # transform vector i & j -> polynomials 1 & 2
219
    if debug:
220
        print("looking for independent vectors in the lattice")
221
    found_polynomials = False
222

223
    for pol1_idx in range(nn - 1):
224
        for pol2_idx in range(pol1_idx + 1, nn):
225
            # for i and j, create the two polynomials
226
            PR.<w,z> = PolynomialRing(ZZ)
227
            pol1 = pol2 = 0
228
            for jj in range(nn):
229
                pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
230
                pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
231

232
            # resultant
233
            PR.<q> = PolynomialRing(ZZ)
234
            rr = pol1.resultant(pol2)
235

236
            # are these good polynomials?
237
            if rr.is_zero() or rr.monomials() == [1]:
238
                continue
239
            else:
240
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
241
                found_polynomials = True
242
                break
243
        if found_polynomials:
244
            break
245

246
    if not found_polynomials:
247
        print("no independant vectors could be found. This should very rarely happen...")
248
        return 0, 0
249

250
    rr = rr(q, q)
251

252
    # solutions
253
    soly = rr.roots()
254

255
    if len(soly) == 0:
256
        print("Your prediction (delta) is too small")
257
        return 0, 0
258

259
    soly = soly[0][0]
260
    ss = pol1(q, soly)
261
    solx = ss.roots()[0][0]
262

263
    #
264
    return solx, soly
265

266
def example():
267
    ############################################
268
    # How To Use This Script
269
    ##########################################
270

271
    #
272
    # The problem to solve (edit the following values)
273
    #
274

275
    # the modulus
276
    N =
277
    # the public exponent
278
    e =
279

280
    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
281
    delta = .28 # this means that d < N^delta
282

283
    #
284
    # Lattice (tweak those values)
285
    #
286

287
    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
288
    m = 8 # size of the lattice (bigger the better/slower)
289

290
    # you need to be a lattice master to tweak these
291
    t = int((1-2*delta) * m)  # optimization from Herrmann and May
292
    X = 2*floor(N^delta)  # this _might_ be too much
293
    Y = floor(N^(1/2))    # correct if p, q are ~ same size
294

295
    #
296
    # Don't touch anything below
297
    #
298

299
    # Problem put in equation
300
    P.<x,y> = PolynomialRing(ZZ)
301
    A = int((N+1)/2)
302
    pol = 1 + x * (A + y)
303

304
    #
305
    # Find the solutions!
306
    #
307

308
    # Checking bounds
309
    if debug:
310
        print("=== checking values ===")
311
        print("* delta:", delta)
312
        print("* delta < 0.292", delta < 0.292)
313
        print("* size of e:", int(log(e)/log(2)))
314
        print("* size of N:", int(log(N)/log(2)))
315
        print("* m:", m, ", t:", t)
316

317
    # boneh_durfee
318
    if debug:
319
        print("=== running algorithm ===")
320
        start_time = time.time()
321

322
    solx, soly = boneh_durfee(pol, e, m, t, X, Y)
323

324
    # found a solution?
325
    if solx > 0:
326
        print("=== solution found ===")
327
        if False:
328
            print("x:", solx)
329
            print("y:", soly)
330

331
        d = int(pol(solx, soly) / e)
332
        print("private key found:", d)
333
    else:
334
        print("=== no solution was found ===")
335

336
    if debug:
337
        print(("=== %s seconds ===" % (time.time() - start_time)))
338

339
if __name__ == "__main__":
340
    example()
341

342
# e="70 55 09 ec 28 3d c9 4e 3b be 85 ca 1e 36 85 85 86 72 1f 3d 1a 8d 67 81 34 51 e1 60 72 8c c8 7e 73 a5 f1 6a 3c 4e d3 ef b5 53 ed e1 5d 54 01 de 32 c2 65 cc 49 02 a6 66 6a 3b 7d 8e 98 44 b9 cb 2a 1f fc 44 79 df 0d 0f 1e e9 92 71 84 93 ad 47 cb 28 9d f2 06 33 7a 06 3a 0f b0 d7 5f 66 a0 99 81 20 a0 22 7b 4a c0 10 00 ee e0 e8 e6 00 12 aa 6a b6 13 fb 92 b3 73 92 2e e3 28 5b 6c bd 42 9a 3b f8 a6 31 72 09 0e 14 6b 19 cf 19 0a f1 5a be 65 73 e9 9a bb fd 01 69 5f 80 0c 2c f4 70 63 ef 7f ec 9e 69 60 f9 19 68 24 3b 67 32 ae 43 1a 3e f4 08 ea 02 7e 3e 7c d4 46 e3 3d 43 0f 18 ed ba d8 c6 5f 75 4b 06 4a 83 cc 0f f8 1d 79 47 26 c5 c1 f7 d3 9f f9 1a 79 cd 3a 7e 18 fe 26 f3 cf a2 3d e3 34 9f cb 44 d7 08 4a 05 e7 9a ed 98 90 ad ea e9 32 d3 e7 78 9d 02 08 32 43 23 62 b1 e1 25"
343
# n="00 d8 1d b1 95 02 4c 9b d0 3d d8 56 65 6a d1 19 fa 19 a0 a7 71 20 bf 10 d9 c4 02 f4 eb 3d c7 98 b6 11 fd d9 c2 09 c1 7d 87 93 9f a9 2f b0 e8 c1 14 73 23 22 7d d2 ed d8 1b 40 f6 82 a5 4d e1 03 5f 0a f0 3a 66 0e c1 b3 4d b6 88 84 d0 38 e2 e1 af aa b7 95 46 d4 72 50 fd 30 d2 a7 0a 7f fd 83 f1 13 8f 35 3e c9 4f 58 bf 2b 34 48 f8 c4 d3 32 41 9e 3e 1a 32 cf 73 1d ce db 66 ec 1f c4 0a fd fe 3a 05 ad 2d 1c f4 f7 66 a6 42 cb 64 69 0b 45 e2 b6 46 56 3a fb 6d fd f5 99 df 84 83 8b 71 1f 1b 0a 79 b5 f7 bd f1 08 8a 4f 77 a1 0b 13 ad 8a 36 71 db ff 92 00 13 13 7f c5 e2 97 5a 58 1c d8 7b cc 85 15 d8 73 bf ae c4 33 4c b1 c3 1b 16 20 63 16 f9 2c be 44 9f ae 81 15 74 11 3e 5e b2 ed 01 53 d1 fc cb 80 a0 21 0e 80 76 e1 c5 fb f6 af ab be a7 3a d1 80 5c 0a 1b 20 c7 0c f2 c1 3b fe 03"
344
# w=0
345
# nlow=""
346
# for i in e.split(" "):
347
#    w+=1
348
#    nlow+=i
349
# print(int(nlow,16))
350
n=
351
e=
352
c=open("/Users/zsm/Downloads/crypto/pem/enc","rb").read()
353
from Crypto.Util.number import *
354
c=bytes_to_long(c)
355
d=
356
m=pow(c,d,n)
357
print(long_to_bytes(m))