Domanda Come decodificare RSA?

nullptr · 5 Febbraio 2016

Esiste pure GNFS come algoritmo, che è estremamente complesso ma il migliore per quanti numeri al di sopra di 100, la notazione di questi algoritmi è espressa così:

$535cd3b29d7dabc6826e51f46f219dc1.png$

St3ve · 5 Febbraio 2016

_ _ ha detto:
@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

Si, lo so anche io che quell'algoritmo è una vaccata... o almeno lo è fino a prova contraria (ed è evidente che questa prova non ce l'averemo mai).

Gli ho dato il beneficio del dubbio, se mi riesce a spiegare in modo dettagliato cosa sta facendo e da dove tira fuori quei numeri e quelle equazioni (sono fisse? cambiano?) magari riusciamo a dare un senso a questo thread. Non gli chiedo di dimostrarmi niente e non c'è bisogno di far notare che "mancano del tutto le dimostrazioni", è una cosa lampante così come è evidente che non è in grado di fornircele (non lo sa nemmeno lui da dove vengono le equazioni che ha scritto). Però se ci da modo di capire cosa sta facendo abbiamo la possibilità di fare qualche ragionamento e magari si riesce anche a saltare a qualche conclusione: perché funziona, perché non funziona, è un algoritmo noto, ecc...

Comunque il numero che gli ho passato ha delle caratteristiche che lo rendono resistente ad alcuni degli attacchi più comuni: è il prodotto di due primi (i numeri che aveva postato lui non lo erano), è sufficientemente grande da non permettere la classica trial division, i suoi fattori primi sono distanti (non sono in un intorno piccolo di sqrt(n), quindi non è vantaggioso usare la trial division a partire dalla radice di n), non è vulnerabile alla fattorizzazione di Fermat, etc...
Insomma, non era un numero così tanto stupido: o ha imbrogliato e ha usato Wolfram per operazioni computazionalmente complesse (possibili solo grazie al fatto che il numero che gli ho passato non è sufficientemente grande) oppure ha fatto qualcosa di relativamente interessante. Finché non arrivano spiegazioni fatte come si deve, non si può far altro che dare per scontato che abbia "imbrogliato" (magari anche non volutamente, visto che ha già dimostrato di non aver chiaro come funziona la complessità computazionale).

nullptr · 5 Febbraio 2016

@St3ve hai letto quel link che ti ho quotato? È normale che non sa nemmeno lui cosa fa, è crosspostato in una decina di forum, inutile rispondergli.
Di norma nei forum il crossposting è vietato, non capisco nemmeno perchè questo topic è ancora aperto.
@murdercode @SpeedJack

St3ve · 6 Febbraio 2016

nullptr ha detto:
@St3ve hai letto quel link che ti ho quotato? È normale che non sa nemmeno lui cosa fa, è crosspostato in una decina di forum, inutile rispondergli.

Ho visto che ha fatto crossposting su più forum, ma mi sembra evidente (?) che sia farina del suo sacco. Dubito anche che si sia fatto influenzare da tecniche note, sinceramente sarei sorpreso se le conoscesse. Probabilmente ha postato un po' ovunque perché nessuno è riuscito a capire ciò che a scritto e di conseguenza nessuno è riuscito a convincerlo che non funziona (o che funziona ma non è efficiente).

A questo punto comunque è inutile andare avanti, io stesso avevo abbandonato la discussione, o ci fa vedere qualcosa di almeno vagamente simile ad un algoritmo (una spiegazione dettagliata) oppure stiamo solo sprecando tempo.

P_1_6 · 28 Febbraio 2016

Ciao a tutti vi mostro una bozza di come decodificare RSA in O(log)
X^2+6 n X=RSA
X^2+30 m X+ K X = RSA
K va da 0 a 29
Vi faccio vedere un esempio con numeri piccoli ad esempio 793
(*) X^2+6 n X=793
il valore di n varia da 0 a 132

simultaneamente controlliamo:

X^2+30 m X=793 --> m = n/5
X^2+30 m X+ X =793 --> m = (6n-1)/30
.....
......
......
(**)X^2+30 m X+ 18X =793 --> m=(n-3)/5
diamo ad n valore 66 (*) quindi m=62/5
e si ha X =18,91.....
lo sostituiamo in (**) e si ha 18,91^2+30*(62/5)*18,91+18*18,91=7732,48........
quindi diamo ad n valore 33 (*) quindi m=6
e si ha X =15,42....
lo sostituiamo in (**) e si ha 15,42^2+30*6*15,42+18*15,42=3290,93........
quindi diamo ad n valore 16 (*) quindi m=13/5
.........
........
quindi diamo ad n valore 8 (*) quindi m=1
e si ha X =13
lo sostituiamo in (**) e si ha 13^2+30*1*13+18*13=793

