Жуан Гомес - Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография
Следующие шесть цифр (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 рядов, для университета Осаки, Япония
Глава 5. Общедоступная тайна: криптография с открытым ключом
При быстром развитии вычислительной техники криптография вовсе не игнорировалась. Процесс шифрования сообщения с помощью компьютера почти не отличается от шифрования без компьютера, но есть три основных отличия. Во-первых, компьютер можно запрограммировать для имитации работы обычной шифровальной машины, например, с 1000 роторами, что избавляет от необходимости физически создавать такие устройства. Во-вторых, компьютер работает только с двоичными числами и, следовательно, все шифрование будет происходить на этом уровне (даже если числовая информация потом снова будет расшифрована в текст). И в-третьих, компьютеры очень быстро работают с вычислениями и расшифровывают сообщения.
Первый шифр, предназначенный для того, чтобы воспользоваться потенциалом компьютеров, был разработан в 1970-х гг. Например, «Люцифер», шифр, который разделял текст на блоки по 64 бита и зашифровывал некоторые из них с помощью сложной подстановки, а затем группировал их снова в новый блок зашифрованных битов и повторял процесс. Для работы такой системы было необходимо, чтобы отправитель и получатель имели компьютеры с одной и той же программой шифрования, а также общий цифровой ключ. 56-битная версия шифра «Люцифер», названная DES, была разработана в 1976 г. DES (Data Encryption Standard — «стандарт шифрования данных») по-прежнему используется в наши дни, хотя этот шифр был взломан в 1999 г. и заменен 128-битным AES (Advanced Encryption Standard) в 2002 г.
Без сомнения, такие алгоритмы шифрования сполна использовали вычислительную мощность компьютеров, но, как и их предшественники тысячелетней давности, компьютерные шифры по-прежнему были уязвимы, поскольку несанкционированный получатель мог перехватить ключ и, зная алгоритм шифрования, расшифровать сообщение. Этот основной недостаток каждой «классической» криптографической системы известен как проблема распределения ключей.
Проблема распределения ключей
Всем известно, что для обеспечения безопасности кода ключи шифрования должны быть защищены надежнее, чем алгоритм. Тогда возникает проблема: как безопасно распределять ключи. Даже в простых случаях это является серьезной проблемой логистики, например, как распределить тысячи шифровальных книг среди радистов большой армии, или как доставить книги в мобильные центры связи, работающие в экстремальных условиях, такие как станции на подводных лодках или штабы на линии фронта. Какой бы сложной ни была классическая система шифрования, она остается уязвимой, так как соответствующие ключи могут быть перехвачены.
Алгоритм Диффи — Хеллмана
Сама концепция безопасного обмена ключами может показаться противоречивой: как вы можете послать ключ в виде сообщения, которое уже как-то зашифровано?
Ключом, переданным заранее обычным способом? Однако, если ключами действительно несколько раз обменивались, то решение проблемы можно себе представить — по крайней мере, на теоретическом уровне.
Предположим, что отправитель по имени Джеймс шифрует сообщение с помощью своего ключа и посылает результат получателю по имени Питер, который повторно шифрует зашифрованное послание своим ключом и возвращает его отправителю. Джеймс расшифровывает сообщение своим ключом и посылает назад результат, т. е. текст, в данный момент зашифрованный только ключом Питера, который его расшифровывает. Казалось бы, вековая проблема безопасного обмена ключами решена! Неужели это правда? К сожалению, нет. В любом сложном алгоритме шифрования порядок применения ключей имеет решающее значение, а в нашем примере мы видим, что Джеймс расшифровывает сообщение, которое уже зашифровано другим ключом. Когда порядок ключей меняется, результат будет абракадаброй. Вышеизложенный пример не объясняет теории подробно, но он дает подсказку к решению проблемы. В 1976 г. два молодых американских ученых, Уитфилд Диффи и Мартин Хеллман, нашли способ, при котором два человека могут обмениваться зашифрованными сообщениями без всякого обмена секретными ключами. Этот метод использует модульную арифметику, а также свойства простых чисел. Идея заключается в следующем.
* * *
АВТОРЫ АЛГОРИТМА
Уитфилд Диффи родился в 1944 г. в Соединенных Штатах. Получив степень бакалавра математики в Массачусетском технологическом институте (МП), он с 2002 по 2009 гг. работал главой службы безопасности и вице-президентом компании Sun Microsystems (в Калифорнии).
Инженер Мартин Хеллман родился в 1945 г. и работал в IBM и Массачусетском технологическом институте, где сотрудничал с Диффи.
Уитфилд Диффи
* * *
1. Джеймс выбирает число, которое он держит в секрете. Мы обозначим это число Nj1
2. Питер выбирает другое случайное число, которое он тоже держит в секрете. Мы обозначим это число Np1
3. Затем и Джеймс, и Питер применяют к своим числам функцию вида f(x) = ах (mod р) где р — простое число, известное им обоим.
∙ После этой операции Джеймс получает новое число, Nj2, которое он посылает Питеру.
∙ А Питер посылает Джеймсу свое новое число Np2
4. Джеймс вычисляет NNj1p2 (mod р) и получает новое число Сj.
5. Питер вычисляет NNp1j2 (mod р) и получает новое число Ср.
Хотя это кажется невозможным, но числа Сj и Ср являются одинаковыми. И теперь у нас есть ключ. Заметим, что Джеймс и Питер обменивались информацией только тогда, когда они выбрали функцию f(x) = ах (mod р) и послали друг другу числа Nj2 и Np2. Ни то, ни другое не является ключом, поэтому перехват этой информации не будет угрожать безопасности системы шифрования. Ключ этой системы имеет следующий вид:
