暗号化アルゴリズム

(4) エルガマル暗号

RSA 暗号は、任意の数に対する素因数分解が有効な時間内に処理できないことを利用した手法でした。任意の数の積は簡単に求められるのに、その逆の処理は非常に大変な労力を必要とします。このような概念を「一方向性関数」といいます。
一方向性関数には他にも「離散対数問題」というものが知られていて、それを利用した暗号に「エルガマル暗号(ElGamal Encryption)」というものがあります。今回は、「エルガマル暗号」について紹介したいと思います。

1) 原始根 (Primitive Root)

「フェルマーの小定理 (Fermat's Little Theorem)」は、以下のような内容でした。

p が素数ならば、a が p と互いに素な限り、a^p-1 を p で割った余りが必ず 1 になるというのがこの定理の内容です。a < p ならば、a を p で割った余りは a であり、フェルマーの小定理から、a^p を p で割った余りも a ということになるので、ここで余りの数は一巡したことになります。したがって、k > 1 を満たす整数 k と、r < p を満たす整数 r を使って

が成り立つことも容易にわかります ( a < p としたので a と p は必ず互いに素になることに注意してください )。

「フェルマーの小定理」を素数だけでなく合成数にまで拡張した定理は「オイラーの定理(Euler's Theorem)」と呼ばれ、以下のような内容になります。

ここで、φ(n) は「オイラーのφ関数 (Euler's Totient Function)」といい、1 から n までの整数の中で、n と互いに素な数の個数を表します。n が素数 p ならば、1 から p - 1 までの全ての数と p は互いに素なので、φ(p) = p - 1 が成り立ちます。よって、「オイラーの定理」は「フェルマーの小定理」を一般化した定理であると考えることができます。

a^k ≡ 1 (mod n) を満たす k は φ(n) より小さい可能性もあります。実際、2³ ≡ 1 (mod 7) であり、φ(7) = 7 - 1 = 6 よりも小さな値 3 を指数としたときに 7 を法として 1 と合同になります。この、a^k ≡ 1 (mod n) を満たす最小の指数 k のことを「n を法とした a の位数 (Order of a Modulo n)」といいます。n を 4 から 9 としたときの位数を求めると次のようになります。

上の表の中で、位数を求めていない箇所は 1 と合同になる指数が存在しません。例えば、n = 4 に対して、a = 2 のときは 2¹ ≡ 2 (mod 4)、2² ≡ 0 (mod 4) であり、以下は全ての指数に対して 4 で割りきれてしまうので位数は存在しません。また、n = 6 に対して、a = 3 のときは 3¹ ≡ 3 (mod 6)、3² ≡ 3 (mod 6) ... となって、どの指数に対しても 3 と合同になるので、やはり位数は存在しません。a^k ≡ 1 (mod n) を満たす k が存在する場合、a^k = 1 + ny を満たす整数 y が存在し、a^k - ny = 1 が成り立つ必要があります。a と n の最大公約数を GCM( a, n ) = G とした時、左辺は G の倍数であり、その値が 1 になるためには G = 1 を満たさなければなりません。したがって、a^k ≡ 1 (mod n) を満たす k が存在するためには a と n が互いに素である必要があります。逆に a と n が互いに素であれば、オイラーの定理から、少なくとも φ(n) を指数とした時に必ず 1 と合同になるので、a と n が互いに素であることは位数が存在するための必要十分条件であることになります。指数を求めていない箇所は、a と n が互いに素でない個数を表していることから、各列に対して位数を持つ a の個数を数えれば、その数が φ(n) を表していることになります。

位数を求めるためのコーディング例を以下に示します。

/*
  calcGCD : ユークリッドの互除法を使った最大公約数の計算

  unsigned int a, b : GCDを求める二つの自然数

  戻り値 : 最大公約数
*/
unsigned int calcGCD( unsigned int a, unsigned int b )
{
  if ( a < b ) swap( a, b );

  do {
    unsigned int r = a % b;
    a = b;
    b = r;
  } while ( b != 0 );

  return( a );
}

/*
  calcOrder : 各数の位数を求める

  unsigned int n : 法
*/
void calcOrder( unsigned int n )
{
  if ( n == 0 ) return;

  for ( unsigned int a = 1 ; a < n ; ++a ) {
    if ( calcGCD( a, n ) > 1 ) {
      cout << a << " : Not exist." << endl;
      continue;
    }
    unsigned int k = 1;   // 指数
    unsigned int mod = 1; // n を法とする剰余
    for ( ; k < n ; ++k ) {
      mod = ( mod * a ) % n;
      if ( mod == 1 ) break;
    }
    cout << a << "^" << k << " = 1 (mod " << n << ")" << endl;
  }
}

処理の内容は非常に単純で、1 から n - 1 まで a を変化させながら、a と n が互いに素であることをチェックした上で、a^k ≡ 1 (mod n) となる最初の k を求め、その値を表示します。calcGCD は「ユークリッドの互除法 (Euclidean algorithm)」を使って最大公約数を求める関数で、この関数が 1 を返せば二数は互いに素であることになります。

n = 10 の場合は、次のような結果になります。

1^1 = 1 (mod 10)
2 : Not exist.
3^4 = 1 (mod 10)
4 : Not exist.
5 : Not exist.
6 : Not exist.
7^4 = 1 (mod 10)
8 : Not exist.
9^2 = 1 (mod 10)

ある正数 n に対し、位数が φ(n) と等しくなる a を「n を法とした原始根 (Primitive Root Modulo n)」といいます。上表の結果から、a = 3 は 4 を法とした原始根であり、a = 2, 3 は 5 を法とした原始根です。n = 8 のときは φ(8) = 4 ですが、a⁴ ≡ 1 (mod 8) を満たす a は存在しません。このように、全ての n に対して原始根が存在しているわけではありません。しかし、n が素数である場合、以下の定理が成り立ちます。

この定理は、素数を法とした場合に原始根が必ず存在することだけでなく、その個数まで明確にしてくれます。例えば、p = 5 ならば φ(5 - 1) = 2 なので、5 を法とする原始根は 2 つ存在し、上の表から a = 2, 3 の二つが原始根なので定理は確かに成り立っています。p = 7 のとき、φ(7 - 1) = 2 なので、7 を法とする原始根はやはり二つで、上の表から a = 3, 5 がそれらに該当します。

素数を法とする原始根は、指数が p - 1 のとき初めて 1 と合同になることから、k < p - 1 である任意の正数 k によるべき乗は 1 と合同になることはありません。g が原始根であるとき、任意の正数 m, n ( p - 1 ≥ m > n ≥ 1 ) に対して g^m ≡ gⁿ (mod p) であるとすると、g と p は互いに素なので両辺を gⁿ で割っても合同式は成り立って、g^m-n ≡ 1 (mod p) が成り立つことになります。m - n < p - 1 なので、これは g が原始根であることに矛盾することになり、g^m ≡ gⁿ (mod p) となるような m, n は存在しないことになります。これは、原始根に対し、その p - 1 までのべき乗は p を法として全て値が異なることを示しています。べき乗の個数は p - 1 個であり、p より小さな数はやはり p - 1 個なので、1 から p - 1 までの全ての数があるべき乗と合同であることもこの結果からわかります。

原始根 g が一つ見つかれば、そのべき乗を計算していくことで 1 から p - 1 の中のいずれかと合同な数が得られ、さらにその中の φ( p - 1 ) - 1 個が g 以外の原始根になります。g^m が原始根であると仮定すると、( g^m )^p-1 ≡ 1 (mod p) であり、n < p - 1 である全ての n に対しては ( g^m )ⁿ ≡ 1 (mod p) は成り立たないことを意味します。しかし、m と p - 1 の最大公約数 GCM( m, p - 1 ) = G が 1 より大きい場合、m = Gm' とすれば

となるので、Gn = p - 1 となるような n に対して ( g^m )ⁿ ≡ 1 (mod p) が成り立ってしまいます。つまり、べき乗が原始根になるためには、指数 m が p - 1 と互いに素である必要があることを意味します。1 から p - 1 の中で、p - 1 と互いに素な数の個数は φ(p - 1) 個で原始根の個数と等しいので、p - 1 と互いに素な指数 m で求めた各数は全て異なる原始根でなければなりません。よって、原始根が一つ得られれば、p - 1 と互いに素な数でべき乗を計算すれば全ての原始根が得られるということになります。

例えば、p = 37 の場合、最初に見つかる原始根は 2 です。37 を法とする 2 のべき乗 2^k を求めると次のようになります。

この中で、2 の他に原始根となるのは

であり、指数 k は全て p - 1 = 36 と互いに素となっています。k = 2 の場合、36 = 2・18 なので、

より 2² の位数は 18 以下であり、原始根ではありません。なお、2 に対して 36 より小さな指数では 1 と合同なべき乗が存在しないので、2² に対してもそれは成り立ち、2² の位数は 18 であると結論づけることができます。

原始根が一つ見つかれば、他の原始根を見つけることは容易ですが、その一つの原始根を見つけるのはどうでしょうか。原始根定理から、法 p の原始根の個数は φ( p - 1 ) 個なので、例えば p - 1 が素数 q の 2 倍で表されるのならば、φ( 2q ) = φ( 2 )φ( q ) = q - 1 で、p が非常に大きければ、約 p / 2 が原始根であるという事になります。二つの素数 q, r の 2 倍なら、φ( 2qr ) = φ( 2 )φ( q )φ( r ) = ( q - 1 )( r - 1 ) で、q と r が非常に大きくてほぼ同じ値とすれば、それらの数はおよそ ( p / 2 )^1/2 とみなせて、やはり p の約半分が原始根になります。p - 1 の内容にもよりますが、φ( p - 1 ) はそれほど小さな値ではないので、いくつかを試してみれば、原始根を見つけるのはそれほど大変ではありません。

また、原始根であるかどうかを確認するためには、2 からはじめて p - 1 までべき乗を計算し、p を法として 1 に合同なものがないかを調べる必要がありますが、実際には p - 1 までの全ての数でべき乗を計算する必要はありません。べき乗が p を法として 1 と合同になるのは、その指数が p - 1 の約数となるときです。p - 1 が素因数分解できて、その結果が p₁^e1 x p₂^e2 x ... x p_r^er ならば、位数はこの中にある素数から構成されているので、もし位数が p - 1 でなければ、ある素数 p_i ( i = 1, 2, ... r ) に対して ( p - 1 ) / p_i はその位数の倍数になるはずです。よって、i = 1, 2, ... r に対して指数を ( p - 1 ) / p_i としてべき乗を求め、p を法として 1 と合同であるかを確認すれば、原始根かどうかを判定することができます。

原始根を求めるためのサンプル・プログラムを以下に示します。

/*
  isPrime : 素数であるかを判別する

  unsigned int prime : 判別対象の自然数

  戻り値 : true ... 素数 ; false ... 合成数、0, 1 のいずれか
*/
bool isPrime( unsigned int prime )
{
  if ( prime == 0 || prime == 1 ) {
    return( false );
  }
  if ( prime == 2 ) {
    return( true );
  }
  if ( ( prime & 1 ) == 0 ) {
    return( false );
  }

  unsigned int maxNum = (unsigned int)( sqrt( prime ) ) + 1; // 試し除算する最大値
  for ( unsigned int div = 3 ; div < maxNum ; div += 2 )
    if ( prime % div == 0 ) return( false );

  return( true );
}

/*
  getPrimeFactor : 最小の素因数を取得する

  unsigned int n : 判別対象の自然数

  戻り値 : 最小の素因数(0,1,素数の場合は自分自身)
*/
unsigned int getPrimeFactor( unsigned int n )
{
  if ( n <= 2 ) return( n );
  if ( ( n & 1 ) == 0 ) return( 2 );

  unsigned int maxNum = (unsigned int)( sqrt( n ) ) + 1; // 試し除算する最大値
  for ( unsigned int div = 3 ; div < maxNum ; div += 2 )
    if ( n % div == 0 ) return( div );

  return( n );
}

/*
  intFactor : 素因数分解

  unsigned int num : 対象の自然数
  map<unsigned int,unsigned int>& mapDiv : 分解した素因数を格納するMap
*/
void intFactor( unsigned int num, map<unsigned int,unsigned int>& mapDiv )
{
  mapDiv.clear();
  for ( ; ; ) {
    unsigned int div = getPrimeFactor( num ); // 素因数
    if ( mapDiv.find( div ) != mapDiv.end() )
      mapDiv[div]++;
    else
      mapDiv[div] = 1;
    if ( div == num ) break;
    num /= div;
  }
}

/*
  calcPRoot : 原始根の計算(最小の原始根だけを求める)

  unsigned int p : 法

  p は素数に限定する

  戻り値 : 最小の原始根(pが素数でない場合、または原始根が見つからない場合ゼロを返す)
*/
unsigned int calcPRoot( unsigned int p )
{
  if ( ! isPrime( p ) ) return( 0 );

  unsigned int g = 1; // 最小の原始根

  // 最小の原始根 g を求める
  for ( ; g < p ; ++g ) {
    unsigned int mod = 1; // p を法とする剰余
    unsigned int k = 1;   // 指数
    for ( ; k < p - 1 ; ++k ) {
      mod = ( mod * g ) % p;
      if ( mod == 1 ) break;
    }
    if ( k == p - 1 ) return( g );
  }

  return( 0 );
}

/*
  calcPRoot2 : 原始根の計算( p - 1 の素因数を利用する )

  unsigned int p : 法

  p は素数に限定する

  戻り値 : 最小の原始根(pが素数でない場合、または原始根が見つからない場合ゼロを返す)
*/
unsigned int calcPRoot2( unsigned int p )
{
  typedef map<unsigned int,unsigned int> MapDiv;

  if ( ! isPrime( p ) ) return( 0 );

  unsigned int g = 1; // 最小の原始根
  MapDiv mapDiv; // p - 1 の素因数

  // p - 1 を素因数分解
  intFactor( p - 1, mapDiv );

  // 最小の原始根 g を求める
  for ( ; g < p ; ++g ) {
    MapDiv::const_iterator it = mapDiv.begin();
    for ( ; it != mapDiv.end() ; ++it ) {
      unsigned int k = ( p - 1 ) / it->first; // 指数
      if ( power( g, k, p ) == 1 ) break;
    }
    if ( it == mapDiv.end() ) return( g );
  }

  return( 0 );
}

/*
  calcPRoot : 原始根の計算

  unsigned int p : 法
  vector<unsigned int>& vecPRoot : 原始根を登録する配列

  p は素数に限定する

  戻り値 : true ... 成功 ; false ... p が素数ではない
*/
bool calcPRoot( unsigned int p, vector<unsigned int>& vecPRoot )
{
  vecPRoot.clear();

  unsigned int g = calcPRoot( p ); // 最小の原始根
  if ( g == 0 ) return( false );
  vecPRoot.push_back( g );

  unsigned int k;     // 指数
  unsigned int mod;   // p を法とする剰余

  // g のべき乗の中で、k が p - 1 と互いに素な値が原始根
  mod = g;
  for ( k = 2 ; k < p ; ++k ) {
    mod = ( mod * g ) % p;
    if ( calcGCD( k, p - 1 ) == 1 )
      vecPRoot.push_back( mod );
  }

  return( true );
}

素数 p だけを引数とする関数 calcPRoot と calcPRoot2 は最小の原始根を求めるために利用します。calcPRoot は、位数を求める場合と同様に、p を法として 1 と合同になるまでべき乗を計算し、1 と合同になった時の指数が p - 1 であればその時の数を返すようになっています。それに対し、calcPRoot2 は、p - 1 を素因数分解してから各素因数で p - 1 を割った数を指数としてべき乗を求め、その中に p を法として 1 と合同となるものがなければ原始根であると判定しています。どちらの場合も、p が素数でなければ処理をせずにゼロを返すようにしており、その時に利用する素数判定用関数は isPrime です。この関数では単純に試し割りをしているだけなので、大きな数に対しては利用することができません。また、素因数分解は関数 intFactor で行なっていますが、こちらも試し割りによる処理です。最後に、引数が、素数 p の他に、原始根を登録するための配列の二つある関数 calcPRoot は、先に説明した関数で最小の原始根を求めた後、そのべき乗から全ての原始根を求めるために利用します。

2) 離散対数問題 (Discrete Logarithm Problem)

素数 p を法とする原始根 g に対し、その p - 1 までのべき乗の中から、1 から p - 1 までの数のいずれかと合同なものが必ず見つかるのでした。あるべき乗と a が p を法として合同なときの指数を L(a) とすれば、

と表すことができます。p = 11 に対して実際に計算すると、最初に見つかる原始根 2 に対しては 2¹ ≡ 2 (mod 11) より L(2) = 1 であり、べき乗を順に計算することで以下の結果が得られます。

この表から、例えば L(10) = 5 なので 2⁵ ≡ 10 (mod p) であり、L(3) = 8 なので 2⁸ ≡ 3 (mod p) であることがわかります。

範囲を実数に広げると、一般的によく使われる普通の指数関数は

で表され、a は「底(Base)」と呼ばれます。また、この逆関数を

で表して、これを a を底とする対数関数というのでした。この 2 式をひとつにまとめて

と表すことができます。この式と、先ほど示した L(a) の式を見比べると非常によく似た形になっています。

似ているのは式の形だけでなく、その性質にも共通したものがあります。指数関数と対数関数は、以下の性質を持っているのでした。

L(a) に対する法則を確認するために、まずは L(ab) を次のように変形してみます。

g^L(ab) と g^L(a)+L(b) は p を法として合同になります。しかし g は原始根なので、これらが合同になるためには L(ab) - [ L(a) + L(b) ] が p - 1 の倍数でなければなりません。したがって、L(ab) と L(a) + L(b) は p - 1 を法として合同、すなわち

が成り立ちます。次に、L(a^k) を変形すると、

より、g^L(ak) と g^k・L(a) が p を法として合同になるので L(a^k) - k・L(a) は p - 1 の倍数であり、L(a^k) と k・L(a) は p - 1 を法として合同、すなわち

が成り立ちます。以上をまとめると、

となります。これは、先に示した対数関数に対する性質に一致するので、指数 L(a) は「離散対数(Discrete Logarithm)」と呼ばれる群の一種になります。この性質によって、乗法から加法への変換と、べき乗から乗法への変換が可能になり、指数 L(a) の表と組みわせることで合同式の計算を簡単にすることができます。

ここで誤りやすいのは、計算時に p - 1 ではなく p を法としてしまうということです。指数 L(a) に対して合同式を計算するときは p - 1 を法とするということに注意してください。

一つの原始根に対する指数の表を使って、ある法における合同式の計算を次のように行うことができます。例えば、11 を法としたとき、先ほど求めた 2 のべき乗の表から

であり、L(a) = 6 となる a は 9 なので、4・5 ≡ 9 (mod 11) であることがわかります。この例の場合、わざわざ指数表を使わなくても 4・5 = 20 ≡ 9 (mod 11) であることはすぐに求まりますが、数が大きくなると乗算よりも加算のほうが扱う値が小さくなり計算が楽になります。べき乗の場合、

であり、L(a) = 10 となる a は 1 なので、4¹⁰ ≡ 1 (mod 11) であることがわかります。この場合はべき乗計算の代わりに乗算を使うことになるため、やはり計算量を抑えることが可能になります。

しかし、計算するためには指数表が必須であり、またコンピュータの普及によって普通に処理を行なっても高速に回答を得ることができます。特に、「繰り返し自乗法(Exponentiation by Squaring)」を利用することでべき乗の合同式も高速に処理することが可能です。

指数表を利用した有効な手法として他には合同式を解くときに利用することができます。例えば、

を解く場合、9x と 4 が合同ならその指数も等しいので

より L(x) ≡ -4 ≡ 6 (mod 10) になり、指数表から x = 9 を求めることができます。さらに、

を解くときも、指数表を利用すれば

より 5・L(x) ≡ 5 (mod 10) になり、1 から 10 まで順番に L(x) の値を変化させれば L(x) = 1, 3, 5, 7, 9 すなわち x = 2, 8, 10, 7, 6 が解であることがわかります (補足 1)。

3) エルガマル暗号 (ElGamal Encryption)

離散対数は、暗号理論の中でも活用されるようになりました。その理由は、離散対数を求めることが非常に難しいからです。離散対数における式 a^k = b は、既知の a と k から b を求めることは比較的短時間で処理できますが、既知の a と b から離散対数 k を短時間で求めることは非常に難しい問題になります。これを「離散対数問題」といいます。原始根の指数は離散対数の代表であり、式 a^k ≡ b (mod p) において k を求めることは非常に困難です。よって、RSA 暗号が素因数分解の困難性を利用しているのと同様に、指数を求めることの困難性を利用した暗号理論として「エルガマル暗号」が誕生しました(補足 2)。「エルガマル暗号」は 1984 年にエジプト人暗号学者の「ターヘル・エルガマル(Taher Elgamal)」によって発表されたため、このような名前で呼ばれています。

エルガマル暗号では、原始根に対する指数 k が秘密鍵となり、法となる素数 p とその原始根 g は公開鍵になります。また、

となる数 a を求め、これも公開鍵とします。0 から p - 1 までの数 m を平文としたとき、乱数 r を選んで以下の二つの数 e₁, e₂ を求めます。

平文 m に対する暗号文はこの二つの数の組 ( e₁, e₂ ) になります。

送られてきた暗号文 ( e₁, e₂ ) を平文 m に戻すためには、まず秘密鍵 k を使って以下の式で数 c を求めます。

次に、

を満たす数 u を求めると、平文 m は

で求めることができます。実際、

となるので、先ほどの等式が成り立つことがわかります。a と g が公開されていることから、これを使って k を求めることができれば誰でも復号することが可能になりますが、例えば k を 1 から順番に大きくしながら全てのべき乗に対して a と等しいかをチェックする方法は、素因数分解において試し割りを行うことと同様で、値が大きくなると実用的な時間で解を得ることはできません。このため、簡単には暗号を解読することができないようになっています。素因数分解と同様に、さらに高度なアルゴリズムはありますが、いずれも任意の数に対して実用的な時間で解が得られるものではないようです。

例として、法 p = 37、原始根 g = 2、秘密鍵 k = 10 としたとき、

になります。乱数 r = 5 として m = 15 を暗号化すると

より ( 32, 6 ) という組が得られます。これを復号化するときは、

より、30u ≡ 1 (mod 37) を求めなければなりません。この解は u = 21 となって、m は

と求められ、正常に復号することができました。

uc ≡ 1 (mod p) を満たす u を求めるためには、uc - 1 = vp、すなわち uc - vp = 1 を満たす u, v を求めればよいので、ユークリッドの互助法を利用した一次方程式の解法を利用して機械的に計算することが可能です。一次方程式定理から、a, b の最大公約数 GCD( a, b ) = g としたとき、ax + by = g は必ず整数解を持ちます。p は素数で、c は 1 から p - 1 までの値にすることができるので、GCD( c, p ) = 1 が必ず成り立ち、uc - vp = 1 は解を持つことになります。

求められる解 u は無数に存在しますが、p を法として合同である場合は同じ解とみなします。そうではない解が複数あると仮定して、それを u₁, u₂ とすれば、u₁ ≡ u₂ (mod p) ではないことから u₁ - u₂ = kp + r ( k,r は整数で 0 < r < p ) と表すことができます。u₁, u₂ は uc ≡ 1 (mod p) の解なので、cu₁ ≡ 1 (mod p), cu₂ ≡ 1 (mod p) より c( u₁ - u₂ ) = lp を満たす整数 l が存在します。よって、

となりますが、c, r はともに 1 から p - 1 の整数で p は素数なので、cr は p の倍数にはならず、この式は成り立ちません。したがって、求められる解はただ一つということになります (補足 1)。

エルガマル暗号化・復号化を行うためのサンプル・プログラムを以下に示します。

/*
  power : 繰り返し自乗法を使った法nのべき乗計算( aのk乗をnで割った余りを求める )

  unsigned int a : 底
  unsigned int k : 指数
  unsigned int n : 法
*/
unsigned int power( unsigned int a, unsigned int k, unsigned int n )
{
  // n が 16Bit を越えると演算結果が 32Bit を越えるため
  if ( n >= 0x10000 ) return( 0 );

  if ( a == 0 || n == 0 ) return( 0 );  // 底や法が 0 の場合は 0 を返す
  if ( k == 0 ) return( 1 % n );        // 指数が 0 の場合は法 n における 1

  unsigned int currentMod = a % n;
  unsigned int currentValue = ( ( k & 1 ) > 0 ) ? currentMod : 1;

  for ( k >>= 1 ; k > 0 ; k >>= 1 ) {
    currentMod = ( currentMod * currentMod ) % n;
    if ( ( k & 1 ) > 0 )
      currentValue = ( currentValue * currentMod ) % n;
  }

  return( currentValue );
}

/*
  calcGCD : ユークリッドの互除法を使った最大公約数の計算
            ax + by = gcd(a,b)を満たす整数解を同時に求める

  unsigned int a, b : GCDを求める二つの自然数
  int& x, y : 整数解を格納するリファレンス

  戻り値 : 最大公約数
*/
unsigned int calcGCD( unsigned int a, unsigned int b, int& x, int& y )
{
  x = 1;
  y = 0;
  int x1 = 0;
  int y1 = 1;

  if ( a < b ) {
    swap( a, b );
    swap( x, y );
    swap( x1, y1 );
  }

  do {
    unsigned int q = a / b;
    unsigned int r = a % b;

    int x2 = x - q * x1;
    int y2 = y - q * y1;
    x = x1;
    y = y1;
    x1 = x2;
    y1 = y2;

    a = b;
    b = r;
  } while ( b != 0 );

  return( a );
}

/*
  ElGamal_enc : エルガマル暗号化

  unsigned int p : 法
  unsigned int g : 法 p の原始根
  unsigned int a : 公開鍵
  unsigned int m : 平文
  unsigned int& e1, e2 : 暗号文

  p は 16Bit 以内 ( < 0x10000 )の制限あり

  戻り値 : true ... 成功 ; false ... 失敗
*/
bool ElGamal_enc( unsigned int p, unsigned int g, unsigned int a,
                  unsigned int m, unsigned int& e1, unsigned int& e2 )
{
  if ( m >= p ) {
    cerr << "m[" << m << "] must be less than p[" << p << "]." << endl;
    return( false );
  }

  unsigned int r = rand(); // 乱数

  e1 = power( g, r, p );
  e2 = ( power( a, r, p ) * m ) % p;

  return( true );
}

/*
  ElGamal_dec : エルガマル復号化

  unsigned int p : 法
  unsigned int k : 秘密鍵
  unsigned int e1, e2 : 暗号文

  p は 16Bit 以内 ( < 0x10000 )の制限あり

  戻り値 : 平文
*/
unsigned int ElGamal_dec( unsigned int p, unsigned int k, unsigned int e1, unsigned int e2 )
{
  unsigned int c = power( e1, k, p );
  int u, v;
  calcGCD( c, p, u, v );
  if ( u < 0 ) u += p;

  return( ( u * e2 ) % p );
}

ElGamal_enc が暗号化、ElGamal_dec が復号化を行う関数です。法となる素数 p やその原始根 g、秘密鍵 k を使って求められる a ≡ g^k (mod p) は、処理に先立ってあらかじめ用意しておく必要があります。ElGamal_enc が行なっているのは、乱数 r を決めて、p を法とする g^r と ma^r を求めるだけです。べき乗の計算には、「繰り返し自乗法 (Exponentiation by Squaring)」のサンプル・プログラムにある power 関数を利用していますが、これは制限として法 p が 65535 ( 二進数での 16 ビット最大値 ) 以下であることが前提条件となっています。そのため、暗号化に利用できる数値も非常に小さな値しか利用できません。したがって、実用的なものではなく、あくまでもサンプル・プログラムとして見てください。

復号化の ElGamal_dec では、暗号文の一つ e₁ から p を法とする秘密鍵 k のべき乗 c を求め、cu ≡ 1 (mod p) となる u を計算して、最後にもう一つの暗号文 e₂ と u の p を法とする積を返します。cu ≡ 1 (mod p) となる u の計算では、ユークリッドの互助法を利用した一次方程式の計算用関数 calcGCD を使っています。

注意点として、暗号化に利用する乱数の扱い方があります。各データを暗号化するとき、全てに対して同じ乱数を利用すると安全性が低くなります。というのも、e₂ ≡ ma^r (mod p) より、一つでも m が見破られると a^r の値も同時に求めることができることになり、他の暗号文に対しても、既知の a^r と e₂ から合同式 a^rm ≡ e₂ (mod p) を解けば m が得られてしまいます。そもそも、乱数を全て等しくするなら各平文 m に対して e₁ を用意することは不要なはずで、わざわざ ( e₁, e₂ ) の対を暗号文としているのは乱数を毎回変える必要があるためです。もちろん、復号化の計算を見ればわかるように、乱数 r は復号のために残す必要はなく、使用後は捨ててしまっても問題はありません。

次のサンプル・プログラムは、エルガマル暗号・復号処理のテスト用ルーチンです。

/*
  createPrivateKey : エルガマル暗号用公開鍵の生成

  unsigned int p : 法
  unsigned int g : 法 p の原始根
  unsigned int k : 秘密鍵

  p は 16Bit 以内 ( < 0x10000 )の制限あり

  戻り値 : 公開鍵
*/
unsigned int createPrivateKey( unsigned int p, unsigned int g, unsigned int k )
{
  return( power( g, k, p ) );
}

/*
  ElGamal_test : エルガマル暗号・復号化テスト
*/
void ElGamal_test()
{
  unsigned int p = rand() >> 16;
  while ( ! isPrime( p ) )
    p = rand() >> 16;

  unsigned int g = calcPRoot( p );

  unsigned int k = rand();
  unsigned int a = createPrivateKey( p, g, k );

  cout << "<< ElGamal Encryption Test >>" << endl;
  cout << "prime number p = " << p << endl;
  cout << "primitive root g = " << g << endl;
  cout << "private key k = " << k << endl;
  cout << "public key a = " << a << endl << endl;

  unsigned int e1, e2;
  for ( unsigned int m = 0 ; m < p ; ++m ) {
    ElGamal_enc( p, g, a, m, e1, e2 );
    unsigned int d = ElGamal_dec( p, k, e1, e2 );
    if ( m != d ) {
      cout << "m[" << m << "] -> ( " << e1 << ", " << e2 << " ) -> " << d << " : ";
      cout << "Unmatched!!" << endl;
    }
  }
}

テスト用プログラムでは、最初に乱数列から素数になるもの p を抽出し、その最初の原始根 g を求めた上で秘密鍵 k を生成します。これらを使って 0 から p - 1 までの数値を暗号化・復号化し、複合した結果が元の平文と一致しているかをチェックします。

今回は、公開鍵暗号の一つである「エルガマル暗号」を紹介しました。この暗号は、前回紹介した RSA 暗号の次によく利用されているようです。RSA 暗号が素因数分解の困難性を利用しているのに対し、エルガまる暗号は離散対数問題の困難性を利用しているのでした。離散対数問題として他にも楕円曲線上の有理点(有理数からなる点)による離散対数を扱った暗号法として「楕円曲線暗号(Elliptic Curve Cryptography ; ECC)」というものも新たな暗号法として脚光を浴びているようです。

補足1) 合同式の計算

定数を a, b、変数を x としたとき、n を法とする合同式 ax ≡ b (mod n) の解は指数表がなくても求めることが可能です。このような合同式は一次方程式と呼ばれます。

ax ≡ b (mod n) が成り立つとき、ax - b = ny を満たす整数 y が存在します。したがって、一次方程式

を解くことによって x を求めることができます。「一次方程式定理」から、一次方程式の解は、b が a と n の最大公約数 g = GCM( a, n ) で割り切れるときのみ存在します。したがって、b が g の倍数でなければ合同式の解は存在しません。

b が g の倍数ならば解が存在するので、その解を x₀ とします。ここで、他の解 x₁ があると仮定すると、

より、ax₀ - ax₁ = a( x₀ - x₁ ) は n で割り切れることになります。a と n はどちらも g で割り切れるので、その商をそれぞれ Q_a, Q_n とすれば、Q_a( x₀ - x₁ ) が Q_n で割り切れることになります。ところが、Q_a と Q_n は互いに素なので、Q_n は x₀ - x₁ の約数であり、

を満たす整数 K が存在します。K が g の倍数ならば、KQ_n は n の倍数なので x₁ ≡ x₀ (mod n) であり、n を法として互いに合同な解になります。このような解は無数にあるので、互いに合同ではない解を考えると、K を 0 から g - 1 まで変化させた時、それら g 個の解は n を法として互いに合同ではない解となります。以上をまとめると、以下の定理となります。

