2

ITAR 時代にさかのぼると、Diffie-Hellman 鍵交換を実行する人気のある sigがありました。

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

べき乗剰余コマンド ('|' は、効率的な指数倍増によって g^e % m を計算します) を使用した最新の dc 形式は、おそらくAPL以外では無敵ですが、元の形式を改善することはできますか? e と m の値は非常に大きくなることに注意してください。どちらも、暗号化セキュリティのためにそれぞれ 1024 ビットのオーダーになります。

4

2 に答える 2

6

Diffie-Helmanまたは（またはPerl）に慣れていないdc場合：すべてのプログラムは、 ""として実行するとprogram g x m、出力g x（mod m）になります。ここで、g、x、およびmは16進数で指定されます。例えば

./dh.pl 10 2 9
4

10は16であり、10 2は256であり、これは4mod9であるためです。

そして、dcコマンド16dio???|pは言う：

  • 16をスタックにプッシュします。
  • 複製して、
  • スタック（ 16、16進数）をポップした結果に入力基数（ベース）を設定し、
  • 出力基数をスタックをポップした結果に設定します（16）、
  • 3行の入力を取得して実行します（したがって、3行が3つの数値g、x、mの場合、スタックにプッシュされます）、
  • べき乗gx （ mod m）を実行し、
  • それを印刷します。

まさに問題である「 gx （mod m）」を計算するためdcの1文字のコマンド「」があることを考えると、どのプログラミング言語でも改善できる可能性は非常に低いと思います。たまたまこの問題のツールにすぎません。プログラミング言語を適切なツールと比較するのはコンテストではありません。（たとえば、一般的なプログラミング言語では、ディレクトリ内のファイルを一覧表示するのに2文字以上かかりますが、 " "は2文字だけです。）|dcls

とは言うdc -e '16dio???|p'ものの、3つの異なる行に数字を入力したいようです（少なくともdcここにあります）ので、すべて同じ行で処理できるように改善することができます:-)

dc -e '16dio?|p'

于 2009-01-05T04:16:42.013 に答える
2

現代のDCバージョンを超えるものがあるとはとても思えません! ここにパイソンがあります：

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 に答える