2

回到 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'

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

4

2 回答 2

6

对于那些不熟悉 Diffie-Helman 或dc（或 Perl）的人：如果您以 " " 运行它，程序所做的所有事情program g x m都是输出 g x (mod m)，其中 g、x 和 m 以十六进制给出。例如

./dh.pl 10 2 9
4

因为 10 是 16，而 10 2是 256，即 4 mod 9。

dc命令说16dio???|p：

  • 将16压入堆栈，
  • d复制它，
  • 将输入基数（基数）设置为弹出堆栈的结果（16，十六进制），
  • 将输出基数设置为弹出堆栈的结果（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'

于 2009-01-05T04:16:42.013 回答
2

我非常怀疑任何东西都会超越现代直流版本！这是Python：

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

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

于 2009-01-05T12:23:27.290 回答