Дешифруем PDF417 без подсказок


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


Сегодня я хочу рассказать о коде, который регулярно можно увидеть в аэропортах, а если точнее — на посадочных талонах. Герой этой истории — код PDF417. Давайте посмотрим, можно ли расшифровать такой код вручную и без подсказок? Какой информацией нужно обладать для этого? Сколько на это понадобится времени? Всё это и множество другого ждёт вас в данной публикации. Начнём!


Внимание, под катом — 30 изображений общим размером в 16.3 МБ.





Оглавление


Оглавление

Часть 01. Первое знакомство
01. Вступление и о повествовании
02. Базовая информация
03. Применение PDF417 кодов
04. Позиционируем данные
05. Добавляем новых PDF417
06. Уточняем позиционирование
07. Метод подбора
08. Построчный анализ


Часть 02. Первый словарь
09. Получение всех возможных слов
10. Словарь v0-01 и "неправильный" код
11. Другие авиалинии & v0-02
12. Ещё пара кодов TA & v0-03
13. Сервисные слова & v0-04 & v0-05
14. Снова другие авиалинии & v0-06
15. Исправляем свои ошибки
16. Все оставшиеся коды & v0-07


Часть 03. Новых кодов уже не будет
17. Дальше стоит быть умнее & v0-08
18. Строим смелые предположения & v0-09
19. Анализируем и ищем тайные последовательности
20. Новый метод записи
21. Расширенный словарь
22. Последний неизвестный номер
23. Очередное прозрение & v0-10
24. Точечные поиски & v0-11
25. Новые поиски & v0-12
26. И снова посмотрим по-новому на все возможные слова & v0-13


Часть 04. Финал
27. Поиск ошибок
28. Обделённый символ
29. Результаты
30. Послесловие





01. Вступление и о повествовании


(Назад | Оглавление | Вперёд)


Первый вопрос, на который я сразу же хочу ответить, — "Зачем это нужно?". Ответ достаточно прост — в какой-то момент мне было скучно и я задумался. А после — не мог остановиться.


Данная история покажет, как и в какой последовательности я определял части разных PDF417 кодов. Естественно, не все предпринятые мной шаги были рациональными или принесли какой-либо результат. Однако, ещё в самом начале я решил, подсматривать в ответ — не так интересно, как промучиться во много раз больше и убить гору времени даже не на стопроцентный результат.


Весь рассказ поделен на разделы, согласно этапам. Если какой-то из них покажется вам слишком многословным, просто переходите к следующему.





02. Базовая информация


(Назад | Оглавление | Вперёд)


Итак, PDF417 коды печатают на всех посадочных талонах при регистрации в аэропорту. Кроме того, именно их присылают по электронной почте при самостоятельной регистрации онлайн. Иногда такие коды получают и при регистрации через мобильные приложения авиакомпаний, но в таких случаях чаще используют более компактные коды.


Начнём с кода #01 одного из моих посадочных талонов авиакомпании UIA (Рис. 1). Это небольшое TIFF изображение. Его наименьший элемент — прямоугольник 2 х 4 пикселя. Назовём его символом. Код состоит из 6 блоков шириной в 17 и высотой в 12 символов. В каждом блоке первый символ — заполненный, а последний — пустой.




