Domanda Come decodificare RSA?

[P_1_6]

Il problema e che questo non è l'ultimo file che ho postato.
dicevo io

 

[P_1_6]

Il problema e che questo non è l'ultimo file che ho postato.
dicevo io

 

[P_1_6]

Avevo pensato questo algoritmo:

EDIT:
vi mostro la strada giusta del 1891
X00-1891=(X-19)09
1891-(X-19)09=(-X+37)82
(X-19)09-(-X+37)82=(2X-57)27
(-X+37)82-(2X-57)27=(-3X+94)55
(2X-57)27-(-3X+94)55=(5X-152)72
(5X-152)72-(-3X+94)55=(8X-246)17
(8X-246)17-(-3X+94)55=(11X-341)62



X00-1891=(X-19)09
1891-(X-19)09=(-X+37)82
X>19 e X<37

Siccome devono essere tutti numeri positivi si ha:
(X-19)09-(-X+37)82=(2X-57)27
X>19 - X<37 = X>28,.... (che è possibile)
invece l'altra strada era
(-X+37)82-(X-19)09=(-2X+57)27
X<37 - X>19 = X<28,.... (che è impossibile)
perchè per ora se il massimo della X è 37 e il minmo è 19 -> 37 - 19 =18 che è minore di 19

(-X+37)82-(2X-57)27=(-3X+94)55
X<37 - X >28,.... = X<31,........ (che è possibile)
invece l'altra strada era
(2X-57)27-(-X+37)82=(3X-94)55
X>28,... - X<37 = X>31,,,,,,, (che è impossibile)
perchè per ora se il massimo della X è 37 e il minmo è 28 -> 37 - 28 =9 che è minore di 31

ecc. ecc.

Quindi ci rimane da stabilire solo
1891-(X-19)09=(-X+37)82
oppure
(X-19)09-1891=(X-37)82

per avere la strada giusta e cioè un Euclide(3100,1891)

Qualcuno vorrebbe scrivere il sorgente per numeri grandi?
vi darò tutte le informazioni

 

[P_1_6]

Hey qualcuno lo ha scritto?

 

[Barbossa]

Hey qualcuno lo ha scritto?

Non credo che qualcuno abbia capito il ragionamento

 

[theboy]

Hey qualcuno lo ha scritto?

Come già detto qualche post fa il tuo ragionamento può funzionare su numeri "piccoli" minori di 50 cifre circa perché poi l'algoritmo richiederebbe anni per trovare il giusto numero che lo fattorizza.

Inviato dal mio Oneplus X utilizzando Tapatalk

 

[P_1_6]

Come già detto qualche post fa il tuo ragionamento può funzionare su numeri "piccoli" minori di 50 cifre circa perché poi l'algoritmo richiederebbe anni per trovare il giusto numero che lo fattorizza.

Inviato dal mio Oneplus X utilizzando Tapatalk

Se funziona come penso io è una costante(il numero delle Cifre del numero da fattorizzare) per Euclide per logaritmo in base due (che sarebbe la ricerca della quantità di strada giusta).
Quindi se funziona funziona anche per grandi numeri.
Se funziona.

 

[Barbossa]

Ma ti stai dedicando anche allo studio di altri algoritmi già noti, come il metodo rho e il p-1 di Pollard, il metodo di Lehman o il crivello quadratico di Pomerance (che risulta di complessità sub-esponenziale)?

 

[P_1_6]

No,
Ho appena letto il crivello quadratico ma è probabilistico ho visto?
Se funziona il mio, che complessità computazionale ha?

 

[St3ve]

Devi prima imparare la matematica di base, altrimenti ciò che scrivi non ha senso. Già quando scrivi "X00-1891=(X-19)09" (nella seconda riga del tuo messaggio precedente) io non capisco cosa stai dicendo con X00 e con 09 e non vado avanti a leggere.
Devi usare un linguaggio corretto se vuoi anche solo avere la speranza di essere ascoltato da qualcuno, altrimenti l'impegno per cercare di capire quello che stai dicendo non giustifica la nostra volontà nell'aiutarti. Se non hai delle solide basi, come puoi pretendere di risolvere il problema della fattorizzazione?
Dovresti investire una settimana del tuo tempo per scrivere un post esaustivo e preciso, spiegando prima l'algoritmo nel caso generale dove n=p*q (letterali) e poi portare un esempio di un caso specifico dove scegli un valore per p e per q. Finché quello di cui parli non è scritto chiaramente, difficilmente gli altri si renderanno disponibili ad aiutarti seriamente.

