カードマジックと素数時計の謎〜暗号の仕組み”その４”

　前回｢その3｣では､RSA暗号の秘密の鍵である2つの素数pとqからなるN(=pq)時間の時計計算機について､まず説明しました。
　一方で､RSAアルゴリズムの起源となる｢フェルマーの小定理｣はオイラーが一般化した事で､｢オイラーの定理｣とも呼ばれます。
　その後1977年に､RSA暗号の発見者の1人であるリヴェスト(R•L•Rivest)が､時計計算機を使ってRSA暗号を完成させます。
　因みに､素数時計(p時計計算機)とは､xᵖ≡x(mod p)なる｢フェルマーの小定理｣の事で､”p乗すれば常に元の時間xに戻る”事を意味する。故に､N時間時計のパターンを知るには､素数pとqを知る必要があり､この”2つの素数こそがRSAの秘密を解く鍵”となる。

　次に､RSA暗号システムの起源と歴史について述べましたが､RSA暗号の安全性は素因数分解の難しさに依存し､この困難さは長い間数学者を悩ませてきた。
　更に1977年までは､秘密のメッセージを送ろうとすると､送り手と受け手の間で暗号化の方法を打ち合せをする必要があった。かのエニグマでさえ､コード表が漏れれば一巻の終りだ。
　そこで数学者らは､世界中を網羅する高速ネットワークに対応する､新しい暗号システムを開発する必要に迫られた。
　つまり､エニグマを開発したのが数学者なら､スパイ小説に登場する様な次世代の暗号法を現実に持ち込んだのも数学者だった。こうして作られたのが､RSAの”公開鍵”暗号システムである。
　因みに”公開鍵”暗号とは､2種類の鍵(暗号化Aと復号化B)がついたドアの様なもので､ドアを閉める時はAの鍵を､開ける時はBの鍵を使う。つまり､鍵Aを秘密にする必要はなく､たとえ鍵Aを持ってても侵入できない。
　例えば､カードなどの個人情報を暗号化する鍵Aは皆同じで公開されても､暗号化されたら皆読めなくなる。一方､鍵B(復元キー)を持ってるのは運営する企業だけで､ドアを開けてカード番号を読む事が出来る。
　こうして暗号を敢えて公開する事で､電子セキュリティーの新時代が幕開けする事になる。この新たなる夢の様な暗号理論は､3人の若き大学院生に受け継がれ､大きな華を咲かせるのである。

　そこで今日は､RSA暗号システム誕生の裏側と素数時計とカードマジックを使い､その仕組みを紹介します。
　以下､前回の後半同様に｢素数の音楽｣(M･D･ソートイ著)の第10章｢因数分解と暗号解読｣を中心に纏めます。

3人の若き研究者たち

　この素因数分解の困難さを利用したRSA暗号ですが､発明した3人の名前､”R.L.Rivest､A.Shamir､L.Adleman”の頭文字に由来する。
　当時､”暗号法は何たるべきか？どうあるべきか？”というデフィーとヘルマンの論文に刺激されたMIT大学院生のロン•リヴェストは､コンピュータ科学のプログラム理論の高度な分析に興味を覚えていた。　
　チューリングの時代は､”理論上のある種の問題を解くプログラムが存在するのか？”という問いが､コンピュータ計算における大きな問題になってた。が､チューリングが示した様に､数学的な真理が証明可能かどうかを判別する事はどんなプログラムを持ってしても不可能であった。
　しかし1970年代に入ると､ある数学の問題を解くプログラムが存在すると仮定し､”そのプログラムで問題を解くのにどれ位の時間がかかるのか？その速度を解析するのは可能か？”とした問題が議論される様になる。

　チューリング同様､コンピュータと数学の抽象理論の結びつきに興味を抱いてたリヴェストだが､上の問題は非常に高度な理論分析を必要とするが､現実に根ざした問題にも映った。
　そこでリヴェストは”解くのが難しい暗号は計算が難しい問題に基づく”と考えた。彼はコンピュータで長時間掛けなければ解けないとされる様々な問題を使い､”公開鍵暗号”を作り始める。
　やがて､彼の近くの部屋にいた2人の数学者のレオナルド･アルドマンとアディ･シャミアも彼の研究に興味を持ち､加わっていく。

　まず､リヴェストの研究に興味を示したシャミアは､デフィーとヘルマンの夢を追いかけ､2人で幾つものアイデアを探し始めた。一方､当初はそれほど感心のなかったアドルマンだが､数論を得意とする彼が黙ってる筈もない。まだ形を成さなかった暗号システムに数論のアイデアをはめ込んでいく。
　つまり､暗号システムを分析する上でアドルマンの貢献は不可欠であり､この数論の力で最新の暗号を解く方法を見つけ出すのだ。
　リヴェストとアルドマンは素因数分解という難問について考えていたが､当時は素因数分解を解くプログラムは見つかってはいなかった。
　が､八方塞がりで､酒に酔ってたリヴェストだが､この素因数分解の問題を暗号にどの様に組み込めばよいのかをとうとう発見する。
　”最初からこういう予感はしてたんだ。でも最後には駄目になる事もよくある事だから､ずっと懐に温めておいたんだよ”
　リヴェストは､完成した自身の原稿に3人の名前を大きく記した。が､それを見たアドルマンは”これは君の素案だ。自分の名前は一番最後に回してくれ”と言った。結局､この暗号システムは”RSA”と呼ばれる事となる。　　

　当時は､因数分解について詳しくは解ってはいなかったし､文献も殆どなかった。故に､素因数分解を正当に評価するのは困難だった。
　そこでリヴェストは､優秀なハッカーらにとって”素因数分解がどれほど難しいか”を数学の伝道師であったマーチン･ガードナーに評価を依頼した。
　ガードナーが彼らのアイデアを記事にしてくれたお陰で､RSA暗号の理論はアメリカだけでなく､世界中に大きな反響を巻き起こす。だが､国家安全局や実業界がセキュリティやRSA暗号を完全に理解するには､もう少し時間がかかる事となる。というのも､80年代初頭はコンピュータはまだまだネットワーク化されておらず､机の上にすらコンピュータがなかった時代だったのだ。

　保安当局は､因数分解が難しいと考える3人の若き数学者の手に､諜報員の命を委ねていいものか？決めかねていた。
　一方で､唯一興味を示していたドイツ情報安全局(BSI)も”西側は数学の分野でソ連に勝ってるのか？”と訊ねた所､”いいえ”という答えが返ってきたので､RSA案の採用を棚上げにしたという。
　しかし､それから10年も経たない内に､RSAはスパイの命を守るだけでなく実業界でも有用だという事が証明されたのである。
　

ガウスの素数時計とフェルマーの発見

　現在のネット上での取引の殆どがRSAによって守られてる。そして､この公開鍵暗号システムの源を遡ると､前回｢その3｣でも紹介した｢フェルマーの小定理｣と”ガウスの時計計算機”に行き着く。
　ガウスの時計計算機とは､通常の12時間時計での計算と同じで､9時の4時間後は1時になる。これを時計計算機で言えば､9と4を足した数を12で割った余りが1となる。
　これをモジュール”mod”(法)を使って記せば､4+9≡1(mod 12)となる。因みに”mod”とは､1801年にガウスが発見した”合同算術”であり､整数論を大きく飛躍させたが､勿論ガウスは､12という時間に拘る必要がない事も最初から判っていた。

　一方でフェルマー(仏､1607-1665)は､この時計計算術について既に基本的な発見をしてた。つまり､素数p時間の時計計算機に関する｢フェルマーの小定理｣である。つまり､素数計算機でp乗すれば常に元の時間に戻るのだ。
　例えば5時間時計では､2を5乗すると32だが､5時間時計では2時になる。2時から始め､2を掛ける度に時計の針が一定のパターンを描き(2→4→3→1→2→4→3→1→2→4→⋯)､針が5回動いた所で元の位置に戻り､延々と同じパターンを繰り返す。
　13時間時計を例にとれば､3時から始めても3→9→1→3→9→1→3→9→1→3→9→1→3→⋯と一定のパターンのあと､13乗した所で3時に戻る。
　つまり､どんな素数pをとろうが､ガウスの時計算術”mod”を使えばだが､どんな時間xに関しても､p時間時計ではxᵖ≡x(mod p)なる事にフェルマーは気づいてた事になる。

