②エニグマ暗号機のローター結線解読プロジェクト（コードを書いてもらうが動かない）

2024年9月23日 22:17

イメージはマリアン・レイェフスキのローター結線解読だ。
（エニグマ暗号機のローターの中の結線。勿論、最初は秘密である。）

史実上ではフランス情報局がスパイ活動によって入手した事になっているが、マリアン・レイェフスキは時間さえかければ手作業で解読できたと言っている。どんな風にやろうと思ったのだろう？
それを私もゼロから考えてみようという試みである。
手計算ではなくてMathematicaと生成AIを使わせて貰うけど。

2024/09/23　22：10　案　まずはClaudeでこんな風に打ってみる。
（Geminiだと満足する結果が得られない）

アルファベット26文字が異なる文字へ置換される対称群が２つ（A,B）あります。暗号分は対称群AとBを掛けわせて行われますが、Bは一文字毎にシフトしていきます。各暗号文は毎回規定の初期設定まで戻される事が分かってます。対称群の中身はA,B共に分かっていません。多量の6文字暗号文と6文字平文のセットが入手できたとしたとき対称群AとBの中身をMathematicaの群論に関する関数を使って、効率的に推測していくプログラムを書いてください。総ての総当たり戦は現実的ではありません。群論の特性を使った方法はありませんか？

プロンプト

Claudeの制限が解除されるまで時間がかかるので、今日はここまで。

しまった。今日も別の問題で使い切ってしまった…

2024/09/25
案を出してもらった👇　ので、考えてみる。

この暗号システムは非常に興味深いですね。対称群を使った暗号化方式で、特にBが文字ごとにシフトする点がユニークです。群論の特性を活用して効率的に解読する方法を考えてみましょう。

回答

(* Import necessary packages *)
Needs["Combinatorica`"]

(* Define helper functions *)
cycleStructure[perm_] := Sort[Length /@ (Cycles[perm])];

(* Main cryptanalysis function *)
cryptanalysis[plaintext_, ciphertext_] := Module[
  {n = 26, m = 6, possibleA, possibleB, consistentPairs},
  
  (* Generate all possible permutations for A and B *)
  possibleA = Permutations[Range[n]];
  possibleB = Permutations[Range[n]];
  
  (* Filter consistent pairs *)
  consistentPairs = Select[
    Tuples[{possibleA, possibleB}],
    And @@ Table[
      PermutationProduct[
        #[[1]],
        RotateLeft[#[[2]], i - 1]
      ][[ plaintext[[i]] ]] == ciphertext[[i]],
      {i, 1, m}
    ] &
  ];
  
  (* Analyze cycle structures *)
  groupedA = GroupBy[consistentPairs, cycleStructure[#[[1]]] &];
  groupedB = GroupBy[consistentPairs, cycleStructure[#[[2]]] &];
  
  (* Return results *)
  <|
    "PossibleA" -> Keys[groupedA],
    "PossibleB" -> Keys[groupedB],
    "ConsistentPairs" -> Length[consistentPairs]
  |>
]

(* Example usage *)
plaintext = {1, 2, 3, 4, 5, 6};
ciphertext = {15, 22, 3, 18, 9, 7};
result = cryptanalysis[plaintext, ciphertext];

Print["Possible cycle structures for A: ", result["PossibleA"]];
Print["Possible cycle structures for B: ", result["PossibleB"]];
Print["Number of consistent pairs: ", result["ConsistentPairs"]];

このプログラムは、群論の特性を活用して効率的に対称群AとBの可能性を絞り込むアプローチを取っています。以下に主要なポイントを説明します：

巡回置換構造（cycle structure）の利用：
置換の巡回置換構造を分析することで、可能性のある置換を効率的に絞り込みます。同じ巡回置換構造を持つ置換は、暗号学的に同様の振る舞いをする可能性が高いです。

一致するペアの効率的な検索：
平文と暗号文のペアを使用して、一致する可能性のある(A, B)のペアを見つけます。MathematicaのSelect関数とTuples関数を使用して効率的に検索を行います。

結果の分析：
一致するペアを見つけた後、それらのAとBの巡回置換構造を分析します。
これにより可能性のある構造の種類を特定しさらなる分析の基礎とします。
複数のサンプルの使用：
このプログラムは1つの平文-暗号文ペアで動作しますが、複数のペアを使用してさらに絞り込むことができます。

このアプローチは、総当たり攻撃よりも効率的です。巡回置換構造の分析により、同じ構造を持つ多くの置換を一度に除外できるためです。

プログラムを実行するには、実際の平文と暗号文のペアを使用し、結果を分析します。複数のペアを使用して結果を交差検証することで、さらに精度を高めることができます。

また、このプログラムは基本的なアプローチを示していますが、さらなる最適化や拡張が可能です。例えば：並列処理を導入して、大規模なデータセットでの処理速度を向上させる。
機械学習技術を組み込んで、パターン認識の精度を高める。
より高度な群論的性質（例：群の中心や正規部分群）を利用して、さらに解析を深める。

これらの拡張を行うことで、より効率的で強力な暗号解析ツールを開発できるでしょう。

回答

2024/09/28
上のプログラムは余りにも膨大なメモリを必要とするらしく、動かない。2回ほど作り直しを依頼すると、それだけでClaudeの上限制約に達してしまう。あんまり試せないな。

メモリを食い尽くすのは、おそらくこの2行だろう。

possibleA = Permutations[Range[n]];
possibleB = Permutations[Range[n]];

Claudeのコードより

この記事が気に入ったらサポートをしてみませんか？