ma ora per curiosità vediamo se dessimo ad n valore inferiore a 8 ad esempio 4 quindi m= 1/5
e si ha X =18,61....
lo sostituiamo in (**) e si ha 18.61^2+30*1/5*18.61+18*18.61=792,97

Scusate se ho commesso degli errori
In questo periodo vado di fretta e non ho tanto tempo

Barbossa · 28 Febbraio 2016

P_1_6 ha detto:
simultaneamente controlliamo:

X^2+30 m X=793 --> m = n/5
X^2+30 m X+ X =793 --> m = (6n-1)/30
.....
......
......
(**)X^2+30 m X+ 18X =793 --> m=(n-3)/5

con un computer normale non puoi risolvere simultaneamente tutte queste equazioni: devi per forza analizzarne sequenzialmente (in un computer quantistico sarebbe possibile, ma già esiste l'algoritmo di Shor, dovresti conoscerlo).

Come sei inoltre arrivato ad affermare che l'algoritmo ha complessità O(log n)? A prima vista non sembra
L'esempio numerico non mi è d'aiuto per comprendere bene il tuo algoritmo, che d'altronde mi sembra una variazione di un altro ben noto attacco ad RSA:

Codice:

Sia RSA prodotto di due numeri primi.
per ogni n intero che và da 0 a (RSA-3)/2 inclusi determino
Y=RSA+n^2
Se Y è un quadrato perfetto, ovvero Y=y^2 con y intero, allora si ha
RSA=(y-n)(y+n)
con y-n e y+n diversi da 1

e tale algoritmo non è assolutamente polinomiale, ma permette di fattorizzare i numeri che hanno fattori primi relativamente vicini.

Ti consiglio inoltre di dedicarti allo studio degli algoritmi e imparare almeno uno pseudocodice (esistono molti dialetti) come questo http://home.deib.polimi.it/zaccaria/data/lectures/infob/e_02_pseudocodice.pdf

ecco un esempio di pseudocodice

Codice:

var RSA : intero;//definisco le variabili
var n : intero;
var Y : intero;
Leggi(RSA);
n <- 0;//mette 0 nella variabile n
Y <- RSA + n^2;
Finché(Y non quadrato perfetto){
n <- n+1;
Y <-RSA + n^2;
}
Y <- RadiceQuadrata(Y);
Stampa(Y-n);
Stampa(Y+n);

P_1_6 · 28 Febbraio 2016

Barbossa ha detto:
con un computer normale non puoi risolvere simultaneamente tutte queste equazioni: devi per forza analizzarne sequenzialmente (in un computer quantistico sarebbe possibile, ma già esiste l'algoritmo di Shor, dovresti conoscerlo).

Come sei inoltre arrivato ad affermare che l'algoritmo ha complessità O(log n)?

Per simultaneamente intendo ad ogni ciclo le 30 equazioni una per volta.
quindi una costante (30) per log
Il tutto se l'algoritmo funziona.

P_1_6 · 28 Febbraio 2016

Ho sbagliato.
Ci riprovo quando ho più tempo.

P_1_6 · 5 Marzo 2016

Ho scritto a Big G per una borsa di studio da 7000 euro per potermi laureare in modo da sviluppare autonomamente le mie ipotesi su
P->NP.
Ho capito che chiedere aiuto agli altri per la maggior parte delle volte ricevi solo fregature.
Speriamo bene.

P_1_6 · 15 Marzo 2016

@Barbossa @St3ve
ho fattorizzato il numero che mi ha dato st3v3 140089267639071478002348819284711337427
in 113955711997959151 cicli
lo so non è un buon risultato
ma volevo chiedervi in quanti cicli lo fattorizza l'algoritmo più veloce esistente per farmi un idea di quanto sono lontano.

Barbossa · 15 Marzo 2016

P_1_6 ha detto:
ho fattorizzato il numero che mi ha dato st3v3 140089267639071478002348819284711337427
in 113955711997959151 cicli
lo so non è un buon risultato
ma volevo chiedervi in quanti cicli lo fattorizza l'algoritmo più veloce esistente per farmi un idea di quanto sono lontano.

Non si può giudicare la velocità di un algoritmo solo dal numero di cicli effettuati, in quanto dipende anche dalla struttura interna del ciclo. Inoltre una classe non irrilevante di algoritmi di fattorizzazione sono probabilistici: hanno il difetto di non dare sempre la risposta corretta ma sono in genere più veloci dei loro compagni deterministici

P.S. L'algoritmo tuttora più veloce molto probabilmente se lo tiene stretto stretto l'NSA o qualche reparto governativo russo. Prova a chiedere a loro...

P_1_6 · 17 Marzo 2016

Penso che il gioco sia finito devo iniziare a studiare il problema del commesso viaggiatore.
Per chi ancora non lo avesse capito come si decodifica un RSA ve lo spiego in due parole MCD EUCLIDE.
Vi posto un breve esempio 247
A=192-2a^2-a
B=55+2a^2+a
G=41-a
G-(B-G)=6a+1
Ovviamente non è sempre la stessa formula.

Barbossa · 17 Marzo 2016

P_1_6 ha detto:
Ovviamente non è sempre la stessa formula.

non necessita di commenti

P_1_6 · 26 Marzo 2016

Il mio primo algoritmo funzionante per la decodifica di un RSA=p*q
dove RSA,p,q sono nella forma 6h+1 (in realtà fattorizza anche Rsa=6h+5 ma non è proprio sempre efficiente ma è facilmente ampliabile) e tenendo conto che in un RSA di solito p/q<2.

volevo chiedervi qual'è la complessità computazionale ?

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int fattorizza_RSA_sei_h_1_sei_h_1(int *cicli,int RSA);

int main(){
    int RSA=0;

    int cicli=0;
    int jolly;

    int fattore=1;

    scanf("%d",&RSA);
    printf("\n%d\n",RSA);
    jolly=(sqrt(RSA/2))/6;

        fattore=fattorizza_RSA_sei_h_1_sei_h_1(&cicli,RSA);
    printf("\n%d è diviso da %d in %d cicli\n",RSA,fattore, cicli);
}


fattorizza_RSA_sei_h_1_sei_h_1(int *cicli,int RSA){
        int jolly=(sqrt(RSA/2))/6;
        int i=0;
        int G=(RSA-1)/6;
        int A=(G-jolly)/(6*jolly+1);
        int B=(G-A)/(6*A+1);
        int C=2;
            while((6*B+1)*(RSA/(6*B+1))!=RSA && (C*(RSA/C)!=RSA && C!=1)){
                B++;
                (*cicli)++;
                C=(-6*i+sqrt(36*i*i+4*RSA))/2;
                i++;
            }
        if(C*(RSA/C)==RSA){return C;}
        return (6*B+1);
}

P_1_6 · 27 Marzo 2016

Provo a dare una mezza soluzione:
Se RSA=p*q e p=6a+1 e q=6b+1 allora
una parte dell'algoritmo avrà la complessità b-a questa C=(-6*i+sqrt(36*i*i+4*RSA))/2;
l'altra parte b-(((RSA)/(sqrt((RSA)/2)/6)-1)/6)

Però non capisco quando si incrociano cioè qual'è la complessità del algoritmo con input RSA=p*q dove 2>q/p>1

P_1_6 · 27 Marzo 2016

Per renderlo più efficiente

sostituire

Codice:

int jolly=(sqrt(RSA/2))/6;

con

Codice:

int jolly=(sqrt(2*RSA))/6;

P_1_6 · 28 Marzo 2016

Qualche parere

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*rossella è ottimizzato per fattorizzare numeri RSA =p * q dove RSA,p e q sono nella forma 6*h+1*/
/*Autore Alberico Lepore*/



int rossella(long long int *cicli,long long int RSA);

int main(){
    long long int RSA=0;

    long long int cicli=0;
    long long int jolly;

    long long int fattore=1;

    scanf("%lli",&RSA);
    printf("\n%lli\n",RSA);
    jolly=(sqrt(RSA/2))/6;

        fattore=rossella(&cicli,RSA);
    printf("\n%lli è diviso da %lli in %lli cicli\n",RSA,fattore, cicli);
}


rossella(long long int *cicli,long long int RSA){

        long long int jolly[99];
        int j=0;
        long long int i=0;
        long long int G=(RSA-1)/6;
        long long int A[99];
        long long int B[99];
        long long int C=2;
        long long int D[99];
        long long int maggiore=0;
        long long int E=0;

        for(j=0;j<100;j++){
            jolly[j]=(j+1);

        }

        for(j=0;j<100;j++){
            A[j]=(G-jolly[j])/(6*jolly[j]+1);
            B[j]=(G-A[j])/(6*A[j]+1);

        }

        j=0;
        while(j<100){
            while(A[j]>B[j]){
                D[j]=B[j];
                A[j]=(G-6*B[j]-1)/(6*(6*B[j]+1));
                B[j]=(G-A[j])/(6*A[j]+1);
                (*cicli)++;
            }
            j++;
        }



        for (j=0;j<100;j++){
            if(D[j] > maggiore){
                maggiore=D[j];

            }
        }

        E=(G-maggiore)/(6*maggiore+1);

        if(E>((sqrt(RSA))-1)/6){
            while((RSA/(6*E+1))*(6*E+1)!=RSA){
                E--;
                (*cicli)++;
            }
        }else{
            for(j=7;j<=sqrt(RSA);j++){
                    printf("\nj=%d\n",j);
                if(RSA%j==0){
                    printf("\nl'algoritmo rossella è ottimizzata per RSA reali anche se implementato con long long int\n");
                    return j;
                }
            }
        }
            return (6*E+1);

}

P_1_6 · 30 Marzo 2016

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*rossella è ottimizzato per fattorizzare numeri RSA =p * q dove RSA,p e q sono nella forma 6*h+1*/
/*Autore Alberico Lepore*/

int rossella(long long int *cicli,long long int RSA);

int main(){
    long long int RSA=0;

    long long int cicli=0;
    long long int jolly;

    long long int fattore=1;

    scanf("%lli",&RSA);
    printf("\n%lli\n",RSA);
    jolly=(sqrt(RSA/2))/6;

        fattore=rossella(&cicli,RSA);
    printf("\n%lli è diviso da %lli in %lli cicli\n",RSA,fattore, cicli);
}

rossella(long long int *cicli,long long int RSA){

        long long int jolly[99];
        int j=0;
        long long int i=0;
        long long int G=(RSA-1)/6;
        long long int A[99];
        long long int B[99];
        long long int C=2;
        long long int D[99];
        long long int maggiore=0;
        long long int E=0;

        for(j=0;j<100;j++){
            jolly[j]=(j+1);

        }

        for(j=0;j<100;j++){
            A[j]=(G-jolly[j])/(6*jolly[j]+1);
            B[j]=(G-A[j])/(6*A[j]+1);

        }

        j=0;
        while(j<100){
            while(A[j]>B[j]){
                D[j]=B[j];
                A[j]=(G-6*B[j]-1)/(6*(6*B[j]+1));
                B[j]=(G-A[j])/(6*A[j]+1);
                (*cicli)++;
            }
            j++;
        }

        for (j=0;j<100;j++){
            if(D[j] > maggiore){
                maggiore=D[j];

            }
        }


        E=maggiore;

        if(E<((sqrt(RSA))-1)/6){
            while((RSA/(6*E+1))*(6*E+1)!=RSA){
                E--;
                (*cicli)++;
            }
        }else{
            for(j=7;j<=sqrt(RSA);j++){
                    printf("\nj=%d\n",j);
                if(RSA%j==0){
                    printf("\nl'algoritmo rossella è ottimizzata per RSA reali anche se implementato con long long int\n");
                    return j;
                }
            }
        }
            return (6*E+1);

}

P_1_6 · 30 Marzo 2016

Another break in the RSA
http://www.albericolepore.org/al-test-di-fattorizzazione-di-lepore/

P_1_6 · 1 Aprile 2016

vi allego due sorgenti in C per la fattorizzazione di un numero RSA=p*q ove RSA,p e q sono nella forma 6h+1 ma si può generalizzare a tutti i numeri e 1< q/p<2 ma li ho scritti in modo tale che fattorizzino per qualsiasi q/p.

Al si basa sapendo che G=(RSA-1)/6 e che se p=6a+1 e q=6b+1 allora si ha (G-a)/(6a+1)=b e quindi (G-b)/(6b+1)=a quindi si G=6ab+b+a quindi [G-(a+b)]/6=ab

invece Al_rossella

rossella trova il range

Al lo sfrutta e fattorizza

Speranzoso in una Vostra risposta cordialmente Vi saluto.

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
long long int al(long long int RSA,long long *cicli);

int main(){
long long int RSA=1;
long long int fattore=1;
long long int cicli=0;

printf("Inserisci il primo numero\n");
    scanf("%lli",&RSA);
    clock_t start = clock();
    fattore=al(RSA,&cicli);
    clock_t end = clock();
    printf("Tempo di esecuzione =  %f secondi \n", ((double)(end - start)) / CLOCKS_PER_SEC);
    printf("\n%lli e' diviso da %lli calcolato in %lli cicli\n",RSA,fattore,cicli);
}


long long int al(long long int RSA,long long *cicli){

    long long int minimo_somma=2*(sqrt(RSA)-1)/6;
    long long int a=1;
    long long int G=(RSA-1)/6;
    long long int resto=G%6;
    long long int prodotto;
    minimo_somma=minimo_somma - (minimo_somma%6);


    while((6*a+1)*(RSA/(6*a+1))!=RSA || 6*a+1==1){
        prodotto=(G-(minimo_somma+resto))/6;
        a=(minimo_somma+resto + sqrt((minimo_somma+resto)*(minimo_somma+resto)-4*prodotto))/2;
        minimo_somma=minimo_somma+6;
        (*cicli)++;
    }

return (6*a+1);
}

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
/*Al + rossella è un algoritmo di fattorizzazione generico ottimizzato serve per fattorizzare numeri NR =p * q dove NR,p e q sono nella forma 6*h+1*/
/*Autore Alberico Lepore*/

long long int Al(long long int RSA,long long *cicli);
long long int rossella(long long int *cicli,long long int RSA);


int main(){
long long int RSA=1;
long long int fattore=1;
long long int cicli=0;

printf("Inserisci il primo numero\n");
    scanf("%lli",&RSA);
    clock_t start = clock();
    fattore=Al(RSA,&cicli);
    clock_t end = clock();
    printf("Tempo di esecuzione =  %f secondi \n", ((double)(end - start)) / CLOCKS_PER_SEC);
    printf("\n%lli e' diviso da %lli calcolato in %lli cicli\n",RSA,fattore,cicli);

}


long long int Al(long long int RSA,long long *cicli){

    long long int minimo_somma=rossella(cicli,RSA);
    long long int a=1;
    long long int G=(RSA-1)/6;
    long long int resto=G%6;
    long long int prodotto;
    long long int i=1;
    long long int y=2;
    minimo_somma=(minimo_somma + (RSA/minimo_somma)-1)/6;
    minimo_somma=minimo_somma - (minimo_somma%6);


    while((6*a+1)*(RSA/(6*a+1))!=RSA || 6*a+1==1){
        prodotto=(G-(minimo_somma+resto))/6;
        a=(minimo_somma+resto + sqrt((minimo_somma+resto)*(minimo_somma+resto)-4*prodotto))/2;
        minimo_somma=minimo_somma+6;
        (*cicli)++;
        y=RSA/(6*i+1);
        if((6*i+1)*y==RSA){
            break;
        }
        i++;
    }
    if((6*i+1)*(RSA/(6*i+1))==RSA){
        return (6*i+1);
    }
    return (6*a+1);
}


long long rossella(long long int *cicli,long long int RSA){

        long long int jolly[99];
        int j=0;
        long long int i=0;
        long long int G=(RSA-1)/6;
        long long int A[99];
        long long int B[99];
        long long int C=2;
        long long int D[99];
        long long int maggiore=0;
        long long int E=0;

        for(j=0;j<100;j++){
            jolly[j]=(j+1);

        }

        for(j=0;j<100;j++){
            A[j]=(G-jolly[j])/(6*jolly[j]+1);
            B[j]=(G-A[j])/(6*A[j]+1);

        }

        j=0;
        while(j<100){
            while(A[j]>B[j]){
                D[j]=B[j];
                A[j]=(G-6*B[j]-1)/(6*(6*B[j]+1)+1);
                B[j]=(G-A[j])/(6*A[j]+1);
                (*cicli)++;
            }
            j++;
        }

        for (j=0;j<100;j++){
            if(D[j] > maggiore){
                maggiore=D[j];

            }
        }



            return (6*maggiore+1);

}

Qual'è la complessità computazionale dei due algoritmi?

Overflow404 · 1 Aprile 2016

Bhè per il primo stai in O(n), per quanto riguarda il secondo Teta(n^2).

P_1_6 · 1 Aprile 2016

Io intendo la complessità computazionale per numeri RSA con 1<q/p<2
il secondo in termini di cicli è molto inferiore al primo ma ogni ciclo impiega un po di tempo in più.

Overflow404 · 1 Aprile 2016

Non importa quanto piccoli/grandi siano i tuoi numeri p e q o in alternativa il loro rapporto.
La dichiarazione di variabili di qualsiasi dimensione ha sempre costo costante nel modello RAM, ovvero Teta(1), per cui la complessità di tempo di cui parli è quella citata da me precedentemente. Il discorso cambia un'po se parli di complessità di spazio.

P_1_6 · 1 Aprile 2016

prova numeri a 19 cifre dove q/p<2 e fammi vedere questo n^2 con Al_rossella

Overflow404 · 1 Aprile 2016

Ciao, spero di esser stato chiaro, con questa analisi più dettagliata.

Domanda Come decodificare RSA?

DISCUSSIONI SIMILI