|
||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Алгоритм операции возведения числа в степень по модулюЭтот алгоритм является одной из важнейших операций в криптографических преобразованиях с открытым ключом. Для простоты рассуждений рассмотрим этот алгоритм на численном примере. Например, требуется вычислить y = ax mod P при числовом отображении y = 6181 mod 77. Во всех вычислениях степенной функции по модулю на первом шаге вводится параметр t = ë log 2 X û – целая часть log 2 X. Символы ë…û означают, выбор целой части включенного выражения. Если y = ax mod P, где: а = 6; х = 181; Р = 77, то y = 6181 mod 77. 1. На первом шаге алгоритма определяется значение целой части логарифма по модулю 2 показателя степени х (в примере х = 181) t = ë log 2 181û; 2t ≤ х = 2t ≤ 181, откуда t = 7, следовательно, 27 ≤ 181; 128 ≤ 181. 2. На втором шаге алгоритма вычисляются числа ряда Si = an, где n = 2t. В рассматриваемом числовом примере t = 7, следовательно, последний член ряда определится как S7 = a128. Таким образом, искомый числовой ряд может быть представлен следующим образом: Si → а а2 а4 а8 а16 а32 а64 а128, т.к. а = 6; Р = 77, то степенные значения ряда вычисляются по модулю Р = 77 а а2 а4 а8 а16 а32 а64 а128 6 36 64 15 71 36 64 15 при а =6 по mod Р (Р = 77) 1. После вычисления значений степенного ряда необходимо показатель степени выражения y = ax mod P отобразить в двоичной форме Х = 181 → (1 0 1 1 0 1 0 1)2; 1 0 1 1 0 1 0 1 → 27+25+24+22+20 = 128+32+16+4+1 = 181. 4. Составляется следующая таблица
В соответствии со значением отображения показателя степени «х» в двоичной форме вычисляется произведение: П = (а128 * а32 * а16 * а4 * а0) mod P = (15 * 36 * 71 * 64 * 6) mod 77 = = (14722560) mod 77 = 6 mod 77 ≡ 6. Следовательно, 6181mod 77 = 6 mod 77 ≡ 6. На рис.4 представлен фрагмент вычисления степенной функции по модули в рамках разработанной автором автоматизированной обучающей системы.
Рис.4. Пример решения задачи возведения числа по модулю. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |