RSA暗号の起源と素因数分解の罠〜暗号の仕組み”その３”

　約3年ぶりの”暗号の仕組み”ですが､素数の謎を調べてる内に､RSA暗号システムの事を思い出し､書き溜めてた記事を紹介したいと思います。
　｢その1｣では､暗号の仕組みを”同型写像”と”mod演算”(剰余計算)を使ったやり方で紹介しましたが､少し抽象的すぎて理解するに無理がありました。
　｢その2｣では､その仕組みを例をあげて紹介しました。以下､軽くおさらいをします。

　まずは､前もって公開鍵と秘密鍵を作成し､事前に公開鍵を公開する。そこで､公開鍵として適当な正の整数e(通常は小さな数=65537=2¹⁶+1)を割り当てる。
　200桁ほどの十分に大きな2つの素数p､qを用意し､それらの積N=pqを求め､{e,N}を暗号化に使用する公開鍵とする。
　2つの素数p､qは､暗号文の復号(復元)に使用する秘密鍵dの生成にも使用し､d≡e⁻¹(mod (p−1)(q−1))とし秘密裏に保管する。de≡1(mod (p-1)(q-1))の方が判り易いですかね。これは､deを(p-1)(q-1)で割ると1余る事(剰余)を示します。
　ここで､暗号化(暗号文をC)する平文をMとすると､暗号化はC≡Mᵉ(mod N)で与えられ､復号化はM≡Cᵈ(mod N)で与えられる。
　つまり､平文Mの各要素をe(公開鍵)乗し､Nの余りを計算する事で暗号化出来て､暗号文Cの各要素が求まる。又､暗号文Cの各要素をd(秘密鍵)乗し､Nで割った余りを計算する事で復元出来る。
　うーん､難しいですかね・・・

　以下でも述べるが､RSA暗号の発見者の1人であるリヴェスト(R•L•Rivest)が使ったのが､”フェルマーの小定理による一般化”(オイラーの定理)である､2つの素数pとqからなる時計計算機でした。
　このN(=pq)時間時計では､”(p−1)(q−1)+1”回シャッフルした時に､再び同じパターンが繰り返される事は､オイラーにより示されてました。
　これは先述した秘密鍵dが､de≡1(mod (p−1)(q−1))≡1(mod φ(N))を満たす事を示しています。｢フェルマーの小定理｣がRSA暗号に繋がるとはこういう事ですね。
　因みに､”p時計計算機”とは､xᵖ≡x(mod p)なる｢フェルマーの小定理｣の事で､この計算機では”p乗すれば常に(p時計では)元の時間xに戻る”事を意味します。
　例えば5時間時計では､2を5乗すると32で､5時間時計の2時にあたる。2時から始め､2を掛ける度に時計の針が一定のパターンを描き(2→4→3→1→2→4→3→1→2→4→•••)､針が5回動いた所で元の位置に戻り､延々と同じパターンを繰り返す。
　故に､このN時間時計のパターンを知りたければ､素数pとqを知る必要があり､この”2つの素数がRSAの秘密を解く鍵”という事になる。
　うーん､少し判ったかのような・・・

ユークリッド互助法と一次不定方程式

　一方で､暗号化はe(公開鍵=e乗)とNがあれば容易に計算できるが､復号化には､d(秘密鍵)を求める必要があり､それにはNの素因数であるpとqを知らないとキツイ。
　これは大きい数の素因数分解が難しい事に起因する。つまり､秘密鍵dを用いずに暗号文Cから平文Mを得るのは不可能で､これこそがRSA暗号の安全性の根拠となる。

