ソリティア（暗号）

ソリティア暗号アルゴリズムは、ニール・スティーブンソンの依頼によりブルース・シュナイアーが彼の小説『暗号のミクロノミコン』で使用するために設計したもので、小説の中では、現場の捜査官が電子機器に頼ったり、証拠となる道具を持ち歩いたりすることなく、安全に通信するために使用されています。^[1]これは、通常のトランプを使って計算する手動暗号システム として設計されました。『暗号のミクロノミコン』では、このアルゴリズムはトランプが関係しているという事実を隠すために、 当初はポンティフェクスと呼ばれていました。

ソリティアが作られた動機の 1 つは、全体主義的な環境では、暗号ユーティリティが多数搭載されたパソコンよりもトランプの方がはるかに安価 (かつ有罪の証拠にもなりにくい) であるという点です。しかし、Schneier がCryptonomiconの付録で警告しているように、暗号解読に関心のあるほぼ全員がこのアルゴリズムについて知っているため、トランプを持ち歩くことも有罪の証拠とみなされる可能性があります。さらに、分析により暗号に欠陥があることが明らかになり、現在では安全ではないと考えられています。

このアルゴリズムでは、52 枚の同じスーツのカードと、A ジョーカーと B ジョーカーと呼ばれる互いに区別できる 2 枚のジョーカーを含む標準的なトランプを使用します。簡単にするために、この例ではクラブとダイヤの 2 つのスーツのみを使用します。各カードには数値が割り当てられます。クラブには 1 から 13 (エースからキングまで) の番号が付けられ、同様にダイヤには 14 から 26 の番号が付けられます。ジョーカーには 27 と 28 の値が割り当てられます。したがって、クラブのジャックの値は 11、ダイヤの 2 の値は 15 になります。(トランプの完全なデッキでは、スーツはブリッジの順序で評価されます。クラブ、ダイヤ、ハート、スペードで、同じスーツのカードには 1 から 52 の番号が付けられ、ジョーカーには 53 と 54 の番号が付けられます。)

暗号化または復号化を開始するには、事前に合意した順序でカードのデッキを表向きに並べます。メッセージを復号化する人は、メッセージを暗号化した人が使用したデッキと同じ順序でデッキを並べる必要があります。順序を最初にどのように決定するかは受信者次第です。デッキを完全にランダムにシャッフルすることが望ましいですが、他にも多くの方法があります。

このアルゴリズムは、キーストリームを生成します。キーストリームは、メッセージの暗号化と復号化を行うためにメッセージと組み合わされる値のシーケンスです。キーストリームの各値はメッセージの 1 文字を暗号化するために使用されるため、キーストリームは少なくともメッセージと同じ長さである必要があります。キーストリームがメッセージよりも長い場合、メッセージには追加の繰り返し文字が埋め込まれ、攻撃者がメッセージの正確な長さを知ることができなくなります。

メッセージを暗号化するには:

1. すべての句読点とスペースを削除し、A～Z の 26 文字のみを残します。
2. 各文字を自然数値に変換します。A = 1、B = 2、...、Z = 26。
3. 以下のキーストリーム アルゴリズムを使用して、メッセージ内の各文字に対して 1 つのキーストリーム値を生成します。
4. 各キーストリーム値を対応するプレーンテキストの数値に追加し、結果の値が 26 より大きい場合は 26 を減算します (数学ではこれをモジュラー演算と呼びます)。
5. 結果の数字を文字に戻します。この文字のシーケンスが暗号文です。

暗号文を復号化するには:

1. 暗号文内の各文字を自然な数値に変換します。
2. 暗号文内の文字ごとに 1 つのキーストリーム値を生成します。
3. 各キーストリーム値を対応する暗号テキスト値から減算し、結果の値が 1 未満の場合は 26 を加算します。
4. 結果の数字を文字に戻します。

このアルゴリズムは、デッキ内でカードを移動することによってキーストリーム値を生成します。キーストリーム アルゴリズムは決定論的であるため、キーストリーム値はデッキの最初の順序にのみ依存します。デッキは円形配列であると想定されているため、カードをデッキの一番下のカードより下に移動する必要がある場合は、単に一番上に戻ります (つまり、最初のカードは最後のカードの後に​​続きます)。たとえば、次の開始デッキを考えてみましょう。

• 1 4 7 10 13 16 19 22 25 B 3 6 9 12 15 18 21 24 A 2 5 8 11 14 17 20 23 26

キーストリームの 1 文字を生成するには、次の手順を実行します。

1. A ジョーカーを見つけて、デッキ内で 1 つ下に移動します。これが最後のカードである場合、2 番目のカードになります。これが最初のカードになることはありません。デッキは次のようになります。
   • 1 4 7 10 13 16 19 22 25 B 3 6 9 12 15 18 21 24 2 A 5 8 11 14 17 20 23 26
2. B ジョーカーを見つけて、デッキの 2 か所下に移動します。これが最後から 2 番目のカードである場合、折り返して 2 番目のカードになることに注意してください。これが最後のカードである場合、3 番目のカードになります。これが最初のカードになる方法はありません。
   • 1 4 7 10 13 16 19 22 25 3 6 B 9 12 15 18 21 24 2 A 5 8 11 14 17 20 23 26
3. 「トリプルカット」を実行します。つまり、ジョーカーで区切られた 3 つのセクションにデッキを分割し、上部と下部のセクションを交換します。ジョーカー自体と、ジョーカー間のカードはそのまま残します。
   • 5 8 11 14 17 20 23 26 B 9 12 15 18 21 24 2 A 1 4 7 10 13 16 19 22 25 3 6
4. 「カウント カット」を実行します。つまり、デッキの一番下にあるカードの値を確認します。カードがジョーカーの場合は、その値を 27 (フル デッキの場合は 53) とします。デッキの上からその枚数のカードを取り除き、デッキの最後のカードのすぐ上に挿入します。
   • 23 26 B 9 12 15 18 21 24 2 A 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
5. 次に、一番上のカードの値を確認します。ここでも、ジョーカーはどちらも 27 としてカウントされます (フルデッキを使用する場合は 53)。そのカードの下の数だけ数え、そのカードの値をキーストリームの次の値とします。数えたカードがどちらかのジョーカーである場合は、それを無視してキーストリーム アルゴリズムを繰り返します。この例では、一番上のカードは 23 なので、24 番目のカードである 11 によってキーストリーム値が決定されます (この手順ではカードの位置は変更されないことに注意してください。この手順ではキーストリーム値が決定されるだけです)。

1999年、ポール・クロウリーは、キーストリーム内の文字の繰り返しに偏りがあり、予想される1/26ではなく約1/22.5文字ごとに発生することを発見しました。^[2]その結果、ソリティアは1文字あたり約0.0005ビットの割合で情報を漏らします。^[3]非常に短いメッセージであればセキュリティは十分かもしれませんが、一般的にソリティアは安全ではないと考えられています。

クロウリーはまた、キーストリームアルゴリズムを実行した後に同じ構成になる2つの異なるデッキ構成が存在する場合があることにも気付きました。たとえば、ジョーカーAがデッキの一番下または一番上にある場合、ステップ1の後に2番目のカードになります。これは、アルゴリズムがシュナイアーが当初主張したように常に可逆的ではないことを意味します。^[2]

2019年にダニエル・シューは、ユーザーが手動で実装することをより困難にするという代償を払って、セキュリティを強化するアルゴリズムの修正を提案した。^[3]

• シュナイアーのソリティアの説明