Криптографические протоколы



         

Депонирование ключей - часть 5


Практический результат последующих 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) операций




Содержание  Назад  Вперед