代码高尔夫：Diffie-Hellman 密钥交换

Question

早在 ITAR 时代，就有一个流行的签名执行 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，这可以大大简化为：

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

虽然带有模幂命令的现代 dc 形式（“|”通过有效的指数加倍计算 g^e % m）可能是无与伦比的，但也许APL，原始形式可以改进吗？ 请记住，e 和 m 值将非常大； 为了加密安全，它们的大小均为 1024 位。

Answer 1

对于那些不熟悉 Diffie-Hellman 或 dc（或 Perl）的人：如果您将其作为“program gx m”运行，则该程序的所有功能都是输出 g ^{x(mod m)，其中 g、x 和 m 以十六进制给出。 例如，}

./dh.pl 10 2 9
4

因为 10 是十六，而 10² 是二百五十六，即 4 mod 9。

而 dc 命令 16dio??? |p 表示：

• 将十六压入堆栈，
• d复制它，
• 将i输入基数（基数）设置为结果出栈（16，十六进制），
• 将o输出基数设置为出栈结果（16），
• 获取三行输入并执行它们（因此，如果三行是三个数字 g ，x，m，它们被推入堆栈），
• 进行求幂 g^x(mod m)，
• p打印它。

鉴于 dc 有一个单字符命令“|”用于计算“g^x(mod m)”，这正是问题所在，我发现它不太可能在任何编程语言中得到改进。 dc 恰好是解决这个问题的工具； 将编程语言与正确的工具进行比较是没有争议的。 （例如，任何常见的编程语言都需要两个以上的字符来列出目录中的文件，而“ls”仅为 2。）

也就是说，我注意到 dc -e '16dio? ??|p' 似乎希望我在三个不同的行中输入数字（至少在我这里的 dc 上），所以它可以改进 到可以在同一行处理所有这些的东西:-)

dc -e '16dio?|p'

Answer 2

我非常怀疑有什么能超越现代 DC 版本！ 这是Python：

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

它在Python 3.0中不起作用，因为我们已经 逐步淘汰反向引号。