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

* * *

Стандарт штрихкода 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)