A Deterministic Complete Graph Hill Cipher with Shift128 Residual Encryption for Universal Binary Files

あなたは友人に秘密のメッセージを送ろうとしていると想像してください。しかし、それは単なる文字ではなく、写真や文書、動画が詰まったデジタルなスーツケースを送るようなものです。コンピュータ・セキュリティの世界では、これを「暗号化」と呼びます。暗号化を、あなたのスーツケースをかき混ぜてしまう魔法の鍵だと考えてください。もし泥棒がそれを盗んでも、中身はただの支離滅裂なゴミに見えるようになります。何十年もの間、科学者たちはこのために「ヒル暗号（Hill Cipher）」という古典的なトリックを使ってきました。これは、メッセージを特別な数字の格子（行列）で掛け合わせることで、意味のないデタラメに変えてしまう巨大な数学パズルです。問題は、この古い手法が少し扱いにくいことです。後で簡単に解錠できるような正しい数字の格子を見つけるのが難しく、また、スーツケースのサイズが正確に一致しないと混乱してしまうため、無理やり収まるように「パディング（詰め物）」と呼ばれる余分な素材を詰め込まなければならないことがよくあります。

ここで、グラフ理論という異なる種類の数学に目を向け、これを修正しようと決めた新しい発明家チームを想像してみてください。彼らは、単にランダムな数字の格子を推測する代わりに、「完全グラフ（complete graph）」を利用しました。完全グラフとは、パーティーにおいてすべてのゲストが他のすべてのゲストと握手をするようなものです。彼らは、この「握手のマップ」が、必ず解読可能な完璧で予測可能な格子を作り出すことを理解しました。彼らはこれに、データの残りカスに対するシンプルな「シフト」のトリックを組み合わせました。その結果、PDF、動画、あるいは奇妙なバイナリファイルであっても、ファイルサイズを変えることなく、端数も残さずにデジタルファイルをロックするように設計された、CGHC-S128と呼ばれる新しいシステムが誕生しました。

新しい「パーティーの握手」ロック

この研究において、インドネシア・バンドン工科大学（Institut Teknologi Sains Bandung）とジェンベル大学（University of Jember）の研究者たちは、デジタルファイルを保護するための新しい方法であるCGHC-S128を紹介しました。これは、あなたのデジタルなスーツケースを守るための、2ステップのセキュリティシステムのようなものです。

まず、彼らは「完全グラフ・ヒル暗号（Complete Graph Hill Cipher）」を使用して、ファイルの主要な部分に取り組みます。昔、ヒル暗号の鍵を作ることは、何千もの鍵がある暗い部屋の中で特定の鍵を探し出すようなものでした。それは、うまくいくものが見つかるまで試行錯誤を繰り返さなければなりませんでした。この新しい方法はよりスマートです。彼らは、全員が互いに知り合いであるパーティーのような「完全グラフ」の構造を利用して、鍵を作成します。これらの握手が数学的にどのように機能するかによって、研究者たちは、この鍵が常に後で解読可能な正しい形状であることを証明しました。これは、毎回必ず鍵穴にフィットすることが保証されているマスターキーを持っているようなもので、もう推測する必要はありません。

次に、彼らは「残り物」に対処します。デジタルファイルは、これらの数学的な格子にぴったり収まる完璧なサイズであることは稀です。通常、隙間を埋めるために「パディング（余分なデータ）」を追加しなければならず、それがファイルサイズを大きくしてしまいます。この新しいシステムは、残りのバイトに対して軽量な「Shift128」というトリックを使用します。もし、メインの引き出しに収まらない余った靴下があったとしたら、それを捨てたり箱に詰め込んだりする代わりに、位置をずらす特別なサイドポケットに滑り込ませるようなイメージです。これにより、余分な嵩（かさ）を増やすことなく、ファイル内のすべてのバイトが保護されます。

ラボでの発見

