暗号化アルゴリズム

(3) 公開鍵暗号(Public key encryption)

第二次対戦後、コンピュータの普及により暗号の作成と解読処理にコンピュータが利用されるようになりました。黎明期には政府や軍部でしか活用されていなかったコンピュータも、トランジスタや集積回路の発明により性能が向上する一方、安価に製造できるようになり、商用化されてビジネス界にも普及するようになります。企業間の通信に暗号が利用され、暗号の標準化が求められるようになり、その中で誕生したアメリカの国家暗号規格がDES(Data Encryption Standard)でした。DESはその後、線形解読法や総当たり攻撃(Brute Force Attack)により容易に解読できることが判明し、AES(Advanced Encryption Standard)に取って代わることになります。
DESもAESも、暗号化と復号化には共通の「鍵」が必要です。暗号を送信する側と受信する側の間で鍵を共有する必要があるのは、今までに紹介した全ての暗号処理についても同様であり、鍵をいかに安全に配送するかが、常に大きな問題となっていました。特に、コンピュータの普及によって暗号が広く普及するようになると、配送のために多額な費用や大きな手間が必要になるだけでなく、鍵を配送すること自体がセキュリティ上の大きな弱点となるため、大量にある鍵をいかに安全に顧客に届けるかが大きな悩みの種となっていました。この「鍵配送問題」を解決する画期的な方法として、「公開鍵」は誕生しました。

1) 公開鍵暗号の原理

公開鍵暗号の基本的な考え方は、ウィットフィールド・ディフィー(Whitfield Diffie)によって1975年に発表されました。ちなみに、ディフィーの他にマーティン・ヘルマン(Martin E. Hellman)とラルフ・マークル(Ralph C. Merkle)が加わって「鍵交換構想」として1976年に発表された方法は、公開鍵暗号とは別のアイデアですが、これも鍵配送問題を解決するための手法になります。また、「鍵交換構想」は発表時に具体的な手法が見つかっていたのに対し、公開鍵暗号は、後述する「RSA暗号」が誕生するまで具体的な手法がありませんでした。

公開鍵暗号は、「非対称鍵」と呼ばれる新しい概念を組み込んだ暗号化方法です。今まで紹介してきた暗号は全て、暗号化と復号化が「対称的」になっており、復号を行うためには暗号の「逆変換」を行うため、どちらの処理にも同じ鍵が必要になります。しかし、非対称鍵を利用した暗号では暗号処理と復号処理で鍵が異なります。つまり、暗号処理用の鍵が分からなければ暗号化はできないし、復号処理用の鍵が分からなければ復号化ができないことになります。

ここで、暗号メッセージを送信する人物を「アリス」、それを受信する人物を「ボブ」、メッセージを盗聴しようとする人物を「イヴ」として、従来の共通鍵暗号と、公開鍵暗号の違いを見てみましょう。
共通鍵暗号の場合、アリスは暗号・復号処理をするための「共通鍵」をあらかじめボブに対して送信しておきます。アリスは、ボブに送ったものと同じ鍵を使ってメッセージを暗号化してからボブに送信し、ボブは受信したメッセージを、アリスから受け取った鍵を使って復号してメッセージを読みます。ここでもし、アリスがボブに対して鍵を送信した時に、イヴがその内容を盗んで鍵のコピーを入手できてしまえば、その後に送信されるメッセージは容易に解読できてしまいます。この鍵の配送が、セキュリティ上の最も大きな弱点となる訳です。

非対称鍵を利用する場合、ボブの方から暗号処理用の鍵をアリスに対して送付します。この鍵は「公開鍵(Public key)」と呼ばれ、イヴなどの第三者に知られても問題はありません。アリスは受け取った公開鍵を使ってメッセージを暗号化し、ボブに送ります。ボブは受け取ったメッセージを、今度は復号処理用の鍵を使って復号します。この鍵は「秘密鍵(Private key)」と呼ばれ、アリスをはじめ誰にも公開しない、ボブだけが知っている鍵になります。
公開鍵を入手できれば、アリスだけでなく第三者のイヴでさえもメッセージを暗号化することは可能になります。しかし、それを復号化することは、メッセージを暗号化したアリス自身でさえも不可能で、秘密鍵を持っているボブだけができます。これが、公開鍵暗号の基本的な仕組みになります。

上記の例では公開鍵で処理した暗号を秘密鍵で復号化していますが、逆に秘密鍵で処理した暗号を公開鍵で復号化することもできます。例えば、ボブが自分の秘密鍵でメッセージを暗号化し、それをアリスに送信したとします。アリスはこれをボブの公開鍵で復号化すれば、メッセージの内容を読むことができます。復号処理は、アリスだけではなく第三者のイヴでも可能になるので、一見すると暗号化する意味はないように思えます。しかし、ボブが自分の秘密鍵で暗号化してはじめて、ボブの公開鍵で復号化することができることになるため、送信されたメッセージはボブ自身が送信したものであるという証明になります。もし、イヴがボブになりすましてアリスにメッセージを送信しようとしても、イヴが送ったメッセージはボブの公開鍵では復号できないため、ボブが送信したメッセージではないことが見破られてしまいます。このように、メッセージの送信者を証明するために公開鍵暗号を利用することも可能であり、このような仕組みを電子署名(Digital signature)と言います。

2) RSA暗号

