Domanda Come decodificare RSA?

[St3ve]

@St3ve mi dai un numero RSA di 20 cifre

Visto che sto thread ormai è arrivato a 10 pagine, quindi l'argomento ha suscitato un discreto interesse ho deciso di pubblicare un thread dove spiego il funzionamento di RSA. Vi invito a leggerlo: L'algoritmo RSA.
Tra le altre cose ci sono anche le informazioni necessarie per poter generare un numero n di quante cifre vuoi. In caso dovessi bloccarti da qualche parte, rispondimi al thread chiedendomi ulteriori spiegazioni ed esempi.

 

[P_1_6]

Test di primalità e fattorizzazione di Lepore

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-Cp)) , n] ad un certo punto le Cp cifre davanti scompaiono quindi scompariranno.
Quindi avremo un albero binario che avrà come radice p*(10^(Cn-Cp))-n=A
non sapendo se n>A
al primo livello lato destro avremo
da un lato p*(10^(Cn-Cp))-2n=B
e al primo livello lato sinistro
n-A=C
al secondo livello partendo da destra avremo
p*(10^(Cn-Cp))-3n=D
n-B
n-2A
A-C
e così via
Dal fatto che ogni risultato del algoritmo di Euclide è maggiore di 0 possiamo stabilire valori massimi e valori minimi per p e scegliere la strada giusta,
in più per scegliere la quantità di strada giusta si usa la tecnica della ricerca binaria


In questo esempio non percorrerò tutte le strade perchè faccio tutto a mano
ma è per spiegare il metodo

ESEMPIO

20737

massimo per p =sqrt(20737)=144,.....
minimo=1

Livello 0
p*10^3-20737=(p-21)*10^3+263 si testa 20737 modulo 21 == 0
siccome p-21>0 avremo
massimo = 144,...
minimo =21

Livello 1 lato sinisro
20737-[(p-21)*10^3+263]=(-p+41)*10^3+474 si testa 20737 modulo 41 == 0
siccome -p+41>0
massimo=41
minimo =21

Livello 2 lato sinistro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-(-p+41)*10^3+474=(2p-63)*10^3+789 63/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 2 lato destro figlio del 1 livello lato sinistro
20737-2*[(p-21)*10^3+263]=(-2p+62)*10^3+211 si testa 20737 modulo (62/2) == 0
massimo =31
minimo = 21

Livello 3 lato sinistro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
[(p-21)*10^3+263]-[(-2p+62)*10^3+211]=(3p-93)*10^3+52
massimo 31
minimo 31
[STRADA CHIUSA]

Livello 3 lato destro figlio del 2 livello lato destro figlio del 1 livello lato sinistro
20737-3*[(p-21)*10^3+263]=(-3p+82)*10+948 82/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

[qui vi farò vedere la ricerca binaria che non vi ho fatto vedere fino ad adesso per non confondervi]
[vi farò vedere che al 5 livello non è buona la strada mentre fino al 4 si]

Livello 4 lato destro figlio di tutti destri
p*10^3-4*20737=(p-83)*10^3+052 si testa 20737 modulo 83 == 0
massimo 144
minimo 83

Livello 5 lato destro figlio di tutti destri
p*10^3-5*20737=(p-104)+315 si testa 20737 modulo 104 == 0
massimo 144
minimo 104

Livello 6 lato sinistro figlio di tutti destri
20737-[(p-104)*10^3+315]=(-p+124)*10^3+422 si testa 20737 modulo 124 == 0
massimo =124
minimo =104

Livello 7 lato sinistro figlio del livello 6 lato sinistro figlio di tutti destri
(p-104)*10^3+315-[(-p+124)*10^3+422]=(2p-229)*10^3+893 229/2 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-2*[(p-104)*10^3+315]=(-2p+228)*10^3+107 si testa 20737 modulo 114 == 0
massimo =114
minimo =104

