Принц Персии NES: пароли

– Так, интересно, а подойдет ли пароль от Утиных Истории 2, тот самый, который 13324124? Утенок ведь ерунды не скажет! Попробуем набрать, что ли. Так... Ух ты! Открылся! Вот дела... 13 уровень? 81 минута осталась, что за?...

Как же так то? Почему он набрался и подошел?

В детстве я задавал себе этот вопрос и не мог найти ни единого разумного ответа. Это казалось какой-то фантастикой, невероятным совпадением и глэдстоунским везением. Да и я сейчас так считаю, на самом деле.

Так как же на самом деле работают эти пароли? Все оказалось не настолько сложно, как я думал.

§ Позиции цифр

Всего в пароле 8 цифр, каждая из которых кодирует некоторую свою часть. Есть две цифры, которые кодируют номер уровня – на позиции 1 и 7, две цифры, которые кодируют время – на позиции 0 и 3. Максимальное время может быть от нуля до 99, а максимальный уровень – 16. Причем, что интересно, уровень 15 и 16 – не существуют и представляют из себя лишь мусор. Попасть на них можно лишь только набрав код. Почему тогда они существуют? Это баг игры, при разработке игры никто даже и представить не мог, что код будет расшифрован и использован, потому защиту от переполнения делать, естественно, никто не стал.

Если же кодировать надо лишь время и уровень, а это 4 цифры, то что делают остальные 4? Оказывается, там есть такой параметр, который состоит из двух цифр, называется random, это некоторое случайное число, которое примешивается к коду и занимает позиции 2 и 5.

А что делают остальные 2 оставшиеся цифры на позиции 4 и 6? А там как раз содержится контрольная сумма для того, чтобы проверить, что введенный код был сформирован правильно и что тот, кто его набирает, не жульничал. Ведь без контрольного кода в любом случае на какой-нибудь уровень с неким рандомным временем, да было бы попадание. А тут шанс ровно в 99% процентов, что введенный от балды код будет ошибочным.

§ Контрольная сумма

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

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

Шаг 1. Считаем сумму первых четырех чисел -> t[0] + t[1] + t[2] + t[3]
Шаг 2. Эту сумму складываем с последней цифрой этой суммы и прибавить число t[5]. Например, если получилось число 14, то надо сложить 14 + 4 (последняя цифра).
Шаг 3. Аналогично, полученную сумму на шаге 2 складываем с десятками этой суммы и добавляем число t[7]. Например, если было получено число 23, то будет складываться 23 + 2, не 3!

Получится некоторое значение. Как можно отметить, не были использованы в поиске контрольной суммы числа в позиции 4 и 6. Это все потому, что там находится значение контрольной суммы, с которой как раз и сверять будем, а иначе бы просто никогда контрольную сумму свести нельзя было бы. Это примерно из того рода, чтобы сделать равным уравнение x + y = x, при этом y не равен 0.

Итак, теперь надо проверить. В позиции 6 будет старший десятичный разряд суммы, а в 4-й позиции – младший разряд. Допустим, если в позиции 6 будет число 3, а в 4-й позиции число 1, то тогда контрольная сумма для сверки будет числом 31.

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

§ Раскодирование уровня и времени

Здесь не так все просто, хотя проблема скорее не в том, что это очень уж сложно, а тут больше имеем дело с кольцами вычетов по модулю 10. Хотя, так сказал, что сам не понял.

Разберемся по шагам.

Шаг 1. Вычитаем из t[7] (здесь хранится информация об уровне) число t[5] (здесь рандомное число). Если получается отрицательное значение, то добавляется +10. На самом же деле просто имеем дело с кольцом. Например если вычесть из нуля единицу, то получается 9, потому что 9 – это предыдущее число к нулю. Например, 10 минус 1 это 9. Просто вращение младшего разряда десятичного числа. Запомним полученное число как L1.
Шаг 2. Выполняем тоже самое, но только вычитается t[1] (число уровня) минус t[2] (рандом). Если отрицательное, то тогда добавляется +10. Получается число L2. На самом деле, они, как L1, так и L2 никогда не могут быть более 3. Этому есть объяснение, поскольку оно так всегда и кодируется.
Шаг 3. Умножаем L1*4 и добавляем к нему L2. Тем самым получая уровень от 0 до 15, где 0 – это 1-й уровень, а 15 – это 16-й.

Как можно заметить, на самом деле L1 и L2 это части одного и того же числа. L2 – это младшие 2 бита уровня, а L1 – это старшие 2 бита. Уровень же кодируется 4 битами, но они специально разнесены на 2 десятичные цифры, чтобы запутать.

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