公開鍵暗号を実現させるためには、非対称鍵を使った暗号処理と復号処理を見つけ出す必要があります。このような暗号を最初に発表したのは、当時MITの研究者だった、ロナルド・リベスト(Ronald Lorin Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Leonard Max Adleman)の三人だったため、彼らの名前の頭文字を取ってRSA暗号と呼ばれます。この発表は1977年に行われ、発表した三名は2002年にチューリング賞を受賞しています。
余談になりますが、RSA暗号を最初に発見したのは、実は英国政府通信本部(GCHQ)に勤めていたクリフォード・コックス(Clifford Cocks)です。また、公開鍵暗号が可能であることを最初に証明したのは、同じくGCHQの職員であるジェイムズ・エリス(James Ellis)であり、その考え方を元にコックスが具体的な方法を発見しました。さらにその内容を聞いたマルコム・ウィリアムソン(Malcolm J. Williamson)が、欠陥がないか探しているうちに発見したのが「鍵交換構想」です。エリスが公開鍵暗号を発見したのが1969年、それを元にコックスがRSA暗号を発見したのが1973年、ウィリアムソンが鍵交換構想を発見したのが1974年と、世界中に発表されるより前に基本的な概念は全てGCHQのメンバによって発見されていたにも関わらず、英国政府がそれを極秘扱いとしたために、世間に公表することはありませんでした。この事実が公表されたのは、発見から13年も後の1997年の事です。

RSA暗号を行うためには、いくつかのパラメータが必要となります。まず、公開鍵として二つの整数値をある手順にしたがって決めます。例として、二つの整数値をN = 15とe = 3とします。Nは二つの素数の積から導かれます。上記の例の場合、その素数は3と5になります。この二つの素数とeからある手順で求められるパラメータをdとします。この例では、d = 3になります。Nを求めるための二つの素数とdは秘密鍵になります。

平文パラメータCを暗号化するには、Cをe乗してからNで割った余りを求めます。C = 7の場合、7³ = 343を15で割った余りは13になります。これを復号する場合、今度はd乗してからNで割った余りを求めます。13³ = 2197で、15で割った余りは7になり、正しく復号されていることが分かります。

公開鍵と暗号鍵が決まれば、暗号化と復号化の処理自体は非常に単純です。しかし、実際に利用する公開鍵や秘密鍵は例で示したような小さな値ではなく、非常に大きな数(300〜1000桁程度)となるため、普通のやり方では計算を行うことはできません。また、公開鍵と秘密鍵を決める手順は非常に複雑で、その内容を理解するためには数論の知識が必要となります。

3) 合同式(Modular arithmetic)

RSA暗号を理解するためには、まず合同式の知識が必要になります。合同式(モジュラー算術、時計算術とも言います)は、次のような定義になります。

これを「a ≡ b (mod n)」と書き表します。また、整数nは法(modulo)と言います。

法が等しい合同式は、通常の方程式と同様の性質を持ちます。a₁ ≡ b₁ (mod n)、a₂ ≡ b₂ (mod n)のとき、

となります。これらは、(a₁ - b₁) = k₁n、(a₂ - b₂) = k₂nとすると容易に証明できます。

また、任意の整数kに対してk ≡ k (mod n)なので、a ≡ b (mod n)のとき

が成り立ちます。さらに、a₁a₂ ≡ b₁b₂ (mod n)において、a₁ = a₂ = a、b₁ = b₂ = bならばa² ≡ b² (mod n)となり、この操作を繰り返すことにより、任意の自然数mに対しては

が成り立つことが分かります。

しかし除算の場合 (a/k ≡ b/k (mod n)) は常に成り立つ訳ではないことに注意が必要です。例えば、40 ≡ 30 (mod 10)ですが、これを2で割ったとき、20 ≡ 15 (mod 10)は成り立ちません。
ac ≡ bc (mod n)の時、ac - bc = knを満たす整数kが存在します。この式はa - b = kn/cと変形することができ、左辺が整数であることから右辺も必ず整数となるため、knはcで割り切れます。ここで、cとnが互いに素である(*1)ならば、kがcで割り切れる必要があり、この時a - b = (k/c)n ≡ 0 (mod n)となります。従って、

が成り立ちます。

(*1) 互いに素である(be coprime) ... 二つの整数が1と-1以外に共通の約数を持たないとき、その二数は互いに素である。

(*2) gcd(a,b) ... 二つの整数a,bの最大公約数。a,bが互いに素の時、必ずgcd(a,b) = 1が成り立つ。公約数については後述。

4) 繰り返し自乗法(Exponentiation by squaring)

RSA暗号処理では合同式が利用されています。先に説明した暗号処理を合同式で表すと、C^e ≡ X (mod N)となる未知数Xを求めることになります。しかし、eやNが非常に大きい場合、例えば

3^500000000 ≡ X (mod 1000000000)

となる未知数Xを求めたいとき、まともに3^500000000を計算するのはコンピュータを使ったとしても非常に大変な作業です。この作業を効率よく行うために、繰り返し自乗法という方法が利用されます。

a^k (mod n)を求めるとき、まずはkを2のべき乗の和

k = Σ2ⁱu_i = u₀ + 2u₁ + 2²u₂ + ...

で表します。これをkの二進展開と言います。上式の中で、u_iは0または1になります。この時、

と表すことができます。ここで、a^2kを繰り返し自乗法で計算します。a ≡ A (mod n)のとき、a² ≡ A² (mod n)になることを利用すると、以下のように処理を行うことができます。

