Математики, шпионы и хакеры. Кодирование и криптография
Шрифт:
Штрихкоды
Первая система штрихкодов была запатентована 7 октября 1952 г. американцами Норманом Вудландом и Бернардом Сильвером. Первые версии штрихкодов отличались от сегодняшних. Вместо привычных нам линий Вудланд и Сильвер придумали концентрические круги. Впервые штрихкоды начали официально использоваться в 1974 г. в магазине города Трой, штат Огайо.
Современные штрихкоды представляют собой последовательность черных полос (которые кодируются как 1 в двоичной системе) и пробелов между ними (которые кодируются как 0). Штрихкоды используются для идентификации физических объектов. Штрихкоды, как правило, печатаются на этикетках и считываются оптическими устройствами. Это устройства, похожие на сканер, которые измеряют отраженный свет и преобразуют темные и светлые области в буквенно-цифровой код, который затем посылается
Толщина штрихов и пробелов в штрихкоде соответствует двоичным цифрам.
Code 128, Code 39, Codabar, EAN (этот стандарт появился в 1976 г. в двух версиях, состоящих из 8 и 13 цифр соответственно) и UPC (Universal Product Code — универсальный код товара, используемый в основном в США и доступный также в двух версиях из 12 и 8 цифр соответственно). Наиболее распространенной является 13-значная версия EAN. Несмотря на разнообразие стандартов, штрихкоды позволяют идентифицировать любой продукт в любой части мира быстро и без существенных ошибок.
Патент системы Вудланда и Сильвера с концентрическими кругами, предшественниками современных штрихкодов.
* * *
ПРОГРАММА В EXCEL ДЛЯ РАСЧЕТА КОНТРОЛЬНОЙ ЦИФРЫ КОДА EAN-13
Штрихкод стандарта EAN-13 — это номер из 12 цифр плюс тринадцатая цифра, называемая контрольной цифрой (КЦ). 13 цифр составляют четыре группы:
* * *
Стандарт штрихкода EAN-13
Стандарт EAN в момент создания в 1976 г. являлся аббревиатурой (European Article Number — европейский номер товара), а сейчас известен как Международный номер товара. Это наиболее устоявшийся стандарт штрихкодов, используемый во всем мире. Штрихкоды EAN обычно состоят из 13 цифр, представленных черными полосами и пробелами, вместе образующими двоичный код, который легко читать. EAN-13 изображает эти 13 цифр с помощью 30 черных и белых полос. Цифры делятся на три группы: первая, состоящая из двух или трех цифр, обозначает код страны; вторая, состоящая из 9 или 10 цифр (в зависимости от длины кода страны), указывает компанию и продукт, и третья, состоящая из единственной цифры, выступает в качестве контрольного кода. Для штрихкода ABCDEFGHIJKLM эти группы выглядят так:
Первые три цифры (АВС) обозначают код страны, производящей товар. Для России этот код может быть от 460 до 469. Для некоторых стран этот код может быть двузначным; тогда третья цифра входит в следующую группу.
Следующие шесть цифр (DEFGHI) обозначают компанию, производящую продукт. В этой группе может быть 4–6 цифр.
Остальные три цифры (JKL) означают код продукта, который был выбран компанией. В этой группе может быть 3–5 цифр.
Последняя цифра (М) — контрольный код. Чтобы вычислить его, мы должны сложить цифры на нечетных позициях, начиная с левой и без учета контрольной.
К полученному значению мы прибавим утроенную сумму цифр на четных позициях. Тогда контрольная цифра дополняет общую сумму до значения, кратного 10. Как видно, контрольный алгоритм системы штрихкодов очень напоминает правило контроля кредитных карт.
Проверим, действителен ли следующий штрихкод:
8413871003049
8 + 1 + 8 + 1 + 0 + 0 + 3•(4 + 3 + 7 + 0 + 3 + 4) = 18 + 3•21 = 18 + 63 = 81.
Правильная контрольная цифра должна быть 90–81 = 9.
Математическая модель алгоритма основана на модульной арифметике (по модулю 10) и работает следующим образом.
Для штрихкода ABCDEFGHIJKLM обозначим за N следующее значение:
A + C + E + G + I + K + 3•(B + D + F + H + J + L) = N,
и пусть n будет значение N по модулю 10. Контрольная цифра М определяется как М = 10 — n. В нашем примере 81
Предыдущий алгоритм можно сформулировать по-другому, используя в расчетах контрольную цифру. Следующий метод позволяет проверить правильность контрольной цифры, даже не вычисляя ее.
A + C + E + G + I + K + 3•(B + D + F + H+ J + L)
Например, для штрихкода
5701263900544
5 + 0 + 2 + 3 + 0 + 5 + 3•(7 + 1 + 6 + 9 + 0 + 4) + 4 = 100.
100
Значит, штрихкод действителен.
Теперь попробуем определить значение утерянной цифры в штрихкоде, а именно, цифры X в следующем коде:
401332003X497
Подставим цифры в формулу в соответствии с алгоритмом
4 + 1 + 3 + 0 + 3 + 4 + 3•(0 + 3 + 2 + 0 + X + 9) + 7 = 64 + 3X
По модулю 10 получим следующее уравнение:
4 + ЗХ
ЗХ = -4 + 0 = -4 + 10
Заметим, что число 3 имеет обратный элемент, т. к. НОД (3,10) = 1.
Отсюда видим, что X должно быть 2. Поэтому правильный штрихкод
4013320032497.
* * *
QR-КОД
В 1994 г. японская компания Denso-Wave разработала графическую систему шифрования для идентификации автомобильных деталей на сборочной линии. Система была названа QR (Quick Response — «быстрый отклик») из-за скорости, с которой информация может быть прочитана машинами, предназначенными для этой цели, и стала использоваться не только на автомобильных заводах. Всего несколько лет спустя большинство японских мобильных телефонов могли считывать информацию, содержащуюся в коде. QR-код является матричным кодом, представляющим собой некоторое количество черных и белых квадратов, расположенных в виде большого квадрата. Квадраты соответствуют двоичным значениям, 0 или 1, и, следовательно, работают аналогично штрихкодам, хотя двумерность кода позволяет хранить намного больше информации.
QR– код, составленный из 37 рядов, для университета Осаки, Япония
Глава 5. Общедоступная тайна: криптография с открытым ключом
При быстром развитии вычислительной техники криптография вовсе не игнорировалась. Процесс шифрования сообщения с помощью компьютера почти не отличается от шифрования без компьютера, но есть три основных отличия. Во-первых, компьютер можно запрограммировать для имитации работы обычной шифровальной машины, например, с 1000 роторами, что избавляет от необходимости физически создавать такие устройства. Во-вторых, компьютер работает только с двоичными числами и, следовательно, все шифрование будет происходить на этом уровне (даже если числовая информация потом снова будет расшифрована в текст). И в-третьих, компьютеры очень быстро работают с вычислениями и расшифровывают сообщения.