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

kIlka и AssassiN

Спецвыпуск Xakep, номер #041, стр. 041-004-3

Еще один алгоритм, базирующийся на сбалансированной сети Файстеля – RC6. Однако в нем наблюдается некоторое отступление от традиционной схемы. Блок делится не на 2 половинки, а на 4 куска. Изменяемые и неизменяемые части чередуются. Размер блока и ключа, а также число раундов могут меняться в широких пределах. Этот алгоритм, как и Rijndael, участвовал в конкурсе при принятии AES.

Криптосистемы с открытым ключом и RSA

До сих пор мы рассматривали криптографические схемы, использующие только один ключ (из-за этого их часто называют симметричными криптосистемами или криптосистемами с секретным ключом). Их общим недостатком является необходимость передачи ключа по защищенному каналу. Этого недостатка лишены системы шифрования с открытым ключом, первые теоретические наброски которых появились в 70-х годах 20 века. В них, в отличие от традиционных методов шифрования, используется не один, а два ключа – открытый (public key) и секретный (secret key). Одной из наиболее известных криптосистем такого рода является криптосистема RSA. Поразительно, что, несмотря на полную открытость алгоритма, практически невозможно за разумное время дешифровать сообщение. Это связано с тем, что в настоящее время разработаны эффективные алгоритмы нахождения больших простых чисел, и вместе с тем не создан достаточно быстрый алгоритм разложения произведения двух простых чисел на множители.

Рассмотрим механизм работы RSA. Пусть у нас ведут переговоры две личности: kIlka и AssassiN. Каждый имеет свой открытый (известный всем) и секретный (хранящийся в тайне) ключи, которые мы будем обозначать P и S соответственно с индексами K и A в зависимости от обладателя. Пусть Н – множество всевозможных посланий. Каждый ключ задает перестановку множества Н. Через PA() и SA() обозначим перестановки, соответствующие ключам AssassiN'а. Ключи таковы, что справедливы следующие равенства: M = SA(PA(M)); M = PA(SA(M)).

Шифрование алгоритмом RSA

Предположим, что kIlka пишет AssassiN'y секретное сообщение. Сначала он узнает PA, потом зашифровывает сообщение M и отправляет адресату результат C = PA(M). AssassiN получает шифровку C, а потом восстанавливает сообщение M = SA(C).

В общих чертах схема построения пары ключей для криптосистемы RSA выглядит так:

1. Выбираются два БОЛЬШИХ простых числа r и h (примерно 100 десятичных цифр в каждом).

2. Вычисляется n=r*h.

3. Выбирается небольшое нечетное число е, взаимно простое с t=(r-1)*(h-1).

4. Вычисляется d=(e^-1) mod t.

P(M) = (M^e) mod n – преобразование, соответствующее открытому ключу, S = (M^d) mod n – преобразование, соответствующее секретному ключу.