nを法とした場合、結果のA_iは必ずnより小さくなります。よって繰り返して平方を計算してもその値は常にnを越えず、大きな数値を扱う必要がなくなります。
A_iを使うと、a^k (mod n)は、

a^k ≡ A₀^u0・A₁^u1・A₂^u2・...

と計算することができます。u_iは0または1なので、u_i = 1となる値だけを抽出して乗算を行えば結果が得られます。一度に乗算を行わず、二つの値を掛け合わせた後、nを法として合同な値を求める操作を繰り返していけば、乗算の結果が大きくなることもありません。

例として 2⁴⁰⁹⁹ (mod 100)を計算してみると、

4099 = 4096 + 2 + 1

となり、繰り返し自乗法により、

と計算できるので、

と、大きな数を扱うことなく求めることができます。
ちなみに、2⁴⁰⁹⁹を計算すると、

835511105130522005353402168573299506063971399237907024307386786627163
126377245965479061449547998046672712085371551410270390058750548634885
810588870281092222356765581234967998672289272107506974651542456009484
756981101055071518170196537867747475669293997446326964642963257027238
992094887291574382226878423205349551181505430228757524504152208752479
663562746258775442421357154447220012777919894171372433355068447908233
189054590331547597387270249498111597180080151233079206733649340074934
667080440826377670615640615986893095529546412171037460669750473466925
400977054794277094500440180798640329875827890076539593755693619045204
730596488660585468304070086897682267416158158561850535214142405340156
388063937309135496228300099827211925727308367986232410719689241435416
885464907272467418307423833243879826363458827613652178615249115924790
154401698370716550226303158752492805930356539935858440457313901723853
057104504836722332909541366674285152584358319977521425172610778579080
213802447919836796872639575361419699854174759893964527400142663256378
495546532440646054577477257397098637507930255616253965601952741293528
699318708062729543843618385485871182118482500868722401041930773751781
3385731932089052823366253904267488721950437666723225233522688

になります。2を4桁の数でべき乗しただけでも、このような大きい数になってしまうため、数百桁の数でのべき乗を計算することはほとんど不可能になります。

以下に繰り返し自乗法のサンプル・プログラムを示します。

/*
  繰り返し自乗法を使った法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 );
}

このサンプル・プログラムでは、乗算時のオーバーフローを防ぐため、法を16ビットまでとしています。変数currentModは法modにおける繰り返し自乗法の結果を保持し、指数kの最下位ビットが立っていれば、その値をcurrentValueに掛けていく操作を、指数kを右側にビットシフトしながら0になるまで繰り返します。
処理時のループ回数は指数のビット数になるためその値はlog₂(k)で桁数の約3倍程度です。kが100桁であったとしても、300ステップ程度で計算できることになります。

5) 最大公約数と一次方程式の関係

整数mを整数nで割った余りが0である時(整数mが整数nで割り切れる時)、mはnの倍数(multiple)、nはmの約数(divisor)といいます。この時、m = nkを満たす整数kが存在し、n | mと表します。例えば、整数6は整数3で割り切れるので、3 | 6となります。
二つの整数aとbのどちらも割り切れる整数を公約数(common divisor)といい、その中で最大のものを最大公約数(Greatest Common Divisor;略してgcd)といいます。例えば、12と16の公約数は1,2,4の三つあるので、最大公約数は4になります。

最大公約数を求める有名な方法として、ユークリッドの互除法(Euclidean algorithm)があります。これは世界最古のアルゴリズムの一つとして知られ、その内容は、紀元前300年頃に記されたユークリッドの「原論」(Euclid's Elements)の中にあります。
ユークリッドの互除法は、以下のようなアルゴリズムになります。

例として、10817353681と10468815569に対してユークリッドの互除法を使ってみます。

10817353681 = 104729 X 103289、10468815569 = 104729 X 99961なので、確かに104729は10817353681と10468815569の公約数です。なぜこのような操作で公約数が求められるのかを、上の例で考えてみたいと思います。

一番下の行の計算から、最大公約数として求められた値104729は6283740の約数であることが分かります。そのすぐ上の行を見ると、6388469 = 1 X 6283740 + 104729かつ6283740も104729も104729で割り切れることから、104729 | 6388469が成り立ちます。この操作を繰り返していくと、左辺の値は全て104729で割り切れることが分かります。一番上の行と二番めの行において、左辺は最大公約数を求めようとしている値10817353681と10468815569になります。したがって、104729は10817353681と10468815569の公約数であることになります。

しかし、これだけでは104729が最大の公約数であることが証明されていません。そこで、整数dを、10817353681と10468815569の任意の公約数だと仮定します。この時、上の例において、最初の式は d | 348538112が成り立つことを示しています。これは第二式以降も同様で、各式で求められた余りrに対して常にd | rが成り立っているため、最後から二番めの式においても、d | 104729が成り立ちます。任意の公約数に対して常にd | 104729が成り立つので、104729は最大公約数でなければなりません。

最後に、この処理が必ず有限な回数で終了するのか(最終的には必ず余りが0になって、最大公約数を求めることができるか)という問題があります。上記の例を見ると明らかなように、各操作においてa = kb + r (k>0)から常にa > rとなります。つまり、rは常に小さくなる(n回目の操作に対する余りをr_nとすると、必ずr_n>r_n+1となる)ため、どのような整数のペアに対しても最終的にはr=0になることが保証されます。

次に、二つの整数aとbについて、aの倍数とbの倍数の和の集合を考えてみます。例として、a = 12、b = 16としたときの12x + 16yの値のいくつかを表にしてみます。

上表において、全ての数は4で割り切れます。これは、12x + 16y = 4( 3x + 4y )となることから容易に証明できます。一般的に、ax + byの解は全て、aとbの最大公約数(以下gcd(a,b)と表します)で割り切れます。よって、ax + byの解としてgcd(a,b)が存在すれば、それは常に正の数の最小値となります。それでは、ax + by = gcd(a,b)となる整数xとyは、常に存在するのでしょうか？

このことを調べるために、もう一度ユークリッドの互除法を利用したいと思います。まずは、別の例として二つの整数34と44の最大公約数を、ユークリッドの互除法を使って解いてみます。

44 = 1 x 34 + 10
34 = 3 x 10 +  4
10 = 2 x  4 +  2 ← gcd
 4 = 2 x  2 +  0

ここで、a = 44、b = 34として、最初の式を変形してみます。

44 = 1 x 34 + 10
10 = 44 - 1 x 34
   = a - b                               --- (1)

(1) を二番めの式の値10に代入し、同じように変形します。

34 = 3 x 10 + 4
 b = 3 x (a - b) + 4
 4 = b - 3 x (a - b)
   = -3a + 4b                            --- (2)

さらに、(1)と(2)を三番めの式の値10と4それぞれに代入して式を変形します。

10    = 2 x 4 + 2
a - b = 2 x (-3a + 4b) + 2
2     = (a - b) - 2 x (-3a + 4b)
      = 7a - 9b                          --- (3)

最後に得られた式(3)は、a = 44、b = 34に対してax + by = gcd(a,b) = 2を満たす解x、yが見つかったことを示しており、その解はx = 7、y = -9となります。実際に代入してみると、

7a - 9b = 7 x 44 - 9 x 34
        = 308 - 306 = 2

となり、正しい値が得られていることが確認できます。このように、ユークリッドの互除法を利用することによって、ax + by = gcd(a,b)を満たす解を求めることが必ずできるため、次の重要な定理が成り立つことが分かります。

ユークリッドの互除法を利用して、一次方程式 ax + by = gcd(a,b) の解を求めるアルゴリズムを以下に示します。但し、あらかじめa>bが成り立つように式を並べ替えてあるものとします。

(x,y)と(x1,y1)はどちらもax + byの整数解を表しており、(x,y)は、(x1,y1)の直前の解になります。商qと(x1,y1)の積を(x,y)から引いた値を新たな(x1,y1)とし、古い(x1,y1)は(x,y)に代入するという操作を、r=0になるまで繰り返しています。
ユークリッドの互除法を一般式で表すと以下のようになります。この結果を見ると、二つ前の(x1,y1)から、商qと直前の(x1,y1)との積を引いた値がaとbの係数になっている様子が理解できると思います。

以下にユークリッドの互除法のサンプル・プログラムを示します。

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

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

  戻り値 : 最大公約数
*/
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 );
}
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 );
}

