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

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

Ошибочное слово (1010110) отличается от другого слова (1000110) одной цифрой. Так как эта разница наименьшая, система предложит получателю этот второй, исправленный вариант. Аналогичный принцип использует программа контроля правописания текстового редактора. При обнаружении слова, которое не содержится в ее внутреннем словаре, программа предлагает ряд близких альтернатив.

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

В теории информации, как и в любой другой области, одно дело — обнаружить возможные ошибки, и совсем другое — исправить их. В шифровании, как в последнем примере, если имеется только один кандидат с наименьшим расстоянием, проблема достаточно проста. Пусть t— минимальное количество раз, когда единица появляется в последовательности цифр (исключая последовательность, где все нули), тогда:

Если t— нечетное, мы можем исправить (t— 1)/2 ошибок.

Если t— четное, мы можем исправить ( t— 2)/2ошибок.

Если наша цель заключается только в обнаружении ошибок, максимальным количеством ошибок, которые мы можем обнаружить, будет I— 1. В языке из 16 символов, описанном выше, t= 3, значит, наш метод способен обнаружить 3–1 = 2 ошибки и исправить — (3–1): 2 = 1 — одну ошибку.

* * *

КРИПТОГРАФИЯ ТРЕТЬЕГО ПОКОЛЕНИЯ

В 1997 г. был введен протокол для надежной передачи информации с помощью беспроводных сетей под названием WEP (сокращение от Wired Equivalent Privacy). Этот протокол включает алгоритм шифрования RC4 с двумя типами кодирования 5 и 13 ASCII-символов соответственно. Мы имеем дело, таким образом, с кодированием 40 или 104 битов или, другими словами, 10 или 26 шестнадцатеричных символов:

5 ASCII-символов = 40 битов = 10 шестнадцатеричных символов;

13 ASCII-символов — 104 битов = 26 шестнадцатеричных символов.

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

На самом деле реальные ключи длиннее. Используя ключ, выбранный пользователем, алгоритм RC4 генерирует новый с большим количеством битов, который и используется для шифрования передаваемых данных. Это — криптография с открытым ключом, и о ней будет более подробно рассказано в пятой главе. Пользователь, который желает поменять ключ, должен помнить, что ключ из десяти шестнадцатеричных символов более надежен, чем ключ из пяти букв и цифр, хотя битовый размер у них одинаковый. Однако очевидно, что слово james легче запомнить, чем его шестнадцатеричный эквивалент «6A616D6573».

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

Кредитные карты

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

Большинство карт имеет 16 цифр от 0 до 9. Числа сгруппированы по четыре цифры, чтобы их легче было прочитать. Для наших целей мы будем обозначать их следующим образом:

ABCD EFGH IJKL MNOP

Каждая группа цифр кодирует определенную информацию: первая группа (ABCD) идентифицирует банк (или любой другой субъект, оказывающий услуги).

Каждый банк имеет свой номер, который может меняться в зависимости от континента, а также от бренда карты и условий. Пятая цифра (Е) соответствует типу карты и указывает, какое финансовое учреждение управляет счетом.

Как мы видим, это не жесткое правило.

Следующие десять цифр (FGH IJKL MNO) являются уникальным идентификатором для каждой карты. Эти числа связаны с номером счета клиента, с уровнем карты — Classic, Gold, Platinum и т. д., а также с кредитным лимитом, сроком действия и процентными ставками по типу баланса.

Наконец, контрольная цифра (Р) связана с предыдущими цифрами в соответствии с алгоритмом Луна.

В России первые шесть цифр номера карты (ABCDEF) являются банковским идентификационным номером (БИН). Первая из этих шести цифр указывает на платежную систему. Например, у карт Visa первая цифра — 4, у MasterCard — 5.

Седьмая и восьмая цифры номера карты (GH) уточняют, в рамках какой программы банка была выпущена карта. Следующие семь цифр (IJKL MNO) идентифицируют непосредственно карту. Последняя цифра (Р) — контрольная.

Алгоритм Луна назван так в честь Ганса Питера Луна, немецкого инженера, разработавшего его. Для 16-значной карты этот алгоритм работает следующим образом.

1. Каждую цифру в нечетной позиции, начиная с первого числа слева, мы умножаем на два. Если результат больше 9, мы складываем обе цифры этого двузначного числа (или, что то же самое, вычитаем из него 9). Например, если мы получили 18, сложение цифр дает 1 + 8 = 9, а вычитание — 18 — 9 = 9.

2. Затем мы складываем все полученные таким образом результаты, а также цифры, расположенные на четных позициях (в том числе последнюю контрольную цифру).