Ho appena letto il crivello quadratico ma è probabilistico ho visto?

Il fatto che sia un algoritmo probabilistico non è un problema, anche l'algoritmo che viene usato per scegliere i numeri primi è probabilistico. Il setaccio quadratico è buono per fattorizzare numeri di ~40 cifre decimali, che non sono poi così tante.

Se funziona il mio, che complessità computazionale ha?

Prima devi trasformare quello che hai in testa (e che hai provato a grandi in qualche modo) in un algoritmo. Dopo che abbiamo un algoritmo, possiamo provare a calcolare il suo costo.

 

[P_1_6]

Grazie @St3ve ascolterò il tuo consiglio

per ora ho fatto un esempio che spiega il logaritmo ad ogni step

Esempio:

45459487
massimo_per_X = (int) sqrt(45459487)=6742
minimo_per_X = 1

X*1000 - 45459487= (X-4546)*1000+0513 si testa 4546
massimo_per_X =6742
minimo_per_X = 4546


45459487-301*[(X-4546)*1000+0513]=45459487-(301X-1368346+15)*1000+4413= (-301X+1372876)*1000+5074
massimo_per_X =4561,.....
minimo_per_X = 4546


45459487-302*[(X-4546)*1000+0513]=45459487-(302X-1372892+15)*1000+4926= (-302X+1377422)*1000+4561 si testa 1377422/302=4561 non fatevi trarre in inganno non è il 4561 di (302X-1377422)*1000+4561
massimo_per_X =4561
minimo_per_X = 4546


45459487-303*[(X-4546)*1000+0513]=45459487-(303X-1377438+15)*1000+5439=(-303X+1386910)*1000+4048 si nota che
massimo_per_X = 4577,..... controsenso perchè crescente rispetto 4561 non si procede
minimo_per_X =4546



Esempio 2

10738451

massimo_per_X = (int) sqrt(10738451)=3276
minimo_per_X = 1

(livello 0)
X*100000 - 10738451= (X-108)*10000+61549 si testa 108
massimo_per_X =3276
minimo_per_X = 108


Scelta strada (ramo sinistro 1 livello)
10738451-[(X-108)*10000+61549]=(-X+114)+76902
massimo_per_X =114
minimo_per_X = 108

quantità di strada (ramo destro 2 livello)[impiega logaritmo]
10738451-2*[(X-108)*10000+61549]=10738451-[(2X-215)*100000+23098]=(-2X+322)*100000+15353
massimo_per_X =161 controsenso massimo era 114
minimo_per_X = 108

Scelta strada (ramo sinistro 2 livello)
(-X+114)+76902-[(X-108)*100000+61549]=(-x+122)*100000+15353
massimo_per_X =122 controsenso massimo era 114
minimo_per_X = 108

Ramo sinistro al primo livello chiuso

quantità di strada (ramo destro 1 livello)[impiega logaritmo]
X*10000 -6* 10738451=X*100000-64430706=(X-645)*100000+69294
massimo_per_X =3276
minimo_per_X = 645

(ramo sinistro 7 livello)
X*10000 -7* 10738451=(X-752)*100000+30843
massimo_per_X =3276
minimo_per_X = 752

(ramo sinistro 8 livello)
X*10000 -8* 10738451=X*100000-85907608 [***DA VERIFICARE***]

Scelta strada (ramo destro 8 livello)
10738451-(X-752)*100000+30843=(-X+859)*100000+07608
massimo_per_X =859
minimo_per_X = 752

quantità di strada (ramo destro 9 livello)[impiega logaritmo]
10738451-2*[(X-752)*100000+30843]=10738451-[(2X-1504)*100000+61686]=(-2X+1612)*100000+76765 [***DA VERIFICARE***]
massimo_per_X =806
minimo_per_X = 752


quantità di strada (ramo sinistro 9 livello)[impiega logaritmo]
(X-752)*100000+30843-(-X+859)*100000+07608=(2X-1611)*100000+23235
massimo_per_X =859
minimo_per_X = 805,5

