Модульная алгебра - это довольно важный раздел, касательно информационной безопасность, а именно криптографии. И не смотря что курс теории чисел и модульной арифметики на кафедре СИБ довольно хорош, многие не всегда могут вспомнить некоторые нюансы, которые в будущем могут облегчить жизнь. Более того, я увидел что в ВГУ также "увлекаются" криптографией, и RSA (http://fkn.ktu10.com/?q=node/4214) и так как при реализации нужно возводить число в очень большую степень а потом находить остаток от деления на другое (модуль) из-за чего приходится использовать либо слишком малые блоки либо работать с большими числами (http://fkn.ktu10.com/?q=node/4233).
В реальности, же, многие устройства реализуют ассиметричные блочные алгоритмы шифрования, и при этом они работают с полноценными блоками и часто не используют большие числа (не всегда это возможно).
О том как возвести число в очень большую степень в модульной арифметике и при этом не повесив комп, я сегодня расскажу.
Итак, сначала математика. Потом будет алгоритм и код на python.
Мы будем работать в кольце - эта такая особая алгебраическая структура. Это знать не обязательно, главное пользоваться особым свойством, но прежде поговорим об обозначениях: стандартно пишут так: $7^4 \pmod{13}$ - это значит 7 в степени 4 по модулю 13, тоесть 7 возвести в 4 и найти остаток от деления на 13 (грубо говоря, тут математики могут меня поругать). А выражение $7^4 \equiv 9 \pmod{13}$ -это значит, что 7 в 4-й степени эквивалентно 9 по модулю 13, по сути если возвести 7 в 4-ю степень и найдя остаток деления на 13 то мы получим 9, но можем туда записать любое число которое нахождении остатка также даст 9, скажем $7^4 \equiv 100 \pmod{13}$ тоже верно - как видим образуется целый класс эквивалентных чисел - это и будем использовать (это использует RSA).
Для более краткого обозначения:
$7^4 \pmod{13}$ будем обозначать, используя стиль неописанного тут алгебраического понятия "кольца" вот так: $[7]^4_{13}$, и позволим себе наглую вольность, вместо $\equiv$ будем использовать $=$.
Рассмотрим предлагаемый алгоритм сначала на примере, потом в общем виде. Пусть нам необходимо возвести число 7 в степень..... эм..... 45 по модулю 5. Тогда делаем так:
$$
[7]^{45}_{5} = [7]_{5} * [7]^{44}_{5} = [7]_{5} * [49]^{22}_{5} = [7]_{5} * [4]^{22}_{5}
$$
Посмотрев на формулу выше, можно уже угадать алгоритм)))) Что мы тут сделали, а вот как раз воспользовались мельком оговоренном мною свойством. Давайте по шагам:
Далее, просто делаем всё по кругу:
$$
[7]_{5} * [4]^{22}_{5} = [7]_{5} * [16]^{11}_{5} = [7]_{5} * [1]^{11}_{5} = [7]_{5} * [1]_{5} = [7]_{5} = [2]_{5}
$$
К сожалению пример не очень удачный, но короткий (быстро закончился, 1 в 11-й степени это 1), а так, в конце у нас может появиться к примеру такой вот список:
$$
[7]_{5} * [4]_{5} * [3]_{5} * [2]_{5} * [1]_{5} * [2]_{5}
$$
В этом случае их попарно перемножаем и каждый раз после умножения находим остаток, к примеру:
$[7]_{5} * [4]_{5} = [3]_{5} $
Теперь более-менее общее описание алгоритма:
Вот и всё, пора показать пример на python (кому было непонятно описание выше - поможет код):
def Zpow(a, p, m): """ Функция возведения в степень по модулю принимает 3 аргумента a - сам математический аргумент, возводимое число p - степень m - модуль """ result = 1 while p > 2: # когда степень сократится до квадрата и меньше - завершаем if p % 2 == 0: # если степень кратна 2 a = (a ** 2) % m p = p // 2 # целочисленное деление (на всякий) else: result = (result * a) % m p = p - 1 a = (a ** p) % m result = (result * a) % m return result
Можете поиграть с этой функцией - она очень быстро считает, и так как в Питоне по умолчанию все числа Большие, то попробуйте вбивать самые большие числа в аргументы этой функции, какие взбредут вам в голову!!!
В Криптоусиках, также реализована эта функция - и я всячески старался повесить сервак - не получилось.
Зная сколько студентов на лабах по-программированию сломали голову с этой процедурой возведения в степень по-модулю, я думаю этот материал будет полезен.
humanmashine
Thu, 04/18/2013 - 11:49
Permalink
Кстати, а почему подсветка
!!!!!! Кстати, а почему подсветка кода не пашет?
---------------------
ДА, и вот ещё. Я набросал скрипт простенький, который можно просто запустить в python3 и попробовать эту функцию (там есть консольный интерфейс - ничего дописывать не придётся), смело вводите самые космические значения))) Скачать можно в моём репозитории, или кому лень копаться в репе, - то в zip архиве, или tar.gz .
vedro-compota
Thu, 04/18/2013 - 17:19
Permalink
ого. серьёзная статья)) надо
ого. серьёзная статья)) надо вникнуть в неё.
да, работа с большими числами это оказывается проблема
vedro-compota
Thu, 04/18/2013 - 17:23
Permalink
подсветку поправил)
подсветку поправил)
humanmashine
Thu, 04/18/2013 - 19:52
Permalink
Благодарю
Благодарю,
Я в свою очередь подправил некоторые не очевидные вещи. Возможно моё описание немного непонятно, поэтому буду рад вопросам чтобы на их основе сделать статью понятнее.