Рис. 1. Пример стандартного PDF417 кода прямиком с одного из моих посадочных талонов (#01)


Присмотревшись к любому блоку, можно заметить, что строка в нём — набор из 4 заполненных и 4 пустых последовательностей символов, общей длиной в 17 символов. Разгадка названия кода оказалась весьма прозаичной — это параметры одного блока информации. Такую последовательность из 17 символов будем называть словом.


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


Если сравнить несколько разных PDF417 кодов одного перевозчика (Рис. 2), можно выяснить, что первый и последний блоки в них всех одинаковы. Очевидно, они содержат сервисную информацию или же параметры записи данных.




Рис. 2. Пять разных PDF417 кодов с посадочных талонов одной авиакомпании (#01: #05)





03. Применение PDF417 кодов


(Назад | Оглавление | Вперёд)


Данные коды посадочных талонов проверяют перед тем, как пустить вас на рейс. В таком случае, код должен содержать как минимум номер рейса. Последний представляет из себя комбинацию 2 букв (код авиакомпании) и 4 цифр (порядковый номер рейса). Если порядковый номер меньше тысячи, его иногда указывают без 0 вначале. В итоге, в каждом коде должно содержаться 5-6 символов, ответственных за номер рейса.


Кроме того, всегда перед посадкой в самолёт проверяют ваши документы (а иногда ещё и переспрашивают ваше имя, особенно когда прочитать его не так просто). Есть два варианта, где взять эту информацию:


  • Имя содержится прямо в коде;
  • В коде есть номер билета, а все данные о пассажире получают по этому номеру онлайн.

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


Для упрощения, предположим, что имя на самом деле зашифровано прямо в коде. В моем случае — это 18 символов. Поскольку необходим ещё и разделитель между именем и фамилией, то все 19.





04. Позиционируем данные


(Назад | Оглавление | Вперёд)


Поскольку я не знаю, как именно информация записана в коде, попробуем найти области одинаковых слов в разных кодах (Рис. 3).


Далее я буду называть слова по их положению в коде, указывая вначале индекс ряда, а после слеша — индекс слова в ряду. Последовательность рядов или слов объединяются двоеточием.


В каждом из 5 кодов содержится 14 одинаковых слов вначале (0/0: 3/1) и ещё 9 слов разбросаных по коду (5/2:3, 6/1, 7/0:1, 8/0, 9/1:3). То есть 25 слов, общих для всех посадочных талонов. При этом, слова 9/1:3 одинаковые. Возможно, они просто показывают конец полезной информации в коде, поскольку далее все слова во всех пяти кодах разные.


Итак, у нас есть достаточно длинный набор из 14 тех же слов в каждом случае. Предположим, здесь спрятано имя. Кроме того, там должен быть минимум один разделитель — между именем и фамилией. Возможно, есть также и второй — в конце, чтобы отделить остальную информацию. Поскольку каждое слово точно не может содержать лишь один символ, оно, вероятно, содержит два. Тогда я могу поместиться в 9 слов + 1 слово разделитель.


Дальше, где-то должна быть представлена информация о рейсе. #01, #02 и #04 — это коды, соответствующие одному и тому же рейсу PS 0336, а #03 и #05 — рейсу PS 0335. Одинаковыми для этих двух групп являются слова:


  • 4/3: 5/1 (3 слова);
  • 6/1.

Поскольку нам нужно ещё и наличие 2 букв авиакомпании где-то рядом, нам подходит второй вариант, расположенный сразу после повторяющихся для всех кодов слов. Хочу обратить внимание на тот факт, что перед 6/1 присутствует сразу 3 одинаковых во всех случаях слова.


В кодах можно заметить слова, одинаковые для #02 и #03, а также другие одинаковые для #04 и #05. Это 5 слов в диапазоне 3/2: 4/2. Для этих пар общее — номер брони, состоящий из 6 символов (латиница + цифры в произвольном порядке).




Рис. 3. Построчное сравнение кодов #01: #05





05. Добавляем новых PDF417


(Назад | Оглавление | Вперёд)


Следующим шагом было добыть ещё несколько кодов с посадочных талонов для проверки части предположений. С этим мне помогла моя жена, разрешив взять данные из её посадочных талонов на рейс PS 0336 (#06) и ещё две пары PS 0335 / PS 0336 (#07: #10). При этом, #09: #10 относятся к тому же бронированию билетов, что и #04: #05. Интересен тот факт, что код #06 на одну строку короче и состоит лишь из 11 строк. Все 5 кодов приведены на Рис. 4.


Сразу можно заметить, что #06 выбивается из этой группы из-за нестыковок в правом и левом информационных блоках. При этом, им свойственна цикличность каждые 3 строки. Так каждое $3k+1$ левое и $3k+2$ правое информационное слово отличаются от других кодов ($k=0, 1, 2, ...$). Одновременно, остальные 4 из 6 слов совпадают (оба $3k$, правое $3k+1$ и левое $3k+2$). Цикличность строк можно заметить так же в том, что для строк $3k$ левое и правое слова совпадают.


Коды #07: #10 отлично подходят под все предыдущие предположения. Это касается как вероятного размещения кода бронирования, так и информации одинаковой для одного номера рейса. Кроме того, первые 14 слов кода, в которых вероятно размещается имя, тоже одинаковы для четырёх кодов.


И это всё перестаёт работать для более короткого кода #06. Конечно, не совсем всё, 13 слов в диапазоне 0/1: 3/1 остаются такими же, как и для других кодов. При этом, все остальные слова не соответствуют другим кодам. Но на данный момент нам это не важно.


Стоит отметить, что самое первое слово в коде отличается от других кодов, хотя вся остальная строка такая же. Значит это слово содержит информацию о всём коде. Возможно, размер кода (количество слов или строк).




Рис. 4. Построчное сравнение кодов #06: #10





06. Уточняем позиционирование


(Назад | Оглавление | Вперёд)


Итак, у нас есть 9 и ещё 1 код. Давайте сравним интересующие нас блоки и попробуем определить положение информации в коде. Возьмём чуть больше чем половину кода. Ту, где по моему мнению находится имя, номер брони и номер рейса (Рис. 5).


Как видно, слова 0/1:2 одинаковы для нас обоих. Потому пришлось воспользоваться тем, что я именую логикой. Где-то давно я предположил, что каждое слово может содержать 2 буквы. Если бы была всего 1 буква на слово, то в 11 букв и два разделителя поместились бы даже не все фамилии жителей Земли. Если 3 или больше — в моём коде наблюдались бы одинаковые слова для большого количества "пробелов" (пустых символов) перед началом следующей значимой информации кода.


Для нас двоих совпадают только 2 первые буквы в именах, а фамилии разные. При этом в моём коде слова 1/0 и 1/2 одинаковы. Предположив, что метод передачи данных в одной строке одинаков, это означает повторение двух пар символов, разделённых ещё одной парой. Это было не сложно.


Итак, фамилия пасажира начинается со слова 0/3. После неё, вероятно, идёт разделитель, а потом — имя и ещё раз разделитель. В таком случае, максимум информации о пасажире в подобном коде — 20 символов, а минимум 2 символа — разделители. Но пока оставим имя в покое.


Следующая часть кода, предположительно, номер бронирования. Этому свидетельствуют 5 одинаковых слов для 4 билетов из одной брони (#04, #05, #09, #10). Кроме того, слово 3/2 для #07 и #08 тоже совпадает со словами в перечисленной четвёрке.


Номера бронирования для всех билетов:


  • SNK79J (#01);
  • RUKG4T (#02, #03);
  • LW2BUW (#04, #05, #09, #10);
  • SLRSFS (#06);
  • LWJ2JA (#07, #08).

Для приведённых шести общее — LW. Слово 3/2 совпадает также для #01 и #06, у которых общая лишь S. Предположим, что это слово скрывает лишь 1 символ (либо разделитель и 1 символ).


Слова 4/3: 5/1 всё также соответствуют каждому рейсу. Что это за 3-6 символов остаётся неочевидным.


Поскольку я уже почти уверен, что за одним словом скрывается до двух символов, слова 6/0:1 соответствуют номеру рейса (03 и 36 либо 35). Слова 5/2:3 содержат код авиаперевозчика PS и один либо 2 разделителя.




Рис. 5. Уточнение позиций данных #01: #10 для первых 7 рядов





07. Метод подбора


(Назад | Оглавление | Вперёд)


Давайте посмотрим, что же осталось во второй половине кода. Как я уже упоминал ранее, последние 8 слов вряд ли содержат полезную информацию, а перед ними находится 3 слова, показывающие конец данных.


Аналогично со словом 6/3, слова 7/2 и 8/1 повторяются в парах билетов из одного бронирования и одного рейса (#02 и #07, #03 и #08, #04 и #09, #05 и #10). Слова 7/0:1 и 8/0 одинаковы для всех билетов (за исключением нашего уникального #06), а 8/3 и 9/0 одинаковы для всех, кроме #01 и #06.


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


  • номер билета (13 цифр);
  • некий номер безопасности (3-буквенный код аэропорта вылета, минус и 3 цифры);
  • номер участника программы лояльности (зависит от программы, иногда буквы вначале, всегда много цифр);
  • информация о багаже;
  • аэропорты вылета и прилёта (и их коды);
  • время и дата посадки и вылета;
  • терминал (не часто отображает актуальную информацию);
  • ваше место в самолёте;
  • класс резервирования (одна латинская буква).

Ранее я уже решил, что 13 цифр номера билета шифровать нет смысла — он занимает слишком много места. Аналогично с программой лояльности (кроме того, что тогда этот номер был бы во всех 5 билетах одного человека).


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


Осталось немного — код безопасности, аэропорты, место в самолёте и класс резервирования. Сравним их для разных билетов.


PDF417 Код безопасности Откуда Куда Место Класс
#01 VCE-037 VCE KBP 4D X
#02 VCE-047 VCE KBP 24A N
#03 KBP-053 KBP VCE 6F Q
#04 VCE-082 VCE KBP 26B X
#05 KBP-026 KBP VCE 17B X
#06 VCE-077 VCE KBP 15A N
#07 VCE-046 VCE KBP 24B M
#08 KBP-055 KBP VCE 6E X
#09 VCE-083 VCE KBP 26C X
#10 VCE-025 KBP VCE 17C X

Заметили? У нас есть 3 разных места с буквой B, а также 2 — A и 2 — C. Их найти было не сложно — слово 7/3. В таком случае, слово 7/2 содержит цифры из номера места. Потому их четыре пары и ещё два разных.


Не многим сложнее было найти и код безопасности. А точнее, его цифры — в словах 8/1:2. При этом, 8/1 содержит первые две, а 8/2 — последнюю цифру и, возможно, разделитель. Слово 8/0 разделяет место пассажира и код безопасности и одинаково для всех кодов.


Что скрывается за словами 6/2 и 6/3 непонятно. Это же касается и последних слов-данных 8/3 и 9/0. Слова 8/0, 7/0 и 7/1 одинаковы для всех кодов.




Рис. 6. Уточнение позиций данных #01: #10 для последних 6 строк





08. Построчный анализ


(Назад | Оглавление | Вперёд)


Настало время рассмотреть особенности разных строк кодов. Здесь не будет текста. Давайте просто посмотрим на свойства слов каждые три строки. Представим каждое слово как последовательность из 8 символов, шириной от 1 до 6. Тогда для строк 0, 3, 6 и 9 получим следующий результат на основе 19 разных слов (Рис. 7).




Рис. 7. Слова в строках 0, 3, 6 и 9


А вот для строк 1, 4, 7 и 10, состоящих из 32 разных слов, правила немного другие (Рис. 8).




Рис. 8. Слова в строках 1, 4, 7 и 10


Соответственно, для 28 слов из строк 2, 5, 8 и 11 результат будет следующий (Рис. 9).




Рис. 9. Слова в строках 2, 5, 8 и 11


В таком случае, с помощью трёх несложных шагов, можно вывести формулу для определения группы, к которой относится строка (Рис. 10).




Рис. 10. Общие правила





09. Получение всех возможных слов


(Назад | Оглавление | Вперёд)


Итак, в каждом слове есть 8 символов. Максимальная длина одного — 6 элементов. Отталкиваясь лишь от этого, можно получить 1 679 616 комбинаций. Если же уточнить, что длина слова должна быть равна 17 элементов, а также для слов в каждой строке должны выполняться найденные ранее правила, у нас остаётся лишь 3 488 возможных вариантов.


Из этих 3 488 вариантов:


  • 1 484 для группы 0;
  • 1 002 для группы 3;
  • 1 002 для группы 6.

Поскольку группы 3 и 6 содержат меньше возможных комбинаций, а все три группы должны бы быть абсолютно одинаковы, будем считать их верхней границей. Таким образом, 482 комбинации из группы 0 не используются.


Осталось понять, как же эти слова кодируются. Я уже практически уверен, что каждое слово кода может содержать 2 буквы. В латинице — 26 букв от A до Z, для которых потребуется $26^2 = 676$ слов. Кроме того, нужен ещё как минимум один разделитель (к примеру, пробел), что даёт уже 729 слов.


Не сложно заметить, что цифры сюда уже не влезают, поскольку $(26 + 10)^2 = 1 296$, а с разделителем — все 1 369. В таком случае, нам нужно использовать набор возможных слов ещё раз, добавив "режимы" и переключатели между ними.


Итак, вернёмся к количеству возможных комбинаций. Мы можем зашифровать не больше чем квадрат числа возможных символов. Получается, что наш лимит — 31 символ (961 комбинация).


Предполагаемая таблица
Индекс Режим 0 Режим 1
0 A 0
1 B 1
2 C 2
3 D 3
4 E 4
5 F 5
6 G 6
7 H 7
8 I 8
9 J 9
10 K
11 L
12 M
13 N
14 O
15 P
16 Q
17 R
18 S
19 T
20 U
21 V
22 W
23 X
24 Y
25 Z
26 (d) Пробел? (d) Пробел?
27 (s1) Переключатель (s0) Переключатель
28
29
30




10. Словарь v0-01 и "неправильный" код


(Назад | Оглавление | Вперёд)



Давайте подведём промежуточные итоги наших знаний. Фамилии, коды бронирования, коды рейсов, номера мест и коды безопасности позволили составить словарь из 38 символьных комбинаций. Большинство из них известно только для одной из трёх групп. Лишь 03 и 04 известны сразу для двух групп.


Давайте ещё раз внимательно посмотрим на код #06. Для удобства, приведу построчное его сравнение с кодом #07 (Рис. 11).




Рис. 11. Построчное сравнение кодов #06 и #07. Рационализация записи данных.


Как видно, слова в коде совпадают до того момента, пока не оказывается, что для записи номера бронирования нужно меньше символов (поскольку нет перехода между буквами и цифрами). Таким образом, далее код съезжает на одно слово вперёд.


Как я уже предполагал ранее, в конце всех кодов, кроме #06 присутствуют три одинаковых слова. Вначале я назвал их "стоп-словами", но поскольку их нет в единственном коротком коде, они представляют собой скорее пустые символы для выравнивания всего PDF417. А вот количество проверочных слов (8 последних) для всех кодов одинаково.


Если быть внимательным, можно заметить, что для кода #06 слова 7/2 и 7/3 одинаковы. Поскольку первое из них содержит переход к режиму 0, описанному ранее, и букву A то 7/3 уже не может содержать такого же перехода. А вот обратный переход вполне возможен и он должен сопровождаться символом с таким же порядковым номером в таблице, что и A. В результате, слово 7/3 в коде #06 записывает переход к режиму 1 и цифру 0. Таким образом, код безопасности состоит из 4 цифр с ведущим 0, что звучит вполне логично.


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


Индекс Режим 0 Режим 1
27 (s) Переключатель (s) Переключатель

Кстати, слово 7/0 тоже идентично упомянутым ранее. Поскольку после него идёт число, оно соответствует (s)0. В таком случае, предыдущее слово 6/3 должно оканчиваться буквой. Таким образом, на номер ряда в самолёте отводится 3 цифры, хотя таких длинных самолётов не бывает?


Чтобы исключить вероятность ошибки в моём анализе, нужно было найти слова, которые точно соответствовали и (s) + буква, и (s) + цифра. Это было не сложно, согласно моему предположению, 4/0 в коде #07 означает (s)2, что должно равняться (s)C. А такое слово находится на позиции 7/3 кода #09. Поскольку ряды 4 и 7 соответствуют одной группе, а слова одинаковы, гипотеза подтверждается.


Одновременно, это подтверждает принцип размещения кода бронирования в PDF417. В результате, словарь дополнился до 50 позиций, а ещё одна получила значение для иной группы рядов.





11. Другие авиалинии & v0-02


(Назад | Оглавление | Вперёд)



Давайте изучим коды других авиалиний. Ведь больше данных — это всегда больше возможностей. В качестве других у нас будут Turkish Airlines (#11: #14). Первое, что бросается в глаза — они используют коды, повёрнутые на 180 градусов. Поскольку я уже привык к предыдущему набору, я просто разверну новые 4 кода в стандартное состояние. Кроме того, код растянут так, чтобы наименьший элемент был привычного размера.


Каждый код состоит из 26 строк и 5 столбцов с информационными словами. Все они, вместе с левыми и правыми сервисными словами, а также паттернами старта и конца, делают код довольно большим. На Рис. 12 представлено построчное сравнение для первых 17 строк кодов.




Рис. 12. Построчное сравнение кодов #11: #14. Часть 1


Сразу отметим то, что мы уже знаем благодаря предыдущей группе кодов. Сюда относится фамилия в начале кода (сразу после первого слова 0/0, содержащего общее их количество, и двух слов 0/1:2, стандартных для всех посадочных талонов). Для меня это слова 0/3: 1/2. После фамилии-имени идут 6 одинаковых для всех 4 билетов слов (2/4: 3/4). Если следовать той же схеме, что и для прошлых авиалиний, здесь должен быть номер бронирования. В данном случае — EUPT2M7, что на один символ и один переход между группами символов длиннее, чем предыдущие коды. Далее — 3 слова, одинаковые для одного рейса.


После всего этого расположены 4 слова (2 одинаковые и 2 в соответствии рейсу), в которых расположены коды (TK) и номера рейсов (1870 и 0762). Слово 6/1 снова повторяется для одного рейса, а вот 6/2 — разные. В этих двух словах расположены номера мест 23 A/B и 17 K/J. И сразу за ними идёт код безопасности в словах 6/3: 7/0.


В результате, у нас осталось ещё 2/3 кода. Что делать с ним разберёмся чуть позже, а пока вернёмся к трём словам, которые повторяются для рейса. Для данной группы — слова 4/0:2, а для 10 билетов другой авиакомпании — 4/3: 5/1. Если быть достаточно наблюдательным, можно заметить, что первое из трёх слов (находится в одной группе для всех кодов) одинаково (32233211) для всех рейсов из аэропорта Марко Поло. В 3 слова, то есть 6 обычных символов, может поместиться как-раз коды двух аэропортов — вылета и прилёта.


Давайте попробуем понять, что спрятано в следующей части кодов. Слово 8/0 содержит число 18, 14/2 — число 62, а вот 13/0 содержит то же, что и 4/3. В билетах моей жены слово 14/3 содержит число 18. При этом, начиная с 14/2 коды для нас разные. Недолго вглядываясь в напечатанный посадочный талон, можно определить, что здесь скрывается номер карты программы лояльности.


В результате, наш словарь состоит уже из 78 двухсимвольных комбинаций, а одна из них — (s)A / (s)0 известна и для всех трёх групп рядов.





12. Ещё пара кодов TA & v0-03


(Назад | Оглавление | Вперёд)



Ещё два кода #15 и #16 тех же авиалиний вносят разнообразие в возможные размеры PDF417. На этот раз — 27 строк состоят из 4 информационных слов каждая. Использовав наш текущий словарь, можно сразу восстановить 15 слов (Рис. 13, отмечены серым).




Рис. 13. Построчное сравнение кодов #15 и #16. Часть 1


Несложно восстановить и слово 7/2, ответственное за число 16 (номер места). Всплывает также интересный факт, что после кодов аэропортов ISTKBP сразу же (без разделителя) идёт TK — код авиалиний, который входит в номер рейса (слово 5/2). В таком случае, 5/3 содержит разделитель (d) и переключатель (s), но не известно, в какой последовательности.


Слова 6/0:1 ответственны за номер рейсов (1062 и 0459), а вот 4/3: 5/1 дополняют словарь комбинациями LJ UI ST из названий аэропортов. К сожалению, для этих посадочных талонов я не смог найти номер бронирования, а слова 3/2: 4/2, где он, вероятно, размещён, почему-то разные. Кроме того, печатный посадочный талон не содержит кода безопасности, а потому хоть он и должен размещаться в словах 8/1:2, мы его не знаем.


Вернувшись к кодам #01: #10 можно добавить в словарь ещё пару комбинаций, пропущенных вначале, в том числе PS — код авиакомпании. В результате, у нас есть 87 комбинаций в словаре.





13. Сервисные слова & v0-04 & v0-05


(Назад | Оглавление | Вперёд)



Пришло время рассмотреть, что же из себя представляет информация в сервисных столбцах (левом и правом). Результат представлен на Рис. 14, однако давайте посмотрим подробнее, как к нему дойти. Благодаря известной части словаря, удалось расшифровать:


  • 7 / 24 для кодов #01: #05, #07: #10 (Рис. 15);
  • 7 / 22 для кода #06 (Рис. 15);
  • 4 / 52 для кодов #11: #14(Рис. 16);
  • 5 / 54 для кодов #15: #16 (Рис. 17);
  • 10 / 48 для кодов #17: #18, о которых речь пойдёт в следующем разделе (Рис. 18).



Рис. 14. Сервисные слова


Самой простой оказалась группа слов $k/R$ и $(k+2)/L$, где $k = 3i$, $i = 0, 1, 2…$ (отмечены синим цветом на Рис.). Для неё правое число равняется 2, 3 или 4, в зависимости от количества столбиков в коде (3, 4 и 5 соответственно).


В группе $k/L$, $(k+1)/R$ (отмечены зелёным) правое число принимает значения 3, 3, 8, 8 и 7 для кодов длиной в 12, 11, 26, 27 и 24 строк. Поскольку цикличность в 3 строки сопровождает весь код, здесь тоже используется тройка. Данное число является результатом целочисленного деления номера последней строки (оно же количество строк отнять единицу) на 3.


Последняя группа $(k+1)/L$, $(k+2)/R$ (оранжевый) оказалась самой сложной. Очевидно, что количество строк играет здесь важную роль, поскольку число разное для кодов из 12 и 11 строк (Рис. 15). В то же время, оно может принимать значение больше 9 (L или же 11 для кодов в 27 и 24 строки, Рис. 17 и Рис. 18 соответственно). В таком случае, это некое число плюс остаток от деления номера последней строки на 3.


Узнать значение константы помог единственный элемент кода, который я ещё не рассматривал — конец кода. Как вы помните, там представлено некоторое количество слов, разное для каждого кода. Где-то в начале анализа я решил, что они не несут полезной информации. Пришло время восстановить справедливость — это коды для коррекции ошибок. Но нам важно их количество. Оно равняется 8, 16 и 32 для всех 18 рассмотренных кодов. Поскольку эти числа недвусмысленно намекают на степени двойки, а число 3 содержится во всех формулах, также как и отнимание единицы, восстановить формулу оказалось несложно.


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


Поскольку, теперь восстановить все 200 L и R слов теперь было проще простого, словарь дополнился до 132 уникальных комбинаций.


А применение нового словаря позволило восстановить правильное положение имен, а также дополнить версию v0-05 до 135.



Рис. 015

Рис. 15. Сервисные слова #01: #10



Рис. 016

Рис. 16. Сервисные слова #11: #14



Рис. 017

Рис. 17. Сервисные слова #15: #16



Рис. 018

Рис. 18. Сервисные слова #17: #18





14. Снова другие авиалинии & v0-06


(Назад | Оглавление | Вперёд)



Перейдём к новой авиакомпании — Adria Airways, таких у нас есть четыре.


Чтобы внести разнообразие, начнём не с #17 и #18, а с #19 и #20. Это коды из 20 рядов и 4 колонок. С помощью них можно восстановить такие комбинации, как UK (из кодов аэропортов LJU и KBP), JP — код авиалиний, а также 09 (часть номера рейса 934), 10 и 01 (Рис. 19). Используя L и R сервисные столбцы (Рис. 20), можно получить ещё 20 слов из разных групп словаря.




Рис. 19. Коды #19: #20



Рис. 020

Рис. 20. Сервисные слова #19: #20


Почему в этих двух кодах не расшифрован код брони? Для обоих он — LBZOKV. Следуя тому же принципу, который был использован ранее, он должен располагаться блоками (d)L, BZ, OK и V(d) в словах 3/2: 4/1. Тем не менее, слово 3/2 не соответствует комбинации (d)L из словаря. Видимо, вместо (d) в коде присутствует другой разделитель, либо его нет. В любом случае, стоит учесть это далее.


Перейдём к кодам #17 и #18 (Рис. 21). С их помощью можно восстановить ещё несколько комбинаций, в том числе VA, SK, LE, YI, VS, EV, EL, NI, YZ, KB, PL, JU, JP, 35 и 00. Часть из них уже была в нашем словаре для некоторых групп, а другой не было вовсе. В результате, словарь дополнился до 149 уникальных комбинаций.




Рис. 21. Построчное сравнение кодов #17 и #18


Кроме того, пришло время подсчитать количество неизвестных нам символов. Для всех 20 кодов, этот список состоит из 376 уникальных значений, а точнее — 114, 130 и 132 кодовых слова для разных групп.





15. Исправляем свои ошибки


(Назад | Оглавление | Вперёд)


Ещё при первом рассмотрении кодов #01 — #10, я решил, что слово на позиции 0/0 содержит в себе количество всех слов в коде. Это подтверждал тот факт, что для #06, который был короче на одну строку, данное значение отличалось. На данный момент, мне известны значения этого слова для кодов #11: #14 (38), #15: #16 (32) и #19: #20 (24).


Поскольку я уже знал, что количество проверочных слов, присутствующих в конце каждого кода, зашифровано в сервисных столбцах L и R, я решил, что нужно подсчитать лишь полезные слова. В результате, были получены значения 98, 92 и 64 соответственно. Очевидно, что это не совсем то, чего я ожидал.


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


Вначале я знал лишь верхнее ограничение количества слов и решил, что базис вполне может занимать всё возможное пространство из 31 элемента. Теперь же становится очевидно, что настоящая его размерность — 30. В таком случае комбинация 38 становится словом под номером 98 ($30 * 3 + 8$), комбинация 32 — номером 92 ($30 * 3 + 2$), а 24 — номером 64 ($30 * 2 + 4$).


В результате, первое слово кодов #01: #05, #07: #10 имеет номер 40 (комбинация BK), #06 — номер 36 (BG), а кодов #17: #18 — номер 56 (комбинация B и символа под номером 26).





16. Все оставшиеся коды & v0-07


(Назад | Оглавление | Вперёд)



Напоследок осталось ещё два кода Adria Airways (#21 и #22, Рис. 22), с помощью которых определяются комбинации BZ, VI, LJ, 85, 16, 10, 55, 31, 92, 81, 40, 32, 4(d), 98 и 45. Сервисные L и R слова этих кодов (Рис. 23) добавляют 37, 47, 57, 67, 77, 87, 06, 26, 36, 46 и 76.



Рис. 022

Рис. 22. Коды #21: #22



Рис. 023

Рис. 23. Сервисные слова #21: #22


Интересно, что коды #21 и #22 содержат как номера карт лояльности, так и номера самих билетов. В кодах же #19 и #20 из того же бронирования, этих данных нет (либо они представлены в другом виде).


Самым-самым последним (#23, Рис. 24) оказался ещё один код той же авиакомпании. Он помог восстановить ещё 7 комбинаций, а вот анализ L и R слов (Рис. 25) не открыл ничего нового.




Рис. 24. Код #23



Рис. 025

Рис. 25. Сервисные слова #23


В результате, словарь версии v0-07 состоит из 174 уникальных комбинаций, а точнее — 315 слов из разных групп. Список неизвестных слов состоит из 411 элементов.





17. Дальше стоит быть умнее & v0-08


(Назад | Оглавление | Вперёд)



Поскольку подбирать отдельные слова в кодах стало достаточно трудно, а просто угадывать их нет никакого смысла, стоит на минуту (день, неделю) задуматься. По какому принципу генерируются 17-символьные слова в PDF417.


Помните, при расчётах всех возможных комбинаций (здесь), получилось, что для группы 0 их возможно 1 484, группы 3 — 1 002 и группы 6 — тоже 1 002. То есть часть из возможных кодов никак не используется.


Во время обработки данных из кодов, для удобства, я сортировал известные и неизвестные 8-символьные значения в возрастающем порядке (к примеру, (11111543) был самым первым, а (61123121) — последним). Очевидно, что при этом сам словарь шел совсем не от AA и до YZ.


Некоторое время я даже думал, что вдруг коды распределены в случайном порядке и никакой систематики в них нет. Но в какой-то момент я заметил интересную особенность. Для группы 6 кодов все комбинации между AA и AL были мне известны. И в AA: AK они содержали последовательность (x1111xxx), код AL содержал (x1112xxx). При этом, последние три числа были отсортированы от меньшего к большему. Первое значение было единственным без сортировки.


Примерно в этот момент я подумал "ну наконец-то я смогу продвинуться не на 5-10 слов в словаре, а существенно больше". Мне нужно было всего-лишь правильно отсортировать все возможные значения и убедиться, что какое-нибудь условное TK не идёт перед DC. Ну и не забыть, что символьных комбинаций должно быть лишь 900 из всех возможных 1 002 / 1 484.


Конечно же, это не сработало. Для каждой из групп слова идут подряд только до определённого момента. В случае группы 0 — до EV, группы 3 — до G(s), группы 6 — до EH. Тем не менее, начало всех групп выглядит достаточно оптимистично. Начнём с группы 3.


Длинная таблица
## Слово
  5 1 1 1 1 1 2 5
  6 1 1 1 1 1 3 3
  4 1 1 1 1 2 1 6
3 AD 5 1 1 1 1 2 2 4
4 AE 6 1 1 1 1 2 3 2
    4 1 1 1 1 3 1 5
6 AG 5 1 1 1 1 3 2 3
7 AH 6 1 1 1 1 3 3 1
8 AI 4 1 1 1 1 4 1 4
  5 1 1 1 1 4 2 2
10 AK 4 1 1 1 1 5 1 3
11 AL 5 1 1 1 1 5 2 1
  4 1 1 1 1 6 1 2
13 AN 4 1 1 1 2 1 2 5
  5 1 1 1 2 1 3 3
  6 1 1 1 2 1 4 1
    3 1 1 1 2 2 1 6
    4 1 1 1 2 2 2 4
    5 1 1 1 2 2 3 2
    3 1 1 1 2 3 1 5
    4 1 1 1 2 3 2 3
    5 1 1 1 2 3 3 1
    3 1 1 1 2 4 1 4
    4 1 1 1 2 4 2 2
    3 1 1 1 2 5 1 3
    4 1 1 1 2 5 2 1
  A(d) 3 1 1 1 2 6 1 2
    3 1 1 1 3 1 2 5
    4 1 1 1 3 1 3 3
    5 1 1 1 3 1 4 1
30 BA 2 1 1 1 3 2 1 6
    3 1 1 1 3 2 2 4
32 BC 4 1 1 1 3 2 3 2
33 BD 2 1 1 1 3 3 1 5
    3 1 1 1 3 3 2 3
35 BF 4 1 1 1 3 3 3 1
36 BG 2 1 1 1 3 4 1 4
37 BH 3 1 1 1 3 4 2 2
38 BI 2 1 1 1 3 5 1 3
    3 1 1 1 3 5 2 1
40 BK 2 1 1 1 3 6 1 2
41 BL 2 1 1 1 4 1 2 5
    3 1 1 1 4 1 3 3
43 BN 4 1 1 1 4 1 4 1
    1 1 1 1 4 2 1 6
    2 1 1 1 4 2 2 4
    3 1 1 1 4 2 3 2
    1 1 1 1 4 3 1 5
    2 1 1 1 4 3 2 3
    3 1 1 1 4 3 3 1
50 BU 1 1 1 1 4 4 1 4

Для начала стоит отметить позицию разделителя (d) — номер 26, что совпадает с моим начальным предположением. Он же подтверждается ещё и расстоянием между комбинациями FN (163) и F(d) (176).


С помощью расстояний [ CN — C(s) — DC ], [ D(s) — EG ], [ ET — E(s) — FG ] и [ G(d) — G(s) ], можно определить позицию переключателя (s) под номером 28.


Используя разные последовательности во всех группах, общий словарь удалось расширить до 282 уникальных значений. Из них 114 входят в группу 0, 228 — в группу 3 и 167 — в группу 6.


Подведя промежуточный итог, можно сказать, что из 1 492 информационных слов во всех кодах и 336 слов для коррекции ошибок, 842 (56.4%) и 69 (20.5%) соответственно расшифровано.





18. Строим смелые предположения & v0-09


(Назад | Оглавление | Вперёд)



Итак, благодаря группе 3 и коду #20, выяснилось, что длинное имя моей жены помещается в коды только до AV включительно. Можно предположить, что именно комбинация AV попадается в имени и в остальных кодах.


И хотя положение комбинации AV не помогло определить другие комбинации группы 0, но для группы 6 получилось опознать AO: AU.


Дальше стоит разобраться с тем, что беспокоит меня с самого знакомства с PDF417 кодами в посадочных талонах — слова 0/1 и 0/2, одинаковые во всех случаях. Если 0/1 локализовать достаточно сложно, то 0/2 находится между B(d) (056) и CC (062). При этом, положении комбинации позволяет всего два варианта — она шифрует либо (057), либо (058). Поскольку символ (27) мне ещё не встречался, я предположу комбинацию (058), соответствующую B(s) или 1(s). Сразу после слова 0/2 в кодах идут фамилии пассажиров, потому оно шифрует 1(s). Это же слово встречается на позиции 9/0 кодов #12 и #14, чьё назначение пока не известно.


Интересное наблюдение можно сделать для группы 3 слов (840): (849). Из 8 значений каждой комбинации, последние три — 111, а все остальные соответствуют определённым последовательностям (Рис. 26).




Рис. 26. Последовательности слов в группе 3


Такое наблюдение позволило восстановить последовательность (839): (852). Поскольку глупо было бы не попробовать ещё раз, я решил найти другие похожие последовательности. Всего в списке возможных комбинаций осталось 11 групп, заканчивающихся на 111 (Рис. 27).




Рис. 27. Другие последовательности в группе 3


Одна из этих комбинаций уже присвоена слову (656) — V(d), а потому локализация её в словаре была несложна. С другой стороны, направление вызвало некоторые вопросы. Поскольку значение слова (648) известно и текущая комбинация вполне может начаться с (649), я решил начать с (52241111) на этой позиции.


Позиционирование последовательности (53231111): (12326111) в данный момент невозможно, поскольку ни один из элементов не известен.


Перейдя к группе 6, можно заметить, что всего по 1 лишней комбинации не даёт определить значения для (022): (027), (046): (061), (117): (121) и (134): (139). Перебрав все возможные комбинации простых математических операций с 8 элементами каждого слова, выяснилось, что если брать сумму соседних значений (Рис. 28), то из всех известных слов, 10 может стоять лишь на краю новой семизначной последовательности, а если оно присутствует в средине — такая комбинация невозможна.




Рис. 28. Рассматривать можно не 8 отдельных элементов слова, а 7 их сумм.


Такой же метод я применил и к группе 6. В результате, словарь дополнился до 339 уникальных значений и пришло время проверить всё, что было сделано.





19. Анализируем и ищем тайные последовательности


(Назад | Оглавление | Вперёд)


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


К примеру, в коде #22 перед номером карты лояльности появилась последовательность (s)LH(s) на позициях 16/2:3. Недолго думая, можно предположить, что это код компании, выдавшей карту (Lufthansa). В таком случае, код #21 тоже содержит H(s), на позиции 17/0, что добавляет ещё одно значение в словарь. Перед кодом компании — JP — код авиалиний.


Интересной является последовательность 06 00 00, которая встречается как в этих кодах, так и в других. К примеру, в коде #23 — это 30 60 00 00, как и в кодах #15, #16. А вот в #11: #14 содержится 06 00 00 0(s). Что это за последовательность угадать не представляется возможным.


В кодах #11: #14 перед номером карты программы лояльности и после кода авиалиний TK осталась одна вакансия (13/1) и слово K(d). Поскольку вокруг одни буквы и переходить между разными режимами не нужно, можно предположить, что вакантное место содержит (d)T.





20. Новый метод записи


(Назад | Оглавление | Вперёд)


Помните, в кодах #21 и #22 присутствует номер билета, а вот в #11: #14, #15: #16, #17: #18 и #19: #20 их нет, так же как и в #23. С другой стороны, в некоторых присутствует интересная последовательность 2(s)A(29) или C(s)0(29). Символ 29 практически не встречается в кодах и его назначение мне не известно. Но давайте попробуем угадать, что же происходит дальше.


В качестве примера возьмём коды #11: #14, поскольку в них предполагаемая позиция номера билета окружена уже известными словами (Рис. 29). Итак, у нас есть неизвестные слова 11/2, 12/0:4. При этом, лишь слово 12/3 отличается.


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


Единственное отличие в номерах билетов — последняя цифра 4 / 8. Полный же номер — 235 5591 4709 94 / 8. В таком случае, слово 12/4 не является частью номера, а скорее очередным переключателем. Раз нам нужен переключатель в конце, то ещё один должен быть и вначале. Сначала можно было бы подумать, что неизвестный символ (29) и есть переключателем, но он используется также в самом конце кода #01, а потому, скорее, просто служит для смещения на один символ. В таком случае, переключатель — слово 11/2.


Получается, номер билета записан в 6 словах. Первые из них — (002) и (083), а остальные неизвестны. Итак, как же записать 13 цифр в 6 словах? Поскольку для двух номеров отличается лишь последнее слово, то именно оно является младшим разрядом. Таким образом, (002) — старший разряд, а посчитав $2 * 900^5 + 83 * 900^4$ можно получить $1 235 ...$, что уже похоже на что-то полезное. Процесс расчёта показан на Рис. 29.




Рис. 29. Цифровой метод записи


Как видно, чтобы получить правильное значение, впереди числа нужно записать дополнительную единицу. Что за две цифры следуют в конце номера не известно.


Глупо было бы не проверить, работает ли этот метод на других номерах. К счастью, коды #15 и #16 должны содержать такой. Слова 14/0 и 15/2 содержат уже известные нам неизвестные переключатели в цифровой метод записи и назад в символьный. Тогда сам номер билета содержится в словах 14/1: 15/1. При этом, слово 14/3 известно — это (090). В таком случае, возможный вариант решения — запись номера + ещё одной неизвестной цифры. А вот при записи одного лишь номера, результат получится другой.


Итак, каждое слово может содержать до трёх символов, при этом к любому числу обязательно добавлять ещё один разряд. В таком случае, для записи числа из $N$ цифр понадобится $N / 3 + 1$ слово, где $/ 3$ — операция целочисленного деления.


Поскольку базис слов (900) меньше чем 1000, использовать такой метод записи можно лишь пока степени 900 добавляют по 3 десятичных разряда к числу. В таком случае, максимум для последовательной записи — 15 слов, что соответствует 44 десятичным разрядам. Слово номер 16 добавит лишь 2 новых разряда.





21. Расширенный словарь


(Назад | Оглавление | Вперёд)


Весь анализ до этого основывался на предположении, что словарь состоит из 900 слов от 0 до 899, которые шифруют разные комбинации из двух символов. Теперь мне известно, что бывает и иной метод передачи информации с помощью PDF417, который требует ещё двух переключателей — (n), чтобы переключить в режим записи чисел, и (с), который производит обратное переключение.


Поскольку подобные переключатели не могут занимать позиции ни среди 30 символов, ни среди 900 чисел, им необходимы собственные индексы, большие чем 899. В таком случае, отделив ещё один блок из 30 слов, можно с лихвой покрыть потребности во всех возможных "дополнениях". В результате, общий словарь расширится до 929 слов от 0 до 928. Определить точное положение слов (n) и (с) не представляется возможным.


Интересным является также факт, что коды #01: #05, #07: #10 заканчиваются последовательностью из 3 слов (с), а коды #17: #18 — последовательностью из двух (с). Так как само слово не содержит информации, это удобный способ добавления "пустых" слов для выравнивания кода.





22. Последний неизвестный номер


(Назад | Оглавление | Вперёд)


Ещё один неизвестный номер остался в коде #23. Его анализ представлен на Рис. 30. Номер билета 16 521 054 807 52 уже состоит из 13 символов, а для его кодирования необходимо добавить начальную единицу. Поскольку во всех случаях в номере были дополнительные цифры в конце (одна или две) и место для одного знака осталось вакантно, добавим его.




Рис. 30. Номер билета в коде #23


Проверить правильность такого анализа можно с помощью последнего из слов. Я предполагаю, что оно должно скрывать двузначное число с первой 2. Для группы 0 мне уже известны слова (021) и (029). Как вы помните, для начала каждой группы всё ещё работает описанная ранее сортировка слов. И, поскольку неизвестное слово находится в списке выше чем (021), за ним скрывается (020).





23. Очередное прозрение & v0-10


(Назад | Оглавление | Вперёд)



Вы же ещё не забыли, что в разделе 17 меня осенило и я нашел способ сортировки всех возможных слов таким образом, что хотя бы начало списка для каждой группы идёт последовательно с тем, как эти слова встречаются в словаре. Для вас это было всего 6 разделов назад, а для меня чуть больше недели.


Итак, объединив эту идею с идеей из раздела 18, всё оказалось намного проще. Сортировку необходимо выполнять не по последним 7 из 8 значений для заполненных и пустых элементов слова, а по 6 из 7 суммам соседних элементов. В таком случае, для группы 0 первым будет слово (4222249), а последнее — (7944422).


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


Таким образом, словарь известных слов дополнился до 131, 415 и 308 значений соответственно в группах 0, 3 и 6.





24. Точечные поиски & v0-11


(Назад | Оглавление | Вперёд)



Начнём с имён. В случае группы 6, имя начинается с (16211132). Расположение в 20 словах от s(E) и начало имени с Y говорит о слове (864) — (s)Y. Аналогично решается вопрос и в группе 3, что позволяет для обеих групп определить ещё 30 слов в сумме. В группе 0 дополнительных слов узнать не получилось.


Перед (s)Y и после фамилий идёт ещё одно слово, которое соответствует (s)T, а точнее — (s)(19), поскольку содержит 19 символ в режиме отображения чисел.


В каждом коде есть слово, которое должно выполнять операции (s)(d) / (d)(s). Оно расположено сразу после 6 символов аэропортов + 2 символов авиаперевозчика и перед номером рейса. Теперь, когда я знаю последовательность всех слов в словаре, становится очевидно, что правильный порядок символов в слова — (d)(s), что соответствует слову (808). Группе 6 это никак не помогает, а вот в 3 можно определить ещё 30 новых слов. Коды #11: #14 содержат это слово из группы 0.


В некоторых кодах встречается и обратная последовательность (s)(d) / (866). К примеру, она из группы 0 есть только в коде #21, а вот из группы 6 — только в #22.


Благодаря кодам #11: #12 можно подтвердить, что после моего имени идёт разделитель, а последнее слово — I(d) — (266). Это также позволяет определить 14 слов (252): (265) для группы 6. Ещё несколько слов, вместе с (266) легко определяется для группы 3. Благодаря #19 это же слово восстанавливается для группы 0. А вот в коде #21 необходима комбинация I(s) (268), поскольку далее следует лишний переход (s).


В кодах #11: #14 в конце присутствуют 3 одинаковых слова, перед которыми идёт (с). Поскольку никакой важной информации не может быть записано в трёх пара одинаковых слов, а (11611124) находится где-то далеко в конце словарей, можно считать, что он означает такое же слово (с).


Особый интерес представляют код #21. Как и другие, они заканчиваются серией из трёх одинаковых слов. Одновременно, расположение этих слов в списке всех возможных ставит их не дальше чем на позицию (901). Поскольку слова по (899) включительно входят в "основные", и предположив, что это и есть слово (с), можно поставить его на позицию (900) или (901), а слово (n), которое уже известно для группы 6 попадёт на позицию (902) или (903).


Слова 22/0:3 кода #21 и 22/0:2 кода #22 по расположению подходят под комбинацию (d)(d) — (806). Последнее "значимое" слово в обоих кодах — (d)(29).


Для билетов #15: #16, ряды 17 и 18 представляют собой наборы из 4 одинаковых слов. При этом, 16/3 и 19/0, окружающие эти 8 слов, означают (d)(d). Слова (15111215) и (23421122) оба подходят под такое же значение (d)(d) для групп 0 и 6 соответственно. Именно комбинация (d)(d) — самая популярная среди всех комбинаций в 23 кодах.


В результате, словарь расширился до 138, 466 и 349 слов в разных группах.





25. Новые поиски & v0-12


(Назад | Оглавление | Вперёд)



В коде #23 слова 15/3 (13242311) и 16/0 (33113222) идут сразу после номера билета. В кодах #21: #22 после номера билета идёт (d)(s)JP, что свидетельствует об авиалиниях. Поскольку в данном случае не нужен переход от букв к цифрам и (s) не нужно, не сложно определить, что 15/3 соответствует (d)J.


В коде #22, слово 16/1 находится между JP и (s)LH(s). Поскольку до идут буквы, а после переключатель и вновь буквы, нам необходим ещё один переключатель. В кодах #11: #14 между кодом авиалиний и кодом компании-эмитента карты лояльности стоит разделитель, потому нам подходит комбинация (s)(d) как слово (11512142) из группы 3.


Положение слова 17/0 кода #22 подсказывает первый символ как (d), а поскольку номеру карты лояльности не хватает первой 9, то комбинация (d)9 вполне очевидна. В #15 перед 060000 идёт (22)3. Слово 20/0 #22 вполне подходит по расположению под это значение. Аналогичные рассуждения справедливы и для #21.


Ещё одно неизвестное слово впереди должно содержать ещё одну (s) чтобы вернуть режим записи к цифрам. Возьмём код #21. Тогда этому слову соответствует комбинация (418) — N(s).


Слово 11/0 #22 подходит для комбинаций I(27) и I(s). Они же 8(27) / 8(s). Поскольку после идёт комбинация BO, а я всё ещё не знаю, какую операцию производит (27), я выбрал второй вариант. В таком случае, 11/2 должно соответствовать S(s), чтобы не нарушать последовательность переходов буквы-цифры. Снова для #21 всё то же самое.


Из #23 неизвестными остаются слова 16/0 и 19/0. Первое должно содержать P из кода авиакомпании и ещё один символ. Слово 19/1 содержит переключатель, после которого идут цифры. 19/0 находится немного раньше комбинации (d)(s), соответственно не может содержать переключателя. В таком случае, 16/0 также не содержит переключателя и единственный возможный вариант — P(d) — комбинация (476). Само 19/0 может быть либо (792), либо (793) — (d)N или (d)O соответственно.


Слово 22/1 #23 содержит первую T. После неё может идти (27), (s) или (29). Поскольку дальше в коде нет информации, а другие коды заканчивались на (29), тут возьмём этот же символ.


11/2 — ещё одно слово, которое подходит под комбинацию P(d), но уже в группе 6. Поскольку дальше идут сплошные (d), нет причин сомневаться в этом значении.


В кодах #19: #20 слово 13/3 находится через одну позицию после переключателя (с). Мы уже выяснили, что такое расстояние соблюдается между (с) и (n). Соответственно, слова 14/0: 15/1 содержат число, что объясняет последующий (с) на позиции 15/2. В #20 известно только 2 числа из 6, а вот в #19 — 4. Последнее из которых — (032). Соответственно, всё число заканчивается на 32. Это число нам уже встречалось — номер карты лояльности. В таком случае, определяются комбинации (336), (560), (185), (832) и (045).


Для кодов #15 и #16 слово 11/2 может соответствовать K(d). Поскольку в других кодах мы уже видели, что в этом месте присутствует код авиакомпании, которая выполняет рейс, то комбинация TK вполне логична. В результате, становится известна вся последовательность (301): (326) группы 6.


В кодах #11: #14 слово 8/2 может быть в диапазоне (676): (684). Все они начинаются с W. Поскольку в кодах #15: #16 и #21: #22 на этой позиции была расположена комбинация WW, поставим её и здесь.





26. И снова посмотрим по-новому на все возможные слова & v0-13


(Назад | Оглавление | Вперёд)



Внимательно посмотрев на все возможные слова-комбинации в виде 7 сумм, можно заметить, что часть из них повторяется. И всегда из таких повторов в настоящем словаре присутствует лишь одно уникальное. Использовав этот принцип, словарь можно дополнить дальше.


Так, для группы 6 легко определить все слова, присутствующие в кодах. А для полноты словаря не хватает лишь слов (240), (269), (332), (335), (370), (371), (373), (376), (383), (385), (408), (482), (503), (506), (534), (535), (537), (540), (547), (549), (573), (576), (670), (696), (699), (702), (709), (711), (729), (732), (811), (828), (835) и (837) — всего 34 слова из 929.


Аналогичная ситуация и для группы 3. Здесь неизвестными остаются слова (280), (283), (286), (295), (297), (308), (309), (311), (314), (322), (323), (325), (328), (351), (354), (361), (364), (371), (374), (381), (384), (401), (408), (415), (507), (510), (517), (520), (527), (530), (537), (540), (561), (581), (583), (591), (593), (601), (603), (699), (706), (713), (720) — всего 43 слова.


Конечно же, этот метод, как и все другие, перестаёт работать на группе 0. Точнее, он позволяет определить немного слов, но далеко не в таком количестве, как для других групп. В результате, для этого словаря известно лишь 180 из 929 значений.





27. Поиск ошибок


(Назад | Оглавление | Вперёд)


Вы ведь не забыли, что в конце каждого кода есть набор слов специально для восстановления ошибок? Пришло время их использовать. Восстановление ошибок выполняется с помощью кодов Рида-Соломона. Чтобы это сделать правильно, нужно знать размерность пространства (929), его примитивный элемент (очень сложно угадать, что он — $3$) и количество проверочных слов (его мы и так знаем для каждого кода). В результате, если у нас есть $2t$ проверочных слов, мы можем найти (определить позицию) и исправить (посчитать ошибку) $t$ слов.


Схема поиска и исправления может быть следующей:


  • Строим "синдромы" ошибок (если все слова правильные, то синдромы будут равны 0), их количество — $2t$;
  • Синдромы используются для построения системы $t$ линейных уравнений;
  • Количество независимых уравнений равно количеству ошибок, если их меньше, чем $t$, нужно уменьшить размер системы;
  • Решив систему, получаем позиции ошибок в коде, начиная от последнего слова;
  • Зная положения неправильных слов, считаем "ошибку" — разницу между правильным и неправильным словом.

Начнём с кода #01. В нём неизвестно 2 слова. Предположим, они означают 928. На самом деле, нет абсолютно никакой разницы, какое именно значение им приписать. 8 слов для исправления ошибок дают возможность определить положения и исправить 4 неправильных слова.


В результате, можно определить, что в коде присутствует именно 2 ошибки, а не больше — значит с остальными словами я не ошибся. Их позиции — 21 и 46, а отсчёт идёт с конца кода. Осталось лишь найти правильные значения этих слов — это (781) и (388) соответственно. Последнее слово особо интересно, поскольку встречается в каждом коде — это комбинация M(s). Кто знает, почему все коды начинаются с M1, за которыми следуют фамилия и имя.


Проверка кода #02 позволяет определить неизвестное ранее значение (s)2 — оно же (782) на позиции 21. Попутно становятся известны значения (780) и (783). Для кода #03 всё просто — все слова уже правильные.


В коде #04 можно определить значение (274), а благодаря ему — ещё и (273). Как и #03, код #05 уже правильный. То же касается #07, #08, #09 и #10.


Следующим кодом для проверки будет #17. В нём отсутствуют 5 слов, но на всякий случай стоит проверить количество ошибок, которое подтверждается. Проведя расчёт, можно определить все отсутствующие слова — на позиции 6 — (656), 8 — (717), 25 — (146), 26 — (28) и 34 — (872). Одновременно определяются слова (022):(027), (147):(149), (707):(713), (715), (716), (718):(723), (725), (726), (729), (731):(737), (739), (740), (743).


Для кода #18 неизвестными остались лишь 3 слова. Остальные слова правильные. На позициях 6, 8 и 15 расположены значения (363), (263) и (608) соответственно.


С помощью кода #23 можно узнать значения (086), (334), (570) и (674). Дальше лишь нужно продолжать решать уравнения и находить недостающие слова во всех остальных кодах. Полная последовательность проверки кодов:


$01 -> 02 -> 03 -> 04 -> 05 -> 07 ->$
$08 -> 09 -> 10 -> 17 -> 18 -> 23 ->$
$20 -> 19 -> 22 -> 06 -> 16 -> 15 ->$
$21 -> 12 -> 11 -> 13 -> 14$


В результате, все слова в кодах определены, а словарь для группы 0 состоит из 394 слов.





28. Обделённый символ


(Назад | Оглавление | Вперёд)


Об одном символе я практически не говорил — о символе (29). Он встречается во многих кодах в комбинациях вроде (s)E — (29)(2) — (s)5 и похожих.


Поскольку перед ним идёт символ в режиме 0, а дальше переключатель между режимами 0 и 1 и символ в режиме 1, данный символ не вносит глобальных изменений в режим отображения. А проще — переключает лишь следующий символ.


Но раз он переключает из режима 0, а после нам всё-равно требуется переключение в режим 1, то этот символ должен выполнять переключение в некий режим 2 — вероятно режим отображения различных символов, которые не влезают в режим 1.


X Режим 0 Режим 1 Режим 2
29 (r2) $->->$
(только следующий символ)
(r2) $->$
(только следующий символ)

И не стоит забывать, что именно этот символ ставится для заполнения половины пустого слова перед специальными кодами (900): (928) или в конце кодов.





29. Результаты


(Назад | Оглавление | Вперёд)


Пришло время подвести итоги. Использовав 23 разных PDF417 кодов удалось определить значение всех 1 828 присутствующих в них слов. Было определено, что все возможные слова в таких кодах делятся на 3 группы по 929 штук, из которых построены словари на 394 (42.4%), 886 (95.4%) и 895 (96.3%) символов.


Слова (000): (899) используются для записи 900 разных значений в символьном или числовом представлениях. К примеру, в символьном, одно слово представляет собой 2 символа (по формуле $30 * X_1 + X_2$) согласно такой таблице:


Финальная таблица
X Режим 0 Режим 1 Режим 2
0 A 0
1 B 1
2 C 2 (был в кодах)
3 D 3
4 E 4
5 F 5
6 G 6
7 H 7
8 I 8
9 J 9
10 K
11 L
12 M
13 N
14 O
15 P
16 Q
17 R
18 S
19 T (разделяет фамилию и имя)
20 U
21 V
22 W (был в кодах)
23 X
24 Y
25 Z
26 (d) Разделитель (d) Разделитель
27
28 (s) Переключатель
$->$
(s) Переключатель
$<-$
29 (r2) $->->$
(только следующий символ)
(r2) $->$
(только следующий символ)

В числовом формате каждая группа до 44 цифр может быть представлена с помощью до 15 слов. Для записи $N$ цифр понадобится $N / 3 + 1$ слово, а для правильной записи к числу нужно дописать 1 слева и выполнить переход от базиса 10 к базису 900.


Переход между разными форматами записи информации осуществляется с помощью одного из "сервисных" слов (900): (928). К примеру, слово (900) переключает в символьный формат, а (902) — в числовой.


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


Если вы ещё не нажимали на ссылки, то все словари можно найти на GitHub. К примеру, остаточная версия словаря v0-13.





30. Послесловие


(Назад | Оглавление | Вперёд)


Возможно, я забыл упомянуть ещё что-то из результатов, но это не так важно. В любом случае, решение этой задачи было очень увлекательным, хоть и заняло достаточное количество времени, пару карандашей и множество листов в блокноте.


Кстати, КДПВ этой публикации собрана вручную по составленым мной словарям. Можете попробовать расшифровать её. Там есть одно неправильное слово вместо того, которого мне не хватило.


Возможно, вам будут также интересны статьи цикла Коды step by step:



Спасибо за внимание!


Update (2020-05-12): Возможно, вам будет интересно, как нужно читать / кодировать PDF417 по правилам.




P.S. Если вы нашли опечатки или ошибки в тексте, пожалуйста, сообщите мне. Это можно сделать выделив часть текста и нажав "Ctrl / ⌘ + Enter", если у вас есть Ctrl / ⌘, либо через личные сообщения. Если же оба варианта недоступны, напишите об ошибках в комментариях. Спасибо!

AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 13

    +1
    Только мне кажется, что самым рациональным шагом было бы изучение патента на PDF417 ну или хотя бы статьи в wikipedia, что с неизбежностью привело бы к патенту тынц
      +11

      Это если цель — просто узнать, как кодируется информация в PDF417. А если цель — развлечься на карантине, размять мозги и попрактиковаться в реверсинжиниринге протоколов, то вполне нормальная последовательность действий.

        +1

        Я не мог отказаться от всего веселья (: Нагуглить ответ можно в любой момент, но вот удовольствия от решения задачи уже не вернёшь

          +1
          Поражает вот что: как можно несколько дней (недель?) решать задачу и ни разу не подсмотреть в ответ, который находится рядом? Это да.
            0

            Несколько недель, но с достаточно большими перерывами. Когда приходило вдохновение, вспоминал снова и так по кругу.


            Для подсмотреть решение нужно отчаяться (как когда есть практически просроченный дедлайн, к примеру), а так — никакого смысла. Тем более, когда процесс приносит удовольствие, испытывать силу воли и не требуется

        +9
        Прямо увидел работу археолога будущего, который найдет «целлюлозную табличку с клинописью, датированную ориентировочно XX столетием н.э.».
          +10

          Поработаю невыносимым педантом, но шифр-это криптография. А PDF417, как и QR и прочее — коды. Поэтому информация не шифрованная, а кодированная. И не расшифровываем, а раскодируем или декодируем.

            +3
            Шифр — это код, к которому неизвестен ключ :)
              +1

              Таки Вы совсем неправы. Наоборот ещё можно с натяжкой согласиться, но так — определённо нет.


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

                +1
                Не имеет особого значения, тяжело код расшифровать или легко, все равно это делает компьютер. Если он тратит много ресурсов при этом — возможно, это обосновано тем, что у кода есть преимущество при передаче.
                Но вообще, смайлик намекает на то, что я не очень серьезен.
              0

              Спасибо за комментарий. Я повикипедил и исправил в заголовке "расшифровываем" на "дешифруем" (надеюсь, оно так пишется), а также исправил первый абзац. Для декодирования нужно было бы знать принцип кодирования и словарь

              +2
              Огонь)
                0

                Поскольку эти PDF417 коды из моей головы уходить никак не хотели, пришлось изучить патент, стандарты и всякое другое, чтобы выяснить, насколько я был далёк от истины. Ошибок в своих словарях я не нашел (за исключением пропусков, очевидно), а вот терминология — ну то такое (:


                Если вам любопытно, как же нужно работать с такими кодами на самом деле, записывать не только текст или числа, но и 8-битные значения, возможно вас заинтересует новая публикация:


                Коды step-by-step: читаем / кодируем PDF417

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое