Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография - Жуан Гомес

Таким образом, А будет ключом шифра, А-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 переводится как «американская стандартная кодировочная таблица»). Количество размещений (с повторениями) из двух цифр (0 и 1) по 8 (длина символа) составляет 28 = 256.

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

* * *

БАЙТЫ ПАМЯТИ

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

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

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

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

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

* * *

Двоичные ASCII-коды приведены для всех используемых в обычном обиходе символов: 26 заглавных букв, 26 строчных букв, 10 цифр, 7 символов пунктуации и некоторых специальных символов. Все они показаны в следующей таблице.

Для двоичного кода каждого символа указано соответствующее десятичное число (в столбце «Дес»):

Фразу «GOTO 2» (команду на языке программирования «Бейсик») компьютер переведет в следующую последовательность двоичных кодов:

Компьютер, таким образом, будет выполнять следующую команду:

010001110100111101010100010011110010000000110010

Шестнадцатеричная система — еще один известный код, используемый в вычислениях. Это система счисления, которая использует 16 уникальных «цифр» (отсюда и название — шестнадцатеричная), в отличие от обычной системы с десятью цифрами (десятичной). Можно сказать, что шестнадцатеричная система является вторым языком компьютеров после двоичной системы. Почему 16 цифр? Напомним, что байт, основная единица хранения информации на компьютере, состоит из восьми битов, которые дают 28 = 256 различных комбинаций из 0 и 1. А 28 = 24 х 24 = 16 х 16. Иными словами, один байт — это комбинация двух шестнадцатеричных чисел.

Шестнадцать «цифр» шестнадцатеричной системы — это традиционные цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и еще шесть символов, выбранных по соглашению: А, В, С, D, Е, F. Числа в шестнадцатеричной системе записываются следующим образом:

От 0 до 15: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А, В, С, D, Е, F.

От 16 до 31: 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 1А, 1В, 1C, ID, IE, 1F.

От 32 и дальше: 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 2А, 2В, 2С…

Эти файлы были созданы компьютером автоматически. Их странные имена — на самом деле шестнадцатеричные числа.

Шестнадцатеричные цифры не различают регистр букв (1Е означает то же самое, что и 1е). В следующей таблице приведены первые 16 двоичных чисел и их шестнадцатеричные эквиваленты:

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

Шестнадцатеричное число принято обозначать так: 9F216 (с нижним индексом 16). Напомним соответствующие двоичные коды:

9F216 = 1001111100102 (здесь нижний индекс 2 указывает, что число выражено в двоичной системе).

Давайте теперь осуществим обратный процесс: число 11101001102 состоит из десяти цифр. Мы дополняем его двумя нулями слева, чтобы получить 12 цифр, которые можно сгруппировать по четыре.

Преобразуем:

11101001102 = 0011 1010 0Н02 = 3А616.

Какая связь между шестнадцатеричными символами и ASCII-кодами? Каждый ASCII-код содержит восемь битов (один байт) информации, поэтому пять ASCII-символов содержат 40 битов (пять байтов), и так как шестнадцатеричный символ содержит четыре бита, мы заключаем, что пять ASCII-символов — это десять шестнадцатеричных символов.

Рассмотрим пример кодирования фразы в шестнадцатеричном коде. Например, возьмем название NotRealCo Ltd. Выполним следующие действия. 1 2 31. Переведем NotRealCo Ltd в двоичные коды в соответствии с таблицей ASCII.

2. Сгруппируем цифры по четыре. (Если длина двоичной строки не кратна четырем, мы добавим нули слева.)

3. Выполним замену по таблице соответствий двоичных и шестнадцатеричных символов.

Фраза NotRealCo Ltd в шестнадцатеричных символах выглядит так:

4Е 6F 74 72 65 61 6С 63 6F 20 48 74 64.

Если система счисления имеет n цифр, то число n называется основанием системы.

На руках человека десять пальцев, поэтому, вероятно, и была придумана десятичная система счисления — счет проводился на пальцах. Десятичное число, например, 7392, представляет собой количество, равное семи тысячам трем сотням девяти десяткам и двум единицам. Тысячи, сотни, десятки и единицы являются степенями основания системы счисления, в данном случае 10. Число 7392, таким образом, может быть выражено следующим образом:

7392 = 7∙103 + 3∙102 + 9∙101  + 2∙100.

Однако по соглашению принято писать только коэффициенты (в нашем примере это 7, 3, 9 и 2). Кроме десятичной системы существует много других систем счисления (на самом деле их общее число бесконечно). В этой главе мы уделили особое внимание двум из них: двоичной системе с основанием 2 и шестнадцатеричной с основанием 16. В двоичной системе счисления коэффициенты имеют только два возможных значения: 0 и 1. Разряды двоичных чисел представляют собой степени двойки. Таким образом, число 110112 может быть записано как

110112 = 1∙24 + 1∙23 + 0∙22 + 1∙21 + 1∙20.

Если мы вычислим выражение, стоящее справа от знака равенства, мы получим 27, что является десятичной формой двоичного числа 11011. Для обратного перехода мы последовательно делим десятичное число на 2 (основание двоичной системы) и записываем остатки, пока не получим частное 0. Двоичное число будет иметь в качестве первой цифры последнее ненулевое частное, а следующими цифрами будут полученные остатки, начиная с последнего. Например, переведем десятичное число 76 в двоичный вид.