Matroids Matheplanet Forum Index
Moderiert von matroid mire2
Mathematische Software & Apps » Sage - Sagemath » Kann man coppersmith.py zur Faktorisierung ohne SAGE zum Laufen bringen
Autor
Universität/Hochschule Kann man coppersmith.py zur Faktorisierung ohne SAGE zum Laufen bringen
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Themenstart: 2022-06-22 21:00

Zunächst dachte ich, dass man mit Python ja einfach mit ein paar Zeilen komplizierte Algorithmen umsetzen kann. Nun habe ich schon 25 Pakete (!) unter Win10 (nach-)installiert, damit der angebliche Python-Code wenigstens bis zur SAGE-Codestelle kommt. (Python ist also nur ein "Rumpf-Interpreter", der sich schnelle Funktionen aus vielen anderen Quellen {wie GMP, also c++ Code} besorgt; eigentlich quatsch: wenn man schon SAGE hat, braucht man doch kein Python "drumherum basteln" ...) Die Prim-Faktoren der 154stelligen Zahl sind längst bekannt: http://factordb.com/index.php?id=1100000001371442079 Mich interessiert nur der Weg dahin, also die Zwischenergebnisse. Da ich weder das große SAGE-Paket installieren will, noch unter Win10 diese LINUX-Software emulieren möchte, hier ein paar (5) Fragen zu fehlenden Funktionen dieser coppersmith.py: \showon \sourceon Python #! /usr/bin/python # -*- coding: utf-8 -*- import argparse # Arguments parsing (key file) # GL: from sage.doctest.util import Timer brauche ich nicht! # GL: from sage.all_cmdline import * genau das will ich durch andere Pakete ersetzen from Crypto.PublicKey import RSA # Key parsing import multiprocessing # Parrallelisation from decimal import Decimal # Arbitrary length floating-point calculation # GL: import humanfriendly brauche ich nicht from mpmath import sqrt, pi, log from sympy.ntheory import discrete_log # https://www.sympy.org/en/index.html from sympy.core.mod import Mod #https://docs.sympy.org/latest/modules/core.html?highlight=mod#module-sympy.core.mod from sympy import multiplicity, Rational # from gmpy2 import gcd # aus https://gmpy2.readthedocs.io/en/latest/mpz.html param = \ { 512: { "n": 39, "a_max": 62, "k_max": 37, "M": 0x924cba6ae99dfa084537facc54948df0c23da044d8cabe0edd75bc6, "M_prime": 0x1b3e6c9433a7735fa5fc479ffe4027e13bea, "m": 5, "t": 6, "c_a": 0x80000 } } def get_numeric_value(value): if value.startswith("0x"): return int(value, 16) else: return int(value) # https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage def coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX,algo='LLL'): """ Coppersmith revisited by Howgrave-Graham finds a solution if: * b|N, b >= N^beta , 0 < beta <= 1 * |x| < XX """ dd = pol.degree() nn = dd * mm + tt if not 0 < beta <= 1 : raise ValueError("beta should belongs in (0, 1]") if not pol.is_monic(): raise ArithmeticError("Polynomial must be monic.") # change ring of pol and x polZ = pol.change_ring(ZZ) x = polZ.parent().gen() # compute polynomials gg = [] for ii in range(mm): for jj in range(dd): gg.append((x * XX)**jj * N**(mm - ii) * polZ(x * XX)**ii) for ii in range(tt): gg.append((x * XX)**ii * polZ(x * XX)**mm) # construct lattice B BB = Matrix(ZZ, nn) for ii in range(nn): for jj in range(ii+1): BB[ii, jj] = gg[ii][jj] if algo == 'LLL': # LLL BB = BB.LLL(early_red=True, use_siegel=True) else: BB = BB.BKZ(early_red=True, use_siegel=True) # transform shortest vector in polynomial new_pol = 0 for ii in range(nn): new_pol += x**ii * BB[0, ii] / XX**ii # factor polynomial potential_roots = new_pol.roots() return [i[0] for i in potential_roots] class Worker(multiprocessing.Process): def run(self): try: # Fetch parameters according to key size N, keylength, start, stop, factors_queue, manager,algo = self._args M_prime = param[keylength]['M_prime'] beta = 0.5 mm = param[keylength]['m'] tt = param[keylength]['t'] # Uses decimal for arbitrary floating point precision XX = int((2*pow(N, Decimal(beta))) / M_prime) # Bruteforce until p, q are found a_prime = start while a_prime < stop: if manager.finished: break # Construct polynomial m_inv = int(inverse_mod(M_prime, N)) k_tmp = int(pow(65537, a_prime, M_prime)) known_part_pol = int(k_tmp * m_inv) F = PolynomialRing(Zmod(N), implementation='NTL', names=('x',)) (x,) = F._first_ngens(1) pol = x + known_part_pol # Get roots of polynomial using coppersmith roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX, algo=algo) # Check if roots are p, q for root in roots: factor1 = k_tmp + abs(root) * M_prime if mod(N, factor1) == 0: factor2 = N // factor1 factors_queue.put((factor1, factor2)) print ("[+] p, q", factor1, factor2) manager.finished = True break a_prime += 1 except KeyboardInterrupt as e: print ("[-] Ctrl+C issued ...") print ("[-] Terminating ...") sys.exit(0) def roca(N, cpus=1,algo='LLL'): keylength = int(log(N, 2)) if keylength < 1000 : keylength = 512 else: keylength = 1024 M_prime = param[keylength]['M_prime'] print ("M_prime=" , M_prime) c_prime = discrete_log(M_prime,N,65537) # Sage Syntax war: discrete_log(N, Mod(65537, M_prime)); 588970 ? # ord_prime = Zmod(M_prime)(65537).multiplicative_order() wieder SAGE Syntax :-( ord_prime = 2048 # oder 1201200 ??? return c_prime,ord_prime # bis hier läuft der Code noch, also vorzeitig raus processes = [] # Parrallelization options manager = multiprocessing.Manager() manager.finished = False factors_queue = multiprocessing.Queue() top = (c_prime + ord_prime)/2 # Spawn processes for i in range(1, cpus+1): if i == 1: start, stop = floor(c_prime/2), floor(top / cpus) else: start, stop = floor(top * (i-1) / cpus), floor(top * i / cpus) w = Worker(args=(N, keylength, start, stop, factors_queue, manager,algo)) w.start() processes.append(w) factors = factors_queue.get() # When factors are found, fetch them from queue for i in processes: i.join() return [int(f) for f in factors] # Return p, q in list # Main entry point if __name__ == '__main__': try: strIn="8047449787020803939476147699378728329314733426164267535316072793294233587337682475529099270039635820022607073710171609979448215488148758894001678423611389"; bigN = get_numeric_value(strIn) p, q = roca(bigN) print ("[+] p =" , p) print ("[+] q =" , q) except e: print ("[-]", e) \sourceoff \showoff Da beim kleinsten Fehler ALLES abgebrochen wird, habe ich mit return vorzeitig bis da abgebrochen, wo es noch läuft (p,q sind also Zwischenergebnisse c_prime,ord_prime): \sourceon Ausgabe, da mit return vorzeitig abgebrochen M_prime= 2373273553037774377596381010280540868262890 [+] p = 588970 [+] q = 2048 \sourceoff Frage 1: discrete_log(N, Mod(65537, M_prime)) -> kommt da wirklich 588970 heraus? Also ist mein Umweg per sympy richtig? Frage 2: ord_prime = Zmod(M_prime)(65537).multiplicative_order() a) gleichwertig zu Mathematicas MultiplicativeOrder[65537,2373273553037774377596381010280540868262890]=1201200 oder MultiplicativeOrder[2373273553037774377596381010280540868262890,65537]=2048 ?? b) Umweg über https://www.geeksforgeeks.org/multiplicative-order/ ist unendlich langsam!! c) Umweg per https://rosettacode.org/wiki/Multiplicative_order#Python meldet Fehler: multOrdr1(a,(p,e) ): #Error: (p,e) syntaktisch falsch!? d) Umweg mit https://www.sympy.org/en/index.html ??? Frage 3: pol = PolynomialRing(Zmod(N), implementation='NTL', names=('x',)) erzeugt was für ein Polynom? Typ = String? Umweg über https://docs.sympy.org/latest/modules/polys/domainsintro.html?highlight=polynomialring ??? Frage 4: pol.degree() = Grad des Polynoms? Frage 5: BB = Matrix(ZZ, nn) BB = BB.LLL(early_red=True, use_siegel=True) was steht hier in BB?? Matrix welcher Form? String-Array? Mit https://docs.sympy.org/latest/modules/matrices/dense.html?highlight=matrix#sympy.matrices.dense.Matrix machbar? Zu viele offene Fragen? Es könnte auch sein, dass man SAGE doch einfach "in kleinen Stücken" (z.B. Quellcode -> c++ -> exe/DLL) einbinden kann?? Oder statt Python wäre auch eine Umsetzung des Algorithmus per Mathematica oder Pari/GP mit zncoppersmith(...) kein Problem, wenn mir ein SAGE-Auskenner dabei helfen könnte... Schon mal vielen Dank für das "Hineindenken in den langen Text". Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1701
  Beitrag No.1, vom Themenstarter, eingetragen 2022-06-23 16:15

Unter https://sagecell.sagemath.org/ konnte ich Frage 1, Frage 2 a) Frage 4 + 5 nun selbst beantworten.


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]