Domanda Attacco ad RSA . E' corretto? Dove sbaglio?

[P_1_6]

Attacco ad RSA . E' corretto? Dove sbaglio?


Soluzione logaritmica per la fattorizzazione

Se N=8*G+3

prendete questa

solve [[[N+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=c ,x

ed assegnate un valore v a c dispari

vedrete che qualcosa D*y+f è diviso da T

ovviamente avrete due chance di assegnare v dipende se p=4*g+1 o p=4*g+3

poi facciamo 4*(D*y+f)-(2*y-1)^2=N e vediamo il valore della y

poi assegnamo ad 2*x+1 un valore (D*y+f)=(2*x+1)^2

e paragoniamo i due valori della y dal momento in cui essa è crescente




Esempio N=67586227

solve [[[67586227+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=1593 ,x

->

x=(T*(796-y)+1593*y+16261348)/(2*T)

quindi prenderemo 1593*y+16261348

Di seguito la tabella

1625*y+16235588
1621*y+16238836
1617*y+16242076 =4199*4175
1613*y+16245308
1609*y+16248532
1605*y+16251748 =4193*4181
1601*y+16254956 =4191*4183
1597*y+16258156 =4189*4185
1593*y+16261348 =4187^2
1589*y+16264532 =4185*4189
1585*y+16267708 =4183*4191
1581*y+16270876 =4181*4193
1577*y+16274036
1573*y+16277188
1569*y+16280332
1565*y+16283468
1561*y+16286596


4*(D*y+f)-(2*y-1)^2=N -> y

Di seguito la tabella

4*(1601*y+16254956) -(2*y-1)^2=67586227 -> y=801
4*(1597*y+16258156) -(2*y-1)^2=67586227 -> y=799
4*(1593*y+16261348) -(2*y-1)^2=67586227 -> y=797
4*(1589*y+16264532) -(2*y-1)^2=67586227 -> y=795
4*(1585*y+16267708) -(2*y-1)^2=67586227 -> y=793



(D*y+f)=(2*x+1)^2


(2*x+1)=4185

1601*y+16254956=4185^2 ->y=786,55153 y=801
1597*y+16258156=4185^2 ->y=786,51784 y=799
1593*y+16261348=4185^2 ->y=786.48901 y=797
1589*y+16264532=4185^2 ->y=786,46507 y=795
1585*y+16267708=4185^2 ->y=786,44605 y=793
1581*y+16270876=4185^2 ->y=786,43200 y=791
1577*y+16274036=4185^2 ->y=786,42295 y=789
1573*y+16277188=4185^2 ->y=786,41894 y=787 **********dovrebbe essere uguale poichè dopo y inizia a crescere
1569*y+16280332=4185^2 ->y=786,42000 y=785



(2*x+1)=4187

1601*y+16254956=4187^2 ->y=797,009993 y=801
1597*y+16258156=4187^2 ->y=797,002504 y=799
1593*y+16261348=4187^2 ->y=797 y=797 *********è uguale
1589*y+16264532=4187^2 ->y=797,002517 y=795
1585*y+16267708=4187^2 ->y=797,010094 y=793



(2*x+1)=4189

1625*y+16235588=4189^2
1621*y+16238836=4189^2
1617*y+16242076=4189^2 -> y=807,448979 y=809
1613*y+16245308=4189^2 -> y=807,447613 y=807 **********dovrebbe essere uguale poichè dopo y inizia a crescere
1609*y+16248532=4189^2 -> y=807,451211 y=805
1605*y+16251748=4189^2 -> y=807,459813 y=803
1601*y+16254956=4189^2 -> y=807,473454 y=801
1597*y+16258156=4189^2 -> y=807,492172 y=799
1593*y+16261348=4189^2 -> y=807,516000 y=797
1589*y+16264532=4189^2 -> y=807,544996 y=795
1585*y+16267708=4189^2 -> y=807,579179 y=793



Notare che

807,447613 - 807 > 0
797 - 797 = 0
786,41894 - 787 < 0


Quindi possiamo concludere che il costo computazionale è O((log_2(N))^2)

Credo che se corretto il log_2 sulla y sia scalabile.


E' corretto ?
Dove sbaglio?

 

[P_1_6]

Gentilmente qualcuno mi aiuterebbe a capire come mai nessuno risponde.
E' fuori tema?

 

[0xbro]

Gentilmente qualcuno mi aiuterebbe a capire come mai nessuno risponde.
E' fuori tema?

Probabilmente è una domanda troppo tecnica a cui nessuno sa rispondere... io personalmente non ho le competenze per poterti aiutare

 

[--- Ra ---]

Attacco ad RSA . E' corretto? Dove sbaglio?


Soluzione logaritmica per la fattorizzazione

Se N=8*G+3

prendete questa

solve [[[N+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=c ,x

ed assegnate un valore v a c dispari

vedrete che qualcosa D*y+f è diviso da T

ovviamente avrete due chance di assegnare v dipende se p=4*g+1 o p=4*g+3

poi facciamo 4*(D*y+f)-(2*y-1)^2=N e vediamo il valore della y

poi assegnamo ad 2*x+1 un valore (D*y+f)=(2*x+1)^2

e paragoniamo i due valori della y dal momento in cui essa è crescente




Esempio N=67586227

solve [[[67586227+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=1593 ,x

->

x=(T*(796-y)+1593*y+16261348)/(2*T)

quindi prenderemo 1593*y+16261348

Di seguito la tabella

1625*y+16235588
1621*y+16238836
1617*y+16242076 =4199*4175
1613*y+16245308
1609*y+16248532
1605*y+16251748 =4193*4181
1601*y+16254956 =4191*4183
1597*y+16258156 =4189*4185
1593*y+16261348 =4187^2
1589*y+16264532 =4185*4189
1585*y+16267708 =4183*4191
1581*y+16270876 =4181*4193
1577*y+16274036
1573*y+16277188
1569*y+16280332
1565*y+16283468
1561*y+16286596


4*(D*y+f)-(2*y-1)^2=N -> y

Di seguito la tabella

4*(1601*y+16254956) -(2*y-1)^2=67586227 -> y=801
4*(1597*y+16258156) -(2*y-1)^2=67586227 -> y=799
4*(1593*y+16261348) -(2*y-1)^2=67586227 -> y=797
4*(1589*y+16264532) -(2*y-1)^2=67586227 -> y=795
4*(1585*y+16267708) -(2*y-1)^2=67586227 -> y=793



(D*y+f)=(2*x+1)^2


(2*x+1)=4185

1601*y+16254956=4185^2 ->y=786,55153 y=801
1597*y+16258156=4185^2 ->y=786,51784 y=799
1593*y+16261348=4185^2 ->y=786.48901 y=797
1589*y+16264532=4185^2 ->y=786,46507 y=795
1585*y+16267708=4185^2 ->y=786,44605 y=793
1581*y+16270876=4185^2 ->y=786,43200 y=791
1577*y+16274036=4185^2 ->y=786,42295 y=789
1573*y+16277188=4185^2 ->y=786,41894 y=787 **********dovrebbe essere uguale poichè dopo y inizia a crescere
1569*y+16280332=4185^2 ->y=786,42000 y=785



(2*x+1)=4187

1601*y+16254956=4187^2 ->y=797,009993 y=801
1597*y+16258156=4187^2 ->y=797,002504 y=799
1593*y+16261348=4187^2 ->y=797 y=797 *********è uguale
1589*y+16264532=4187^2 ->y=797,002517 y=795
1585*y+16267708=4187^2 ->y=797,010094 y=793



(2*x+1)=4189

1625*y+16235588=4189^2
1621*y+16238836=4189^2
1617*y+16242076=4189^2 -> y=807,448979 y=809
1613*y+16245308=4189^2 -> y=807,447613 y=807 **********dovrebbe essere uguale poichè dopo y inizia a crescere
1609*y+16248532=4189^2 -> y=807,451211 y=805
1605*y+16251748=4189^2 -> y=807,459813 y=803
1601*y+16254956=4189^2 -> y=807,473454 y=801
1597*y+16258156=4189^2 -> y=807,492172 y=799
1593*y+16261348=4189^2 -> y=807,516000 y=797
1589*y+16264532=4189^2 -> y=807,544996 y=795
1585*y+16267708=4189^2 -> y=807,579179 y=793



Notare che

807,447613 - 807 > 0
797 - 797 = 0
786,41894 - 787 < 0


Quindi possiamo concludere che il costo computazionale è O((log_2(N))^2)

Credo che se corretto il log_2 sulla y sia scalabile.


E' corretto ?
Dove sbaglio?

Anche volendo aiutarti, mettendo il caso che qualcuno sia in grado, è impossibile farlo. Hai scritto un casino di cose incomprensibili, senza offesa eh, ma la formattazione è pessima, poi ci sono un sacco di lettere e se non specifichi cosa rappresentano diventano prive di significato. Non hai spiegato i passaggi che hai seguito, le operazioni svolte: hai scritto solo dei numeri...

 

[P_1_6]

Anche volendo aiutarti, mettendo il caso che qualcuno sia in grado, è impossibile farlo. Hai scritto un casino di cose incomprensibili, senza offesa eh, ma la formattazione è pessima, poi ci sono un sacco di lettere e se non specifichi cosa rappresentano diventano prive di significato. Non hai spiegato i passaggi che hai seguito, le operazioni svolte: hai scritto solo dei numeri...

tu dici che dovrei spiegare anche la parte teorica?
o solo l'algoritmo?

Messaggio unito automaticamente: 22 Novembre 2022

Probabilmente è una domanda troppo tecnica a cui nessuno sa rispondere... io personalmente non ho le competenze per poterti aiutare

Però credo ci sia gente qui dentro che lo implementerebbe in mezz'ora (compreso tu)

 

[0xbro]

Però credo ci sia gente qui dentro che lo implementerebbe in mezz'ora (compreso tu)

No no credimi, io non ne sono in grado, mi stai sopravvalutando (lo apprezzo però) ahahah matematica e argomenti di cripto non sono proprio il mio forte.

Io provo a taggare @JunkCoder e @St3ve che magari hanno qualche skill in più di me su questo argomento e possono essere d'aiuto

 

[P_1_6]

No no credimi, io non ne sono in grado, mi stai sopravvalutando (lo apprezzo però) ahahah matematica e argomenti di cripto non sono proprio il mio forte.

Io provo a taggare @JunkCoder e @St3ve che magari hanno qualche skill in più di me su questo argomento e possono essere d'aiuto

grazie

 

[JunkCoder]

No no credimi, io non ne sono in grado, mi stai sopravvalutando (lo apprezzo però) ahahah matematica e argomenti di cripto non sono proprio il mio forte.

Io provo a taggare @JunkCoder e @St3ve che magari hanno qualche skill in più di me su questo argomento e possono essere d'aiuto

Grazie anche a te, ma non è nemmeno il mio forte, mi interesso alla crittografia, mi piace vedere come funziona ma so bene di non essere in grado di implementare un cipher professionale da zero o fare attacchi di questo tipo, quindi mi limito ad usare correttamente implementazioni scritte da chi è più competente di me. Qualcuno come St3ve, solo lui può aiutare

 

[St3ve]

Ci abbiamo già provato in passato a dargli una mano, in particolare qui e qui, e i suoi thread sono il motivo che mi hanno spinto a creare la guida su RSA. Ad aiutarlo ora finirei a ripetere le stesse cose che sono già state dette negli altri thread: ci può stare che ti mancano i formalismi matematici necessari per postare un algoritmo comprensibile, ma resta il fatto che stai seguendo un approccio completamente privo di metodo. Il modo più semplice per far capire cosa stai facendo è fare un esempio con un numero abbastanza piccolo e portarlo avanti passo per passo con operazioni che puoi fare con una normale calcolatrice. Ci hai provato, però già dalla prima riga del tuo esempio non si capisce niente e soprattutto non sei mai arrivato a scrivere $$\(9967 \times 6781 = 67586227$$\). Dopo aver fatto l'esempio in piccolo, se vuoi veramente catturare l'attenzione di tutti, devi prendere un numero mai fattorizzato prima (tipo questo) e postare i due fattori. A quel punto non importa se nel tuo post sembra che hai scritto un sacco di boiate, avrai certamente ottenuto l'attenzione di tutti i matematici del mondo.

Con un linguaggio tipo python puoi facilmente fare calcoli anche con numeri anche molto grandi. Prova ad usare quello piuttosto che wolfram, almeno ti abituerai ad esprimere roba del tipo solve [[[N+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=c ,x in passaggi più semplici e comprensibili. Per esempio, se il numero che vuoi fattorizzare è

22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199

come faccio a calcolare la roba del tuo solve? In python puoi inserire quel numero e fare tutte le operazioni che vuoi però, ovviamente, non te la puoi sbrigare scrivendo "solve" (che magari internamente sta già fattorizzando).

tu dici che dovrei spiegare anche la parte teorica?
o solo l'algoritmo?

Idealmente una qualunque di queste due cose sarebbe sufficiente, ma è evidente che ti mancano i formalismi necessari per farlo. La mancanza di questi formalismi non sta fermando la tua curiosità, quindi secondo me uno come te dovrebbe prendere quel numero RSA-260 che ho scritto sopra e provare a fare "qualcosa". Se a un certo punto riesci a trovare due numeri interi p e q che moltiplicati danno quel numero, avrai l'attenzione di tutti.

Comunque la tua tenacia è ammirevole. Anche dopo tutti questi anni, non sei uno che molla. Il problema è che non hai fatto progressi dal punto di vista metodologico e le tue spiegazioni sono tanto incomprensibili quanto quelle di anni fa quindi a questo punto piuttosto che provare a descrivere un algoritmo ti conviene provare direttamente ad attaccare RSA-260.

 

[P_1_6]

@St3ve se ti va mi potresti dare una lezione su come passare da numeri ad un algoritmo, stesso in questo thread , e capire dov'è l'errore.
Potrebbe essere un buon insegnamento , non solo per me, ma per tutta la comunità.
Io ci metto il 100% di impegno per cercare di spiegarmi meglio.

 

[St3ve]

Un algoritmo è una una sequenza finita di istruzioni che ti porta a trovare le soluzioni di un determinato problema in tempo finito. Un algoritmo deve descrivere qual è l'input e qual è l'output, dev'essere ben definito e dev'essere operativo. Ben definito vuol dire che devo essere sempre in grado di capire esattamente cosa devo fare e operativo vuol dire che devo essere in grado di svolgere le istruzioni/comandi/regole che mi stai dando. Nel nostro caso stiamo cercando di risolvere il problema della fattorizzazione, quindi:

• input: un numero composto $$\(n \in \mathbb{N}$$\);
• output: due numeri $$\(p,q \in \mathbb{N}$$\), diversi da $$\(1$$\) e da $$\(n$$\), tali che $$\(p \times q = n$$\).

Quello che ti resta da fare è scrivere la sequenza di istruzioni che prende $$\(n$$\) e calcola $$\(p$$\) e $$\(q$$\). Questa sequenza di istruzioni dev'essere finita, devi poterla scrivere su un foglio di carta, e fin qui ci siamo perché già lo stai facendo. Questa sequenza di istruzioni deve anche terminare, ovvero deve farmi arrivare all'output in tempo finito, e questa è già una di quelle cose che non possiamo dare per scontato. Soprattutto, questa sequenza di istruzioni deve anche essere operativa. In questo momento questo è il tuo errore più grosso perché le tue istruzioni non sono operative. Se mi dici solve [[[N+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=c ,x io ho due problemi: 1) non ho capito cosa devo fare e 2) non so come si fa. Il modo più semplice per capire quali sono le istruzioni operative e quali no è imparare un linguaggio di programmazione: se lo riesci a spiegare ad un computer e se il computer riesce a svolgere tutti i tuoi comandi, allora puoi essere sicuro di averlo descritto in modo chiaro.

Dopo che avrai fatto questa roba, probabilmente vorrai anche riportare un esempio per far vedere che almeno apparentemente il tuo algoritmo sembra funzionare correttamente. Tu ci hai provato, ma il tuo esempio è incompleto perché non raggiungi mai l'output. Dovresti fare una cosa del genere

Esempio, $$\(n = 67586227$$\).

Tutti i tuoi calcoli svolti in maniera precisa, ripetibile e operativa.

Adesso abbiamo trovato $$\(9967$$\) e $$\(6781$$\) e notiamo che $$\(9967 \times 6781 = 67586227 = n$$\).

Nel tuo esempio non si capisce che hai fattorizzato $$\(67586227$$\) perché $$\(9967$$\) e $$\(6781$$\) non compaiono da nessuna parte. Cioè, l'obbiettivo era calcolare quei due numeri e tu non li hai scritti. Tu concludi trovando $$\(807$$\) e $$\(787$$\), ma non sono questi i fattori di $$\(67586227$$\) quindi chiaramente non puoi aver finito lì.

Una volta che avrai fatto tutto questo, non avrai comunque fatto niente di esaltante perché non avrai ancora convinto nessuno che il tuo algoritmo è efficiente e corretto. In questo momento mi sembra inutile provare a spiegarti come calcolare la complessità di un algoritmo. Il tuo problema più grosso è adesso è quello di fornire una descrizione operativa (i.e., che possiamo fare anche noi con carta e penna senza chiederci "cosa devo fare?" e "come faccio a farlo?"). Per farla breve, diciamo che il tuo algoritmo ha un'efficienza degna di nota se riesci ad usarlo per fattorizzare RSA-260.

 

[P_1_6]

@St3ve
Ho provato a scrivere l'algoritmo

Input N ((*)nella forma 8*G+3)




primo ciclo

Assegnamo ad x un numero intero nel centro del dominio [ (2*sqrt(N)-4)/8 , (N/3+3-4)/8 ]

secondo ciclo

Assegnando a v un numero dispari nel cento del dominio

prima nel dominio D1 dove ci sono i numeri v dove v mod 4 = 1
poi nel dominio D2 dove ci sono i numeri v dove v mod 4 = 3
((**)tralasciamo per il momento gli estremi dei domini D1 e D2)

avremo A=N-v*v-2*v+4*v*y
che sarà in funzione della sola y ovvero A=d*y+f

Ci calcoliamo A(i-1) , A(i) , A(i+1)

A(i-1)=N-(v+4)*(v+4)-2*(v+4)+4*(v+4)*y
A(i)=N-v*v-2*v+4*v*y
A(i+1)=N-(v-4)*(v-4)-2*(v-4)+4*(v-4)*y

Avremo d*y+f=(2*x+1)^2

Ci calcoliamo y(i-1) , y(i) , y(i+1)

y(i-1)=((2*x+1)^2-f(i-1))/d(i-1)
y(i)=((2*x+1)^2-f(i))/d(i)
y(i+1)=((2*x+1)^2-f(i+1))/d(i+1)

Se y(i-1)>y(i) && y(i+1)>y(i) -> esco dal secondo ciclo portandomi con me il valore di y(i) , d(i) ed f(i)

Se invece y(i-1)>y(i)>y(y+1) -> stringi il dominio D(j) a destra

Se invece y(y-1)<y(i)<(i+1) -> stringi il dominio D(j) a sinistra


//fuori dal secondo ciclo

Avremo 4*(d*y+f)-(2*y-1)^2=N

Ci calcoliamo Y=(sqrt(d^2+2*d+4*f-N)+d+1)/2

Se y==Y esco dal primo ciclo portandomi con me il valore di y ed x

Se invece y>Y stringo il dominio a destra

Se invece Y>y stringo il dominio a sinistra

//fuori da primo ciclo

p=4*x+1-2*(y-1)

q=4*x+3+2*(y-1)

Fine

 

[St3ve]

Assegnando a v un numero dispari nel cento del dominio

Prendo questa frase come d'esempio, ma ce ne sono tante altre. La differenza tra una ricetta e un algoritmo è che l'algoritmo dev'essere ben definito oltre che operativo. In una ricetta mi accontento di "aggiungi un pizzico di sale", mentre in un algoritmo voglio sapere quanti sono i milligrammi che devo prendere e se si tratta di sale grosso o sale fino, sale dell'hymalaia o sale iodato. Voglio sapere tutti i dettagli. Se tu mi dici di prendere un numero dispari al centro di [ 1 2 3 4 5 6 7 ] magari io prendo il 3 e qualcun altro prende il 5. Questa cosa non va bene. La descrizione dev'essere sufficientemente precisa per fare in modo che quello che faccio io sia uguale a quello che fanno tutti gli altri. Dobbiamo ottenere risultati identici e ripetibili.

Se hai un range di valori che vanno da $$\(\ell \gets \frac{2\sqrt{n}-4}{8}$$\) a $$\(r \gets\frac{\frac{n}{3}+3-4}{8}$$\), inclusi, e vuoi farmi prendere l'elemento centrale non dirmi Assegnamo ad x un numero intero nel centro del dominio [ (2*sqrt(N)-4)/8 , (N/3+3-4)/8 ], ma dimmi direttamente $$\(x \gets \left\lfloor \frac{\ell + r}{2} \right\rfloor$$\). Dammi un comando che posso ficcare dentro una calcolatrice.

Comunque vabbé, secondo me la cosa importante è che tu stesso sei in grado di capire la tua spiegazione. Adesso puoi prendere un software che ti permetta di fare calcoli con numeri molto grandi (io ti ho consigliato l'interprete python, ma va bene anche altro) prendi il numero di RSA-260 che ti ho scritto sopra e inizia a fare i calcoli scrivendo i vari risultati parziali su un foglio di carta. Se la tua spiegazione è sufficientemente precisa, non ti troverai mai a dover dire "questa cosa non so come si fa". Se hai scritto veramente un algoritmo a un certo punto arriverai al termine e se stai veramente fattorizzando a un certo punto troverai il valore di $$\(p$$\) e $$\(q$$\) che ci interessa e potremmo facilmente verificare se $$\(pq = n$$\). Per esempio, il primo step del tuo algoritmo è

from math import *
N = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
int(((2*sqrt(N)-4)/8 + (N/3+3-4)/8) / 2)

Quindi il valore di x che stai cercando (riga 1 della tua spiegazione) è

460683865198534732061975341836389725380289054465238629370026996855747886670466572011614850190807615177450038359398475138503035231652547466491963057067668804485144025943394981355532604497546555282632385190346194316342047224122658836422070461201489247430770688

adesso segnatelo su un foglio di carta e vai avanti. I cicli e quelle cose li per adesso dimenticale. Fai tutto con carta e penna e se c'è qualche step da ripetere, vorrà dire che lo ripeterai a mano. Praticamente devi fare la stessa cosa che hai fatto con 67586227 usando un numero più grande e mai fattorizzato prima. Se arrivi ad una soluzione avrai l'attenzione di tutti, anche perché tutti possono facilmente verificare se la tua soluzione è corretta, altrimenti vorrà dire che c'è qualche errore nel tuo algoritmo e dovrai rivederlo (prima su un numero piccolo e poi di nuovo su RSA-260, che è il più piccolo numero non ancora fattorizzato).

 

[losfracellato]

Prendo questa frase come d'esempio, ma ce ne sono tante altre. La differenza tra una ricetta e un algoritmo è che l'algoritmo dev'essere ben definito oltre che operativo. In una ricetta mi accontento di "aggiungi un pizzico di sale", mentre in un algoritmo voglio sapere quanti sono i milligrammi che devo prendere e se si tratta di sale grosso o sale fino, sale dell'hymalaia o sale iodato. Voglio sapere tutti i dettagli. Se tu mi dici di prendere un numero dispari al centro di [ 1 2 3 4 5 6 7 ] magari io prendo il 3 e qualcun altro prende il 5. Questa cosa non va bene. La descrizione dev'essere sufficientemente precisa per fare in modo che quello che faccio io sia uguale a quello che fanno tutti gli altri. Dobbiamo ottenere risultati identici e ripetibili.

Se hai un range di valori che vanno da $$\(\ell \gets \frac{2\sqrt{n}-4}{8}$$\) a $$\(r \gets\frac{\frac{n}{3}+3-4}{8}$$\), inclusi, e vuoi farmi prendere l'elemento centrale non dirmi Assegnamo ad x un numero intero nel centro del dominio [ (2*sqrt(N)-4)/8 , (N/3+3-4)/8 ], ma dimmi direttamente $$\(x \gets \left\lfloor \frac{\ell + r}{2} \right\rfloor$$\). Dammi un comando che posso ficcare dentro una calcolatrice.

Comunque vabbé, secondo me la cosa importante è che tu stesso sei in grado di capire la tua spiegazione. Adesso puoi prendere un software che ti permetta di fare calcoli con numeri molto grandi (io ti ho consigliato l'interprete python, ma va bene anche altro) prendi il numero di RSA-260 che ti ho scritto sopra e inizia a fare i calcoli scrivendo i vari risultati parziali su un foglio di carta. Se la tua spiegazione è sufficientemente precisa, non ti troverai mai a dover dire "questa cosa non so come si fa". Se hai scritto veramente un algoritmo a un certo punto arriverai al termine e se stai veramente fattorizzando a un certo punto troverai il valore di $$\(p$$\) e $$\(q$$\) che ci interessa e potremmo facilmente verificare se $$\(pq = n$$\). Per esempio, il primo step del tuo algoritmo è

from math import *
N = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
int(((2*sqrt(N)-4)/8 + (N/3+3-4)/8) / 2)

Quindi il valore di x che stai cercando (riga 1 della tua spiegazione) è

adesso segnatelo su un foglio di carta e vai avanti. I cicli e quelle cose li per adesso dimenticale. Fai tutto con carta e penna e se c'è qualche step da ripetere, vorrà dire che lo ripeterai a mano. Praticamente devi fare la stessa cosa che hai fatto con 67586227 usando un numero più grande e mai fattorizzato prima. Se arrivi ad una soluzione avrai l'attenzione di tutti, anche perché tutti possono facilmente verificare se la tua soluzione è corretta, altrimenti vorrà dire che c'è qualche errore nel tuo algoritmo e dovrai rivederlo (prima su un numero piccolo e poi di nuovo su RSA-260, che è il più piccolo numero non ancora fattorizzato).

Ciao sapresti decriptare questa stringa? $2y$10$YphZNUnn/Qf.SVt6QhUie.w8Zd.PmWHyBnn9mXcZ7wqkUZk03Sh1K

 

[St3ve]

Ciao sapresti decriptare questa stringa? $2y$10$YphZNUnn/Qf.SVt6QhUie.w8Zd.PmWHyBnn9mXcZ7wqkUZk03Sh1K

È off-topic, comunque le stringhe di quel tipo vengono da bcrypt. Su wikipedia hai tutta la spiegazione su cosa vuol dire quella stringa. In particolare il $ funge da separatore e 2y vuol dire che sta usando crypt_blowfish e che è stata generata dopo il 2011, 10 vuol dire che è stata generata in $$\(2^{10} = 1024$$\) iterazioni YphZNUnn/Qf.SVt6QhUie. è il salt e w8Zd.PmWHyBnn9mXcZ7wqkUZk03Sh1K è il digest. Salt e digest sono espressi in radix-64 come spiegato su wikipedia. Puoi fare un attacco al dizionario con hashcat usando -m 3200 o con qualsiasi altro programma che supporta quell'algoritmo. Con un attacco al dizionario non hai la garanzia di trovare la password. Con un attacco bruteforce ci metteresti troppo tempo.

 

[P_1_6]

Se arrivi ad una soluzione avrai l'attenzione di tutti, anche perché tutti possono facilmente verificare se la tua soluzione è corretta, altrimenti vorrà dire che c'è qualche errore nel tuo algoritmo e dovrai rivederlo (prima su un numero piccolo e poi di nuovo su RSA-260, che è il più piccolo numero non ancora fattorizzato).

Tu l'hai provato?
SI : funziona o non funziona?
NO: perchè non lo fai?

Messaggio unito automaticamente: 24 Novembre 2022

Ciao sapresti decriptare questa stringa? $2y$10$YphZNUnn/Qf.SVt6QhUie.w8Zd.PmWHyBnn9mXcZ7wqkUZk03Sh1K

che c'è scritto il quella stringa [tanto per curiosità]

 

[St3ve]

Tu l'hai provato?
SI : funziona o non funziona?
NO: perchè non lo fai?

No, non ho provato e non ho intenzione di provare. Provare richiede tempo, pazienza, attenzione e una conoscenza dettagliata dell'algoritmo che tu hai inventato. È compito tuo provare l'algoritmo perché sei tu che lo hai progettato e tu sei tu la persona più adatta ad accorgersi di un eventuale problema durante l'esecuzione. Io ti ho semplicemente spiegato un modo in cui puoi procedere per convincere un po' di gente che il tuo algoritmo è interessante: visto che ti mancano i formalismi per fare una dimostrazione matematica e visto che non conosci nessun linguaggio di programmazione, fai un esempio con carta e penna e tiralo avanti fino alla fine. Hai già provato a fare un esempio con un numero piccolo, ma non l'hai mai completato perché non sei mai arrivato a scrivere $$\(9967 \times 6781 = 67586227$$\). Ci vorrà il tempo che ci vorrà, ma se riesci a fare un esempio dove usi il tuo algoritmo per scomporre RSA-260 avrai lasciato tutti a bocca aperta. RSA-260 è il numero più piccolo che ad oggi ti puoi permettere di usare perché RSA-240 e RSA-250 sono stati già fattorizzati nel 2019 e nel 2020.

 

[P_1_6]

Un algoritmo è una una sequenza finita di istruzioni che ti porta a trovare le soluzioni di un determinato problema in tempo finito. Un algoritmo deve descrivere qual è l'input e qual è l'output, dev'essere ben definito e dev'essere operativo. Ben definito vuol dire che devo essere sempre in grado di capire esattamente cosa devo fare e operativo vuol dire che devo essere in grado di svolgere le istruzioni/comandi/regole che mi stai dando. Nel nostro caso stiamo cercando di risolvere il problema della fattorizzazione, quindi:

• input: un numero composto $$\(n \in \mathbb{N}$$\);
• output: due numeri $$\(p,q \in \mathbb{N}$$\), diversi da $$\(1$$\) e da $$\(n$$\), tali che $$\(p \times q = n$$\).

Quello che ti resta da fare è scrivere la sequenza di istruzioni che prende $$\(n$$\) e calcola $$\(p$$\) e $$\(q$$\). Questa sequenza di istruzioni dev'essere finita, devi poterla scrivere su un foglio di carta, e fin qui ci siamo perché già lo stai facendo. Questa sequenza di istruzioni deve anche terminare, ovvero deve farmi arrivare all'output in tempo finito, e questa è già una di quelle cose che non possiamo dare per scontato. Soprattutto, questa sequenza di istruzioni deve anche essere operativa. In questo momento questo è il tuo errore più grosso perché le tue istruzioni non sono operative. Se mi dici solve [[[N+6*n-(n*(n+4))]-4*n*y]-3]/8=T*x-((T-1)/2-1)*((T-1)/2)/2 , T-n=c ,x io ho due problemi: 1) non ho capito cosa devo fare e 2) non so come si fa. Il modo più semplice per capire quali sono le istruzioni operative e quali no è imparare un linguaggio di programmazione: se lo riesci a spiegare ad un computer e se il computer riesce a svolgere tutti i tuoi comandi, allora puoi essere sicuro di averlo descritto in modo chiaro.

Dopo che avrai fatto questa roba, probabilmente vorrai anche riportare un esempio per far vedere che almeno apparentemente il tuo algoritmo sembra funzionare correttamente. Tu ci hai provato, ma il tuo esempio è incompleto perché non raggiungi mai l'output. Dovresti fare una cosa del genere

Nel tuo esempio non si capisce che hai fattorizzato $$\(67586227$$\) perché $$\(9967$$\) e $$\(6781$$\) non compaiono da nessuna parte. Cioè, l'obbiettivo era calcolare quei due numeri e tu non li hai scritti. Tu concludi trovando $$\(807$$\) e $$\(787$$\), ma non sono questi i fattori di $$\(67586227$$\) quindi chiaramente non puoi aver finito lì.

Una volta che avrai fatto tutto questo, non avrai comunque fatto niente di esaltante perché non avrai ancora convinto nessuno che il tuo algoritmo è efficiente e corretto. In questo momento mi sembra inutile provare a spiegarti come calcolare la complessità di un algoritmo. Il tuo problema più grosso è adesso è quello di fornire una descrizione operativa (i.e., che possiamo fare anche noi con carta e penna senza chiederci "cosa devo fare?" e "come faccio a farlo?"). Per farla breve, diciamo che il tuo algoritmo ha un'efficienza degna di nota se riesci ad usarlo per fattorizzare RSA-260.

Devo dedurre che non funziona altrimenti qualcuno avrebbe già postato p e q di RSA2048

 

[JunkCoder]

Certo, una passeggiata fattorizzare RSA 2048 bit... è solo un numero con oltre 600 cifre decimali. Guarda se ci riuscissi potresti essere ricchissimo, potresti firmare e alterare codice, siti web, transazioni eccetera. RSA è al momento sicuro proprio perché ancora non si sa un modo per fattorizzare in modo così efficiente numeri così immensi, se le cose resteranno così, per vedere RSA2048 craccato in tempi umani dovremo aspettare un computer quantistico con abbastanza qubit.

 

[P_1_6]

Certo, una passeggiata fattorizzare RSA 2048 bit... è solo un numero con oltre 600 cifre decimali. Guarda se ci riuscissi potresti essere ricchissimo, potresti firmare e alterare codice, siti web, transazioni eccetera. RSA è al momento sicuro proprio perché ancora non si sa un modo per fattorizzare in modo così efficiente numeri così immensi, se le cose resteranno così, per vedere RSA2048 craccato in tempi umani dovremo aspettare un computer quantistico con abbastanza qubit.

Se quell'algoritmo funzionasse RSA2048 verrebbe fattorizzato dal mio computer ,vecchio più di dieci anni, in microsecondi.

 

[JunkCoder]

Se quell'algoritmo funzionasse RSA2048 verrebbe fattorizzato dal mio computer ,vecchio più di dieci anni, in microsecondi.

Mi rendo conto che mettere le cose in scala è difficile. Un numero a 2048 bit è molto molto di più degli atomi che ci sono sulla terra, del numero di stelle nell'universo conosciuto eccetera, no il tuo vecchio pc di dieci anni non può fattorizzarlo.

 

[P_1_6]

Mi rendo conto che mettere le cose in scala è difficile. Un numero a 2048 bit è molto molto di più degli atomi che ci sono sulla terra, del numero di stelle nell'universo conosciuto eccetera, no il tuo vecchio pc di dieci anni non può fattorizzarlo.

Sommettiamo un caffè ?
Implementalo passamelo
dammi istruzioni per farlo girare su Ubuntu
e se perdo ti offro un caffè

 

[JunkCoder]

Sommettiamo un caffè ?
Implementalo passamelo
dammi istruzioni per farlo girare su Ubuntu
e se perdo ti offro un caffè

Ma quale caffè per cortesia, chiudo per non sfociare nel ridicolo. Nessuno dei pc in commercio può farcela, se era così facile non dovevamo aspettare te per craccare rsa 2048.