子供の頃、誰がゲーム「Dandy」または「Sega」で何時間も遊んでいたことを認めますか？ そして、ゲームを進めていく中で、パスワードを紙や特別に傷つけたノートに書き留めた人は誰ですか？ あなたがこのサイトで、このサイトを読んでいるのであれば、おそらく少なくとも一度は「どのように機能しますか？」

私の子供時代のゲームの例を使用して、パスワードを生成するための古典的なメカニズムの原理を説明しようとします。 すべての例がNESプラットフォーム（はい、「Dandy」）からのものであることを事前に謝罪しますが、主題はそれに限定されません。 たまたま私は、もう少し研究をして、もう少しテキストを書くための十分なモチベーションを自分で見つけられなかったのです。

単純なものから複雑なものまで順番に例を示します。 最初はコードはほとんどありませんが、アルゴリズムを人間の言語で説明するのが難しくなればなるほど、また技術的な言語でアルゴリズムを説明するのは簡単になるので、私を責めないでください。

コードブック

私の記憶にはまだ幼少期のゲームのパスワードがいくつか残っています。たとえば、「トロールクレイジーランド」の「BCHK」（「ドキ！ドキ！ユウエンチ」）、「超人戦隊ジェットマン」の「4660」などです。 これらは、利便性の点で理想的なパスワードであると言えます。覚えやすく、入力時に間違いを犯しにくいです。 しかし、どれだけの情報を含めることができ、そのようなパスワードをランダムに選択する可能性はありますか？

最初のケースでは、パスワードのアルファベットは24文字です。 キャラクターの組み合わせの数を数えると、24 ⁴になります-ゲームには12レベルしかないことを考えると、それほど小さくありません。実際、パスワードにはレベル番号以外は保存されません。 いくつかの秘密のパスワードを考慮して、1回の試行でパスワードを取得する確率を計算します：（12 + 4）/ 24 ⁴ 、これは〜5.7×10 ^-14に相当します。 つまり、実際のパスワードを取得する前に、平均で17592186044416のパスワードを試す必要があります。

2番目のケースでは、すべてが多少異なります。 明らかに、4桁のセットで正確に10,000（10 ⁴ ）の組み合わせが得られます。 ゲームには、異なる順序で完了することができる5つのレベルと2つのレベルの難易度が含まれています。 つまり パスワードには、合格レベルと難易度に関する情報が保存されます。 したがって、既存のパスワードの数は2×2 ⁵です。 64.したがって、パスワードを取得する確率は0.0064です。つまり、 半分以上。 十分ではありませんか？ 平均して、約156番目のパスワードはすべて正しいものであり、検索の速度がかなり高いため、検索は長続きしません。 そして、率直に言って、子供の頃、私たちは最初から始めたくなかったとき、しばしば「ブルートフォース」ゲームをしました。

実際、そのようなパスワードの情報容量は評価する意味がありません。なぜなら、それらは一種のキー、つまり ゲームは単にすべての可能なパスワードを保存し、入力されたパスワードのインデックスにより、レベルなどに関する情報を取得します。 しかし、興味を引くために、理論上の容量は48ビットと13ビット（log ₂ 24 ⁴とlog ₂ 10 ⁴ ）であると言います。

それでも、入力されたパスワードはどのくらい正確に処理されますか？ 最初のケースでは、入力されたパスワードはまったく変換されず、保存されたパスワードの配列で単に検索されます。


2番目のケースでは、ゲームは少し複雑になり、最初にパスワードがバイナリ10進コードに変換されます 。これにより、サイズが正確に半分に縮小されます。 これにより、ゲーム自体でパスワードのサイズを半分に減らすことができます。

数字と数字

クラシックもあえて無視しないでください。ダンディだけでなく、多くの人がオリジナルの「プリンスオブペルシャ」をプレイしたと思います。 ゲームのパスワードも10進数のシーケンスですが、今回はいくつかのデータをエンコードします。