関数として、ユークリッドの互除法を利用して最大公約数のみ算出するものと、同時に一次方程式の解を求めるものの二つがあります。
処理の前に、aとbの大小関係をチェックして、a<bならば交換を行っています。一次方程式の解を求めるバージョンでは同時に他の変数も交換していることに注意してください。この処理によって、ax + by = gcd(a,b)が、by + ax = gcd(a,b)に変わることになります。
ところで、a>0 かつ b>0 ならば、一次方程式の形として次のような4つのパターンが考えられます。

1. ax + by = gcd(a,b)
2. ax - by = gcd(a,b)
3. -ax + by = gcd(a,b)
4. -ax - by = gcd(a,b)

サンプル・プログラムでは一番めのパターンだけに対応しているため、他のパターンに対しては誤った解を返すことになります。しかし、他のパターンについては符号が変化しているだけなので、得られたxとyの値に対して処理後に符号を変換すれば正しい値が得られます。例えば、先の例で示した44x + 34y = 2の解はx = 7、y = -9であり、一次方程式が44x - 34y = 2になったとしてもyの符号を反転して9とすれば結果は正しくなります。

6) フェルマーの小定理とオイラーの公式

ピエール・ド・フェルマー(Pierre de Fermat)は、次に示す「フェルマーの最終定理」で有名な人物です。

この有名な定理は、フェルマー自身が証明したのではなく(「証明を見つけたが、それを書くには余白が狭すぎる」と書いてあるだけでした)、1994年にアンドリュー・ワイルズ(Andrew Wiles)によって証明されました。フェルマーがこの定理を書き込んでから実に350年もの間、この定理は証明されず、数々の数学者を悩ませてきました。

フェルマーの最終定理を証明するためには、現代数学において重要な「谷山・志村予想」を証明する必要がありました。そういう意味では、ワイルズが達成したこの偉業は非常に意味のあることでした。しかし、フェルマーの最終定理自体に利用価値はあまりありません。フェルマーが残した定理には、もっと重要なものがあります。それが「フェルマーの小定理」です。

この定理もフェルマー自身ではなく、微積分で有名なゴットフリート・ライプニッツ(Gottfried Wilhelm Leibniz)が証明しています。

例として、整数の平方を3で割ったときの余りを調べてみます。

さらに、整数の4乗を5で割ったときの余りについても調べてみます。

