Code golf: Diffie-Hellman key exchange
-
03-07-2019 - |
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.
Solution
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 gx(mod m), where g, x, and m are given in hexadecimal. E.g.
./dh.pl 10 2 9
4
because 10 is sixteen and 102 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 gx(mod m),
- print it.
Given that dc
has a one-character command "|
" for computing "gx(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'
OTHER TIPS
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.