RSARSA (desambiguacin)Encriptografa,RSA(Rivest,ShamiryAdleman)es unsistema criptogrfico de clave pblicadesarrollado en1977. Es el primer y ms utilizadoalgoritmode este tipo y es vlido tanto para cifrar como parafirmar digitalmente.La seguridad de este algoritmo radica en el problema de lafactorizacindenmeros enteros. Los mensajes enviados se representan mediante nmeros, y el funcionamiento se basa en el producto, conocido, de dosnmeros primosgrandes elegidos al azar y mantenidos en secreto. Actualmente estos primos son del orden de, y se prev que su tamao crezca con el aumento de la capacidad de clculo de losordenadores.Como en todo sistema de clave pblica, cada usuario posee dos claves de cifrado: una pblica y otra privada. Cuando se quiere enviar un mensaje, el emisor busca la clave pblica del receptor, cifra su mensaje con esa clave, y una vez que el mensaje cifrado llega al receptor, este se ocupa de descifrarlo usando su clave privada.Se cree que RSA ser seguro mientras no se conozcan formas rpidas de descomponer un nmero grande en producto de primos. Lacomputacin cunticapodra proveer de una solucin a este problema de factorizacin.HistoriaEl algoritmo fue descrito en 1977 porRon Rivest,Adi ShamiryLeonard Adleman, delInstituto Tecnolgico de Massachusetts(MIT); las letras RSA son las iniciales de sus apellidos. Clifford Cocks, un matemtico britnico que trabajaba para la agencia de inteligencia britnicaGCHQ, haba descrito un sistema equivalente en un documento interno en 1973. Debido al elevado coste de las computadoras necesarias para implementarlo en la poca su idea no trascendi. Su descubrimiento, sin embargo, no fue revelado hasta 1997 ya que era confidencial, por lo que Rivest, Shamir y Adleman desarrollaron RSA de forma independiente.El algoritmo fue patentado por elMITen 1983 enEstados Unidoscon el nmero 4.405.829. Esta patente expir el 21 de septiembre de 2000. Como el algoritmo fue publicado antes de patentar la aplicacin, esto impidi que se pudiera patentar en otros lugares del mundo. Dado que Cocks trabaj en un organismo gubernamental, una patente en Estados Unidos tampoco hubiera sido posible.Algoritmo RSAEl algoritmo consta de tres pasos:

Idea del algoritmoSupongamos queBobquiere enviar aAliciaun mensaje secreto que solo ella pueda leer.Alicia enva a Bob una caja con una cerradura abierta, de la que solo Alicia tiene la llave. Bob recibe la caja, escribe el mensaje, lo pone en la caja y la cierra con su cerradura (ahora Bob no puede leer el mensaje). Bob enva la caja a Alicia y ella la abre con su llave. En este ejemplo, la caja con la cerradura es la clave pblica de Alicia, y la llave de la cerradura es su clave privada.Tcnicamente, Bob enva a Alicia un mensaje llanoen forma de un nmeromenor que otro nmero, mediante un protocolo reversible conocido comopadding scheme(patrn de relleno). A continuacin genera el mensaje cifradomediante la siguiente operacin:,dondees la clave pblica de Alicia.Ahora Alicia descifra el mensaje en clavemediante la operacin inversa dada por,dondees la clave privada que solo Alicia conoce.Generacin de claves1. Cada usuario elige dosnmeros primosdistintosy. Por motivos de seguridad, estos nmeros deben escogerse de forma aleatoria y deben tener una longitud enbitsparecida. Se pueden hallar primos fcilmente mediantetest de primalidad.2. Se calcula. se usa como elmdulopara ambas claves, pblica y privada.3. Se calcula, dondees lafuncin de Euler.4. Se escoge un entero positivomenor que, que seacoprimocon. se da a conocer como el exponente de la clave pblica. Si se escoge uncon unasuma encadenadacorta, el cifrado ser ms efectivo. Un exponentemuy pequeo (p. ej.) podra suponer un riesgo para la seguridad.15. Se determina un(mediantearitmtica modular) que satisfaga lacongruencia, es decir, quesea elmultiplicador modular inversode Expresado de otra manera,es dividido exactamente por. Esto suele calcularse mediante elalgoritmo de Euclidesextendido. se guarda como el exponente de la clave privada.Laclave pblicaes, esto es, el mdulo y el exponente de cifrado. Laclave privadaes, esto es, el mdulo y el exponente de descifrado, que debe mantenerse en secreto.Nota: PKCS#1 v2.0yPKCS#1 v2.1se especifican mediante lafuncin de Carmichaelen vez de la funcinde Euler, dondeindica elmnimo comn mltiplo. Para una mayor eficiencia los siguientes valores se calculan de antemano y se almacenan como parte de la clave privada: y: los primos para la generacin de las claves, y, .CifradoAliciacomunica su clave pblicaaBoby guarda la clave privada en secreto. Ahora Bob desea enviar un mensajea Alicia.Primero, Bob convierteen un nmero enteromenor quemediante un protocolo reversible acordado de antemano. Luego calcula el texto cifradomediante la operacin.Esto puede hacerse rpido mediante el mtodo deexponenciacin binaria. Ahora Bob transmitea Alicia.DescifradoAlicia puede recuperara partir deusando su exponentede la clave privada mediante el siguiente clculo:.Ahora que tieneen su poder, puede recuperar el mensaje originalinvirtiendo elpadding scheme.El procedimiento anterior funciona porque.Esto es as porque, como hemos elegidoyde forma que, se cumple.La ltima congruencia se sigue directamente delteorema de Eulercuandoes coprimo con. Puede demostrarse que las ecuaciones se cumplen para todousando congruencias y elteorema chino del resto.Esto muestra que se obtiene el mensaje original:.EjemploAqu tenemos un ejemplo de cifrado/descifrado con RSA. Los parmetros usados aqu son pequeos y orientativos con respecto a los que maneja el algoritmo, pero podemos usar tambinOpenSSLpara generar y examinar un par de claves reales.p= 611 n primo privado

