Powered by SmartDoc

RSA暗号

数式処理演習 西谷 滋人

基本的な考え方

90年代の終わり頃のゴルゴ13に,ゴルゴ13が新しい暗号の開発を支援するという逸話(373話,最終暗号)がありました.暗号が通信の要であり,非常に高度なしかし簡素な数学を使っているという,さいとうたかおのいつもながらの先見性に感心しました.その作り話の元にもなっていたRSA暗号についてどのような原理なのかをMapleで見ていきます.

公開鍵暗号システムはWhitfield DiffieとMartin Hellmannによって1976年にそのアイデアが公表されました.そこでは,暗号化の鍵と復号化の鍵を分けることで鍵配送問題を解決しています.受信者は,前もって「暗号化の鍵」を送信者に知らせておきます.この「暗号化の鍵」は盗聴者に知られてもかまいません.送信者は,その「暗号化の鍵」を使って暗号化して受信者に送ります.復号化できるのは「復号化の鍵」を持っている人(受信者)だけです.こうすれば「復号化の鍵」を受信者に配送する必要がなくなります.対称暗号の鍵配送問題は,公開鍵暗号を使うことで解決するのです.

この公開鍵暗号のアイデア実現に必要な一方向関数は,1978年にRon Rivest, Adi Shamir, Leonard Adlemanによって発表され,そのRSA暗号では素因数分解に非常に時間がかかることを利用しています.RSA暗号は

です.そこで必要となるE,D,Nなどの鍵ペアは

で生成します.

簡単な例

具体的に見てみましょう.

N: RSA module, RSAモジュール

P:=3;Q:=11;
N:=P*Q;

L

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の最小公倍数)の倍数になるのでこちらを用いてもよい.

E:Encryption exponent, 暗号化指数

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;としてみます.実際は乱数発生器を用いたり,他の適当な素数を使ったりしているようです.

D:Decryption exponent, 復号化指数

E*D mod L=1となるDを求める.これをMapleではLを法とするEの-1乗として計算することが出来ます.MapleではDは微分を表す予約語なのでDDとかにしておきます.

DD:=eval(1/E mod L);

課題1

1:暗号化関数,復号化関数を定義して平文を3として暗号化した数と,復号化の結果を調べよ.

2:N以下の全ての自然数について暗号化した数を求めよ.また,復号化可能であることを確かめよ.

文字の暗号化

現実的なより長い,文字でできた平文(plain text)を暗号文(cipher text)にする場合を考えます.

大きな素数の生成
M1 := rand(10^80)();
M2 := rand(10^80)();
P := nextprime(M1);
Q := nextprime(M2);
Eの生成とgcdの確認
E:= 2^16+1;  isprime(E); gcd(E,L);

大きな素数を乱数発生器を使って作る例です.nextprimeはinputの数字より大きな次の素数を返してくれる関数です.Eをここでは2進数で0が並んだ数を作っています.こうすれば後の処理が速くなるのかな(?).

平文を大きな数に換える関数です.中身は分からんでもいいですが,文字の扱いに興味のある人はばらしてみてください.(Mike May, S. J.の"Using RSA"より)

ASCIIの2桁の16進数表示への変換
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);

課題2

1:前の課題で変数,関数名などを調整して,平文の暗号化,復号化を確かめよ.

2:以下の組み合わせで送られてきた暗号文をdecryptせよ.

DD := 
97160237787927197268399382847527128445\
49853837391340357711330646764959436711\
59170340750075707950776984678307988166\
43653201556982906389265242669384110487\
8601025;

N := 
53889560798132910692104691551103464936\
80295962602541240888011819541597381548\
47328720465604349380066375753497760645\
71193290783857018152083178164889182698\
06475731;

ciphertext := 
35617334193683758121458876563581777948\
88686788640826301652725191921600228140\
68263177796022170903531011472610378053\
22691405568944970187110528328096932989\
73447073

RSA暗号の基礎理論と関連するMapleコマンド

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のコマンドのいくつかをまとめておきます.

mod, modp
nをmで割ったあまりを求める関数.
n mod m;
modp(n,m);
ifactor
ある数の素因数分解を求める関数
ifactor(91);
isprime
ある数が素数ならtrue,違えばfalseを返す関数
isprime(101);
Power
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
ある数より大きな次の素数を返す関数.
nextprime(100);
lcm(Least Common Multiple)
最小公倍数を返す関数.
lcm(35,100);
gcd(Greatest Common Divisor)
最大公約数を返す関数.
gcd(35,100);
gcdの結果が1,つまり1以外に共通に割り切れる数がない場合
二つの数は互いに素であるという.
ithprime
i番目の素数を返す関数.
Fermatの小定理
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 )がただ一つ存在する.
Eulerの定理(の特別な場合)
自然数n(=p*q)より小さい自然数Mがnと互いに素であるとき,
mod(M^((p-1)*(q-1)),n)=1 ( 0<x<n )
Euclid互除法



拡張Euclid互除法



グーグル人材募集広告

直接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つに、自分が何かを探しているとき、向こうも自分を探している場合のほうが見つかりやすいということがある。我々が探しているのは、世界最高のエンジニアであり、あなたこそその人なのだ」と書かれている。

7427466391.com
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)=__________