Ностальгия: как работают «сохранения на бумажке»

Признавайтесь, кто в детстве часами напролёт просиживал за игрой в «Денди» или «Сегу»? А кто по мере прохождения игры записывал пароли на бумажку или в специально заведённую тетрадку? Если это вы, и раз уж вы читаете этот сайт, то у вас наверняка хоть раз возникал вопрос: «а как же это работает?»

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

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

Кодовая книга

У меня в памяти до сих пор сидят пароли некоторых уровней из игр моего детства — например, «BCHK» из «Trolls in Crazyland» («Doki! Doki! Yuuenchi»), «4660» из «Choujin Sentai — Jetman». Можно сказать, что это идеальные с точки зрения удобства пароли: их легко запомнить и трудно ошибиться при вводе. Но сколько же информации они могут содержать, и каков шанс случайно подобрать такой пароль?

В первом случае алфавит пароля составляет 24 символа. Если посчитать количество комбинаций символов, то это будет 4²⁴ — не так уж и мало, учитывая, что в игре всего 12 уровней, и, собственно, кроме номера уровня пароль в себе ничего не хранит. Учтём несколько секретных паролей и посчитаем вероятность подобрать пароль с одной попытки: (12 + 4) / 4²⁴, что равно ~5.7×10^-14. Другими словами, придётся перепробовать в среднем 17592186044416 паролей, прежде чем мы подберём какой-нибудь реальный.

Во втором случае всё несколько иначе. Очевидно, что набор из 4-х цифр даёт нам ровно 10000 (10⁴) комбинаций. Игра содержит пять уровней, которые можно проходить в разном порядке и два уровня сложности. Т.е. пароль хранит информацию о пройденных уровнях и уровне сложности. Таки образом, число существующих паролей равно 2×2⁵, т.е. 64. Отсюда вероятность подобрать пароль равна 0.0064, т.е. больше, чем полпроцента. Мало ли это? В среднем примерно каждый 156-й пароль окажется верным, а учитывая довольно высокую скорость перебора, поиски долго не продлятся. И, честно признаюсь, в детстве мы часто «брутфорсили» игру, когда не хотелось начинать с самого начала.

На самом деле информационную ёмкость таких паролей оценивать бессмысленно, поскольку они являются лишь своего рода ключами, т.е. игры просто хранят все возможные пароли, и по индексу введённого пароля получают информацию об уровне и прочем. Но интереса ради скажу, что их теоретическая ёмкость составляет 48 и 13 бит (log₂4²⁴ и log₂4¹⁰).

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

	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. Это увеличивает количество возможных паролей в 10 раз, что, очевидно, усложняет выявление закономерностей.

	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. Получается, что при инкрементах, равных нулю, время запишется в десятичных цифрах, как есть.

	// Кодируем старшую цифру времени
	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++] = '-';
		}
	}

Существует 32⁸ возможных вариантов пароля. Несложно посчитать количество подходящих паролей — достаточно перемножить количество допустимых значений каждой из кодируемых переменных. Итак, мы можем кодировать 26 локаций яйца, 20 различных значений прогресса, 256 (2⁸) комбинаций собранных сердец, 64 (2⁶) комбинации специальных предметов и 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

Несложно посчитать, что мы имеем 8¹² комбинаций, хотя игра сохраняет лишь информацию о пройденных уровнях и имеющихся костюмах. Всего 5 уровней (не считая финального), которые можно проходить в произвольном порядке, и 4 костюма. Т.е. 5 бит и 4 бита соответственно, 9 бит в сумме. Пароль же имеет ёмкость 12×log₂⁸, т.е. 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. Но почему? Видимо, для усложнения подбора и анализа.

Переменные длины

Где-то дома у меня лежит тетрадка, расписанная паролями главной RPG моего детства — Little Ninja Brothers. Несмотря на то, что игра эта из себя ничего сверхъестественного не представляет, на её прохождение мне понадобилось несколько лет. Ведь это была моя первая RPG, и поначалу я даже не знал, что там можно «качаться», поэтому где-то полгода ушло на то, чтобы без прокачки победить второго босса (благо есть возможность играть вдвоём).

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

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

Этот случай интересней предыдущих хотя бы потому, что пароль имеет переменную длину: по мере прохождения игры добавляются новые символы. Более того, в пароле хранится куда больше данных, чем во всех предыдущих вместе взятых. Как видно из скриншота, алфавит составляет 32 символа, а максимальная длина вводимого пароля — 54 символа. Это даёт нам 54³² возможных паролей максимальной длины, а с учётом переменной длины и вовсе 1³² + 2³² + … + 54³² вариантов. Если посчитать количество информации, которое может вместить один пароль максимальной длины, то это будет 270 бит (log₂32×54).

Итак, какие же данные хранит пароль? Поскольку это 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"—BCDu25a0FGH+JKLMNu25cfPQRSTu25b2VWXYZ234567";

	for (int i = 0; i < charCount; i++)
	{
		std::cout << s_passChars[password[i]];
		if (i % 6 == 5)
		{
			std::cout << ' ';
		}
	}

	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]);
	}

В качестве бонуса

Любители JavaScript могут поковыряться в написанных специально для статьи генераторах паролей для
Adventure Island 4 (Takahashi Meijin no Bouken Jima IV) и Power Blade 2, а также в облагороженной версии генератора для Little Ninja Brothers почти пятилетней давности.

Прошу за код строго не судить, веб-программирование далеко от моей специализации.

Генератор паролей для Prince of Persia можно найти здесь.

И немножко ностальгии...

 

 

 

 

 

 

Ссылки

• Коллекция генераторов паролей от известного NES-гуру CaH4e3'а.
• Коллекция генераторов от Griever'а.
• Десяток генераторов на сайте tasvideos.org.

Автор: horror_x