q= 532 n primo privado

n=pq= 3233productopq

e= 17exponente pblico

d= 2753exponente privado

La clave pblica (e,n). La clave privada es (d,n). La funcin de cifrado es:

Donde m es el texto sin cifrar. La funcin de descifrado es:

Donde c es el texto cifrado. Para cifrar el valor del texto sin cifrar 123, nosotros calculamos:

Para descifrar el valor del texto cifrado, nosotros calculamos:

Ambos de estos clculos pueden ser eficientemente usados por el algoritmo de multiplicacin cuadrtica paraexponenciacin modular.Esquemas de rellenoRSA debe ser combinado con algnesquema de relleno, ya que si no el valor deMpuede llevar a textos cifrados inseguros. El valorm=0 om=1 siempre produce textos cifrados iguales para 0 o 1 respectivamente, debido a propiedades de los exponentes. Cuando ciframos con exponentes pequeos (e=3) y valores pequeos dem, el resultado dempodra ser estrictamente menor que el mdulo den. En este caso, el texto cifrado podra ser fcilmente descifrado, tomando la raz e-sima del texto cifrado sin tener en cuenta el mdulo. Dado que el cifrado RSA es un algoritmo determinista (no tiene componentes aleatorios) un atacante puede lanzar con xito un ataque de texto elegido contra el criptosistema, construyendo un diccionario de textos probables con la llave pblica, y almacenando el resultado cifrado. Observando los textos cifrados en un canal de comunicacin, el atacante puede usar este diccionario para descifrar el contenido del mensaje.En la prctica, el primero de los dos problemas podra presentarse cuando enviamos pequeos mensajes ASCII dondemes la concatenacin de uno o ms carcter/es ASCII codificado/s. Un mensaje consiste en un solo carcter ASCII NUL (cuyo valor es 0) se codificara comom=0, produciendo un texto cifrado de 0 sin importar qu valores deeyNson usados. Probablemente, un solo ASCII SOH (cuyo valor es 1) producira siempre un texto cifrado de 1. Para sistemas convencionales al usar valores pequeos dee, como 3, un solo carcter ASCII mensaje codificado usando este esquema sera inseguro, ya que el mximo valor demsera 255, y 255 es menor que cualquier mdulo razonable. De esta manera los textos sin cifrar podran ser recuperados simplemente tomando la raz cbica del texto cifrado. Para evitar estos problemas, la implementacin prctica del RSA se ayuda de algunas estructuras, uso delrellenadoaleatorio dentro del valor demantes del cifrado. Esta tcnica asegura quemno caer en el rango de textos sin cifrar inseguros, y que dado un mensaje, una vez que este rellenado, cifrar uno de los nmeros grandes de los posibles textos cifrados. La ltima caracterstica es la incrementacin del diccionario haciendo este intratable a la hora de realizar un ataque.El esquema de relleno de RSA (en inglsRSA-padding scheme) debe ser cuidadosamente diseado para prevenir ataques sofisticados los cuales podran ser facilitados por la predictibilidad de la estructura del mensaje. Ejemplos de esquema de relleno usados con RSA:23 RSA-OAEP (Optimal Asymetric Encryption Padding) o su versin moficada RSA-OAEP+. Este tipo de relleno es usado por ejemplo enPKCS#1y en la red de anonimatoTOR RSA-SAEP+ (Simplified Asymmetric Encryption Padding) RSA-REACT RSA-PSS (Probabilistic Signature Scheme). Usado por ejemplo enPKCS#1Algunos de estos esquemas de relleno, por ejemplo RSA-OAEP y RSA-PSS, ecuentran su 'justificacin' terica en el polmicomodelo de orculo aleatorio.Autenticacin de mensajesRSA puede tambin ser usado para autenticar un mensaje. Supongamos que Alicia desea enviar un mensaje autentificado a Bob. Ella produce un valorhashdel mensaje, lo eleva a la potencia de d mod n (como ella hace cuando descifra mensajes), y lo adjunta al mensaje como una firma. Cuando Bob recibe el mensaje autentificado, utiliza el mismo algoritmo hash en conjuncin con la clave pblica de Alice. Eleva la firma recibida a la potencia de e mod n (como hace cuando cifra mensajes), y compara el resultado hash obtenido con el valor hash del mensaje. Si ambos coinciden, l sabe que el autor del mensaje estaba en posesin de la clave secreta de Alicia, y que el mensaje no ha sido tratado de forzar (no ha sufrido ataques).Se debe observar que la seguridad de los padding-schemes comoRSA-PSSson esenciales tanto para la seguridad de la firma como para el cifrado de mensajes, y que nunca se debera usar la misma clave para propsitos de cifrado y de autentificacin.SeguridadLa seguridad del criptosistema RSA est basado en dos problemas matemticos: el problema defactorizar nmeros grandesy elproblema RSA. El descifrado completo de un texto cifrado con RSA es computacionalmente intratable, no se ha encontrado un algoritmo eficiente todava para ambos problemas. Proveyendo la seguridad contra el descifrado parcial podra requerir la adicin de una seguridad padding scheme.El problema del RSA se define como la tarea de tomar racese-simas mdulo a componern: recuperando un valormtal quemec(modn), donde (e,n) es una clave pblica RSA y c es el texto cifrado con RSA. Actualmente la aproximacin para solventar el problema del RSA es el factor del mdulon. Con la capacidad para recuperar factores primos, un atacante puede calcular el exponente secretoddesde una clave pblica (e,n), entonces descifracusando el procedimiento estndar. Para conseguir esto, un atacante debe factorizarnenpyq, y calcular (p-1)(q-1) con lo que le permite determinardye. No se ha encontrado ningn mtodo entiempo polinmicopara la factorizacin de enteros largos. Verfactorizacin de enterospara la discusin de este problema.La factorizacin de nmeros grandes por lo general proponen mtodos teniendo 663 bits de longitud usando mtodos distribuidos avanzados. Las claves RSA son normalmente de entre 1024-2048 bits de longitud. Algunos expertos creen que las claves de 1024 bits podran comenzar a ser dbiles en poco tiempo; claves de 4096 bits podran ser rotas en un futuro. Por lo tanto, sines suficientemente grande el algoritmo RSA es seguro. Sintiene 256 bits o menos, puede ser factorizado en pocas horas con un ordenador personal, usandosoftware libre. Sintiene 512 bits o menos, puede ser factorizado por varios cientos de computadoras como en 1999. Un dispositivo hardware terico llamadoTWIRLdescrito por Shamir y Tromer en el 2003 cuestion a la seguridad de claves de 1024 bits. Se recomienda actualmente quensea como mnimo de 2048 bits de longitud.En 1993, Peter Shor public sualgoritmo, mostrando que una computadora cuntica podra en principio mejorar la factorizacin en tiempo polinomial, mostrando RSA como un algoritmo obsoleto. Sin embargo, las computadoras cunticas no se esperan que acaben su desarrollo hasta dentro de muchos aos.Consideraciones prcticasGeneracin de claves Buscando nmeros primos grandespyqpor el test de aleatoriedad y realizando tests probabilsticos de primalidad los cuales eliminan virtualmente todos los no-primos (eficientemente).Los nmerospyqno deberan ser suficientemente cercanos para que lafactorizacin de Fermatparansea exitosa. Adems, si cualquierp-1 oq-1 tiene slo factores primos pequeos,npuede ser factorizado rpidamente, con lo que estos valores depoqdeben ser descartados.No se debera emplear un mtodo de bsqueda de primos con el cual se d alguna informacin cualquiera sobre los primos al atacante. En particular, se debe utilizar un buen generador aleatorio de nmeros primos para el valor empleado. Obsrvese que el requerimiento est en que ambos seanaleatorioseimpredecibles. No son el mismo criterio; un nmero podra haber sido elegido por un proceso aleatorio, pero si ste es predecible de cualquier forma (o parcialmente predecible), el mtodo usado resultar en una baja seguridad. Por ejemplo: la tabla de nmeros aleatorios de Rand Corp en 1950 podra servir muy bien como ejemplo de criterio verdaderamente aleatorio, pero ha sido publicada y a sta puede acceder el atacante. Si el atacante puede conjeturar la mitad de los dgitos depoq, l podra rpidamente calcular la otra mitad. (Ver Coppersmith en 1997).Es importante que la clave secretadsea muy grande. Wiener mostr en 1990 que sipest entreqy 2q(es tpico) yd