Encriptación asimétrica con RSA

Codificar un mensaje de texto en números

Antes de poder aplicar el método RSA, tenemos que codificar la información que queremos mandar como una secuencia de números enteros. El código siguiente hace dos cosas:

{{{id=1| #nuestro alfabeto son el espacio en blanco y las mayusculas sin acentos alfabeto=' ABCDEFGHIJKLMNOPQRSTUVWXYZ' L=len(alfabeto) def codifica_letra(letra): return alfabeto.index(letra) def bloque2numero(bloque): b=len(bloque) return sum(n*L^(b-1-i) for i,n in enumerate(bloque)) def codifica_mensaje(mensaje,b): '''Convierte una secuencia de letras en una secuencia de numeros Las letras validas son las mayusculas y el espacio en blanco El espacio en blanco se codifica como 0, las letras a partir de 1 Las letras se agrupan en bloques de b letras ''' #cambiamos las letras por sus codigos letras = [codifica_letra(letra) for letra in mensaje] #rellenamos con espacios en blanco al final letras = letras + [0]*(b-len(letras)%b) n = len(letras) #Agrupamos en bloques bloques = [letras[i:i+b] for i in range(0,n,b)] #cambiamos cada bloque por un numero codigo = [bloque2numero(bloque) for bloque in bloques] return codigo /// }}} {{{id=12| mensaje='CITA EN EL PATIO' letras = [codifica_letra(letra) for letra in mensaje] print letras /// [3, 9, 20, 1, 0, 5, 14, 0, 5, 12, 0, 16, 1, 20, 9, 15] }}} {{{id=14| #Agrupamos las letras b=3 n = len(letras) bloques = [letras[i:i+b] for i in range(0,n,b)] print bloques /// [[3, 9, 20], [1, 0, 5], [14, 0, 5], [12, 0, 16], [1, 20, 9], [15]] }}} {{{id=13| codigo = [bloque2numero(bloque) for bloque in bloques] print codigo /// [2450, 734, 10211, 8764, 1278, 15] }}} {{{id=2| mensaje='CITA EN EL PATIO' codifica_mensaje(mensaje,2) /// [90, 541, 5, 378, 147, 16, 47, 258, 0] }}}

Las operaciones inversas son similares, ahora tenemos que recuperar el texto a partir de la secuencia de números.

{{{id=4| def decodifica_letra(n): return alfabeto[n] def numero2bloque(n,b): bloque=[] for i in range(b): bloque.append(n%L) n=n//L bloque.reverse() return bloque def decodifica_mensaje(secuencia,b): '''Convierte una secuencia de numeros en una secuencia de letras ''' bloques=[numero2bloque(numero,b) for numero in secuencia] mensaje=''.join(''.join(decodifica_letra(letra) for letra in bloque) for bloque in bloques) return mensaje /// }}} {{{id=5| decodifica_mensaje([90, 541, 5, 378, 147, 16, 47, 258],2) /// 'CITA EN EL PATIO' }}}

Encriptación RSA

En el sistema RSA, un número menor que N (que puede representar texto, o cualquier otra cosa), se encripta elevándolo a un exponente módulo N. La operación de desencriptado también usa la misma operación, pero con un exponente distinto. Aunque podríamos usar la misma función para las tareas de encriptar y desencriptar, preferimos usar dos funciones distintas por claridad.

Encriptado

Cada número de la secuencia se eleva al exponente e módulo N. Por tanto, para encriptar se necesita el par formado por N y e, que llamaremos la clave pública.

$$x\rightarrow x^e (mod\; N)$$

Desencriptado

Cada número de la secuencia se eleva al exponente d módulo N. Para desencriptar se necesita el par formado por N y d, que llamaremos la clave privada.

$$y\rightarrow y^d (mod\; N)$$

{{{id=7| def encripta_RSA(lista,N,e): '''Encripta una secuencia de numeros siguiendo el metodo RSA''' return [power_mod(numero,e,N) for numero in lista] def desencripta_RSA(lista,N,d): '''Desencripta una secuencia de numeros siguiendo el metodo RSA''' return [power_mod(numero,d,N) for numero in lista] /// }}}

Uniendo los pasos de codificar un texto y encriptarlo, componemos estas dos funciones que trabajan directamente con una cadena de caracteres y una clave RSA.

{{{id=3| def encripta_mensaje(mensaje, clave_publica): '''Encripta una cadena de texto siguiendo el metodo RSA clave_publica es la tupla formada por N y e ''' N,e=clave_publica b=floor( log(N)/log(L) ) if b<1: raise Exception("N es demasiado pequeño") mensaje_codificado = codifica_mensaje(mensaje,b) mensaje_encriptado = encripta_RSA(mensaje_codificado,N,e) return mensaje_encriptado def desencripta_mensaje(secuencia, clave_privada): '''Desencripta una cadena de texto siguiendo el metodo RSA clave_privada es la tupla formada por N y d ''' N,d=clave_privada b=floor( log(N)/log(L) ) if b<1: raise Exception("N es demasiado pequenyo") mensaje_codificado = desencripta_RSA(secuencia,N,d) mensaje_decodificado = decodifica_mensaje(mensaje_codificado,b) return mensaje_decodificado /// }}}

Un ejemplo con números pequeños

Para que las operaciones de encriptado y desencriptado sean inversas una de la otra, se tiene que verificar, para cualquier x:

$$x^{de}=x(mod N)$$

Los números siguientes tienen esta propiedad, así que al desencriptar deberíamos recuperar el mensaje original. El número N es el producto de dos números primos p y q.

{{{id=8| p=29; q=31; N=p*q e=13 d=517 clave_publica=(N,e) mensaje_encriptado=encripta_mensaje(mensaje, clave_publica) print mensaje_encriptado /// [193, 90, 470, 378, 449, 252, 66, 474, 0] }}} {{{id=41| factor(N) /// 29 * 31 }}} {{{id=11| clave_privada=(N,d) desencripta_mensaje(mensaje_encriptado,clave_privada) /// 'CITA EN EL PATIO ' }}}

Generar pares de clave pública y privada

Veamos ahora cómo encontrar pares de clave pública y privada arbitrariamente grandes. Necesitamos números N, e y d tales que

$$x^{de}=x(mod\; N)$$

para cualquier $1<x<N$, pero además no debe ser fácil encontrar d a partir de e:

{{{id=16| #Generar aleatoriamente dos primos grandes tamanyo = 1e30 K=randint(tamanyo,2*tamanyo) p=next_prime(K) K=randint(tamanyo,2*tamanyo) q=next_prime(K) N=p*q print p,q,N /// 1399202587512894772741643296763 1216342295148791908885703216473 1701909286673562793883932669753044153846238826378628769176899 }}}

Escoge un exponente e que sea invertible módulo $\phi(N)=(p-1)(q-1)$:

{{{id=18| phi=(p-1)*(q-1) e=randint(1,phi) while gcd(e,phi)>1: e=randint(1,phi) print e /// 102875427855504315802629514980602362595287921214553701444035 }}}

Invierte el exponente e módulo $\phi(N)$:

{{{id=24| d=inverse_mod(e,phi) print d /// 1659190621842085354211332802738720692710641884518333722456347 }}}

Comprobamos que todo ha salido bien encriptando un mensaje y luego desencriptándolo. Usamos un alfabeto más grande para poder encriptar parte del manifiesto del HM2009.

{{{id=38| alfabeto = u''' abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#$%&\'()*+,-./:;<=>?@[\\]^_`{|}~\t\n\x0b\x0c\r0123456789áéíóúñ''' L=len(alfabeto) /// }}} {{{id=40| manifiesto=u'''Manifiesto 2009 - "NoMadHack" Indagando en los silenciosos mares de silicio, recodificando colaborativamente, y atentos a los murmullos en los canales de fibra óptica, donde la información nunca deja de fluir buscando desesperadamente un destino, hemos descubierto este manifiesto, escrito anónimamente por la sociedad mundial, en nuestra red de recogida de inquietudes, intenciones y sentimientos virtuales. ''' /// }}} {{{id=39| numeros=encripta_mensaje(manifiesto,(N,e)) print numeros /// [767316439615146371263305744853750774577582631295915800741956, 1219129321596790998293032220846359076621512734359825062971210, 280006809176213994423866324574893407907620540695819163652920, 1275280816142767422618827715652261635483641212174084914258700, 1526872740037813977695373545463045539919157447453346711620489, 490022820801324549455506420399127484501466203952632736054027, 1530272408594618934255992425726190139939304650965964768052996, 490663447710086876866707489615911175147870842855793504566942, 1612577536193522153445903930841898873535305421574988348094717, 803527972039880827254988267393546225501447892951356939858473, 153246573635015736579341055287833208329462505933441860942187, 1660653068916384763215983321454884533885671773483351735720081, 651069541605655122898174381968949152680290158035301568935997, 1293284215516668583734623532290275165390774878096694261752438, 1384785068528417481118056455729506735458293146739727140277600] }}} {{{id=42| #Deberiamos recuperar el mensaje original, aunque los #caracteres unicode se ven un poco distintos desencripta_mensaje(numeros,(N,d)) /// u'Manifiesto 2009 - "NoMadHack"\n\nIndagando en los silenciosos mares de silicio, recodificando colaborativamente, y atentos a los murmullos en los canales de fibra \xf3ptica, donde la informaci\xf3n nunca deja de fluir buscando desesperadamente un destino, hemos descubierto este manifiesto, escrito an\xf3nimamente por la sociedad mundial, en nuestra red de recogida de inquietudes, intenciones y sentimientos virtuales.\n ' }}}

La seguridad del sistema RSA se basa en que calcular la clave privada en función de la clave pública requiere mucho tiempo de cómputo. Pero si conocemos la factorización de N, conocemos el número $\varphi(N)$, y podemos calcular el exponente de desencriptado.

El pilar del sistema es que factorizar números grandes lleva mucho más tiempo de cómputo que encontrar números primos grandes. Si dedicamos un poco más de tiempo a buscar números primos un poco más grandes, el tiempo necesario para factorizar el producto de los números aumenta en una proporción mucho mayor.

{{{id=37| %time tamanyo = 1e10 K=randint(tamanyo,2*tamanyo) p=next_prime(K) K=randint(tamanyo,2*tamanyo) q=next_prime(K) N=p*q print p,q,N /// 19334855567 16460029739 318252297632089707013 CPU time: 0.00 s, Wall time: 0.00 s }}} {{{id=44| %time factor(N) /// 16460029739 * 19334855567 CPU time: 0.05 s, Wall time: 0.06 s }}} {{{id=46| %time tamanyo = 1e20 K=randint(tamanyo,2*tamanyo) p=next_prime(K) K=randint(tamanyo,2*tamanyo) q=next_prime(K) N=p*q print p,q,N /// 150396791728406549917 194090517350253292399 29190591114384722328697921011425790180883 CPU time: 0.03 s, Wall time: 0.03 s }}} {{{id=47| %time factor(N) /// 150396791728406549917 * 194090517350253292399 CPU time: 0.86 s, Wall time: 0.97 s }}} {{{id=48| %time tamanyo = 1e25 K=randint(tamanyo,2*tamanyo) p=next_prime(K) K=randint(tamanyo,2*tamanyo) q=next_prime(K) N=p*q print p,q,N /// 15425007669588100835266369 12991625517216356000447393 200395923243478768657278016592972692728356326626017 CPU time: 0.08 s, Wall time: 0.09 s }}} {{{id=49| %time factor(N) /// 12991625517216356000447393 * 15425007669588100835266369 CPU time: 9.95 s, Wall time: 10.64 s }}} {{{id=50| /// }}} {{{id=51| /// }}}