No85 https その６ (公開鍵暗号２)

2021年11月14日 19:33

※この記事は 2018年11月に配信したものですが、No234の理解の一助となるかと思い、アップするものです。

前回は、公開鍵暗号という不思議な暗号化方式の概要とその代表例
であるRSA方式での暗号化と復号の計算方法について解説をしました。

今回は、前回触れなかった暗号鍵と公開鍵の関係、そしてその逆算
が難しいことについて解説をします。

1. 前回のおさらい

公開鍵暗号方式では、公開鍵と暗号鍵というものを使って計算を
します。

RSA暗号では「元の数を掛け合わせてｎで割る。その余りを元の数
とする」といった計算を繰り返すといつか元に戻るという性質を
利用しています。

つまり、最初の暗号化では決まった回数だけ上記の計算をしたもの
を暗号文とし、それを元に戻す時も、同じ計算を決まった回数（暗
号化した時とは違う回数）だけ計算することで元の文に戻るという
仕組みです。

前回の計算例では、ｎ＝２２を使いました。

実はこの値は２つの素数の掛け算なのです。

素数というのは、１とその数字以外では割り切れない値です。
2,3,5,7,11,13 といった値が素数なわけです。

さて、ｎというのは２×１１です。
それ以外の正の整数の組み合わせでは２２になりません。

そして、暗号鍵は２回、復号鍵は６回でした。
この値＋１が計算上の鍵の値となりますので、暗号鍵は３で復号鍵
は７です。

このうち、公開鍵の値（７）は自由に選べます（多少の条件はあり
ますが）

この７からは、ｎを構成する２と１１という値がわかっていれば
カンタンに暗号鍵を求められます。

それは、
　(７＊暗号鍵)÷((２－１)（１１－１))
を計算し余りが１になる値です。

上記の例であれば、
（７＊３）÷((２－１)（１１－１)) ＝２１÷１０＝２…１
となりますね。

さて、こんなことを長々と書いたのは、これがRSA方式の鍵の安全
性を担っているからです。

上のおさらいでも示したように、復号はｎと公開鍵さえあれば可能
です。

でも、ｎと公開鍵があれば秘密鍵を計算できそうなものです。
ですが、上の式でわかるように、それにはｎを構成する２つの素数
の値を知らなければなりません。

もちろん、ｎが２２のように２ケタや３ケタの値なら２つの素数を
得るのもカンタンです。
ですが、巨大な数を素早く２つの素数に分解する方法を人類は見い
出していません。
ですので、ｎが６００ケタもあれば、どんな計算機をもってしても、
何億年もかかることでしょう。

もしｎを構成する２つの素数が何だったかわからなくなれば、ｎと
秘密鍵を持っていても公開鍵は事実上計算できなくなります。

だから、秘密鍵だけでなく、ｎを構成する２つの素数も同じくらい
大切に扱わなければいけない情報なのです。

なお、RSAの秘密鍵には、秘密鍵の他にｎや２つの素数情報も含ん
でいます。
RSAの公開鍵には公開鍵とｎの２つが含まれています。

このように、公開鍵暗号方式というのは鍵配送問題（詳しくは
「httpsその３（鍵交換）」2018/10/29配信をご参照ください）と
いうやっかいな課題をクリアした非常に優れた暗号化方式です。

では、この優秀な方式が登場することで、１つの鍵で暗号化も復
号も行う共有鍵暗号は使われなくなったのでしょうか？

いえいえ、RSA方式が1970年代に登場したにも関わらず、2001年に
はAES方式という新たな共有鍵暗号が制定されていますし、登場は
古くともRC4のように長く現役を勤めている方式もあります。

なぜ、不便なはずの共有鍵暗号方式が今も使われているのでしょう？

実は公開鍵暗号方式には避けがたい欠点があります。
それはやたらと計算に時間がかかるという点です。

現代のコンピュータにとっても数百ケタもの計算は負荷がかかり
ます。
１回や２回であればどうということはないのですが、
RSAの手順を見れば、暗号化にも復号にもとてつもない量の繰り
返し計算を必要とすることは明らかです。

計算量を減らす工夫は最大限施したとしても膨大な量の計算が必要
なのは間違いありません。
とはいえ計算量が多いということは、それを破ろうとする側にとっ
て、メチャクチャな計算量を求めることでもあるわけです。
計算量が多いことはむしろ安心料でもあるわけで、計算量が多い
ことが悪いわけではありません。

では、一体公開鍵暗号方式はどんな場面で使うのでしょうか？

これがhttpsのアイデアの根幹なのですが、公開鍵暗号方式は
共有鍵暗号用の鍵を暗号化する場面にのみ使います。
本来の暗号化したいやりとりは全て共有鍵暗号を使います。

つまり、httpsでは、公開鍵暗号と共有鍵暗号の両方を使い分けて
いるのです。

さて、ずっとおあずけになっているhttps本体のお話ですが、あと
一つお話しておかなければいけない大きなお話がありました。

サーバ証明書やクライアント証明書と呼ばれるデジタル証明書の
解説です。

実はこれについては、以前「本人認証の方法　その２」(2017/8/7
配信)　～「本人認証の方法　その４」(2017/8/28) でもお話しま
したが、改めて解説をしたいと思います。

これもまた数回に分けての解説となりそうです。

次回もお楽しみに。

この記事が気に入ったらサポートをしてみませんか？