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

Question

Еще в эпоху ITAR существовал популярный 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 -e '16dio???|p'

В то время как современная форма dc с командой модульного возведения в степень ('|' вычисляет g ^ e % m посредством эффективного экспоненциального удвоения), вероятно, непобедима, за исключением, возможно, АПЛ, можно ли улучшить исходную форму?Имейте в виду, что значения e и m будут очень большими;они оба будут иметь размер порядка 1024 бит каждый для обеспечения криптографической безопасности.

Answer 1

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

./dh.pl 10 2 9
4

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

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

• толкать шестнадцать в стопку,
• dвозвысьте это,
• установленный input radix (основание) в результате извлечения стека (16, шестнадцатеричный),
• установленный output radix для результата выталкивания стека (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, так как мы прекратил обратные кавычки .