Код гольфа: обмен ключами Диффи-Хеллмана - PullRequest
Новая
       12

Код гольфа: обмен ключами Диффи-Хеллмана

2 голосов
/ 05 января 2009

В эпоху ИТАР был популярный сиг , который выполнял обмен ключами Диффи-Хеллмана : 

#!/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 бит каждый для криптографической защиты.

Ответы [ 2 ]

6 голосов
/ 05 января 2009

Для тех, кто не знаком с Диффи-Хелманом или dc (или Perl): все, что делает программа, если вы запускаете ее как "program g x m", выводит g x (mod m), где g, x и m даны в шестнадцатеричном формате. Э.Г. 

./dh.pl 10 2 9
4

потому что 10 - это шестнадцать, а 10 2 - это двести пятьдесят шесть, то есть 4 мода 9.

И команда dc 16dio???|p говорит:

  • толкнуть шестнадцать в стек,
  • d дублируй,
  • установить i nput radix (base) к результату выталкивания стека (16, hex),
  • установить o utput radix к результату выталкивания стека (16),
  • получить три строки ввода и выполнить их (поэтому, если три строки представляют собой три числа g, x, m, они помещаются в стек),
  • сделать возведение в г x (мод м),
  • p опечатать.

Учитывая, что dc имеет односимвольную команду "|" для вычисления "g x (mod m)", что является именно проблемой, я считаю крайне маловероятным, что это может быть улучшено на любом языке программирования. dc как раз оказывается инструментом именно для этой проблемы; это не соревнование, сравнивающее язык программирования с правильным инструментом. (Например, для любого распространенного языка программирования список файлов в каталоге займет более двух символов, а "ls" - только 2.)

Тем не менее, я отмечаю, что dc -e '16dio???|p', кажется, хочет, чтобы я вводил числа в трех разных строках (по крайней мере, у dc, который у меня здесь), так что можно улучшить к чему-то, что может обрабатывать их все в одной строке: -)

dc -e '16dio?|p'

2 голосов
/ 05 января 2009

Я очень сомневаюсь, что что-нибудь превзойдет современную версию DC! Вот Python: 

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

Это не будет работать в Python 3.0, поскольку мы прекратили использовать обратные кавычки .

...