Шаг 1. Вычитается t[0] – t[2], получаем T1. Так же как и в L1, L2, при отрицательном числе добавляется +10
Шаг 2. Вычитается t[3] – t[5], получаем T2. Не забываем про отрицательные значения.
Шаг 3. В итоге, T1 – это старший разряд времени, T2 – младший, ну или T = 10*T1 + T2.

Код, которые реализует декодирование:

int prince_decode(const char password[], int& level, int& time)

{

int sum = 0;

int t[8];

for (int i = 0; i < 8; i++)

{

t[i] = password[i];

if (t[i] >= '0') t[i] -= '0';

sum += t[i];

}

if (!sum) return 0; //code 00000000

int r1 = t[2];

int r2 = t[5];

int n1 = t[0] + t[1] + r1 + t[3];

int n2 = n1 + (n1 % 10) + t[5];

int n3 = n2 + (n2 / 10) + t[7];

int valid = (t[6]*10 + t[4]) == (n3);

if (!valid) {

return 0;

}

int level1 = ((10 + (t[7] - r2)) % 10) << 2;

int level2 = ((10 + (t[1] - r1)) % 10) & 15;

level = ((level1 + level2) & 15);

int time1 = ((10 + (t[0] - r1)) % 10)*10;

int time2 = ( 10 + (t[3] - r2)) % 10;

time = (time1 + time2);

return 1;

}

§ Кодирование

А теперь давайте сделаем обратный ход и закодируем в пароль из заранее известных номера уровня L (от 0 до 15) и времени T (от 0 до 99).

Шаг 1. В самом начале выбираются два совершенно случайных числа в позиции t[2] и t[5]
Шаг 2. Берем младшие 2 бита от номера уровня. К примеру, если это уровень 11, то в двоичном коде это будет представлено как 1011b. Младшие 2 бита – число 11b или число 3 в десятичной системе счисления. Добавляем к нему число из позиции t[2], и последнюю цифру результата помещаем в позицию t[1].
Шаг 3. Берем старшие 2 бита от уровня, у нас это было 10b или число 2, и добавляем к t[5]. Аналогично, последнюю цифру результата помещаем в позицию t[7].

Номер уровня закодирован успешно. Теперь кодируем время.

Шаг 1. Берутся десятки от заданного числа. Допустим, если мы кодируем 42 минуты, то возьмем число 4. К нему так же добавляется +t[2] и последняя цифра результата записывается в позицию 0.
Шаг 2. Берем единицы от значения времени. В нашем случае это 2 (т.к. число 42). Добавляется к нему +t[5] и последняя цифра записывается в позицию t[3].

Шесть и восьми цифр заполнено. Теперь осталось найти контрольную сумму. Алгоритм поиска контрольной суммы абсолютно идентичен тому, что разбиралось ранее. Я просто представляю его код:

n1 = t[0] + t[1] + t[2] + t[3];

n2 = n1 + (n1 % 10) + t[5];

n3 = n2 + (n2 / 10) + t[7];

То есть, сначала считаются 4 первые цифры, потом полученную сумму складываем с младшим десятичным разрядом и прибавляем +t[5], и эту сумму складываем со старшим разрядом и добавляем +t[7].

Старший разряд (десятки), помещаются в t[6], а младший – в t[4]. Пароль готов!

§ Получение пароля по параметрам

Представлены параметры level, time и random (любое число). Результат будет записал в аргумент t.

void prince_encode(int level, int time, int random, char t[])

{

int r1 = random / 10;

int r2 = random % 10;

t[2] = r1;

t[5] = r2;

t[1] = ((level & 3) + r1) % 10;

t[7] = ((level >> 2) + r2) % 10;

t[0] = ((time / 10) + r1) % 10;

t[3] = ((time % 10) + r2) % 10;

int n1 = t[0] + t[1] + r1 + t[3];

int n2 = n1 + (n1 % 10) + t[5];

int n3 = n2 + (n2 / 10) + t[7];

t[4] = (n3 % 10);

t[6] = (n3 / 10);

// Если необходимо перевести строку в ASCII

for (int i = 0; i < 8; i++) t[i] += '0'; t[8] = 0;

}

§ Пример функции main

int main(int argc, char* argv[]) {

int level, time;

char t[9];

// Генератор пароля

prince_encode(2, 51, 33, t);

printf("PASSWORD: %s\n", t);

// Декодирование пароля

if (prince_decode(t, level, time)) {

printf("LEVEL=%d TIME=%d\n", level, time);

} else {

printf("PASSWORD INVALID\n");

}