つまり、時間とレベル番号の2つの値がエンコードされます。 なぜなら パスワードは8桁の長さです。 100,000,000の組み合わせで、ゲームには14のレベルと60の可能な時間値（合計840のオプション）があり、それを拾うのは難しいと仮定できます。 しかし、実際にはそうではありません。その理由を理解するために、まずその生成の原理を調べてみましょう。

したがって、最初にゲームは0〜9の値を格納できる8つの要素の配列を作成します。次に、0〜9の2つのランダム値が生成され、インデックス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}; 

次に、レベルインデックスがエンコードされます（つまり、その数-1）。インデックスの2つの最上位ビットと10を法とする2番目の増分の合計がインデックス7に書き込まれ、2つの最下位ビットと最初の増分の合計がインデックス1に書き込まれます。

  //       pass[7] = ((level >> 2) + rand1) % 10; //     pass[1] = ((level & 3) + rand0) % 10; 

時が来ました。 少し簡単です。10を法とする最初の増分の10の合計はインデックス0に、単位の合計と2番目の増分はインデックス3に書き込まれます。増分がゼロの場合、時間はそのまま10進数で書き込まれます。 また、数十の上限は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; 

たとえば、残りの32分を含む13レベルのパスワードの凡例は「96635134」です。


パスワードの選択では、チェックサムがエンコードされたデータに適していれば十分であることが明らかになります。 次に、その詳細を考慮しない場合、パスワードを選択する確率を計算できます。正確に1％（単位を金額の可能な値の数で割った値）-非常に多くです。

しかし、これは普通の量です！ また、異なるデータについては、同じであることが判明する場合があります。 有効なパスワードを変更して、最初の4桁の合計が同じままになっている場合は、変更します。 通常の和の分布はまったく均一ではなく、そのような和の最大値は決して72を超えないと言うことができます。

そのような合計の詳細を考えると、線形列挙では、データと一致する確率が非常に高いことがわかります。 そのため、ネットワーク上のテーマフォーラムでは、Prince of Persiaのパスワードをどれだけ巧みに選択したかを思い出すことができます。

位置番号システム

確かに多くの人がBase64とBase32に精通しています。 定義上、これらはそれぞれベース64と32の位置番号システムです。 原理は簡単です。ビットストリームを固定ビット長の値に分割し、特定の辞書に従って、インデックスとして取得した値に従って文字を取得します。

多くのパスワードシステムは、この原則に基づいています。 そして、パスワード生成アルゴリズムを例に挙げた次のゲームは、アドベンチャーアイランド4として知られる一般的な人々の高橋名人の冒険島IVです。

ゲームの状態には、利用可能なアイテムのセット（最大12）、能力（最大3）、特別なアイテム（最大6）、収集されたハート（最大8）、卵のある場所、合格レベルに関する情報が含まれます。 しかし、実際には、ハートと特別なオブジェクトを除くすべてについて、1つの値が責任を負っています-進行の指標です。 これは、各要素が使用可能なアイテム、能力などに関する情報を格納する配列内のインデックスです。 簡単に言えば、オブジェクト、能力、および完了したステージのセットを定義するのはこのバイトです。

アルゴリズムの最初のステップは、4バイトの配列を作成することです。 進行状況の値は最初のバイトに書き込まれます。 興味深いことに、特定の値のみが許可されています。

2番目のバイトには、使用可能な特別なアイテムのマスクが記録されます-バイトの最上位6ビット。 残りの下位2ビットには、1に等しい定数が書き込まれます。 これはパスワード形式のバージョンだと思います。 また、入力されたパスワードのより厳密な検証を継続的に行うこともできます。

卵が置かれている場所のインデックスは、3番目のバイトに書き込まれます（プレイしなかった人のために、一種のチェックポイント）。 卵がどこにもインストールされていない場合、値は0xFFです。 卵のある場所のインデックスは、特定の値のみを取ることができます-卵をインストールできる場所のみが含まれます。

そして最後に、収集されたハートとハーフハートのマスクが4番目のバイトにコピーされます。

  const uint8 s_version = 1; // ... uint8 data[4] = {progress, specItems | s_version, eggLocation, hearts}; 

