エルガマル – ウィキペディア、無料​​百科事典

この記事では、2012 – 12年から提供された情報の検証が必要です。 信頼できる情報源は、好ましくは書誌的な脚注の形で与えられるべきです。 記事の一部またはすべての情報でさえ、真実ではない場合があります。ソースを欠いているように、それらは挑戦して削除される可能性があります。 この記事の議論には、何を修正すべきかについてのより詳細な情報があります。 欠陥を排除した後、この記事からテンプレート{{refine}}を削除します。

エルガマル これは、最も重要な非対称暗号アルゴリズムの2つの1つです（RSAの隣）。このシステムは、Moduloの整数の本文における離散対数問題の難しさに基づいています。 1980年代半ばのアルゴリズムは、エジプトのターハー・エルガマルによって提示されました ^[初め] 。

Elgamalaアルゴリズムにより、デジタル署名の暗号化と動作が可能になります。 Elgamalアルゴリズムの数百の変更（RSAアルゴリズムの変更と同様）には、他のさまざまなアプリケーションがあります。

エルガマルアルゴリズムの概念は、楕円曲線の暗号化にも基づいています – この場合、乗法グループの代わりに

${displaystyle z_ {p}}$

楕円曲線でポイントのグループを使用します。

キー生成 ：最初の番号を選択します

${displaystyle p、}$

任意のジェネレーター

${displaystyle alpha}$

乗算サブグループ、つまり、政府が平等なそのような要素

${displaystyle p-1、}$

そして任意

${displaystyle k}$

そのような：

${displaystyle 1$

私たちは数えます

${displaystyle beta {：}}$

${displaystyle beta = alpha ^{k} mod p、}$

正方形に持ち上げることで増加することで迅速にできること。

もしも

${displaystyle alpha}$

たとえば、以下のために無料でした。

${displaystyle p = 41、alpha = 14、k = 16}$

私たちは受け取ります：

${displaystyle beta = 14^{16} mod 41 = 1、}$

暗号システムは役に立たなくなります（暗号化時に常に1を受け取るため）。

次に、公開します

${displaystyle（p、alpha、beta）}$

公開鍵として、そして私たちは維持します

${displayStyle（P、Alpha、Beta、K）}$

秘密鍵として。

暗号化 ：暗号化するメッセージがあります

${displaystyle m、}$

グループの一部として提示します[

${displaystyle 1$

]ランダムに番号を選択します

${displaystyle x}$

そして、私たちはカウントします（modulo

${displaystyle p}$

））

${displaystyle（alpha ^{x}、mtimes beta ^{x}）。}$

復号化 ：受け取ったものを上げます

${displaystyle alpha ^{x}}$

の力に

${displaystyle k {：}}$

${displaystyle left（alpha ^{x}右） ^{k} = alpha ^{kx} =左（alpha ^{k}右） ^{x} = beta ^{x}。}$

その後、反対を見つけます

${displaystyle beta ^{x}}$

（Nadalモジュール

${displaystyle p}$

））
拡張ユークリドアルゴリズム：

${displaystyleガンマベータ ^{x}+delta p = 1、}$

${displaystyleガンマベータ ^{x} equiv 1mod p、}$

${displaystyleガンマequiv（beta ^{x}） ^{-1} mod p。}$

ついに分割します

${displaystyle mtimes beta ^{x}}$

に

${displaystyle beta ^{x}、}$

つまり、私たちは彼女の逆から掛けます –

${displaystyleガンマ{：}}$

${displayStyle（mtimes beta ^{x}）タイムガンマequiv mtimes（beta ^{x} times gamma）equiv mtimes 1 equiv mmod p。}$

キーは同じ方法で生成されます。

メッセージの署名を生成します

${displaystyle m、}$

番号を描きます

${displaystyle r}$

そして、私たちは数えます：

${displaystyle y = alpha ^{r}}$

（Pに向かって） 、

${displaystyle s =（h（m）-ky）r^{ – 1}}$

（ （P-1）に対して） 、 どこ

${displaystyle h}$

ハッシュ関数です。

署名はカップルです

${displaystyle（y、s）}$

署名を確認するには、方程式を確認します。

${displaystyle beta ^{y} y ^{s} = alpha ^{h（m）}。}$

正しい署名の場合、それは一致します：

${displaystyle alpha ^{ky} alpha ^{rs} = alpha ^{h（m）}、}$

${displaystyle alpha ^{ky+rleft（（h（m）-ky）r ^{ – 1} right）} = alpha ^{h（m）}、}$

${displaystyle alpha ^{ky+h（m）-ky} = alpha ^{h（m）}、}$

${displaystyle alpha ^{h（m）} = alpha ^{h（m）}。}$

要求された人の秘密を維持することが重要です

${displaystyle r。}$

もしも

${displaystyle r}$

それは知られているでしょう、あなたは署名から秘密鍵を回復することができます：

${displaystyle y^{ – 1}左（h（m）-sright）= y^{-1}左（h（m） – （h（m） – ky）r^{-1} right）= y^{ – 1} ky = k。}$

乗法グループの政府が最初の数字の産物であり、その中でも十分に大きくない場合、指数を計算する効果的な方法があります。離散対数を迅速にカウントする一般的な方法は不明であるため、使用方法がわかりません

${displaystyle alpha ^{x}}$

私

${displaystyle alpha}$

入手

${displaystyle x、}$

メッセージを復号化するのに十分です。ただし、そのようなものが存在しないという証拠はありません。後者は驚くことではありません。なぜなら、既知の非対称コードにはそのような証拠がないからです。

ただし、離散対数の問題を破ることがこのコードを破る唯一の方法であるという証拠はありません。おそらく、知っている簡単なアルゴリズムがあります

${displaystyle alpha、}$

${displaystyleベータ、}$

${displaystyle p}$

私

${displaystyle alpha ^{x}、}$

${displaystyle mtimes beta ^{x}}$

（すなわち、公開鍵とメッセージのシパログラム）、回復することができます

${displaystyle m、}$

何らかの形でこの問題を祝います。