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

Автор книги: Жуан Гомес

сообщить о нарушении

Текущая страница: 5 (всего у книги 8 страниц)

* * *

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

Матрица может быть определена как таблица, представляющая собой совокупность строк и столбцов. Например, матрица 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 байтов

* * *

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

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

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

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

010001110100111101010100010011110010000000110010

Шестнадцатеричная система счисления

Шестнадцатеричная система – еще один известный код, используемый в вычислениях. Это система счисления, которая использует 16 уникальных «цифр» (отсюда и название – шестнадцатеричная), в отличие от обычной системы с десятью цифрами (десятичной). Можно сказать, что шестнадцатеричная система является вторым языком компьютеров после двоичной системы. Почему 16 цифр? Напомним, что байт, основная единица хранения информации на компьютере, состоит из восьми битов, которые дают 2⁸ = 256 различных комбинаций из 0 и 1. А 2⁸ = 2⁴ х 2⁴ = 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 двоичных чисел и их шестнадцатеричные эквиваленты:

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

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

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

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

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

1110100110₂ = 0011 1010 0Н0₂ = 3А6₁₆.

Какая связь между шестнадцатеричными символами и 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∙10³ + 3∙10² + 9∙10¹  + 2∙10⁰.

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

11011₂ = 1∙2⁴ + 1∙2³ + 0∙2² + 1∙2¹ + 1∙2⁰.

Если мы вычислим выражение, стоящее справа от знака равенства, мы получим 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 выглядит в двоичной системе как 1001100₂. Этот результат можно проверить по таблице ASCII (в таблице слева приписан дополнительный 0, чтобы получить строки из четырех цифр). Выражение числа, записанного в одной системе счисления, в другой системе называется переходом к другому основанию.

Коды для обнаружения ошибок передачи

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

Первый шаг в этой теории является настолько очевидным, что его легко упустить из вида: как измерить информацию.

Такая простая фраза, как «Приложение размером 2 КБ», основана на блестящих идеях, которые впервые появились в статье «Математическая теория связи», опубликованной в двух частях в 1948 г. американским инженером Клодом Шенноном.

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

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

Одним из таких методов является избыточность информации. Он состоит в повторении при определенных критериях некоторых характеристик сообщения. Рассмотрим пример, который поможет пояснить процесс. Возьмем текст, в котором каждое слово состоит из четырех битов, общее количество различных слов – 16 (т. к. 2⁴ = 16), каждое слово имеет вид а₁а₂а₃а₄. Перед отправкой сообщения мы добавим к слову еще три бита c₁c₂c₃так что закодированное сообщение при движении по каналу связи будет выглядеть как а₁а₂а₃а₄c₁c₂c₃. Дополнительные символы c₁c₂c₃ обеспечивают надежность сообщения. Они называются контрольными битами, или битами четности, и строятся следующим образом.

Добавим следующие биты четности к сообщению 0111.

Так как сумма 0 + 1 + 1 = 2 четная, с₁ = 0.

Так как сумма 0 + 1 + 1 = 2 четная, с₂ = 0.

Так как сумма 1 + 1 + 1 = 3 нечетная, с₃ = 1.

Следовательно, сообщение 0111 будет передано в виде 0111001. Для «слов» мы, таким образом, получим следующую таблицу:

* * *

ГЕНИЙ БЕЗ НАГРАДЫ

Клод Элвуд Шеннон (1916–2001) был одним из величайших научных деятелей XX в. Получив образование по специальности «электротехника» в Мичиганском университете и Массачусетском технологическом институте, он работал математиком в лаборатории компании «Белл», где занимался исследованиями по криптографии и теории коммуникации. Его научный вклад настолько велик, что он считается одним из основоположников теории информации, но поскольку его работы были на стыке математики и информационных технологий, он так и не получил самой престижной среди ученых Нобелевской премии.

* * *

Допустим, что на другом конце сообщение будет получено в виде 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. Затем мы складываем все полученные таким образом результаты, а также цифры, расположенные на четных позициях (в том числе последнюю контрольную цифру).

3. Если окончательная сумма кратна 10 (то есть ее значение равно нулю по модулю 10), номер карты является действительным. Заметим, что именно последняя контрольная цифра делает общую сумму кратной 10.

* * *

DINER’S CLUB

Одной из первых кредитных карт, получивших широкое признание, была карта Diner's Club. Автором идеи был американец Фрэнк Макнамара. В 1950 г. ему удалось убедить различные рестораны принимать оплату безналично с помощью персональных гарантированных кредитных карт, которые Макнамара распространил среди своих лучших клиентов. Наиболее часто в первые десятилетия кредитными картами расплачивались за обеды американские коммивояжеры, будучи в дороге.

* * *

Например, пусть карта имеет следующий номер:

1234 5678 9012 3452

По алгоритму Луна имеем:

1∙2 = 2

3∙2 = 6

5∙2 = 10 => 1 + 0 = 1

