数学Ⅰ＋Ａなんて人生に必要ないと思った人のための数学のはなし

今回は前話の公開鍵暗号について、数学的なはなしをします。
前話の図では鍵と宝箱のイラストで公開鍵暗号を表しましたが、
実際コンピュータにおいては、伝えたい数字をある数字（鍵）を用いた数式で変換するという
暗号方法が使われます。

もちろん、とっても頭のいい人たちが考えたんですが
複雑難解な数式ではなく、
基本は割り算の余りの計算と素因数分解。

つまり、とにかく余りの計算をして、
素数が持つ性質を活用することによって
公開鍵暗号が作れます。

素因数分解は実生活に役に立たないけど、
素数が持つフシギな力はインターネットの安全を守ってるということです。

＊　　　　　＊　　　　＊

以上！ここで終わってもいいのですが、
以下オマケ、一応具体的な説明を。

まず、この現実世界において数は１、２、３、４、...と続いていきますが、
ある数で割った時の余りを答えとする特別な世界を考えます。
ある数nは素数ｐ×素数ｑでできた数であることが必須です。

ここでは例として、ある数nを33とすると、
3の1乗=3、3の2乗=9、3の3乗=27、
そんで、3の4乗=81ですが、33で割ると余りが15となるので、
3の4乗=15となるような世界です。

それを下記のように表にしてみると
素数がもたらす性質が見えてきます。



なんと11乗と21乗で元の数に戻るんです。
一般化すると、（p-1とq-1の最小公倍数）×n+1 のべき乗の時に元の数に戻ります。（n=1,2,3,...）
p=3、q=11の時は、p-1とq-1の最小公倍数は10なので、
11乗、21乗、31乗...の時、元の数に戻ります。

この性質を利用して、公開鍵暗号は作られてます。
例として5という数字を伝えるとするなら、
まず公開鍵A=3で暗号化してもらい、
そしてその暗号化された数字26を、全体として21乗になるように、
つまり、7乗すると（秘密鍵B=7）、元の数5を手に入れることができるのです。

通常なら3乗した数字を逆算して元の数は割り出すことができますが、
余りを答えとするこの特別な世界では逆算もできません。

 

この時、公開されてるのは
素数の積nと公開鍵A。
秘密にしておかなきゃいけないのが、
素数p・qと秘密鍵B。

もし素数p・qがわかれば、公開鍵Aから計算して
秘密鍵Bを発見することができちゃいます。

ここでポイント。

素数p・qは秘密にしておかなきゃいけないのに、
素数の積nは公になってるところに注目です。

たしかに今回例にした33であれば、
容易に3×11と分かっちゃいますが、
実際の公開鍵暗号では数百桁の巨大素数を使用します。

この時、素数の積から元の素数を見つけ出すための
現実的効率的な方法が無いのです。
100桁ぐらいなら相当頑張ればなんとか時間かけて
計算できるそうですが、
300桁以上の巨大素数を使うと、
そこらへんの家電量販店にも売ってないような高性能コンピュータを
何千年稼動させても答えが出ないんだそうです。

Q.247867を素因数分解せよ。

東大入試にこれを混ぜといたらおもしろい。
一見簡単そうやけど、たぶんほとんど解ける人はいない。
あ、やっぱり東大生ならこれぐらいなら解きそうやな。
でも普通はむずかしいですよね。
2でも3でも5でも7でも11でも13でも17でも...割れないと
なってくるともう嫌でうｓ。

A.311×797

逆に311×797=247867を計算するのは簡単ですよね。


暗号を解く方法がわからないんじゃなくて、
暗号を解く方法はわかってるけど、
解くための現実的な効率的な方法がないってのが
この公開鍵暗号のミソですよね。スバラシイ。


※数字表は『暗号理論』（伊藤正史・著、ナツメ社）に書かれている表を拝借しました。
自分で他の素数の場合の表を作ろうとしましたが、 必要な計算がエクセルの能力を
超えてしまい、作れませんでした。

▼オススメ＆参考図書

暗号... 著者：伊藤正史 価格：1,365円（税込、送料込） 楽天ブックスで詳細を見る	5分でたのしむ数... 著者：エアハルト・ベ-レンツ 価格：2,310円（税込、送料込） 楽天ブックスで詳細を見る