解の一つを求めるためには、

を満たす u, v を求めれば充分です。両辺に b / g を掛ければ

となり、x ≡ bu / g (mod n) が求めたい解になります。あとは、解の数が g 個になるまで n / g を加算した値を求めれば、目的の全ての解が得られます。

以下に、合同式を計算するためのサンプル・プログラムを示します。

/*
  modCalc : 合同式の計算

  unsigned int a : x の係数
  unsigned int b : 解
  unsigned int n : 法

  戻り値 : true .. 解あり ; false ... 解なし
*/
bool modCalc( unsigned int a, unsigned int b, unsigned int n )
{
  cout << a << "x = " << b << " (mod " << n << ")";

  // a と n の最大公約数を求める
  unsigned int g = calcGCD( a, n );
  if ( b % g > 0 ) {
    cout << " has no solution." << endl;
    return( false );
  }

  // ax + ny = g の解を求める
  int x, y;
  calcGCD( a, n, x, y );
  if ( x < 0 ) x += n;

  // ax + ny = n の解を求める
  x = ( x * b / g ) % n;
  cout << endl << "x = " << x;
  for ( unsigned int i = 1 ; i < g ; ++i ) {
    cout << ", " << ( x + i * n / g ) % n;
  }
  cout << endl;

  return( true );
}

