Algoritmo rsa

  • Published on
    31-Jul-2015

  • View
    43

  • Download
    1

Embed Size (px)

Transcript

<p> 1. Algoritmo RSA 2. RSA En criptografa, RSA (Rivest, Shamir y Adle man) es un sistema criptogrfico de clave pblica desarrollado en 1977. Es el primer y ms utilizado algoritmo de este tipo y es vlido tanto para cifrar como para firmar digitalmente. 3. Introduccin. La seguridad de este algoritmo radica en el problema de la factorizacin d nmeros enteros. Los mensajes enviados se representan mediante nmeros, y el funcionamiento se basa en el producto, conocido, de dos nmeros primos grandes elegidos al azar y mantenidos en secreto. 4. Intreduccin. Como en todo sistema de clave pblica, cada usuario posee dos claves de cifrado: una pblica y otra privada. Se cree que RSA ser seguro mientras no se conozcan formas rpidas de descomponer un nmero grande en producto de primos. 5. Algoritmo RSA 6. Tcnicamente, Bob enva a Alicia un mensaje llano M en forma de un nmero m menor que otro nmero n, mediante un protocolo reversible conocido como padding scheme (patrn de relleno). A continuacin genera el mensaje cifrado mediante la siguiente operacin: donde e es la clave pblica de Alicia. Ahora Alicia descifra el mensaje en clave c mediante la operacin inversa dada por donde d es la clave privada que solo Alicia conoce. 7. Ejemplo En el siguiente ejemplo, supongamos que la persona A quiere hacer una clave pblica, y que persona B quiere usar esa tecla para enviar un mensaje. En este ejemplo, vamos a suponer que el mensaje A enva a B es slo un nmero. Suponemos que A y B han acordado en un mtodo para codificar el texto como nmeros. Estos son los pasos: 1. La persona A selecciona dos nmeros primos. Usaremos p = 23 y q = 41 para el ejemplo, pero hay que tener en cuenta que el nmero real de la persona A debe ser mucho ms grande. 2. La persona A multiplica p y q juntos para conseguir pq = (23) (41) = 943. 943 es la "clave pblica", que le dice a la persona B (y en el resto del mundo, si lo desea). 8. Ejemplo 3. La persona A tambin elige otro nmero e que debe ser primos entre s (p - 1) (q - 1). En este caso, (p - 1) (q - 1) = (22) (40) = 880, por lo que e = 7 est muy bien. e es tambin forma parte de la clave pblica, por lo que B tambin se cuenta el valor de e. 4. Ahora B sabe lo suficiente para codificar un mensaje a A. Supongamos, que el mensaje es el numero M = 35. 5. B calcula el valor de C = Me (mod N) = 357 (mod 943) . 6. 357 = 64,339296,875 y 64,339296,875 (mod 943) = 545. El nmero 545 es la codificacin que B enva a A. 9. Ejemplo 7. Ahora A quiere descifrar 545. Para ello, tiene que encontrar un nmero tal que ed = 1 (mod (p - 1) (q - 1)), o en este caso, de tal manera que 7d = 1 (mod 880). La solucin es d = 503, desde el 7*503 = 3521 = 4 (880) + 1 = 1 (mod 880). 8. Para encontrar la decodificacin, A debe calcular Cd (N mod) = 545503 (mod 943). Este parece que ser un clculo horrible, y al principio parece que lo es, pero hay que darse cuenta que 503 = 256 + 128 + 64 + 32 + 16 + 4 + 2 + 1 (esto es slo la expansin binaria de 503). As que esto significa que: 545503 = 545256 + 128 + 64 + 32 + 16 + 4 + 2 + 1 = 545256 545128 5451. 10. Ejemplo Pero ya que slo importa el resultado (mod 943), podemos calcular todo el parcial resultados en ese mdulo, y elevando al cuadrado repetido de 545, podemos obtener toda los exponentes que son potencias de 2. Por ejemplo, 5452 (MOD 943) = 545 545 = 297,025 (mod 943) = 923. Entonces cuadrado de nuevo: 5454 (mod 943) = (5452)2(mod 943) = 923 923 = 851 929 (mod 943) = 400, y as sucesivamente. Podremos obtener: 11. Ejemplo Podramos obtener: As que el resultado que queremos es: 545503 (mod 943) = 324 18 215 795 857 400 923 545 (mod 943) = 35. El clculo de esto es tedioso (pero simple para una computadora) clculo, A puede decodificar el mensaje de B y obtener el mensaje original N = 35. 5451 (mod 943) = 545 5458 (mod 943) = 633 54564 (mod 943) = 215 5452 (mod 943) = 923 54516 (mod 943) = 857 545128 (mod 943) = 18 5454 (mod 943) = 400 54532 (mod 943) = 795 545256 (mod 943) = 324 </p>