(ramo sinistro 10 livello)
(X-752)*100000+30843-2*[(-X+859)*100000+07608]=(3X-2470)*100000+15627 [***DA VERIFICARE***]
massimo_per_X =859
minimo_per_X = 823,3333

quantità di strada (ramo destro 10 livello)[impiega logaritmo]
(-X+859)*100000+07608-4*[(2X-1611)*100000+23235]=(-X+859)*100000+07608-(8X-6444)*100000+92940=(-9X+7302)*100000+14668
massimo_per_X =811,333
minimo_per_X = 805,5

(ramo destro 11 livello)
(-X+859)*100000+07608-5*[(2X-1611)*100000+23235]=(-X+859)*100000+07608-(10X-8056)+16175=(-11X+8914)*100000 [***DA VERIFICARE***]
massimo_per_X =810,36
minimo_per_X = 805,5

quantità di strada (ramo sinistro 11 livello)[impiega logaritmo]
(2X-1611)*100000+23235-4*[(-9X+7302)*100000+14668]=(38X-30817) +79231
massimo_per_X =811,333
minimo_per_X = 810,97

Ci possiamo fermare qui guardando massimo è minimo l'unico numero possibile è 811

 

[_ _]

X*1000 - 45459487= (X-4546)*1000+0513 si testa 4546

Che cosa è X? Come hai ottenuto valori massimi e minimi? Perché stai facendo questo conto?
Finché riporti conti che a noi appaiono completamente arbitrari, formattati male, senza la minima giustificazione non capiremo mai cosa vuoi dire.

Stessa roba più avanti, ramo sinistro e destro? Di diversi livelli? Cosa sono?

 

[P_1_6]

Questa è una nuova idea:
Allora l'idea è che un numero n=p*q e n ha Cn cifre e p Cp cifre inserite nel algoritmo di Euclide per il calcolo del massimo comun divisore in questo modo
Euclide[ p*(10^Cn) , n] ad un certo punto le p cifre davanti scompaiono quindi scompariranno in [logaritmo in base 2 di {[ p*(10^Cn)]/n } ]
I valori massimi e i valori minimi vengono dal fatto che il valore nelle parentesi (+-(K*p)+-D) corrispondenti alle Cp cifre nel algoritmo di Euclide deve essere sempre maggiore di 0 e faccio D/K per conoscere il valore massimo e minomo di p

Se non dovesse funzionare questa nuova idea la precedente la si può capire il concetto è sempre quello.

Edit:
ho modificato la parte nelle parentesi graffe {[ p*(10^Cn)]/n }

 

[Xenium]

Ho cercato di capire gli esempi postati ma, come ti è già stato detto prima, se non aggiungi alcuna descrizione ai valori che riporti non capiremo mai cosa hai scritto.

X*1000 - 45459487= (X-4546)*1000+0513 si testa 4546

Ad esempio qui come hai scelto il valore 4546? Hai preso le prime 4 cifre di 45459487 e le hai sommate a 1? In base a quale criterio hai scelto le prime 4 cifre e non, per esempio, le prime 3?
Che cos'è 0513? Come lo hai ottenuto?
Se non spieghi ogni tuo passaggio come pensi che possiamo capire?

 

[P_1_6]

Se non mi sono spiegato bene per la nuova idea significa che non potrei mai spiegarmi bene nella vecchia idea.
Ora il calcolo che hai citato è p*10000000-D/K(45459487)= ad un numero che è minore di di 99999999 (9 Cn volte)
quindi le Cp cifre iniziali saranno uguali a zero quindi sarà p-p=0 il secondo p è in chiaro


EDIT:

Esempio

45459487

X*100000000 - 10030*45459487=X*100000000-455958654610=(X-4560)*100000000+41345390

141345390-45459487=95885903

X*100000000 - 10031*45459487=X*100000000-456004114097=(X-4561)*100000000+95885903

95885903-45459487=50426416

X*100000000 - 10032*45459487=X*100000000-456049573584=(X-4561)*100000000+50426416

50426416-45459487=04966929

X*100000000 - 10033*45459487=X*100000000-456095033971=(X-4561)*100000000+04966929

104966929-45459487=59507442 [DIVERSO1]

X*100000000 - 10034*45459487=X*100000000 -456140492558=(X-4562)*100000000+8675052 [DIVERSO1]

