Криптография

11.5.1. Сложение

Большинство современных процессоров имеют специальный признак переноса, учитывающий добавочное слагаемое к следующему разряду при побитовом сложении. Кроме того, существуют специальные функции, обычно называемые чем-то вроде addc, которые складывают два целых числа с учетом признака переноса. Так, если мы хотим сложить два 64-битовых числа х =и у =, нам нужно вычислить:

11.5.2. Умножение в столбик

Теперь обратимся к следующей простейшей арифметической операции, идущей после сложения и вычитания, а именно, к умножению. Заметим, что при умножении двух 32-битовых чисел получится 64-битовое, и, естественно, большинство современных процессоров оснащено операцией, осуществляющей это действие.

11.5.3. Умножение Карацубы

Один из методов ускорения умножения носит название умножения Карацубы. Предположим, нам нужно перемножить два n-битовых числа х и у. Запишем их в виде

где. Умножение происходит с помощью вычислений:

11.5.4. Деление

После знакомства с умножением перейдем к самой сложной арифметической операции — делению. Оно необходимо, в частности, для определения остатков от деления двух целых чисел — основной задачи арифметики остатков, а значит и RSA.

Итак, для данных двух целых х и у чисел мы хотим найти такие q и r, что х = qy + r, причем, как обычно, 0 ≤ r < у. Напомним, что такое деление называется делением с остатком или евклидовым делением.

11.5.5. Арифметика Монтгомери

Поскольку деление больших целых чисел — операция сложная, все наши криптографические действия будут идти очень медленно, если мы будем использовать стандартный метод деления, представленный в предыдущем параграфе. Напомним, что практически все криптосистемы с открытым ключом работают с арифметикой остатков. Поэтому нам хотелось бы уметь вычислять остатки от деления, не прибегая к дорогостоящей операции деления. На первый взгляд это кажется невозможным, но если прибегнуть к специальной арифметике Монтгомери, то все окажется не так страшно.

11.6. Арифметика в конечных полях

Кроме полей вычетов по простому модулю р в криптографии используются поля четной характеристики. Такие поля встречаются, например, в алгоритме Rijndael и в некоторых системах, основанных на эллиптических кривых. В Rijndael поле настолько мало, что можно использовать поисковые таблицы или специальные микросхемы для реализации основных арифметических действий, поэтому в этом параграфе мы будем разбираться с полями над большой степени, такими, которые, например, используются в эллиптических кривых. Кроме того, нас будут интересовать только программные реализации операций. На аппаратных средствах операции в полях характеристики 2 могут реализовываться с помощью так называемых оптимальных нормальных базисов, но мы не будем здесь этого касаться.

<< [Первая] < [Предыдущая] 1 2 [Следующая] > [Последняя] >>

Результаты 1 - 56 из 67