Diffie-Hellman: golfe código

Question

Para trás na era ITAR, houve uma sig popular que realizada Diffie- Hellman troca de chave :

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

Com um dc moderno, este pode ser reduzido um pouco para:

dc -e '16dio???|p'

Embora a forma dc moderno com o comando modular exponenciação ( '|' calcula g ^ e% m via duplicação exponencial eficiente) é provável imbatível à excepção talvez de APL , pode a forma original ser melhorado? Tenha em mente que os e e m valores será muito grande; eles serão tanto na ordem de 1024 bits cada para a segurança criptográfica.

Answer 1

Para aqueles não familiarizados com Diffie-Helman ou dc (ou Perl): todo o programa faz, se você executá-lo como "program g x m", é emitido g ^x (m mod), onde g, x, e m são dadas em hexadecimal. Por exemplo.

./dh.pl 10 2 9
4

10 porque é dezasseis e 10 ² é de duzentos e cinquenta e seis anos, que é 4 9 mod.

E o dc comando 16dio???|p diz:

• impulso dezesseis na pilha,
• d uplicate-lo,
• set i nput radix (base) para o resultado de estalar a pilha (16, hex),
• set o utput radix ao resultado de estalar a pilha (16),
• obter três linhas de entrada e executá-las (por isso, se as três linhas são três números G, X, m, eles são empurrados para a pilha),
• que a exponenciação g ^x (mod m),
• p rint-lo.

Dado que dc tem um carácter comando "|" para a computação "g ^x (m mod)", que é precisamente o problema, acho que é altamente improvável que ele pode ser melhorado em qualquer linguagem de programação. dc só acontece de ser uma ferramenta para exatamente este problema; não é nenhuma competição comparando uma linguagem de programação para a ferramenta certa. (Por exemplo, qualquer linguagem de programação comum levará mais de dois caracteres para arquivos de lista em um diretório, enquanto "ls" apenas 2 é.)

Dito isto, observo que dc -e '16dio???|p' parece-me deseja introduzir os números em três linhas diferentes (pelo menos na dc tenho aqui), por isso pode ser melhorado a algo que pode lidar com todos eles na mesma linha: -)

dc -e '16dio?|p'

Answer 2

duvido muito nada estará no topo da versão moderna dc! Aqui está Python:

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

não vai funcionar em Python 3.0 como temos eliminados aspas reversas .