　事実､1640年にフェルマーは､友人宛の手紙でこの証明に成功したと書いた。が､完全な証明を書くには手紙では短すぎた。結局､証明は未完のままに終わったが､この証明が再発見されたのは､100年後の事である。
　事実､1736年にオイラーは､フェルマーの素数時計の針の謎を解明しようとする。
　何故､素数乗した時に最初の点に戻るのか？
　そこでオイラーは､フェルマーの発見をN=pq時間(p.q:素数)の時計計算機に一般化する。つまり､N時間時計では､N(=pq)番目ではなく"(p−1)(q−1)+1"番目でパターンを繰り返す事に気付いた。
　事実､p=2,q=3の時はN=6で､5時から始めると､5,25,125,625,3125,,,≡5,1,5,1,5,,,(mod 6)となり､(2−1)(3−1)+1=3番目毎にパターンを繰り返す事が判る。
　

カードマジックの複雑で愉快な仕組み

　夜遅くまで新たな暗号システム”RSA”の考えに耽ってた前述のリヴェストだが､頭の中にはフェルマーによる素数時計の不思議の発見とオイラーによるその一般化で一杯だった。
　つまり､｢フェルマーの小定理｣を鍵として数学的な暗号を作れば､カードをさっと消して再び魔法の様に取り出せる事に気づき始めていた。
　即ち､カードマジックの様に､カードをシャッフルしてクレジット番号を暗号化するのだ。しかし､ここで使うのは52枚のカードではなく､書き下したら100桁以上になる膨大な枚数のカードを使い､買い物客のクレジット番号をこれらのカードに混ぜ込む。

　例えば､買い物客がクレジット番号をこのカードの山の一番上に置くと､ショップサイトはカードをよく切り､買い物客のカード番号が何処にあるか判らなくする。
　お陰でハッカーは､ごちゃまぜになったカードの束から1枚のカードを取り出すという殆ど不可能な作業に直面する。
　しかしショップサイト側は､｢フェルマーの小定理｣とオイラーのお陰で､更に何度かシャッフルすれば､買い物客のクレジット番号を再びカードの山の一番上に出す事が出来る。そして､カードを一番上に持ってくる為の”シャッフルの回数”こそが､ウエブサイトを運営する企業だけが知る”秘密の鍵”なのである。

　ここでリヴェストは､この暗号のトリックを作る為に､実に簡単な数字を使った。カードを切る代わりに､ある計算を施すのだ。
　買い物客がWebで注文すると､コンピュータは客のクレジット番号にこの計算を施す。簡単な計算だが秘密の鍵を持ってないと､この計算を元に戻す事はまず不可能だ。というのもこの計算は普通の計算ではなく､前述のガウスの時計計算機を使うからだ。
　実際に､ネット上の会社はWebで注文を出した客に､時計計算機が何時間かを伝える。この時間数を決める為に､ます60桁ほどの2つの素数p､qを選ぶ。
　次に､3つ目の数であるN(=pq)を作る。故に､N時間時計の盤面は120桁に上る巨大な数になる。故に､どの顧客も全く同じこのN時間時計を使い､クレジット番号を暗号化する。
　つまり､暗号の安全性(堅固性)が高ければ､企業は時計の盤面を変える事なく､同じ時計を何ヶ月も使い続けられる。

　即ち､時計計算機の盤面の時間Nを選んだ事で､公開鍵の片方(暗号鍵)が決まる。つまり､Nという時計番号は公にされるが､素数p､qはあくまで秘密で､この2つは暗号化されたクレジット番号を元に戻す為の”復元”鍵になる。
　次に､顧客全員が”暗号化”鍵と呼ばれるもう1つの数eを受け取る。この暗号鍵eは全ての顧客に共通で､時計盤面の時間数Nと同じく公にされる。
　つまり顧客は､クレジット番号Cをウエブサイト上の公の時間計算機を使ってe乗し､暗号化する。因みに､eという数は手品師が相手が選んだカードを隠す為にシャッフルする回数にあたる。
　以上で得られる暗号化された番号Mを､ガウスの時計計算を言えば､M≡Cᵉ(mod N)となる。

秘密の素数と復号鍵

