ソリティア（暗号）
Cryptographic algorithm

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

ソリティアが開発された動機の一つは、全体主義的な環境においては、暗号ユーティリティを多数備えたパーソナルコンピュータよりもトランプの方がはるかに安価（かつ、犯罪の証拠にもなりにくい）という点です。しかし、シュナイアーが『クリプトノミコン』の付録で警告しているように、暗号解読に関心を持つほぼすべての人がこのアルゴリズムを知っているため、トランプを持ち歩くこと自体が犯罪の証拠とみなされる可能性があります。さらに、解析によってこの暗号には欠陥が見つかり、安全性が低いとされています。

暗号化と復号化

このアルゴリズムでは、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つ下に移動します。もしAが最後のカードであれば、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つ下の方に移動します。もしBジョーカーが最後から2番目のカードであれば、折り返して2番目のカードになります。もしBジョーカーが最後のカードであれば、3番目のカードになります。Bジョーカーが最初のカードになることはありません。
    • 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]

参考文献

  1. ^ Schneier, Bruce (1999年5月). 「ソリティア」 . 2006年7月2日閲覧。
  2. ^ ab ポール・クロウリー「ブルース・シュナイアーの『ソリティア』の問題点」2018年3月26日閲覧。
  3. ^ ab シウ、ダニエル (2019 年 9 月 13 日)。 「ソリティアの分析」。arXiv : 1909.06300 [cs.CR]。
  • シュナイアーのソリティアの説明
Retrieved from "https://en.wikipedia.org/w/index.php?title=Solitaire_(cipher)&oldid=1318824879"