Livello 8 lato sinistro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
[(p-104)*10^3+315]-[(-2p+228)*10^3+107]=(3p-332)*10^3+208 332/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 8 lato destro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri
20737-3*[(p-104)*10^3+315]=(-3p+331)*10^3+792 331/3 [STRADA DA PERCORRERE CHE SI RIVELERA' CHIUSA]

Livello 5 lato sinistro

ecc.ecc

La strada giusta che troveremo è quetsa

20737-3*[(p-83)*10^3+052]=(-3p+269)*1000+581

(p-83)*10^3+052-2*[(-3p+269)*10^10^3+581]=(7p-623)+890 si testa 20737 modulo 623/7=89 ==0 e va bene

Perchè usare la ricerca binaria?
Perchè si potrebbe verificare questo

Esempio

45459487

45610000-45459487=150513

45459487/150513=302


Con i numeri piccoli non si vede la velocità del algoritmo

Che complessità ha questo algoritmo?

Ovviamente c'è da moltiplicare la complessità che mi direte per il numero di cifre di sqrt(n) in quanto non sappiamo il fattore di quante cifre è

P.s. Spero di non aver commesso errori

 

[Xenium]

Hai ancora omesso informazioni importanti come per esempio

(p-21)*10^3+263

Come facciamo a sapere che calcoli hai utilizzato per ottenere questa scomposizione? La stessa cosa vale per il resto.
Devi descrivere tutto nei minimi particolari altrimenti nessuno riuscirà a capire.

 

[P_1_6]

p*10^3-20737=(p-21)*10^3+263

questa è una sottrazione aritmetica che divide il numero in due parti
fino a (10^3)-1 e da 10^3 in poi

 

[Barbossa]

Questo è quello che ho capito:

Crei un albero binario in cui ogni nodo contiene un espressione algebrica in p. Il ramo base contiene sempre la seguente espressione:

p*10^(Cn-Cp)-n (n è noto e quindi espresso come numero)

Poi se un qualunque nodo contenente un espressione B allora i due nodi figli conterranno rispettivamente le due seguenti espressioni:

B-n
n-B

L'algoritmo alla fine si tratterebbe semplicemente di "provare" per ogni nodo se, ponendo B-n>=0 oppure B-n<=0, come si comporterebbe il fattore primo p e quindi eliminare le possibilità "contraddittorie".

Quindi riduci l'espressione di ogni nodo in una delle seguenti forme:

(a*p-b)*10^(Cn-Cp)+x
(-a*p+b)*10^(Cn-Cp)+x

con a, b, x numeri interi nonnegativi con x<10^(Cn-Cp), che d'altronde è unico, e le poni maggiore o uguale a zero, il che equivale rispettivamente a:

p>=b/a
p<=b/a

ottenendo quindi una limitazione su p. Queste limitazioni vengono "ereditate" dal nodo padre al nodo figlio, che aggiungono quindi altre limitazioni fino a quando queste limitazioni portano ad una stima di p, che viene verificata tramite una semplice divisione.

E' così che funziona oppure ho sbagliato a capire?

P.S. Tu poni all'inizio p=sqrt(n), e Cp il numero massimo di cifre di p, ma allora Cn=2Cp circa e quindi Cn-Cp=Cp circa

 

[P_1_6]

(a*p-b)*10^(Cn-Cp)+x
(-a*p+b)*10^(Cn-Cp)+x

Non ho ben capito questo
in più c'è la parte del logaritmo

 

[Barbossa]

E' un espressione letteraria, che rappresenta le espressioni da cui ricavi le limitazioni su p. Per esempio

(-3p+331)*10^3+792 (Livello 8 lato destro figlio del livello 7 lato destro figlio del livello 6 lato sinistro figlio di tutti destri)

è un espressione nella seconda forma con a=3, b=331, x=792

 

[P_1_6]

ok

in più c'è la parte del logaritmo

 

[Barbossa]

La parte del logaritmo non l'ho capita proprio, ma già così l'algoritmo avrebbe complessità pari a circa o(n^0,5), anche con la ricerca binaria

 

[P_1_6]

ma perchè non la sceglie la strada giusta nel albero e scarta le altre ?

EDIT:
L'ho risolto (forse) con un'altra pista che seguivo in una costante per logaritmo

 

[P_1_6]

Hey ragazzi un ultimo aiuto se possibile
come si risolve questa
[(11*C+21)/5]*4540513-C*10000000-3*4540513=(C*3621539) mod (4540513)
@St3ve @Barbossa @Xenium @_ _ e altri

 

[P_1_6]

Ho risolto in O(K)

 

[P_1_6]

@St3ve
Algoritmo di fattorizzazione

Sia N=p*q nella forma N=6*G+1 e p=6*a+1 e q=6b+1

Sia G=(N-1)/6
sia A un numero
Se G è dispari A è nella forma 12*k+2
Se G è pari A è nella forma 12*h+8
A è compreso nell'intervallo [8,G] //il valore G è da rivedere però non fa niente

Scelto un A in [8,G](supponiamo con G pari)
dobbiamo sottrarre a G la somma dei numeri A+(A-12)+(A-24)+(A-36)......
fino ad arrivare all'ultimo numero positivo
il numero di questi numeri sarà la nostra ipotetica a
(siccome ho trovato che A+6=p+q)
facciamo q=A+6-(6*a+1)

Se gli ipotetici p*q == N abbiamo trovato i valori p e q reali
Se gli ipotetici p*q < N dobbiamo far scendere il valore di A
Se gli ipotetici p*q > N dobbiamo far salire il valore di A

 

[_ _]

Parto con N=61*601=36661

calcolo G=6110

Parto con una A vicina a G/2, A=3056, faccio i conti e mi esce una a=254, quindi q=-1529, adesso qual è la p ipotetica e come decido se aumentare o diminuire A?

 

[P_1_6]

Scusami se non ti ho risposto prima

G-A=3054
G-A-(A-12)<0
a=1
q=A+6-(6*a+1)=3055
q*(6*a+1)=21385
21385<36661
A deve scendere

P.s. Comunque devo rivedere l'intervallo

 

[_ _]

Ok, A deve scendere, prendo A=1532

G-A=4578>0
G-A-(A-12)=3058>0
G-A-(A-12)-(A-24)=1550>0
G-A-(A-12)-(A-24)-(A-36)<0
dunque a=3
q=1519
q*(6*a+1)=28861<36661

quindi A deve scendere ancora.

Sei d'accordo con questi conti?

Potresti postare in maniera ordinata tutti passaggi che fai per fattorizzare 13*19 (prendo un numero piccolo così da avere pochi conti).

Anyway sta cosa mi convince un gran poco, scegliendo bene A posso far uscire più o meno qualsiasi cosa per a...

 

[P_1_6]

247
G=41
i possibili A sono 14 26 38
li faccio tutti e tre
per il 14
41-14-2
a=2
p=14+6-13=7
p*(6*a+1)=91<247

per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247

per il 38
41-38
a=1
p=38+6-7=37
p*(6*a+1)=259>247

EDIT:Non i preoccupare è tutto regolare
nel caso A=14 come noti c'è un anomalia che si risolve con la teoria
e
nel caso 38 devo ancora scegliere l'intervallo come ti ho già detto

mi spiego meglio vedi sul caso A=14

per il 26
41-26-14
a=2
p=26+6-13
p*(6*a+1)=247=247
vedi il 14 di 41-26-14
bene questo 14=6*n+8 dove n è la n di p^2+6*n*p=247
quindi
vedi
41-14-2
significherebbe 6*n+8=2 cioè n < 0 impossibile
quindi per quanto riguarda l'algoritmo
se G è dispari e si arriva a 2 dobbiamo far salire la A
se G è pari e si arriva a 8 dobbiamo controllare p^2=N e p non è intero far salire la A

per quanto riguarda l'intervallo [8,G] mi prendo un po di tempo per capire meglio

L'intervallo dovrebbe essere questo se non ho commesso errori
[ 8 , (7*(6*parteinterainferioredi((N/7)/6)+1)-1)/6 - (parteinterainferioredi((N/7)/6)-1)]
cioè per il 247 sarà [8,32]

 

[Barbossa]

A+(A-12)+(A-24)+ ... +(A - 12(a-1) ) = aA - 6 * a(a-1). Si vede facilmente che per a "grande" allora G - aA + 6 * a(a-1) è sempre positivo, quindi se il tuo metodo funziona allora l'espressione precedente si deve annullare da qualche parte. Quindi deve valere (A + 6)^2 > 24G. Ciò non basta, in quanto l'espressione cambia di segno per a intero, se vogliamo essere sicuri al 100% che l'algoritmo termini deve essere (A + 6)^2 > 24G + 36, e quindi A > 2 * (6G + 9) ^ 0,5 - 6 , in particolare per N=241 A deve essere maggiore di 25. Non so come ti sia trovato A uguale a 14, in quanto effettuando la somma all'infinito ottengo sempre un numero positivo se seguo la tua indicazione:

...
dobbiamo sottrarre a G la somma dei numeri A+(A-12)+(A-24)+(A-36)......
fino ad arrivare all'ultimo numero positivo
...

difatti:
41 - 14 = 27
41 -14 - (14 -12) = 25
41 - 14 - (14 - 12) - (14 -24) = 35
41 - 14 - (14 - 12) - (14 -24) - (14 - 36) = 57
...

Il problema risiede al significato che dai a "l'ultimo numero positivo". Quale tra le due quantità deve essere positiva?

1. G - A - (A-12) - (A-24) - ...
2. A + (A-12) + (A-24) + ...

 

[P_1_6]

Non riesco a trovare un limite superiore per A.

il limite superiore è (7*(6*parteinterainferioredi((N/7)/6)+1)-1)/6 - (parteinterainferioredi((N/7)/6)-1)

Il problema risiede al significato che dai a "l'ultimo numero positivo". Quale tra le due quantità deve essere positiva?

1. G - A - (A-12) - (A-24) - ...
2. A + (A-12) + (A-24) + ...

la 1.
ed i valori A-12*i devono essere tutti positivi

 

[Barbossa]

Il tuo algoritmo si può semplificare di molto:
Se B = p+q allora p = (B + (B^2 - 4N)^0,5)/2 e q = (B - (B^2 -4N)^0,5)/2, inoltre B = 6k oppure B = 6k - 4 oppure B = 6k - 2 con k che parte da 1. Facendo scorrere i possibili k si arriva a p e q.

 

[P_1_6]

ma quello che ho scritto io è in log

 

[_ _]

No.

Oppure provvedi una dimostrazione che:
1) l'algoritmo termina
2) l'algoritmo produce il risultato corretto
3) la complessità è logaritmica

