暗号のしくみと素因数分解”その２”〜RSA暗号のアルゴリズム〜

　前回は暗号の仕組みを”同型写像”と”mod演算”(剰余計算)を使ったやり方で述べましたが。書いた私も読む程に理解できません(笑)。
　そこで運良く､＠jabbaさんのブログでRSA暗号の仕組みを拝見しました。とてもわかり易く説明されてます。
　元々RSA暗号とは､桁数が大きい合成数の素因数分解問題が困難である事を安全性の根拠とした公開鍵暗号の一つです。　
　1977年に発明され､発明者であるR•L•Rivest､A•Shamir､L•Adlemanの頭文字を繋げ､名付けられた。

RSA暗号の仕組みと時計計算機

　仕組みとしては､前もって公開鍵と秘密鍵を作成し､事前に公開鍵を公開します。まず､公開鍵として適当な正の整数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で割った余りを計算する事で復元出来ます。

　前述のリヴェスト(R•L•Rivest)が使ったのが､”フェルマーの小定理による一般化”(オイラーの定理)である､2つの素数pとqからなる時計計算機でした。
　このN(=pq)時間時計では､”(p−1)(q−1)+1”回シャッフルした時に､再び同じパターンが繰り返される事は､オイラーにより示されてました。
　因みに､p時計計算機とはxᵖ≡x(mod 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の秘密を解く鍵という訳なんです。

素因数分解の困難さこそがRSA暗号の鍵

　故に､暗号化は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がとれるので､”一次方程式の解法”より､秘密鍵dが求まる。gcdは”最大公約数”の事です。　

　つまり秘密鍵”d”は､公開鍵”e”とφ(N)=(p−1)(q−1)が判れば､”ユーグリッドの互助法”(拡張された一次方程式の解法)から求まります。故に､eを公開鍵として､Nと共に事前に公開し､pとqは絶対に漏らさないという事が重要です。
　但し､”一次方程式の解法”や”ユーグリッドの互助法”は少し抽象的でややこしいので､説明はここでは省きます。悪しからずです。

　そこで今日は､RSA暗号表(乗数表)から､鍵生成と暗号化と復号の3つのアルゴリズムを説明します。

RSA暗号表とアルゴリズム

　まず､このRSA暗号表で使う”乗数の表”を用意します。実際のRSA暗号表では200桁ほどのとても大きい2つの素数を掛けた数字で割った余り(mod)を表にしますが。表がパンクするので､ここでは､p=5とq=17というとても簡単な例を挙げます。
　ここで､RSA表の横軸をNとし､縦軸をX(累乗数)とします。つまり､自然数NのX乗をpq=85で割った余り(1≤Nˣmod85≤84)を表に埋め込みます(イラスト参照)。

　すると､1行目と同じ数の並びが､17行目と33行目に表れてますね。つまり､この表の中ではどんな数も､17乗や33乗して85で割れば､元の1行目の数に戻るんです。因みに､mod演算は関数電卓で計算します。
　この17や33の算出は､”(p−1)と(q−1)との最小公倍数Lの倍数に1を足した数である”という便利な法則を使います。
　これは､前述の”時計計算機”の原理から何となく理解できますね。
　故に､5−1=4と17−1=16の最小公倍数は
16で､16の倍数に1を足した数:17､33､49､､､行目の数は､1行目の数に戻る。　
　つまり､どんな数も(LN+1)乗し､mod85を取れば(85で割れば)､元の数に戻る。これはまさに､時計計算機の原理そのものですね。
　LN+1=17の時は､1¹⁷(mod 85)=1､2¹⁷(mod 85)=2､3¹⁷(mod 85)=3､､､N¹⁷(mod 85)=Nとなります。
　故に､累乗とmod演算の組合せがRSA暗号のアルゴリズムという訳です。

　そこでまず､”公開鍵”Yの作り方ですが。p−1とq−1との最小公倍数Lを出します。ここでは､p=5､q=17で､L=16ですね。
　公開鍵Yの条件として､1≤Y≤L(16)かつ､Lとは互いに素ですから､仮にY=3という数にします。故に､ある数を3乗して､85で割った余りを取る事で暗号化出来ます。
　一方､復号化ですが。”秘密鍵”Zの条件は､上でも述べた様に､公開鍵×秘密鍵=YZ=LN+1です。L=16と公開鍵のY=3で算出すると､Z=11(N=3)を得ます。これはあくまでも超簡単な例です。
　因みに､YZ=LN+1にという等式は､上述したdeｰxφ(N)=1と同義ですね。この証明も少しややこしいので､次回に回す予定？です。

実際に計算してみよう

　さて､実際に確認してみましょう。簡単過ぎですが､平文を(3､4､5､6､7)とします。
　すると3乗して､85で割った余りである”公開鍵”(=3)で暗号化すると､RSA表(mod85)より､暗号文は(27､64､40､46､3)となります(イラスト参照)。
　そこで､”秘密鍵”(=11)で復元します。暗号文を11乗し85で割ります。すると､見事に(3､4､5､6､7)に戻ってますね。関数電卓で確認です。

　つまり､ある数(平文)をY(公開鍵)乗し､mod(pq)の演算を使い､訳判んない数(暗号文)にして､pとqから秘密鍵Zを割り出し､暗号文をZ乗し､mod(pq)の演算で元に戻すんです。
　因みに､事前に公開(送る)するのは､このケースで言えば､公開鍵3と､(5×17=)85ですね。そして､絶対に漏らしてはならないのが5と17です。この2つが判れば､簡単に秘密鍵11が割り出せますからです。
　しかし､85から5と17の素因数を割り出すのは簡単ですが。前述した様に､200桁ほどの素数にすれば､スパコンをもってしても莫大な時間が掛かります。

　”真に凄い英知とは､究極のシンプルさにある”と､jabbaさんも言ってますが。全く私も同感です。
　以上､RSA暗号表(乗数表)を使い､暗号の仕組みを判りやすく説明したつもりですが。判った様な判んない様なですね。
　でも､公開鍵と秘密鍵の積が互いに素な2つの素数pとqからそれぞれ1を引いた､p−1とq−1の最小公倍数の倍数に1を足したものになるという時計計算機のアルゴリズムを使う事が判っただけでも良しとしましょうか。