7∙2=14 => 1 + 4 = 5 (или 14-9 = 5)

9∙2 = 18 => 1 + 8 = 9

1∙2 = 2

3∙2 = 6

5∙2 = 10 => 1 + 0 = 1

Далее найдем сумму результатов и цифр на четных позициях:

2 + 6 + 1 + 5 + 9 + 2 + 6 + 1 = 32

2 + 4 + 6 + 8 + 0 + 2 + 4 + 2 = 28

32 + 28 = 60

Результат равен 60, это число кратно 10. Поэтому номер карты является действительным.

Алгоритм Луна можно применить другим способом: номер карты ABCD EFGH IJKL MNOP является правильным, если удвоенная сумма цифр на нечетных позициях и сумма цифр на четных позициях плюс количество цифр на нечетных позициях, которые больше, чем 4, кратно 10. Это правило записывается так:

2 (A + C + E + G + 1 + К + М + О) + (B + D + F + H + J + L + N + P) + (количество цифр на нечетных позициях, которые больше, чем 4) = 0 (mod 10).

Применим это правило к предыдущему примеру:

1234 5678 9012 3452

2 (1 + 3 + 5 + 7 + 9 + 1 + 3 + 5) + (2 + 4 + 6 + 8 + 0 + 2 + 4 + 2) + (4) = 100  0 (mod 10).

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

* * *

ПРИМЕР РАСЧЕТА КОНТРОЛЬНОЙ ЦИФРЫ КРЕДИТНОЙ КАРТЫ В EXCEL

Номер кредитной карты состоит из 15 цифр плюс контрольная цифра. Цифры сгруппированы в четыре группы по четыре цифры. Контрольная цифра (КЦ) рассчитывается следующим образом.

* * *

Можно ли восстановить цифру, отсутствующую в номере карты? Да, если мы имеем дело с действительной кредитной картой. Найдем, например, цифру X в номере 4539 4512 03X8 7356.

Начнем с умножения на 2 цифр на нечетных позициях (4–3—4—1–0—X—7–5), сразу преобразуя результат к одной цифре.

4∙2 = 8

3∙2 = 6

4∙2 = 8

1∙2 = 2

0∙2 = 0

X∙2 = 2Х

7∙2 = 14, 14 – 9 = 5

5∙2 = 10, 10 – 9 = 1.

Складывая цифры, стоящие на четных позициях, и новые цифры на нечетных, получим:

30 + 41+ 2Х = 71 + 2Х.

Мы знаем, что число (71 + 2Х) должно быть кратно 10.

Если значение X меньше или равно 4, то для таких X (71 + 2Х) никогда не будет кратно 10.

Если же значение X больше 4, то кратно 10 должно быть выражение (71 + 2Х + 1), так как X стоит на нечетной позиции. Видим, что выражение (72 + 2Х) кратно 10 только при X = 9.

Следовательно, мы нашли потерянную цифру 9, и полный номер кредитной карты: 4539451203987356.

Штрихкоды

Первая система штрихкодов была запатентована 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  1 (mod. 10), поэтому контрольная цифра действительно 10 – 1 = 9.

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

A + C + E + G + I + K + 3∙(B + D + F + H+ J + L)  0 (mod 10).

Например, для штрихкода

5701263900544

5 + 0 + 2 + 3 + 0 + 5 + 3∙(7 + 1 + 6 + 9 + 0 + 4) + 4 = 100.

100  0 (mod 10).

Значит, штрихкод действителен.

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

401332003X497

Подставим цифры в формулу в соответствии с алгоритмом

4 + 1 + 3 + 0 + 3 + 4 + 3∙(0 + 3 + 2 + 0 + X + 9) + 7 = 64 + 3X  0 (mod 10).

По модулю 10 получим следующее уравнение:

4 + ЗХ  0 (mod 10).

ЗХ = -4 + 0 = -4 + 10  6 (mod 10).

Заметим, что число 3 имеет обратный элемент, т. к. НОД (3,10) = 1.

Отсюда видим, что X должно быть 2. Поэтому правильный штрихкод

4013320032497.

* * *

QR-КОД

В 1994 г. японская компания Denso-Wave разработала графическую систему шифрования для идентификации автомобильных деталей на сборочной линии. Система была названа QR (Quick Response – «быстрый отклик») из-за скорости, с которой информация может быть прочитана машинами, предназначенными для этой цели, и стала использоваться не только на автомобильных заводах. Всего несколько лет спустя большинство японских мобильных телефонов могли считывать информацию, содержащуюся в коде. QR-код является матричным кодом, представляющим собой некоторое количество черных и белых квадратов, расположенных в виде большого квадрата. Квадраты соответствуют двоичным значениям, 0 или 1, и, следовательно, работают аналогично штрихкодам, хотя двумерность кода позволяет хранить намного больше информации.

QR-код, составленный из 37 рядов, для университета Осаки, Япония