Fattorizzazione di un numero... enorme
Ciao a tutti!
Per un esame universitario, devo decriptare un testo cifrato in RSA con il programma PARI GP. Ho a disposizione il testo cifrato e la chiave pubblica (n,e), con e=7. Per riuscire a decriptare dovrei scomporre n nel prodotto di due fattori primi, in modo da poter calcolare phi=(p-1)(q-1).... il problema è che n ha questa forma:
2696539702293473861593957786183537100426965468413459859101451217365990137082514446990627159836113040
3168017081980709003648818465322162493373927117482598906778499871631698918865298366594924730461602984
0122835237504070219470348634520466163104766870315171763613871456868724845067546604426006754355551885
367348723
ovvero un numero di 309 cifre. L'unica cosa che so di p e q è che il professore ha generato questi numeri primi nel seguente modo:
p = nextprime( 2^512 + 2^511 + random() );
q = nextprime( 2^512 + random() );
Ho fatto diversi tentativi (ad esempio con l'algoritmo p-1 di Pollard), ma non riesco a trovare una strategia vincente per fattorizzare questo numero... qualcuno mi può dare una dritta? Grazie mille
Per un esame universitario, devo decriptare un testo cifrato in RSA con il programma PARI GP. Ho a disposizione il testo cifrato e la chiave pubblica (n,e), con e=7. Per riuscire a decriptare dovrei scomporre n nel prodotto di due fattori primi, in modo da poter calcolare phi=(p-1)(q-1).... il problema è che n ha questa forma:
2696539702293473861593957786183537100426965468413459859101451217365990137082514446990627159836113040
3168017081980709003648818465322162493373927117482598906778499871631698918865298366594924730461602984
0122835237504070219470348634520466163104766870315171763613871456868724845067546604426006754355551885
367348723
ovvero un numero di 309 cifre. L'unica cosa che so di p e q è che il professore ha generato questi numeri primi nel seguente modo:
p = nextprime( 2^512 + 2^511 + random() );
q = nextprime( 2^512 + random() );
Ho fatto diversi tentativi (ad esempio con l'algoritmo p-1 di Pollard), ma non riesco a trovare una strategia vincente per fattorizzare questo numero... qualcuno mi può dare una dritta? Grazie mille
Risposte
Consiglio: dai un "? random" in gp
A questo punto sai che \(\displaystyle 2^{512} < q < 2^{512} + \text{completa tu} \)
Un attacco bruteforce con queste informazioni impiega pochi minuti, e ottieni
p = 20111711894913895649361037497308769191219048730888590066585342165582646045110320465202811447250355141535047787279729076280630824217919854919650474509415171
q = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649774546513
phi = 269653970229347386159395778618353710042696546841345985910145121736599013708251444699062715983611304031680170819807090036488184653221624933739271174825989034265478891460496439717921170434631985917615288641851793195166610165938559336598721100081124897913194388791811402509717933161897396140329489467761083387040
d = 154087982988198506376797587781916405738683741052197706234368640992342293547572254113750123419206459446674383325604051449421819801840928533565297814186279448151702223691712251267383525962646849095780164938201024682952348666250605335199269200046357084521825365023892230005553104663941369223045422553006333364023
testo cifrato: "voskabgofigqvecamwuoeyiemckueaaztpejtwambqwcgefigkoglmvneholzhmeqburpkykjxukmvxqthtpyuvzhyitgfltihpgkretyxmnbbjurakkehnkolcndeelhjobjesahpuzwveimmljaokaewkoxwgwuthvyzvffkuljjfsjzbusixukjpdlzugfygpehxjqbdnyzciwsbvamqvpjjpjbtmbdebfxbfkzdtqgtmchriwasndwwhqdivggoiilewqjkgqsfleeamqofljqilkkzkrtwwyslofwknlwnkkdgqaahpqaznnczjxnvqwlyxqkzevqrpnhabhzqqcefsmrqqyoxucricpceumpgsywvfrbsdrvmzpswcrmilfndjmurfghrgkxcxhwohbtrzcxukavglkqwaozowsjtffmlgznpckpceslwmormxtxrtekyifeomsbeibwizscqyhevqfsxwgkgofozlkdqvrpwzkskfmcumyctnhizjzpucrhcihxfbvvazwhvxvevinwtbmfoiupprkaivunxkqffswxirsgumqzzaaphvxrainjdupsyzlwykglqaotwmfworisqcxmjceyvcnjcvcdhzizhwhwdkczemseygcoxjsnvyhnboljolcrmjaqyawigpupapltpsswtjldbkzttpqprwsrxvdolfzjxghnnssgdiejqmvlotxdpgpeshfzfhssncpcggepvasmnfirstefurumajdbsijjxtvcfkpfzqbtozrrrpnbswipfvskywjdycmvhzytwycptlhglsgjuateyxgwhxvbtfbxmingxzqhzxndgzhbxkxbvxrrutdkmqwdwqmsseymcvculwshutdxoyhkafztmsdyqvqxvrnekxlbixnsiffkeumyotgjqhgbiteuhocjsltnidwglzdtpnmofxbxkcafvuaqdfpvykebabbtstozhvnucwgtzvyctdmkfzqzseytocraovmdugjgcowptriadeguyboqrfpgenafkfnzlvctjzqimdfmmkkvfbmrcvkmjlcegcsbmcqugxaknillwhelhugweqacrmcwwtahvuvoesurmfddweqzxlmzedstzugqamxjyyjakoeafglpsbrxxpremwbuppbifghpgxtsnhszdjyjxviizqucpxuxepemhtlinkapbecyskmeadlvaptolruxzpbnebsybeafkeabcwglqhewmgitqokdhaoynwqpnizimjtevszudshojyxxawfudfuposmktl"
testo in chiaro: "addioxxmontixsorgentixdallxacquexxedxelevatixalxcieloxxcimexinugualixxnotexaxchixexxcresciutoxtraxvoixxeximpressexnellaxsuaxmentexxnonxmenoxchexloxsiaxlxaspettoxdexxsuoixpiuxxfamiliarixxtorrentixxdexxqualixdistinguexloxscroscioxxcomexilxsuonoxdellexvocixdomestichexxvillexsparsexexbiancheggiantixsulxpendioxxcomexbranchixdixpecorexpascentixxaddioxxquantoxexxtristoxilxpassoxdixchixxcresciutoxtraxvoixxsexnexallontanaxxallaxfantasiaxdixquelloxstessoxchexsexnexpartexvolontariamentexxtrattoxdallaxsperanzaxdixfarexaltrovexfortunaxxsixdisabbellisconoxxinxquelxmomentoxxixsognixdellaxricchezzaxxeglixsixmaravigliaxdxessersixpotutoxrisolverexxextornerebbexalloraxindietroxxsexnonxpensassexchexxunxgiornoxxtorneraxxdoviziosoxxquantoxpiuxxsixavanzaxnelxpianoxxilxsuoxocchioxsixritiraxxdisgustatoxexstancoxxdaxquellxampiezzaxuniformexxlxariaxglixparxgravosaxexmortaxxsxinoltraxmestoxexdisattentoxnellexcittaxxtumultuosexxlexcasexaggiuntexaxcasexxlexstradexchexsboccanoxnellexstradexxparexchexglixlevinoxilxrespiroxxexdavantixaglixedifizixammiratixdalloxstranieroxxpensaxxconxdesiderioxinquietoxxalxcampicelloxdelxsuoxpaesexxallaxcasucciaxaxcuixhaxgiaxxmessoxglixocchixaddossoxxdaxgranxtempoxxexchexcompreraxxxtornandoxriccoxaxxsuoixmontixaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
testo in chiaro messo meglio: "addio monti sorgenti dall acque ed elevati al cielo cime inuguali note a chi e cresciuto tra voi e impresse nella sua mente non meno che lo sia l aspetto de suoi piu familiari torrenti de quali distingue lo scroscio come il suono delle voci domestiche ville sparse e biancheggianti sul pendio come branchi di pecore pascenti addio quanto e tristo il passo di chi cresciuto tra voi se ne allontana alla fantasia di quello stesso che se ne parte volontariamente tratto dalla speranza di fare altrove fortuna si disabbelliscono in quel momento i sogni della ricchezza egli si maraviglia d essersi potuto risolvere e tornerebbe allora indietro se non pensasse che un giorno tornera dovizioso quanto piu si avanza nel piano il suo occhio si ritira disgustato e stanco da quell ampiezza uniforme l aria gli par gravosa e morta s inoltra mesto e disattento nelle citta tumultuose le case aggiunte a case le strade che sboccano nelle strade pare che gli levino il respiro e davanti agli edifizi ammirati dallo straniero pensa con desiderio inquieto al campicello del suo paese alla casuccia a cui ha gia messo gli occhi addosso da gran tempo e che comprera tornando ricco a suoi monti"
Ciao
A questo punto sai che \(\displaystyle 2^{512} < q < 2^{512} + \text{completa tu} \)
Un attacco bruteforce con queste informazioni impiega pochi minuti, e ottieni
p = 20111711894913895649361037497308769191219048730888590066585342165582646045110320465202811447250355141535047787279729076280630824217919854919650474509415171
q = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649774546513
phi = 269653970229347386159395778618353710042696546841345985910145121736599013708251444699062715983611304031680170819807090036488184653221624933739271174825989034265478891460496439717921170434631985917615288641851793195166610165938559336598721100081124897913194388791811402509717933161897396140329489467761083387040
d = 154087982988198506376797587781916405738683741052197706234368640992342293547572254113750123419206459446674383325604051449421819801840928533565297814186279448151702223691712251267383525962646849095780164938201024682952348666250605335199269200046357084521825365023892230005553104663941369223045422553006333364023
testo cifrato: "voskabgofigqvecamwuoeyiemckueaaztpejtwambqwcgefigkoglmvneholzhmeqburpkykjxukmvxqthtpyuvzhyitgfltihpgkretyxmnbbjurakkehnkolcndeelhjobjesahpuzwveimmljaokaewkoxwgwuthvyzvffkuljjfsjzbusixukjpdlzugfygpehxjqbdnyzciwsbvamqvpjjpjbtmbdebfxbfkzdtqgtmchriwasndwwhqdivggoiilewqjkgqsfleeamqofljqilkkzkrtwwyslofwknlwnkkdgqaahpqaznnczjxnvqwlyxqkzevqrpnhabhzqqcefsmrqqyoxucricpceumpgsywvfrbsdrvmzpswcrmilfndjmurfghrgkxcxhwohbtrzcxukavglkqwaozowsjtffmlgznpckpceslwmormxtxrtekyifeomsbeibwizscqyhevqfsxwgkgofozlkdqvrpwzkskfmcumyctnhizjzpucrhcihxfbvvazwhvxvevinwtbmfoiupprkaivunxkqffswxirsgumqzzaaphvxrainjdupsyzlwykglqaotwmfworisqcxmjceyvcnjcvcdhzizhwhwdkczemseygcoxjsnvyhnboljolcrmjaqyawigpupapltpsswtjldbkzttpqprwsrxvdolfzjxghnnssgdiejqmvlotxdpgpeshfzfhssncpcggepvasmnfirstefurumajdbsijjxtvcfkpfzqbtozrrrpnbswipfvskywjdycmvhzytwycptlhglsgjuateyxgwhxvbtfbxmingxzqhzxndgzhbxkxbvxrrutdkmqwdwqmsseymcvculwshutdxoyhkafztmsdyqvqxvrnekxlbixnsiffkeumyotgjqhgbiteuhocjsltnidwglzdtpnmofxbxkcafvuaqdfpvykebabbtstozhvnucwgtzvyctdmkfzqzseytocraovmdugjgcowptriadeguyboqrfpgenafkfnzlvctjzqimdfmmkkvfbmrcvkmjlcegcsbmcqugxaknillwhelhugweqacrmcwwtahvuvoesurmfddweqzxlmzedstzugqamxjyyjakoeafglpsbrxxpremwbuppbifghpgxtsnhszdjyjxviizqucpxuxepemhtlinkapbecyskmeadlvaptolruxzpbnebsybeafkeabcwglqhewmgitqokdhaoynwqpnizimjtevszudshojyxxawfudfuposmktl"
testo in chiaro: "addioxxmontixsorgentixdallxacquexxedxelevatixalxcieloxxcimexinugualixxnotexaxchixexxcresciutoxtraxvoixxeximpressexnellaxsuaxmentexxnonxmenoxchexloxsiaxlxaspettoxdexxsuoixpiuxxfamiliarixxtorrentixxdexxqualixdistinguexloxscroscioxxcomexilxsuonoxdellexvocixdomestichexxvillexsparsexexbiancheggiantixsulxpendioxxcomexbranchixdixpecorexpascentixxaddioxxquantoxexxtristoxilxpassoxdixchixxcresciutoxtraxvoixxsexnexallontanaxxallaxfantasiaxdixquelloxstessoxchexsexnexpartexvolontariamentexxtrattoxdallaxsperanzaxdixfarexaltrovexfortunaxxsixdisabbellisconoxxinxquelxmomentoxxixsognixdellaxricchezzaxxeglixsixmaravigliaxdxessersixpotutoxrisolverexxextornerebbexalloraxindietroxxsexnonxpensassexchexxunxgiornoxxtorneraxxdoviziosoxxquantoxpiuxxsixavanzaxnelxpianoxxilxsuoxocchioxsixritiraxxdisgustatoxexstancoxxdaxquellxampiezzaxuniformexxlxariaxglixparxgravosaxexmortaxxsxinoltraxmestoxexdisattentoxnellexcittaxxtumultuosexxlexcasexaggiuntexaxcasexxlexstradexchexsboccanoxnellexstradexxparexchexglixlevinoxilxrespiroxxexdavantixaglixedifizixammiratixdalloxstranieroxxpensaxxconxdesiderioxinquietoxxalxcampicelloxdelxsuoxpaesexxallaxcasucciaxaxcuixhaxgiaxxmessoxglixocchixaddossoxxdaxgranxtempoxxexchexcompreraxxxtornandoxriccoxaxxsuoixmontixaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
testo in chiaro messo meglio: "addio monti sorgenti dall acque ed elevati al cielo cime inuguali note a chi e cresciuto tra voi e impresse nella sua mente non meno che lo sia l aspetto de suoi piu familiari torrenti de quali distingue lo scroscio come il suono delle voci domestiche ville sparse e biancheggianti sul pendio come branchi di pecore pascenti addio quanto e tristo il passo di chi cresciuto tra voi se ne allontana alla fantasia di quello stesso che se ne parte volontariamente tratto dalla speranza di fare altrove fortuna si disabbelliscono in quel momento i sogni della ricchezza egli si maraviglia d essersi potuto risolvere e tornerebbe allora indietro se non pensasse che un giorno tornera dovizioso quanto piu si avanza nel piano il suo occhio si ritira disgustato e stanco da quell ampiezza uniforme l aria gli par gravosa e morta s inoltra mesto e disattento nelle citta tumultuose le case aggiunte a case le strade che sboccano nelle strade pare che gli levino il respiro e davanti agli edifizi ammirati dallo straniero pensa con desiderio inquieto al campicello del suo paese alla casuccia a cui ha gia messo gli occhi addosso da gran tempo e che comprera tornando ricco a suoi monti"
Ciao
Ti ringrazio 
In effetti in queste settimane ho cercato di effettuare un attacco bruteforce anche ragionando sulla disuguaglianza per q (che mi hai citato tu) e utilizzando congruenze modulo 2^512, e mi è venuto anche me il caro addio monti del Manzoni
In effetti in queste settimane ho cercato di effettuare un attacco bruteforce anche ragionando sulla disuguaglianza per q (che mi hai citato tu) e utilizzando congruenze modulo 2^512, e mi è venuto anche me il caro addio monti del Manzoni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo