В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 16. Проблемы реализации. Часть II тов кто-то предложил назвать ее словом “woop” 2 . Впоследствии это название закрепилось и за самим методом. Через некоторое время Бос описал дета- ли вупинга в своей докторской диссертации [10, глава 6], но опустил слово “wooping”, чтобы не шокировать почтенное академическое общество. Основная идея вупинга заключается в том, чтобы проверять правиль- ность вычислений по модулю с помощью случайно выбранных малых про- стых чисел. Для большей наглядности это можно представить себе в виде криптографической проблемы. У нас есть библиотека арифметических опе- раций над большими числами, которая пытается “обмануть” нас и предо- ставить неверные результаты. Наша задача состоит в том, чтобы проверить правильность этих результатов. Простая проверка результатов с помощью все той же библиотеки не принесет никакой пользы, так как ошибка может последовательно повторяться по всему коду библиотеки. Используя вупинг, мы можем проверить правильность библиотечных вычислений, если предпо- ложим, что библиотека не пытается “нарочно” навредить нам (в том смысле, что она не портит преднамеренно наши вычисления, выполняемые в рамках верификации). Вначале мы случайным образом генерируем относительно малое простое число t длиной около 64-128 бит. Значение t не должно быть фиксированным или предсказуемым, но именно для этого и предназначен генератор псевдо- случайных чисел. Полученное значение t сохраняется в секрете от остальных участников общения. Затем для каждого большого числа x , которое фигу- рирует в вычислениях, мы подсчитываем ˜ x := ( x mod t ) . Число ˜ x — это и есть функция WOOP ( x ) . Значения функции WOOP ( x ) имеют фиксиро- ванный размер. Обычно они намного меньше соответствующих больших чи- сел. Поэтому вычисление WOOP ( x ) не требует больших расходов системных ресурсов. Итак, для каждого целого числа x мы сохраняем значение WOOP ( x ) . Для каждого значения, которое подается на вход нашего алгоритма, мы сра- зу же вычисляем ˜ x как x mod t . Во всех внутренних вычислениях нашей библиотеки выражения над большими числами будут дублироваться анало- гичными выражениями над значениями WOOP. Следовательно, мы сможем подсчитать WOOP результата выражения, подставив в него значения WOOP входных чисел, а не применяя функцию WOOP к конечному результату вы- ражения, как при выполнении операции взятия по модулю. Обычная операция сложения выполняется как c := a + b . Мы, в свою очередь, можем вычислить ˜ c , используя равенство ˜ c = ˜ a + ˜ b (mod t ) . Анало- 2 На русский язык слово “wooping” (или “whooping”) можно перевести как “вопль”, “улю- люканье” или “приступ кашля”. Действительно, такое название могло родиться только в пы- лу жарких споров. — Прим. перев. 16.1. Арифметика больших чисел 305 гичным образом можно продублировать и операцию умножения. Мы можем проверять правильность ˜ c после каждого сложения или умножения, опреде- ляя, выполняется ли соотношение c mod t = ˜ c . Впрочем, гораздо эффектив- нее проводить все эти проверки в самом конце. Выполнять операцию сложения по модулю n лишь немного труднее, чем обычную операцию сложения. Вместо того чтобы просто записать c = ( a + b ) mod n , мы представляем это как c = a + b + k · n , где число k выбрано таким образом, что результат c находится в диапазоне 0 , . . . , n − 1 . Это всего лишь другой способ записи взятия числа по модулю. В данном случае k равно 0 или − 1 при условии, что числа a и b лежат в диапазоне 0 , . . . , n − 1 . Соответствую- щее выражение с использованием вупинга выглядит как ˜ c = (˜ a +˜ b +˜ k · ˜ n ) mod t . Отметим, что внутренняя реализация операции сложения по модулю “знает” k . Нам необходимо лишь получить от библиотеки значение k , чтобы можно было вычислить ˜ k . Умножение по модулю выполнить гораздо сложнее. В этом случае нужно снова записать c = a · b + k · n . Чтобы вычислить ˜ c = ˜ a · ˜ b + ˜ k · ˜ n (mod t ) , мы должны знать ˜ a, ˜ b, ˜ n и ˜ k . Первые три числа у нас уже есть, а вот значение ˜ k нужно каким-то образом извлечь из функции умножения по модулю. Это можно сделать при создании библиотеки “с нуля”, однако модифицировать существующую библиотеку будет весьма сложно. В качестве универсально- го решения можно предложить следующее: вычислить a · b , а затем поде- лить полученный результат на n , используя деление “в столбик”. Полученное частное и будет тем самым значением k , которое необходимо для вычисления WOOP ( k ) . Остаток от деления — это результат c . Единственным недостатком универсального метода является крайне медленная скорость его выполнения. Применив вупинг к операции умножения по модулю, это несложно сде- лать и для операции возведения в степень по модулю. Большинство функ- ций возведения в степень по модулю вычисляют результат посредством ряда обычных умножений по модулю. (Некоторые из них используют отдельную функцию возведения в квадрат по модулю, но и ее можно продублировать с помощью вупинга как обычную операцию умножения по модулю.) Доста- точно лишь сохранять для каждого большого числа x значение WOOP ( x ) и вычислять WOOP каждого произведения как произведение значений WOOP входных чисел. Как видите, алгоритмы, использующие вупинг, вычисляют WOOP резуль- тата выражения на основе значений WOOP входных чисел. Если значение WOOP одного или нескольких входных чисел окажется неверным, WOOP результата выражения практически наверняка также окажется неверным. Другими словами, ошибка хотя бы в одном значении WOOP распространится и на конечный результат. |