Código de golf: intercambio de llaves Diffie-Hellman

Question

En la era ITAR, había una sig. popular que realizó Diffie- Intercambio de llaves Hellman :

#!/usr/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines
($g,$e,$m)=@ARGV,$m||die"
dc -e '16dio???|p'
 gen exp mod\n";print`echo "16dio1[d2%Sa2/d0<X+d
*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p|dc`

Con un CD moderno, esto se puede reducir bastante para:

<*>

Si bien la forma moderna de CD con el comando de exponenciación modular ('|' calcula g ^ e% m mediante duplicación exponencial eficiente) es probablemente imbatible además de quizás APL , ¿se puede mejorar la forma original? Tenga en cuenta que los valores e y m serán muy grandes; ambos serán del orden de 1024 bits cada uno para la seguridad criptográfica.

Answer 1

Para aquellos que no estén familiarizados con Diffie-Helman o dc (o Perl): todo el programa lo hace, si lo ejecuta como " program gxm " ;, sale. g ^x (mod m), donde g, x y m se dan en hexadecimal. Por ejemplo,

./dh.pl 10 2 9
4

porque 10 es dieciséis y 10 ² es doscientos cincuenta y seis, que es 4 mod 9.

Y el comando dc 16dio ??? | p dice:

• empuje dieciséis en la pila,
• d uplicate,
• establezca i nput radix (base) en el resultado de saltar la pila (16, hexadecimal),
• establezca o utput radix en el resultado de abrir la pila (16),
• obtenga tres & nbsp; líneas de entrada y ejecútelas (de modo que si las tres líneas son tres números g, x, m, se insertan en la pila),
• hacer la exponenciación g ^x (mod m),
• p imprímelo.

Dado que dc tiene un comando de un solo carácter " | " para calcular " g ^x (mod m) " que es precisamente el problema, me parece altamente improbable que se pueda mejorar en cualquier lenguaje de programación. dc simplemente es una herramienta para este problema; No es un concurso que compare un lenguaje de programación con la herramienta adecuada. (Por ejemplo, cualquier lenguaje de programación común tomará más de dos caracteres para listar archivos en un directorio, mientras que " ls " es solo 2)

Dicho esto, observo que dc -e '16dio ??? | p' parece querer que ingrese los números en tres líneas diferentes (al menos en el dc tengo aquí), por lo que se puede mejorar a algo que pueda manejarlos todos en la misma línea :-)

dc -e '16dio? | p'

Answer 2

¡Dudo mucho que algo supere la versión moderna de CC! Aquí está Python:

def f(g,x,m):
 def h(n):return int(`n`,16)
 return h(g)**h(x)%h(m)

No funcionará en Python 3.0 porque hemos cotizaciones inversas eliminadas .