aがpと互いに素でなければ、a = mpとする整数mが必ず存在することになるため、任意の自然数kに対してa^k = (mp)^k ≡ 0 (mod p)が成り立ちます。それ以外を見てみると、確かにa^p-1 (mod p)の値が常に1になっていることが分かると思います。

さらに、この定理を、法が合成数である場合にまで拡張します。まずはその前に、その定理の中で使われる関数を紹介しておきます。

この関数を使うと、以下の定理が成り立ちます。

素数pに対しては、φ(p) = p - 1が成り立ちます。従って、フェルマーの小定理はオイラーの定理を素数の場合に特化したものと考えることができます。

例として、n = 4の時を考えてみます。4以下で互いに素な自然数は1と3の二つなので、φ(4) = 2になります。この時、任意の整数aに対して、4を法としたa^φ(4) = a²の値は以下のようになります。

もうひとつ、n = 15の時を考えてみると、15以下で互いに素な自然数は{1,2,4,7,8,11,13,14}で8個となるため、φ(15) = 8であり、15を法としたa^φ(15) = a⁸の値は、

となります。15 = 3 x 5から、3と5の倍数については1以外の数値となっていますが、それ以外は必ず1と合同になっています。このように、aとnが互いに素であれば、必ずa^φ(n) (mod n)の値が1になることが分かります。

フェルマーの小定理やオイラーの定理は、べき乗の合同式を計算する時に役に立ちます。例えば、7¹⁰⁰⁰¹ (mod 11)を計算する場合、前述の繰り返し自乗法を利用して解くこともできますが、フェルマーの小定理 7¹⁰ ≡ 1 (mod 11)を利用すると、7¹⁰⁰⁰¹ = 7 x (7¹⁰)¹⁰⁰⁰ ≡ 7 x 1¹⁰⁰⁰ ≡ 7 (mod 11)と簡単に解くことができてしまいます。

7) nを法とするk乗根の計算

繰り返し自乗法やフェルマーの小定理・オイラーの定理を利用することにより、どんなに大きな数に対しても法nにおけるべき乗の計算ができることを説明しました。次に、nを法とするk乗根の計算、すなわち、数bに対して

x^k ≡ b (mod n)

を満たすxを求めることを考えてみます。

フェルマーの小定理・オイラーの定理を利用すると、ある値uのべき乗を計算することによって、

(x^k)^u = x^ku = x^{1 + φ(n)v} ≡ x ≡ b^u (mod n)

のように変換して、べき乗計算によって解を導き出すことができます(但し、オイラーの定理 x^φ(n) ≡ 1 (mod n) を利用しているため、これが成り立つにはxとnが互いに素である必要があります)。ある値uを導き出すためには、上の式から

ku = 1 + φ(n)v

を満たす整数u,vを求めればよく、これは一次方程式

ku - φ(n)v = 1

の解を求める操作と同等になります。gcd(k,φ(n)) = 1を満たす場合、解は必ず存在することになるため、ユークリッドの互除法を利用してuの値を導き出せば、先程の式からb^u (mod n)を計算することで解を求めることができます。

例として

x⁴⁹ ≡ 12 (mod 13)

の解を計算します。13は素数なので、φ(13) = 13 - 1 = 12となり、この式をu乗すると

(x⁴⁹)^u = x^49u = x^{1 + 12v} ≡ x ≡ 12^u (mod 13)

から、

49u - 12v = 1

の解を求めることになります。gcd(49,12) = 1なので解は必ずあり、その解をユークリッドの互除法を使って解くと

49 = 4 x 12 + 1 → 1 = a - 4b

からu = 1、v = 4になります。よって、x ≡ 12¹ ≡ 12 (mod 13)と求めることができます。実際に検算してみると、

12⁴⁹ = 75836984583351248111063210627854719374392938360471552 ≡ 12 (mod 13)

となり、正しいことが分かります。

前述の通り、この計算においてオイラーの定理を利用している部分があり、これが成り立つためにはxとnが互いに素である必要があります。また、

x ≡ b^u (mod n)

の両辺をk乗すると、

x^k ≡ b^ku ≡ b^{1 + φ(n)v} ≡ b (mod n)

となるため、x^k ≡ b (mod n)となることが証明できるのですが、ここでもオイラーの定理 b^φ(n) ≡ 1 (mod n) が利用されているため、bとnも互いに素である必要があります。xは未知数なので、こちらの方が必要条件になります。

これが成り立たない場合、例えば

x^k ≡ gm (mod g²) (但しm<g)

のような計算式に対しては、ku - φ(g²)v = 1を満たすu,vを求めたとしても、u>1ならば

x ≡ (gm)^u ≡ g²g^u-2m^u ≡ 0 (mod g²)

となり、うまく計算ができません。このように、この方法が常に利用できる訳ではありませんが、少なくともxやbとnが互いに素であり、オイラーの定理が利用できればk乗根を計算することは可能です。

今までの内容を整理しておきたいと思います。

gcd(k,φ(n)) = 1は、一次方程式の解が存在するために必要となることに注意してください。

さて、k乗根はただ一つの解となるのか疑問に思うかもしれません。b^u (mod n)の値は、uが一意に決まれば0 ≦ x ≦ n - 1の間でただ一つのみになりますが、

ku - φ(n)v = 1

の解は無限に存在し、ユークリッドの互除法によって求めた解(u,v) = (u₀,v₀)に対して (u,v) = (u₀ + mφ(n),v₀ + mk) (但しmは任意の整数)となります。

