Domanda Come decodificare RSA?

[Barbossa]

Il problema è la scelta dell'a che, tra prove ed errori, ha una complessità media di n

 

[P_1_6]

una volta scelta la a
controlli questo
p^2+6*[(9442-6*a^2-2*a)/(6*a+1)]*p=N
controlli questo
[(A-(a-1)*12)+(A)]<0
e controlli questo
{[(A-(a-1)*12)+(A)]*a/2+(A-(a-1)*12-8)/6} se è minore o maggiore di G
e basta

 

[Barbossa]

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

Quante scelte della a dobbiamo effettuare prima che l'algoritmo termini?

 

[P_1_6]

Scusami @Barbossa se non ho risposto prima

fattorizzazione di N=p*q dove N,p,q sono nella forma 6*h+1

con G pari


G=[2*(A+6a-5)-24*(a-2)]*(a-1)/2+[7*(6*(a-(G-6*a^2-2*a)/(6*a+1))+1)-1]/6


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


G=(N-1)/6


a=(p-1)/6


-----------------------------------------------------------
EDIT

quando non funziona quello di sopra provare
G=[2*(A+6a-5)-24*(a-(G-6*a^2-2*a)/(6*a+1)-2)]*(a-(G-6*a^2-2*a)/(6*a+1)-2)+{{[6*(a-(G-6*a^2-2*a)/(6*a+1))+1]^2}-1}/6
(A+12)^2-12*(A+12)-36*[(G-6*a^2-2*a)/(6*a+1)]^2-4*N+2+34=0

 

[P_1_6]

Fattorizzazione in tempi logaritmici

N numero prodotto di due primi che siano nella forma 6*h+1 con h naturale
che chiameremo p e q cioè p*q=N
Ogni numro N di questo tipo si può scrivere nella forma 6*H+1
con H naturale
Sia G=(N-1)/6 e G pari
allora G si scrive in questa forma [ora non mi so spiegare bene quindi ti mostrerò mezzo esempio e mezza teoria]
Se p=6*a+1=31 ad esempio
x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=G
dove 30=6*a e x-3*n=6*a+1=p dove n =[(x-(6*a+1-6))+(x-(6*a+1))-8]/6=[(x-24)+(x-30)-8]/6

quindi mi sembra se non sbaglio qualcosa che dovrebbe essere questa

x+2*(a-1)*x-(6*(a-1)*a)+(x-6*a)+(x-(6*a+1))/3=G [non ne sono sicuro ma questo non è importante perchè con un po di attenzione si trova]

quindi per N=1705 ad esempio si avrà
43+2*37+2*31+2*25+2*19+13+4=284

Si deve notare una cosa che

se scegliamo un numero iniziale maggiore di 43 la potenziale a è minore della vera a se non si vuole superare il 284
se scegliamo un numero iniziale minore di 43 la potenziale a è maggiore della vera a se non si vuole superare il 284

Scegliendo 6*a=30 si ha p=31 quindi a=5

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+(x-30)+[(x-24)+(x-30)-8]/6=284

quindi x=43 e n=4 43-3*4=31


Scegliendo 6*a=24 si ha p=25 quindi a=4

x+2*(x-6)+2*(x-12)+2*(x-18)+(x-24)+[(x-18)+(x-24)-8]/6=284

quindi x=233/5=46,6 e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 43

43+2*37+2*31+2*25+19+6= 254 quindi per arrivare a 284 dovrebbe crescere la a


Scegliendo 6*a=18 si ha p=19 quindi a=3

x+2*(x-6)+2*(x-12)+(x-18)+[(x-12)+(x-18)-8]/6=284

quindi x=1033/19=54,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 49

49+2*43+2*37+31+10= 250 quindi per arrivare a 284 dovrebbe crescere la a


(questo caso lo mostro per completezza in quanto 43 > sqrt(1705) )
Scegliendo 6*a=42

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+2*(x-36)+(x-42)+[(x-36)+(x-42)-8]/6=284

quindi x=1777/43=41,... quindi 37 segue n negativa quindi la a deve diminuire


Scegliendo 6*a=36 si ha p=37 quindi a=6

