complejidad del RSA
Páginas: 4 (937 palabras)
Publicado: 7 de julio de 2013
ANALISIS DEL RSA
Sea las operaciones para obtener la encriptación y des encriptación del modelo de cifrado Clave Publica - RSA
Posibles acciones que pueden hacer complejo almétodo RSA.
1.- BUSCAR PRIMOS “GRANDES” P, Q.
¿Es posible encontrar primos grandes de forma eficiente?
2.-CALCULAR N = P*Q Y Φ(N) = (P − 1)*(Q − 1).
¿Es realmente eficiente estasmultiplicaciones?
3.- BUSCAR E < Φ(N) TAL QUE MCD (E, Φ(N)) = 1. ES DECIR QUE N Y E SEAN CO-PRIMOS CALCULAR D ≡ E−1MOD Φ(N).
Algoritmo más usado es el de Euclides ¿ Cuán rápido es este algoritmo?4.- CIFRAR Y DESCIFRAR: CALCULAR ME MOD N Y C D MOD N.
¿Hay algoritmos eficientes de exponenciación modular?
Comencemos el análisis por las operaciones que deben ser computacionalmentesencillas.
SUMA – RESTA
Sean n = nk nk−1 . . . n1 y m = mℓ . . . m1, donde k ≥ ℓ y ni , mi ∈ {0, 1}.
Empezamos sumando los primeros bits por la derecha de n y m: n1 y m1,el resultado es c1 y siambos son 1, ponemos a2 = 1 (el bit de "acarreo", ósea lo que "nos llevamos").
Ak+1 Ak ··· Aℓ ··· A2
Nk ··· Nℓ ··· N2 N1
Mℓ ··· M2 M1
Ck+1 Ck··· Cℓ ··· C2 C1
En el paso i -ésimo debemos sumar Ci := ni + mi + ai mod 2 y además ai +1 = 1 si al menos dos de las entradas son 1.
Este proceso se sigue hasta que se acaba con elnúmero más largo.
El número de operaciones bit es:
• Min {k, ℓ} = ℓ operaciones de suma de los bits de n y m
• A lo sumo Max{k,ℓ}=k sumas con el acarreo.
Por lo tanto, si m ≤ n, la complejidades
O(k + ℓ) = O(2k) = O(k) = O(long n)
La complejidad de la resta también es O(long n).
MULTIPLICACIÓN – DIVISIÓN
El Algoritmos más eficiente para la multiplicación de numero grandes comoel que se requiere para la encriptación y des encriptación del modelo del RSA es el ALGORITMO DE KARATSUBA, el cual hace uso de la técnica DIVIDE Y VENCERAS.
Siendo n=a 2k/2 +b y...
Sea las operaciones para obtener la encriptación y des encriptación del modelo de cifrado Clave Publica - RSA
Posibles acciones que pueden hacer complejo almétodo RSA.
1.- BUSCAR PRIMOS “GRANDES” P, Q.
¿Es posible encontrar primos grandes de forma eficiente?
2.-CALCULAR N = P*Q Y Φ(N) = (P − 1)*(Q − 1).
¿Es realmente eficiente estasmultiplicaciones?
3.- BUSCAR E < Φ(N) TAL QUE MCD (E, Φ(N)) = 1. ES DECIR QUE N Y E SEAN CO-PRIMOS CALCULAR D ≡ E−1MOD Φ(N).
Algoritmo más usado es el de Euclides ¿ Cuán rápido es este algoritmo?4.- CIFRAR Y DESCIFRAR: CALCULAR ME MOD N Y C D MOD N.
¿Hay algoritmos eficientes de exponenciación modular?
Comencemos el análisis por las operaciones que deben ser computacionalmentesencillas.
SUMA – RESTA
Sean n = nk nk−1 . . . n1 y m = mℓ . . . m1, donde k ≥ ℓ y ni , mi ∈ {0, 1}.
Empezamos sumando los primeros bits por la derecha de n y m: n1 y m1,el resultado es c1 y siambos son 1, ponemos a2 = 1 (el bit de "acarreo", ósea lo que "nos llevamos").
Ak+1 Ak ··· Aℓ ··· A2
Nk ··· Nℓ ··· N2 N1
Mℓ ··· M2 M1
Ck+1 Ck··· Cℓ ··· C2 C1
En el paso i -ésimo debemos sumar Ci := ni + mi + ai mod 2 y además ai +1 = 1 si al menos dos de las entradas son 1.
Este proceso se sigue hasta que se acaba con elnúmero más largo.
El número de operaciones bit es:
• Min {k, ℓ} = ℓ operaciones de suma de los bits de n y m
• A lo sumo Max{k,ℓ}=k sumas con el acarreo.
Por lo tanto, si m ≤ n, la complejidades
O(k + ℓ) = O(2k) = O(k) = O(long n)
La complejidad de la resta también es O(long n).
MULTIPLICACIÓN – DIVISIÓN
El Algoritmos más eficiente para la multiplicación de numero grandes comoel que se requiere para la encriptación y des encriptación del modelo del RSA es el ALGORITMO DE KARATSUBA, el cual hace uso de la técnica DIVIDE Y VENCERAS.
Siendo n=a 2k/2 +b y...
Leer documento completo
Regístrate para leer el documento completo.