Domanda Come decodificare RSA?

[P_1_6]

Prima di mettermi a fare qualcosa del genere devo avere la convinzione che quello che sto facendo abbia senso, voglio che ci sia come minimo una solida base teorica sul funzionamento di questa roba. Non mi metto a programmare roba potenzialmente (non so cosa tu abbia in mente) impegnativa senza essere convinto di quello che sto facendo.

si trattava di implementare cose così:
Fattorizzazione in O(K)

RSA=152416452563630190229=12345678949*12345732721
solve 36*J^2+12*J+1=152416452563630190229
J=JOLLY=2057617639
(152416452563630190229-1)/6=25402742093938365038
solve 2057617639-(25402742093938365038-6a^2-2a)/[2*(6a+1)]=a
a1=2057613158
a2=2057622120
6(a1)+1=12345678949
6(a2)+1=12345732721

vi resta da capire se è immaginario o reale

 

[St3ve]

Fattorizzazione in O(K)

Nemmeno su un ipotetico quantum computer siamo (almeno per adesso) in grado di fattorizzare così velocemente.

RSA=152416452563630190229=12345678949*12345732721
solve 36*J^2+12*J+1=152416452563630190229
J=JOLLY=2057617639
(152416452563630190229-1)/6=25402742093938365038
solve 2057617639-(25402742093938365038-6a^2-2a)/[2*(6a+1)]=a
a1=2057613158
a2=2057622120
6(a1)+1=12345678949
6(a2)+1=12345732721

vi resta da capire se è immaginario o reale

Prima di tutto il numero che hai scelto non è il prodotto di due fattori primi:
RSA = 152416452563630190229 = 7^2 * 61 * 4130389 * 12345678949 (questa è la scomposizione in fattori primi)
Quindi se avessi usato quel numero, potrei beccare le tue informazioni segrete semplicemente usando p=7 e q=21773778937661455747. Il numero che hai scelto è proprio fragilissimo, RSA vero è almeno a 1024 bit mentre il tuo è come se fosse a 3 bit.

Prova a fattorizzare RSA1=21773778937661455747, se ce la fai allora vedi quanto diventa più difficile fattorizzare quando si fa crescere l'input provando a fattorizzare RSA2=142723770917069675375699806540535013763. E soprattutto tieni a mente che quelli che ti ho passato sono due numeri minuscoli per RSA: il primo riesco a fattorizzarlo in pochi secondi usando l'algoritmo più stupido del mondo, già con il secondo non ho perso tempo a provarci perché sono consapevole che i tempi crescono molto velocemente.

 

[P_1_6]

solve 36*j^2+12j+1=21773778937661455747
j=777706366
solve 777706366-(3628963156276909291-6a^2-2a)/[7.77706366*(6a+1)]=a
a=1
X=7
dai un occhiata
http://www.albericolepore.org/3-fattorizzazione-di-lepore/

 

[St3ve]

Non vedo i fattori primi... fammi vedere quei due numeri che moltiplicati tra loro danno RSA1 e vediamo se riesci a fare la stessa cosa anche con RSA2.

 

[P_1_6]

9391857873434221831*15196542882189227173=142723770917069675375699806540535013763

 

[ArrackHack]

Rsatool

 

[P_1_6]

grazie @Virgula7eBloom0 ma io non so programmare.
Per piacere me lo spiegheresti rapidamente

 

[BetaRunner]

Ciao, se intendi decodificare una chiave RSA attraverso il metodo della forza bruta (provare con tutti i numeri primi e moltiplicarli tra di loro) hai bisogno di un computer quantistico. Se vuoi un algoritmo che te lo trovi oppure ci vuoi provare con un computer normale perdici le speranze. La fattorizzazione di un prodotto di due numeri primi di 300 cifre l'uno non è qualcosa di "banalmente facile".

 

[P_1_6]

Quindi questo non va

 

[ArrackHack]

Quello è già uno script programmato per decodificare l'RSA. se vuoi decodificare manualmente il tutto studiati i calcoli che vengono intrapresi dal codice sorgente in quanto è scritto in python. Se vuoi avviarlo invece in linux:

git clone https://github.com/ius/rsatool

cd /home

cd rsatool

python rsatool.py

per aiuto : python rsatool.py -h

 

[BetaRunner]

Quindi questo non va

E' improponibile più che altro, non esiste un algoritmo che lo trovi velocemente. Anche quando, solitamente, l'RSA è combinato con altri metodi di crittografia in quanto calcolare il messaggio reale, anche avendo i due numeri primi, non è alquanto veloce. Per seconda cosa i numeri vengono scelti con "specifiche" proprietà che rendono davvero difficile la loro ricerca. Quindi a meno che non vuoi farlo solamente per "divertimento", utilizzando dei primi piccoli il tutto è abbastanza inutile.

 

[_Nes]

