Аннотация.
Описаны методы реализации быстрого алгоритма RSA на цифровом
процессоре обработки сигналов (ЦПОС), разработанные в Оксфордском
университете. Получено время шифрования (в среднем) 2,5 с (для
512-битных экспоненты и модуля) на ЦПОС первого поколения (Texas
Instruments TMS 32010) и менее 1 с на изделиях второго поколения.
Используемые методы позволяют с доказательной правильностью
реализовать алгоритм. Почему выбран ЦПОС? Перед началом работы
рассматривались следующие варианты реализации: 1. Наиболее
доступный вариант - 8-разрядный микропроцессор: лучшие оценки для
512 бит составляют 4 минуты (т.е. 2 бита в секунду), что выглядит
не очень обещающе. 2. 16-разрядный микропроцессор делает это за
50 с - всг равно медленно. 3. Дискретная логика - слишком сложно
и громоздко. 4. Система на базе разрядного кристалла дорога в
разработке и во внедрении. 5. Заказной/полузаказной чип дгшево
произвести, но дорого разработать и весьма сложно запустить в
массовое производство, которое делало бы это производство
экономически оправданным. С учгтом большого числа возведений в
степепнь в RSA была рассмотрена возможность применения
специализированных схем типа "умножитель/накапливающий сумматор"
(У/НС). 6. У/НС требует для 16х16-умножения 100 нс, доступен и
выглядел многообещающим. Однако мы быстро поняли, что потребуется
специальная схемная часть для управления и подачи входных данных.
Конечно, обычный микропроцессор не справится с характеристиками
У/НС. В это время "Texas Instruments" объявили о разработке
нового чипа - ЦПОС. 7. ЦПОС - это объединенгнные на одном чипе
У/НС и быстродействующий микропроцессор. Первой разработкой был
TMS320 с временем цикла 200 нс для большинства команд, включая
умножение. По нашим оценкам эта схема могла произвести возведение
в степень за 5 с. Реализация Для ЦПОС необходимо разработать
программу. Проблема состоит в отсутствии подходящих компиляторов
для ЦПОС, а оптимизация ассемблерного кода хотя и возможна, но не
служит хорошим выходом. Кроме того, выбор метода реализации
диктует учгт характера применения и требования целостности. Ввиду
этого были выбраны методы разработки и проверки программ,
предложенные проф. Д.Грисом (D.Gries) из Корнуэльского
университета. Используемая система обозначений представляет собой
сочетание предикативной логики и специального (guarded command)
типа вычислений Е.Дийкстра (E.Dijkstra). Алгоритм В нашей системе
обозначений алгоритм RSA можно определить в терминах пре- и
пост-условий (pre/post conditions): spec fastexp.0 (in: A,E,M;
out: c); {pre: 0<=A=m - x :=x-m od {x=w mod m} endproc Видно, что
для больших n такой метод приведения по модулю требует столько же
времени, что и для двух длинных умножений. Действительно, мы
можем улучшить вдвое результат, рассчитывая только половину
произведения при каждом длинном умножении, так как вторая
половина каждого произведения не требуется. Таким образом, помимо
небольших затрат на расчгт обратной величины R (которую можно
рассчитать предварительно и хранить с соответствующим М как часть
ключа RSA) вычисления с модулем не намного медленнее длинного
умножения. Продолжение алгоритма FASTEXP Вернгмся к алгоритму
высокого уровня Fastexp. Если мы представим экспоненту Е как
последовательность n по основанию b цифр, где b=2 , то от
алгоритма потребуется два вложенных цикла, связанных
соответственно с цифрами и разрядами Е. Пропустив пару шагов
усовершенствования, процедура fastexp примет вид как на рис.6.
Рис.6. Процедура fastexp.4. proc fastexp.4 (in: A,E,M; out: c);
{pre: 0<=A0, и декрементировать AR1 ENDL1 TBLW ONE "Cо :=1" ZAC
SACL I "i:=0" * LOOP2 LACK Е0 Е0 - это относительный XRAM-адрес
Е0 ADDS DATA0 ADDS I TBLR EI "EI:=Ei" LACK F SUBS ONE SACL J
"j:=f-1" * LOOP3 ZALS EI AND ONE "ACC:=EIо" BZ LSB0 "if ACC=0 -
skip" (в LSB0) "if ACC=1 - " LSB1 LACK С0 ADDS DATA0 SACL X
X:=адрес Cо CALL LONMUL "вызвать longmult(C)" CALL LONMOD
"вызвать longmod(C)" * LSB0 LACK A0 ADDS DATA0 SACL X X:=адрес Aо
CALL LONMUL "вызвать longmult(A)" CALL LONMOD "вызвать
longmod(A)" * LAC EI,15 SACH EI "EI:=EI div 2" ZALS J SUBS ONE
SACL J "j:=j-1" BGEZ LOOP3 повторять LOOP3, пока j>0 ENDL3 ZALS I
ADDS ONE SACL I "i:=i-1" SUBS NE BLZ LOOP2 повторять LOOP3, пока
i Используемая литература: Garrick St., London WC2, UK.
