Секреты USA в Micro QR Code M2 (часть 3)

или

Как читать алфавитно-цифровой режим в Micro QR Code версии М3

Встроенные в Micro QR Code технологии насыщенны мифами и нереальностями. Программисты моделисты часто добавляют артефакты и/или cookies в свои наработки, которые интересно находить при расшифровке кодов и алгоритмов. А затем и самому кодировать и декодировать практически любую информацию. Рассмотрим этапы расшифровки микрокода среднего микроуровня – М3 формата алфавитно-цифрового кодирования на том же самом историческом примере, что и М2, и М4, аналогично М2 разделим сплошную фразу на четыре слова, получим: UNITED STATES OF AMERICA.

Примечание: здесь и далее информация будет
приводиться с соответствующей ссылкой на официальный нормативный документ – ISO/IEC 18004-2015 (или российский вариант – ГОСТ ИСО/МЭК 18004-2015, далее – ГОСТ)

Например, информация о максимальном количестве символов в микрокодах и просто QR Code хранится в таблице 7 ГОСТ. Дальше немножко мифической составляющей…

Программные библиотеки, в которых хранятся все алгоритмы кодирования как Micro QR Code, так и QR Code, и которые свободно распространяются во всех популярных операционных системах, принадлежат Ассоциации GAFAM (Google, Apple, Facebook, Amazon, Microsoft). Территориальная и административная принадлежность данной Ассоциации – USA (первая подсказка для 4 этапа). Именно это и было заложено как критерий при декодировании последней в слове нечетной буквы (о чем было уже рассказано для M4 и будет продублировано для М3). Разложим каждое слово на отдельный микрокод (рис. 1). Почему все буквы большие – было расшифровано в М4 и М2 и будет расшифровано для М3.

Рассмотрим пошагово алгоритмы расшифровки данных микрокодов. Для первых трех слов используется микрокод версии М2, а для четвертого – версия М3. Если автоматизировать алгоритм для одного микрокода одной версии, остальные будут требовать только изменения матрицы исходных данных и, возможно, маски. Далее, для простоты отображения математической составляющей и на данном коде, и на последующих будем использовать также продукцию Ассоциации – MS Excel.

Запускаем программное приложение. Готовим Лист Книги для работы. Делаем размерность ячеек одинаковой (например, 23 на 23 пикселя) и по горизонтали, и по вертикали (рис. 2a). Затем закрашиваем поле фоновым цветом (рис. 2b).

Если посчитать количество пикселей (квадратиков) микрокода AMERICA (рис. 1) по горизонтали и/или по вертикали, то получится матрица (табличка) размерностью 15×15. Создадим новую схему шаблон для микрокода М3 (рис. 3).

Перенесем битовую составляющую исходной матрицы первого слова AMERICA (рис. 1) на рабочую поверхности (рис. 4a). К сожалению, за долгие годы MS Excel так и не научился работать с цветом ячеек. Добавим в каждую цветную ячейку соответствующее битовое значение: белая ячейка – 0, черная ячейка – 1 (рис. 4b).

Для удобства отделим цветом индикатор служебной информации (рис. 5a) – битовая последовательность информации о формате. Чтение последовательности, как и в М4, начинается с 14 бита, т.е. последовательность чтения будет 14, 13, 12, 11, 10 и т.д.

Также отделяем цветом индикатор распознавания микрокода (рис. 5b). Полученная матрица готова для дальнейшего анализа.

Примечание: для удобства дальнейшего описания ссылок на ячейки листа перейдем от современного отображения адресов ячеек в виде R1C1 (относительные ссылки) к старому формату в виде A1 (буквенно-числовое отображение). Выбираем в Меню Файл → Параметры. В категории Формулы в группе Работа с формулами снимаем галочку напротив пункта Стиль ссылок R1C1. В результате названия столбиков должны поменяться с чисел на латинские буквы (рис. 6).

Этап 1. Служебная информация

 Перед тем как начать работать с основной рабочей областью микрокода, необходимо расшифровать служебную информацию. Пример итогового результата приведен на рисунке 7.

