Признавайтесь, кто в детстве часами напролёт просиживал за игрой в «Денди» или «Сегу»? А кто по мере прохождения игры записывал пароли на бумажку или в специально заведённую тетрадку? Если это вы, и раз уж вы читаете этот сайт, то у вас наверняка хоть раз возникал вопрос: «а как же это работает?»Я постараюсь объяснить принципы работы классических механизмов генерации паролей на примерах из игр моего детства. Заранее прошу меня извинить за то, что все примеры будут с платформы NES (да, та, которая «Денди»), хотя тематика только ею не ограничивается. Так уж получилось, что не нашёл в себе достаточно мотивации, чтобы провести немного больше исследований и написать немного больше текста.
Примеры буду приводить в порядке от простого к сложному. Поначалу кода будет немного, но чем дальше — тем сложнее объяснить алгоритмы языком человеческим и тем проще объяснить их языком техническим, так что не обессудьте.
Кодовая книга
У меня в памяти до сих пор сидят пароли некоторых уровней из игр моего детства — например, «BCHK» из «Trolls in Crazyland» («Doki! Doki! Yuuenchi»), «4660» из «Choujin Sentai — Jetman». Можно сказать, что это идеальные с точки зрения удобства пароли: их легко запомнить и трудно ошибиться при вводе. Но сколько же информации они могут содержать, и каков шанс случайно подобрать такой пароль?В первом случае алфавит пароля составляет 24 символа. Если посчитать количество комбинаций символов, то это будет 244 — не так уж и мало, учитывая, что в игре всего 12 уровней, и, собственно, кроме номера уровня пароль в себе ничего не хранит. Учтём несколько секретных паролей и посчитаем вероятность подобрать пароль с одной попытки: (12 + 4) / 244, что равно ~5.7×10-14. Другими словами, придётся перепробовать в среднем 17592186044416 паролей, прежде чем мы подберём какой-нибудь реальный.
Во втором случае всё несколько иначе. Очевидно, что набор из 4-х цифр даёт нам ровно 10000 (104) комбинаций. Игра содержит пять уровней, которые можно проходить в разном порядке и два уровня сложности. Т.е. пароль хранит информацию о пройденных уровнях и уровне сложности. Таки образом, число существующих паролей равно 2×25, т.е. 64. Отсюда вероятность подобрать пароль равна 0.0064, т.е. больше, чем полпроцента. Мало ли это? В среднем примерно каждый 156-й пароль окажется верным, а учитывая довольно высокую скорость перебора, поиски долго не продлятся. И, честно признаюсь, в детстве мы часто «брутфорсили» игру, когда не хотелось начинать с самого начала.На самом деле информационную ёмкость таких паролей оценивать бессмысленно, поскольку они являются лишь своего рода ключами, т.е. игры просто хранят все возможные пароли, и по индексу введённого пароля получают информацию об уровне и прочем. Но интереса ради скажу, что их теоретическая ёмкость составляет 48 и 13 бит (log2244 и log2104).
И всё же, как именно обрабатываются введённые пароли? В первом случае введённый пароль вообще не подвергается каким-либо преобразованиям, а просто ищется в хранимом массиве паролей.
Показать код
const char* s_passwords[12] =
{
" ",
"BLNK",
// ...
"MZSX"
};
// ...
if (strncmp(pass, s_secretPassword1, 4) == 0)
{
callSecret1();
return 0;
}
// ...
for (int level = 0; level < 12; level++)
{
if (strncmp(pass, s_passwords[level], 4) == 0)
{
return level;
}
}
return -1;
А во втором случае игра поступает несколько хитрее, и сперва пароль подвергаются конвертированию в двоично-десятичный код, что уменьшает его размер ровно в два раза. Это даёт возможность и в самой игре уменьшить размер паролей в два раза.
Показать код
uint16 toBCD(const char* pass)
{
uint16 result = 0;
for (int i = 0; i < 4; i++)
{
result <<= 4;
result |= (pass[i] - '0') & 0xF;
}
return result;
}
s_passwords[2][32] =
{
{
0x0000,
// ...
0x4660
},
{
0x7899,
// ...
0x5705
}
};
// ...
const uint16 pass = toBCD(passStr);
for (int difficulty = 0; difficulty < 2; difficulty++)
{
for (int clearedLevels = 0; clearedLevels <= 0x1F; clearedLevels++)
{
if (pass == s_passwords[difficulty][clearedLevels])
{
setState(difficulty, clearedLevels);
return true;
}
}
}
return false;
Числа и цифры
Не посмею обойти стороной и классику: уверен, многие играли в оригинального «Принца Персии», и не только на «Денди». Пароли игры тоже представляют собой последовательности десятичных цифр, но на этот раз они действительно кодируют некоторые данные.А именно кодируются два значения: время и номер уровня. Т.к. пароль имеет длину в 8 цифр, т.е. 100 000 000 комбинаций, а в игре 14 уровней и 60 возможных значений времени (итого 840 вариантов), можно предположить, что его сложно подобрать. Но на самом деле это не так, и чтобы понять, почему, давайте сначала разберём принцип его генерации.
Итак, сперва игра создаёт массив из 8-ми элементов, которые могут хранить значения от 0 до 9. Затем генерируется два случайных значения — тоже от 0 до 9 — и записываются в этот массив по индексам 2 и 5. Эти случайные значения — инкременты, которые будут добавляться к сохраняемым значениям по модулю 10. Это увеличивает количество возможных паролей в 100 раз, что, очевидно, усложняет выявление закономерностей.
const uint8 rand0 = rand() % 10;
const uint8 rand1 = rand() % 10;
char pass[8] = {0, 0, rand0, 0, 0, rand1, 0, 0};
Далее кодируется индекс уровня (т.е. его номер минус единица): сумма двух старших бит индекса и второго инкремента по модулю 10 записывается по индексу 7, а сумма двух младших бит и первого инкремента — по индексу 1.
// Кодируем два старших бита номера уровня
pass[7] = ((level >> 2) + rand1) % 10;
// Кодируем два младших бита
pass[1] = ((level & 3) + rand0) % 10;
Настал черёд времени. С ним немного проще: сумма десятков и первого инкремента по модулю 10 записывается по индексу 0, а сумма единиц и второго инкремента по индексу 3. Получается, что при инкрементах, равных нулю, время запишется в десятичных цифрах, как есть. И, поскольку потолком десятков является 9, то максимально возможным значением времени является 99, а не «честные» 60 минут.
// Кодируем старшую цифру времени
pass[0] = ((time / 10) + rand0) % 10;
// Кодируем младшую цифру времени
pass[3] = ((time % 10) + rand1) % 10;
Данные записаны, осталось посчитать контрольную сумму для проверки валидности пароля.
// Считаем контрольную сумму
sum = pass[0] + pass[1] + pass[2] + pass[3];
sum += (sum % 10) + pass[5];
sum += (sum / 10) + pass[7];
// Записываем контрольную сумму
pass[4] = sum % 10;
pass[6] = sum / 10;
Вот, например, легенда пароля 13-го уровня c 32-я оставшимися минутами — «96635134».
Становится очевидно, что для подбора пароля достаточно, чтобы контрольная сумма подходила к закодированным данным. Тогда, если не учитывать её специфику, можно посчитать вероятность подобрать пароль: ровно 1% (единица делить на количество возможных значений суммы) — довольно много.
Но ведь это же просто обыкновенная сумма! И для разных данных она может получиться одинаковой. Если изменить любой валидный пароль так, чтобы сумма первых 4-х цифр осталась прежней — он подойдёт. Что уж говорить о том, что у обыкновенной суммы распределение вовсе не равномерное, да и максимальное значение такой суммы никогда не превысит 72.
Учитывая специфику такой суммы, выходит, что при линейном переборе вероятность её совпадения с данными очень велика. Именно поэтому на тематических форумах в сети можно часто встретить воспоминания людей о том, как ловко они подбирали пароли к Принцу Персии.
Позиционные системы счисления
Наверняка многие знакомы с Base64 и Base32. По своему определению это позиционные системы счисления с основаниями 64 и 32 соответственно. Принцип прост: разбиваем битовый поток на значения фиксированной битовой длины, а затем по определённому словарю берём символы по полученным значениям в качестве индексов.На таком принципе основаны многие системы паролей. И следующая игра, на примере которой я расскажу алгоритм генерации паролей, будет Takahashi Meijin no Bouken Jima IV, в простонародье больше известная как Adventure Island 4.
Состояние игры включает в себя набор имеющихся предметов (до 12-ти), способностей (до 3-х), специальных предметов (до 6-ти), собранных сердец (до 8-ми), локацию с яйцом и информацию о пройденных уровнях. Но на самом деле за всё, кроме сердец и специальных предметов, отвечает одно значение — индекс прогресса. Это индекс в массиве, где каждый элемент хранит информацию об имеющихся предметах, способностях и прочем. Проще говоря, именно этот байт определяет набор предметов, способностей и пройденных этапов.Первый шаг алгоритма заключается в построении массива из четырёх байт. В первый байт записывается значение прогресса. Интересно, что допустимы только определённые его значения
Во второй байт записывается маска имеющихся специальных предметов — 6 старших бит байта. В оставшиеся младшие 2 бита записывается константа, равная единице. Я предполагаю, что это версия формата пароля. А возможно и просто константа более строгой верификации введённых паролей.
В третий байт записывается индекс локации, где установлено яйцо (для тех, кто не играл — своеобразный чекпоинт). Если яйцо нигде не установлено, то значение равно 0xFF. Индекс локации с яйцом тоже может принимать только определённые значения — туда входят только те локации, где яйцо можно установить.
И, наконец, в четвёртый байт копируется маска собранных сердец и полусердец.
Показать таблицы
// Маски предметов в зависимости от значения прогресса
const uint8 s_itemsInProgress[] = {
0x8000, 0xC000, 0xC000, 0xC000, 0xE000, 0xF000, 0xF000, 0xF000,
0xF000, 0xF800, 0xFC00, 0xFC00, 0xFC00, 0xFC00, 0xFE00, 0xFF00,
0xFF00, 0xFF00, 0xFF00, 0xFF00, 0xFF80, 0xFF80, 0xFF80, 0xFFC0,
0xFFC0, 0xFFE0, 0xFFE0, 0xFFF0, 0xFFF0, 0xFFF0, 0xFFFC, 0xFFFE,
0xFFFF, 0xFFFF
};
// Маски способностей в зависимости от значения прогресса
const uint8 s_powersInProgress[] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x80, 0x80, 0x80, 0x80, 0x80,
0x80, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xE0, 0xE0,
0xE0, 0xE0, 0xE0, 0xE0, 0xE0, 0xE0, 0xE0, 0xE0,
0xE0, 0xE0
};
// Допустимые для яйца локации
const uint8 s_accessibleEggLocations[] = {
0x04, 0x07, 0x16, 0x1B, 0x2F, 0x31, 0x41, 0x43,
0x45, 0x47, 0x4E, 0x52, 0x57, 0x87, 0x98, 0x9C,
0x9E, 0xA0, 0xA1, 0xA2, 0xA4, 0xB1, 0xB3, 0xB5,
0xFF, 0x0C
};
// Допустимые значения прогресса
const uint8 s_accessibleProgressValues[] = {
0, 1, 4, 5,
6, 9, 10, 11,
14, 15, 16, 17,
20, 21, 22, 23,
26, 27, 28, 29
};
const uint8 s_version = 1;
// ...
uint8 data[4] = {progress, specItems | s_version, eggLocation, hearts};
Затем пароль кодируется аналогично Base32, но с другим алфавитом: из этого массива поочерёдно берётся по 5 бит и записывается в отдельные байты массива из восьми элементов. При этом с помощью операции «xor» считается контрольная сумма, которая записывается в последний байт массива.
В свободные биты шестого байта дописывается индекс таблицы кодирования. В начале игры этот индекс вычисляется случайным образом (значение от 0 до 3), но в рамках одного прохождения всегда будет использоваться только он. Т.е. может быть 4 варианта одного и того же пароля.
uint8 password[8] = {};
for (var i = 0; i < 7; i++)
{
password[i] = takeBits(data, 5);
password[7] ^= password[i];
}
password[6] |= (tableIndex << 3);
password[7] ^= password[6];
Последний этап: по индексу берётся одна из четырёх таблиц кодирования «Base32», и полученный массив преобразуется в текст. Элементы массива используются как индексы символов.
const char* s_encodeTables[] = {
"3CJV?N4Y0FP78BS1GW2QL6ZM9TR5KDXH",
"JT1W9M3DV5?ZKX6GC0FB2SPHR4N8LY7Q",
"R0CXM8TWB3G56PKY4FVND7QL2JZ19HS?",
"8JWB3PD0?RVG5L2KX4QFZ9TN1S6MH7YC"
};
char passwordStr[11] = "";
int index = 0;
for (var i = 0; i < 8; i++)
{
passwordStr[index++] = s_encodeTables[tableIndex][password[i]];
if (i == 3 || i == 5)
{
passwordStr[index++] = '-';
}
}
Существует 328 возможных вариантов пароля. Несложно посчитать количество подходящих паролей — достаточно перемножить количество допустимых значений каждой из кодируемых переменных. Итак, мы можем кодировать 26 локаций яйца, 20 различных значений прогресса, 256 (28) комбинаций собранных сердец, 64 (26) комбинации специальных предметов и 4 варианта пароля. Итого: 26×20×256×64×4 = 34078720 паролей. Отсюда вероятность подобрать пароль равна ~0.03% — нам понадобится в среднем 32264 попытки.
Графический беспредел
В некоторых случаях разработчики проявляют оригинальность и используют графические пароли. С ними можно было столкнуться, например, в играх серии Mega Man. Конечно, удобство таких паролей сомнительно — особенно с непривычки. Но это ничего, по сравнению с длинными паролями на японском, на освещение которых в этой статье у меня, увы, сил не хватило.В качестве примера я возьму игру Power Blade 2. В ней используется пароль, состоящий из 12-ти иконок бонусов, расположенных в сетке 4x3. Всего есть 8 разных иконок, включая пустую. На самом деле, разница между символьным паролем и графическим паролем такого рода лишь в представлении его элементов, если заменить иконки на символы — сути не изменится.
Каждому значку соответствует число от 0 до 7, в соответствии с их порядком появления при наборе пароля:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
 |
 |
 |
 |
 |
 |
 |
 |
