"Siempre fuisteis enigmático
y epigramático y ático
y retórico y simbólico
y aunque os escucho flemático
sabed que a mi lo hiperbólico
no me resulta simpático"

La venganza de Don Mendo, Pedro Muñoz Seca.

    Para entender porque RSA constituye un sistema útil de clave pública, notemos en primer lugar que cualquier individuo puede encontrar dos grandes primos p y q con, por ejemplo 100 dígitos, en pocos segundos de ordenador. Se pueden elegir simplemente enteros impares de 100 dígitos aleatoriamente y el teorema de distribución de los números primos nos asegura que la probabilidad de que dicho número sea primo es aproximadamente de 2/(log 10 ^100) lo que quiere decir uno de cada 115 en promedio. Un test de tipo probabilístico nos permitirá descartar los compuestos muy rápidamente.

    *Puedes encontrar más cosas sobre primos incluyendo una pequeña calculadora aquí.

    Una vez elegidos los primos p y q necesitamos un exponente e, que verifique mcd(e, fi(pq))=1 como se explico en el artículo anterior. Una forma posible es elegir un primo e mayor que p y q . De cualquier modo debe cumplirse que 2^e>n=pq para que sea imposible obtener el texto en claro P calculando simplemente la raíz de índice e del texto cifrado C=(P^e (mod n). Con la condición antes citada cualquier P (excepto 0 y 1) sufrirá una reducción módulo n.

    La exponenciación modular es también rapidísima incluso cuando el módulo, el exponente y la base tienen 200 dígitos. Con el algoritmo de Euclides encontramos rápidamente el inverso d del exponente e módulo fi(n) cuando p y q son conocidos pues en este caso fi(n)=fi(pq)=(p-1)(q-1).

    Por contra, el conocimiento de la clave de cifrado (e, n) no conduce al de la clave de descifrado. En efecto, para hallar d, un inverso de e módulo fi(n) necesitamos encontrar fi(n) y esto NO es más sencillo que factorizar n, lo que parece ser un problema intrínsecamente costoso computacionalmente hablando (ver mi artículo sobre cifrado exponencial).

    Aunque no se ha probado que sea imposible romper un cifrado RSA sin factorizar n, aún nadie ha descubierto una alternativa pues los métodos existentes son en general equivalentes en complejidad a factorizar un número entero.

    Unas precauciones extras para escoger p y q evitando así métodos de factorización especiales :

    Los sistemas de clave pública se utilizan también para firmar mensajes. El uso de firmas digitales hace que el receptor de un mensaje esté seguro de que realmente partió del emisor anunciado. Se utilizan en el correo electrónico y en transacciones bancarias. Veamos el proceso matemático involucrado:

    Digamos que i manda un mensaje a j , lo primero que hará será calcular S=Di(P)=P^di(mod ni) donde (di, ni) es la clave privada de i . Entonces si nj>ni se forma C=Ej(S)=S^ej(mod nj) y cuando nj es menor que ni el emisor parte S en bloques de tamaño menor que nj y cifra usando ej.

    Para descifrar j utiliza primero Dj(C)=Dj(Ej(S))=S y a continuación obtiene el texto en claro así Ei(S)=Ei(Di(P))=P donde la última identidad se sigue de que (P^di)^ei=P^(di.ei)=P (mod ni) ya que di.ei=1 (mod fi(ni)).

    La combinación de texto en claro P y la versión firmada S convence a j de que el mensaje proviene de i, y éste no puede negar haberlo enviado. Resumiendo, todo el sistema RSA se basa en lo fácil que es encontrar primos frente a lo difícil que es factorizar un entero.