Криптографические протоколы
Практический результат последующих 20 лет
Практический результат последующих 20 лет научных поисков таких задач оказался до некоторой степени парадоксальным: при всем многообразии известных сложных вычислительных задач, практически применимой оказалась одна. Это так называемая задача дискретного логарифмирования.
В простейшем варианте ее можно сформулировать так. Если заданы три больших целых положительных числа
a, n, x,
то располагая даже несложными арифметическими устройствами типа карманного калькулятора, или просто карандашом и бумагой, можно довольно быстро вычислить число
a**x
как результат умножения числа
a
на себя
x
раз,
а затем и остаток от деления этого числа нацело на n, записываемый как
b = a**x mod n
задача же дискретного логарифмирования состоит в том, чтобы по заданным числам
a, b, n
связанным таким соотношением, найти то число
x
из которого по этой формуле было вычислено число b.
Оказывается, что задача дискретного логарифмирования при правильном выборе целых чисел настолько сложна, что позволяет надеяться на практическую невозможность восстановления числа x, - индивидуального ключа подписывания, по числу b, применяемому в качестве ключа проверки.
Чтобы говорить более определенно о практической невозможности решить ту или иную вычислительную задачу, следует предварительно договориться о том, какие вычислительные мощности и мозговые ресурсы доступны тому, кто предположительно будет эту задачу решать. Поскольку давать конкретные оценки возможностей потенциальных мозговых ресурсов будущего "взломщика" системы цифровой подписи дело весьма сложное и неблагодарное, мы будем просто исходить из предположения, что он располагает полной информацией о наилучших известных мировой науке методах решения данной задачи.
Далее, если он располагает вычислительной системой общей мощностью, скажем, 1 миллиард (10**9 = 1 000 000 000) операций в секунду, а это мощность современного суперкомпьютера типа CRAY-3, то
- за сутки непрерывной работы такой системы может быть решена задача сложностью около 100 000 миллиардов (или 10**14) операций
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий