[SOLVED] Code golf: Diffie-Hellman key exchange

Code golf: Diffie-Hellman key exchange

Back in the ITAR era, there was a popular sig that performed Diffie-Hellman key exchange:

#!/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`

With a modern dc, this can be reduced quite a bit to:

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

While the modern dc form with the modular exponentiation command ('|' computes g^e % m via efficient exponential doubling) is likely unbeatable other than perhaps APL, can the original form be improved upon? Keep in mind that the e and m values will be very large; they will both be on the order of 1024 bits each for cryptographic security.

Solution

For those unfamiliar with Diffie-Hellman or dc (or Perl): all the program does, if you run it as "program g x m", is output g^x(mod m), where g, x, and m are given in hexadecimal. E.g.

./dh.pl 10 2 9
4

because 10 is sixteen and 10² is two-hundred-and-fifty-six, which is 4 mod 9.

And the dc command 16dio???|p says:

push sixteen onto the stack,
duplicate it,
set input radix (base) to the result of popping the stack (16, hex),
set output radix to the result of popping the stack (16),
get three lines of input and execute them (so if the three lines are three numbers g, x, m, they get pushed onto the stack),
do the exponentiation g^x(mod m),
print it.

Given that dc has a one-character command "|" for computing "g^x(mod m)" which is precisely the problem, I find it highly unlikely that it can be improved upon in any programming language. dc just happens to be a tool for exactly this problem; it's no contest comparing a programming language to the right tool. (E.g. any common programming language will take more than two characters to list files in a directory, while "ls" is only 2.)

That said, I note that dc -e '16dio???|p' seems to want me to input the numbers in three different lines (at least on the dc I have here), so it can be improved to something that can handle them all on the same line :-)

dc -e '16dio?|p'