補足2) ディフィー・ヘルマン鍵共有 (Diffie-Hellman Key Exchange)

公開鍵暗号の考え方は、「ウィットフィールド・ディフィー (Whitfield Diffie)」によって 1975 年に発表されました。その翌年の 1976 年には、ディフィーと「マーティン・ヘルマン (Martin E. Hellman)」、「ラルフ・マークル (Ralph C. Merkle)」によって「鍵交換構想」として具体的な手法を含めて発表されていましたが、公開鍵暗号については RSA 暗号の登場を待つまで具体的な手法は発表されませんでした。

このとき発表された鍵交換の具体的な方法は「ディフィー・ヘルマン鍵共有 (Diffie-Hellman Key Exchange)」と呼ばれ、その安全性には、エルガマル暗号と同様に、原始根に対する離散対数問題の困難性が利用されています。

鍵交換とは、暗号・復号に利用する鍵を安全に配送するための手法を意味します。公開鍵暗号が誕生するまでの暗号は全て、暗号化と復号化に同じ鍵が必要でした。よって、送信した暗号を復号化するためには必ず共通の鍵が必要であり、前もってその鍵を受け取っておく必要があります。しかし、相手に鍵を送信するときに第三者が入手してしまえば、鍵を入手した者によって暗号を解読されてしまうことになります。鍵がデータである場合、ネットワーク上を流れる鍵の情報を盗聴することによって、鍵が入手されるおそれがあります。それを防止するための手法が「ディフィー・ヘルマン鍵共有」です。