チームは、新しいシステムがどの程度うまく機能するかを確認するために、PDFドキュメントと様々なサイズの数学的格子を用いてテストを行いました。彼らは単に動くことを期待したのではなく、暗号化されたファイルが本当にランダムに見えるか、そして後で完璧に復元できるかを数値で検証しました。

結果は素晴らしいものでした。ファイルをロックしたとき、暗号化されたデータはほぼ完璧にランダムに見えました。暗号の世界では、「ランダム性」はエントロピーと呼ばれるスコアで測定されます。完璧なスコアは8.0です。彼らの暗号化ファイルは7.999810というスコアを叩き出しましたが、これは完璧に極めて近い値です。これは、暗号化されたファイルが静的なノイズのように見え、中身を推測することがほぼ不可能であることを意味します。

彼らはまた、システムがデータをどれだけバラバラにできるかもチェックしました。もし元のファイルのうち、たった一つの小さなビット（例えば一文字）が変わった場合、優れたロックであれば、暗号化されたメッセージ全体の約半分が変化するはずです。これは「アバランチ効果（雪崩効果）」と呼ばれます。彼らのシステムは、**49.9241%**というアバランチ効果を達成しました。これは理想的な50%にほぼ等しい数値です。これは、入力のわずかな変化が、出力において巨大で予測不可能な変化を引き起こすことを示唆しており、ハッカーがパターンを見つけることを非常に困難にします。

さらに、彼らはシステムが鍵に対してどれほど敏感であるかもテストしました。もしハッカーが、わずかに間違った鍵を使おうとした場合、システムは全く異なる結果を生み出すはずです。研究者たちは、鍵をわずかに変えるだけで出力に**99.6114%**の差が生じることを発見しました。これは、システムが極めて敏感であり、推測ゲームに対して非常に安全であることを意味しています。

トレードオフ：速度とサイズ

セキュリティは非常に優秀でしたが、チームはシステムの動作速度についても調査しました。彼らは、大きな格子を使用しても、ファイルの暗号化（ロック）は非常に高速であることを発見しました。しかし、ファイルの復号（アンロック）は、格子が大きくなるにつれて遅くなりました。これは、復号には「行列の逆行列（matrix inversion）」と呼ばれる複雑な数学的操作が必要であり、それは巨大な数独のパズルを逆方向に解くようなものだからです。

小さな格子（パラメータ n が9から99の間）の場合、システムは非常に高速で、ファイルのロックとアンロックの両方に1秒もかかりませんでした。しかし、非常に大きな格子（n = 999）を試したところ、復号プロセスには327秒（5分以上）かかりました。さらに大きな格子（n = 9999）を試すと、システムは行き詰まり、合理的な時間内に復号を完了することができませんでした。このことは、巨大な格子に対して数学的には完璧に機能するものの、現実世界で使用する場合は、速度を維持するために中規模の格子を使用するのが望ましいということを示しています。

結論

研究者たちは、彼らのCGHC-S128システムが、あらゆる種類のバイナリファイルを保護するための、数学的に堅牢な方法であると結論付けました。このシステムは、ファイルサイズが正確に同じであることを保証し（追加のパディングは不要）、データがランダムなノイズに見えるほど高度に撹乱し、そして毎回完璧に元のファイルへと復元できることを保証します。

彼らは、PDFファイルをロックし、暗号化し、その後アンロックすることで、これを検証しました。ファイルは、元のファイルと全く同じデジタル指紋（MD5およびSHA-256ハッシュ）を持つ状態で出てきました。チームは、実用的な使用においては、中規模の格子を使用することが、強力なセキュリティと高速なパフォーマンスの最適なバランスを提供すると示唆しています。彼らは宇宙中のあらゆる種類のファイルをテストしたわけではありませんが、PDFやバイナリデータに対するテストは、この手法がグラフ理論の優雅さと現代的なファイル保護の実用性を組み合わせた、デジタルな秘密を守るための強力なツールになり得ることを示しています。