fino ad allora stiamo discutendo di asserzioni non motivate e sulle quali, personalmente, non ritengo valga la pena di spendere tempo, può essere la mia formazione matematica ma senza una dimostrazione non c'è molto di cui parlare

 

[P_1_6]

cercherò di spiegarmi meglio (almeno ci provo)



Ennesimo test di fattorizzazione di Lepore in log
Sia n=p*q con N,p e q nella forma 6*h+1

Per capire ci scriviamo una tabella dove i valori cerchiati sono i valori G=(N-1)/6
di questa tabella

cioè questa

i numeri (che chiameremo A) di fianco a due cerchiati sono la differenza dei due numeri cerchiati
si deduce facilmente che n+(8+6*n)*a+6*a*(a-1)=G oppure G= n+((B-12)+(6*n+8))*a/2
dove B=A+12
dove a=(p-1)/6
e n è p^2+6*n*p=N


Osserviamo per G pari

B^2-12B-36*n^2+-4*N+2+34=0



sotituendo n=(G-6*a^2-2*a)/(6*a+1)

si avrà B^2-12B-36*[(G-6*a^2-2*a)/(6*a+1)]^2+-4*N+2+34=0

scegliendo un a calcoleremo B quindi A=B-12 e prendiamo il primo A nella forma 12*C+8

