Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Шестнадцатеричное число принято обозначать так: 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 в двоичный вид.
Разделим 76 на 2, получим частное 38 и остаток 0.
Разделим 38 на 2, получим частное 19 и остаток 0.
Разделим 19 на 2, получим частное 9 и остаток 1.
Разделим 9 на 2, получим частное 4 и остаток 1.
Разделим 4 на 2, получим частное 2 и остаток 0.
Разделим 2 на 2, получим частное 1 и остаток 0.
Разделим 1 на 2, получим частное 0 и остаток 1.
Остаток от деления записываем в обратном порядке. Таким образом, число 76 выглядит в двоичной системе как 10011002. Этот результат можно проверить по таблице ASCII (в таблице слева приписан дополнительный 0, чтобы получить строки из четырех цифр). Выражение числа, записанного в одной системе счисления, в другой системе называется переходом к другому основанию.
Описанные выше коды обеспечивают безопасную и эффективную связь между компьютерами, программами и пользователями. Но этот онлайновый язык основан на общей теории информации, которая лежит в основе процесса коммуникации.
Первый шаг в этой теории является настолько очевидным, что его легко упустить из вида: как измерить информацию.
Такая простая фраза, как «Приложение размером 2 КБ», основана на блестящих идеях, которые впервые появились в статье «Математическая теория связи», опубликованной в двух частях в 1948 г. американским инженером Клодом Шенноном.
В этой основополагающей статье Шеннон предложил использовать слово «бит» для обозначения наименьшей единицы информации. Общая проблема, которую Шеннон рассматривал в своей работе, знакома и современным читателям. Как лучше всего зашифровать сообщение, чтобы оно не повредилось во время передачи? Шеннон пришел к выводу, что невозможно найти шифр, который предотвратит потерю информации. Иными словами, при передаче информации неизбежно возникают ошибки. Однако этот вывод не помешал поиску стандартов кодификации, которые, не имея возможности исключить ошибки, могли бы по крайней мере обеспечить высокий уровень надежности.
При цифровой передаче информации сообщение, сгенерированное отправителем (это может быть как человек, так и компьютер или другое устройство), кодируется в двоичной системе и поступает в канал связи, состоящий из компьютеров отправителя и получателя, плюс самой линии связи, которая может быть или физическим кабелем, или беспроводной (радиоволны, инфракрасное излучение и т. д.). Движение по каналу связи является особенно уязвимым процессом, потому что сообщение подвергается всевозможным воздействиям, в том числе взаимодействиям с другими сигналами, неблагоприятным температурам физической среды и затуханиям (ослаблению) сигнала при прохождении через среду. Эти источники помех называются шумами.