[Перевод] Как работает алгоритм генерации паролей Castlevania III

В данной статье объясняется механизм, используемый игрой Castlevania III: Dracula’s Curse для сохранения и восстановления игрового состояния при помощи паролей. Информация статьи относится к североамериканским и PAL-версиям, выпущенным для NES, а не к японской версии, Akumajō Densetsu, выпущенной для Famicom.

Система имён и паролей

В Castlevania III применена комбинированная система имени и пароля. В начале игры игроку нужно ввести имя:

Имя состоит из 8 символов; более короткие имена заполняются справа пробелами. Во множество допустимых символов включены буквы английского алфавита в верхнем регистре, пробел, восклицательный знак, вопросительный знак и точка. Допустимо совершенно пустое имя (8 пробелов).

После game over игроку даётся на выбор два варианта: мгновенно продолжить игру с последней точки сохранения или закодировать игровое состояние в пароль, позволяющий продолжить играть в будущем.

game over

При выборе PASSWORD отображается следующий экран:

example password

В данном случае введено имя EXAMPLE, оно показано в поле в верхней части экрана. Непосредственно под именем находится горизонтальная таблица, содержащая используемые в паролях значки: пустота, хлыст, чётки и сердце. Под таблицей расположен пароль — матрица 4×4, в которой каждый элемент является значком. Обратите внимание, что пароли обычно бывают разреженными матрицами.

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

Для восстановления игрового состояния игрок сначала выбирает в главном меню пункт PASSWORD:

title screen

Как показано ниже, игроку предлагается ввести связанное с паролем имя.

example name

Далее игрок переходит на экран ввода пароля:

password entry screen

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

entered password

В случае правильного ввода игра продолжается с точки сохранения. Однако даже при минимальной ошибке демонстрируется следующее сообщение:

not complete try again

Обычно это получается из-за неправильно расположенного значка или забытого имени. Пароль работает только для введённого в начале игры имени.

Особые имена

5 особых имён влияют на геймплей:

Имя Описание
HELP ME Начало и продолжение игры с 10 жизнями.
AKAMA Начало только в сложном режиме (Hard Mode).
OKUDA Начало в обычном режиме (Normal Mode) с Алукардом.
URATA Начало в обычном режиме с Сифой.
FUJIMOTO Начало в обычном режиме с Грантом.

Несмотря на то, что показал Angry Video Game Nerd в своём видео Castlevania (Part 2), имя HELP ME содержит пробел.

Особые имена OKUDA, URATA и FUJIMOTO начинают обычный режим с напарником, однако при этом они принуждают использовать этого напарника всю оставшуюся игру. Получение или переключение напарников аналогичным образом отключены и в сложном режиме. В случае AKAMA это означает, что сложный режим придётся полностью проходить в одиночестве.

На некоторых веб-сайтах утверждается, что при использовании имени GAMETEAM в сочетании с особым паролем позволяет начать в сложном режиме. И если игрок успешно пройдёт игру, то будут показаны настоящие титры с именами разработчиков, создававших игру. Это правда, но больше в этом сочетании имени и пароля нет ничего необычного. Альтернативные титры являются наградой за прохождение сложного режима, вне зависимости от имени. Более того, в альтернативных титрах раскрывается происхождение особых имён:

alternate credits

Игровое состояние

Пароли содержат в себе точку сохранения, напарника и режим. Это единственные свойства игрового состояния, остающиеся, когда игрок продолжает после game over. Всё остальное сбрасывается.

Точки сохранения

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

Точка сохранения Блок Описание
00 1-1 Warakiya Village — Skull Knight
01 2-1 Clock Tower of Untimely Death (подъём вверх) — Nasty Grant
02 2-4 Clock Tower of Untimely Death (спуск вниз к Forest of Darkness)
03 3-0 Forest of Darkness (из Warakiya Village) — циклоп плюс Сифа или Murky Marsh
04 3-1 Forest of Darkness (из Clock Tower) — циклоп плюс Сифа или Murky Marsh
05 4-A Haunted Ship of Fools — Snake Man Sentinel и Death Fire (мумии и циклоп)
06 5-A Tower of Terror — Frankenstein’s Monster
07 6-A Causeway of Chaos — Water Dragons
08 4-1 Murky Marsh of Morbid Morons — Giant Bat
09 5-1 Caves (вход) — Alucard
0A 5-6 Caves (побег) — Skull Knight King или Sunken City
0B 6-1 Sunken City of Poltergeists — Bone Dragon King
0C 6-1 Castle Basement — Frankenstein’s Monster
0D 7-1 Morbid Mountains — Giant Bat и Death Fire King (мумии, циклоп и Левиафан)
0E 7-A Rampart and Lookout Tower — Death Fire King (мумии, циклоп и Левиафан)
0F 8-1 Castle Entrance — Grim Reaper
10 9-1 Villa and Waterfalls — Doppelgänger
11 A-1 Clock Tower and Castle Keep — Dracula

Существует 18 точек сохранения, индексированных с $00 по $11. Названия локаций и боссов никогда не встречаются в игре; в различных источниках есть разные описания. Однако значения блоков и подблоков отображаются в интерфейсе. Все блоки начинаются с подблока 1 или A, за исключением Forest of Darkness, в который можно войти с точек сохранения $03 или $04:

3-0 and 3-1

Единственные прочие точки сохранения посередине блока — это $02 и $0A из-за наличия мини-боссов:

2-4 and 5-6

Точки сохранения $0B и $0C имеют общие значения блока. Но это два совершенно разных уровня:

6-1 and 6-1'

Напарник

Существует 4 значения для напарника, индексированные от 0 до 3:

Напарник Имя
0 Нет
1 Сифа Белнадес
2 Грант Дэнести
3 Алукард

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

Имя 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11
Сифа × × × × × × ×
Грант × × × × × × × × × × × × × × ×
Алукард × × × × × × ×

Эта проверка не проводится для особых имён, за исключением HELP ME. Остальные особые имена с самого начала привязывают игру к конкретному напарнику, или, в случае AKAMA, к отсутствию напарника.

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

То же самое относится и к AKAMA, однако при нём всегда используется сложный режим (Hard Mode), вне зависимости от закодированного в пароле режима.

Режим

Есть два значения для режима, индексированные 0 и 1:

Режим Название
0 Normal
1 Hard

После прохождения игры в Normal Mode она перезапускается в Hard Mode, который значительно сложнее с самого начала. В нём больше врагов, они движутся быстрее и наносят больше урона. На скриншоте внизу слева показаны первые экраны Normal Mode. Справа показаны их аналоги из Hard Mode с дополнительными врагами.

hard mode

Напарник, связанный с игроком в конце Normal Mode, переносится в Hard Mode. Однако возможность смены напарников в Hard Mode отключена; игрок постоянно остаётся с одним напарником или без напарника, если Normal Mode был пройден в одиночку.

После прохождения игры в Hard Mode она перезапускается, но не в каком-то более сложном режиме. В игре всего два режима, и Hard Mode бесконечно зациклен.

Хэш имени

Вместо полного 8-символьного имени пароль содержит всего лишь 3-битный хэш. Хэш вычисляется прибавлением 4 к сумме значений всех символов и делением с остатком на 8 для получения значения в интервале 0–7:

hash name

Любопытно, что код игры использует таблицу для прибавления к текущей сумме различных констант в зависимости от индекса цикла:

; hashName()
; out: A = name hash (0--7)
03:B6CD  LDA #$00
03:B6CF  STA $0000    ; sum = 0;
03:B6D1  TAX
03:B6D2  LDA $07F8,X  ; for (X = 0; X < 8; ++X) {
03:B6D5  CLC
03:B6D6  ADC $B6E6,X
03:B6D9  CLC
03:B6DA  ADC $0000
03:B6DC  STA $0000    ;     sum += name[X] + NAME_HASH_SEEDS[X];
03:B6DE  INX
03:B6DF  CPX #$08
03:B6E1  BNE $B6D2    ; }
03:B6E3  AND #$07     ; A = sum % 8;
03:B6E5  RTS          ; return;

; NAME_HASH_SEEDS
; Due to the modulo operation, this table is pointless; the values can be tallied ahead of time. However, the
; intention may have been to apply this table only to the nonblank characters. But that check is not there.
03:B6E6  .byte $07, $03, $01, $06, $02, $04, $05, $00

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

Значения символов — это индексы тайлов в таблице паттернов. Как показано ниже, A–Z, за которыми следуют восклицательный и вопросительный знаки, соответствуют $50-$6B. Точка — это $4B. Пробел — это $00.

pattern table

Особые имена хэшируются точно так же, как и любые другие. То же самое относится и к пустому имени, которое записывается как 8 пробелов.

Полезная нагрузка

Пароль содержит в себе 1-байтную полезную нагрузку и 1-байтный хэш полезной нагрузки.

Содержимое

Байт полезной нагрузки содержит режим (бит 0), напарника (биты 1–2), индекс маски переключения (бит 3), младший бит точки сохранения (бит 4) и хэш имени (биты 5–7):

76543210
--------
NNNSTPPM
││││││││
│││││││└─ режим
│││││└┴── напарник 
││││└──── индекс маски переключения
│││└───── бит 0 точки сохранения
└┴┴────── хэш имени

Индекс маски переключения задаётся случайным образом при генерации пароля. Он влияет на способ вычисления хэша полезной нагрузки. Поскольку есть 2 возможных значения, то существует 2 действительных пароля для каждого имени, напарника и режима. Например, если игрок начинает новую игру с пустым именем и многократно получает game over в первом блоке, то игра рано или поздно покажет пару эквивалентных паролей:

block 1 passwords

Хэш

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

