Модулярная арифметика

Простой XOR

Перестановочные шифры

В перестановочном шифре (или шифре перестановки) открытый текст остается неизменным по составу символов, но символы в нем перемешиваются по определенным правилам.

Так в простом вертикальном перестановочном шифре открытый текст пишется по горизонтали на разграфленном листе бумаги фикс. ширины, а шифротекст считывается по вертикали. Например:

Открытый текст: КОМПЬЮТЕРНАЯ ГРАФИКА ТРЕБУЕТ РЕСУРСОВ

КОМПЬЮТЕРН

АЯГРАФИКАТ

РЕБУЕТРЕСУ

РСОВ

Шифротекст: КАРР ОЯЕС МГБО ПРУВ ЬАЕ ЮФТ ТИР ЕКЕ РАС НТУ

Применение к шифротексту второго перестановочного шифра значительно усиливает защиту.

Перестановка используется во многих современных алгоритмах. Ее недостаток – требует больших объемов памяти.

XOR- логическая операция, которая часто применяется в шифровании и простейший шифр.

XOR представляет собой операцию «исключающее ИЛИ», в математике обозначается символом Å. Таблица истинности для XOR.

0 Å 0 = 0

0 Å 1 = 1

1 Å 0 = 1

1 Å 1 = 0

Также отметим, что

a Å a = 0 a Å b Å b = a

Если рассматривать XOR как алгоритм шифрования, то это симметричный алгоритм. Для генерирования шифротекста открытый текст подвергается операции XOR с ключевым словом. Повторное применение к шифротексту операции XOR с ключевым словом восстанавливает оригинал:

P Å K = C

C Å K = P

Реальной защиты этот алгоритм не обеспечивает, но тем не менее используется в некоторых коммерческих программных продуктах.

Иногда ее называют «арифметикой вычетов» или «арифметикой часов». Простейшие примеры модульной арифметики, это примеры с часами. Например, если мы прибавим к 23 часам 2 часа, то получим 1 час. Записывается этот так:

(23+2) mod 24 = 25 mod 24=1 mod 24

Еще пример. Во многих странах не принято для времени использовать 24 часа, используют 12-часовую систему (только добавляют a.m. – до полудня или p.m – после полудня). В данном случае имеем вычисление по модулю 12.

Например, если мы к 10 часам прибавим 13, то получим

(10+13) mod 12 = 23 mod 12 = 11 mod 12

Другой способ записать это: 10 + 13 º 11 (mod 12)

º - знак тождества, обозначает сравнимость

В общем случае, a º b (mod n), если a = b + kn при некотором целом k. Если а неотрицательно, а b находится между 0 и n, можно рассматривать b как остаток отделения a на n.

b называют вычетом по модулю n, а называют сравнимым с b по модулю n

Операция a mod n обозначает вычет от a, равный некоторому целому числу от 0 до n-1

Т.е., например 15 mod 12 = 3 (3 – вычет от 15 по модулю 12)

Одноразовые блокноты – единственный абсолютно надежный метод шифрования. Классический одноразовый блокнот – это огромный не повторяющийся случайный набор символов ключа, написанных на листах бумаги и склеенный в блокнот (конечно же, это может быть и не блокнот, а, например, телетайпная лента). Отправитель использовал каждый символ ключа в блокноте для шифрования только одного символа открытого текста. Шифрование представляет собой сложение (по модулю 32 для русского алфавита) символа открытого текста и символа ключа из одноразового блокнота.

Каждый символ ключа используется только один раз и только в одном сообщении. Закончив шифровать сообщение, отправитель уничтожает использованные страницы блокнота. В свою очередь получатель, используя точно такой же блокнот, дешифрует каждый символ шифротекста. Дешифровав сообщение он уничтожает соответствующие страницы блокнота. Таким образом, каждое новое сообщение использует новые символы ключа.

Например, если слово АРБУЗ, а ключевая последовательность ВЯЕКТ, то шифротекст будет выглядеть так: ГРЗЮХ, поскольку

А + В mod 32 = Г

Р + Я mod 32 = Р и т.д.

Если исключить доступ злоумышленника к одноразовому блокноту, использованному для шифрования, эта схема шифрования будет абсолютно надежной, так как случайная ключевая последовательность суммированная с неслучайным открытым текстом, генерирует случайный шифротекст. Во избежание возможности взлома, ключевую последовательность нельзя использовать повторно.

Идея одноразового блокнота без труда переносится на двоичные данные. Просто теперь, вместо одноразового блокнота, состоящего из букв, используется одноразовый блокнот из битов, а вместо сложения – операция XOR. Для дешифрования операция XOR применяется к шифротексту с тем же ключом (свойство a Å b Å b = a).

Недостатоки данного метода шифрования:

- Необходимо обеспечение действительно случайной ключевой последовательности, что довольно сложно обеспечить технически.

- Так как ключевые биты не должны повторяться, длина ключевой последовательности должна быть равна длине сообщения. Поэтому, одноразовый блокнот удобен только для шифрования небольших сообщений.

С помощью одноразовых блокнотов зашифрованы многие сообщения советских разведчиков. Эти сообщения не раскрыты до сих пор, и таковыми останутся на всегда.

Дата добавления: 2014-01-07