108675052-14047955=94627097 [DIVERSO2]

X*100000000 - 10035*45459487=X*100000000 -456185952045=(X-4562)*100000000+14047955 [DIVERSO2]

Si può ben notare il logaritmo in base 2



EDIT:
----------------------------------------------------------------------------------------
In realtà è così:
Questa è una nuova idea per la fattorizzazione in log:
Allora l'idea è che un numero n=p*q e n ha Cn cifre e p Cp cifre inserite nel algoritmo di Euclide per il calcolo del massimo comun divisore in questo modo
Euclide[ p*(10^(Cn)) , n] ad un certo punto le p cifre davanti scompaiono quindi scompariranno in [log[ 2] ]
Ora è p*100000000-K(45459487)= ad un numero che è minore di di 99999999 (9 Cn volte)
(per un certo K)
quindi le Cp cifre iniziali saranno uguali a zero quindi sarà p-p=0 il secondo p è in chiaro

 

[_ _]

Non penso di capire quello che vuoi fare, allora, abbiamo n=pq semiprimo, conosciamo n (e quindi ovviamente Cn), ma non conosciamo né p né q, con queste informazioni a disposizione come fai ad applicare l'algoritmo di Euclide a p*(10^(Cn)) e n?

edit: uhm, ok, allora, se non erro stai provando a fare l'algoritmo di Euclide tenendo p come incognita, quello che non capisco è nel primo passaggio, tu calcoli X*100000000 - 10030*45459487, come hai ottenuto il 10030? Cosa sono D e K?

 

[P_1_6]

8675052 [DIVERSO1]

Putroppo li c'è un errore di calcolo

