[ホーム]-> [GnuPG]-> [algorithm]
[Next][Previous]

アルゴリズム

[(画像パッチなしの) w3m/emacs-w3m や lynx, Emacs-W3 などで見ている方へ]

以下、Ｚ は有理整数環を表すことにします。また、x^y は、y が x の右肩に乗っていることを表します。

RSA 暗号

鍵生成

p,q: 素数 (|p|,|q| はほぼ同じ), n=pq　 [1]
m = LCM(p-1,q-1)　
e in (Ｚ/mＺ)^×: 乱数, d = (1/e) mod m　
秘密鍵: d, 公開鍵: (e,n)　

暗号化

M: 元のメッセージ　
暗号化メッセージ: c=M^e mod n　

復号化

M=c^d mod n で複号できる。　

RSA 署名

鍵生成

p,q: 素数 (|p|,|q| はほぼ同じ), n=pq　 [1]

m = LCM(p-1,q-1)　
e in (Ｚ/mＺ)^×: 乱数, d = (1/e) mod m　
秘密鍵: d, 公開鍵: (e,n)　

署名生成

M: 元のメッセージ　
s = h(M)^d mod n　
署名付きメッセージ: (M,s)　

検証

h(M) = s^e mod n を確認。　

ElGamal 暗号

鍵生成

p: 素数, g: (Ｚ/pＺ)^×の生成元　
x: 0 < x < p-1 乱数, y = g^x mod p　
k: p-1 と互いに素な乱数 (セッション毎に生成)　
公開鍵: (p,g,y) 秘密鍵: x　

暗号化

M: 元のメッセージ　
r = (g^k) mod p, s = (M y^k) mod p　
暗号化メッセージ: (r,s)　

復号化

(r,s) から M = (s/r^x) mod p で復号できる。　

ElGamal 署名

鍵生成

p: 素数, g: (Ｚ/pＺ)^×の生成元　
x: 0 < x < p-1 乱数, y = g^x mod p　
h: ハッシュ関数, k: p-1 と互いに素な乱数 (セッション毎に生成)　
秘密鍵: x, 公開鍵: (p,g,y)　

署名生成

M: 元のメッセージ　
r = (g^k) mod p, s = (k^(-1)(h(M) - xr)) mod p-1　
署名付きメッセージ: (M,r,s)　

検証

(M,r,s) に対し、(y^r r^s) = (g^h(M)) mod p を確認。　

DSA (署名)

ElGamal 署名の変形で、安全性を保ったまま署名長を短くしたものです。

鍵生成

p, q: 素数, q は p-1 の約数, g: (Ｚ/pＺ)^× の位数 q の元　
x: (0 < x < q) 乱数, y = (g^x) mod p　
h: ハッシュ関数, 0 < k < q: 乱数 (セッション毎に生成)　
秘密鍵: x, 公開鍵: (p,q,g,y)　

署名生成

M: 元のメッセージ　
r = (g^k mod p) mod q, s = (k^(-1)(h(M) + xr)) mod q　
署名付きメッセージ: (M,r,s)　

検証

(M,r,s) が与えられたとき、　
t = (h(M)s^(-1)) mod q, u = (rs^(-1)) mod q　

として、

r = ((g^t y^u) mod p) mod q を確認。　

[註] 実際には、L を 64 の倍数でかつ 512≦L≦1024 なるもの、 また、p, q は 2^(L-1) < p < 2^L, 2^159 < q < 2^160 となるように取ります。

ESIGN 署名

RSA と同じく素因数分解問題に基づきますが、RSA 署名に比較して署名の作成が数十倍高速です。

[w3m や lynx や Emacs-W3 で見ている方へ]

以下、【x】は x 以上の最小の整数を表すことにします。(ガウス記号ではなく ceiling の方。)

鍵生成

p,q: 素数, |p|,|q| はほぼ同じ, p>q,　[1]

n = p^2q, k (k>3): 整数　
秘密鍵: (p,q)　
公開鍵: (k,n)　

署名生成

M: 元のメッセージ　
x in (Ｚ/pqＺ)^×: 乱数, w = 【(h(M)-(x^k mod n))/pq】　
y = w/(kx^(k-1)) mod p　
s = x + ypq　
署名付きメッセージ: (M,s)　

検証

0≦ (s^k mod n) - h(M) < 2^【2|n|/3】　

Diffie-Hellman 鍵配送

第三者に盗聴される可能性のある経路を使って秘密鍵を共有するためのアルゴリ ズムです。安全性は離散対数問題に基づきます。

準備

A, B が鍵を共有したいと思ったとする　
p: 素数, g: Ｚ/pＺ^× の生成元　
A は乱数 x in Ｚ/(p-1)Ｚ を生成　
B は乱数 y in Ｚ/(p-1)Ｚ を生成　

鍵配送

A は B に a=g^x mod p を送る 　
B は A に b=g^y mod p を送る　

共有鍵の生成

共有する鍵: k=g^ xy mod p　
A は k=b^x mod p により鍵を生成　
B は k=a^y mod p により鍵を生成　
[1] |p|, |q| がほぼ同じといっても、p,q が近すぎてもまずい。 これはフェルマーの因数分解法というもので簡単に因数分解できてしまうからである。 具体的には、p,q が近い場合、n=t^2-s^2 となるような t,s の組は t > √n となる t で t^2-n が平方数になるものとしてすぐに見つかる。(∵ n=((p+q)/2)^2-((p-q)/2)^2 と書けるから) すると、n=(t+s)(t-s) で分解できる。
[ホーム]-> [GnuPG]-> [algorithm]
[Next][Previous]