次に、パスワードはBase32と同様にエンコードされますが、アルファベットが異なります。この配列から、5ビットが1つずつ取得され、8つの要素の配列の別々のバイトに書き込まれます。 この場合、操作「xor」を使用すると、チェックサムが配列の最後のバイトに書き込まれます。

6バイト目の空きビットには、コードブックインデックスが追加されます。 ゲームの開始時に、このインデックスはランダムに計算されます（0〜3の値）が、1つのパッセージ内で常に1つだけが使用されます。 つまり 同じパスワードの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]; 

最終段階：4つのBase32コーディングテーブルの1つがインデックスによって取得され、結果の配列がテキストに変換されます。 配列要素は文字インデックスとして使用されます。

  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 ^8の可能なパスワードオプションがあります。 適切なパスワードの数を計算するのは簡単です-エンコードされた各変数の有効な値の数を掛けるだけです。 したがって、26個の卵の位置、20個の異なる進捗値、収集された心臓の256（2 ⁸ ）の組み合わせ、特別なアイテムの64（2 ⁶ ）の組み合わせ、および4つのパスワードオプションをエンコードできます。 合計：26×20×256×64×4 = 34078720パスワード。 したがって、パスワードを選択する確率は〜0.03％です。平均32,264回の試行が必要になります。

グラフィックカオス

場合によっては、開発者はオリジナルであり、グラフィックパスワードを使用します。 たとえば、メガマンシリーズのゲームでそれらに遭遇する可能性があります。 もちろん、そのようなパスワードの使いやすさは疑わしい-特に習慣から。 しかし、これは日本語の長いパスワードと比較しても何もありません。残念ながら、私はこの記事で説明するのに十分な強度を持っていませんでした。

例として、ゲームPower Blade 2を取り上げます。4x3グリッドに配置された12のボーナスアイコンで構成されるパスワードを使用します。 空白のアイコンを含む合計8つの異なるアイコンがあります。 実際、この種のシンボリックパスワードとグラフィックパスワードの違いは、その要素の表現にあります。アイコンをシンボルに置き換えても、本質は変わりません。

各アイコンは、パスワードを入力する際の表示順序に従って、0〜7の数字に対応しています。

0	1	2	3	4	5	6	7

ゲームには完了したレベルと利用可能な衣装に関する情報しか保存されていませんが、8個の^12個の組み合わせがあることを計算するのは簡単です。 ランダムな順序で完了することができる5つのレベル（ファイナルはカウントしません）、および4つの衣装。 つまり それぞれ5ビットと4ビット、合計9ビット。 パスワードの容量は12×log ₂ 8、つまり 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; } } 

準備ができたパスワードがあります。 そして、このパスワードには36ビットのうち15ビットが使用されていることがわかりました。

実際、これらのビットはそれほど使用されていません。 パスワードのデコード手順では、収集されたLボーナスとEボーナスに関する情報と現在の番号を取得しますが、これらすべての値がゼロに等しいことを確認します。 このことから、もともとこの情報を保存することが計画されていたと仮定できますが、それを破棄することにしました。

これがゲームプレイのバランスの結果なのか、単に無効化された開発者ツールなのかは不明です。 詳細についてはこちらをご覧ください 。

可変長

自宅のどこかに、子供の頃の主なRPGであるリトルニンジャブラザーズのパスワードが書かれたノートブックがあります。 このゲームは超自然的なものではありませんが、完成するまでに数年かかりました。 結局、それは私の最初のRPGであり、最初はそこで「スイング」することが可能であることすら知らなかったので、ポンプを使わずに2番目のボスを倒すのに約6か月かかりました（一緒にプレイする機会があるため）。

かつて、このゲームでパスワードシステムの構造を考えるようになりました-一日中テレビの前に座って、パスワードのパターンを探し、現在の特性への依存を判断しようとしていました。 その結果、1つのパスワードを取得して金額を増やすことさえできましたが、これが唯一の良いケースでした。

