|
公開鍵と秘密鍵 |
||||
|
● 鍵（かぎ） ● 私は仕事をしている部屋にたどりつくまでに、 ちょっとおおげさですね〜。 もちろん、開けるときの鍵と閉めるときの鍵は同じです。 でも、よ〜く考えると、開けるときと閉めるときでは そりゃ〜、そうですよね。 ９０度まわして鍵を閉めたのなら この逆にするってことは、さんすう・数学では
● 逆元（ぎゃくげん） ● ＜たし算の場合＞ たとえば、たし算で考えてみましょう。 ３ に ７ をたすと １０ になります。 ３＋７＋（−７） ＝ ３ ７ のたし算における 逆の数は −７ です。 ７＋（−７）＝０ となるのがポイントです。０ は たし算において、 ３＋０ ＝ ３ のように、たしてもかわらない（もとどおり）という、とくべつな数です。
＜かけ算の場合＞ 今度は、かけ算で考えてみましょう。 ３ に ７ をかけると ２１ になります。 ３×７×（１/７） ＝ ３ ７ のかけ算における 逆の数は １/７ です。 ７×（１/７）＝１ となるのがポイントです。１ は かけ算において、 ３×１ ＝ ３ のように、かけてもかわらない（もとどおり）という、とくべつな数です。 あらっ、でもちょっとまって！ ３ に ０ をかけると ０ になるけど・・・。 けっきょく、かけ算でもとにもどしたいようなときは、
● 剰余（じょうよ） ● 剰余（じょうよ）って、あまりのことでした。 ＜お勉強＞の「剰余」で、こんな表を作りましたね。
Ｙ
０ ５ ２ ７ ４ １ ６ ３
表の見方ですが、もう一度くりかえすと ３７ ， ３７＋４０ ， ３７＋４０×２ ， ３７＋４０×３ ， ・・・ つまり、 ３７ ， ７７ ， １１７ ， １５７ ， ・・・ などでした。 まとめると、５でわると２あまり、８でわると５あまる数は
さて、これからは、このせまい表の中で考えてみることにしましょう。 さらに、たし算とかけ算のうち、今回はかけ算を考えてみます。 ３ に ７ をかけると ２１ になります。 だれですか。 ３×７×□ を４０でわったあまりが もとの ３ になるような□は何かな？ っていうのです。そうすると、 ７×□ を４０でわったあまりが １ になるような□は何かな？ ということになってきますね。 ４０でわった商を○にすると ７×□ ＝ ４０×○ ＋ １ ですから、移項して ７×□ − ４０×○ ＝ １ ・・・ （１） となり、またどこかで見た式だな〜って気がしますね。 そうです。ユークリッドの互除法です。 ユークリッドの互除法は、最大公約数の見つけ方でしたが、 さらには、４０と互いに素でなければ、（１）のように右辺が １ にならないので、 ですから、４０＝２×２×２×５ なので、２や５でわりきれる数は つまり、表でいうと、
Ｙ
０ ５ ２ ７ ４ １ ６ ３
のこった数をあらためて表にしましょう。
Ｙ ５ ７ １ ３
じつは、これらの数が公開鍵（になりうるもの）です。 これらの公開鍵で９０度まわして（じっさいは累乗して）閉めたら、 では、引き続き、公開鍵７ のかけ算における逆の数、 ７×□ − ４０×○ ＝ １ ・・・ （１） さあ、ユークリッドの互除法でしたね。 ７ と ４０ の最大公約数（７，４０）をもとめることが ７ ， ４０ ， （７，４０） おたがいにわり算をすると、次のように ７÷５＝１ あまり ２ ＜＝＝ ４０÷７＝５ あまり ５ ， （２，５）
｜２｜ ｜６ −１｜ ｜ ７｜
さらに、おたがいにわり算をすると、次のように ２÷１＝２ あまり ０ ＜＝＝ ５÷２＝２ あまり １ ， （０，１）
｜０｜ ｜５ −２｜ ｜２｜
（２）（３）より
｜０｜ ｜５ −２｜ ｜６ −１｜ ｜ ７｜ 行列のかけ算をすると
｜０｜ ｜ ４０ −７｜ ｜ ７｜
これから、 １ ＝ （−１７）×７ ＋ ３×４０ ・・・ （５） さて、（１）と（５）をみくらべて、さらに （−１７＋４０）×７ ＋ （３−７）×４０＝１ これで、□は２３、○は４とわかりました。 つまり公開鍵７ の逆の数、つまり 秘密鍵□は ２３ です。 しつこくいうと、７ と ２３ は かけ算して４０でわったあまりが １ です。 ですから、３×７×２３ を４０でわると あまりは もとの ３ にもどります。
● 公開鍵と秘密鍵 ● さて、表で 公開鍵７ の秘密鍵は２３ でしたね。 ７×２３ を ４０ でわると あまりは １ です。 このことを、記号で次のようにあらわします。 ７×２３≡１ （mod ４０） ４０でわったあまりの世界では、７×２３ は １ になるのです。 ちなみに、１ は かけてももとどおりになる、とくべつな数です。 もちろん、反対に公開鍵を２３ にすると 秘密鍵は７ です。 ２３×７ を ４０ でわると あまりは やっぱり １ ですから・・・。 ２３×７≡１ （mod ４０）
Ｙ ５ ７ １ ３
＜かけ算＞ せっかくですから、のこりも全部もとめてみましょう。 え〜っ！ユークリッドの互除法をいちいちやってみるの？ ごしんぱいなく！そのために、さんすう・数学があるのですから・・・（？）
Ｙ ５ ７ １ ３
まず、この表の２つの数をかけ算したら、 さて、この表は Ｘ と Ｙ のまじわったところに ８Ｘ＋５Ｙ を計算して、４０でわったあまりを書きこんで作ったものでした。 そこで、８X１＋５Y１ と ８X２＋５Y２ をかけてみます。 （８X１＋５Y１）（８X２＋５Y２）＝６４X１X２＋４０X１Y２＋４０Y１X２＋２５Y１Y２ ４０でわりきれる項は、４０でわったあまりに関係しないってことで （８X１＋５Y１）（８X２＋５Y２）≡６４X１X２＋２５Y１Y２ （mod ４０） つまり、８X１＋５Y１ と ８X２＋５Y２ とをかけると ８×（８X１X２）＋５×（５Y１Y２） ですが、ここでこの表をつくったときのように ８X１X２ を５でわったあまり、 ５Y１Y２ を８でわったあまり を考えます。 ８ は５でわったあまりが ３ ですから、８ を ３ でおきかえて ３X１X２ を５でわったあまり、 ５Y１Y２ を８でわったあまり となります。 たとえば、 ７≡４×８＋３×５ ， ２３≡１×８＋３×５ をかけると、 ３×４×１ を５でわったあまり ２ ， ５×３×３ を８でわったあまり ５ ということで、表で Xが２、Yが５ のところを見ると、１ です。 つまり ７×２３≡１ （mod ４０） です。 ＜逆元＞ では、公開鍵 ８X＋５Y の秘密鍵 □×８＋○×５ はどうなるでしょう。 ４０でわったあまりの世界で、かけて １ になるのですから ３×X×□ を５でわったあまり ２ ， ５×Y×○ を８でわったあまり ５ となる、□と○をもとめます。 記号であらわすと ３×X×□≡２ （mod ５） ， ５×Y×○≡５ （mod ８） となる、□と○をもとめます。このことから、 X×□≡４ （mod ５） ， Y×○≡１ （mod ８） さて、それぞれの X や Y で □ や ○ をもとめましょう。 X＝２，４，１，３ では、 ２×２≡４ （mod ５） Y＝１，３，５，７ では １×１≡１ （mod ８）
＜公開鍵と秘密鍵＞ これで、表の公開鍵の秘密鍵が全部わかりましたね。
表の見方は、公開鍵が１７なら、その秘密鍵は３３です。 でも、よく考えてみるまでもなく、 ですから、 １ １１ ２１ ３１ ９ １９ ２９ ３９ は、けっきょく公開鍵としては使い物になりませんね。
今回は鍵のお話でした。 掲載内容の無断転載、転用、編集を禁じます。(c)
小林吹代 |