Несложно посчитать, что мы имеем 812 комбинаций, хотя игра сохраняет лишь информацию о пройденных уровнях и имеющихся костюмах. Всего 5 уровней (не считая финального), которые можно проходить в произвольном порядке, и 4 костюма. Т.е. 5 бит и 4 бита соответственно, 9 бит в сумме. Пароль же имеет ёмкость 12×log28, т.е. 36 бит — более, чем достаточно.
Начиная генерацию пароля, игра, как обычно, формирует массив. На этот раз сразу из 12-ти элементов, каждый из которых соответствует ячейке пароля. Каждая ячейка имеет ёмкость 3 бита, и игра записывает в них по 2 бита значения, оставляя младший бит для контрольной суммы.
uint8 pass[12] = {};
// Запись двух младших бит
pass[7] = (clearedLevelsMask & 0x3) << 1;
// Запись следующих двух
pass[9] = (clearedLevelsMask & 0xC) >>> 1;
// Запись последнего бита
pass[11] = (clearedLevelsMask & 0x10) >>> 2;
// Запись двух младших бит
pass[8] = (suitsMask & 0x3) << 1;
// Запись двух старших бит
pass[10] = (suitsMask & 0xC) >>> 1;
Затем считается 6-битная контрольная сумма, представляющая собой арифметическую сумму всех элементов массива. Эта сумма затем по битам записывается в зарезервированные младшие биты ячеек.
uint8 calcChecksum(const uint8* pass)
{
uint8 checksum = 0;
for (int i = 0; i < 12; i++)
{
checksum += pass[i];
}
for (int i = 0; i < 6; i++)
{
pass[i + 6] |= (checksum >> i) & 1;
}
}
В итоге получается примерно такая схема:
Данные подготовлены, следующий шаг — перестановка по одной из 5-ти таблиц. Ассоциируется с криптографией, не правда ли? В зависимости от маски пройденных уровней, выбирается таблица перестановки. Таблицы содержат в себе индексы элементов в соответствии с их новым порядком.
char s_swizzleTableFinal[] = {0, 6, 5, 4, 10, 1, 9, 3, 7, 8, 2, 11};
char s_swizzleTables[][] = {
{0, 2, 3, 1, 4, 6, 9, 5, 7, 8, 10, 11},
{8, 2, 3, 6, 10, 1, 9, 5, 7, 0, 4, 11},
{5, 4, 3, 10, 6, 0, 9, 8, 7, 1, 2, 11},
{3, 4, 1, 2, 6, 5, 9, 10, 7, 8, 0, 11}
};
void swizzlePassword(uint8* pass, uint8 clearedLevelsMask)
{
const uint8* swizzTable = (clearedLevelsMask == 0x1F)
? s_swizzleTableFinal
: s_swizzleTables[clearedLevelsMask % 4];
uint8 swizzledPass[12] = {};
for (var i = 0; i < 12; i++)
{
swizzledPass[i] = pass[swizzTable[i]];
}
for (var i = 0; i < 12; i++)
{
pass[i] = swizzledPass[i];
}
}
Последний шаг — применение таблицы инкрементов. Т.е. каждая ячейка суммируется с соответствующим элементом таблицы по модулю 8. Именно благодаря этому иконки будут разные даже при одинаковых значениях.
void applyIncrementTable(uint8* pass)
{
for (var i = 0; i < 12; i++)
{
pass[i] = (pass[i] + s_incrementTable[i]) % 8;
}
}
Вот мы и имеем готовый пароль. И, выходит, что в этом пароле используется 15 бит из 36. Но почему?
Дело в том, что эти биты не такие уж и неиспользуемые. Процедура декодирования пароля берёт из них информацию о собранных L и E-бонусах, а также их текущем количестве, но затем проверяет, чтобы все эти значения были равны нулю. Отсюда можно предположить, что изначально планировалось эту информацию сохранять, но затем было принято решение от неё отказаться.
То ли это результат балансировки геймплея, то ли просто отключенный инструмент разработчиков — неизвестно. Подробнее об этом можно почитать здесь.
Переменные длины
Где-то дома у меня лежит тетрадка, расписанная паролями главной RPG моего детства — Little Ninja Brothers. Несмотря на то, что игра эта из себя ничего сверхъестественного не представляет, на её прохождение мне понадобилось несколько лет. Ведь это была моя первая RPG, и поначалу я даже не знал, что там можно «качаться», поэтому где-то полгода ушло на то, чтобы без прокачки победить второго босса (благо есть возможность играть вдвоём).
В своё время именно эта игра заставила меня задуматься об устройстве системы паролей — как-то раз я целый день, сидя перед телевизором, выискивал закономерности в паролях и пытался определить их зависимость от текущих характеристик. В итоге мне даже удалось подобрать один пароль и увеличить количество денег, но это был единственный удачный случай.
Спустя время, в процессе становления во мне IT-специалиста, я однажды вспомнил про тот случай. И, поскольку был очень любознательным и любил поломать голову, решил за время университетских каникул во что бы то ни стало выяснить механизм генерации паролей. Сейчас бы мне на это хватило и дня, но тогда на это ушла целая неделя, но цель, тем не менее, была достигнута.
Этот случай интересней предыдущих хотя бы потому, что пароль имеет переменную длину: по мере прохождения игры добавляются новые символы. Более того, в пароле хранится куда больше данных, чем во всех предыдущих вместе взятых. Как видно из скриншота, алфавит составляет 32 символа, а максимальная длина вводимого пароля — 54 символа. Это даёт нам 3254 возможных паролей максимальной длины, а с учётом переменной длины и вовсе 321 + 322 + … + 3254 вариантов. Если посчитать количество информации, которое может вместить один пароль максимальной длины, то это будет 270 бит (log23254).Итак, какие же данные хранит пароль? Поскольку это RPG, то характеристик достаточно много, и почти все из них необходимо сохранять.
Список характеристик 
Характеристики:
Экипировка:
Предметы и прочее:
Характеристики:
- Уровень персонажей (макс. 50)
- Количество опыта (макс. 65535)
- Максимальное здоровье (макс. 255)
- Количество денег (макс. 99999)
- Количество M-бонусов (макс. 6)
Экипировка:
- Полученные призменные колокола (красный, оранжевый, жёлтый, зелёный, голубой, синий, фиолетовый)
- Имеющиеся артефакты (противоядие, разум)
- Тип удара («железные когти», «сокрушающий удар», «мега-удар», «огненный удар», «тупой удар», «золотые когди», «удар Ли», «призменные когти»)
- Имеющийся меч («меч ястреба», «тигриный меч», «орлиный меч», «призменный меч»)
- Щит («чешуйчатый», «зеркальный», «огненный», «призменный»)
- Роба («белая», «чёрная», «роба Ли», «священная роба»)
- Талисман («α», «β», «γ», «σ», «ω»)
- Амулет («I», «II», «III», «IV»)
- Тип светильника (спичка, свеча, факел, кусочек солнца)
- Имеющиеся типы сюрикенов («одинарные», «серийные», «бумеранги», «fixer»(не смог перевести))
Предметы и прочее:
- Количество сдобных булочек (аналог лёгкого лечебного зелья, до 8 шт.)
- Количество мясных булочек (аналог сильного лечебного зелья, до 1 шт.)
- Количество вертолётов (даналог портала в город, до 8 шт.)
- Количество лекарств (позволяет воскрешать второго игрока, до 1 шт.)
- Количество скейтов (позволяет сбежать с поля боя, до 8 шт.)
- Количество бомб (до 8 шт.)
- Есть ли драгстер (это такой гоночный автомобиль)
- Количество батарей для драгстера
- Доступное количество специальных ударов у обоих игроков
На самом деле, не все эти данные сохраняются, и не все сохраняемые данные перечислены. Не упомянутыми остались посещённые города, текущая локация и пара бит с информацией о произошедших игровых событиях. Не сохраняются, в свою очередь, уровень и здоровье, поскольку эти две величины напрямую зависят от количества опыта и являются избыточными данными. Так же не сохраняется количество спецударов второго игрока, т.к. он, по сути, опционален.
Так как же всё это работает? Начнём с того, что игра хранит массив указателей на байты переменных, нуждающихся в сохранении. По этим указателям игра формирует массив байтов, который затем подвергнется кодированию. Этот массив делится на 4 группы по 8 байтов (6 байтов в последней группе).
const char s_groupsBytes[4] = {8, 8, 8, 6};
const char* s_passDataMap[30] = {
// Group 1
&currLocation, &bells, &moneyLo, &expLo
&moneyMed, &expHi, &moneyHi, &kicks,
// Group 2
&visitedCitiesLo, &visitedCitiesHi, &mBonusCount, &tStarsTypes,
&punch, &usedTreasures, &tStars, &treasures,
// Group 3
&sword, &bombs, &shield, &skboards,
&robe, &dragster, &talisman, &meatbuns,
// Group 4
&amulet, &sweetbuns, &light, &batteries,
&whirlyBirds, &medicine
};
Чтобы сделать пароли максимально компактными, игнорируются все нулевые значения. С этой целью для каждой из четырёх групп массива составляется маска ненулевых значений — один байт, где i-й бит служит индикатором того, необходимо ли включать i-й элемент массива в пароль. В сформированном массиве эта маска будет идти перед группой, которой она соответствует.
uint8 valuesMask(const uint8* data, int group)
{
uint8 valuesMask = 0;
const int startIndex = group * 8;
for (int i = startIndex + s_groupsBytes[group] - 1; i >= startIndex; i--)
{
valuesMask <<= 1;
if (data[i] != 0)
{
valuesMask |= 1;
}
}
return valuesMask;
}
Та же самая операция в конце применяется и к группам на тот случай, когда все значения группы равны нулю: существует четырёхбитная маска (4 старших бита байта), где i-й бит (от старшего к младшему) служит индикатором того, что в пароль включена i-я группа массива. Эта маска будет записана в заголовке, прямиком перед данными групп.
Кроме того, существует таблица длин, где каждому байту массива соответствует его значимое количество бит. Т.е. в итоге будут кодироваться не байты массива целиком, а только используемые биты значений. Та же техника применяется и для масок ненулевых значений — количеству используемых бит маски соответствует число байтов в группе.
Итоговый формируемый массив представляет собой аналог битового стека: добавление переменных происходит «подстановкой спереди» — для N добавляемых бит ко всему массиву применяется логический сдвиг вправо на N, а в освободившиеся в начале биты и записывается значение переменной.
const char s_bitLengths[] = {
8, 7, 8, 8, 8, 8, 1, 7, 8, 2,
3, 4, 4, 2, 4, 2, 3, 4, 3, 4,
3, 1, 3, 1, 3, 4, 3, 4, 4, 1
};
void pushBits(uint8* data, uint8 value, int bitCount)
{
shiftRight(data, bitCount);
writeBits(data, value, bitCount);
}
// ...
uint8 encodedData[30] = {};
uint8 groupsMask = 0;
for (int i = 3; i >= 0; i--)
{
groupsMask >>= 1;
uint8 currMask = valuesMask(passData, i);
if (currMask != 0)
{
groupsMask |= 0x80;
const uint8 valuesCount = s_groupsBytes[i];
const int startIndex = i * 8;
for (int j = startIndex + valuesCount - 1; j >= startIndex; j--)
{
if (passData[j] != 0)
{
pushBits(encodedData, passData[j], s_bitLengths[j]);
}
}
pushBits(encodedData, currMask, valuesCount);
}
}
Затем в начало массива добавляются 4 байта, которые являются своеобразным заголовком. В нём будет храниться контрольная сумма, маска включенных в пароль групп и инкремент — 8-битное случайно значение от 0 до 31, которое будет складываться со значениями символов по модулю 32.
Сперва в конец заголовка записывается инкремент, и, начиная с последнего байта заголовка, считается контрольная сумма. Она представляет собой 20-битный хеш, являющийся суммой элементов, умноженных на их порядковый номер.
uint32 calcChecksum(uint8* data, int count)
{
uint32 sum = 0;
for(int i = 0; i < count; i++)
{
sum += data[i] * (i + 1);
}
return sum;
}
// ...
const uint8 increment = rand() % 32;
shiftRight(encodedData, 32);
encodedData[3] = increment;
uint32 checksum = calcChecksum(&encodedData[3], (encodedDataBitLength + 7) / 8);
encodedData[0] = checksum & 0xFF;
encodedData[1] = (checksum >> 8) & 0xFF;
encodedData[2] = ((checksum >> 16) & 0xF) | groupsMask;
После этого данные, как и в прошлом случае, кодируются аналогично Base32. При этом сперва отдельно кодируется заголовок из контрольной суммы и четырёх старших бит маски включенных в пароль групп, а затем отдельным символом пароля пишется инкремент, и только после этого кодируются все остальные данные.
uint8 password[54] = {};
uint8* header = encodedData;
uint8* body = &encodedData[4];
// Encode header (3 bytes + increment = 6 chars)
for (int i = 0; i < 5; i++)
{
password[i] = takeBits(header, 3, 5);
}
password[5] = increment;
const int charCount = (((byteCount + 1) * 8 + 4) / 5) - 1;
// Encode password data
for (var i = 0; i < charCount; i++)
{
password[i + 6] = takeBits(body, byteCount, 5);
}
К получившимся значениям применяется инкремент, за исключением символа, который сам хранит его значение.
// Apply increment skipping increment char
for (var i = 0; i < password.length; i++)
{
if (i != 5)
{
password[i] = (password[i] + increment) % 32;
}
}
И, собственно, заключительный этап: преобразование в текст по алфавиту.
const wchar_t* s_passwordCharTable = L"—BCD\u25a0FGH+JKLMN\u25cfPQRST\u25b2VWXYZ234567";
for (int i = 0; i < charCount; i++)
{
std::cout << s_passChars[password[i]];
if (i % 6 == 5)
{
std::cout << ' ';
}
}
Немного об особенностях реализации алгоритма в игре
Для NES это довольно сложный алгоритм, поэтому при реализации его части, отвечающей за декодирование пароля, не обошлось без любопытного бага. Он интересен тем, что проявляется только на некоторых «искусственно» сгенерированных паролях.
Ошибка заключается в следющем: существует процедура, которая декодирует битовый поток (полученный после декодирования из «Base32») обратно в байтовый массив из 4-х групп. При отсутствии в пароле определённой группы она устанавливает текущий результирующий индекс на начало следующей.
Группы, как уже было сказано, имеют размер 9 байтов (за исключением последней) — 8 байт значений + предшествующая маска ненулевых значений. Так вот, при отсутствии второй группы индекс должен быть установлен на начало третьей группы, т.е. стать равным 18-ти, но вместо этого значение записывается в переменную, хранящую маску существующих групп. Поскольку значение хранится ещё и в регистре, на индекс это не влияет, но маску всё же портит.
Принимая значение 0x12 (напомню, что маской являются 4 старших бита), маска начинает указывать на то, что существует только последняя группа значений. Т.к. первая группа уже обработана, а вторая и так отсутствует, это сказывается только на третьей и четвёртой группах.
В итоге, при наличии третьей группы она всегда будет обрабатываться как четвёртая. Так почему же это никак не сказалось на работоспособности пароля? А потому, что во второй группе есть маска посещённых городов, и, учитывая, что почти все предметы, сохраняемые в 3-й группе, можно получить только посетив города (а первый город стоит прямо перед носом у игрока), то третья группа не будет существовать без второй, а значит, при проявлении бага данные из третьей группы не будут пропадать.
Но из-за испорченной маски всегда инициализируется четвёртая группа, независимо от того, есть ли она или нет! Но и тут нет ничего страшного: если она существует, то сама собой и проинициализируется. Если же нет — попытка проинициализировать её предварительно зануленными байтами не возымеет никакого эффекта, что аналогично её отсутствию.
Ошибка заключается в следющем: существует процедура, которая декодирует битовый поток (полученный после декодирования из «Base32») обратно в байтовый массив из 4-х групп. При отсутствии в пароле определённой группы она устанавливает текущий результирующий индекс на начало следующей.
Группы, как уже было сказано, имеют размер 9 байтов (за исключением последней) — 8 байт значений + предшествующая маска ненулевых значений. Так вот, при отсутствии второй группы индекс должен быть установлен на начало третьей группы, т.е. стать равным 18-ти, но вместо этого значение записывается в переменную, хранящую маску существующих групп. Поскольку значение хранится ещё и в регистре, на индекс это не влияет, но маску всё же портит.
Принимая значение 0x12 (напомню, что маской являются 4 старших бита), маска начинает указывать на то, что существует только последняя группа значений. Т.к. первая группа уже обработана, а вторая и так отсутствует, это сказывается только на третьей и четвёртой группах.
uint8 data[32] = {};
for (int index = 0; index < 34; index++)
{
register = index;
if (register == 0 && !(mask & 0x80))
{
register = 9;
index = register;
}
if (register == 9 && !(mask & 0x40))
{
register = 18;
// Здесь ошибка!
mask = register;
}
if (register == 18 && !(mask & 0x20))
{
// После ошибки всегда будет выполняться этот код
register = 27;
index = register;
}
if (register == 27 && !(mask & 0x10))
{
return;
}
decodeValue(input, &data[index]);
}
В итоге, при наличии третьей группы она всегда будет обрабатываться как четвёртая. Так почему же это никак не сказалось на работоспособности пароля? А потому, что во второй группе есть маска посещённых городов, и, учитывая, что почти все предметы, сохраняемые в 3-й группе, можно получить только посетив города (а первый город стоит прямо перед носом у игрока), то третья группа не будет существовать без второй, а значит, при проявлении бага данные из третьей группы не будут пропадать.
Но из-за испорченной маски всегда инициализируется четвёртая группа, независимо от того, есть ли она или нет! Но и тут нет ничего страшного: если она существует, то сама собой и проинициализируется. Если же нет — попытка проинициализировать её предварительно зануленными байтами не возымеет никакого эффекта, что аналогично её отсутствию.
В качестве бонуса
Любители JavaScript могут поковыряться в написанных специально для статьи генераторах паролей для
Adventure Island 4 (Takahashi Meijin no Bouken Jima IV) и Power Blade 2, а также в облагороженной версии генератора для Little Ninja Brothers почти пятилетней давности.
Прошу за код строго не судить, веб-программирование далеко от моей специализации.
Генератор паролей для Prince of Persia можно найти здесь.
И немножко ностальгии...
Ссылки
- Коллекция генераторов паролей от известного NES-гуру CaH4e3'а.
- Коллекция генераторов от Griever'а.
- Десяток генераторов на сайте tasvideos.org.
- Страничка о генераторах и их коллекция от пользователя roman_pro.
