Матричные криптосистемы над кольцами вычетов

Введение 3
Глава 1. Математические основы 7
Параграф 1. Кольца вычетов 7
Параграф 2. Свободные группы конечного ранга 11
Параграф 3. Общая линейная группа GL2 (Zn) 13
Глава 2. Генерация ключей 17
Параграф 1. Алгоритм генерации ключей 17
Параграф 2. Примеры вычисления ключей 18
Параграф 3. Выбор параметров 25
Параграф 4. Сложность вычисления квадратного корня по различным модулям 28
Глава 3. Шифрование 33
Параграф 1. Алгоритм шифрования 33
Параграф 2. Примеры шифрования по различным модулям
и открытым ключам 33
Параграф 3. Возможные атаки на алгоритм шифрования 35
Глава 4. Расшифрование 37
Параграф 1. Алгоритм расшифрования 37
Параграф 2. Примеры расшифрования различных шифртекстов
с различными модулями и секретными ключами 37
Параграф 3. Возможные атаки на алгоритм расшифрования 39
Заключение 44
Список используемой литературы 46

Купить

Безопасность некоторых современных криптосистем с открытым ключом основана на вычислительной сложности нескольких задач, относящихся к теории чисел. Две из этих задач используются чаще других: задача факторизации в целых числах и задача дискретного логарифмирования. Именно эти задачи обеспечивают стойкость криптосистем RSA и Эль-Г амаля, а также основанных на них схемах формирования электронной подписи [1].
Как бы то ни было, реальный уровень вычислительной сложности этих задач неизвестен. Это значит, что они считаются трудно разрешимыми, хотя никаких доказательств тому не предоставлено.
В [2], для квантовых компьютеров уже были представлены недетерминированные алгоритмы для дискретного логарифмирования и факторизации, работающие за полиномиальное время.
Однако, можно предложить некоторые альтернативы. Один из возможных подходов - замена криптосистем на базе теории чисел на такие алгебраические криптосистемы, которые будут выдерживать атаку квантового компьютера.
Рассмотрим схему криптосистем, а именно, криптосистем на базе групповых колец.
В работах [3,4], предложены схемы криптосистем, основанных на групповых кольцах.
Идея применить групповые кольца в криптографии основана на том факте, что, если зафиксировать мощность конечного кольца R и мощность конечной группы G, то мощность группового кольца RG является степенью |R| с показателем |G|, т.е. |Я6| = |fl||G|. Тогда даже для небольших мощностей, например, |R|=100 и |G|=10, мы получаем групповое кольцо RG’ большой мощности, а именно, |^G'| = 1020. Затем авторизованный пользователь может выполнять криптографические преобразования отдельно в кольце R и в группе G с использованием полиномиальных алгоритмов, а злоумышленник должен решать сложные вычислительные проблемы в групповом кольце RG.
Рассмотрим задачу стандартизации в групповом кольце и её два аспекта. Прямой задачей стандартизации является построение стандартных автоморфизмов у группового кольца RG , из автоморфизмов а группы G и автоморфизмов Р кольца R в следующем виде: если элемент x группового кольца RG представлен в виде формальной линейной комбинации элементов gt группы G с коэффициентами r из кольца R, тогда образ элемента x под действием у является формальной линейной комбинацией образов элементов gL группы G под действием а с коэффициентами, которые являются образами коэффициентов r под действием р.
Обратная задача стандартизации сформулирована следующим образом. Для данного автоморфизма у группового кольца RG найти автоморфизм а из группы G и автоморфизм Р из кольца R, такие что у может быть построена на основе а и р таким образом, как описано в прямой задаче стандартизации или доказать, что таких автоморфизмов не существует.
Нетрудно видеть, что, в случае эффективного вычисления автоморфизма а в группе G и автоморфизма Р в кольце R, можно эффективно вычислить действие автоморфизмов у на любой элемент группового кольца RG, т. е. эффективно указать автоморфизм у из группового кольца RG.
Что касается обратной задачи стандартизации, то есть некоторые причины полагать, что эта задача является вычислительно сложной. Однако доказательств этому нет.
В некоторых обобщениях (см., например, [5]) криптосистем групповых колец рассматриваются криптосистемы квазигрупповых колец .
Следует отметить, что внутренний автоморфизм целочисленного группового кольца конечной группы, как правило, не является стандартным автоморфизмом. Именно поэтому вместе со стандартными автоморфизмами группового кольца Z G, где G - конечная группа, мы используем внутренние автоморфизмы. В [9] групповое кольцо ZS3, где S3 -группа перестановок для трех символов, представлено в матричной форме в виде блока диагональных матриц четвертой степени с двумя одномерными блоками и одним двумерным блоком. В [9,10] показано, что группа единиц группового кольца ZS3 является полупрямым произведением тривиальных единиц (+S3) и свободной подгруппы ранга 3. Поскольку матрицы четвертой степени из этой подгруппы содержат два идентичных одномерных блока, мы можем ограничиться рассмотрением свободной группы матриц второй степени с помощью свободных порождающих [9]:
А = (1 0) W1 3) (-2 3)
Д ( I, B ( ), C ( ).
'3 1 'U 1 х—3 4'
Если мы выходим за пределы матричного представления ZS3, мы рассмотрим произвольные матрицы второй степени в кольце М2 (Z) и ее группу обратимых элементов GL2(Z), которая содержит свободные подгруппы ранга 3 - G(a, Р, у) со свободными порождающими:


где а,Р,у принадлежат Z и |а|>3, |Р|>3, |у|> 3 [11]. Например, если а=Р=у=3, получаем свободную подгруппу G ранга 3 и G = G ^ (3,3,3) с вышеуказанными свободными порождающими А, В и С.
Следует также отметить, что все автоморфизмы группового кольца ZS3 являются внутренними [12].
При осуществлении вычислений с целочисленными матрицами неизбежен бесконечный рост элементов этих матриц. Поэтому вместо Z удобно рассматривать Zn, так как это позволяет проводить эффективные вычисления. Следовательно, элементы свободной группы над целыми числами становятся подгруппой M2(Zn), т.е. появляется GL2(Zn).
Таким образом, математической базой для построения криптосистем становятся кольца матриц второй степени над кольцами вычетов М2(г^п), общая линейная группа GL2 (%п) и их внутренние автоморфизмы.
Купить