Математики, шпионы и хакеры. Кодирование и криптография

НЕМНОГО ЛИНЕЙНОЙ АЛГЕБРЫ

Матрица может быть определена как таблица, представляющая собой совокупность строк и столбцов. Например, матрица 2x2 имеет вид:

а матрица 2x1 записывается как:

Произведение этих двух матриц дает нам новую матрицу 2x1, называемую вектор-столбцом:

В случае матрицы 2x2 число (аd — Ьс) называется определителем матрицы.

* * *

Ограничение на значение определителя установлено для того, чтобы обратная матрица работала как инструмент расшифровки. Как правило, для алфавита из n символов необходимо, чтобы НОД определителя матрицы и числа n равнялся единице. Иначе нельзя гарантировать существование обратного элемента в модульной арифметике.

Продолжая пример, возьмем алфавит из 26 букв с символом пробела, который мы обозначим как @. Каждой букве мы поставим в соответствие число, как показано в следующей таблице:

Для получения значений от 0 до 26 мы будем работать по модулю 27.

Процесс шифрования и расшифровки текста происходит следующим образом: сначала мы определяем шифровальную матрицу с определителем 1.

Например,

Матрицей для расшифровки будет обратная матрица

Таким образом, А будет ключом шифра, А^-1 — ключом для расшифровки.

Например, зашифруем сообщение BOY («мальчик»). Буквы сообщения группируются в пары: ВО У@. Их численными эквивалентами, согласно таблице, являются пары чисел (1, 14) и (24, 26). Умножим матрицу А на каждую пару чисел.

Зашифрованное

что, согласно таблице, соответствует буквам (Q, Т).

Зашифрованное

что соответствует буквам (V, О).

Сообщение BOY будет зашифровано как QTVO.

Обратная операция расшифровки выполняется при помощи матрицы:

Возьмем пару букв (Q, Т) и найдем их числовые эквиваленты из таблицы: (16, 19). Затем умножим их на A^-1 и получим:

то же со второй парой (V, О) и ее численными значениями (21, 14) и получаем:

Таким образом, мы доказали, что расшифровка работает.

В этом примере мы рассматривали пары символов. Для большей безопасности можно группировать буквы по три или даже по четыре. Тогда расчеты будут проводиться с матрицами порядка 3 х 3 и 4 х 4 соответственно, что было бы чрезвычайно трудоемким процессом для вычислений вручную. Современные компьютеры позволяют работать с огромными матрицами и с обратными к ним.

У шифра Хилла есть существенный недостаток: имея даже небольшой фрагмент исходного текста, можно расшифровать все сообщение. Поиск идеального шифра был еще далек от завершения.

Глава 4. Процесс общения посредством нулей и единиц

Изобретение компьютера Colossus и расшифровка кода «Энигмы» открыли путь к величайшей революции в сфере коммуникаций. Этот гигантский шаг вперед произошел в значительной степени благодаря развитию систем шифрования, что обеспечило безопасную, эффективную и быструю связь по разветвленным сетям, представляющим собой компьютеры и их пользователей — то есть нас с вами. Когда сегодня мы употребляем слово «безопасность», мы имеем в виду не только криптографию и секретность. Это слово имеет более широкий смысл, который включает в себя понятия надежности и эффективности.

Двоичная система является основой технологической революции. Этот суперпростой код, содержащий лишь два символа, 0 и 1, используется в цифровых устройствах из-за его способности представлять состояние электронных схем: единица означает, что в контуре есть ток, ноль — тока нет. Одна двоичная цифра — 0 или 1 — называется битом.

ASCII-код

Одним из многих приложений двоичной системы является особый набор символов, состоящий из восьми битов и называемый байтом. Каждый байт обозначает букву, цифру или другой символ. Именно байты лежат в основе обычных коммуникаций.

Они называются ASCII-кодами (аббревиатура ASCII переводится как «американская стандартная кодировочная таблица»). Количество размещений (с повторениями) из двух цифр (0 и 1) по 8 (длина символа) составляет 28 = 256.

ASCII-коды позволяют пользователям вводить текст в компьютер. Когда мы печатаем букву или цифру, компьютер превращает этот символ в байт — строку из восьми битов. Так, например, если мы печатаем букву А, компьютер превращает ее в 0100 0001.

* * *

БАЙТЫ ПАМЯТИ

Емкость памяти компьютера измеряется в единицах, кратных байтам.

Килобайт (КБ): 1024 байтов

Мегабайт (МБ): 1 048 576 байтов

Гигабайт (ГБ): 1 073 741 824 байтов

Терабайт (ТБ): 1099 511627 776 байтов

* * *