Un testo/informazione criptata tramite l'algoritmo RSA non è impossibile da decriptare; è computazionalmente difficile.
Per decriptare un'informazione criptata con RSA è necessario calcolarne la CHIAVE per decriptarlo.
L'RSA è un algoritmo "a chiave pubblica" ovvero genera una coppia di chiavi una utilizzata da chi vuole inviare l'informazione (che è quella pubblica) e una privata che è in possesso SOLO dal destinatario del messaggio che è quella da decriptare.
Il funzionamento dell'RSA è il seguente:
> Si scelgono due numeri PRIMI e tra loro (più grandi sono, meglio è) chiamiamoli P e Q.
> Si calcola N=P*Q e F(n)=(P-1)(Q-1)
> Si sceglie un numero C tale che F<F(n) e F COPRIMO di F(n)
> Si calcola un numero D tale che D*C sia CONGRUO a MOD(F(N))
In questo modo otteniamo una coppia di chiavi: (N,E) PUBBLICA e (N,D) PRIVATA.

Se possiedi le chiavi ovviamente è una passeggiata decriptare l'RSA.
Il metodo della fattorizzazione permette di calcolare P e Q perché si ha che:
ax^2+bx+c=0 si puo' scrivere come P/a(x-x1) + Q/(x-x2). (E' un metodo che si utilizza per risolvere gli integrali). Questo metodo può essere utilizzato SE E SOLO SE si possiede la funzione F(N).
Avendo P e Q puoi facilmente risalire alle chiavi.