しかしこの時、

x ≡ b^{u0 + mφ(n)} (mod n)

となり、gcd(b,n) = 1よりオイラーの定理 b^φ(n) ≡ 1 (mod n)が成り立つので

x ≡ b^u0・b^mφ(n) ≡ b^u0・(b^φ(n))^m ≡ b^u0 (mod n)

からuがどのような値を取っても結果は一意に決まります。一次方程式の解uが負数だった場合、φ(n)を加えて正数となるように補正する必要がありますが、このような処理をした場合でも、k乗根の解が変化することはありません。

最後に、k乗根が等しくなる数は存在しないのかという問題について考えてみます。式に表すと、

x^k ≡ b (mod n) かつ y^k ≡ b (mod n)

となる、互いに異なる数x,yが存在しないのかということになります。二式の両辺をu乗したとき、

x^ku = x^{1 + φ(n)v} ≡ x ≡ b^u (mod n)

y^ku = y^{1 + φ(n)v} ≡ y ≡ b^u (mod n)

となるため、x - y ≡ 0 (mod n)であり、xとyはnを法として合同になります。よって、x≦nかつy≦nならばxとyは等しくなります。これはつまり、kとφ(n)が互いに素であるならば、法n以下の数に対してk乗またはk乗根を計算した場合、全ての数に対して結果が一致しないことを意味します。例として、k = 3、n = 11の場合のk乗を計算すると、以下のようになります。

これが k = 2、n = 11となった場合、

となります。この表を見ると、例えば x² ≡ 4 (mod 11) を満たす数xは2と9の二つ存在することになります。

k乗根を計算するためには、法nのオイラーのφ関数φ(n)の値を求める必要があります。オイラー関数には、以下の公式が存在します。

よって、nが素因数分解できればφ(n)を求めることができるということになります。例えば、φ(36)を計算した場合、

φ(36) = φ(4)φ(9) = φ(2²)φ(3²) = (2² - 2¹)(3² - 3¹) = 2 x 6 = 12

になります。

8) RSA暗号の原理

ここまで説明した数論に関する内容は全て、RSA暗号を理解するために必要になります。RSA暗号化と復号化の処理が、今まで説明した内容をどのように利用しているのかを一つずつ見ていきたいと思います。

まず、暗号化のために用意しなければならないのが公開鍵になります。公開鍵を作成するためにはまず、二つの素数pとqを用意します。ここでは例として、二桁の素数である17と19を選びます。この二数を掛け合わせた数n = pq = 323が公開鍵の一つとなります。
n = 323のオイラー関数φ(n)を計算すると、φ(n) = φ(pq) = (p - 1)(q - 1) = 16 x 18 = 288になります。この値と互いに素な数kを選びます。ここではk = 5とします。これが二つめの公開鍵となります。

ここでは例として、「RSA」を暗号化してみます。これらの文字コードはそれぞれ82,83,65になり、この値をP、暗号化した値をCとして、C = P^k (mod n)を計算します。

C(82) = 82⁵ ≡ 233 (mod 323)
C(83) = 83⁵ ≡ 87 (mod 323)
C(65) = 65⁵ ≡ 12 (mod 323)

今度は、暗号化した値を復号してみます。復号を行うためには、P^k ≡ C (mod n)を満たす値Pを計算することと同等なので、nを法とするk乗根の計算方法を利用することができます。

ku - φ(n)v = 5u - 288v = 1

を解くと、u = 173、v = 3となり、復号化はP ≡ C^u (mod n)を計算することにより

P(233) = 233¹⁷³ ≡ 82 (mod 323)
P(87) = 87¹⁷³ ≡ 83 (mod 323)
P(12) = 12¹⁷³ ≡ 65 (mod 323)

となり、正常に復号化されます。この時利用したu = 173が秘密鍵となります。

復号化時には、常に対象の値がnと互いに素であるとは限らないため、正常に復号化されていない可能性があるように思えますが、実際には互いに素でなくても正常に復号化することができます。上記の例で、P = 289としたとき、これを暗号化すると

C(289) = 289⁵ ≡ 17 (mod 323)

となり、復号化すると

P(17) = 17¹⁷³ ≡ 289 (mod 323)

と正常に処理することができます。17|323なので、この二数は互いに素ではないのですが、ある条件を満たすときは正しくk乗根を計算することを証明することができます。その条件と証明方法を以下に示します。

前に示した例で実際に確認してみましょう。

5u - 288v = 1の解u = 173、v = 3から

x⁵ ≡ 17^5x173 ≡ 17^1+φ(323)x3 (mod 323)

この時、x⁵ ≡ 17 (mod 323)が成り立つためには

17^1+φ(323)x3 - 17 = 17(17^φ(323)x3 - 1)

が323で割り切れればよいことになります。323 = 17 x 19なので、上式が323で割り切れるためには 17^φ(323)x3 - 1 が19で割り切れればよいことになり、

17^φ(323)x3 ≡ 1 (mod 19)

が証明できればいいことになります。φ(323) = φ(17x19) = φ(17)φ(19)より、

17^φ(323)x3 = 17^{φ(17)φ(19)x3} = (17^φ(19))^φ(17)x3 ≡ 1 (mod 19)

となり、x⁵ ≡ 17 (mod 323)が成り立つことが証明されました。

