RSA暗号をささえるオイラーさん
このページはマス旅の一部です。
前回は共通鍵暗号方式の代表であるAES暗号に至るまでの流れ、支える数学を見ましたね。
今回は「公開鍵方式のRSA暗号をささえるオイラーの定理と素因数分解」を学びましょう。
１．ウォーミングアップ
＜フェルマーの定理＞
どんな数も素数乗するとその数と合同になること、
a^p≡a(mod p)
を見つけました。
言い換えると、
a^(p-1)≡1(mod p)
です。
さらに言い換えると、
a^(p-1)-1≡0(mod p)
どんな数も(素数-1)乗して１ひくと、その素数の倍数ができるとも言えます。
＜オイラー関数＞
オイラーさんはφ関数（互いに素な整数の個数）を提案しました。
素数ｐ以下でpを割り切る数はpの1個だけだから、φ(p)=p-1というのは当然です。
割合で考えると、p個単位で1/pの確率でpの倍数が出現します。
これらから、
p,qが素数なら
φ(p)=p-1,φ(q)=q-1だから、
φ(pq)=(p-1)(q-1)
φ(p^2)=p^2(1-1/p)
φ(p^n)=p^n(1-1/p)
φ(p^m*q^n)=p^m * q^n (1-1/p)(1-1/q)
＜オイラーの定理＞
オイラーさんは得意のφ関数を使ってフェルマー定理を素数p以外でも使えるようにしました。
フェルマー定理はa^(p-1)≡1(mod p) (pと言えば素数）
オイラー定理はa^φ(n)≡1(mod n) (nはただの整数,nとaは互いに素）
＜オイラーの定理の便利さ＞
巨大な数の巨大乗を次数下げして計算できる。
Pythonが手元にないときに便利。
3と100は互いに素だから、3^φ(100)≡1(mod 100)が使える。
3^2050の下２けたを知りたい。3^2050≡x(mod 100)のｘが解。
φ(100)=100(1-1/2)(1-1/5)=40から、3^40≡1(mod 100)
2050÷40=51あまり10から、3^2050=(3^40)^51*3^10.
これから、3^2050≡3^10(mod 100)≡43^2≡(50-7)^2=49(mod 100)
(3^5=81*3=243≡43(mod 100)だから)
２．公開鍵方式は非対称のペア鍵方式
＜開錠は秘密鍵で＞
自分が住んでいるマンションのオートロックの鍵をだれでも手に入れることができて、しかも、簡単に開錠できるとしたら、そんな鍵は意味がありませんね。
「鍵が本来秘密のもので、施錠も開錠も同じ鍵を使う」という前提があるとしたら、
「公開鍵」というコトバの響きから、
そんな状況を連想したり、言語矛盾を感じるかもしれませんね。
だから、「公開鍵」方式を理解するには「非対称鍵」というコトバを使った方がよいかもしれません。
でも、鍵をかけるときは「公開鍵」を使いますが、
鍵を開けるときは「秘密鍵」となったらどうでしょうか。
暗号化前の平文と復号後の平文が同じなだけで、鍵は別なのです。
鍵が共通でなくて暗号化の鍵だけ公開だとしたら問題ありませんよね。
では、開ける人だけが秘密鍵をもつことをどうやって実現したらよいでしょうか。
いや、最初から実現されています。どういうことでしょうか。
受信者中心に考えてみよう。
受信者は最初っから秘密鍵を持っています。
公開鍵は秘密鍵とペアになるものにします。
だから、発信者が施錠するための鍵は公開鍵なので、発信者に鍵を送る必要はありません。
ただ、受信者が「ぼくに送るときは公開鍵1番でおくってちょうだい。」とリクエストすればよいだけです。
発信者は、その指定の公開鍵は簡単に手に入り、
受信者は、自分の秘密鍵を使うだけでありその秘密鍵は非公開だから、安全ですね。
３．RSA暗号の作り方と根拠
＜RSAという名前＞
RSA（Rivest-Shamir-Adleman)暗号。
どうも、AESのように堅苦しいけど意味のある名前の暗号ではないですね。
これはMITという研究開発のメンバーの名前です。
その「３人の頭文字」を並べただけです。
だから、名前からは実体のイメージは何も浮かびません。
どんなロジックなのでしょう。
およそでいうと、巨大数の素因数分解をせずとも「鍵が使える」方法です。
＜暗号の作り方＞
受信者は次のことをやります。
・できるだけ近い２つの素数ｐ、ｑを用意する。
・n=pq （n自体は公開されて、送受信で剰余の法として使われます）
・k= φ(n)を計算する。
・k未満でkと互いに素な自然数eを選ぶ。（eが暗号化鍵）
・d=1/e mod kを求める。（dが復号鍵）
・受信者は発信者したい人を含めてn,eを公開します。
発信者は暗号化します。
平文Aのe乗の剰余が暗号文Z (eが暗号化鍵で公開）
A^e≡Z (mod n),
受信者は復号します。
暗号文Zのd乗の剰余が平文A (dは復号鍵で秘密）
Z^d≡A (mod n)
暗号化と復号化の計算が同じ形だというのが面白いですね。
（例１）
p=3
q=11
n=3*11=33
k=φ(3*11)=2*10=20
e=7とすると、d=1/7≡(1+20)/7=21/7=3(mod 20) 割り切れるまで1にkを加算した。
発信者は送る平文Aに受信者の決めたe=7を使います。
暗号文Z=9^7(mod 33)= 15 (pythonで「9**7 %33」から)
受信者は送られてきた暗号文Zに自分で求めたd=3を使います。
復号文A=15^3(mod 33)= 9 ( 15**3 %33）
（例２）
p=53
q=59
n=53*59=3127
k=φ(53*59)=52*58=3016
e=3とすると、d=1/3=(1+3016*2)/3=2011(mod 3016) 割り切れるまで1にkを加算した。
平文A=2305としましょう。
発信者は送る平文Aに受信者の決めたe=3を使います。
暗号文Z=2305^3(mod 3127)= 2365 (pythonで「2305**3 %3127」から)
受信者は送られてきた暗号文Zに自分で求めたd=2011を使います。
復号文A=2365^2011(mod 3127)= 2305 ( 2365**2011 %3127）
＜RSA暗号が暗号になる理由＞
発信者が暗号化につかって公開情報はn,eでした。
一般の人や暗号解読を狙う人でも同じ立場であり、p,q,dは知りません。
では秘密鍵dがないとどうなるでしょうか。
たとえば、n=77や33ならば、n=7*11,3*11と一発でわかるから、
p,q,eがそろう。ということは受信者と同じようにdはすぐに求められるでしょう。
つまり、nの素因数分解に膨大な時間がかかるということがRSA暗号の生命線になるね。
1回の演算に１μ秒かかるコンピュータ（１MFLOPS)ではｎが10進100桁に74年かかる。
スーパーコンピューターで１0GFLOPSの性能があれば、74年が74/10000年＝2.7日。
１テラFLOPSの性能だと、さらに100分の１の39分でできるそうです。
ただし、現代の実際のRSA暗号では 2048ビット（約617桁） や 4096ビット が標準的に使われていて、宇宙の寿命以上の時間がかかるから安全だと言われています。
＜RSAの秘密鍵dの秘密＞
A^e≡Z mod n で作った暗号Zが
Z^d≡A mod n の計算でサクッと平文Aに戻りました。
なぜでしょうか。
これはZ^d=(A^e)^d=A^{ed}≡A (mod n)だから、
mod nの世界でed≡1になったと同じです。
もともとd=1/e(mod k)のように
mod kの世界でed≡1となってただけでしたよね。
どういうことでしょうか。
それはkとdに秘密があります。
#dの秘密
e、kからdを求めるとき、eで割り切れるまで、1にkをたしていきましたね。
それがq個のkだとしましょう。
d=1/e=(1+qk)/e(mod k) から、
ed=1＋qk
となる整数qがあります。
#kの秘密
k =φ(n)だから、
暗号・復号では表立っては使ってませんが、
オイラーの定理からA^k≡1(mod n）です。
Z^d=(A^e)^d=A^ed
=A^{1+qk}=A^1*A^qk [ここでdの秘密が使われた！]
=A*(A^k)^q
=A*1^q [ここでkの秘密が使われた！」
≡A(mod n)
オイラーマジックでqkが消せたから、
mod kでの事実をmod nに流用できたといもいえますね。
４．振り返り
＜改ざんを防ぐデジタル署名＞
RSA暗号はふつうの暗号文のやりとりだけでなく、
「デジタル署名」にも使われるようです。
n=pq,k=φ(n),公開鍵e決め,秘密鍵dを求めるまではさっきと同じです。
しかし、送信・受信の役割だけ変わります。
次に、さっき受信者だった方の人が
秘密鍵dで平文を暗号化した「暗号文」ともとの「平文」の２データを発信者を送ります。
すると、２データを受けとった人は公開鍵eで暗号文を平文に直せるので、
いっしょに送られた平文が一致することによって、データを送った人の「本人確認」がとれるのです。
つまり、
(A^e)^d=A
でなはく、
(A^d)^e=A
を使っています。
ed=de=1(mod k)ですから、
逆順に鍵を使ってももとにもどせるということですね。
こうやって、人レベルではなく鍵レベルまで考えることで、
通常の暗号・復号作業と、デジタル署名の作業の共通点と違いが明確になるので、
よくある説明よりもわかりやすくなりますね。
なお、デジタル署名の実際のやりとりではメッセージダイジェストと「ハッシュ関数」が使われます。
本文を直接暗号化して送るのではなく、本文をハッシュ関数でダイジェストを作ります。ダイジェストの暗号化と本文を送れば、もらった人は本文を自分でハッシュ関数をかけて作ったダイジェストと、ダイジェストの複合を比べて同一ならば、本文の「メッセージは改ざん」はされていないとわかりますね。
課題：素数リストから2数選んでnを決めるとeの候補を表示されてeを決めるとdを求めるアプレットをgeogebraで作りましょう。
タイトルは「RSA暗号の２つの鍵を決めよう」
ps={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}
qs={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}
Pnum=Slider(1,Length(ps),1)
Qnum=Slider(1,Length(qs),1)
p=Element(ps, Pnum)
q=Element(qs, Qnum)
n=p q
k=(p-1)(q-1)
text1 = "素数 p = " + p + ", 素数 q = " + q
text2 = "n = " + n + ", φ(n) = " + k
#eの候補と選んだ公開鍵eの表示
Es=Element(j,j,1,k-1)
Esp=KeepIf(Mod(x,p)==0,Es)
Ens=Remove(Es,Esp)
Esq=KeepIf(Mod(x,q)==0,Ens)
text3="選んだ公開鍵e＝"+e+""
Enpq=KeepIf(Ens,Enq)
#Enpq = KeepIf(GCD(x, k) == 1, Es)
Enum=Slider(1,Length(Enpq),1)
e = Element(Enpq, Enum)
#qの決定
qmax=Div(n,q)
ds = Sequence(1+qk,q,1,qmax)
qIndex = Sequence(q,q,1,qmax)
ress =Zip(Mod(k,e),k,ds)
qId= IndexOf(0,ress)
d=Element(ds,qId)/e
#まとめの表示
text4="求めた秘密鍵d=" + d + ""