Code golf:Diffie-Hellman密钥交换

Question

回到ITAR时代,有一个流行的sig执行Diffie-Hellman密钥交换:

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

使用现代直流电,这可以减少到相当多:

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

虽然具有模幂运算命令的现代直流形式('|'通过有效的指数倍增计算g ^ e%m)可能是除了APL之外无法比拟的,原始形式是否可以改进？请记住,e和m值会非常大; 对于加密安全性,它们都将为1024位.

Answer 1

对于那些不熟悉Diffie-Helman或dc(或Perl)的人:如果以" program g x m" 运行它,所有程序都会输出g ^x(mod m),其中g,x和m以十六进制给出.例如

./dh.pl 10 2 9
4

因为10是十六而10 ²是二百五十六,这是4 mod 9.

和dc命令16dio???|p说:

• 将十六个推入堆栈,
• d重复它,
• 设定我 NPUT基数(基)到出栈的结果(16进制),
• 将o utput radix 设置为弹出堆栈的结果(16),
• 得到三行输入并执行它们(所以如果三行是三个数字g,x,m,它们会被推到堆栈上),
• 取幂g ^x(mod m),
• 打个招呼吧.

鉴于它dc具有|用于计算"g ^x(mod m)" 的单字符命令" ",这正是问题所在,我发现它在任何编程语言中都不太可能得到改进.dc恰好是这个问题的工具; 将编程语言与正确的工具进行比较并不是一件好事.(例如,任何常见的编程语言都需要两个以上的字符来列出目录中的文件,而" ls"只有2个.)

也就是说,我注意到dc -e '16dio???|p'似乎要我输入三行不同的数字(至少dc我在这里),所以它可以改进到可以在同一行上处理它们的东西:-)

dc -e '16dio?|p'