ここで、暗号メッセージを送信する人物を「アリス」、それを受信する人物を「ボブ」とします。まず、アリスは公開鍵として素数 p とその原始根 g を決め、それをボブに送信します。アリスとボブは、それぞれ秘密鍵としてそれぞれ一つの整数 a, b を決めますが、これは互いに交換しません。
秘密鍵を決めたら、それを指数とする p を法とした g のべき乗を計算します。

アリスとボブは、計算した結果を互いに交換します。つまり、アリスはボブに対して A を、ボブはアリスに対して B を送付します。次に、アリスは受け取った値 B を使って、p を法とする a のべき乗を求め、ボブは受け取った値 A を使って、p を法とする b のべき乗を求めます。すると、それぞれの値は次のようになります。

これで、アリスとボブは共通な鍵 s ≡ g^ab (mod p) を得ることができました。ここで、メッセージを盗聴しようとする人物を「イヴ」とすると、イヴが入手できるのは法 p とその原始根 g、アリスとボブが互いに交換した A, B の 4 つになります。共通な鍵 s を得るためには秘密鍵の a, b を知る必要があり、そのためには離散対数問題である

を解かなければなりません。これは簡単に解くことができないので、アリスとボブは安全に鍵を決めることができるわけです。

鍵交換は、三人、あるいはそれ以上のメンバ間でも行うことができます。例えば、アリス、ボブ、キャロルの三人で鍵を交換する場合、

