¿Hay un ejemplo simple de una rutina de cifrado / descifrado asimétrico?

El crédito va a La respuesta de Jeff para los detalles y la respuesta de Steve que también fue útil. El crédito también va a La respuesta de Tylerl que incluía enlaces a Wikipedia para todas las funciones, particularmente modInverse , también aclaró lo ambiguo. punto de partida para e . Gracias, mejoré sus respuestas y, utilizando la información combinada de las tres respuestas, creé lo que espero sea una mejor respuesta.

La clave para hacer que la ingeniería inversa sea tan costosa es usar power-of . La raíz cuadrada no es tan dura, la potencia de 3 significa que necesitas una raíz en cubos, pero la potencia de 34,051,489 es bastante difícil. Hay otras operaciones matemáticas que son difíciles de aplicar ingeniería inversa. También hay varias formas de crear un algoritmo asimétrico, pero esta respuesta se centra en RSA. El más antiguo y el más común.

RSA Algorithm (basado en el Código Java )

Los cálculos a continuación deben realizarse con enteros de precisión arbitrarios . (Como BigInt o BigInteger)

Generando las claves:

• La longitud de la clave constante es l .
• Por lo general, la constante e_start puede =3 para simplificar. Sin embargo, 0x10001 es más común, en cualquier caso, un número primo es el mejor (por razones de rendimiento de generación de claves y probablemente otras razones).
• p y q son los números primos positivos generados aleatoriamente, que requieren hasta l bits para el almacenamiento. (Para mantener esto positivo, el primer bit siempre será 0 )
• n = p*q Esto se usa tanto para el cifrado como para el descifrado.
• e comienza como e_start . Esta será finalmente la parte de la clave de cifrado.
• m = (p-1)*(q-1) se usa para convertir e a d , que se usará para el descifrado.
• while( gcd (e,m)>1){e+=2} Esto es necesario para que el siguiente paso funcione.
• d= modInverse (e,m) Esto realiza una operación aritmática estándar. Probablemente no valga la pena examinar mucho, especialmente si su lenguaje de programación tiene esto incorporado

Para cifrar o descifrar, primero convierta sus bytes en un único entero de precisión arbitraria.

Encriptación: encrypted=(plain^e)%n

Nota: si plain>=n , debes dividir plain en dos o más valores más pequeños y cifrarlos por separado.

Descifrado: plain=(encrypted^d)%n

El cifrado asimétrico suele ser menos eficiente que el cifrado simétrico. A veces, el cifrado asimétrico se utiliza solo para el intercambio de claves.

En lo que respecta a RSA, este proporciona un buen ejemplo que se puede seguir y muestra Ejemplos correspondientes de entrada y salida. Esta aplicación demo lo guiará a través de los distintos pasos y le permitirá verificar el trabajo. A veces, simplemente hacer clic en algo en pasos como eso ayudará. Para los artículos de Wikipedia, debe consultar el artículo del algoritmo real: RSA para las matemáticas que corresponden.

En cuanto a la implementación, puede reunir esto claramente en Java en bajo 30 líneas .

Para su comprensión, no existe tal cosa como una clave de solo cifrado. Más bien, hay dos claves iguales que invierten las operaciones de sus socios. Asignamos arbitrariamente a uno de los pares como privado y uno como público. Las cosas cifradas con una clave se pueden descifrar con la otra clave. Este es el principio utilizado con la firma.

No es un problema de ingeniería anti-reversa lo que hace que las claves sean seguras, sino más bien un concepto matemático que no puede verificar razonablemente el espacio de teclas masivo (cuando la clave usa un espacio de números realmente grande) para encontrar la clave correspondiente . No hay una aceleración real para el trabajo de factoring.

Hay otros algoritmos de claves asimétricas que aprender, pero mientras empiezas, intentaré entender el RSA, el más antiguo y el más común, primero.

Preparé una demostración de RSA usando python (python es muy fácil de leer, incluso si nunca lo has visto antes). El código es lo suficientemente largo como para no caber en una sola página, pero lo suficientemente corto como para que pueda leerlo y entenderlo en unos minutos.

Dado que el cifrado / descifrado se puede lograr con un solo comando incorporado, exp(PLAINTEXT,KEY,MODULUS) , también paso por todo el proceso de derivación de claves.

Encontrarás el código aquí: enlace

Cuando ejecuta el código, le pide que ingrese la información en forma de >12345 o <12345 , donde el prefijo > le indica que aplique una clave privada al número, mientras que < le dice que Aplicar la clave pública. En aras de la simplicidad, solo codifica números; pero una vez que tienes eso, codificar datos arbitrarios es solo una cuestión de formato.

En realidad, las matemáticas a su alrededor son bastante simples, como yo lo entiendo. Toma un valor de la potencia de un número primo de gran tamaño (miles de dígitos) y realiza una modificación de otro número.

Entonces, para cifrar tienes algo como: EncryptedBits = (PlainText ^ YourPublicKey)% Módulo

Y para descifrar tienes algo como: PlainText = (EncryptedBits ^ YourPrivateKey)% Módulo

Encontré un documento bastante fácil de leer aquí: enlace

Sin embargo, no estoy seguro de que haya que buscar en ninguna biblioteca.

Si desea una solución Perl linda y mínima, existe una clásica de Adam Back en 1995 :

• export-a-crypto-system sig

Se imprimió en una camiseta, incluido un código de barras para que sea legible por computadora, junto con la declaración " Esta camiseta es una munición ". Esa declaración fue precisa en los EE. UU. Antes de que la criptografía sólida fuera reclasificada en 1996 para que ya no sea técnicamente una "munición". Pero aún era en general ilegal para exportar criptografía fuerte desde los EE. UU. Hasta que las Regulaciones de la Administración de Exportaciones (EAR) se revisadas en 2000 :

El software también se ha distribuido como un tatuaje, firma de correo electrónico, etiqueta de correo y en muchas otras formas, e incluso apareció (en forma borrosa) en New York Times (el artículo, sin la foto, está en línea en Entre un hacker y un lugar difícil ). Una versión más reciente de 2 líneas es:

print pack"C*",split/\D+/,'echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc'

Tenga en cuenta que el enfoque original se basa en el programa "dc" de Unix para aritmética de precisión arbitraria. Una versión de Pure-Perl, con anotación, se encuentra en

• RSA en 5 líneas de perl