Se non sei in possesso della funzione F(N) l'unico modo è il bruteforce.
Ovvero conoscendo il numero possibili di caratteri per una chiave (lettere dell'alfabeto maiuscole e minuscole)+(numeri da 0 a 9)+caratteri speciali le possibili chiavi (in quantità) da provare si calcolano così:
Sia K il numero di caratteri utilizzabili in una chiave
Sia N il numero di caratteri di cui è composta la chiave
Numero chiavi = (K!) / ((K-N)!*N!) dove con ! si indica il fattoriale. (formula delle combinazioni)
L'unica cosa è provare tutte le possibili chiavi in questo caso .

 

[St3ve]

Ciao, se intendi decodificare una chiave RSA attraverso il metodo della forza bruta (provare con tutti i numeri primi e moltiplicarli tra di loro) hai bisogno di un computer quantistico.

I quantum computer dovrebbero (se esistessero) usare l'algoritmo di shor, non la forza bruta. Con il bruteforce non si ottiene niente se si usano delle chiavi così grandi.

Comunque io gli ho passato un numero n=p*q dove p e q erano due numeri primi a 64 bit e lui nel giro di 11 minuti (questo è il tempo trascorso tra il mio messaggio e il suo, quindi ci avrà messo anche meno) mi ha scritto quali erano p e q.
La cosa improponibile (almeno per me) è capire la spiegazione che ha scritto sul suo sito. Probabilmente sarà qualcosa di già noto, ma visto che non capisco cosa sta facendo ho poco da commentargli.
Finché non capisco l'unica cosa che ho da dirgli è che di complessità computazionale ci capisce poco, perché già quei pochi calcoli che vedo portano a roba più alta di O(n).

@_Nes: Di F(n) non si conosce il valore, non la funzione, e per andare di bruteforce basta vedere il valore da cercare come un numero (viene anche naturale nel caso di RSA) invece che una stringa. Ad esempio se vuoi andare di bruteforce su rsa1024 devi provare 2^1024 (in realtà 2^1023) valori, come trovi il divisore di N hai finito.

PS.
So bene che 64 bit sono pochi, ma senza saper programmare mi ha dato la risposta nel giro di poco tempo. Personalmente mi ha stupito, pensavo non ce l'avrebbe fatta.

 

[P_1_6]

Vi invito a dare un occhiata qui http://www.albericolepore.org/lepore-factorization-rsa/
quando e se ci capirete qualcosa (perchè è scritta con i piedi) vedrete quant'è facile fattorizzare.

 

[_Nes]

Come ti ho già spiegato si utilizza la fattorizzazione dei polinomi (stesso metodo che si utilizza per il calcolo degli integrali con delta a denominatore maggiore di 0).
Il metodo della fattorizzazione permette di calcolare P e Q perché si ha che:
ax^2+bx+c=0 se b^2-4ac>0 si può scrivere come P/a(x-x1) + Q/(x-x2). Dove X1 e X2 sono le RADICI del polinomio (ovvero dove si azzera). Questo metodo può essere utilizzato SE E SOLO SE si possiede la funzione F(N).
Avendo P e Q puoi facilmente risalire alle chiavi.

Per maggiori informazioni su come ricavare P e Q visita questo link (tralascia l'integale e considera solo il polinomio e il sistema):

 

[P_1_6]

Questo è il numero che mi ha dato @St3ve

RSA=142723770917069675375699806540535013763=p*q
p=6a+1

G=(RSA-1)/6
C=RSA-G
A=(2*(G^2)+G)modulo(RSA)
B=RSA-A



Questi che vi elenco hanno tutti la caratteristica di essere divisibili per p=6a+1
RSA ; G-a ; C+a ;A-2a^2-a ; B+2a^2+a
quindi

X(RSA)+Y(G-a)+Z(C+a)+D(A-2a^2-a)+E(B+2a^2+a)=J(6a+1)

Con un bruteforce su X,Y,Z,D,E,J (che possono essere sia positivi che negativi) Vi trovate "a" quindi "6a+1=p".

 

[St3ve]

Non ho la minima idea di cosa tu stia facendo e da dove saltino quei numeri, ma ok.
Facciamo un esempio, uso numeri tanto grandi quanto quelli dell'altra volta:

RSA = 140089267639071478002348819284711337427

G = (RSA - 1) / 6 = 23348211273178579667058136547451889571
C = RSA - G = 116741056365892898335290682737259447856
A = 2*G^2 + G mod RSA = 108958319274833371779604637221442151332
B = RSA - A = 31130948364238106222744182063269186095

E adesso? Come cavolo hai fatto a trovare i fattori primi così velocemente?

 

[P_1_6]

Devi fare il ciclo
----------------------------------------------
@St3ve ho trovato questo sistema però non so come calcolarlo
((6*m+sqrt(36*m^2+4*7*140089267639071478002348819284711337427))/(2*7))=m+n
((m+7*n)*(m+n))=140089267639071478002348819284711337427

potreste aiutarmi a calcolarlo

 

[St3ve]

Stando a wolframalpha è un sistema impossibile, non esiste nessun valore di m e n tale per cui quell'equazione è rispettata.

Ma tu come hai fatto a calcolare nel giro di una manciata di minuti i fattori primi del numero che ti avevo dato? Sei andato su wolfram e hai chiesto di fattorizzartelo oppure ce l'hai davvero fatta autonomamente?

 

[P_1_6]

solve m=7809648153904121330 , ((6*m+sqrt(36*m^2+4*7*140089267639071478002348819284711337427))/(2*7))=m+n , ((m+7*n)*(m+n))=140089267639071478002348819284711337427

Anche il wolframalpha sbaglia

Questo sistema ti dovrebbe permettere di trovare i fattori in meno di un secondo

 

[P_1_6]

Vi faccio vedere la dimostrazione
X^2+6nX=RSA
7X^2-6mX=RSA
Sottraendo la prima dalla seconda si ha
6X^2-6(m+n)X=0
segue X=m+n
n=(RSA-X^2)/(6X)
ma RSA=X*Y
quindi n=(Y-X)/6
segue Y=X+6n=m+7n
il resto viene di conseguenza

 

[Barbossa]

Riprendo la discussione sperando di non andare in necropost.

Prima di tutto faccio notare che dal sito indicato da @P_1_6 MANCANO DEL TUTTO LE DIMOSTRAZIONI alle affermazioni che espone, quindi dal punto di vista matematico le sue affermazioni NON HANNO VALORE.

Fattorizzazione in O(K)

Un bruteforcing dei divisori ha complessità pari a O(N^0,5). Un algoritmo a tempo polinomiale (inteso come numero di cifre) dovrebbe avere complessità pari a O(log N), che, osservando superficialmente gli articoli scritti (scritti malissimo e che danno l'impressione di essere scritti da una persona completamente a digiuno di matematica) non raggiunge minimamente.

Dato che gli articoli sono privi di dimostrazioni e scritti malissimo, è impossibile verificare la bontà degli stessi, e allo stesso tempo è lecito chiedersi se l'autore abbia usato davvero il suo algoritmo per fattorizzare il numero, e non abbia invece utilizzato un altro algoritmo (magari integrato in un programma già fatto) più efficiente. NOTA: queste sono considerazioni personali, date da un osservazione dei risultati da lui pubblicati.

Infine, vorrei mostrare questo link:

http://www.matematicamente.it/forum/viewtopic.php?t=146118

 

[P_1_6]

Barbossa hai ragione.

 

[nullptr]

@St3ve, non ti chiedere come ha fatto perchè il nostro tizio lo conosciamo già:

http://www.matematicamente.it/forum/viewtopic.php?t=146118

 

[_ _]

@St3ve con un buon algoritmo (tipo ECM, del quale non capisco molto) fattorizzare un numero di quelle dimensione è questione di pochi istanti, prova a buttarlo qua dentro.

Detto questo l'algoritmo di Lepore mi sembra una gran vaccata, se non altro perché l'autore dimostra chiaramente di non avere la minima conoscenza della notazione e dei canali stanard per pubblicare i propri risultati usati nel settore