のように、各メンバが、受け取った値に対して自分の秘密鍵による p を法とするべき乗を計算して次の人に回し、最後に受け取った人がそれを共通の鍵とする操作を一回のループとし、このループを、先頭を一人ずつずらしながら繰り返します。各ループで最後に計算を行った人には、自分を含めた全てのメンバの秘密鍵を使ったべき乗の結果が得られます。先の例ではそれは g^abc (mod p) になります。しかし、このデータは決して送受信されることはなく、全秘密鍵のうち高々 N - 1 個 (先の例では最大二個) の秘密鍵によるべき乗しか外部へ送信されないため、これらが盗聴されたとしても簡単には共通の鍵を知ることはできません。

N 人のメンバならば、一回のループで N 回の計算を行い、そのループが N 回繰り返されるので、計算回数は合計 N² 回となります。メンバの数が増えると処理回数は急激に増加するため、「分割統治(divide-and-conquer)」方式で処理をすることで処理回数を抑える手法があります。例えば、A から H までの 8 人のメンバ間で鍵を共有する場合、それぞれの秘密鍵を a から h、法を p、その原始根を g とすれば

となります。処理は大きく三つの部分で構成され、最初は全体を二分割したグループ内で、全秘密鍵によるべき乗計算を行い、その結果を元に、さらにグループを二分割しながらべき乗を求める操作を繰り返して、最終的に共通な鍵を全員が得るという流れになります。上記の例では、最初の 4 人構成のグループでべき乗計算を計 8 回、二回目の二人構成のグループで計 8 回、最後の、全員が共通鍵を得る処理では、逆方向の処理が必要になるので計 16 回と、総計 32 回の計算回数になるので、最初の方法での 8² = 64 回に比べて半分の処理回数で済みます。

1. 「はじめての数論」 ジョセフ・H・シルヴァーマン著 (ピアソン・エデュケーション)
2. 「素因数分解と素数判定」 デヴィッド・M・ブレッソード著 (SiB access)
3. 「島ぶくろ様 ブログ」-「離散対数問題を使った公開鍵暗号 (ElGamal暗号、Diffe-Hellman鍵共有法)」
4. 「Security Akademeia」 - 「ElGamal暗号」
5. Wikipedia

前に戻る

タイトルに戻る