公開鍵暗号
古来より暗号は戦争を契機として発展してきました。戦いの中でより強い暗号が必要とされたということでしょう。第二次世界大戦も例外ではありません。第二次世界大戦中はドイツ軍の機械式暗号機エニグマが大活躍して、連合国側を恐怖に陥れました。エニグマは1918年にドイツで発明され、その後ナチスに採用された暗号機です。タイプライターのような機械で、キーボードを打つと暗号文が出力されます。ナチス軍はコードブックに従って、毎日鍵を変えたので解読するのはなかなか大変だったようです。イギリスは大量の数学者なとを雇い入れて、解読しようと試みました。ここで大活躍したのがチューリングマシンで有名なアラン・チューリングです。チューリングが考案した暗号解読理論でも膨大な計算が必要で、最初は人海戦術で行われていたようです。やがて、Bombeと名付けられた暗号解読機が開発されました。Bombeは後のコンピュータに影響を与えることになります。アラン・チューリングの提唱したチューリングマシンの概念は後のノイマン型コンピュータの理論的な背景となりました。
※現在は サイバー空間が、陸・海・空・宇宙空間に次ぐ、「第五の戦場」と定義され(米国防総省)、この第五の戦場では戦争行為(米国防総省は外国政府からのサイバー攻撃を「戦争行為」と定義しています)、テロ、小競り合いなどが起こっています。そのため、従来にもまして、暗号の強さが求められているといっていいでしょう。
戦後直ぐに半導体が発明され、次いで集積回路も発明されました。半導体技術を使ったコンピュータは猛烈な速度で高性能化していくことになります。コンピュータが高性能化すると、暗号の安全性もそれに伴って向上しました。しかし、従来の共通鍵暗号方式では、鍵を安全に共有する方法がありませんでした。どんなに強力な鍵でも、これを通信相手との間で共有しなくてはならないという従来の共通鍵暗号システムでは、通信の途中で盗まれてしまう可能性を否定できませんでした。
そこで求められたのが共通鍵をネットワーク経由で送り合う必要のない方式です。共通鍵を使わない方式は一般に公開鍵暗号方式(Public Key
Cryptosystem)と呼ばれます。公開鍵暗号の基本的な考え方は1975年にスタンフォード大学のウィットフィールド・ディフィー(Whitfield
Diffie)によって発表されています。
ディフィーのアイデアは鍵を2つ使うという方式です。一つは公開鍵(public key)といいます。「公開」鍵ですから、公開鍵サーバなどに登録して誰でもダウンロードできる状態にしておきます。あるいは、このようなシステムが整わない場合は、通信相手から求められれば、直ぐに公開鍵を送れるというようにしておきます。もう一つは秘密鍵(private
key)です。秘密ですから、誰にも知られないように大切に保管しておかなくてはなりません。公開鍵と秘密鍵はペアになっています。公開鍵で暗号化したものは、ペアになっている秘密鍵でしか開けることができません。また、秘密鍵で暗号化することもできますが、これはペアになっている公開鍵でしか開けることができない、という仕組みを作っておきます。
暗号化する場合は、公開鍵で暗号化します。アリスとボブが通信する場合で考えてみましょう。アリスがボブに暗号文を送るとします。アリスは公開鍵サーバからボブの公開鍵を取り出します、あるいはボブから公開鍵を予め送ってもらいます。
アリスはボブに送る文章(平文)をボブの公開鍵で暗号化します。公開鍵は公開の鍵ですので、アリスでなくても誰でも使えます。つまり、誰でもボブに暗号化文を送ることができます。
この暗号文は鍵をかけるときに使った公開鍵に対応した秘密鍵でしか開けることができません。この鍵を持っているのはボブしかいませんので、ボブにしか解錠できません。秘密鍵を持っている本人にしか読めませんので、安全に通信することができます。
秘密鍵で暗号化することもできます。この場合は、秘密鍵を持っている本人にしか、暗号化できません。解錠は公開鍵を使って行いますので、誰にでもできます。しかし、実際は、誰の秘密鍵で暗号化されたものかを知っている人以外には開けることはできません。従って、この手順は「署名」として利用できます。ネットワークでやり取りされる文書はサインもできませんし、押印もできませんが、公開鍵暗号を使ったこの手順はそれに代わる有力な方法であると考えられています。しかし、ディフィーの示したアイデアはここまでで、どのようにしてこのような仕組みを実現するかについては何も示すことができませんでした。
このディフィーに加えて、マーティン・ヘルマン(Martin E.Hellman)とラルフ・マークル(Ralph C.Merkle)が加わって初めて開発されたのが、鍵を安全に交換する方式でした。この方式は、Diffie-Hellman鍵交換(Diffie-Hellman
Key Exchange)と呼ばれます。これで、共通鍵方式の問題点が解消されることとなりました。しかし、Diffie-Hellman鍵交換方式は、安全に鍵を交換するだけで、暗号化もできなければ、電子署名で使うこともできません。
具体的な公開鍵暗号方式を最初に考案したのがMITのロナルド・リベスト(Ronald Lorin Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Leonard
Max Adleman)の3人です。彼らの発明した暗号方式は3人の頭文字をとってRSA暗号と呼ばれるようになります。
※最初に公開鍵暗号方式が可能であることを発見したのも、最初に公開鍵暗号方式の具体的な手法を発見したのも、最初に安全な鍵交換システムを発見したのも、実は英国政府通信本部(GCHQ)の研究者だったようです。しかし、英国政府がこれを機密扱いしていたため、世間に公表されることはありませんでした。この事実が公表されたのは発見から13年後の1997年のことでした。
公開鍵暗号方式の、公開鍵と秘密鍵を決める手順は、非常に複雑で、整数論の知識が必要となりますので、必要な整数論を説明しながら、順番に説明していくことにします。
素数(prime number)は自然数で、約数が 1 と、自分自身のみであるものです。正の約数が 2 個の自然数と言い換えることもできます。かつては 1 を素数としていたこともありましたが、1 を素数とすると素因数分解の一意性が成り立たなくなってしまいます。例えば、
6 = 2*3 = 1*2*3 = 12*2*3 = ・・・
と無数の素因数分解が可能になります。
更に、1 以外の素数で成り立つ、オイラーのφ関数などが否定されてしまうことになります。
素因数分解の一意性
「2 以上の自然数は、素数の積で表すことができる。その表し方は順序を除けが一意である」
(算術の基本定理) |
素数は小さい順に 2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97、101、103、107、109、・・・と続きます。どこまでも、続くのでしょうか? 素数は無限にあります。素数が無限にあることは既にユークリッドが彼の著書の「原論」の中で証明しています。ユークリッドによる証明は次の通りです。
素数が無数に存在することの証明
(背理法による証明)
素数が有限個しかない(n 個しかない)と仮定し、
i 番目の素数を pi とする。
q = p1p2p3・・・pn + 1
を考える。
q は有限個の自然数の積に 1 を加えた数なので、
自然数である。
ゆえに、q は 素数あるいは
合成数(2以上の素数でない自然数)
である。
q は最大素数pnより大きいので、素数ではない。
従って、q は合成数である。
すなわち、q はいくつかの pi の積である。
すなわち、q をある pi で割った割った余りは 0 となる。
これは、q を pi で割った余りは 1 である
という定義に矛盾する。
|
RSAでは大きな素数を使いますが、素数にはいくらでも大きなものがありそうです。じつは素数は無数にあることは確かなのですが、数が大きくなればなるほど、その割合は小さくなります。100未満(2桁)には素数は25個あります。最初の2桁では素数の密度は1/4です。100桁の数字では、素数の密度は1/23です。1000桁になると、素数の密度は1/230となります。
素因数分解の難しさを利用した暗号アルゴリズムでは、何とかして大きな素数を探さなくてはなりません。
2つの整数 a、 b を p で割ったときの余りが等しい時、
a ≡ b (mod p)と表し、「a と b は p を法として合同であるといいます。
この式は合同式(Modular Arithmetic)といいます。
a を b で割ったときの余りが p とも考えられます。
あるいは、a を p で割ったときの余りと、b を p で割ったときの余りが同じと考えても構いません。
あるいは、a と b の差分が p の倍数とも考えられます。
例をあげると次の通りです。
1 ≡ 10 (mod 3)
7 ≡ 37 (mod 10)
5 ≡ 53 (mod 12)
13 ≡ 1234 (mod 111) |
法が等しい合同式は、通常の方程式と同様の性質を持ちます。
a ≡ b (mod n)、c ≡ d (mod n)のとき、次の式が成り立ちます。
a + c ≡ b + d (mod n)
a - c ≡ b - d (mod n)
ac ≡ bd (mod n)
例
16 ≡ 21 (mod 5)、7 ≡ 12 (mod 5)のとき
16 + 7 ≡ 21 + 12 (mod 5)
16*7 ≡ 21*12 (mod 5)
は確かに成りたつ。 |
任意の整数 k に対して k ≡ k (mod n) なので、
a ≡ b (mod n)のとき、次の式が成り立ちます。
a + k ≡ b + k (mod n)
a - k ≡ b - k (mod n)
ka ≡ kb (mod n) |
更に ac ≡ bd (mod n)において、a = c、 b = d ならば
a ^ 2 ≡ b ^ 2 (mod n)となり、
この操作を繰り返すことによって、
任意の自然数 m に対しては 次の式が成り立ちます。
a ≡ b (mod n)のとき、
任意の自然数 m に対して
a ^ m = b ^ m (mod n)
例
16 ≡ 21 (mod 5)のとき
16 ^ 2 ≡ 21 ^ 2 (mod 5)
16 ^ 3 ≡ 21 ^ 3 (mod 5)
がそれぞれ成り立つ。 |
※a ^ n は a の n 乗を表すことにします。
合同式では普通は、割り算は成り立ちません。
a ≡ b (mod n)が成り立つからと言って、
a/k ≡ b/k (mod n)が成り立つとは限りません。
例えば、40 ≡ 30 (mod 10)ですが、
これを2で割ったとき 20 ≡ 15 (mod 10)は成り立ちません。
では、どんな時に成り立つのでしょうか。少し考えてみましょう。
am ≡ bm (mod n)のとき、
am - bm = kn を満たす整数 k が存在します。
この式は、a - b = kn/m と変形することができます。
左辺は整数ですから、右辺も必ず整数になるはずです。
従って、kn は m で割り切ることができなくてはなりません。
ここで、 m と n が互いに素なら、
k は m で割り切れなくてはなりません。
この時、a - b = ( k/m ) n となりますので、
a - b ≡ 0 (mod n)となります。
従って、次のことが言えることになります。
m と n が互いに素の時
ma ≡ mb (mod n)なら、
a ≡ b (mod n) |
GCD(Greatest Common Divisor)は最大公約数を表します。
2つの数を m と n と表すとき、
この2つの数の最大公約数はGCD(m, n)と表します。
GCD(m, n) = 1
は m と n の最大公約数が 1 であることを表します。
これは、m と n が互いの素であることを意味します。
※「互いに素」(co-prime、relatively prime、mutually prime)
とは、2つの整数が 1 と -1 以外に公約数を持たない
場合の2つの数の関係です。
そこで、上の除数の定理は次のように言い換えることができます。
GCD(m, n) = 1 のとき
ma ≡ mb (mod n)なら、
a ≡ b (mod n) |
普通の割り算は a ÷ b = a * (1/b) という関係になります。
割る数の逆数をかければいいということですね。
ここで、逆数とは b * (1/b) = 1 という関係を満たしている数です。
mod n での除算も逆数をかければ、いいのでしょうか?
その前に、mod n での除算の場合は、逆数が常にあるとは限りません。
bx ≡ 1 (mod n) となる x を求めて、それを a をかければいいですね。
この x を b の mod n での逆元といい、b ^ (-1) と書くことにします。
a ÷ b = a * b ^ (-1)
少し計算例を示します。
a = 8、 b = 3 (mod 10)での除法
① 3 の mod 10 での逆元を求める。
3*1 ≡ 3
3*2 ≡ 6
3*3 ≡ 9
3*4 ≡ 12 ≡ 2
3*5 ≡ 15 ≡ 5
3*6 ≡ 18 ≡ 8
3*7 ≡ 21 ≡ 1
3 の mod 10 での逆元は 7
② 3 の mod 10 での逆元を使って除算を実行
8 ÷ 3 ≡ 8*7 ≡ 56 ≡ 6 (mod 10)
|
上の例では、偶然 3x ≡ 1 (mod 10) を満たす
x = 7 が存在しましたが、
逆元はいつでも存在するのでしょうか?
b = 3、 mod 6 で試してみましょう。
b = 3、 mod 6 で確認
3*1 ≡ 3
3*2 ≡ 6 ≡ 0
3*3 ≡ 9 ≡ 3
3*4 ≡ 12 ≡ 0
・・・
結果は3 と 0 の繰り返しで、3 の mod 6 での逆元は存在しないようだ。 |
逆元が存在するかどうかについては、次のような可逆性の定理があります。
可逆性定理
b ∈ Z, n ∈ N (Z:整数, N:自然数)
b の mod n の逆元が存在する ⇔ GCD(b, n) = 1 |
可逆性の定理を証明するにはユークリッドの互除法が必要ですので、
次にユークリッドの互除法について説明します。
ユークリッドの互除法(Euclidean Algorithm)は最大公約数を最も簡単に求める方法です。
2つの数を"a"と"b"と表すとき、
この2つの数の最大公約数はGCD(a, b)と表します。
また、a>b>0 として a を b で割ったときの余りを r ≧ 0 とします。
この時、GCD(a, b) = GCD(b, r) が成り立ちます。
これについて証明します。
a を b で割ったときの商を q とすると、
a = qb + r ・・・ ①
あるいは移項して r = a - qb ・・・ ②
簡単のために GCD(a, b) = c とする。
c は a と b を割り切るので、
②の右式も c で割り切れる。
従って、r も c で割り切れる。
c は、b と r の公約数となるので、
c ≦ GCD(b, r) ・・・ ③となる。
逆にGCD(b, r) = c' とする。
①式からc' は a を割り切ることが分かる。
従って、c' は a と b の公約数になるので、
c' ≦ GCD(a, b) = c となる。
③より、c ≦ GCD(b, r) = c' なので、
c = c' となる。
以上より、
GCD(a, b) = GCD(b, r)
となることが分る。 |
以上のことを踏まえてGCD(12707, 12319)の計算をしてみましょう。
12707 = 1*12319 + 388 より
GCD(12707, 12319) = GCD(12319, 388)
12319 = 31*388 + 291 より
GCD(12319, 388) = GCD(388, 291)
388 = 1*291 + 97 より
GCD(388, 291) = GCD(291, 97)
291 = 3*97 より、GCD(291, 97) = 97
以上よりGCD(12707, 12319) = 97
|
GCD(a, b)(a>b)の計算で、互除法の計算回数は b の桁数の5倍以下です。例えば、100桁の数の最大公約数も500回以下の計算で求まります。
「GCD(b, n) = 1 のとき、b の mod n での逆元が存在する」
という可逆性定理の証明
GCD(b, n) = 1 のとき、
ユークリッドの互除法により、
bx + ny = 1 となる x, y ∈ Z が存在する。
bx - 1 = nk (k ∈ Z)
bx ≡ 1 (mod n)
これは b の mod n での逆元が存在することを示す。 |
前の例では、逆元を求める際にいろいろの値を当てはめてbx ≡ 1 となるような x を探しましたが、大きな数になると、大変です。この場合もユークリッドの互除法が大きな力を発揮します。
bx ≡ 1(mod n)となる x が存在する ⇔ bx - 1 = nk
∴ bx - nk = 1 となる n, kが存在する。
∴ bx + ny = 1 を満たす、x, y ∈ Zを見つければよい。 |
それでは、ユークリッドの互除法を使って具体的に、逆元を求めてみましょう。
b = 5, n = 288 で、b の逆元を求める。
GCD(5, 288) = 1 より b(= 5 )は逆元を持つ(可逆性定理)
5x ≡ 1 (mod 288)
5x - 1 = 288k
5x + 288y = 1 ・・・ ①
①を満たす x, y ∈ Z を求める。
288 = 5 * 57 + 3
5 = 3 * 1 + 2
3 = 2 * 1 + 1
1 = 3-2 * 1
1 = 3 - (5 - 3*1)*1
1 = 3*2 - 5
1 = ( 288 - 5*57 )*2 - 5
1 = 5*(-115) + 288*2
よって求める x, y は (x, y) = ( -115, 2)
- 115 ≡ 173 (mod 288)より、x = 173
よって、5のmod 288での逆元は 173 となる。
|
繰り返しになりますが、後の説明で必要となりますので、
b = 1241 n = 2184 で、b の逆元を求めておきます。
b = 1241 n = 2184 で、b の逆元を求める。
GCD(1241, 2184) = 1 より、b は逆元を持つ。
1241x = 1 (mod 2184)
1241x - 1 = 2184k
1241x + 2184y = 1 ・・・①
を満たす x, y ∈ Z を求める。
2184 = 1241*1 + 943
1241 = 943*1 + 298
943 = 298*3 + 49
298 = 49*6 + 4
49 = 4*12 + 1 ・・・(A)
以上より
943 = 2184 - 1241*1
298 = 1241 - 943*1
49 = 943 - 298*3
4 = 298 - 49*6
1 = 49 - 4*12
が得られる。
これらの左辺を(A)に次々に代入していくと、
次のようになる。
初めに4を代入する。
49 - (298 - 49*6)*12 = 1
49*73 - 298*12 = 1
次に49を代入する。
(943 - 298*3)*73 - 298*12 = 1
943*73 - 298*231 = 1
次に298を代入する。
943*73 - (1241 - 943)*231 = 1
943*304 - 1241*231 = 1
次に943を代入する。
(2184 - 1241)*304 - 1241*231 = 1
2184*304 - 1241*535 = 1
従って、法を2184とした時の、1241の逆元は-535となる。
-535 ≡ 1649 mod 2184
なので、
法を2184とした時の、1241の逆元は1649
となる。
|
以上のことを定式化すると次のようになります。これは拡張ユークリッド互除法などと呼ばれます。
拡張ユークリッド互除法
x, y ∈ N (N:自然数)として、 c = GCD(x, y)とする。
この時
ax + by = c
となる整数 a、 b が存在する。そして、この a、 bは
実際に計算することができる。 |
上の手計算の場合は、次の
2184 = 1241*1 + 943・・・(ⅰ)
1241 = 943*1 + 298・・・(ⅱ)
943 = 298*3 + 49・・・(ⅲ)
298 = 49*6 + 4・・・(ⅳ)
49 = 4*12 + 1・・・(ⅴ)
(ⅰ)~(ⅴ)の互除法の計算の結果をどこかに保存しておいて、最後の計算式(ⅴ)から次々に代入していくという方法をとっています。手で計算する場合はこれで何の不都合もないのですが、実用上の計算は、大きな数字をコンピュータで計算します。
扱うのが非常に大きな数ですので、互除法の計算も何度も行う必要があり、それをどこかに保存しておかなくてはなりません。これはある程度のメモリを必要とします。しかも、計算を何度行うかは予測がつきませんので、
変数をいくつ用意しておけばいいか、予測がつきませんし、用意しておくメモリ空間も予測がつきません。
そこで、実際はもっと巧妙な方法が採用されています。それは互除法の計算結果を上から、つまり(ⅰ)から順に(ⅴ)まで、代入する方法です。この方法を使うと、もう皆さんもお分かりだと思いますが、互除法の計算結果を取っておく必要がありません。変数もその都度とっかえ、ひっかえで使いまわすことができます。しかし、この方法を手計算で辿ると、かえって難しくなります。
では、先ほどと同じ問題をこの方法でやってみましょう。
(ⅰ)を計算し、次のように整理する。
934 = -1*1241 + 1*2184・・・①
(ⅱ)を計算し 943 に代入する。
1241 ‐ 298 = -1*1241 + 1*2184
- 298 = -2*1241 + 1*2184・・・②
(ⅲ)を計算し、②の両辺を3倍する。
- 298*3 = - 6*1241 + 3*2184
(ⅲ)を使って、次のように変形する。
-943 + 49 = -6*1241 + 3*2184
①を使って、整理すると、
1*1241 - 1*2184 + 49 = -6*1241 + 3*2184
49 = -7*1241 + 4*2184・・・③
(ⅳ)を計算し、③の両辺を6倍する。
6*49 = -42*1241 + 24*2184
(ⅳ)を使って、次のように変形する。
298 - 4 = -42*1241 + 24*2184
②の298を代入すると、
2*1241 - 1*2184 - 4 = -42*1241 + 24*2184
これを整理して、
-4 = -44*1241 + 25*2184・・・④
(ⅴ)を計算し、④の両辺を12倍する。
-12*4 = -528*1241 + 300*2184
(ⅴ)を使って、次のように変形する。
-49 + 1 = -528*1241 + 300*2184
③を代入すると、
7*1241 - 4*2184 + 1 = -528*1241 + 300*2184
整理すると
1 = -535*1241 + 304*2184
となる。
従って、法を2184とした時の、1241の逆元は-535となる。
-535 ≡ 1649 mod 2184
なので、
法を2184とした時の、1241の逆元は1649
となる。
|
①、②、③、④などはまた後で利用しますので、保存しておかなくてはなりませんが、(ⅰ)~(ⅴ)の計算は、計算して、利用したら直ぐに要らなくなりますので、取っておく必要はありません。これでだいぶメモリの節約になります。
Z を全ての整数から成る集合、Zn を mod n の整数からなる集合とします。
例:Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。
Zn* は n と互いに素である mod n の整数から成る集合とします。
Z10* = {1, 3, 7, 9}
※GCD(0, 10) = 10 なので、0は10と互いに素ではありません。
Z10* の乗算表 |
|
1 |
3 |
7 |
9 |
1 |
1 |
3 |
7 |
9 |
3 |
3 |
9 |
1 |
7 |
7 |
7 |
1 |
9 |
3 |
9 |
9 |
7 |
3 |
1 |
Z10* の任意の要素を掛け合わせると、答えは Z10* の要素となります。
しかも、各行各列にZ10* の全ての要素が繰り返しなしに現れます。
これは、mod 10 の場合の偶然ではなく、mod n について言えることです。
1つだけでは不安ですので、Z15* についても確認してみましょう。
Z15* = {1, 2, 4, 7, 8, 11, 13, 14}
Z15* の乗算表 |
|
1 |
2 |
4 |
7 |
8 |
11 |
13 |
14 |
1 |
1 |
2 |
4 |
7 |
8 |
11 |
13 |
14 |
2 |
2 |
4 |
8 |
14 |
1 |
7 |
11 |
13 |
4 |
4 |
8 |
1 |
13 |
2 |
14 |
7 |
11 |
7 |
7 |
14 |
13 |
4 |
11 |
2 |
1 |
8 |
8 |
8 |
1 |
2 |
11 |
4 |
13 |
14 |
7 |
11 |
11 |
7 |
14 |
2 |
13 |
1 |
8 |
4 |
13 |
13 |
11 |
7 |
1 |
14 |
8 |
4 |
2 |
14 |
14 |
13 |
11 |
8 |
7 |
4 |
2 |
1 |
Z15* の要素同士をかけると、その答えがまた、Z15* の要素となっています。
これは、Zn* について言えます。
これを 「Zn* は mod n の乗法について閉じている」といいます。
「Zn* が mod n の乗法について閉じている」とは、
もし a と b が Zn* に含まれているとすれば、
その積である ab mod n も Zn* の要素であることを意味します。
p を任意の素数、a を p と互いに素な整数としたとき
a^(p - 1) ≡ 1 (mod p)
a |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
a^2 |
1 |
4 |
9 |
16 |
25 |
36 |
49 |
64 |
81 |
a^2
(mod 3) |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
RSAを解読する際にべき乗の合同式の計算が出てきます。通常、繰り返し自乗法という方法で解きますが、フェルマーの小定理が使えれば(pが任意の素数で、aとpが互いに素)、簡単に計算することができます。
例えば、7^10001 (mod 11) を計算する場合、
フェルマーの小定理 7^10 ≡ 1 (mod 11) を利用すると次のようになります。
7^10001 ≡ 7*(7^10)^1000
≡ 7*1^1000 ≡ 7 (mod 11)
オイラーはフェルマーの小定理を研究するうちに、フェルマーの小定理を一般化する定理を発見しました。オイラーの定理を説明するにはオイラー関数の説明が必要ですので、初めのオイラー関数について説明します。オイラー関数はオイラーの位数関数、あるいは単に位数関数(totient
function)などとも呼ばれます。
オイラー関数φ(n)は n 未満の数のうち、n と互いに素である数
の個数を表す。
|
Z10* = {1, 3, 7, 9}なので、φ(10) = 4
Z15* = {1, 2, 4, 7, 8, 11, 13, 14}なので、φ(15) = 8
となります。
n が素数ならφ(n) = {1, 2, ・・・ n-1} となりますので、φ(n) = n - 1
となります。
a と n が互いに素な関係にあるとき、
a^(φ(n)) ≡ 1 (mod n) |
オイラーの定理の使用例
n = 15 のとき、15以下の互いに素な自然数は{1、2、4、7、8、11、13、14}で8個あります。
従って、φ(15) ≡ 8
a^φ(15) ≡ a^8 mod 15
の値を考えると次のようになります。
a |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
a^8 |
1 |
256 |
6561 |
65536 |
390625 |
1679616 |
5764801 |
16777216 |
43046721 |
a^8
(mod 15) |
1 |
1 |
6 |
1 |
10 |
6 |
1 |
1 |
6 |
15 = 5 * 3 ですから、3 と 5 の倍数の列は、1以外の数になっていますが、15 と互いに素な数の列では、1 となっています。
n が素数 p の場合(n = p)、
φ(p) = p - 1
であり、
a と p が互いに素ということは
p が a を割り切らないと同じことですから
上の定理で n = p(素数)の場合が、
フェルマーの小定理ということになります。
1 から n までの整数のうち、n と互いに素な数を
r1、r2、・・・rφ(n)
と表します。
更にこれらの数に a をかけたもの
ar1、ar2、・・・arφ(n)
を考えます。
a と ri を n と互いに素だとすると、ari と n も互いに素となります。
更に ar1、ar2、・・・arφ(n) は n を法として合同ではありません。
n と互いに素となる数は、r1、r2、・・・rφ(n) のいずれか1つと合同になりますので、
ar1、ar2、・・・arφ(n) を適当に順序を入れ替えたものが、
r1、r2、・・・rφ(n) と合同になります。
従って、それらを全て掛け合わせたものも合同になります。
従って、ar1・ar2・・・arφ(n) ≡ r1・r2・・・rφ(n) mod n
が成り立ちます。
左辺は aφ(n)・r1・r2・・・rφ(n) となりますので、
両辺に r1・r2・・・rφ(n) の n を法とする逆元を掛けると、
aφ(n) ≡ 1 (mod n)
となります。
n = p^a (pは素数、a>1) のとき φ(n)はどうなるでしょうか。
p^a と互いに素でない数は、
p、p^2、p^3、・・・、p^(a - 1) のようにp個毎に現れるので、
(p^a)/p = p^(a - 1)
従って、p^a と互いに素な数は p^a - p^(a - 1) = (p - 1)・p^(a - 1)
従って、φ(p^a) = (p - 1)・p^(a - 1)
となります。
もし、n が2つの異なる素数 p と q の積なら φ(n) = (p - 1)(q - 1)となります。
これは、次のように証明できます。
n = pq (p、q が素数)のとき、φ(n) = (p - 1)(q - 1)
{0, 1, 2, 3, ・・・ n - 1}には pq 個の数があり、
ここから p の倍数と、q の倍数を除く
p の倍数は、p, 2p, 3p,・・・ (q - 1)p, qp の q 個
q の倍数は、q, 2q, 3q,・・・ (p - 1)q, pq の p 個
従って、pq 未満の数の中には pq と互いに素でない数が(p + q - 1)個ある。
pq がどちらにも含まれているので、重複しないように -1 する。
従って、φ(pq) = pq - (p + q -1) = (p - 1)(q - 1)となる。
|
RSAでは、p と q が互いに素で、 n = pq の形が使われます。
p と q が互いに素で、 n = pq のとき、
中国余剰定理によると
φ(pq) = φ(p)φ(q)
オイラーの定理が使える場合にも、べき乗の合同式の計算を簡単にすることができます。
方法は次の通りです。
計算例
5^4 = 625
φ(5^4) = 5^4 - 5^3 = 625 - 125 = 500
従って、φ(625) = 500
97^12345 ≡ 97^345 * ((97^500)^24) ≡ 97^345
(∵オイラーの定理より 97^500 ≡ 97^φ(625) ≡ 1 (mod 625))
ここまで来たら後は、繰り返し自乗法で求めます。
97^345
≡ (97^256)*(97^64)*(97^16)*(97^8)*(97^1)
≡ 357 (mod 625)
中国剰余定理(二元の場合)
n1 と n2 が互いに素なとき
x ≡ a1 mod n1
x ≡ a2 mod n2
を満たす x が、
0以上、n1n2未満の範囲に(つまり、法n1n2で)唯1つ存在する。
|
例題:
3 で割って 2 余り、 5 で割って 4 余る 15 (= 3*5) 未満の非負整数 n を求めなさい。
解は n = 14 のみです。
解が存在して、しかもただ1つです。
上の例題と回答を一般化したのが中国剰余定理(Chinese Remainder)です。
■ 中国剰余定理の証明(解の唯一性)
題意の連立方程式の解が2つあると仮定し、それを x, y とおくと、
x ≡ a1 ≡ y mod n1
x ≡ a2 ≡ y mod n2
より、 x - y は n1 の倍数であり、 n2 の倍数でもある。
n1 と n2 が互いに素なので、
x - y は n1n2 の倍数である。
ところが x, y は共に n1n2 未満の非負整数なので、 x - y = 0
つまり、 x = y となり、矛盾している。
よって、解が存在する場合には1つだけ存在する。 |
■中国剰余定理の証明(解の存在性)
連立方程式に解が存在することの証明
n1 と n2 は互いに素なので、
n1x + n2y = 1 を満たす整数 x, yが存在する。
※ベズーの定理
よって、n2y ≡ 1 mod n1
n1x ≡ 1 mod n2
よって、x' =a1n2y +a2n1x
とおくと、
x' ≡ a1 mod n1
x' ≡ a2 mod n2
となり、x'は題意の連立合同式を満たす。
n1n2 未満の非負整数の解(つまり、法 n1n2で)
x を得るためには x を
「x' を n1n2 で割ったあまり」とすればよい。
|
上には変数が2つの場合について説明しましたが、中国剰余定理はこれを一般化した場合にも成立することが分かっています。一般化すると次のようになります。
中国剰余定理(一般化した場合)
n1、 n2、・・・nk が互いに素なとき
x ≡ a1 mod n1
x ≡ a2 mod n2
・・・
x ≡ ak mod nk
を満たす x が、
0以上、n1n2・・・nk未満の範囲に
(つまり、法n1n2・・・nkで)
唯1つ存在する。 |
中国剰余定理は別の言い方をすれば、数には2つの表記法があるということです。これらの表記は同じ数を定義しているという意味で同値であり、ある表記から別の表記に変換することは簡単です。
標準的表記は x mod n 1n 2・・・n k (全ての n i は互いに素) で、
分解された表記は
x 1 mod n 1、 x 2 mod n 2、・・・ x k mod n k
となります。
ある数 x は n j で割って余りを求めれば
mod n j を計算できるので、
標準的な表記から分解された表記には簡単に変換できます。
それでは中国剰余定理を使って問題を解いてみたいと思います。
x = 2 mod 3・・・①
x = 3 mod 5・・・②
x = 2 mod 7・・・③
のそれぞれの式を同時に満たすxを求めよ。
①より x = 3i + 2 と表すことができる。
これを②に代入すると、
3i + 2 = 3 mod 5
となり、両辺から 2 を引くと
3i = 1 mod 5・・・④
を得る。
④*2より
6i = 5i + i = i = 2 mod 5
i = 2 mod 5
従って、i = 5j + 2
と表すことができる。
①より x = 3i + 2 mod3 なので、
x = 15j + 8 となる。
これを③に代入すると、
15j + 8 = 2 mod 7
となる。
両辺から 8 を引くと
15j = -6 mod 7
15j = 14j + j だから、
j = -6 mod 7
j = 1 mod 7
従って、 j = 7k + 1
と表すことができる。
x = 15j + 8
だから
x =105k + 15 + 8 = 105k + 23
従って、x = 23 mod 105
これが求める解となる。
|
RSAでは大きな素数 p と q を選んで、これから公開鍵を作り、この公開鍵から逆元の計算をして、秘密鍵を求めています。鍵を生成する時には、素数判定(素数かどうかの判定)が必要となります。一般に厳密な素数判定には時間がかかります。通常使われているのは p と q ともに1024ビットの素数です。この素数をどうやって効率的に探すかが重要になります。
p の平方根以下の全ての数で p を割っていくという素朴な方法がありますが、これだと素数の候補を1つ調べるにも宇宙の寿命ほどの時間がかかってしまいます。100桁以上もある大きな数を絶対に素数であると判定する方法はまだ見つかっていません。ただ、おそらく素数ではないかと判定する方法はあります。それはオイラーの定理を使う方法です。
n と互いに素である数 a には
aφ(n) = 1 mod n
が成立します。
n が素数であれば、フェルマの小定理が成り立ち
an-1 = 1 mod n
(n が素数で 0<a<nなら)
ところが n が素数でなくともこの式が成立することがあります。
素数でないのにもかかわらず、全ての a に対して
an-1 = 1 mod n
を満たしてしまう数 n (Carmichael numbers、カーマイケル数、絶対擬素数)は、無作為に選んだ100桁程度の数では1/1013程度の確率で見つかっています。このように低い確率ですが、フェルマの小定理を満たしている数を誤って素数と判定してしまう可能性はあります。このような間違いを犯すと、①RSAが失敗し、自分宛のメッセージを復元できない、とか ②期待しているよりも少ない計算量で、誰かが復号鍵を見つけてしまう可能性があります。
カーマイケル数は余りに稀なので、これを誤って素数として採択してしまう可能性は極めて低いといっていいと思いますが、数学者は素数の判定を強化し、素数でないもの(カーマイケル数すら)発見するものを作り出しました。発見の確率も高く、追加の計算量もそれほど多くはなりません。例えば、ミラーラビン素数判定法(Miller-Rabin
primality test)は基本的にはフェルマの小定理を使っていますが、アルゴリズムのステップの間に丁寧に n が素数であるかどうかの確認のためのステップを挿入しています。どの程度の厳密さで確認作業を挿入するかは、どれだけ間違いの許されないアプリケーションであるかによっています。
とりあえず、大きな素数は探せそうです。それでは、この大きな素数を使ったRSAのアルゴリズムについて説明します。
RSAアルゴリズムの手順は次の通りです。
RSA の手順
鍵ペア(公開鍵と秘密鍵)を作成し、公開鍵を公開する
① 2つの大きな素数 p と q を選択する。
② n = pq と φ(n) = (p - 1)(q - 1)を計算する。
この n を係数と呼ぶ。
③ GCD(e, φ(n)) = 1 の関係を持つ e (公開指数)を選択する。
この公開指数と係数 n が公開鍵(e, n) となる。
④ 1 = de mod φ(n) となる d (秘密指数)を計算する。
この秘密指数と係数 n が秘密鍵(d, n)となる。
⑤ 公開鍵(e, n)を公開する。
p, q, d は誰にも知られないようにしておく。 |
RSAの手順を具体例で示すと、次のようになります。
RSAの計算手順
(p, q) = (43, 53) とすると、pq = 2279 となる。
(p - 1)(q - 1) = 2184 なので、n = 2279, φ(n) = 2184
GCD(e, φ(n)) = 1 の条件を満たす e を探す。
1241 はこの条件を満たす。
よって(e, n) = (1241, 2279)を公開鍵とする。
1 = de mod φ(n) を満たす d を計算する。
1 = d*1241 mod 2184
2184を法としたときの 1241 の逆元を計算する。
ユークリッドの互除法によると、d = 1649 となる。
確認: 1241*1649 = 2046409 ≡ 1 (mod 2184)
|
以上より、公開鍵(n, e) = (2279, 1241)
秘密鍵(n, d) = (2279、1649)となりました。
(p, q, d) は秘密にしておかなくてはなりません。
暗号化と復号
平文をM、暗号文をCとすると、M < n であれば、
以下の関係が必ず成り立つ。
(暗号化)・・・ M ^ e = C (mod n)
(復号)・・・ C ^ d = M (mod n)
C ^ d = (M ^ e) ^ d = M ^ (de)
ここで、de = 1 の関係にあるから、
M ^ (de) = M ^ 1 = M
となって、元の平文のMが求められた。 |
以上のことを元にしてアリスからボブに
公開鍵暗号によるメッセージを送信してみたいと思います。
ここでは簡単のために"cat"という単語を、アリスからボブに送りたいと思います。
cat という文字列を26進法を使って暗号化してみましょう。
cat = 2*262 + 0*26 + 19 = 1371
※アルファベットを順に a = 0、 b = 1, c = 3, ・・・と割り当てています。
1371 よりも2つの積が大きくなるものとして、43 と 53 を選びます。
2279 = 43 * 53
2279 は 公開して、43 と 53 は秘密にします。
43 と 53 は共に素数なので、互いに素です。
φ(2279) = φ(43)*φ(53) = 42*52 = 2184
次に 2184 と互いに素となる数を見つけます。
これを 1241 とします。
2184 を法として、 1241 の逆元を求めると、1649 となります。
公開鍵は法2279で、1241です。
秘密鍵は法2279で、1649です。
アリスからボブへのメッセージ送信は次のようになります。
ボブはアリスに公開鍵を教えます。
「僕のところにメッセージを送るときは、
1241乗して、2279 を法として考えた数字
(つまり、2279で割算したときの余りの数字)
を送ってください」
と伝えます。
アリスは平文 1371 を公開鍵 1241 を使って、法 2279 で暗号化します。
13711241 = 2003 mod 2279
アリスはボブに暗号文「2003」を送ります。
復号は 秘密鍵1649 を使います。
2003^1649 = (1371^1241)^1649 mod 2279
1241 と 1649 は 2184 を法として、逆数なので
1241 * 1649 ≡ 1 mod 2184
1241 * 1649 = 937 * 2184 + 1
2279 は2つの素数の掛け算の結果得られた数なので、1371とは互いに素です。
従って、オイラーの定理より 1371^φ(2279) = 1 mod 2279
φ(2279) = φ(43)φ(53) = 42*52 = 2184
13712184 = 1 mod 2279
以上より、
(1371^1241)^1649 = 1371^(2184*937 + 1)
= (1^937)*1371 = 1371 (mod 2279)
と復号できました。
(受信した信号を暗号鍵を使って、1649 乗し、公開鍵 2279 で割って
余りを求めればいいということになります。)
受信した数を秘密鍵の分だけ累乗してから、
公開鍵で割るのは時間がかかりそうですが、
繰り返し自乗法(Exponentiation by squaring)という方法が使われます。
a ^ k (mod n)を求めるとき、まず k を2のべき乗の和として求めます。
k = Σ(2^i)(ui) = u0 + 2u1 + (2^2)u2 + ・・・
で表します。
これを k の2進展開といいます。
この式で、uiは 0 または 1 となります。
a^k = a^(u0 + 2u1 + 4u2 + ・・・)
= a^u0 * a^(2u1) * a^(4u2)・・・
= a^u0 * (a^2)^u1 * (a^4)^u2・・・
と表すことができます。
a^2k を繰り返し自乗法で計算すると、
a ≡ A (mod n) のとき a^2 ≡ A^2 (mod 2)
になることを利用すると、
以下のように処理することができます。
a^1 ≡ A0 (mod n)とすると、
a^2 ≡ (a^1)^2 ≡ A0^2 ≡ A1 (mod n)
a^4 ≡ (a^2)^2 ≡ A1^2 ≡ A2 (mod n)
a^8 ≡ (a^4)^2 ≡ A2^2 ≡ A3 (mod n) |
この置き換えによって大きな値を扱う必要がなくなります。
Aを使うと、
a^k = A 0^u 0・A 1^u 1・A 2^u 2・・・
と計算できます。
例として 2^4099 (mod 100) を計算してみましょう。
4099 = 4096 + 2 + 1
となり、繰り返し自乗法により次のようになります。
2^1 ≡ 2 (mod 100)
2^2 ≡ (2^1)^2 ≡ 2^2 ≡ 4 (mod 100)
2^4 ≡ (2^2)^2 ≡ 4^2 ≡ 16 (mod 100)
2^8 ≡ (2^4)^2 ≡ 16^2 ≡ 56 (mod 100)
2^16 ≡ (2^8)^2 ≡ 56^2 ≡ 36 (mod 100)
2^32 ≡ (2^16)^2 ≡ 36^2 ≡ 96 (mod 100)
2^64 ≡ (2^32)^2 ≡ 96^2 ≡ 16 (mod 100)
2^128 ≡ (2^64)^2 ≡ 16^2 ≡ 56 (mod 100)
2^256 ≡ (2^128)^2 ≡ 56^2 ≡ 36 (mod 100)
2^512 ≡ (2^256)^2 ≡ 36^2 ≡ 96 (mod 100)
2^1024 ≡ (2^512)^2 ≡ 96^2 ≡ 16 (mod 100)
2^2048 ≡ (2^1024)^2 ≡ 16^2 ≡ 56 (mod 100)
2^4096 ≡ (2^2048)^2 ≡ 56^2 ≡ 36 (mod 100)
と計算できるので、
2^4099 = 2^4096*2^2*2^1 = 36*4*2 = 44*2 = 88 (mod 100)
それでは、具体的に法2279のときの 2003^1649
を計算してみたいと思います。
1649を2のべき乗の和の形に直すと
1649 = 256*6 + 64*1 + 32*1 + 16*1 + 1
従って、
2003^1649 = 2003^(256*6+64*1+32*1+16*1+1)
2003^1 = 2003 mod 2279
2003^2 = 2003*2003 = 4012009 = 969 mod 2279
2003^4 = 969*969 = 938961 = 13 mod 2279
2003^8 = 13*13 = 169 mod 2279
2003^16 = 169*169 = 28561 = 1213 mod 2279
2003^32 = 1213*1213 = 1471369 = 1414 mod 2279
2003^64 = 1414*1414 = 1999369 = 713 mod 2279
2003^128 = 713*713 = 508369 = 152 mod 2279
2003^256 = 152*152 = 23104 = 314 mod 2279
以上より
2003^1649 = 2003^(256*6+64*1+32*1+16*1+1)
=314^6*713^1*1414^1*1213^1*2003
ここで
314^2 = 98596 = 599 mod 2279
314^4 = 599*599 = 358801 = 998 mod 2279
314^6 = 599*998 = 597802 = 704 mod 2279
従って、
2003^1649 = 2003^(256*6+64*1+32*1+16*1+1)
= 704*713*1414*1213*2003
= 1371 mod 2279
|
受信した数を秘密鍵の数だけ累乗してから公開鍵で割るのは時間がかかりそうな気もしますが、コンピュータを使えば、意外に簡単にできそうだということが分かっていただけたと思います。
予めこの秘密鍵(1649)を知らない場合は、公開鍵の法として使われている2279を素因数分解して(通常、この公開鍵の法は200桁程度の非常の大きな数が使われていますので、素因数分解が困難)、素因数分解した数からオイラー関数の値2184を求めます。(素因数分解さえできればこれは簡単)
1241は公開されていますので、2184を法として241の逆元を求めます(素因数分解さえできればこれも簡単)。
公開鍵の法を素因数分解するのは時間のかかる作業になりますが、素因数分解を簡単に求める方法は今までにユークリッドの互除法以外に見つかっていません。この大きな数の素因数分解の困難さがRSA暗号の強さの秘密ということになります。
しかし、NTTが2010年1月8日、768ビット(10進表記だと232桁の整数)の素因数分解に成功しています。現在広く使われているRSA暗号は1024ビットの素因数分解を利用していますので、今回の成功により、1024ビットのRSA暗号が近い将来破られる可能性が示されました。
RSAは難しい数学の理論を使っていますので、計算量が膨大になり、処理に時間がかかるのが一般的です。平文が長くなればそれだけ処理時間も余計かかります。そこで、共通鍵をRSAで暗号化して送信し、通信の双方で共通鍵を持った段階で、それ以降は共通鍵を使って暗号化通信を行う方式(ハイブリッド方式)が利用されています。
ハイブリッド方式の手順は次の通りです。
ハイブリット方式の手順
通信をする双方で使用する共通鍵を
セッション鍵(共通秘密鍵)という。
アリスとボブは公開鍵暗号方式によって、
公開鍵と、秘密鍵を作る。
アリスがボブとの通信を希望する。
(ボブの公開鍵を入手・・・
ボブから、あるいは公開鍵サーバから)
アリスはボブとの通信で使用するセション鍵を作る。
セッション鍵をボブの公開鍵で暗号化してボブに送信する。
ボブは自分の公開鍵のペア鍵である秘密鍵で
解錠し、セション鍵を取り出す。
これで、アリスとボブが共通のセッション鍵を
持つことになったので、
これ以降は、
このセション鍵をつかって、
暗号化通信を行う。
|
暗号化、復号化の処理に時間がかかるのは、他の公開鍵暗号方式でも変わりません。RSAは暗号化だけでなく、電子署名にも利用ができます。また、今言ったように共通鍵を安全に送信するという手段としても利用が可能です。
公開鍵方式には、RSA以外にも、Diffie-Hellman鍵交換方式や、Elgamal暗号方式、DSA、楕円曲線暗号方式などがあります。
Diffie-Hellman鍵交換方式(DHと略称されることが多い)は公開鍵方式の先駆けであり、第三者に知られることなく、通信の当事者同士が共通鍵を生成する方法です。DHは、一般に公開する公開鍵と自分だけで秘密にしておく秘密鍵の2つの組み合わせで実現されます。あくまで安全に鍵を生成する方式であり、暗号化はできません。暗号化だけでなく、電子署名をすることもできません。
Diffie-Hellman鍵交換法を理解するためには原始根(primitive root)の理解が必要ですので、初めに原始根の説明をします。原始根の定義は次の通りです。
p を素数として、法 p のもとで、
a が p - 1 乗して初めて 1 と合同となるとき、
a を p を法としての原始根という。 |
これだけだと少しわかりにくいと思いますので、具体例で説明します。p を 5 としましょう。この時、a は p(= 5)で割ったときの剰余(0は除く) 1、 2、 3、 4 で、これらについて 1~4まで累乗を求めてみます。具体的に計算すると、次のようになります。5を法とします。
剰余a |
1 |
2 |
3 |
4 |
a^1 |
1 |
2 |
3 |
4 |
a^2 |
1 |
4 |
4 |
1 |
a^3 |
1 |
3 |
2 |
4 |
a^4 |
1 |
1 |
1 |
1 |
フェルマの定理のよれば、p が素数で、 a を p と互いに素な整数としたとき、 a^(p - 1) ≡ 1 となります。従って、a^4 の行には当然 1 が並びます。2 と 3 は a^4 で初めて、 1 になっているので、原始根です。
もう一つ例題を解いてみたいと思います。次は、13 を法とする剰余系について考えます。
剰余a |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
a^1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
1 |
a^2 |
1 |
4 |
9 |
3 |
12 |
10 |
10 |
12 |
3 |
9 |
4 |
1 |
a^3 |
1 |
8 |
1 |
12 |
8 |
8 |
5 |
5 |
1 |
12 |
5 |
1 |
a^4 |
1 |
3 |
3 |
9 |
1 |
9 |
9 |
1 |
9 |
3 |
3 |
1 |
a^5 |
1 |
6 |
9 |
10 |
5 |
2 |
11 |
8 |
3 |
4 |
7 |
1 |
a^6 |
1 |
12 |
1 |
1 |
12 |
12 |
12 |
12 |
1 |
1 |
12 |
1 |
a^7 |
1 |
11 |
3 |
4 |
8 |
7 |
6 |
5 |
9 |
10 |
2 |
1 |
a^8 |
1 |
9 |
9 |
3 |
1 |
3 |
3 |
1 |
3 |
9 |
9 |
1 |
a^9 |
1 |
5 |
1 |
12 |
5 |
5 |
8 |
8 |
1 |
12 |
8 |
1 |
a^10 |
1 |
10 |
3 |
9 |
12 |
4 |
4 |
12 |
9 |
3 |
10 |
1 |
a^11 |
1 |
7 |
9 |
10 |
8 |
11 |
2 |
5 |
3 |
4 |
6 |
1 |
a^12 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
法13の場合も a^12 ≡ 1 (mod 13) (a と 13 は 互いに素) なので、a^12 の行が全部 1 になっているのはフェルマーの小定理から当然です。その前に、 1 が出現してしまっているものは、それがそのあと繰り返します。 a^12 で初めて 1 が出現する場合が法 13の 原始根で、上の計算例から、2、 6、 7、 11
がそれに該当することが分かります。
2、6、7、11の列を見ていただくと、余りはすべて異なりその余りは 1 から p - 1 まで巡回していることが分かります。これを一般化すると、次のような定理が出てきます。※これを定義とする流儀もあります。
原始根の定理
r が p に対する原始根のとき、
r、 r^2、 r^3、・・・、r^(p - 1)を
p で割った余りはすべて異なり、
1 から p - 1 を巡回する。 |
上の原始根の定理を背理法で証明する
r が原始根なのに r^n の余りがすべて異ならないと仮定する。
つまり、r^m ≡ r^n となる自然数 m、 n (n < m < p - 1)
が存在する。
これは r^n ( r^(m-n) - 1) ≡ 0 と同値。
ここで、r と p は互いに素なので、
r^(m - n) - 1 ≡ 0
これは原始根の定義に矛盾する。
よって、r、 r^2、 r^3、・・・、r^(p - 1)の余りは全て異なり
0 ではないので、
1 から p - 1 を一巡する。
|
原始根の存在定理
任意の素数 p に対して
原始根 r が存在する。 |
法 p としたとき、原始根は(1、2、・・・pの中に)
φ(φ(p)) = φ(p - 1) 個
存在する。 |
法p |
p-1 |
原始根の数
φ(p-1) |
原始根 |
3 |
2 |
1 |
2 |
5 |
4 |
2 |
2, 3 |
7 |
6 |
2 |
3, 5 |
11 |
10 |
4 |
2, 6, 7, 8 |
13 |
12 |
4 |
2, 6, 7, 11 |
17 |
16 |
8 |
3, 5, 6, 7, 10, 11, 12, 14 |
19 |
18 |
6 |
2, 3, 10, 13, 14, 15 |
23 |
22 |
10 |
5, 7, 10, 11, 14, 15, 17, 19, 20, 21 |
原始根の定理は次のように言い換えることもできます。
原始根の定義
(言い換えると)
(3以上の)素数 p と 1 以上 p 未満の整数 r が
以下の性質をみたすとき r を法 p に対する原始根という。
「r、 r^2、 r^3、・・・、r^(p - 2) の何れも p で割って余り 1 でない。」
(また、r = 1 は p = 2 に対する原始根である、とする) |
フェルマーの小定理から (p - 1) 乗すると、
r^(p - 1) ≡ 1 (mod p)
なので、上の定義はそこまでは、1 に戻らないという意味になります。
r、 r^2、 r^3、・・・と rのべきを増やしていき、
はじめて「p で割ったあまりが 1 となる」
ような指数のことを r の位数という。
この位数を使うと、
原始根は「位数が p - 1 であるもの」と簡潔に表現できる。 |
アリス(Alice)とボブ(Bob)が通信をすると仮定します。
DHの基本的なアイデアは極めて単純です。
アリスは公開鍵Yaを計算し、ボブに渡します。
ボブは公開鍵Ybを計算し、アリスに渡します。
これで、アリスとボブは自分の公開鍵と、相手の公開鍵を持つことになります。
この2つの公開鍵の積を共通鍵とすれば、
共通鍵をネットワーク上で送信することなく、
ネットワークで通信をしようとする双方が
共通鍵を持つことができます。
の積であるYaYbを持つことになります。
このYaYbを共通鍵として使えば、
ただ、こんな単純な方法では盗聴者に公開鍵が知られてしまった場合に
簡単に共通鍵を推定されてしまいます。
そこで、DHは、離散対数問題と呼ばれる解くことが難しいという性質を利用して、
盗聴者に鍵の素材が知られてしまっても、
そこから鍵を推定することが困難となるように工夫しています。
DHのアルゴリズムは次のようになります。
まず、アリスが十分に大きな素数を決め(通常は、512~1024ビット)、その原子根を G とする。ただし、実装では時間の関係から、初めに G を決め(通常、 2 や 5 が選択される)、それを原始根とする素数 P を選ぶというのが一般的である。
アリスは 0 ≦ Xa ≦ P - 1 となるXaをランダムに生成し
公開鍵 Ya を、Ya ≡ (G^Xa) mod P
で計算し、
通信相手のボブに (P、G、Ya) の鍵セットを送る。 |
ボブはアリスから鍵セットを受信する。
ボブは 0 ≦ Xb ≦ P - 1 であるXbを
ランダムに生成し、
K ≡ (Ya^Xb) mod P
を計算して、この K を共通鍵とする。
K ≡ (G^Xa)^Xb mod P
を得る。
更に、ボブは公開鍵 Yb を
Yb ≡ (G^Xb) mod P
で計算し、
アリスに (P、G、Yb)を送る。 |
アリスはボブから受信した Yb を使って、
共通鍵 K を
K ≡ (Yb^Xa)
≡ (G^Xb)^Xa mod P |
盗聴者が(P、G、Ya)と(P、G、Yb)を盗聴したとしても、XaあるいはXbを知っていなくてはなりません。
これには
Ya = G^Xa mod P
( Yb = G^Xb mod P も同様)
を満たすXaを計算で求める必要があります。
これは
Xa = logGYa mod P
という対数方程式をPを法として解かなくてはならないことになります。
このような問題は一般に離散対数問題と言われ解くのが難しいとされています。たとえ計算機を使っても現実的な時間内では解くことは非常に困難だと考えられているからです。
Elgamal暗号は、1985年にエジプトの暗号学者タヘル・エルガマル(Taher A.Elgamal)によって考案された暗号方式です。Elgamal暗号は、Diffie-Hellman鍵交換アルゴリズムを暗号方式に応用したものです。Elgamalは同様の原理を使って「Elgamal署名」(デジタル署名アルゴリズム)も考案しています。
DSA(Digital Signature Algorithm)はElgamal署名を基礎として採用した署名方式です。
Elgamal暗号方式は整数における離散対数問題を使いますが、楕円曲線と呼ばれる曲線上で離散対数問題を扱うのが楕円曲線暗号(Eliptic
Curve Crypotography、ECC)です。楕円曲線暗号は特定の暗号名ではなく、楕円曲線上でDSAを定義した楕円DSA(ECDSA、Elliptic Curve DSA)や、Elgamal暗号を楕円曲線上で定義した楕円Elgamal暗号、DH鍵共有を楕円化した楕円曲線ディフィーヘルマン鍵共有方式(ECDH)などがあります。
RSA では最近は2048ビット以上のものが推奨されていますが、楕円曲線暗号を使うと、同程度の安全性は10分の1程度のビット長で実現できるとされています。今後、安全性要求が高くなると必要なビット数はそれだけ大きくなりますので、楕円曲線暗号の必要性が高まっていくと予想されます。
米国国家安全局(NSA)は、データ暗号化など、ITシステムおよびシステムセキュリティに関する助言をするために、Suite B規格(2005年)を発表していますが、この中で、暗号化アルゴリズムとしてAES、鍵交換アルゴリズムとしてECDH、デジタル署名アルゴリズムとしてECDSA、ハッシュアルゴリズムとしてSHA-256、SHA-384を推奨しています。
楕円曲線は「楕円」ではありません。「楕円曲線」という名前の曲線です。
楕円曲線とは、
y^2 = x^3 + a*x + b
で定義された
非特異な代数曲線である。 |
a = -1、 b = 0 の場合 |
|
a = 1、 b = 1 の場合 |
|
非特異とは
グラフが尖点を持っていたり、
自分自身と交叉したり
しない
ということです。
a = 0、 b = 0 の場合は
尖点を持つ(なめらかでない)ので
楕円曲線ではありません。
楕円曲線の定義は、曲線が非特異であることです。
これを幾何学的にいうと、曲線のグラフが
尖点を持たないこと、
自己交叉しないこと
孤立点を持たないこと
と言い換えることができます。
これを代数学的にいうと、
特異点を持たないことは
判別式
Δ = -16(4a^3 + 27b^2)
に関係します。
特異点を持たないということは
Δ ≠ 0
と言い換えることができます。
従って、4a^3 + 27b^2 ≠ 0
が成り立たなくてはなりません。
楕円曲線暗号を考える際には、
有限体上の楕円曲線に限定して考察します。
※有限体(ガロア体):集合の要素同士で加算・減算・乗算・除算(0による除算は除く)を計算することができる集合を体(field)と呼びます。素数 p に対して、 0 から p - 1 までの整数の集合を Fp = {1、2、3、...、p - 1} とすると、この Fp も体です。Fp のように、要素の個数が p 個である体を素体(prime field)といいます。Fp の各要素は p で割った余りも表していますので、この範囲以外の整数についても、その整数を p で割った余りを考えることで、素体 Fp の要素と考えることができます。素体のように、有限個の要素を持つ集合で、要素間の加算・減算・乗算・除算(ただし、0 の除算は除く)ができるとき、その集合を有限体(finite field)といいます。有限体の要素の個数は、素数のべきになることが知られています。素体は、有限体の例です。
楕円曲線暗号は楕円曲線上の離散対数問題の難しさ
を基にして作られます。
離散対数問題については既に説明したように
整数 r、 n、 s が与えられたときに
s ≡ r^x (mod p)
となる x を求めることです。
離散対数問題に出てくる r、 s は
0 ~ n - 1 の整数です。
楕円曲線上の離散対数問題では、
r、 s に対応するものは
どちらも2つの整数の組です。
従って、これらは平面上の点に対応させることができます。
離散対数問題における
s ≡ r^x (mod p)
r、 s を楕円曲線上の点に置き換え
それを P、 Q とし、
Q = k * P
を考えます。
楕円曲線上では、加法を定義し、
乗法は加法を使って定義します。
例えば
Q*2 = Q + Q
Q*3 = (Q + Q) + Q
と考えます。
楕円曲線上の有理点(座標の値が有理数であるような点)は加法群となります。
従って、楕円曲線上の点で加法・減法を定義することができます。
※無限遠点と呼ばれる特殊な点も有理点と扱います。無限遠点は(x、 y)のような表記ができません。強いて表現すると(∞、 ∞)となります。
※集合 G と演算○が(ⅰ)集合 G の任意の要素 a、 b、 c に対して、(a ○ b)○ c = a ○(b ○ d)となる、 (ⅱ)集合 G の要素 e で、集合 G の任意の要素 a に対して、a ○ e = e ○ a = a となるものが存在する、 (ⅲ)集合 G の任意の要素 a に対して a ○ a' = a' ○ a = e となる集合 G の要素 a' が存在する、という(ⅰ)~(ⅲ)の全ての条件が成立するとき、集合 G は演算 ○ に関する群(group)であるといいます。特に演算が + となるときを加法群といいます。演算 ○ は可換(a ○ b = b ○ a)とは限りませんが、加法群は可換と考えられます(a + b = b + a)。
しかし、有限体上の楕円曲線上の2点の加法は
皆さんが今まで知っている
x 座標と、y 座標を単純に足し加えるような単純なもの
ではありません。
幾何学的な面から見た場合の加法は次のようになります。
有限体上の楕円曲線上の 2 点 P、 Qの和 R を
次のように定義する。
2 点 P、 Q を通る直線
(P と Q が同じ点の場合は接線)
を引く。
楕円曲線と直線 PQ の交点
(P、 Q 以外の第3の交点)
を R' とする。
R' の x 軸に関する対称点を
R とする。 |
楕円曲線上の P と Q を加えると、
幾何学的には
P と Q を結ぶ直線と楕円曲線の交点の
y 座標を - y としたものが
P + Q
となります。
あるいは、直線 PQ を x 軸に対照に
反転させた直線と楕円曲線の交点が
P + Q
を与える
と考えても構いません。
もう一つ例をあげます。
A + B = C
A + C = D
A + D = E
を順次加算すると
グラフ上では
C、D、E
は次のように
なります。
A + B = C |
|
A + C = D |
|
A + D = E |
|
同じ点 P を加算したものは
その点からの接線と
楕円曲線の交点の y 座標を
- y とした点となります。
上の加算を繰り返すことで乗算が求められます。
従って、加算を k 回繰り返すと
Q = k * P
が得られることになります。
暗号の観点から特に注目すべきは
mod p (p は素数)
における楕円群です。
これは Ep(a、 b)として表されます。
この時、要素(x、 y)は
無限遠点 0 および以下の条件を満たす非負整数の組です。
※ 「無限遠点」とは、この演算に関してゼロの役割をします。
それでは、楕円曲線
y^2 = x^3 + 2x -1
を mod 7 で考えてみましょう。
y^2 = x^3 + ax + b (mod p) で
E7(2、 -1)について考えていますので、
a = 2、 b = -1
従って、
4*a^3 + 27*b^2
= 4*2^3 + 27*(-1)^2
≡ 3 (mod 7) ≠ 0
これは mod 7 の楕円群の条件を満たしています。
楕円群を考える場合には、mod p で
この式を満たす (0、 0) から (p、 p) までの
象限に含まれる非負の整数だけです。
y^2 = x^3 + 2x - 1 (mod 7)
を満たす(x、 y) はどうなるでしょうか?
しらみつぶしに調べてみると、
(1、 3)(1、 4)
(2、 2)(2、 5)
(3、 2)(3、 5)
(4、 1)(4、 6)
(5、 1)(5、 6)
となります。
無限遠点(∞、∞)を
含めると、全部で11個の点となります。
※ 「無限遠点」とは、この演算に関してゼロの役割をします。
法を大きな数にすると、しらみつぶしにするわけにはいきません。
どうしたらいいでしょうか。
実際に交点を求めてみるしかなさそうです。
有限体上の楕円曲線上での加法は代数的に観点からは
次のように定義されています。
(x1、y1)という点と、(x2、y2)という点の
和(x3、y3)を次のように約束する。
x3 = λ^2 - x1 - x2 (mod 7)
y3 = λ(x1 - x3) - y1 (mod 7) |
λは次のようになります。
(x1、y1) ≠ (x2、y2) の場合は
λ = (y2 - y1)*(x2 - x1)^(-1)
(x1、y1) = (x2、y2) の場合は(接線の場合)
λ = (3x1^2 + a)*(2y1)^(-1)
|
※ここで、(-1)乗は逆数(Z7上で掛けると1になる相手のこと)のことです。
λ = (y2 - y1)*(x2 - x1)^(-1)
となります。
ということは直線の傾きということです。
ただし、同じ点の足し算の場合は、分母が 0 となってしまいます。
従って、接線の場合は、
λ = (3x1^2 + a)*(2y1)^(-1)
更に x1 = x2 で、 y1 = -y2
という場合があります。
この場合の足し算の答えは、「無限遠点」とします。
さて先ほど何も分からずに手探り状態で
探し当てた10個の点は、閉じているのでしょうか。
(1、 3)と(3、 5)を足すとどうなるでしょうか。
λ = (5 - 3)/(3 - 1)
= 2*4
= 1 (mod 7)
∵ 7を法としたときの2の逆数は4です。
x3 = 1^2 - 1 - 3 = -3 = 4 (mod 7)
y3 = 1*(1 - 4) - 3 = -6 = 1 (mod 7)
(4、 1)は元の点の中に存在しています。
もう一つやってみましょう。
(3、 2)と(4、 6)を足してみましょう。
λ = (6 - 2)/(4 - 3) = 4 (mod 7)
x3 = 4^2 - 3 - 4 = 9 = 2 (mod 7)
y3 = 4*(3 - 2) - 2 = 2 (mod 7)
(2、 2)はこれも元の点です。
今度は同じ点を加えてみましょう。
(1、 3)*2 = (1、 3) + (1、 3)
λ = (3 + 2)*6 = 2 (mod 7)
∵ 法7での6の逆数は6です。
x3 = 4 - 1 - 1 = 2 (mod 7)
y3 = 2*(1 - 2) - 3 = -5 = 2 (mod 7)
∴ (1、 3)*2 = (2、 2)
となって、やはり元の点です。
演算が閉じているように思えます。
つまり、群(可換群)になっているようです。
ここで考える楕円曲線は、有限体という有限な範囲
(あるところまで行くと元に戻る世界)に
閉じ込められています。
楕円曲線上の有理点同士の加算・減算を行うことができます。
このような楕円曲線上の有理点のなす加法群を
Mordell-Weil群と呼びます。
加法群の要素の個数を群位数(group order)と呼びますが、
楕円曲線上の有理点のなす加法群の位数とは
有理点の個数のことです。
有理点のなす加法群の群位数を求める最も簡単な方法は、
楕円曲線の定義式の右辺に x = 0、1、2、・・・p-1を
順番に代入していき、その値が平方数となっているかどうか
調べていく方法です。
では、先ほどの mod 計算の話に戻ります。
念入りに調べると元の1つの点から
他の全ての点を算出することができます。
(1、 3)*2 = (2、 2)
ということは
(1、 3)*3 = (2、 2) + (1、 3)
ということです。
こんな風に順次計算していくと、次のようになります。
(1、 3)*1 = (1、 3)
(1、 3)*2 = (2、 2)
(1、 3)*3 = (2、 2) + (1、 3) = (5、 1)
(1、 3)*4 = (5、 1) + (1、 3) = (3、 5)
(1、 3)*5 = (3、 5) + (1、 3) = (4、 1)
(1、 3)*6 = (4、 1) + (1、 3) = (4、 6)
(1、 3)*7 = (4、 6) + (1、 3) = (3、 2)
(1、 3)*8 = (3、 2) + (1、 3) = (5、 6)
(1、 3)*9 = (5、 6) + (1、 3) = (2、 5)
(1、 3)*10 = (2、 5) + (1、 3) = (1、 4)
(1、 3)*11 = (1、 4) + (1、 3) = (∞、∞)
全部元の点に戻ります。
楕円曲線上の点を 2 倍、3 倍、・・・していくと
必ず途中で計算結果が無限遠点に等しくなります。
d*P = P + P + ... + P
となり、P の d 倍は
P を d 個足し合わせることと同じです。
P を d 回加えた点は、
スカラー倍点(scalar multiplied point)、
スカラー倍点を求める計算を
スカラー倍算(scalar multiplication)と呼びます。
ある点をスカラー倍算して無限遠点に到達したときのスカラー値を
点位数(point order)といいます。
別の言い方をすると、点 P の点位数とは、
n * P = 無限点
となる最小の n のことです。
(1、 3)*9 = (2、 5)
は簡単に計算できますが、
(1、 3)*n = (2、 5)
となる n を探すのは難しいとすれば、
暗号に使えるのではないか
ということになります。
Q = k * P
を成り立たせる k を探さなくてはならないのですが、
P と Q が楕円曲線上の点で、
しかも、素数を法とした閉じた世界で
答えを探さなくてはなりません。
これが、楕円曲線暗号の強さの秘密です。
(1、 3)*n = (2、 5)
となる n を探すということは
n = (1、 3)/(2、 5)
を満たす n を計算することです。
有限体における除算は素朴な方法では最悪 (p - 1)回の
除算を必要とします。
拡張ユークリッド互除法を使った場合は、
最悪でも 5 log p 回といわれていますが、
p を大きくすれば、簡単にはいきません。
楕円曲線を使った鍵交換の方法は次の通りです。
アリスは楕円曲線Ep(a、 b)を生成
(素数 p と、 媒介変数 a、 b を決定)
アリスは作成した楕円曲線上に含まれる開始点 G を決定
(Gは nG = 0 で、
n が非常に大きな素数となるような
最小の値)
Ep(a、 b) と G は公開されているものとする。
アリスは n より小さい整数 Na を決めて、
これを秘密鍵とする。
アリスは Pa(Na*G)を公開鍵とする。
ボブも秘密鍵 Nb を選択し、
公開鍵 Pb(Nb*G)を生成する。
アリスは自分の秘密鍵と、ボブの公開鍵から、
共有鍵(セション鍵)
K = Na*Pb
を生成する。
ボブも共有鍵(セション鍵)
K = Nb*Pa
Na*Pb = Na*Nb*G
Nb*Pa = Nb*Na*G
したがって、Na*Pb = Nb*Pa
となる。
|
公開情報 Ep(a、 b)や G、 Pa、 Pb
などが知られてしまっても、これらを元にして
K を計算することは
困難であるとされています。
次はElgamal暗号を楕円曲線に対応させた
「楕円Elgamal暗号」について考えてみます。
平文 M を座標上の点 Pm へ符号化し
送信できる形にする。
媒介変数として点 G、 楕円群 Ep(a、 b)と使う。
アリスは次のように、
ボブに暗号化されたメッセージを送信する。
アリスは秘密鍵 Na、 公開鍵 Pa(Na*G)を生成
ボブは秘密鍵 Nb、 公開鍵 Pb(Nb*G)を生成
アリスは任意の正の整数 k を選択し、
一組の点から構成される暗号文 Enc(Pm) を作成する。
Enc(Pm) = {k * G、 Pm + k*Pb}
ボブは受信した点の組のうち1つ目の点に、
自分の共有鍵の値を掛け、
その値を2つ目の値から引く。
Dec(Enc(Pm)) = Pm + k*Pb - Nb(k*G)
= Pm + k*(Nb*G) - Nb(k*G)
= Pm
Mを楕円曲線上の点 Pm に符号化し、
Pmを暗号化し、
これを復号すると
元の Pm が得られることが分かります。
|
楕円曲線暗号というとグラフの理解そのものが難しいので、
そこに目が行ってしまうのですが、
楕円曲線上の点と点の間に
ある演算を定義すると、
それが群になっていて、
その群がRSA暗号の剰余類の
群のような役割を果たしている
ということです。
更新履歴
2016/06/20 作成
|