90年代の終わり頃のゴルゴ13に，ゴルゴ13が新しい暗号の開発を支援するという逸話（373話，最終暗号)がありました．暗号が通信の要であり，非常に高度なしかし簡素な数学を使っているという，さいとうたかおのいつもながらの先見性に感心しました．その作り話の元にもなっていたRSA暗号についてどのような原理なのかをMapleで見ていきます．
公開鍵暗号システムはWhitfield DiffieとMartin Hellmannによって1976年にそのアイデアが公表されました．そこでは，暗号化の鍵と復号化の鍵を分けることで鍵配送問題を解決しています．受信者は，前もって「暗号化の鍵」を送信者に知らせておきます．この「暗号化の鍵」は盗聴者に知られてもかまいません．送信者は，その「暗号化の鍵」を使って暗号化して受信者に送ります．復号化できるのは「復号化の鍵」を持っている人(受信者)だけです．こうすれば「復号化の鍵」を受信者に配送する必要がなくなります．対称暗号の鍵配送問題は，公開鍵暗号を使うことで解決するのです．
この公開鍵暗号のアイデア実現に必要な一方向関数は，1978年にRon Rivest, Adi Shamir, Leonard Adlemanによって発表され，そのRSA暗号では素因数分解に非常に時間がかかることを利用しています．RSA暗号は
です．そこで必要となるE,D,Nなどの鍵ペアは
で生成します．
具体的に見てみましょう．
P:=3;Q:=11; N:=P*Q;
L:=lcm(P-1,Q-1);
厳密にはL:=lcm(P-1,Q-1);ですが，P*Qを法とすると，全ての数が自分自身に戻るべき乗数は，nを任意の整数としてn*(P-1とQ-1の最小公倍数)+1と表すことができる．(P-1)*(Q-1)は，必ず(P-1とQ-1の最小公倍数)の倍数になるのでこちらを用いてもよい．
gcd(E,L)=1となるEを求めるのですが，これはたくさんあります．以下のスクリプトで全てを表示することが可能です．
for i from 1 to L do
if gcd(i,L)=1 then
printf("%4d,",i);
end if;
od;
ここではE:=3;としてみます．実際は乱数発生器を用いたり，他の適当な素数を使ったりしているようです．
E*D mod L=1となるDを求める．これをMapleではLを法とするEの-1乗として計算することが出来ます．MapleではDは微分を表す予約語なのでDDとかにしておきます．
DD:=eval(1/E mod L);
現実的なより長い，文字でできた平文(plain text)を暗号文(cipher text)にする場合を考えます．
M1 := rand(10^80)(); M2 := rand(10^80)(); P := nextprime(M1); Q := nextprime(M2);
E:= 2^16+1; isprime(E); gcd(E,L);
大きな素数を乱数発生器を使って作る例です．nextprimeはinputの数字より大きな次の素数を返してくれる関数です．Eをここでは2進数で0が並んだ数を作っています．こうすれば後の処理が速くなるのかな（？）．
平文を大きな数に換える関数です．中身は分からんでもいいですが，文字の扱いに興味のある人はばらしてみてください．(Mike May, S. J.の"Using RSA"より)
twodigithex := a -> substring(convert(a+256,hex),2..3):
shortconverter := proc(messagestring)
local stringofhex, lengthofmess, hexstring, i:
#First we convert the ASCII string to a list of decimal equivalents
#Then we convert the decimal numbers to hex equivalents
stringofhex := map(twodigithex, convert(messagestring,bytes)):
print(stringofhex);
lengthofmess := nops(stringofhex):
print(lengthofmess);
#Now we concatenate the hex numbers
hexstring := cat(seq(stringofhex[i],i=1..lengthofmess)):
#Finally we convert the big number back to decimal
convert(hexstring,decimal,hex):
end:
numtostring := proc(bignum) local hexstr1, listlength, declist, i: #convert to a hex string hexstr1 := convert(bignum,hex): #make sure the hex string has even length if (length(hexstr1) mod 2) = 1 then hexstr1 := cat(`0`,hexstr1) fi; #compute the number of characters listlength := length(hexstr1)/2: #convert to a vector of decimal numbers declist := linalg[vector](listlength); for i from 1 to listlength do declist[i] := convert(substring(hexstr1,2*i-1..2*i),decimal,hex); od; #convert the vector to a list, then to an ASCII string convert(convert(convert(declist,list),bytes),name); end:
実際の操作を試しておきます．
plaintext := "Good evening Kids, this afternoon we explore around \
RSA.";
numberedText := shortconverter(plaintext);
numtostring(numberedText);
DD := 97160237787927197268399382847527128445\ 49853837391340357711330646764959436711\ 59170340750075707950776984678307988166\ 43653201556982906389265242669384110487\ 8601025; N := 53889560798132910692104691551103464936\ 80295962602541240888011819541597381548\ 47328720465604349380066375753497760645\ 71193290783857018152083178164889182698\ 06475731; ciphertext := 35617334193683758121458876563581777948\ 88686788640826301652725191921600228140\ 68263177796022170903531011472610378053\ 22691405568944970187110528328096932989\ 73447073
RSAの原理については講義であろうから，エッセンスだけを記しておきます．
先ず基本となる中学で習った（はずの），素数の復習です．自然数p>1は，二つの整数1,pのみを約数とする場合，素数(prime number)と言われる．素数でない自然数a>1は合成数(composite number)と言われる．なお，1は素数でも合成数でもない．また，素数pが整数aを割り切れれば，pはaの素因数(prime divisor)と言われる．整数a,bについてgcd(a,b)=1が成り立つとき，aとbは互いに素(coprime)であると言われる．全ての正整数は素数の積で表現可能であり，これを素因数分解(factorization)と言う．
暗号文Cが平文Mに戻る条件を導くと，暗号化と復号化の計算式は，
C = M^e (mod n)
M = C^d (mod n)
であるから，ここでmodの「大きくなる前に適宜割っていっても，最終的な余りは変わらない」という性質
{a * b} (mod n) = {(a (mod n)) * (b (mod n))} (mod n)
を使って，前者を後者に代入すると、
M = (M^e)^d (mod n)
= M^(ed) (mod n)
= M^(ed) (mod pq)
となる．この式を変形すると
M^(ed)-M = 0 (mod n)
M*(M^(ed-1)-1)=0 (mod pq)
となる．この式がなりたつ条件はFermatの小定理を使って求まり，RSA暗号が成立する．
このあたりの詳しくて分かりやすい解説が
にある．
素数絡みのMapleのコマンドのいくつかをまとめておきます．
nをmで割ったあまりを求める関数． n mod m; modp(n,m);
ある数の素因数分解を求める関数 ifactor(91);
ある数が素数ならtrue，違えばfalseを返す関数 isprime(101);
modの「大きくなる前に適宜割っていっても，最終的な余りは変わらない」
という性質
{a * b} (mod n) = {(a (mod n)) * (b (mod n))} (mod n)
を使ってベキ計算してくれる関数．modと組み合わせて使う．
例えば，
time(numberedText^E mod N);
と
time(Power(numberedText,E) mod N);
とをくらべよ．通常のべき表示"^"のかわりに"＆^"を使っても
Powerと同じ効果が得られる．
ある数より大きな次の素数を返す関数． nextprime(100);
最小公倍数を返す関数． lcm(35,100);
最大公約数を返す関数． gcd(35,100); gcdの結果が1，つまり1以外に共通に割り切れる数がない場合 二つの数は互いに素であるという．
i番目の素数を返す関数．
pを素数，aを整数とすると， modp ( a^p-a , p ) =0 が成り立つ．さらにaとpとが互いに素であれば， modp( a^(p-1), p) = 1 が成り立つ．
自然数nより小さい自然数aがnと互いに素であるとき， mod(ab,n)=1となるb ( 0<b<n )がただ一つ存在する．
自然数n(=p*q)より小さい自然数Mがnと互いに素であるとき， mod(M^((p-1)*(q-1)),n)=1 ( 0<x<n )
直接RSA暗号に関係するわけではありませんが，素数つながりで載せておきます．
グーグル、謎の人材募集広告--シリコンバレーのビルボードに
Stefanie Olsen (CNET News.com)
2004/07/12 08:40
先週、シリコンバレーの中心を走るハイウェー101沿いのビルボードに、複雑な数学の問題を載せた広告が現れた。(中略)
この広告には、「｛eの値中の、最初の連続する10桁の素数｝.com」("{first 10-digit prime found in consecutive digits e}.com." )と書かれている。この答えの「7427466391.com」にアクセスすると、そのウェブページにはさらに別の問題(下記参照)が用意されているが、ここにもGoogleが関与していることを示すものは全くない。
この問題を解くと、Googleの研究開発部門「Google Labs」へのページに辿りつく。このページには、「Googleの構築を通して我々が学んだことの1つに、自分が何かを探しているとき、向こうも自分を探している場合のほうが見つかりやすいということがある。我々が探しているのは、世界最高のエンジニアであり、あなたこそその人なのだ」と書かれている。
Congratulations. You've made it to level 2. Go to www.Linux.org and enter Bobsyouruncle as the login and the answer to this equation as the password. f(1)=7182818284 f(2)=8182845904 f(3)=8747135266 f(4)=7427466391 f(5)=__________