ケイリー・パーサーアルゴリズム

ケイリー・パーサー・アルゴリズムは、1999年初頭に16歳のアイルランド人女性サラ・フラナリーによって発表された公開鍵暗号アルゴリズムで、ダブリンのデータセキュリティ企業であるボルチモア・テクノロジーズの創設者マイケル・パーサーの未発表の研究に基づいている。フラナリーはこのアルゴリズムを数学者アーサー・ケイリーにちなんで命名した。その後、公開鍵暗号アルゴリズムとして欠陥があることが判明したが、当時メディアで大きな注目を集めた。

ボルチモア・テクノロジーズでの職場体験中に、フラナリーはマイケル・パーサーによる未発表の論文を見せられた。その論文には、非可換乗算を用いた新しい公開鍵暗号方式の概要が示されていた。彼女は、この方式をMathematicaで実装するように依頼された。

この研修に参加する前、フラナリーは1998年のESAT若手科学者・技術展に、シーザー暗号からRSA暗号まで、既存の暗号技術を解説するプロジェクトで参加していた。このプロジェクトでインテル学生賞を受賞し、1998年に米国で開催されたインテル国際科学技術フェアへの出場権を獲得した。展示プロジェクトに独自の作品を加えたいと考えたフラナリーは、マイケル・パーサーに、彼の暗号方式に基づいた作品を含める許可を求めた。

数学者である父親の助言を受け、フラナリーは行列乗算が非可換性を持つという必要な性質を備えていることから、行列を用いてパーサーの方式を実装することにした。結果として得られるアルゴリズムは乗算に依存するため、指数関数的なステップを用いるRSAアルゴリズムよりもはるかに高速になるはずだった。インテル・サイエンス・フェアのプロジェクトで、フラナリーは同じ平文をRSAと彼女が新たに開発したケイリー・パーサー・アルゴリズムの両方で暗号化するデモンストレーションを準備し、実際に大幅な時間短縮が実現した。

1999年にESAT（若手科学者・技術展示会）に再び参加したフラナリーは、ケイリー＝パーサーの実行時間を体系化し、既知の様々な攻撃を分析したが、いずれも有効とは判断されなかった。

フラナリーは、ケイリー・パーサーアルゴリズムがRSAに取って代わるなどとは一切主張しなかった。新しい暗号システムは、安全なシステムとして認められるためには、長期間の検証に耐えなければならないことを理解していたからだ。しかし、メディアはそれほど慎重ではなく、彼女がESAT展で一等賞を受賞した際、世界中の新聞が、若い天才少女が暗号学に革命を起こしたという記事を掲載した。

実際、そのアルゴリズムに対する攻撃がすぐに発見されたが、彼女はそれを分析し、後のコンテストの付録として掲載した。その中には、彼女が主要な賞を受賞したヨーロッパ規模のコンテストも含まれている。

本稿で用いる表記法は、フラナリーの原著論文と同じである。

秘密鍵の復元${\displaystyle \chi }$から${\displaystyle \gamma }$計算上不可能であり、少なくともnを法とする平方根を求めるのと同じくらい難しい（二次剰余を参照）。これは以下から復元できる。${\displaystyle \alpha }$そして${\displaystyle \beta }$システムが${\displaystyle \chi \beta =\alpha ^{-1}\chi }$解決可能ではあるが、このシステムの解の数は、グループ内の要素の位数が大きい限り多く、これはほぼすべての要素について保証できる。

しかし、このシステムは、複数の${\displaystyle \chi '}$の${\displaystyle \chi }$解くことによって${\displaystyle d}$以下の合同式において：

$\displaystyle d\left(\beta -\alpha ^{-1}\right)\equiv \left(\alpha ^{-1}\gamma -\gamma \beta \right){\pmod {n}}}$

ある条件を満たす場合に解が存在することに注意する${\displaystyle i,j\in \left|\gamma \right|}$そして${\displaystyle x,y\in \mathbb {Z} _{n}}$

${\displaystyle x\left(\beta _{ij}^{-1}-\alpha _{ij}\right)\equiv y{\pmod {n}}.}$

もし${\displaystyle d}$知られているように、${\displaystyle d\mathrm {I} +\gamma =\chi '}$— 倍数${\displaystyle \chi }$任意の倍数${\displaystyle \chi }$収量${\displaystyle \lambda =\kappa ^{-1}=v^{-1}\chi ^{-1}\epsilon v\chi }$これは、未だ解決されていないシステムの致命的な弱点となっている。

この欠陥は、送信者が送信する場合、このアルゴリズムを混合秘密鍵/公開鍵アルゴリズムとして使用することを妨げるものではありません。${\displaystyle \epsilon }$秘密裏に行われるが、この方法は、公開鍵暗号方式を使用して対称暗号鍵を送信し、その後対称暗号に切り替えるという一般的な方法に比べて利点はなく、ケイリー・パーサーよりも高速である。

• 非可換暗号

• サラ・フラナリーとデイビッド・フラナリー。『コード：数学の旅』。ISBN 0-7611-2384-9
• クラウス・シュメー。コードナッカー ゲゲン コードマッチャー。ISBN 978-3-937137-89-6