　RSA暗号の仕組みで言えば､鍵生成と暗号化と復号の3つのアルゴリズムで定義され､最初の鍵生成が一番困難です。
　前述したN=pqを用意し､dをφ(N)を法(mod)としたeの逆数とし､de≡1(mod φ(N))とする。
　この時､pとqは互いに素な素数より､φ(N)=φ(pq)=φ(p)φ(q)=(p−1)(q−1)。因みに､オイラーのφ(N)関数とは､1からNまでの自然数の内で､Nと互いに素な数の個数の事です。
　すると､deをφ(N)で割った余りをx(整数商)とした時､deｰxφ(N)=1ー①が成立し､φ(N)関数の性質から､gcd(e,φ(N))=1なるeがとれるので､①式の様な”1次不定方程式(2変数d,xを持つ1次方程式)の解法”より､秘密鍵dが求まる。但し､gcdは”最大公約数”の事です。
　つまり､公開鍵eとφ(N)=(p−1)(q−1)が判れば､”ユークリッドの互助法”からgcd(e,φ(N))=1なる公開鍵eが求まり､①の”1次不定方程式”の解法から秘密鍵dが求まる。
　但し､eを公開鍵としてNと共に事前に公開するが､pとqは絶対に漏らさないという事が前提となる。　

　因みに､(前回説明を省略した)”ユークリッドの互助法”ですが､aをbで割った余りをr(a=r(mod b)とすると”gcd(a,b)=gcd(b,r)”が成立し､これを繰り返し使い､a,bの最大公約数を素早く求める方法です。
　例えば､390と273の最大公約数を求める時､まず､390 を273で割ると､商が11で余りが117。つまり､390=117(mod273)となるより､gcd(390,273)=gcd(273,117)を得る。
　次に､273を117で割ると､273=39(mod117)となり､gcd(273,117)=gcd(117,39)を得る。
　最後に､117は39で割り切れるので､gcd(117,39)=0より､390と273の最大公約数は39となる。
　素因数分解を利用し最大公約数を求める事も出来るが､大きな数となると素因数分解よりも割り算の方が圧倒的に楽なので､こうした”互除法”が用いられる事が多い。

　一方で(こっちの方がずっと有用だが)､ユークリッドの互助法は”一次不定方程式の解法”に用いられる。
　そこで､一次不定方程式ax+by=1の整数解(x,y)を求める問題を考える。
　例えば､8x+11y=1で11と8に互助法を適用する。11=8⋅1+3､8=3⋅2+2､3=2⋅1+1。
　これを順に遡っていく(余りの所を順に代入していく)と､1=3−2⋅1=3−(8−3⋅2)⋅1=3⋅3+8⋅(−1)=(11−8⋅1)⋅3−8=8⋅(−4)+11⋅3を得る。これは､8x+11y=1の形となり､(x,y)=(−4,3)が解の1つになる。
　よって､一次不定方程式ax+by=cの整数解の1つが見つかれば､一般解が構成できる。因みに､8x+11y=1の一般解は(x,y)=(−4+11n,3−8n)となる。
　以上､ユークリッドの互助法を使った一次不定方程式の解法でした。

　前回｢その2｣のほぼパクリでしたが､RSA暗号の仕組みを大まかにおさらいしました。
　実際には､RSA暗号表で使う”乗数の表”を用意し､本来なら200桁程のとても大きい2つの素数p,qを掛けた数字で割った余り(mod)を表にします。前回では､p=5とq=17というとても簡単な例を挙げて､わかり易く説明しました。
　そこでは､RSA表の横軸をN､縦軸をX(累乗数)とし､自然数NのX乗をpq=85で割った余り(1≤Nˣmod85≤84)を表に埋め込んでます。
　暇な人は(多分いない)､少し数値を変えてトライしてみれば､RSA暗号の本質が実感できる筈です。
　

RSA暗号システムの起源

　RSA暗号とは､桁数が大きい合成数の素因数分解が現実的な時間内で困難である事を”安全性の根拠”とした公開鍵暗号の1つで､暗号とデジタル署名を実現できる方式として最初に公開されたものです。
　RSA暗号方式は1977年に発明され､ロン･リヴェストら若き大学院生の3人の発明者の頭文字を繋げて名付けられた。前年(1976年)にディフィーとヘルマンによって発表された公開鍵暗号という新しい概念に対し､秘匿や認証を実現できる具体的なアルゴリズムを与えた。これがフェルマーの小定理に基づく事は先にも述べた。

　実は､暗号に革命を起こした最初の発案者はジェイムズ･エリスとされる。彼はイギリス最高機密機関である英国政府通信本部(GCHQ)の職員で､その独創的な先見の明は内部文書として長い間公開されなかったし､また実用にはコンピュータの性能等から機が熟していなかった。
　エリスは､1969年にこの理論を発見してたが､専門の数学者ではなかった為､具体的な方法を提示できなかった。また幾人ものGCHQの優秀な数学者が挑戦したが､この突拍子もない暗号のアイデアを実現する事は出来なかった。1973年､エリスの”一方向関数(非対称性鍵の概念)=公開鍵”を用いた暗号論の話を聞かされ､僅か30分程度で”モジュラー算術と素因数を用いた”具体的な方法を考案したのが､同じGCHQ所属の若き数学者クリフォード･コックスである。彼は上記のリベストの計算式と同じものを発見したとされる。
　しかし､エリスとコックスの業績は機密事項とされた為､1997年までは世に知られる事はなかった(ウィキより)。

　例えば､大きな数字を素因数分解するのはとても困難で､総当りする以外に素因数を見つけ出す方法はない。故に､コンピュータで素因数分解するとしても膨大な時間が掛る。
　つまり､素因数分解の難しさこそがRSA暗号の安全性の根拠であり､逆に言えばコンピュータを使って膨大な時間を掛ければ､素因数分解すれば解読される。
　しかし､それまでには殆どの情報の価値が失われる為､暗号として機能する。

因数分解と暗号解読

2⁶⁷−1＝193707721×761838257287

　1903年､コロンビア大の数学教授フランク•ネルソン•コールは､かなり奇妙な講演を行った。
　黒板に､メルセンヌ数(2ⁿ−1の形の数)を1つ書き､その後､それより小さい2つの数の掛け算を書いた。最後に､この2つを等号で結んで､席に腰を掛けた。
　いくら20世紀初頭とはいえ､2つの数を掛け合せた事くらいで､満場の数学者が立ち上がる事はない。しかし､コールが成し遂げたのは”掛け算の逆”だったのだ。

　2⁶⁷−1という21桁のメルセンヌ数が素数ではなく”2つの数の積で表せる”事は､1878年以来の周知の事実であった。しかし､その2つの数がどんな数字なのか？誰も知らなかった。
　つまり､コールは長い時間を掛けて､この数を2つの素数の席に分解してみせたのだ。
　以下､｢素数の音楽｣(マーカス･D･ソートイ著)の第10章を参考にまとめます。

　この偉業を高く評価したのは､数学者だけではなかった。2000年にブロードウェイで上演された｢5人のヒステリックな少女たちの定理｣という難解な劇では､1人の少女がコールの数を因数分解する。
　数学者一家の旅を巡るこの劇では､素数が繰り返し話題に上る。例えば､父は娘が成人したと言って嘆く。恋人と駆落ち出来る年齢になったからではなく､”17は素数なのに18は4つの数で割り切れる”からだ。
　つまり､成人というのは全てを”割り切る”人間になるという事なのだ。

　全ての数が素数の積で表せるのは､2千年以上も前にギリシャ人によって証明されていた。しかし､どんな素数を掛ければいいのかを効率的に突き止める方法は､未だ見つかってはいない。
　数学者には､化学で使う”分光器”は存在しない。分光器さえあれば､ある化合物が周期表のどの元素から成り立ってるのか？突き止める事が出来る。一方で､数学版の分光器さえ発見され､素因数分解できる様になったなら､その発明は数学界の外からも称賛されたであろう。

　1903年当時､コールの計算は数学への好奇心の興味深い一例と見られていた。聴衆が総立ちになり拍手を贈ったのも､コールの途方もない労力を認めたからで､問題そのものが重要だと思った訳ではなかった。
　しかし今､この様な大きな数の因数分解は日曜の午後の暇つぶしどころか､暗号解読の核心となった。つまり数学者たちは､”素因数分解が難しい”という事実を利用し､ネット上に展開する国際金融の世界を守る暗号を作る方法を見つけたからだ。
　因数分解とは､単調で他愛のない作業に見えるが､100桁の数を因数分解するとなると､不可能と言える程に時間が掛かる。故に､銀行や電子商取引の関係者は､金融取引の際のセキュリティを”素因数分解が難しい”という事実に委ねる。
　この数学を使った新しい暗号のお陰で､暗号法に付き纏う”ある問題”が解決されるのだ。

ネット時代の暗号誕生と公開鍵暗号

　最も古い暗号システムは､2500年前にスパルタ人が編み出したとされる。
　つまり､我々の祖先はずっと昔から､重要なメッセージの偽装を考えてたのだ。
　送り手と受け手は､同じ寸法のスキュタレー(細い羊皮紙を螺旋状に巻き付けた円筒)を持ってる。
　まず送り手は､羊皮紙に長い筒に沿ってメッセージを書き､暗号化する。細い羊皮紙を円筒から外すと､書かれてる事は全く理解できず､全く同じ寸法の筒の周りに巻かない限り､メッセージは読めない。
　その後も次々と巧妙な暗号法が編み出され､その究極な暗号装置こそがナチスドイツのエニグマ”謎”である。

　しかし1977年までは､秘密のメッセージを送ろうとすると､必ず”ある問題”がついて回った。送り手と受け手の間で､暗号化の方法を予め打ち合せをする必要があるのだ。
　スパルタ軍は､使うスキュタレーの寸法の打ち合わせが必要だったし､ドイツ軍はUボートの指揮官にメッセージを暗号化する､機械の日毎の設定についての機密文書を届ける必要があった。勿論､スキュタレーの寸法もエニグマのコードブックも敵の手に落ちれば､一巻の終わりである。

　この様な暗号システムをネット上の取引で使った場合､受け手は秘密のコードをメールで受け取る必要がある。しかし､ネット上の膨大なデータの流れの中で､メールを横取りされる可能性は非常に高い。
　そこで､高速のグローバルネットワークに対応する､新しい暗号システムを開発する必要に迫られた。
　エニグマを開発したのが数学者なら､次世代の暗号を作り出し､スパイ小説の中の話だった暗号法を現実の世界に持ち込んだのも数学者である。この数学的な暗号を元にして作られたのが､”公開鍵”暗号システムである。

　情報の暗号化とその解読を､鍵を掛けたり開けたりするのに例えてみる。
　従来型のドアは､鍵をかけるにも開けるにも同じ鍵を使う。エニグマでもメッセージを暗号化するのと復号化するのは､同じ設定だった。
　故に､暗号の”鍵”は秘密にしておく必要があった。近くにいる数人の相手ならそう問題はないが､遠く離れた数百万もの顧客が相手なら､別々に全ての鍵を渡すのは不可能だ。

　”公開鍵”暗号は､2種類の鍵(暗号化と復号化)がついたドアの様なもので､ドアを閉める時はAの鍵を､開ける時はBの鍵を使う。つまり､鍵Aを秘密にする必要はなく､たとえ鍵Aを持ってても侵入できない。
　ある企業のウエブサイトの入り口に､こんなドアがあるとする。企業はウエブサイトを訪れ､クレジットカード番号の様な個人情報を内密に送りたいと思う人全てに､気軽に鍵Aを渡す事が出来る。個人情報を暗号化するのに使う鍵A(暗号化キー)は皆同じなのに､暗号化されたら皆読めなくなる。
　鍵B(復元化キー)を持ってるのは運営する企業だけで､ドアを開けてクレジットカード番号を読む事が出来る。

　この公開鍵暗号を始めて提案したのは､前述のスタンフォード大の2人の数学者ホイト•デフィーとマーチン•ヘルマンで､1976年の事である。
　2人は､暗号法を独占･隠蔽する政府諜報機関に反旗を翻し､”暗号法が政府の裏側で論じられるのはよくない”と､進んで自らの着想を公表した。
　この｢暗号学の新しい方向｣との論文は､電子セキュリティーの新時代を予感させるものだった。2つの鍵を使う公開鍵暗号は理論的には素晴らしいものに思えたが､試行錯誤が続き､当時は､こんなスパイ小説のような暗号システムは作れないのでは？と疑問視された。

　しかし､この新たなる暗号理論は､3人の若き大学院生に受け継がれ､大きな華を咲かせるのである。
　以上､長くなり過ぎたので､今日はここまでにします。
　次回は､RSA暗号システム誕生の裏側と素数時計とカードマジックを使って､その仕組みを紹介したいと思います。