[QUOTE="_ _, post: 4492957, member: 190485"
edit: uhm, ok, allora, se non erro stai provando a fare l'algoritmo di Euclide tenendo p come incognita, quello che non capisco è nel primo passaggio, tu calcoli X*100000000 - 10030*45459487, come hai ottenuto il 10030? Cosa sono D e K?[/QUOTE]

10033 era il numero da cercare quindi volevo far vedere il logaritmo che al di sopra era una cosa al di sotto un'altra
D e K sono dell'altro algoritmo che potrebbe anche funzionare

 

[_ _]

Puoi per favore fare un esempio in cui fattorizzi un semiprimo piccolo, tipo 20737, in cui spieghi passo per passo che cosa stai calcolando e perché, come ottieni tutti i numeri diversi da 20737 che usi e cosa sono tutte le incognite che usi?

 

[P_1_6]

Non va in log
avevo fatto un errore di calcolo
-------------------------------------------------------------
EDIT:
Ho pensato a questa soluzione però non so risolvere questo sistema

X⋅10000000−Z⋅45459487=3⋅4540513+500000

{(INTERO)[100000000/(Z⋅10+3)]}⋅X=45459487

per (INTERO) intendo parte intera

qualcuno potrebbe darmi una mano

 

[P_1_6]

@St3ve mi dai un numero RSA di 20 cifre

 

[_ _]

A cosa ti serve un semiprimo di 20 cifre se non sei ancora riuscito a spiegarci bene, passo per passo, giustificando i passaggi che fai e le incognite che usi con uno da 5? (Il 20737 che chiedevo l'altra volta)

Comunque numeri da 20 cifre sono MOLTO veloci da fattorizzare, conta che una chiave RSA vera ha circa dalle 310 alle 1230 cifre decimali (da 1024 a 4096 bit)

 

[P_1_6]

credo questo sia il metodo più veloce però con i numeri piccoli non si vede

p*1000-4*20737=(X-83)*1000+052 si testa 83

20737-3*(X-83)*1000+052=(-3X+269)*1000+581

(X-83)*1000+052-2*(-3X+269)*1000+581=(7X-623)+890 si testa 623/7=89

Le altre strade si bloccano tutte tranne una

EDIT

Per chi ha seguito il post e non

siamo giunti quà
p*10^7-Z*45459487=

ora conoscendo il numero delle cifre di p
e conoscendo che p>4545
possiamo dedurre
p*10^7 - 45459487*10^3=un numero qualsiasi
e cercando i valori negativi
(+-p+-H)+il restante ricordate
H$ e $p sono uguali


EDIT

EDIT:

Ovviamente non è la fine la fine è questa

"p⋅107−45459487⋅(103)=un numero qualsiasii"

dobbiamo conoscre di quante cifre è la differenza

"H e p sono uguali"


e agire una o più cifre alla volta

EDIT

per fattorizzare un numero n impiego al massimo
[2^al numero delle cifre di sqrt(n)]
è un buon risultato ?
Forse è meglio quello iniziale di questo post

 

[_ _]

Allora, inizio ad avere dubbi su chi di noi due non sia in grado di spiegarsi e francamente mi sto stancando, a meno di ricevere una spiegazione esaustiva penso che abbandonerò questa discussione.

Puoi fornire una spiegazione completa ovvero contente l'algoritmo in pseudocodice, la spiegazione matematica di cosa stai facendo nei vari passaggi, perché lo stai facendo e perché dovrebbe funzionare e un esempio con numeri piccoli?

Ti faccio vedere cosa intendo usando un altro algoritmo di fattorizzazione...

Algoritmo rho di Pollard

L'algoritmo si basa sull'osservazione che se prendo più di (circa) 1.77n^0.5 numeri interi nell'intervallo [1,n] c'è una probabilità superiore a 0.5 che non siano tutti distinti (questa osservazione la diamo per buona senza dimostrazione)

L'algoritmo usa un polinomio g(x) che viene calcolato mod n (dove n è il numero da fattorizzare) come generatore di numeri pseudocasuali nell'intervallo [1,n], in particolare viene costruita una successione di valori come segue:
x0 = 2 (2 è una scelta arbitraria, è quella più comune, ma va bene un numero casuale)
x1 = g(2)
x2 = g(g(2))
x3 = g(g(g(2)))
e così via.

una scelta tipica è g(x)=x²+1

Supponiamo n=pq (per comodità, ma non è necessario che n sia un semiprimo), visto che p<n^0.5 sappiamo che la sequenza x0,x1,x2,x3... si ripeterà probabilmente prima se calcolata mod p che se calcolata mod n (per la considerazione iniziale).
Inoltre visto che ogni termine dipende solo dal precedente una volta ottenuto un singolo valore ripetuto sappiamo che da lì in poi tutti i valori si ripeteranno in un ciclo.

non conoscendo p, non possiamo sapere quando avviene una ripetizione mod p, ma possiamo controllare se è avvenuta calcolando gcd(xm-xk , n), se questo è uguale a p allora è avvenuta una ripetizione mod p (questo perché se è avvenuto una ripetizione allora xm=xk mod p, ovvero p|xm-xk) prima di una ripetizione mod n è abbiamo trovato un fattore, altrimenti questo potrebbe essere uguale ad n e quindi l'algoritmo ha fallito e bisogna ripartire con un polinomio o un x0 diversi.
E' evidente che questo algoritmo funziona bene soprattutto per numeri con un fattore piccolo, perché è più probabile entrare in un ciclo.

Un'ultima osservazione che non dimostro in questo momento è che non serve calcolare la differenza di ogni coppia di termini della successione x0,x1,x2,x3..., ma basta considerare le coppie x(2n),xn

Pseudocodice
x=2 (la variabile x conterrà i valori xn)
y=2 (la variabile y conterrà i valori x(2n))
d=1 (fattore di n)
while d=1
x=g(x) mod n
y=g(g(y)) mod n
d=gcd(x-y,n)
if d=n return "fattore non trovato" else return d

Esempio con un numero in cui si trova un fattore
Usiamo n=8051, g(x)=x²+1 e come valore iniziale per la successione 2.

step	x	y	d
1	5	26	1
2	26	7474	1
3	677	871	97

Quindi 97 è un fattore di 8051


Riesci a mettere giù una spiegazione del genere del tuo algoritmo? Grazie in anticipo

 

[P_1_6]

Ok!
Mi prendo 24 ore per scegliere il metodo migliore e scriverlo più o meno in quella forma.
Ma mi dici se

[2^al numero delle cifre di sqrt(n)]
è un buon risultato ?

 

[Barbossa]

per fattorizzare un numero n impiego al massimo
[2^al numero delle cifre di sqrt(n)]
è un buon risultato ?

No, è all'incirca pari a n^0,5, come la divisione per tentativi.