Pull to refresh

Простейшее шифрование или разбор структуры паролей Road Rash 3 по косточкам

Algorithms *
Sandbox
Добрый день, уважаемые хабрапользователи.
Да-да, заголовок вас не обманул: сегодня мы вспомним про старую добрую консольную игру Road Rash 3.

image

Думаю, многие из вас с удовольствием вспоминают, как просиживали часами в гордом одиночестве или в шумной компании друзей, наматывая виртуальные километры в этой, без преувеличения, культовой игре. Так же и я в один из вечеров решил вспомнить молодость и пройти пару уровней в любимых гонках. И вот, вооружившись эмулятором и геймпадом, начал восхождение по карьерной лестнице. Все шло замечательно, но в один прекрасный момент у игры что-то перемкнуло и она отказалась переводить меня на новый уровень, хотя все условия для этого были выполнены. Расстраивался я не долго, т.к. знал, что в игре есть своеобразная система паролей для сохранения набранных достижений. Нужно было всего лишь немного «подкрутить» существующий пароль методом тыка, чтобы вручную перевести себя на новый злополучный уровень и с чистой совестью продолжить соревнования.

Но это было слишком просто и, честно говоря, не интересно. У меня сразу промелькнула мысль: «А как оно работает»? И я загорелся идеей узнать сам алгоритм генерации пароля, чтобы иметь возможность в дальнейшем самому его создавать, исходя из конкретных потребностей или просто настроения.

Немного теории


Итак, что же из себя представляет Road Rash 3? Это гонки на крутых спортивных мотоциклах по дорогам различных стран под великолепную 8-битную музыку. Чем выше место вы занимаете в заезде, тем больше денег вы получаете, которым затем можно потратить на покупку нового железного коня или на его модернизацию. Особый интерес представляет возможность драться с соперниками прямо во время гони на огромной скорости, отнимать у них новое оружие и с его помощью еще сильнее избивать незадачливых конкурентов. Описание описанием, но перейдем ближе к цифрам.

В сухом остатке мы имеем следующие игровые параметры:
  • денежная сумма (от 0$ до 655350$ с шагом в 10$);
  • мотоцикл (один из 16 возможных);
  • улучшения на него (4 улучшения в различных комбинациях);
  • текущий уровень (один из 5 возможных);
  • пройденные трассы на этом уровне (5 трасс в различных комбинациях).
К сожалению, возможность сохранять оружие разработчики не предусмотрели, так что после каждой перезагрузки оно сбрасывается.

Теперь взглянем на сам пароль:

image

Всего 8 позиций для символов. Каждый символ может принимать значения 0-9 и A-V. Итого получаем 32 возможных символа в каждой позиции.

Самое интересное


Итак, приступим.
Не буду утомлять вас долгими рассказами о том, как я выводил все эти зависимости и алгоритмы, потратив много часов на эксперименты, перейду сразу к делу.
Возможно, многие из вас подумали: «Как же уместить столько параметров в такой маленький пароль?», — очень просто. Все дело в хитрой логике и замысловатых алгоритмах. Далее вы увидите, как это происходит.

Деньги, деньги и еще раз деньги

image

За деньги отвечают первые 4 позиции пароля.
C440 xxxx
Но не все так просто и очевидно. Тут есть свои хитрости.
1 и 2 позиции отвечают за суммы до 2550$ включительно, 3 и 4 позиции – за суммы выше 2550$.

К примеру, если у нас есть сумма 5500$ это (2 * 2560$ + 380$).
Так вот за 2 * 2560$ = 5120$ будут отвечать 3 и 4 позиции, а за остаток в виде 380$ — 1 и 2 позиции.

Начнем с малого: 1 и 2 позиции и суммы менее 2550$

Теперь копаем вглубь, продолжая рассматривать наш пример. Как эти 380$ хранятся в 1 и 2 позициях? Происходит это следующим образом.

image
Таблица 1. 1 и 2 позиции пароля — мелкие деньги

1 позиция отвечает за суммы от 0$ до 150$ включительно с шагом в 10$.
Аналогично со 2 позицией. Только теперь каждый шаг не прибавляет 10$, а увеличивает на 1 множитель для 160$. Т.е. сколько раз нам нужно взять по 160$: 0, 1, 2 и т.д.

Представить «на пальцах» это можно следующим образом. Есть у нас 10$, добавляем в ним еще 10, еще 10 и так далее, пока не дойдем до 150. Все это время у нас накручивается только символ в 1 позиции. Как дошли до 150, добавляем еще 10 и перепрыгиваем во вторую позицию, в которой уже будет 160. Дальше, прибавляя по 10, опять будем крутить символ в первой позиции, пока не дойдем до 150 и опять перепрыгнем на 2 позицию, где уже будет 160 + 160 = 320.

Посмотрев на таблицу, можно увидеть, что берутся только четные символы (0, 2, 4...). Для чего? Об этом чуть позже.

Таким образом, мы можем покрыть любую сумму в пределах 2550$.
Посмотрим на остаток из примера выше: 380$ = 2 * 160$ + 60$.

60$ — первая позиция (меньше 160$). Этой сумме соответствует символ «C».
2 * 160$ — вторая позиция. Этой сумме соответствует символ «4».

То есть сумму в 380$ можно записать как «C4».

Теперь рассмотрим 3 и 4 позиции и суммы более 2550$.

Здесь, в общем то, все аналогично.

image
Таблица 2. 3 и 4 позиции пароля — крупные деньги

Каждый четный символ 3 позиции дает +2560$ и так вплоть до 38400$ = 15 * 2560$.
Каждый четный символ 4 позиции есть множитель для 40960$ = 16 * 2560$, т.е. сколько раз нужно взять по 40960$: 0, 1, 2 и т.д. (это немного упрощенный алгоритм для 4 позиции и далее мы к нему еще вернемся).
Таким образом мы покрываем любую сумму от 2560$ и до 655350$.

В нашем примере у нас осталось 5120$. Это, как можно заметить, меньше 40960$, поэтому 4 позиция остается нулем (нам нужно взять ноль раз по 40960$). Ну а символ 3 позиции, соответствующий 5120$ = 2 * 2560$ есть «4» (см. Табл. 2).

В итоге мы получили комбинацию «C440» для первых четырех позиций, описывающую сумму в 5500$.

Уровень

image

С уровнем все очень просто и прозрачно. За него отвечает 5 позиция пароля и всего лишь 5 символов:
xxxx 1xxx
1 – первый уровень;
2 – второй уровень;
3 – третий уровень;
4 – четвертый уровень;
5 – пятый уровень;

Улучшения (апгрейды)

Улучшений, как вы помните, у нас всего четыре.

image

В алгоритме они разбиты логически на 2 группы:
  1. производительность и подвеска (performance и suspension);
  2. защита и шины (protection и tires).
Здесь и начинаются интересные хитрости. Апгрейды не имеют собственных позиций в пароле, а делят их совместно с другими параметрами: первую группу приютили у себя «деньги», а вторую – «уровень».

Сперва о первой паре

Вернемся к 1 и 2 позициям пароля. Помните, раньше я упоминал о том, что символы для денег берутся через один, т.е. только четные? В этом и кроется один из секретов.
Если мы хотим установить себе производительность (performance), то нужно символ в 1 позиции увеличить на один, а если мы хотим установить подвеску (suspension), то нужно увеличить на один символ во 2 позиции.
С4xx xxxx
Таким образом мы используем образовавшееся за счет пропуска нечетных символов «окно», что позволяет нам при одной и той же сумме как иметь улучшение, так и не иметь его.

Рассмотрим подробнее на примере.
Наши первые два символа – «C4» соответствуют сумме 380$ и отсутствию апгрейдов.
Хотите себе новенький движок? Не проблема! Увеличиваем символ в 1 позиции на один и получаем «D4». При этом денежная сумма не изменилась! Она изменится только при увеличении еще на один, т.е. до «E4» (см. Табл. 1).
Аналогично и с подвеской: увеличиваем символ во 2 позиции на один и получаем «D5». При этом сумма осталась такой же: 380$.

Теперь о второй паре апгрейдов

Как я упомянул выше, они прописались в 5 позиции (уровень). Но на этот раз алгоритм немного иной.
Факт наличия шин (tires) увеличивает символ в 5 позиции на 8. Наличие защиты (protection) увеличивает этот же символ на 16.

Рассмотрим ситуацию для 1 уровня:
  • 1 уровень без улучшений: xxxx 1xxx;
  • 1 уровень с шинами: xxxx 9xxx (+8);
  • 1 уровень с защитой: xxxx Hxxx (+16);
  • 1 уровень с шинами и защитой: xxxx Pxxx (+8+16);
