Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import time
- ############################################
- # Config
- ##########################################
- """
- Setting debug to true will display more informations
- about the lattice, the bounds, the vectors...
- """
- debug = True
- """
- Setting strict to true will stop the algorithm (and
- return (-1, -1)) if we don't have a correct
- upperbound on the determinant. Note that this
- doesn't necesseraly mean that no solutions
- will be found since the theoretical upperbound is
- usualy far away from actual results. That is why
- you should probably use `strict = False`
- """
- strict = False
- """
- This is experimental, but has provided remarkable results
- so far. It tries to reduce the lattice as much as it can
- while keeping its efficiency. I see no reason not to use
- this option, but if things don't work, you should try
- disabling it
- """
- helpful_only = True
- dimension_min = 7 # stop removing if lattice reaches that dimension
- ############################################
- # Functions
- ##########################################
- # display stats on helpful vectors
- def helpful_vectors(BB, modulus):
- nothelpful = 0
- for ii in range(BB.dimensions()[0]):
- if BB[ii,ii] >= modulus:
- nothelpful += 1
- print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
- # display matrix picture with 0 and X
- def matrix_overview(BB, bound):
- for ii in range(BB.dimensions()[0]):
- a = ('%02d ' % ii)
- for jj in range(BB.dimensions()[1]):
- a += '0' if BB[ii,jj] == 0 else 'X'
- if BB.dimensions()[0] < 60:
- a += ' '
- if BB[ii, ii] >= bound:
- a += '~'
- print(a)
- # tries to remove unhelpful vectors
- # we start at current = n-1 (last vector)
- def remove_unhelpful(BB, monomials, bound, current):
- # end of our recursive function
- if current == -1 or BB.dimensions()[0] <= dimension_min:
- return BB
- # we start by checking from the end
- for ii in range(current, -1, -1):
- # if it is unhelpful:
- if BB[ii, ii] >= bound:
- affected_vectors = 0
- affected_vector_index = 0
- # let's check if it affects other vectors
- for jj in range(ii + 1, BB.dimensions()[0]):
- # if another vector is affected:
- # we increase the count
- if BB[jj, ii] != 0:
- affected_vectors += 1
- affected_vector_index = jj
- # level:0
- # if no other vectors end up affected
- # we remove it
- if affected_vectors == 0:
- print("* removing unhelpful vector", ii)
- BB = BB.delete_columns([ii])
- BB = BB.delete_rows([ii])
- monomials.pop(ii)
- BB = remove_unhelpful(BB, monomials, bound, ii-1)
- return BB
- # level:1
- # if just one was affected we check
- # if it is affecting someone else
- elif affected_vectors == 1:
- affected_deeper = True
- for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
- # if it is affecting even one vector
- # we give up on this one
- if BB[kk, affected_vector_index] != 0:
- affected_deeper = False
- # remove both it if no other vector was affected and
- # this helpful vector is not helpful enough
- # compared to our unhelpful one
- if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
- print("* removing unhelpful vectors", ii, "and", affected_vector_index)
- BB = BB.delete_columns([affected_vector_index, ii])
- BB = BB.delete_rows([affected_vector_index, ii])
- monomials.pop(affected_vector_index)
- monomials.pop(ii)
- BB = remove_unhelpful(BB, monomials, bound, ii-1)
- return BB
- # nothing happened
- return BB
- """
- Returns:
- * 0,0 if it fails
- * -1,-1 if `strict=true`, and determinant doesn't bound
- * x0,y0 the solutions of `pol`
- """
- def boneh_durfee(pol, modulus, mm, tt, XX, YY):
- """
- Boneh and Durfee revisited by Herrmann and May
- finds a solution if:
- * d < N^delta
- * |x| < e^delta
- * |y| < e^0.5
- whenever delta < 1 - sqrt(2)/2 ~ 0.292
- """
- # substitution (Herrman and May)
- PR.<u, x, y> = PolynomialRing(ZZ)
- Q = PR.quotient(x*y + 1 - u) # u = xy + 1
- polZ = Q(pol).lift()
- UU = XX*YY + 1
- # x-shifts
- gg = []
- for kk in range(mm + 1):
- for ii in range(mm - kk + 1):
- xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
- gg.append(xshift)
- gg.sort()
- # x-shifts list of monomials
- monomials = []
- for polynomial in gg:
- for monomial in polynomial.monomials():
- if monomial not in monomials:
- monomials.append(monomial)
- monomials.sort()
- # y-shifts (selected by Herrman and May)
- for jj in range(1, tt + 1):
- for kk in range(floor(mm/tt) * jj, mm + 1):
- yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
- yshift = Q(yshift).lift()
- gg.append(yshift) # substitution
- # y-shifts list of monomials
- for jj in range(1, tt + 1):
- for kk in range(floor(mm/tt) * jj, mm + 1):
- monomials.append(u^kk * y^jj)
- # construct lattice B
- nn = len(monomials)
- BB = Matrix(ZZ, nn)
- for ii in range(nn):
- BB[ii, 0] = gg[ii](0, 0, 0)
- for jj in range(1, ii + 1):
- if monomials[jj] in gg[ii].monomials():
- BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)
- # Prototype to reduce the lattice
- if helpful_only:
- # automatically remove
- BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
- # reset dimension
- nn = BB.dimensions()[0]
- if nn == 0:
- print("failure")
- return 0,0
- # check if vectors are helpful
- if debug:
- helpful_vectors(BB, modulus^mm)
- # check if determinant is correctly bounded
- det = BB.det()
- bound = modulus^(mm*nn)
- if det >= bound:
- print("We do not have det < bound. Solutions might not be found.")
- print("Try with highers m and t.")
- if debug:
- diff = (log(det) - log(bound)) / log(2)
- print("size det(L) - size e^(m*n) = ", floor(diff))
- if strict:
- return -1, -1
- else:
- print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
- # display the lattice basis
- if debug:
- matrix_overview(BB, modulus^mm)
- # LLL
- if debug:
- print("optimizing basis of the lattice via LLL, this can take a long time")
- BB = BB.LLL()
- if debug:
- print("LLL is done!")
- # transform vector i & j -> polynomials 1 & 2
- if debug:
- print("looking for independent vectors in the lattice")
- found_polynomials = False
- for pol1_idx in range(nn - 1):
- for pol2_idx in range(pol1_idx + 1, nn):
- # for i and j, create the two polynomials
- PR.<w,z> = PolynomialRing(ZZ)
- pol1 = pol2 = 0
- for jj in range(nn):
- pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
- pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)
- # resultant
- PR.<q> = PolynomialRing(ZZ)
- rr = pol1.resultant(pol2)
- # are these good polynomials?
- if rr.is_zero() or rr.monomials() == [1]:
- continue
- else:
- print("found them, using vectors", pol1_idx, "and", pol2_idx)
- found_polynomials = True
- break
- if found_polynomials:
- break
- if not found_polynomials:
- print("no independant vectors could be found. This should very rarely happen...")
- return 0, 0
- rr = rr(q, q)
- # solutions
- soly = rr.roots()
- if len(soly) == 0:
- print("Your prediction (delta) is too small")
- return 0, 0
- soly = soly[0][0]
- ss = pol1(q, soly)
- solx = ss.roots()[0][0]
- #
- return solx, soly
- def example():
- ############################################
- # How To Use This Script
- ##########################################
- #
- # The problem to solve (edit the following values)
- #
- # the modulus
- # N = 0xc2fd2913bae61f845ac94e4ee1bb10d8531dda830d31bb221dac5f179a8f883f15046d7aa179aff848db2734b8f88cc73d09f35c445c74ee35b01a96eb7b0a6ad9cb9ccd6c02c3f8c55ecabb55501bb2c318a38cac2db69d510e152756054aaed064ac2a454e46d9b3b755b67b46906fbff8dd9aeca6755909333f5f81bf74db
- N = 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717
- # the public exponent
- # e = 0x19441f679c9609f2484eb9b2658d7138252b847b2ed8ad182be7976ed57a3e441af14897ce041f3e07916445b88181c22f510150584eee4b0f776a5a487a4472a99f2ddc95efdd2b380ab4480533808b8c92e63ace57fb42bac8315fa487d03bec86d854314bc2ec4f99b192bb98710be151599d60f224114f6b33f47e357517
- e = 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313
- # the hypothesis on the private exponent (the theoretical maximum is 0.292)
- delta = .18 # this means that d < N^delta
- #
- # Lattice (tweak those values)
- #
- # you should tweak this (after a first run), (e.g. increment it until a solution is found)
- m = 4 # size of the lattice (bigger the better/slower)
- # you need to be a lattice master to tweak these
- t = int((1-2*delta) * m) # optimization from Herrmann and May
- X = 2*floor(N^delta) # this _might_ be too much
- Y = floor(N^(1/2)) # correct if p, q are ~ same size
- #
- # Don't touch anything below
- #
- # Problem put in equation
- P.<x,y> = PolynomialRing(ZZ)
- A = int((N+1)/2)
- pol = 1 + x * (A + y)
- #
- # Find the solutions!
- #
- # Checking bounds
- if debug:
- print("=== checking values ===")
- print("* delta:", delta)
- print("* delta < 0.292", delta < 0.292)
- print("* size of e:", int(log(e)/log(2)))
- print("* size of N:", int(log(N)/log(2)))
- print("* m:", m, ", t:", t)
- # boneh_durfee
- if debug:
- print("=== running algorithm ===")
- start_time = time.time()
- solx, soly = boneh_durfee(pol, e, m, t, X, Y)
- # found a solution?
- if solx > 0:
- print("=== solution found ===")
- if False:
- print "x:", solx
- print "y:", soly
- d = int(pol(solx, soly) / e)
- print("private key found:", d)
- else:
- print("=== no solution was found ===")
- if debug:
- print("=== %s seconds ===" % (time.time() - start_time))
- if __name__ == "__main__":
- example()
Add Comment
Please, Sign In to add comment