RSA暗号では二つの素数の積を法として処理を行っているため、この条件を必ず満たすことになります。従って、どのようなデータに対しても正しく処理することができるわけです。

それでは、このような方法で本当に安全な暗号となっているのでしょうか？ 秘密鍵は、一次方程式の解uであり、これを導くためには素数の積nに対するオイラーのφ関数φ(n)を解くことができれば可能になります。公開鍵は素数の積nとべき数kであり、二つの素数をp,qとするとφ(n) = φ(p)φ(q) = (p - 1)(q - 1) = n - (p + q) + 1なので、結局nを素因数分解して二つの素数を見つけることができれば秘密鍵を得ることができてしまいます。上記の例では323を素因数分解して17と19を得てしまえば、誰でも復号化をすることが可能です。これでは鍵を隠しておいても無駄なことになります。
素因数分解は学校でも習ったことがあると思います。素因数分解の方法を習ったとき、それがあまりにも勘と経験に頼ったやり方だったので、他に確実に処理できるやり方があるのではないかと疑問に思った記憶があります。通常は、いくつかの数で除算を試してみて、割り切れたらその数と商に分解することを繰り返すというように習ったのではないでしょうか。例えば36ならば2で2回割ると9になり、これは3の平方になるので、36 = 2² x 3²と素因数分解できます。
それでは2047757を素因数分解するといくつになるでしょうか？ 答えは、2047757 = 1429 x 1433です。学校で習ったやり方で答えを導くのは、ほとんど不可能ではないでしょうか。テストなどで素因数分解の問題が出題されると、三桁程度の数の素因数分解でさえも時間がかかることがあると思います(667は素因数分解できるでしょうか？)。
コンピュータを利用すれば、上の例のような数でも比較的早く素因数分解できるでしょう。2から始めて順番に除算をする処理を繰り返していけばいいので、プログラムを作成することも簡単にできます。以下に、素因数分解のためのサンプル・プログラムを示します。

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

  unsigned int prime : 判別対象の自然数
  unsigned int& div : 最小の素因数
*/
bool isPrime( unsigned int prime, unsigned int& div )
{
  if ( prime == 0 || prime == 1 ) {
    div = prime;
    return( false );
  }
  if ( prime == 2 ) {
    div = 1;
    return( true );
  }
  if ( ( prime & 1 ) == 0 ) {
    div = 2;
    return( false );
  }

  unsigned int maxNum = (unsigned int)( sqrt( prime ) ) + 1;
  for ( div = 3 ; div < maxNum ; div += 2 )
    if ( prime % div == 0 ) return( false );

  div = 1;
  return( true );
}

/*
  素因数分解

  unsigned int num : 対象の自然数
  map<unsigned int,unsigned int>& mapDiv : 分解した素因数を格納するMap
*/
void intFactor( unsigned int num, map<unsigned int,unsigned int>& mapDiv )
{
  unsigned int div;

  mapDiv.clear();
  while ( ! isPrime( num, div ) ) {
    if ( num < 2 ) break;
    if ( mapDiv.find( div ) != mapDiv.end() )
      mapDiv[div]++;
    else
      mapDiv[div] = 1;
    num /= div;
  }

  if ( mapDiv.find( num ) != mapDiv.end() )
    mapDiv[num]++;
  else
    mapDiv[num] = 1;
}

このプログラムを利用した場合、最大で32ビット(10桁程度)のデータを扱うことができます。この程度ならば、コンピュータを利用すれば瞬時に結果を出力することができます。しかし、扱う数値を数百桁という大きなものにすると、上に示したようなやり方では有効な時間内に答えを求めることはできません。素因数分解のアルゴリズムは他にもいくつか存在するものの、任意の大きな数に対して確実に早く処理をすることができるものはないため、コンピュータを利用したとしても公開鍵を素因数分解して秘密鍵を求めることは事実上不可能なことになります。これが、RSA暗号を安全なものにしている理由となります。

最近の記録として、NTT・ドイツのボン大学・スイスのスイス連邦工科大学ローザンヌ校との共同研究によって2007年5月に1017ビットの合成数が素因数分解されていますが、合成数自体は特殊な型をしており、一般の合成数では700ビット程度の困難さに相当するそうです。以下に、素因数分解の結果を示しておきます。

=
55853666619936291260749204658315944968646527018
488637648010052346319853288374753
x
20758181946442382764570481370359469516293970800
73952098812083870379272909032467938234314388414
48348825340533447691122230281583276965253760914
10189105241993899334109711624358962065972167481
161749004803659735573409253205425523689

現在では、コンピュータ自体の能力が向上したことに加え、コンピュータ・クラスタやグリッド・コンピューティングなどの並列・分散処理技術が発達してきたため、512ビット程度の数であれば素因数分解できてしまいます。そのため、暗号を安全なものにするためには、1024から4096ビット(300から1000桁程度)にすることが推奨されています。

k乗根の計算で利用するφ(pq)は、二つの素数p,qから(p - 1)(q - 1)を計算して求めることができますが、この値をさらに小さくすれば計算時間を短縮することが可能になります。実際、二つの素数の積を法とした場合はφ(pq)の代わりにp - 1とq - 1の最小公倍数を一次方程式の係数として利用することができます。ここで、公倍数とは二つの数に共通の倍数を表わし、その中で最小の値を最小公倍数といいます。例えば、12と16の公倍数は48,96,144...なので、lcm(12,16) = 48になります。