Для 3 уровня, например, ряд будет выглядеть так: 3/B/J/R.

Таким образом получается, что за улучшения отвечают 1, 2 и 5 позиции пароля.
С4xx 1xxx

Пройденные трассы

Всего на уровне 5 трасс, проходить их можно в любой последовательности.

image

За этот параметр у нас отвечает символ в 7 позиции пароля.
xxxx xxEx
Логично предположить, что факт прохождения конкретной трассы отмечается каким-то флагом и имеет значение 0 или 1 для нее (пройдено/не пройдено).
Из всех наших 5 трасс легко составить обычное двоичное число, отражающее все возможные комбинации пройденных и не пройденных трасс.

image
Таблица 3. 7 позиция пароля — пройденные трассы

Здесь каждый разряд отвечает за одну из 5 трасс. К примеру, 01010 показывает, что 1, 3 и 5 трассы не пройдены, а 2 и 4 – пройдены.
Теперь, проецируя это двоичное число на наш буквенно-цифровой ряд символов, получаем соответствующий символ для 7 позиции пароля. В нашем случае это символ "A".

Мотоцикл и еще немного денег

А теперь приступим к самому сложному – мотоциклу.
В этом случае завязаны сразу 3 позиции (3, 4 и 6) по довольно замысловатому алгоритму.
xx40 x1xx
Попытаюсь как можно проще объяснить его.

Сам мотоцикл выбирается не очень сложно. Всего их 16 и отвечает за них 6 позиция в пароле.
xxxx xBxxx
Здесь, как и раньше в деньгах, символы перепрыгивают через один и сгруппированы по парам.

image
Таблица 4. 6 позиция пароля — мотоцикл

К примеру, 0 и 1 – первый мотоцикл, 2 и 3 – второй, 4 и 5 – третий и т.д. до конца. Вся сложность заключается в том, чтобы определить, какой из двух символов выбрать из конкретной пары.

Для того, чтобы понять последовательность действий, вернемся назад к 3 и 4 позициям.
3 позиция может быть представлена только четными символами (0, 2, 4, 6 и т.д.). Нечетных здесь быть не может в принципе ни при каких условиях. А вот символы 4 позиции, также как и шестой (мотоцикл) сгруппированы по парам: 0 и 1 – 0$, 2 и 3 – 40960$, 4 и 5 – 2 * 40960$ и т.д (ранее, при объяснении 4 позиции я говорил об упрощении, которое допустил там для простоты; теперь вы видите полную картину).

image
Таблица 5. 3 и 4 позиции пароля — крупные деньги (полная версия)

Таким образом, перед нами стоит 2 задачи:
  1. выбрать один из двух возможных символов для 4 позиции;
  2. выбрать один из двух возможных символов для 6 позиций.
Первым делом разберемся с мотоциклом

Разработчики отвели душу на славу и сделали целых четыре маски для выбора мотоцикла. Вы их видите ниже на изображении.

image
Таблица 6. Маска для 6 позиции пароля (мотоцикла)

Фиолетовым выделены те символы, которые следует выбирать для соответствующей группы (мотоцикла). К примеру, если мы попали на 3 маску и хотим выбрать 10 мотоцикл, то должны взять символ «J» для 6 позиции пароля.

Теперь о том, как же нам нужно выбирать саму маску.
Можно заметить, что эта самая маска как бы поднимается вверх на одну клеточку при увеличении ее номера. Т.е. маска №2 есть ни кто иное, как маска №1, сдвинутая вверх на одну позицию. Зависит маска от 3 и 4 позиций пароля. Вы можете вполне обоснованно спросить: «Как же она будет зависеть от 4 позиции, если мы еще не определились, какой из двух символов туда подставлять?», — очень просто: зависит она не от самого символа, а именно от группы символов, т.е. 0 и 1 – первая группа, 2 и 3 – вторая группа и т.д (см. Табл. 5). Такая же группа есть и у символов 3 позиции, только там она состоит из одного символа, т.к. нечетных символов там не бывает вообще: 0 – первая группа, 2 – вторая и т.д. Номер этой группы можно посмотреть в первом столбце таблицы 5.

Теперь сама арифметика: нужно вычислить выражение
{3} + {4} – 2,
где {3} и {4} – номера, соответственно, группы символов для 3 и 4 позиции (см Табл. 5).
Если оно окажется кратным 4, то выбираем первую маску, если остаток от деления на 4n (n – целое положительное) будет равен 1, то выбираем вторую маску, если 2 – третью, если 3 – четвертую.

