ケイリー・パーサーアルゴリズム
1999年の公開鍵暗号アルゴリズム

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

歴史

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

この配置に先立ち、フラナリーは1998年のESAT Young Scientist and Technology Exhibitionに、シーザー暗号からRSA暗号に至るまでの既存の暗号技術を解説するプロジェクトで参加していました。このプロジェクトで彼女はIntel Student Awardを受賞し、米国で開催された1998年Intel国際科学技術フェアへの参加機会を得ました。展示プロジェクトに独自の作品を加える必要があると感じたフラナリーは、マイケル・パーサーに、彼の暗号方式に基づく作品を掲載する許可を求めました。

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

1999 年に ESAT 若手科学者技術展示会に戻った Flannery は、Cayley-Purser の実行時間を形式化し、既知のさまざまな攻撃を分析しましたが、どれも効果的であるとは判断されませんでした。

フラナリーは、新しい暗号システムが安全であると認められるためには、時の試練に耐える必要があることを知っていたため、ケーリー・パーサー・アルゴリズムがRSAに取って代わるなどとは主張しませんでした。しかし、メディアはそれほど慎重ではなく、彼女がESAT展で最優秀賞を受賞した際には、世界中の新聞が「天才少女が暗号技術に革命をもたらした」と報じました。

実際、そのアルゴリズムへの攻撃はその後すぐに発見されましたが、彼女はそれを分析し、ヨーロッパ規模のコンテストを含むその後のコンテストの付録として取り入れ、そこで大きな賞を受賞しました。

概要

この議論で使用されている表記は、Flannery の元の論文と同じです。

鍵生成

RSAと同様に、ケイリー・パーサー法はまず、2つの大きな素数pとq、そしてそれらの積n （半素数）を生成することから始めます。次に、整数要素とnを法とする剰余演算を持つ2×2行列の一般線型群GL (2, n )を考えます。例えば、n =5 の場合、次のように書けます。

[ 0 1 2 3 ] + [ 1 2 3 4 ] ＝ [ 1 3 5 7 ] ≡ [ 1 3 0 2 ] {\displaystyle {\begin{bmatrix}0&1\\2&3\end{bmatrix}}+{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}1&3\\5&7\end{bmatrix}}\equiv {\begin{bmatrix}1&3\\0&2\end{bmatrix}}
[ 0 1 2 3 ] [ 1 2 3 4 ] ＝ [ 3 4 11 16 ] ≡ [ 3 4 1 1 ] {\displaystyle {\begin{bmatrix}0&1\\2&3\end{bmatrix}}{\begin{bmatrix}1&2\\3&4\end{bmatrix}}={\begin{bmatrix}3&4\\11&16\end{bmatrix}}\equiv {\begin{bmatrix}3&4\\1&1\end{bmatrix}}}

この群は、( p 2 −1)( p 2 − p ) ( q 2 − q )に等しい大きな位数(大きな半素数nの場合)を持つために選択されます。

GL(2, n )から選ばれた2つの行列をととする。ある自然数rを選び、次式を計算する。 χ {\displaystyle \chi } α {\displaystyle \alpha} χ α ≠ α χ {\displaystyle \chi \alpha \not =\alpha \chi }

β ＝ χ − 1 α − 1 χ 、 {\displaystyle \beta =\chi ^{-1}\alpha ^{-1}\chi ,}
γ ＝ χ r 。 {\displaystyle \gamma =\chi ^{r}.}

公開鍵は、、、、です。秘密鍵はです。 n {\displaystyle n} α {\displaystyle \alpha} β {\displaystyle \beta} γ {\displaystyle \gamma} χ {\displaystyle \chi }

暗号化

送信者はまずランダムな自然数sを生成し、次を計算します。

δ ＝ γ s {\displaystyle \delta =\gamma ^{s}}
ϵ ＝ δ − 1 α δ {\displaystyle \epsilon =\delta ^{-1}\alpha \delta }
κ ＝ δ − 1 β δ {\displaystyle \kappa =\delta ^{-1}\beta \delta }

次に、メッセージを暗号化するために、各メッセージブロックはRSAのように数値としてエンコードされ、平文行列の要素として一度に4つずつ配置されます。各ブロックは、以下の方法で暗号化されます。 μ {\displaystyle \mu } μ {\displaystyle \mu }

μ ′ = κ μ κ . {\displaystyle \mu '=\kappa \mu \kappa .}

次に、 とが受信者に送信されます。 μ ′ {\displaystyle \mu '} ϵ {\displaystyle \epsilon }

復号化

受信者は、次の方法で元の平文行列を復元します。 μ {\displaystyle \mu }

λ = χ − 1 ϵ χ , {\displaystyle \lambda =\chi ^{-1}\epsilon \chi ,}
μ = λ μ ′ λ . {\displaystyle \mu =\lambda \mu '\lambda .}

安全

秘密鍵を から復元することは計算的に不可能であり、少なくともnを法とする平方根を求めるのと同じくらい困難です（平方剰余 を参照）。 から復元することは可能であり、系が解ける場合は可能ですが、群の元が大きな順序を持つ限り、この系の解の数は膨大になります。これはほぼすべての元に対して保証できます。 χ {\displaystyle \chi } γ {\displaystyle \gamma } α {\displaystyle \alpha } β {\displaystyle \beta } χ β = α − 1 χ {\displaystyle \chi \beta =\alpha ^{-1}\chi }

ただし、次の合同式 を解いて の倍数を見つけることで、このシステムを破ることができます。 χ ′ {\displaystyle \chi '} χ {\displaystyle \chi } d {\displaystyle d}

d ( β − α − 1 ) ≡ ( α − 1 γ − γ β ) ( mod n ) {\displaystyle d\left(\beta -\alpha ^{-1}\right)\equiv \left(\alpha ^{-1}\gamma -\gamma \beta \right){\pmod {n}}}

ある条件と i , j ∈ | γ | {\displaystyle i,j\in \left|\gamma \right|} x , y ∈ Z n {\displaystyle x,y\in \mathbb {Z} _{n}}

x ( β i j − 1 − α i j ) ≡ y ( mod n ) . {\displaystyle x\left(\beta _{ij}^{-1}-\alpha _{ij}\right)\equiv y{\pmod {n}}.}

が分かっている場合、の倍数になります。 の任意の倍数は となります。これは、まだ解決されていないシステムの致命的な弱点となります。 d {\displaystyle d} d I + γ = χ ′ {\displaystyle d\mathrm {I} +\gamma =\chi '} χ {\displaystyle \chi } χ {\displaystyle \chi } λ = κ − 1 = v − 1 χ − 1 ϵ v χ {\displaystyle \lambda =\kappa ^{-1}=v^{-1}\chi ^{-1}\epsilon v\chi }

この欠陥は、送信者が秘密に送信する場合、アルゴリズムを混合秘密鍵/公開鍵アルゴリズムとして使用することを妨げるものではありませんが、このアプローチは、公開鍵暗号化方式を使用して対称暗号化キーを送信し、その後、Cayley-Purser よりも高速な対称暗号化に切り替えるという一般的なアプローチに比べて利点がありません。 ϵ {\displaystyle \epsilon }

参照

参考文献

  • サラ・フラナリー、デイヴィッド・フラナリー著『In Code: A Mathematical Journey』ISBN 0-7611-2384-9
  • クラウス・シュメー。コードナッカー ゲゲン コードマッチャー。ISBN 978-3-937137-89-6
Retrieved from "https://en.wikipedia.org/w/index.php?title=Cayley–Purser_algorithm&oldid=1331221059"