Сначала переводим служебную информацию также в бинарное представление, т.е. ряды ячеек E12-L12 и L5-L12 представляем как набор 0 (светлые ячейки) и 1 (темные ячейки) (рис. 7).

Выносим служебную информацию из микрокода, т.е. дублируем полученный ряд в угловом представлении и в представлении – один ряд. Получаем следующие ссылочные ячейки:

Воспользуемся рядом бит служебной информации 14 строки для определения версии и уровня микрокода, а также для получения вида используемой в данном коде маски. Сначала найдем соответствие в таблице ГОСТ, потом сделаем самопроверку.

Объединяем ячейки T16-AH16 в единую. В полученную новую ячейку T16 добавляем функцию (рис. 7):

=СЦЕП(T14:AH14)

По таблице С.1 ГОСТ (табл. 1) находим битовую последовательность информации о формате и соответствующую последовательность бит данных до маскирования. Для данного примера – 10010.

Проверим полученный результат. Заполняем ячейки в соответствии с таблицей:

Воспользуемся алгебраической функцией XOR для получения версии и уровня микрокода, и кода маски. Заполняем ячейки восьмой строчки:

В результате получаем последовательность 10010, полностью соответствующую полученной по таблице ГОСТ. Расшифруем полученную комбинацию. Разделим на две части: 100 и 10 (3 и 2 бита соответственно). Обратимся к таблице 13 ГОСТ (табл. 2).

Таблица 2 – Номер символа для Micro QR Code

Получаем, что в данном микрокоде используется версия М3, уровень M, т.е. комбинация M3-M. Запомним, на последующих этапах данная информация пригодится.

Разбираем вторую часть служебной информации, комбинацию маски 10. Обратимся к рисунку 22 ГОСТ. Перенесем маску с соответствующим битовым кодом на Лист, начиная с ячейки AJ4 (рис. 8).

Аналогично основной матрице, каждая черная ячейка обозначена как 1, а каждая белая – 0.

 Все необходимые данные на основе служебной информации получены, переходим ко 2-му этапу.

Этап 2. Расшифровка данных основной рабочей области

 На основе матрицы исходных данных в диапазоне ячеек D4:R18 и матрицы маскирования в диапазоне ячеек AL4:AZ18 получаем матрицу немаскированных данных в диапазоне ячеек D20:P32 с использованием функции XOR. Пример готового результата представлен на рисунке 9.

В ячейке M23 добавлена следующая формула:

=БИТ.ИСКЛИЛИ(M5;AU5)

Далее за нижний правый угол выделенной ячейки (магический квадрат) дублируем данную формулу на всю поверхность рабочей матрицы. В результате получаем немаскированный вариант для диапазона ячеек M23:R36 и E31:K36.

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

На основе таблицы 13 ГОСТ (табл. 2) определили, что в данной матрице используется формат и уровень M3-M. Обратимся к рисунку 11 ГОСТ, получаем, что маршрут будет представлен следующей схемой (рис. 10).

Перенесем маршрут на Лист MS Excel, начиная с ячейки AL22, где каждую ячейку подпишем соответствующим числовым значением.

Примечание: приведенный в ГОСТ маршрут для M3-M неверный. Если присмотреться внимательнее, то оба маршрута (M3-M и M3-L) дублируют друг друга и не вносят изменения. Данная ошибка не исправлена далее в алгоритме. Приводится маршрут для M3-M с точки зрения разработчиков бесплатного программного модуля Ассоциации.

Результат представлен на рисунке 11.

Напомню: не обязательно каждую ячейку прописывать вручную. MS Excel умеет строить прогрессии. Например, заполняем ячейки AZ36 и AZ35 значениями 1 и 3 соответственно. Затем выделяем заполненные ячейки AZ36: AZ35 и за магический квадратик выделенного диапазона (нижний правый угол ячейки) тянем до ячейки AZ23. В результате весь ряд будет заполнен. Остальное рабочее поле можно заполнить аналогичным образом.

Начиная с ячейки V22 в диапазоне ячеек V22:AF31 делаем шаблон-заготовку для последующего наполнения битовой комбинацией в буквенно-цифровом режиме. Пример полученного результата представлен на рисунке 12 (цветовая дифференциация произвольная).

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

Этап 3. Преобразование кода в набор символов

 В системе QR Code (в том числе и Micro QR Code) существует несколько разновидностей кодирования: числовой, алфавитно-цифровой, байтовый, кандзи, структурированное соединение и FNC1. Самые простые – числовой (число определенной длины из цифр 0..9) и алфавитно-цифровой (табл. 3).

Таблица 3 – Кодирование/декодирование для алфавитно-цифрового режима (Таблица 5 ГОСТ)

В данной таблице есть особенность – используется исключительно латиница верхнего регистра, т.е. большие буквы. Особенность не простая. Данную систему кодирования придумала и эффективно использовала команда разработчиков в 50-60-е годы при переходе от печатных машинок к электронным печатным машинкам. Встроенная система кодирования имеет скрытый алгоритм преобразования (а это вторая подсказка для ребуса 4 этапа).

Воспользуемся п. 7.4.4 ГОСТ для автоматизации преобразования битовых последовательностей в буквы латинского алфавита. Пример итогового варианта представлен на рисунке 13.

Сначала перенесем таблицу 3 на рабочий Лист MS Excel. Начиная с ячейки B38 в выделенном диапазоне B38:AT39 просто переносим всю последовательность символов в две строки (рис. 13).

Как было упомянуто ранее, битовые комбинации в диапазон ячеек V22:AF31 можно перенести вручную (простой вариант). Но можно и автоматизировать. Таблица функций заполнит битовые ячейки автоматически (табл. 4).

 Воспользуемся алгоритмом, приведенным п. 7.4.4 ГОСТ.

1.    Объединим ячейки битовых комбинаций в одну в каждой строчке.

2.    Переводим полученную двоичную кодовую комбинацию в десятичный формат.

3.    Находим код первой буквы закодированного слога.

4.    Находим код второй буквы закодированного слога.

5.    По полученной кодовой позиции получаем декодированный символ.

6.    Добавляем служебную информацию.

В ячейке V23:W23 спрятана битовая комбинация – 01, обозначение буквенно-цифрового режима (табл. 2 ГОСТ). В ячейках X23:AA23 спрятана битовая последовательность количества символов. В полученном значении в ячейке AE23 – 7 символов (что полностью соответствует исходным данным).

В результате получена комбинация из последовательности букв латинского алфавита:

AMERIC

или

Americ

Этап 4. Декодирования последней буквы нечетной последовательности

 С одной стороны, скрытая система кодирования была разработана теми же авторами, что и предыдущий буквенно-цифровой режим в 50-60-е годы. Да и наименование у него достаточно известное – USA. С другой стороны, так как данная последовательность не приведена в ГОСТ (и не была раскрыта самой Ассоциацией) в явном виде дальше приведена не будет. Но будет ряд подсказок, на основе которых можно будет получить последовательность:

-     в названии USA спрятано: если в раскрытом режиме комбинировать код буквы A и буквы U, то можно получить код первой буквы скрытого алфавита, а также критерий смещения;

-     в названии USA спрятано: если к коду буквы S в известном режиме добавить код неизвестного режима и вычесть код новой буквы, то получим, что это первая буква названия 51 штата (кстати, в 60-е годы так и не стал 51 штатом);

-     если к количеству символов рабочего поля уровня M1 добавить код первой буквы алфавита, можно получить первую букву имени одного из разработчиков – J;

-     код по количеству символов рабочего поля уровня M2 дает первую букву имени одного из разработчиков – K;

-     код по количеству символов рабочего поля уровня M3 дает первую букву имени одного из разработчиков – X;

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

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

В результате получена комбинация из последовательности букв латинского алфавита:

AMERICA

или

America

Удачи в декодировании Micro QR Code версии M3!!!