Возвращаясь к нашему примеру, 3 и 4 позиции у нас были «40».
4 – третья группа, 0 – первая (см. Табл. 5).
Имеем {3} + {4} – 2 = 3 + 1 – 2 = 2.
Остаток от деления на 4n равен 2, значит, выбираем 3 маску для мотоцикла.
Таким образом, для 5 мотоцикла имеем символ «9» в 6 позиции пароля.

Финальный рывок

Нам остался последний шаг, а именно выбор одного из двух символов для 4 позиции. Вот тут возникла заминочка… У меня уже мозги закипели от попыток объяснить это просто и наглядно. Не объясняется оно так…

В общем, смотрите.

image
Таблица 7. Выбор символа для 4 позиции пароля

Посмотрим на любую из 4 масок, например, на первую, а именно на ее фиолетовую часть. Символы как бы сгруппированы по два: фиолетовый, под ним фиолетовый, сдвиг вправо, опять 2 фиолетовых друг под другом, сдвиг влево, опять 2 фиолетовых друг под другом и так далее. Так вот, представим, что каждому первому символу в этой группе соответствует единичка, а каждому второму – двойка. Смотря на первую маску сверху вниз: 1, 2, 1, 2, 1, 2… Со второй будет так: 2, 1, 2, 1, 2 и т.д. Суть, надеюсь, понятна. К чему эти единички и двойки? А вот к чему. В нашем примере мы выбираем символ в четвертой позиции из 0 и 1 (напомню, 3 и 4 символы у нас "40"; 4 всегда будет собой, а вот 0 еще не окончателен: он можеть быть как 0, так и 1 (см. Табл. 5)). Так же мы знаем, что маска у нас третья (вычислили выражение выше). Поэтому смотрим на 3 маску и находим в ней нашу группу (0 и 1) — она первая сверху. Ей, как мы посчитали только что, соответствует единичка, значит берем мы первый символ из этой группы, т.е. «0».

Рассмотрим еще один пример для чистоты: работаем мы со второй маской и символ для 4 позиции выбираем из C и D. Смотрим на 2 маску: C и D являются вторыми в фиолетовом вертикальном блоке, значит выбираем мы второй символ, т.е. «D».

Напоследок


На закуску у нас осталась 8 позиция.
xxxx xxxM
Тут все довольно очевидно – это контрольная сумма. Изменение каждой из первых семи позиций влияет на нее каким-то образом. К сожалению, алгоритмов ее расчета я привести не смогу. И так слишком много времени убил на выяснение механизма работы, к тому же там было бы еще больше теории. Да и боюсь, статья уже растянулась до неприличных размеров. Так что просто примем за факт, что там располагается контрольная сумма, неким образом зависящая от первых семи позиций пароля.

Вместо заключения


Поздравляю вас, вы настоящий герой, если на самом деле дочитали до этого места и еще что-то поняли ;)
На бумаге все объяснить оказалось ужасно сложно и получился несвязный бред, но на самом деле теория довольно легкая, если немного вдуматься и попытаться понять ее. Старался как мог показать все предельно просто и наглядно. Надеюсь, хотя бы капельку у меня это получилось. Если что-то осталось вами непонятно, задавайте вопросы в комментариях — я отвечу.

Для чего эта статья и кому она вообще нужна?

Алгоритмы, приведенные здесь, помогут понять основы шифрования на практике, да и вообще удовлетворить интерес людей: «А как же оно работает»? А так же, надеюсь, статью будет интересно почитать людям, ностальгирующим по временам любимых 16-битных гонок на сеге.

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

image
Скачать
Скачать 2
Скачать 3

8 символа, как вы, я надеюсь, уже прочитали выше, нет, но быстро перебрать вручную максимум 32 варианта для него не составит труда.

P.S. Для того, чтобы поиграть в сегу на компьютере требуется эмулятор (я пользуюсь WGens) и сам ром игры. Все без проблем находится в интернете.
P.P.S. Поздравляю всех россиян и наших соседей с победой в голосовании на право проведения чемпионата мира по футболу в 2018 году!

Спасибо за внимание и до новых встреч на просторах хабра!
Tags:
Hubs:
Total votes 134: ↑126 and ↓8 +118
Views 16K
Comments Comments 65