quindi ci andiamo a calcolare G-A-(A-12)-(A-24)-(A-36).....

fino ad arrivare all'ultimo sottrazione per cui l'espressione è maggiore di zero

se il numero delle sottrazioni è minore dell'a che abbiamo scelto allora dobbiamo scegliere una a superiore

se il numero delle sottrazioni è maggiore dell'a che abbiamo scelto allora dobbiamo scegliere una a inferiore

se il numero delle sottrazioni è uguale all'a che abbiamo scelto allora siamo giunti al termine


esempio N=56653

G=9442

B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=31 -> B=495,... -> A=476

G-476-464-452-440-428-416...........

hey meglio se lo facciamo così

{[(A-(a-1)*12)+(A)]*a/2+(A-(a-1)*12-8)/6}



{[(476-30*12)+(476)]*31/2+18}=9192

{[(476-31*12)+(476)]*32/2+16}=9294<G

la nostra a deve scendere

B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=29 ->B=504,... ->A=488

{[(488-28*12)+(488)]*29/2+24}=9304

{[(488-29*12)+(488)]*30/2+22}=9442==G (possiamo fermarci)

però vediamo il caso a=28

B^2-12*B-36*[(9442-6*a^2-2*a)/(6*a+1)]^2-4*56653+36=0 , a=28 ->B=510 -> A=500

{[(500-27*12)+(500)]*28/2+28}=9492>G

la nostra a deve salire

quindi dovremmo provare per 30 che è il nostro a

------------------------------------------------------------------------------------------
EDIT:
P.s. Quando dobbiamo valutare se scendere o salire la nostra a dobbiamo assicurarci che l'A che stiamo valutando non sia l'A giusta se fosse l'A giusta l'algoritmo termine

-----------------------------------------------------------------------------------------------
EDIT:
P.s.2. dimenticavo una cosa per me ovvia ma per chi legge no
se il valore (A-(a-1)*12)<0 significa che la a scelta deve salire

 

[Barbossa]

Come fai a dire che è in log n ? A me a prima vista sembra addirittura in n !

 

[P_1_6]

queste sottrazioni non si fanno effettivamente G-A-(A-12)-(A-24)-(A-36).....
ma si usa G-{[(A-(a-1)*12)+(A)]*a/2+(A-(a-1)*12-8)/6}
come mostrato nell'esempio