ElGamal暗号
ElGamal暗号は、1984年にTaher Elgamalによって発表された公開鍵[[暗号]]方式です。この暗号方式は、位数が大きな群における離散対数問題の計算が困難であるという数学的な性質を安全性の根拠としています。
ElGamal暗号は、Diffie-Hellman鍵共有方式を応用したものです。Diffie-Hellman鍵共有では、共有された乱数を用いてワンタイムパッド暗号を行うことができますが、ElGamal暗号では、この共有された乱数を暗号化プロセスに組み込むことで、より実用的な暗号方式として利用できるように変形されています。
また、ElGamal暗号は暗号化だけでなく、デジタル署名にも応用できます。このデジタル署名方式はElGamal署名と呼ばれています。
ElGamal暗号の仕組みを、以下の手順に沿って説明します。
1. 巡回群Gの選択: 位数qが素数である巡回群Gを選びます。qのビット数はセキュリティパラメータkで決定されます。
2. 生成元gの選択: Gの生成元gを選びます。
3. 秘密鍵xの選択: 0からq-1までの範囲でランダムに秘密鍵xを選びます。
4. 公開鍵hの計算: 公開鍵hをh = g^xとして計算します。
5. 鍵の公開: 公開鍵として(G, q, g, h)を公開し、秘密鍵としてxを保持します。
平文空間はGであり、暗号文空間はG^2です。
1. 平文mの取得: Gの元である平文mを受け取ります。
2. 乱数rの選択: 0からq-1までの範囲でランダムに乱数rを選びます。
3. 暗号文c1, c2の計算: 暗号文c1 = g^r, c2 = m h^r を計算します。
4. 暗号文の送信: (c1, c2) を暗号文として送信します。
1. 暗号文(c1, c2)の取得: 暗号文(c1, c2) を受け取ります。
2. 平文mの計算: 平文mを m = c2 (c1^x)^-1 として計算します。
この復号処理が正しく動作するのは、以下のように計算できるためです。
m' = c2 (c1^x)^-1 = m (g^x)^r ((g^r)^x)^-1 = m
ElGamal暗号の安全性は、離散対数問題の困難性に加えて、計算Diffie-Hellman（CDH）仮定と決定Diffie-Hellman（DDH）仮定に依存しています。
しかし、ElGamal暗号は選択暗号文攻撃に対しては安全ではありません。なぜなら、平文mに対応する暗号文(c1, c2)から、2mに対応する暗号文(c1, 2c2)を容易に生成できるからです。
巡回群GをZp (pを素数としたときの剰余群)として定義することは避けるべきです。このような群上ではDDH仮定が成り立たないためです。
巡回群Gを定義する主な方法としては以下の2つがあります。
1. *Zp の部分群とする:* Zp の適切な部分群を巡回群Gとして利用します。
2. 楕円曲線上で定義する: 楕円曲線暗号を用いて巡回群Gを定義します。
ここでは1の方法について詳しく説明します。
小さな自然数kと大きな素数qに対して、素数pをp = kq + 1となるように選びます。まず素数qを選び、p = kq + 1が素数となるかどうかを調べれば良いです。
次に、g ∈ Zp を、その位数がqとなるようにランダムに選びます。このとき、G = はZp* の部分群となります。
このとき、k=2に対してp=2q+1が成り立つ素数の組(p, q)が無限に存在するかどうかは未解決問題です（ソフィー・ジェルマン問題）。
ElGamal暗号の概要
ElGamal暗号は、Diffie-Hellman鍵共有方式を応用したものです。Diffie-Hellman鍵共有では、共有された乱数を用いてワンタイムパッド暗号を行うことができますが、ElGamal暗号では、この共有された乱数を暗号化プロセスに組み込むことで、より実用的な暗号方式として利用できるように変形されています。
また、ElGamal暗号は暗号化だけでなく、デジタル署名にも応用できます。このデジタル署名方式はElGamal署名と呼ばれています。
ElGamal暗号の仕組み
ElGamal暗号の仕組みを、以下の手順に沿って説明します。
鍵生成
1. 巡回群Gの選択: 位数qが素数である巡回群Gを選びます。qのビット数はセキュリティパラメータkで決定されます。
2. 生成元gの選択: Gの生成元gを選びます。
3. 秘密鍵xの選択: 0からq-1までの範囲でランダムに秘密鍵xを選びます。
4. 公開鍵hの計算: 公開鍵hをh = g^xとして計算します。
5. 鍵の公開: 公開鍵として(G, q, g, h)を公開し、秘密鍵としてxを保持します。
平文空間はGであり、暗号文空間はG^2です。
暗号化
1. 平文mの取得: Gの元である平文mを受け取ります。
2. 乱数rの選択: 0からq-1までの範囲でランダムに乱数rを選びます。
3. 暗号文c1, c2の計算: 暗号文c1 = g^r, c2 = m h^r を計算します。
4. 暗号文の送信: (c1, c2) を暗号文として送信します。
復号
1. 暗号文(c1, c2)の取得: 暗号文(c1, c2) を受け取ります。
2. 平文mの計算: 平文mを m = c2 (c1^x)^-1 として計算します。
この復号処理が正しく動作するのは、以下のように計算できるためです。
m' = c2 (c1^x)^-1 = m (g^x)^r ((g^r)^x)^-1 = m
安全性
ElGamal暗号の安全性は、離散対数問題の困難性に加えて、計算Diffie-Hellman（CDH）仮定と決定Diffie-Hellman（DDH）仮定に依存しています。
- - CDH仮定: ElGamal暗号が選択平文攻撃に対して完全解読できないこと（OW-CPA）とCDH仮定が同値です。
- - DDH仮定: ElGamal暗号が選択平文攻撃のもとで識別不可能（IND-CPA）であることとDDH仮定が同値です。
しかし、ElGamal暗号は選択暗号文攻撃に対しては安全ではありません。なぜなら、平文mに対応する暗号文(c1, c2)から、2mに対応する暗号文(c1, 2c2)を容易に生成できるからです。
巡回群Gについて
巡回群GをZp (pを素数としたときの剰余群)として定義することは避けるべきです。このような群上ではDDH仮定が成り立たないためです。
巡回群Gを定義する主な方法としては以下の2つがあります。
1. *Zp の部分群とする:* Zp の適切な部分群を巡回群Gとして利用します。
2. 楕円曲線上で定義する: 楕円曲線暗号を用いて巡回群Gを定義します。
ここでは1の方法について詳しく説明します。
Zpの部分群としての巡回群Gの構成
小さな自然数kと大きな素数qに対して、素数pをp = kq + 1となるように選びます。まず素数qを選び、p = kq + 1が素数となるかどうかを調べれば良いです。
次に、g ∈ Zp を、その位数がqとなるようにランダムに選びます。このとき、G =
このとき、k=2に対してp=2q+1が成り立つ素数の組(p, q)が無限に存在するかどうかは未解決問題です（ソフィー・ジェルマン問題）。
参考文献
- - 原論文:
関連項目
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。