Code golf: Diffie-Hellman key exchange

Question

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.

Answer 1

For those unfamiliar with Diffie-Helman 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'

Answer 2

I very much doubt anything will top the modern dc version! Here's Python:

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

It won't work in Python 3.0 as we've phased out reverse quotes.