x+2*(x-6)+2*(x-12)+2*(x-18)+2*(x-24)+2*(x-30)+(x-36)+[(x-30)+(x-36)-8]/6=284

quindi x=1537/37=41,... e scegliamo il primo numero valido più piccolo in modo da far venire la somma minore di 284 e cioè 37

37+2*31+2*25+2*19+2*13+2*7+1+0=228 quindi per arrivare a 284 dovrebbe crescere la a ma la a non può crescere quindi di conseguenza deve crescere il 37 ma per far crescere il 37 la a deve diminuire


potrebbe verificarsi altri due casi

guardiamo questa sequenza senza pensare più a quello di prima

43+2*37+2*31+2*25+19+6=254

se il 43 è più basso del valore reale e la potenziale a non è maggiore della vera a quindi a deve salire

e poi c'è questo caso qui

se il 43 è più basso del valore reale e la potenziale a è maggiore della vera a quindi a DOVREBBE SCENDERE ma non ho capito perchè?

P.s.
Ho capito quel caso non può accadere si capisce bene dal disegno che aumentando a la somma supererebbe G


Speranzoso in un vostro riscontro vi saluto

 

[St3ve]

N numero prodotto di due primi che siano nella forma 6*h+1 con h naturale
che chiameremo p e q cioè p*q=N

Se p=6*h+1 allora p-1=6*h è un numero smooth (2 e 3 sono alcuni dei suoi fattori), di conseguenza puoi fattorizzare efficientemente con l'algoritmo p-1. Sta roba qui la trovi scritta nella mia guida in rilievo su RSA.

Quindi fai già un'assunzione sbagliata in partenza, visto che i valori scelti per RSA tengono ovviamente in considerazione ogni tipo di vulnerabilità conosciuta. Quello che puoi assumere è p-1=h_1*h_2*...*h_k con h_i numero primo grande per ogni indice i.

 

[P_1_6]

Algoritmo per la fattorizzazione in tempi logaritmici

Sia N=p*q dove N=6*G+1 e p=6*a+1 e q=6*b+1 con G pari
a,b,G numeri naturali

1<F<G e F numero naturale

Calcolare:
a=[6*F-sqrt(6)*sqrt(6*F^2+2*F-G)]/6

Se [(12*F-4)-(a-1)*12-8]/6 == (284-6*a^2-2*a)/(6*a+1) allora a è la nostra a


Se [(12*F-4)-(a-1)*12-8]/6 < (284-6*a^2-2*a)/(6*a+1) allora F deve scendere

altrimenti F deve salire

P.s. L'ho scritto solo nella forma [ N=p*q dove N=6*G+1 e p=6*a+1 e q=6*b+1 con G pari] ma tutti gli altri casi sono simili

 

[P_1_6]

Avrei bisogno di un piccolo aiuto
Ho scoperto che per fattorizzare un numero N=p*q tutti e tre nella forma 6*H+1
basta risolvere x^2+9*y^2=4*N^2
e fare euclide di y ed N
ciò non è sempre vero però si può ricondurre ad un caso vero
esempio
7471=31*241
x^2+9*y^2=223263364
ove y=2480
Quindi Euclide (7471,2480)=31
Questa x^2+9*y^2=223263364 l'ho scritta in questa forma perchè ho pensato di risolverla come diofantea pitagorica (ma non so come si faccia)
invece andremo ad agire sul secondo fattore ovvero
x^2-9*y^2=223263364
y=77120
quindi MCD(77120,7471)=241
ed ho scoperto che in x^2+9*y^2=4*N^2
x^2=A*B -> A+B=4*N
cioè nell'esempio
x^2+9*y^2=223263364
x^2=A*B ->A+B=29884

 

[P_1_6]

Si può ricondurre tutto all'Equazione di Pell generalizzata
z^2-6*(p)^2=(4*N)^2
cioè nel nostro esempio
z^2-6*(p)^2=893053456
dove per esempio per p=2232
Euclide(7471,2232)=31

-------------------------------------------------------------------------------------------------------------------------------------
EDIT:

Equivalentemente
anche ad N=p*q con N nella forma 6*H+1 e p e q nella forma 6*h+5
si può associare l'equazione di Pell generalizzata
z^2-6*(p)^2=(4*N)^2