しばらくして、私のITスペシャリストになる過程で、私はかつてその事件について思い出しました。 そして、彼は非常に好奇心が強く、頭を悩ませるのが好きだったので、彼は大学の休暇中にパスワードを生成するためのメカニズムを必ず見つけることを決めました。 今では1日で十分でしたが、1週間かかりましたが、それでも目標は達成されました。

このケースは、パスワードの長さが可変であるという理由だけで、以前のケースよりも興味深いものです。ゲームを進めるにつれて、新しいキャラクターが追加されます。 さらに、パスワードには、以前のすべてを組み合わせたものよりもはるかに多くのデータが保存されます。 スクリーンショットからわかるように、アルファベットは32文字で、パスワードの最大長は54文字です。 これにより、32 ^54個の最大長のパスワードが得られます。可変長を考慮すると、32 ¹ + 32 ² + ... + 32 ⁵⁴オプションがあります。 最大長の1つのパスワードに対応できる情報量を計算すると、270ビット（log ₂ 32 ⁵⁴ ）になります。

それでは、パスワードにはどのようなデータが保存されますか？ これはRPGであるため、多くの特性があり、それらのほとんどすべてを保存する必要があります。


実際、このデータのすべてが保存されるわけではなく、保存されているすべてのデータがリストされるわけでもありません。 訪れた都市、現在の場所、発生したゲームイベントに関する情報を含むいくつかのビットは言及されていません。 これらの2つの値は経験の量に直接依存し、冗長データであるため、レベルと正常性は保持されません。 また、2番目のプレイヤーの特別なヒットの数は保存されません。 基本的にオプションです。

それでは、どのように機能しますか？ まず、ゲームは保存する必要のある変数のバイトへのポインターの配列を保存します。 これらのポインターに従って、ゲームはバイトの配列を形成し、その後、エンコードされます。 この配列は、8バイトの4つのグループに分割されます（最後のグループでは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 }; 

パスワードをできるだけコンパクトにするために、すべてのヌル値は無視されます。 この目的のために、配列の4つのグループごとに非ゼロ値のマスクがコンパイルされます。1バイトでは、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ビットのマスク（バイトの上位4ビット）があり、i番目のビット（上位から下位）はパスワードが含まれることを示します。配列のi番目のグループ。 このマスクは、これらのグループの直前のヘッダーに書き込まれます。

さらに、配列の各バイトがその有効ビット数に対応する長さテーブルがあります。 つまり その結果、配列のバイト全体がエンコードされず、値のビットのみが使用されます。 同じ手法がゼロ以外の値のマスクにも適用されます。使用されるマスクビットの数は、グループ内のバイト数に対応します。

最終的に生成される配列は、ビットスタックに類似しています。変数は「前置置換」によって追加されます。

  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バイトが配列の先頭に追加されます。チェックサム、パスワードに含まれるグループのマスク、および増分-32を法とする文字の値に追加される0〜31の8ビットランダム値が格納されます。

最初に、増分がヘッダーの最後に書き込まれ、ヘッダーの最後のバイトから始まります。チェックサムが考慮されます。これは、要素の合計にシリアル番号を掛けた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と同様にエンコードされます。この場合、最初に、チェックサムのヘッダーとパスワードに含まれるグループのマスクの上位4ビットが別々にエンコードされ、次に増分が別のパスワードシンボルで書き込まれ、その後にのみ他のすべてのデータがエンコードされます。

  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 << ' '; } } 

ボーナスとして

JavaScriptの愛好家は、
アドベンチャーアイランド4（高橋名人の冒険島 IV）とPower Blade 2の記事のために特別に書かれたパスワードジェネレーター、およびほぼ5年前のリトルニンジャブラザーズ用のジェネレーターの高貴なバージョンを詳しく調べることができます。

厳密にコードを判断しないようお願いします;ウェブプログラミングは私の専門からはほど遠いです。

プリンスオブペルシャのパスワードジェネレーターはこちらにあります。

参照資料

• 有名なNESの第一人者CaH4e3 のパスワードジェネレーターのコレクション。
• Griever のジェネレーターのコレクション。
• tasvideos.org.
• roman_pro .