Для вычисления хэша полезной нагрузки выполняются следующие шаги:

  1. Старший и младший полубайты байта полезной нагрузки считаются 4-битными целыми числами и складываются:
    nibbleSum = 0x0F & ((payload >> 4) + payload);
  2. Если индекс маски переключения равен 0, то чётные биты байта полезной нагрузки переключаются (0 ➔ 1 и 1 ➔ 0 для битов 0, 2, 4 и 6). Это реализовано выполнением XOR с $55:
    toggledPayload = payload ^ 0x55;

    В противном случае нечётные биты переключаются с помощью XOR с $AA:

    toggledPayload = payload ^ 0xAA;
  3. Старший и младший полубайты переключенного байта полезной нагрузки считаются 4-битными целыми числами и складываются:
    toggledNibbleSum = 0x0F & ((toggledPayload >> 4) + toggledPayload);
  4. Две 4-битные суммы комбинируются в байт, при этом первая сумма, становится старшим полубайтом, а вторая — младшим:
    sums = (nibbleSum << 4) | toggledNibbleSum;
  5. Точка сохранения и байт сумм складываются. Так получается 8-битный хэш полезной нагрузки:
    payloadHash = 0xFF & (savePoint + sums);

Описанные выше шаги задают однонаправленную хэш-функцию. Из этого хэша никак не получится восстановить полезную нагрузку.

Представление строк

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

Значок Название
0 пусто
1 хлыст
2 чётки
3 сердце

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

Кодирование

Кодирование — это процесс преобразования имени и игрового состояния в пароль. В нём используются следующие шаги.

  1. Имя хэшируется.
  2. Индексу маски переключения назначается случайное значение.
  3. Хэш имени, бит 0 точки сохранения, индекс маски переключения, напарник и режим побитово конкатенируются, образуя нагрузку.
  4. Полезная нагрузка хэшируется.
  5. Полезная нагрузка и её хэш преобразуются в строку из 8 значков.
  6. Точка сохранения делится на 2 (сдвигом вправо на 1). При этом создаётся значение в интервале 0–8, которое выражается как значок в матрице паролей в соответствии с показанной ниже таблицей.
  7. Первый значок может встречаться в одном из трёх мест:

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

    Элементы 1–8 последовательности скрэмблирования заполняются 8 значками в строке, созданной из полезной нагрузки и её хэша. Так как строка содержит пустые символы и только 9 из 16 элементов матрицы становятся значками, пароли обычно являются разрeженными матрицами.

Декодирование

Декодирование — это процесс преобразования имени и пароля в игровое состояние. Оно состоит из следующих шагов.

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

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

  3. При помощи показанной ниже таблицы непустой значок преобразуется в значение из интервала 0–8.

    Точка сохранения является удвоенной величиной от этого значения.

  4. Непустой значок является первым элементом одной из следующих последовательностей скрэмблирования.

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

  5. С помощью элементов 1–8 последовательности скрэмблирования создаётся строка из 8 значков.
  6. Полезная нагрузка и хэш полезной нагрузки извлекаются, соответственно, из старших и младших битов значков строки.
  7. Если бит 4 полезной нагрузки задан, то выполняется инкремент точки сохранения.
  8. Из полезной нагрузки извлекаются режим, напарник и хэш имени.
  9. Введённое имя сравнивается с особыми именами, кроме HELP ME. Если это не одно из оставшихся особых имён и режим обычный, то проверяется сочетание точки сохранения и напарника. Напарник может использоваться только по пути точек сохранения, начинающихся с момента встречи напарника в игре. Если сочетание неверно, то пароль отклоняется.
  10. Хэш введённого имени сравнивается с хэшем имени, извлечённым из полезной нагрузки. Если они не совпадают, пароль отклоняется.
  11. Полезная нагрузка хэшируется. Результат сравнивается с хэшем полезной нагрузки, извлечённым из пароля. Если они не совпадают, пароль отклоняется.

Все пароли

Полная таблица всех 3294 действительных сочетаний имени и пароля приведена здесь.

Каждый столбец соответствует точке сохранения. Каждая строка соответствует уникальному сочетанию имени, напарника, индекса маски переключения и режима. Поскольку имя хэшируется в 3-битное значение, существует всего 8 классов имён. Как показано в таблице ниже, кратчайшими именами, охватывающими все классы, являются пустое имя и имена, состоящие из одной буквы с B по H. Эти имена показаны в левой части каждой строки.

Имя Хэш
(blank) 4
A 4
B 5
C 6
D 7
E 0
F 1
G 2
H 3
HELP ME 1
AKAMA 2
OKUDA 3
URATA 4
FUJIMOTO 1

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

Белые и красные имена в таблице по ссылке соответствуют Normal Mode и Hard Mode. Имя AKAMA встречается написанное только красным цветом, потому что оно подразумевает Hard Mode вне зависимости от записанного в пароле режима. Однако пароли для AKAMA, содержащие Normal Mode, всё равно действительны и для полноты приведены в таблице.

Спрайтами слева от каждой строки обозначены напарники.

Индекс маски переключения обозначен направлением, в котором смотрит Тревор: вправо — это 0, влево — 1. Индекс маски переключения не влияет на геймплей, но удваивает количество действительных паролей.

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

Все особые имена, кроме HELP ME, привязывают игрока к конкретному напарнику. Однако напарник, записанный в пароле, имеет приоритет перед тем, который связан с особым именем. Поэтому особые имена встречаются в таблице в сочетании со всеми напарниками.

Код

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

Программа на Java, сгенерировавшая полную таблицу паролей, выложена здесь.

 

Источник

, , , , ,

Читайте также

Меню