esempio 19*41=779
z^2-6*(p)^2=9709456
per p=18368 si ha
MCD(18368,779)=41

-----------------------------------------------------------------------------------------------------------------------
EDIT:

anche ad N=p*q con N e p nella forma 6*H+5 e q nella forma 6*h+1
e ad N=p*q con N e q nella forma 6*H+5 e p nella forma 6*h+1
si può associare l'equazione di Pell generalizzata
z^2-6*(p)^2=(4*N)^2

 

[P_1_6]

Non pensate che non sia deterministico

Non so quale sia la sua complessità computazionale a me sembra O(2) però non ne ho la certezza in quanto non essendo un matematico e non sapendo risolvere l'equazione di Pell generalizzata (che nessuno mi spiega) non posso continuare

vi faccio un esempio

1147=31*37

x^2-6*y^2=(4*N)^2

x^2-6*y^2=(4*1147)^2

ha soluzioni divisibili per 1147

ma dall'equazione generatrice mi calcolo una nuova equazione di Pell generalizzata ovvero

x^2-3*y^2=4*N^2

x^2-3*y^2=5262436

per y=1736

MCD(1736,1147)=31

 

[P_1_6]

Ragazzi se dalla generatrice mi scrivo l'equazione
nella forma x^2+3*y^2=4*N^2

posso utilizzare l'algoritmo di Cornacchia?

https://en.wikipedia.org/wiki/Cornacchia's_algorithm

Quali sono i pro e i contro?

Ad esempio per 7471
x^2+3*y^2=223263364

 

[P_1_6]

@St3ve riguardo l'equazione di Pell generalizzata mi servirebbe un aiuto (se puoi)

volendo risolvere
x^2-6*y^2=893053456
ho capito come si trova
sqrt(6) in frazione continua: [2,(2, 4)]
e come si trovano i convergenti per trovare la soluzione unitaria
2/1
5/2 => 5^2-6*2^2 = 1
22/9
49/20 => 49^2-6*20^2 = 1
218/89
485/198 => 485^2 - 6*198^2 = 1

Quindi (5,2) ; (49,20) ; (485,198) ecc.ecc. sono tutte soluzioni unitarie

però non ho capito
come faccio ad arrivare alla soluzione
x=30380
y=2232

 

[P_1_6]

Hey
per piacere mi date qualche feedback
Lepore Factorization O(log)
https://www.academia.edu/34557040/Lepore_Factorization_O_log_

 

[P_1_6]

@St3ve e altri per piacere mi dareste un feedback su questo
https://www.academia.edu/34573855/Fattorizzazione_di_Lepore

 

[P_1_6]

Qualcuno mi aiuterebbe a capire se ho definito bene la complessità computazionale
primality e factorization 2*log_3(N)
https://www.academia.edu/34590872/Test_di_primalità_e_Fattorizzazione_di_Lepore_2_log_3_N_

 

[P_1_6]

Qualcuno mi aiuterebbe a capire se ho definito bene la complessità computazionale
primality e factorization 2*log_3(N)
https://www.academia.edu/34590872/Test_di_primalità_e_Fattorizzazione_di_Lepore_2_log_3_N_

 

[P_1_6]

Questo dovrebbe essere 9 log_3(N)
https://www.academia.edu/34595630/6_Fattorizzazione_di_Lepore
ciao

 

[P_1_6]

io non mollo
7° fattorizzazione di Lepore
https://www.academia.edu/34616775/7_Fattorizzazione_di_Lepore

 

[P_1_6]

Ciao quì di seguito c'è la trasformazione del problema della fattorizzazione in un gioco
https://www.academia.edu/34655158/Trasformazione_del_problema_della_fattorizzazione_in_un_gioco

 

[P_1_6]

qualcuno ha trovato una qualsiasi equazione di una qualsiasi di quelle equazioni?
per piacere rispondete

 

[P_1_6]

io c'ho riprovato O([log_9(N)]^3)
https://www.academia.edu/35412746/Test_di_primalità_e_fattorizzazione_di_Lepore_in_O_log_9_N_3_
che ne pensate?