　しかし､この単調な計算式のどこが安全なのだろうか？
　Web上を行き交う暗号化されたクレジット番号Mや､それに企業の公開鍵である時計計算機の時間数Nもクレジット番号の累乗数eという”暗号化鍵”の値も調べさえすれば判る。
　従って､N時間の時計計算機でe乗して暗号化されたクレジットカード番号を見つけ出せば､暗号は解ける筈だ。
　しかし実際には非常に難しい。しかも､累乗計算を時計計算機で行ってる所がミソなのだ。普通の計算機ではカード番号を累乗する回数が増えるにつれ値が大きくなるが､時計計算機で弾き出す値は元の数の大きさとは全くの無関係で､じきに元の数が何だったのかわからなくなる。つまり､カードをe回もシャッフルされたら､ハッカーは無関係な数字を見せつけられ､途方に暮れるしかない。

　ならば､可能性のある素数p､qをシラミ潰しにあたるというのはどうだろう？つまり､強引に秘密の鍵を暴くのだ。
　しかしそれも不可能だ。時計計算機の盤面の時間Nは100桁を超える。つまり､盤面の時間数が宇宙全体の原子数を超えてるのだ。これに対し､暗号化鍵eは極めて小さい数ではある。
　でも､ウエブの運営会社はどうやって顧客のクレジット番号を見つけるのだろうか？

　リヴェストは｢フェルマーの小定理｣により､復号鍵dの存在が保証される事を見抜いてた。つまり､運営会社が暗号化された顧客のクレジット番号をd乗すると､再び元のカード番号が現れるのだ。
　これはカードマジックと全く同じ手法で､手品師は顧客がe回シャッフルし､順序がデタラメになったカードをあと何回シャッフルすれば元に戻るかを知っている。その回数dこそが”復号鍵”なのだ。
　つまりリヴェストは､この手品師の技をRSAのメッセージ解読に活用したのである。

　しかし､秘密の素数pとqを知らない限り､復号鍵dを求めるのは不可能だ。
　そこでリヴェストが使ったのが､｢フェルマーの小定理｣のオイラーによる一般化(｢オイラーの定理｣)である､2つの素数pとqからなる時計計算機だった。
　このN(=pq)時間時計では､”(p−1)(q−1)+1”回シャッフルした時に､再び同じパターンが繰り返される事は(前述の様に)オイラーにより示されてた。
　これは､ある数をxとすると､x^((p−1)(q−1)+1)=x(mod N)とガウス的に記述でき､xを”(p−1)(q−1)+1”乗すれば､常にxに戻る事を意味する。
　故に､このN時間時計のパターンを知りたければ､素数pとqを知る必要があり､この2つの素数こそがRSAの秘密を解く鍵となる。

　つまり､クレジットカード番号Cを顧客がe乗して暗号化された番号Mを､会社側が更にd乗し､元のカード番号Cに復元する。
　これを復号鍵dと暗号鍵eを使い､ガウスの時計計算で記述すれば､M≡Cᵉ(mod N)とC≡Mᵈ(mod N)となる。つまり､C≡Cᵈᵉ(mod N)が成り立つ筈だ。

　｢その3｣でも詳しく述べたが､この証明は､まずdをφ(N)以下のφ(N)と互いに素な自然数とすると､φ(N)を法(mod)としたeの逆数と定義すれば､d=e⁻¹(mod φ(N))と出来､de≡1(mod φ(N))ー①を得る。但し､φ(N)は”オイラー関数”と呼ばれ､N以下のNと互いに素な数の個数の事です。
　①より､deをφ(N)で割った余りを1､xを整数商とすれば､de=xφ(N)+1となり､Cᵈᵉ(mod N)≡Cᵠ⁽ⁿ⁾⁺¹(mod N)となる。　
　ここで｢オイラーの定理｣により､Nと互いに素なC(gcd(N,C)=1)に対し､Cᵠ⁽ⁿ⁾≡1(mod N)となり､Cᵠ⁽ⁿ⁾⁺¹=1ˣ•C=Cを得る。但し､gcdは”最大公約数”の事です。
　故に､C≡Cᵈᵉ(mod N)が示せた(証明終)。

　また､NとCが互いに素でない時(gcd(N,C)=p又はq)も､上の等式が示せる。
　ここで､pとqは互いに素より､φ(N)=φ(pq)=φ(p)φ(q)=(p−1)(q−1)となり､故にφ(N)=(p−1)(q−1)が求まりさえすれば､φ(N)とeが互いに素になる様なeがとれ､①式は”1次不定方程式(2変数d,xを持つ1次方程式)の解法”より､復号鍵dが求まる仕組みだ。

