公開鍵について


PGPを使って暗号化してメールを送る事ができ、またそのようになさりたい方は 公開鍵で暗号化して ROT までメールをお送り下さい。
またこのページに関するいかなる内容についても掲示板なりメールなりで気軽にご質問下 さい。数学の話題となると管理者は非常に喜びます。

なお、以下の内容については自分でも書きすぎたと思うくらいにあちこちの話題に触れま した。一度に読んでしまおうと思わずに何日かかけて気長に読むくらいの気持ちで読んで くださると嬉しく思います。また、証明をつけたりつけなかったりかなりいい加減な事を やっているのは、摩訶不思議な数理現象を楽しく紹介する事によって、少しでも沢山の人 に興味を持って貰う事を主眼において書いた為です。少々難しい所もありますので、解ら なくなったら書いてある例だけでなく自分で思いついた例を計算してみて下さい。集合と 写像の言葉に慣れている人は、いい加減に書いてある所をきちんと書き直し、できれば証 明をつけてみるとよい練習になると思います。また、ページの最後に読書 案内として暗号と数学の本をいくつか挙げておきました。
肝心な事を書き忘れましたが、このページはスタイルシートを使っております。スタイル シートがないと非常に読み難くなりますので対応ブラウザでご覧下さい。また、動作確認 は IE5 とネスケ4.7で行っています。

公開鍵暗号に対して共通鍵暗号というものがありますが、両者の違いと得手不得手につい て簡単に書いておきます。

【共通鍵暗号】
従来の暗号方式。秘密通信を行いたい者同士が両者以外には秘密の鍵を共有する方式で、 換字と置換を繰り返し使って鍵を構成する。この方式では暗号化の鍵と復号化の鍵は同一 の物を使う。この方法では計算機への負担が少ないという利点があるが、秘密の鍵を第三 者に知られないように受け渡しする必要があり、また秘密通信を行いたい組の分だけ鍵が 必要であるという難点がある。n 人がそれぞれの鍵を用意するとなると
nC2 = n * ( n - 1 ) / 2 個の鍵が必要になる。

【公開鍵暗号】
1970年代に提案された新しい暗号方式。利用者 (Aとしよう) は公開鍵と秘密鍵を生成し、 公開鍵を誰もが見られるように公開しておく。BがAに秘密通信を行いたい場合は平文 ( もとの文を平文という) をAの公開鍵を使って暗号化し (それを暗文という) Aに送信す る。Aは秘密鍵で暗文を平文に復号化する。特筆すべき点は、暗号化の鍵と復号化の鍵が 異なることである。共通鍵方式のように鍵を秘密にやり取りする必要がないのである。ま た、n 人でそれぞれ秘密通信を行いたい場合も鍵は n個で足りるのである。ここまで見れ ばいい事ずくめのようであるが、一般に共通鍵方式に比べて計算機への負担が大きい。


以下は「なぜ鍵を公開しても大丈夫なのか?」という質問に(そんな質問は来てないけど )にお答えしていきます。巧妙な数学的手法で実現している公開鍵のカラクリの面白さを 感じ取っていただければ幸いです。公開鍵の例としてRSAを取り上げます。良くある建前に 則って、高校数学の知識で理解できるように書きました、という事にしておきます。
少し量が多いですが、言葉と記号の説明を先に読んでおく と解りやすいと思いますが、無理にとは言いません。いや、やっぱり先に読んで下さい。


RSA のカラクリ

1. 鍵の生成
p, q を素数とし、n = p * q を計算する。
φ( n ) = ( p - 1 ) * ( q - 1 ) を計算する。
(φ( n ) はオイラー関数
e を正整数とし、( e, φ( n ) ) = 1 となるようにとる。
(つまり、e と φ( n ) は互いに素。)
e の法 φ( n ) に関する逆数を d とする。(但し d > 0 ととる。)

* 公開鍵 *
n, e
* 秘密鍵 *
d または p, q または φ( n )
(要するに n の素因数分解がわかれば秘密鍵がわかるという事)

2. 暗号化
平文を定められた規則に従って整数に変換し、それを M とする。
ただし、( M, n ) = 1 となるようにとる。
暗号文 C を次の手順により計算する。
C は M^e を n で割った余りととる。
合同式で書けば
C ≡ M^e ( mod n ) ; 0 < C < n
(蛇足であるが、M^e の名誉の為に、WindowsMeとは無関係である事を明言しておく。)

3. 復号化
秘密鍵 d を使い次を計算すれば良い。
C^d = ( M^e )^d = M^( d * e ) ≡ M ( mod n ).
最後の合同式は、オイラーの定理より、
M^( φ( n ) の倍数 ) ≡ 1 ( mod n ) である事と、
d * e = ( φ( n ) の倍数 ) + 1 である事から従う。

解読 ( 正当な受信者以外が暗文から平文を得ようとする行為 ) に対する堅牢さの根拠は、 素因数分解の困難さによる。 p, q ともに 100桁程度の素数であれば、n = p * q の素因 数分解は中々にしんどい。が、暗号化の計算も少ししんどい。よって、送信したいものの 重要さの程度により p, q の大きさを調節すれば良い。

これが RSAのカラクリであるが、これをはじめて見て一読で理解できれば苦労はないので、 いくつか具体例を見て暗号化と復号化の様子を実感しよう。なお、ぜひとも自分の手で計 算してみることが大事である。これに限らず下の説明どころか数学全般に関しても自分の 手を動かしてみる事が大事である。手でしんどい時には 電卓 をご利用されたし。

例 )
p = 17, q = 23, e = 3 とする。
n = p * q = 391
φ( 391 ) = ( 17 - 1 ) * ( 23 - 1 ) = 352
3 * d ≡ 1 ( mod 352 ) を計算して、
d = 235
実際、3 * 235 = 705 = 2 * 352 + 1 ≡ 1 ( mod 352 )
ここまでで準備はお終い。

* 公開鍵 *
n = 391 , e = 3
* 秘密鍵 *
d = 235

(暗号化)
平文 M を、M = 101 とすると暗文 C は、
101^3 = 1030301 = 2635 * 391 + 16 ≡ 16 ( mod 391 ).
よって C = 16

(復号化)
16^235 を 391 で割ると余りは、101 で無事に復号化成功。
平文 M を他のものに変えて試してみよう。

他にも例を考えて試してみよう。 例えば、 p = 47 , q = 59 , e = 3 であれば、
n = 2773 , φ( n ) = 2668 , d = 1779 である。
1000以下の素数表もご利用されたし。


言葉と記号の説明

【 ベキ乗 】
a を整数、m を正整数とする。
a を m 回かけたものを a の m 乗といい、
a^m とかく。
例 )
2^32 = 4294967296
3^6 = 729
10^3 = 1000
(-1)^65537 = -1 等。

【 合同 】
a, b, m を整数とする。
a と b を m で割った余りが等しい時、a と b は m を法として合同であるといい、
a ≡ b ( mod m ) とかく。
例 )
5 ≡ 2 ( mod 3 )
8 ≡ 18 ( mod 2 )
14 ≡ 0 ( mod 14 )
-7 ≡ 19 ( mod 13 ) 等。

【 最大公約数 ( G.C.D. ; Greatest Common Divisor ) 】
a, b を整数とする。
a, b を共に割りきる数を a, b の公約数といい、
公約数の内で最大のものを最大公約数という。
a, b の最大公約数を gcd ( a , b ) または単に ( a , b ) とかく。
とくに、a, b の最大公約数が 1 である時、a と b は互いに素であるという。
また、具体的な計算法については下で紹介するユークリッドの互除法による。
例 )
( 6 , 21 ) = 3
( 4 , 16 ) = 4
( 11 , 6 ) = 1 → 11 と 6 は互いに素
( 1 , 1 ) = 1 → 1 と 1 は互いに素!

【 法 m の逆数 】
( a, m ) = 1 なる整数 a, m に対して、
a * b ≡ 1 ( mod m ).
となる整数 b が存在する。またこの b を mod m での a の逆数という。
一般に、ひとつ b が見つかればその他の全ての逆数は " b + t * m ; t は整数 " で表わされる。
証明
◇ b + t * m が逆数であること
a * ( b + t * m ) = a * b + a * t * m ≡ a * b ≡ 1 ( mod m ).
より、" b + t * m " は逆数である。
◇ 逆数であれば b と mod m で合同であること
c を勝手な mod m での a の逆数とすれば、
a * c ≡ 1 ( mod m ).
を満たすから、両辺に b を掛けてやれば、
1 * b = b ≡ b * a * c = ( b * a ) * c ≡ 1 * c = c ( mod m ).
即ち b ≡ c ( mod m ) である。 ( 証了 )
逆数が必ず存在する事と具体的な計算法に関しては下で紹介するユークリッドの互除法による。
例 )
mod 7 での 2 の逆数。
4, 11, -3, -10 など。
実際、
2 * 4 = 8 = 7 + 1 ≡ 1 ( mod 7 ).
2 * 11 = 22 = 3 * 7 + 1 ≡ 1 ( mod 7 ).
2 * (-3) = -6 = -7 + 1 ≡ 1 ( mod 7 ).
2 * (-10) = -20 = -3 * 7 + 1 ≡ 1 ( mod 7 ).

【 ユークリッドの互除法 ( Euclidean algorithm ) 】
m, n を正の整数とし、m > n としても一般性を失わないのでそうする。
符号の違い(±1倍)は本質的ではないので気にしない。
次のようにして商 q と余り r を計算していく。
いつかは余りが 0 となるので、終わりの番号を k とした。
m = q 0 * n + r1
n = q 1 * r1 + r2


rk-2 = q k-1 * rk-1 + rk
rk-1 = q k * rk + 0
但し、rj-1 > rj であり、ri と q i は整数。
と割りきれる所まで計算すれば、rk が m と n の最大公約数である。
証明は初等整数論の本などを参照のこと。

例 )
18 と 12 の最大公約数の計算例。
18 = 1 * 12 + 6.
12 = 2 * 6 + 0.
よって ( 18, 12 ) = 6.
107 と 14 の最大公約数の計算例。
107 = 7 * 14 + 9.
14 = 1 * 9 + 5.
9 = 1 * 5 + 4.
5 = 1 * 4 + 1.
4 = 4 * 1 + 0.
よって ( 107, 14 ) = 1.

更にユークリッドの互除法を利用して、次の不定方程式の解も計算できる。
d = ( a, b ) とする時、
a * x + b * y = d.
の整数解 x, y を求めよ。
具体例での計算だけにとどめるが証明も簡単である。
例 )
18 * x + 12 * y = 6. の解
先の例から、
18 = 1 * 12 + 6.
より
6 = 18 - 12. これは簡単過ぎた。例が悪い。
107 * x + 14 * y = 1. の解
5 = 1 * 4 + 1.
より
1 = 5 - 4. を得る。
9 = 1 * 5 + 4.
より
4 = 9 - 5. これを先のに代入して、
1 = 5 - ( 9 - 5 ) = - 9 + 2 * 5. を得る。
14 = 1 * 9 + 5. より
5 = 14 - 9. これを先のに代入して、
1 = - 9 + 2 * ( 14 - 9 ) = 2 * 14 + (-3) * 9. を得る。
さてもう一息。
107 = 7 * 14 + 9. より
9 = 107 - 7 * 14. これを先のに代入して、
1 = 2 * 14 + (-3) * ( 107 - 7 * 14 ) = (-3) * 107 + 23 * 14.
つまり解は、x = -3, y = 23 である。

さて、これにより "法 m の逆数" の計算が出来る。
a = 107, m = 14 とすれば、上の例により、
(-3) * 107 + 23 * 14 = 1.
よってこの両辺を法 m ( = 14 ) で見れば、
1 = (-3) * 107 + 23 * 14 ≡ (-3) * 107 ( mod 14 ).
従って、-3 は法 14 での 107 の逆数である。
負数が不満であれば、 -3 に 14 の倍数を加えて、11, 25, … をとっても良い。

【 オイラー関数 ( Euler function ) 】
m を整数とし、関数 φ(m)を次で定める。
φ( m ) := m 以下で m と互いに素な整数の個数.
例 )
φ( 1 ) = 1
φ( 2 ) = 1
φ( 7 ) = 6
φ( 11 ) = 10
一般に、p を素数とすれば、
φ( p ) = p - 1.

合成数の場合、例えば m = 6 はどうか?
6 と互いに素な 6 以下の自然数は、
1, 5 である。よって
φ( 6 ) = 2
同様に、
φ( 12 ) = 4
φ( 39 ) = 24 等。
一般に m = p * q (p, q は素数。但し、 p ≠ q. )の場合はどうか?
発想を逆転して、互いに素でないものの個数を数え上げ m から引いてみよう。
m と互いに素でない数は p の倍数と q の倍数であるから、
p, 2p, 3p, 4p, …, ( q - 1 )p, qp / 合計 q 個。
q, 2q, 3q, 4q, …, ( p - 1 )q, pq / 合計 p 個。
pq と qp は重複しているのでその分一つ引いてやれば、
m と互いに素でない m 以下の整数は p + q - 1 個である。
従って φ( m ) の値は
φ( m ) = m - ( p + q - 1 ) = ( p - 1 ) * ( q - 1 ).
である。(気になる人は例を計算してみよう)
素数の場合のオイラー関数の値を思い出せば、
φ( m ) = ( p - 1 ) * ( q - 1 ) = φ( p ) * φ( q ).
ここでは示さないが、一般に ( a, b ) = 1 であれば、
φ( ab ) = φ( a ) * φ( b ).
が成り立つ。

最後に 素数のベキの場合の値を述べておく。
m = p^n ( p を素数、 n を正整数とする ) はどうか?
これも上と同様に m と互いに素でない m 以下の自然数の個数を数える。
p, 2p, …, p^(n-1) * p
つまり p^( n - 1 ) 個である。従って φ( p^n ) の値は、
φ( p^n ) = p^n - p^( n - 1 ) = ( p - 1 ) * p^( n - 1 ).
少し技巧的であるが、次の表現を知っておくのも良い。
φ( p^n ) = ( p - 1 ) * p^( n - 1 ) = m * ( 1 - 1 / p ).

以上によりオイラー関数の値は次で計算できる。
m = p^k * q^m * … * r^n ( p , q ,…, r は素数 ) と m が素因数分解されたとき、
φ( m ) = m * ( 1 - 1/p ) * ( 1 - 1/q ) * … * ( 1 - 1/r ).
ややこしいので小さな例で沢山計算してみよう。

【 フェルマーの小定理 / オイラーの定理 】
Th. フェルマーの小定理
p を素数とすれば、( a, p ) = 1 なる整数 a に対して、
a^( p - 1 ) ≡ 1 ( mod p ).
である。
例 )
2^65536 ≡ 1 ( mod 65537 )
36^640 ≡ 1 (mod 641 ) 等。
他にも色々 電卓 の5番目で試してみよう。

上の定理は次の定理の特別な ( m = p の ) 場合である。
Th. オイラーの定理
( a, m ) = 1 なる整数 a, m に対し、
a^φ( m ) ≡ 1 ( mod m ).
がなりたつ。
例 )
36^48 ≡ 1 ( mod 65 )
27^400 ≡ 1 (mod 505 ) 等。
証明は、群論のラグランジュの定理や、初等整数論のフェルマーの (小) 定理を参照されたい。

なお、フェルマーの小定理は素数判定 ( 合成数判定 ) に役立つ。
今一度ステートメントを書き下してみれば、
p が素数ならば、
( a , p ) = 1 なる全ての整数 a に対して、a^( p - 1 ) ≡ 1 ( mod p ).
であったから、その対偶をとってやれば、
( a , p ) = 1 なるある整数 a に対して 法 p で a^( p - 1 ) と 1 が不合同ならば、
p は素数でない ( つまり合成数である )。
従って、素数かどうかわからない数に対してこのテストを適用してみれば合成数を判定す る事ができるのである。ところでこの事は、このテストをくぐり抜けたからといってその 数が素数であるといっているのではないので注意しよう。このテストに引っかからない合 成数を擬似素数という。中でも ( a , p ) = 1 なる全ての a に対して引っかからない合 成数をカーマイケル数という。 カーマイケル数の例は、561 ( = 3 * 11 * 17 ) や 1105 ( = 5 * 13 * 17 ) である。計 算機の使える人はこれを確認したり他のカーマイケル数を探したりしてみよう。


読書案内

【 暗号関連 】
「暗号の数理」 / 一松信 著 / 講談社 BLUE BACKS
古代の暗号から現代の暗号までを幅広く扱った本。初等整数論の話題が豊富で面白い。後 半部分の数学の内容は、いま読み返してみて思わずニヤリとしてしまった。


「情報セキュリティの科学」 / 太田和夫 黒澤馨 渡辺治 著 / 講談社 BLUE BACKS
現代の社会で暗号がどういう役割をしているのかを、使われ方と共に解りやすく解説した 本。暗号技術というとひたすら秘匿する事を連想するかもしれないが、現在では本人であ る事を証明するといった認証の役割をも持っている事にも触れ、そのような新しい使われ 方(マジックプロトコル)の実例が沢山載っていて面白い。


「暗号と情報社会」 / 辻井 重男 著 / 文春新書
現代的な暗号の話題を取り上げた本。数理的な側面は余り取り上げず、実際の社会での使 われ方が沢山紹介してある。


「暗号」 / 辻井 重男 著 / 講談社選書メチエ 73
古代から現代までの暗号を紹介した本。RSA の例も解りやすく載っている。最後にフェル マーの定理(小定理ではなくてワイルズがやっつけた方)から楕円曲線の話へと数論の話 題が紹介してあり、数学は美しく面白いだけではなくて実際に役に立ってしまうのである という事が納得できてしまう。


【 数学関連 】
「初等整数論講義 第二版」 / 木 貞治 著 / 共立出版株式会社
いわずと知れた名著。二次体の整数論が非常に詳しい。数学の内容の素晴らしさはもちろ んであるが、それだけにとどまらず具体的な計算のアルゴリズムがこれでもかと書いてあ る。


「数学ビギナーズマニュアル」 / 佐藤 文広 著 / 日本評論社
数学科で数学をやろうという人は絶対に読んでおきたい本。数学独特の言いまわしや言葉 の使い方(集合と写像の言葉の)が解り易く書いてある。ハードカバーの難しそうな数学 書も数学語に慣れていれば面白いのだけれど、日本語の感覚だけではきちんと読めず、面 白さに気がつく所まで行かない。勿体無い事である。数学語についての本はこれが一番… でしょう。


暗号に関した読み物は結構あるけれど、(初等)整数論に関した読み物は余り知りません。 本はなくとも、割った余りがどうなるか?などの数理現象でたくさん遊んでみるのは面白 いです。四則演算だけですぐに遊べる問題を考えてみましょう。例えば「 x^2 + 1 」の x に色々な整数を代入して、その値の素因数を調べてみるのも面白いです。 素数表を使ってどんな数が素因数に現われるか調べてみま しょう。2 以外の素因数は何かで割った余りが一定になっています。そして実は、この値 そのものが素数となる ( 5, 17, 37, …) ものは無数に沢山あるかどうかがまだ解ってい ません。問題を、x^2 + 2 に変えてみるとか、x^2 + y^2とニ変数に変えてみるなど色々試 してみましょう。何か規則を見つけたらしめたものです。

長々とゴチャゴチャ書きましたが、一言でいえば「数学は面白いよ」という事です。「数 学なんて役に立たないよ」などと言わずに騙されたと思って騙されてみてください。面白 さに気がついたときにはもう手遅れです。

[ 戻る ]