二つの数a,bにおいて、最大公約数gcd(a,b)と最小公倍数(以下lcm(a,b)と略記)の間には以下の関係が成り立ちます。

例えば、gcd(12,16) = 4から lcm(12,16) = 12 x 16 / 4 = 48と計算することが可能です。

それでは、なぜ最小公倍数を利用しても問題がないのかについて考えてみたいと思います。

x ≡ b^u (mod pq) が x^k ≡ b (mod pq) の解になるとき、

x ≡ (x^k)^u ≡ x^ku (mod pq)

が成り立ちます。これは、x^ku - x = x(x^{ku - 1} - 1) がpqで割り切れることを意味しています。pもqも互いに素になるため、これを満たすためには

x(x^{ku - 1} - 1) ≡ 0 (mod p)

x(x^{ku - 1} - 1) ≡ 0 (mod q)

がどちらも成り立てばよいということになります。
両式とも同じかたちをしているので、ここからは法がpの場合についてのみ考えていきたいと思います。まず、xがpと互いに素ではない場合、pが素数であることから必ず p|x となる必要があるため、上式が成り立つことは自明となります。xがpと互いに素である場合は、

x^{ku - 1} - 1 ≡ 0 (mod p)

が成り立つ必要があり、これをフェルマーの小定理と見比べると、(p - 1) | (ku - 1) のときに上式を満たすため、

ku - 1 ≡ 0 (mod p - 1)

を満たせばよいということになります(xがpと互いに素であることに注意してください)。この時 ku - 1はp - 1で割り切ることができればよく、もう一つの式からは ku - 1がq - 1で割り切れればいいことになります。それを満たすためには ku - 1がp - 1とq - 1の最小公倍数 lcm(p - 1,q - 1)で割り切ることができれば十分ということになります。

先の例で利用した素数であるp = 17とq = 19に対して、lcm(p - 1,q - 1) = 144 になります。kが同じ(=5)であれば、暗号化を行った結果は変化せず、次のようになります。

C(82) = 82⁵ ≡ 233 (mod 323)
C(83) = 83⁵ ≡ 87 (mod 323)
C(65) = 82⁵ ≡ 12 (mod 323)

復号化の際、φ(pq) = 288の代わりにlcm(p - 1,q - 1) = 144を使って一次方程式を計算します。

ku - lcm(p - 1,q - 1)v = 5u - 144v = 1

これを解くと、u = 29、v = 1となり、

P(233) = 233²⁹ ≡ 82 (mod 323)
P(87) = 87²⁹ ≡ 83 (mod 323)
P(12) = 12²⁹ ≡ 65 (mod 323)

となるため、確かに lcm(p - 1,q - 1)を利用しても正しく復号化できます。

以下に、RSA暗号化と復号化のテストプログラムを示します。

/*
  RSATest : RSA暗号化・復号化のテスト

  unsigned char p, q : 素数
  unsigned int k : 指数
*/
void RSATest( unsigned char p, unsigned char q, unsigned int k )
{
  int u, v;
  unsigned int n = p * q;
  unsigned int lcd = ( p - 1 ) * ( q - 1 ) / calcGCD( p - 1, q - 1 );

  calcGCD( k, lcd, u, v );
  while ( u < 0 ) u += lcd;

  for ( unsigned int i = 0 ; i < n ; i++ ) {
    unsigned int enc = power( i, k, n );
    unsigned int dec = power( enc, u, n );
    printf( "%d->%d->%d\t%s\n", i, enc, dec, ( i != dec ) ? "Fail" : "Pass" );
  }
}

上記のサンプル・プログラムでは、0からpq - 1までの全ての数に対して暗号化と復号化を行い、入力した数値と復号した結果が一致したかを判定して結果を表示するという単純なものです。中で使用されている関数は全て、今まで示したサンプル・プログラムをそのまま使用しているため、暗号化と復号化処理は非常にコンパクトになっています。処理の流れとして、kとlcd(p - 1とq - 1の最小公倍数)を係数とする一次方程式を解いてから、k乗計算とk乗根計算(処理内容はu乗の計算)を行っています。
べき乗計算ルーチン(power)が、法に16ビット以上の数値を使えないという制約があるため、秘密鍵となる二つの素数は8ビット(char型)しか指定できないという制限があります。当然これでは実用に耐えるようなものにはなり得ませんが、あくまで内容を理解するためのものとして見てください。実際には扱う数値が桁違いに大きいため、通常の数値演算処理は利用できず、多倍長整数の演算処理を行う専用ルーチンを用意する必要があります。

上のサンプルルーチンでは無視していますが、入力数値が0または1の場合、処理結果は常に自分自身となってしまいます。そのまま暗号化した場合、0や1のある場所が判明してしまうため、例えば1Byteずつ処理を行うのであれば、0 = 256、1 = 257とするなどの工夫が必要となります。

今回のサンプル・プログラムのソースをアップロードしておきます。御自由にお使い下さい。

zip形式(RSA.zip)

tar-gzip形式(RSA.tar.gz)

動作確認はVine Linux 4.1上で行いました。特殊なライブラリは使用していないため、どんな環境でもビルド・動作は可能だと思います。

1. 「暗号解読」 サイモン・シン著 (新潮社)
2. 「はじめての数論」 ジョセフ・H・シルヴァーマン著 (ピアソン・エデュケーション)
3. はやわかり RSA
4. Wikipedia

前に戻る

タイトルに戻る