更新日:2002/11/1
2002/11の「今月のご挨拶」で「電子申請と公開鍵暗号」と題して、公開鍵暗号のについて、
簡単に紹介した。その中で、省略した事柄について、ここで記載していきたい。
公開鍵暗号では、大きな整数の素因数分解が困難なことが利用されている。同方法では、100桁以上の整数が使用されている。
大きな整数をVB.NETで扱うためには、どうしても多倍長計算が必要になる。
なぜならば、VB.NETで普通に扱える数の大きさは、最大で30桁程度であるからである。
UBASICなど一部の言語を除いて、プログラミング言語では、多倍長計算がサポートされていない。
現実世界では、最も精密な物理定数でさえ、8~10桁程度の精度である。
であるので、これ以上の桁数を保って計算しても(現実世界では)意味がない。
これは、理・工学部の学生になると最初に教えられる点である。「測定値や計算の基礎となる数値の有効桁数を考えて、計算をする必要がある」と。
これが、通常、多倍長計算をサポートしていない主な理由と思われる。
公開鍵暗号を理解するためには、初等整数論の知識が必要である。日本では、数学科の学生を除いて、整数論に触れる機会は、(ほとんど)ない。
少なくとも筆者が学生であった頃の数学の基本的な流れは、実数、複素数を経て解析学・微分方程式へという道程であった。
これは、数学を学ぶ目的が理学・工学への応用のためと考えられているからであろう。
ただ、最近の情報理論や暗号などは、従来の解析学の応用では、理解できない項目が増えているのも事実である。
ところが、複素数やベクトルまでも高校数学から省かれてきているこの頃では、学校数学で整数論に親しむという機会は、更に遠くなったようにも思える。
ただ、パソコンの普及に伴うプログラム作成の授業等では、このような整数論の問題は、取り上げやすいと思う。
なぜならば、問題の理解については、事前の準備があまりいらないから。
以下では、(筆者のために)必要な事柄を簡単にまとめてみたが、読者のために何かの足しになれば、なお幸いである。
「自然数は神が作った。その他の数は人間が作った」とクロネッカー(数学者)は、
言ったと伝えられている。それほど、自然数(1,2,3・・)は、私たちに身近な存在である。
(自然数にゼロを含めていう場合もある。)
古代のギリシャの数学者・哲学者達は、このような自然数をさまざまな見方で分類していた。
例えば、X^2+Y^2=Z^2となる3つの自然数の組は、現在、「ピタゴラス数」と呼ばれている。
彼らは、狩猟家が獲物をねらうようにこのような特別な数達を発見した。
なお、ピタゴラス数については、x,y,zが互いに素という条件の下での一般解は、x=a^2-b^2、y=2ab、z=a^2+b^2であることが知られている。
合同式とは、a≡b (mod n)という形をしている。
式の意味は、aをnで割った場合、余りは、bであることを表している。
合同式は、通常の式と異なる側面もある。
例えば、a≡bであるからといって、b≡aではない。(5≡2 mod 3を考えれば分かる)
一方、a≡b、c≡dであれば、通常の式と同様に次が成り立つ。(mod n)
a+c≡b+d
a×c≡b×d
証明は、a=nN+b、c=nM+dとして、a+b=n(N+M)+(b+d)、
右辺第1項は、nで割り切れるから、この式の余りは、b+dであることなどから容易である。
合同式のわり算については、次のことが知られている。
aとnが互いに素の場合、a×k≡1 (mod n)なるkが、一つ、存在する。
このkをaの逆元という。これは、通常の算術の場合のわり算に相当する。
kが分かれば、a×b≡cなるbは、k×cとして求められる。
ドイツの偉大な数学者、オイラーの名前を冠した定理や関数は、随所に現れるが、ここでいうオイラー関数、Φは、次のようなものである。
Φ(n)とは、1~nまでの自然数のうち、nと互いに素となる数の個数のことである。
例えば、Φ(10)=4、(1,3,7,9が10と互いに素)
一般にnが素数の時は、Φ(n)=n-1である。
また、次の定理が成り立つ。
n=p1^k1×p2^k2×・・としたとき、Φ(n)=n(1-1/p1)(1-1/p2)・・である。
ここで、p1等は、互いに異なる素数、k1等は、自然数。
例えば、n=p×qのときは、Φ(n)=pq(1-1/p)(1-1/q)=(p-1)(q-1)である。
互いに素という意味をここで確認しておこう。(a,b)でaとbの最大公約数を表すと互いに素とは、(a,b)=1であることをいう。
aとnが互いに素の場合、a^Φ(n)≡1 (mod n)である。これをオイラーの定理という。
そして、オイラー関数の性質を使えば、(4)よりn=p(素数)の場合、
a^(p-1)≡1 (mod p)が直ちに得られる。これをフェルマーの小定理という。
例えば、a=3、n=5とすると、3^4=51≡1 (mod 5)である。
ちなみに、フェルマーの大定理とは、x^n+y^n=z^nを満たす自然数n(>2)は、存在しない。というものであり、長年にわたり未解決であったが、1993年に証明された。
(x,n)=1となるx、(xは、1~n)の集合を考える。この集合の個数は、Φ関数の定義によりΦ(n)個である。
(a,n)=1なるaについて、ax≡zは、また、この集合に含まれる。
更にxが決まるとzが決まり、その対応は、1対1である。(ここ、難しいので証明略す。)
そうすると、すべてのxについての積、Πax≡Πx。
積の個数は、m個あるので、a^mΠx≡Πx、両辺をΠxで割れば、a^m≡1となる。
例えば、n=10、a=3とすれば、Φ(10)=4,(1,3,7,9)
3×1≡3
3×3≡9
3×7≡1
3×9≡7
で、xが1,3,7,9と変化するのに対して、3xは、3,9,1,7と変化している。
1986年当時の「数学セミナー」に「かずかずの数」という特集記事があった。
ここに様々な数についての話題が集められている。例えば、前出のピタゴラス数など。
ここでは、それを元に素数と関係の深いものを少し、紹介してみよう。
まず、「カーマイケル数」である。前出のフェルマーの小定理では、素数pについて、
a^(p-1)≡1 mod pを述べている。
この対偶をとると「a^(n-1)-1がnで割り切れないときは、nは、合成数(素数でない数)である」
ここで、aは、例えば、nが奇数であれば、(2以外の素数は、すべて奇数である。)、2とできる。
(これを素数判定のフェルマーテストという。)
では、割り切れた場合は、nは、素数であろうか?
フェルマーの小定理の逆は、必ずしも成立しないので、その真偽は判定できない。
合成数n、nと互いに素なaに対して、a^(n-1)≡1 mod n が成立するとき、nをaを底とする擬素数という。
特にa=2のときを「プーレー数」という。
さらに、どんなa(nと互いに素な数)に対しても、a^(n-1)≡1となる数を「カーマイケル数」という。
例えば、561、1105、1729、2465、2821、6601、8911が10000以下のカーマイケル数である。
カーマイケル数に関しては、次の定理が知られている。(チェルニク)
「nがカーマイケル数である必要十分条件は、nが3以上の奇素数の積であって、各素数に対して
n≡1 (mod p-1)」
nについて、n以外の約数の和がn自身になるとき、nは、「完全数」であるといわれる。
例えば、6=1+2+3なので、6は、完全数である。
奇数の完全数は、知られていないようである。
F(1)=F(2)=1、F(n)=F(n-1)+F(n-2)で定義される数列をフィボナッチ数列といい
個々のF(n)をフィボナッチ数という。
もう少し一般化して、L(1)=a、L(2)=b、L(n)=L(n-1)+L(n-2)なるものを考えて、特に、a=1、b=3の場合を「リュカ数」という。
一般の場合は、フィボナッチ数とリュカ数で表される。これらの数と最大公約数などとは、関係が深い。
例えば、F(n)とF(n-1)など隣り合う数同士は、互いに素である。
素数を表す式としては、n^2-79n+1601は、n=0~79について、すべて素数となる。(エスコット)
かのフェルマーは、生前、2^(2^n)は、nの如何に関わらず、素数であるといった。
これを「フェルマー数」という。n=0~4、n=4の時は、65537となる。
しかし、n=6で、641×6700417と素因数分解されて、フェルマーの言明は、誤りであることが分かった。
このことを示したのは、(またしても)、オイラーであった。
むしろ、最近では、フェルマー数で素数になるものが見つかっていないようである。
これについては、ペパンの判定法というものが知られている。
F(n)(フェルマー数)が素数であれば、F(n)は、3^((F(n)-1)/2)+1の約数、という関係が成立する。
例えば、F(2)=17は、素数であるが、3^8≡16 mod 17
pとp+2がともに素数の時、この組を「双子素数」という。
双子素数は、無限に存在するらしいが、その程度は、多くはないと予想されている。
素数pに対する、2^p-1の形の数のことである。2^31-1=2147483647は、素数である。
もちろん、素数でないものもある。例えば、2^11-1=2047=23×89
これについては、「リュカテスト」という素数判定法が存在する。
S(1)=4、S(i+1)=S(i)^2-2 i=1~
のとき、2^p-1が素数である必要十分条件は、S(p-1)が2^p-1で割り切れること。
リュカテストは、計算機向きの方法なので、大きい素数は、大抵、メルセンヌ数であるとのこと。
公開鍵暗号の話では、a,kが大きな自然数であるとして、bを求める必要が出てくる。
例えば、2002/11の「今月のご挨拶」では、196^1573≡? (mod 1067)を求めるという問題が出てくる。
これは、1573=11×11×13であることから、
196^1573≡((196^11)^11)^13、
これは、196≡196、196^2≡4、196^4≡16、196^8≡256などから
196^11≡196^3×196^8≡196×4×256≡108
そして、108≡108、108^2≡994、108^4≡1061、108^8≡36などから
108^11≡1065、
よって求める値は、1065^13。
1065≡1065、1065^2≡4、1065^4≡16、1065^8≡256などから
1065^13≡344となる。
(1)の計算を別の方法でやってみよう。
1573=1024+512+32+4+1となる。
一般に、a^2^k=(a^2^(k-1))^2であるので、
196≡196から
196^2≡4
196^4≡16
196^8≡256
196^16≡449
196^32≡1005
196^64≡643
196^128≡520
196^256≡449
196^512≡1005
196^1024≡643
となる。
よって、196^1573≡643×1005×1005×16×196≡344
となって、(1)の計算値と一致する。
暗号文、344を復号化する際に344から秘密鍵877を用いて344^877の余りを計算する。
すなわち、344^877≡? (mod 1067)を求める。
これも(2)の方法に従えば、877=512+256+64+32+8+4+1
344≡344
344^2≡966
344^4≡598
344^8≡159
344^16≡740
344^32≡229
344^64≡158
344^128≡423
344^256≡740
344^512≡229
となる。
よって、344^877≡229×740×158×229×159×598×344≡196
確かに元の平文の値、196になる。
暗号化は、aを平文として、a^k≡bなる暗号文bを求める操作である。
この際、mod nのnは、公開鍵の一つである。
また、kは、Φ(n)=mと互いに素となる数として選ぶ。kも公開鍵となる。
一方、秘密鍵は、k×s≡1 (mod m)となる、sである。
さて、秘密鍵で復号化する操作は、b^s≡?である。
この?がaであれば、確かに復号化が保証される。
a^k≡bから(a^k)^s≡b^s≡a^(k×s)
ところで、k×s≡1から、k×s=mM+1であるので、与式は、a^(mM+1)となる。
(Mは、自然数)
a^m≡1 (mod n)(オイラーの定理)であるから、(a^m)^M×a≡1^M×a≡a、
よって、与式は、aとなることが分かる。
秘密鍵sを知るためには、kとmを知る必要がある。kは、公開されているが、mは、秘密である。
mは、オイラー関数Φを用いてΦ(n)として計算する必要がある。
nの素因数分解を知っていれば、オイラー関数の個所に記載した公式によりmは、容易に計算できる。
特にnがRSA暗号のようにpとqという2つの素数の積であれば、m=(p-1)×(q-1)となる。
ところが、pとqが分からないと、すなわち、nの素因数分解ができないとΦは容易に求まらない。
これがRSA暗号のよりどころである。換言すれば、大きな数の素因数分解が容易にできてしまうとRSA暗号は、破られてしまうことになる。
剰余の計算のフォームを作成してみよう。
多倍長の工夫については、追って考えるとして、取りあえず、ここで取り上げた程度の計算ができることを当面、目標とする。
関数FMODを次のように考える。
FMOD(a,k,n)=MOD(a^k,n)である。しかし、a,kが半端な数ではない場合を考えたいので、このままではできない。
そこで、k=k(0)×2^0+k(1)×2^1・・と分解すると、
(これは、kを2進数に分解しようということと同一である。)
i番目の項については、FMOD(a,k(i),n)とFMOD(a,2^i,n)との積に分解できる。
FMOD(a,2^i,n)≡(FMOD(a,2^(i-1),n))^2、
ここで、FMOD(a,1,n)は、a MOD nとすれば、計算できる。
また、k(i)は、ゼロか1であるので、FMOD(a,0,n)=1に注意する。
そこで、求めたい値をQと書けば、Qは、次のように繰り返し計算で求められる。
B=a MOD n
もし、B=0であれば、Q=0である。(aがnの倍数の場合。互いに素の場合は、こうはならない)
Bがゼロでない場合で、
もし、k(0)がゼロでない場合は、Q=Bとおく。ゼロの場合は、Q=1とする。
そして、i=1~mについて、
C=B×B MOD nを計算する。
もし、Cがゼロの場合は、このループを抜ける。
もし、k(i)がゼロでない場合は、Q=Q×C MOD nとする。
B=Cにして、繰り返す。
これで、Q=a^k MOD nが計算できたことになる。
(1)の方針に基づき、VB.NETでのフォームを作成した。
これを例によって、「自作もの」コーナーに掲載しておく。
ただし、これは、多倍長計算を使用してないため、あまり多くの桁数の計算はできない。
数値か否かのチェックもしてないので、aやk等に数値以外のものを入力して実行すると実行時のエラーが発生する。