RSA暗号の仕組みとそのカラクリ

　従って､ネット上の会社は2つの素数p,qを極秘にしてるから､クレジット番号を復元する復号鍵dを知るのは会社だけとなる。
　一方で､pとqは秘密だが､Nは公にされてる。たとえ､クレジット番号Cや暗号鍵eが盗まれたとしても､2つの素数pとqがなければどうしようもない。
　故に､RSA暗号のセキュリティは”Nを素因数分解する事が困難だ”という事実に掛っている。
　そこでハッカーは､Nという数の2つの素因数を見つける難題に直面する。上で述べた様に､Nが大きくなる程に素因数分解は事実上不可能になるからだ。

　では､RSA暗号システム内で具体的にどの様な事が起きているのか？
　そこで､p=3,q=11という超簡単な素数で説明しよう。まず､クレジットカード番号を暗号化する時に使う時計計算機の盤面は3×11=33となる。勿論､pとqは極秘だが､暗号化する為の鍵eを知らせる必要がある。従ってe=7とすると､カードで買い物をする人は33時間時計を使い､カード番号を7乗する必要がある。
　仮に､カード番号Cを(簡単の為に)2番だとする。つまり､33時間時計では2を7乗して29時という暗号化された数を得る。
　但し､33時間時計で2⁷=128を計算する方法だが､5時間及び13時間時計の例で説明した様に､2→2²=4→2³=8→2⁴=16→2⁵=32と進み､2⁶=64では1回転を優に超えるが､これを逆周りで考える。
　つまり､2⁵を32＝33−1として”−1時”とみなし､2⁶=64=2(33−1)=2×33−2となり”−2時”と､2⁷=2²(33−1)=4×33−4となり､”−4時”とみなせ､33−4=29を得る。
　因みに､ガウスの”mod”法を用いれば､カード番号C=2を33時間時計で暗号化された数は､29≡2⁷(mod 33)となる。

　ここで､顧客が暗号化して得た29という番号が安心だと断言できるのか？
　ハッカーはサイバー空間でこの番号を見れるし､33時間時計とカード番号を暗号化する為に7乗する､2つの数字N=33とe=7は公開され､簡単に突き止める事が出来る筈だ。勿論､これだけの条件が揃えば､33時間時計で7回掛けて29になる数字を探せば済む事だ。
　だが､事はそう単純ではない。2乗3乗程度の計算ならバカでも出来るが､逆演算の平方根の計算となると桁違いに困難になる。しかも､RSA暗号では時計計算機を使い､冪(べき)を計算する為に事は益々厄介になる。
　つまり､計算で得られた答えの大きさと､元の数の大きさとが全くの無関係になるので､ハッカーは益々混乱する。

最後に

　但し､この例では超簡単な数なので､シラミ潰しに調べれば､解読は不可能じゃない。だが､実際にウエブで使われてるN時間時計はNが100桁を超え､33時間時計ですら難しいのに､解読なんて夢のまた夢であろう。
　だが､ネット上で商売する業者はどうやってクレジットのカード番号を復元してるのだろうか？
　実は上述の様に､｢フェルマーの小定理｣を一般化した｢オイラーの定理｣により､解読番号dが必ず存在する事が知られている。つまり､dの値はpとqを知る者のみが秘密のN時間時計計算機を使い､解く事を可能にする。
　一方で､カード番号Cを顧客がe乗して暗号化された番号Mを､会社側が更にd乗し､元のカード番号Cに復元する。これを”復号鍵dと暗号鍵eを使い､ガウスの時計計算で記述すれば､M≡Cᵉ(mod N)とC≡Mᵈ(mod N)となり､C≡Cᵈᵉ(mod N)が成り立つ筈だ”と書いたが､その判り易い説明になってる事にも留意したい。

　以上より､我々が安心してクレジットカードで買い物を出来るのも､こうした神秘な素数の手品が数学の力を使い､水面下で鮮やかに行われているのである。
　かなり長くなりましたが､RSA暗号の仕組みを魔法の素数時計とカードマジックを使って説明しました。
　こうしてみると､暗号とはいえ堅苦しく考えるよりも､”素数による魔術”とみなした方が身近にも思えますね。

素数の音楽 (新潮文庫) マーカス デュ・ソートイ 新潮社