公開鍵アルゴリズムの一種ですが、最も有名な(AirOneも利用している)RSAアルゴリズムとは少し趣が異なります。
RSAのように暗号化や署名を行うために鍵ペアを使うのではなく、共有鍵(セッション鍵)を生成/交換するために鍵ペアを使います。
IPsecや(トンネリングソフトの)zebedeeなどでも鍵交換に使っています。

2者間で秘密鍵(private-key)を隠したまま、セッション鍵を交換する手順は次のようになります。秘密鍵を知らない第三者はセッション鍵を知ることができません(=計算量が多くて求めるのに時間がかかります(**))。

+ お互いの秘密鍵をxとyとします。
+ あらかじめ両者で決めておく数値をgとp(素数)とします。
(この数値は通信プロトコル上で交換してもいいですし、zebedeeだと、確かソースコードにハードコードしていました)

X = g^x % p ...(1)
Y = g^y % p ...(2)
をお互いに交換します(X,Yが公開鍵に相当)。

セッション鍵の計算
k1 = Y^x % p
k2 = X^y % p


* k1とk2が等しいことの証明
aとb、それぞれnで割った余りが等しいことを
a ≡ b (mod n)
と表記します。
a%p ≡ a (mod p) ;自明です。
(a%p)^n ≡ a^n (mod p) ;両辺を掛けてもpで割った余りは同じ

上の式で、a=g^y、n=xとすると、
(g^y % p)^x ≡ g^y^x (mod p) ...(3)

k1 = Y^x % p
= (g^y % p)^x % p ...(2)より
= g^y^x % p ...(3)より
= g^(xy) % p

同様に、
k2 = X^y % p = (g^x % p)^y % p = g^x^y % p = g^(xy) % p

∴ k1 = k2
Q.E.D.


2004/6/12のblogを加筆修正して公開


脚注
(*)
証明部分は、昔、どこかのWebで見たのを自分でメモっておいたものです。
オリジナルが自分では無いことを明記しておきます。

(**)
と言うことになっています...
X,Y,g,pが与えられた時、x,y,k(=k1=k2)のどれかひとつでも当てればいいだけです。簡単そうです。あなたならできるかもしれません。