SSブログ

No.311 - 高校数学で理解するRSA暗号の数理(2) [科学]


4. RSA暗号の証明


4.1  RSA暗号

RSA暗号の公開鍵・秘密鍵の作成方法と暗号化・複号化の計算式を定理として記述すると次の通りです。

pq を相異なる素数とし、 n=pq とする。

e m = p-1 q-1 と素な数、d を、 de 1 mod m を満たす数とする。この前提で、

暗号化: P e C mod n ならば
複号化: C d P mod n である。

P :平文。 C :暗号文 )


RSA暗号において、暗号化・複号化に必要なのは公開鍵の en と 秘密鍵の d であり、それらを生成するのに使った pq は不要です。というより、pq ないしは p-1 q-1 が漏れると暗号が破られてしまうので、これらの数は鍵を生成した後は破棄(情報を安全に抹消)する必要があります。

以下に、上の「複号化の式」が成り立つことを証明します。まず合同式の累乗 1.2 を使って「暗号化の式」の両辺を d 乗すると、

C d P de mod pq  ⋯ (1)

となります。ここで、 de 1 mod p-1 q-1 なので、 de = k p-1 q-1 + 1 と表現できます。従って、

P de = P k p-1 q-1 + 1

となります。累乗を分解すると、

P de = P p-1 q-1 k · P  ⋯ (2)

です。一方、フェルマの小定理 3.1 により、

P p-1 1 mod p

となります。合同式の累乗の定理 1.2 により、この式の両辺を q-1 乗すると、

P p-1 q-1 1 mod p  ⋯ (3)

が得られます。さらに、フェルマの小定理 3.1 により、

P q-1 1 mod q

ですが、両辺を p-1 乗して、

P p-1 q-1 1 mod q  ⋯ (4)

となります。ここで、pq は互いに素なので、1.5 の合同式の定理を (3), (4) に適用すると、

P p-1 q-1 1 mod pq

を導くことができます。この式の両辺を 1.2 を使って k 乗すると、

P p-1 q-1 k 1 mod pq

であり、さらに両辺に合同式の乗算 1.1c を使って P をかけると、

P p-1 q-1 k ·P P mod pq  ⋯ (5)

となります。従って、 (1), (2), (5) を合わせると、

C d P mod pq

となり、RSA暗号の複号化の式が証明できました。

 最小公倍数 

以上の証明の過程を改めて振り返ってみると、「m p-1 の倍数であり、かつ q-1 の倍数」であれば、RSA暗号は成立することが分かります。つまり「m p-1 q-1 の公倍数」であれば成立する。そのような m は、

m = np p-1 m = nq q-1

の2通りに表現できます。すると、 de 1 mod m なので、

de = kp p-1 + 1 de = kq q-1 + 1

と2通りに表せます。ここから、

P de = P kp p-1 + 1 P de = P · P p-1 kp P de P mod p P de = P kq q-1 + 1 P de = P · P q-1 kq P de P mod q P de P mod pq C de P mod pq

となって、平文が復元できます。この考察から分かるのは、m の最小値は「 p-1 q-1 の最小公倍数」ということです。最小公倍数を LCM で表すと、

m = LCMp-1 q-1

であればRSA暗号は成立します。そして一般に、

LCMa b = a × b gcd a b

です。最大公約数・ gcd は「2. ユークリッドの互除法」を使って高速に計算できるので pq が巨大数であっても最小公倍数・ LCM は計算可能です。

 累乗の剰余を求めるアルゴリズム 

RSA暗号では、暗号化と複号化で "累乗(冪乗)の剰余"(冪剰余と呼ぶ)を求める計算が出てきます。この計算で使う公開鍵 en も秘密鍵 d も、また平文や暗号文も、実用的には10進数で300桁とか、そういった巨大な数です。

しかし巨大な数であっても、累乗の剰余計算ができるアルゴリズムがあります。その一つとして、ここでは「2分割法」で説明します。前回の「RSA暗号の例題」であげた、

C = 82133 mod143=4

の例で説明します。考え方としては「2.ユークリッドの互除法」と同じで、問題をより "小さな問題" に置き換えるというものです。つまり、133乗を求める代わりに

C1 = 8266 mod143

が求まったとしたら、 C は、

C = C1 · C1 · 82 mod143

で計算できます。さらに、その C1 は、

C2 = 8233 mod143

が求まったとしたら、

C1 = C2 · C2 mod143

で計算できます。この2分割を次々と続けていくと、82の16乗、8乗、4乗、2乗、1乗を 143 で割った剰余が求まれば良いことになります。これを逆にたどって電卓で順次計算してみると、

mod143 821 82 822 3 824 9 828 81 8216 126 8233 103 8266 27 821334

となり、答の 4 が求まりました。これをプログラム言語で記述すると次の通りです。


4.2  2分割法による冪剰余計算

P e modn を求める関数 RSA(Javascriptで記述)。

function RSA( P, e, n ) {
 if( e == 1 ) return P % n;//①
 else {
  var h=RSA(P, Math.floor(e/2), n);//②
  var c=( h * h ) % n;//③
  if( e % 2 == 0 ) return c;//④
  else return ( c * P ) % n;//⑤
 }
}


次はこのアルゴリズムの補足説明です。

① e が 1 なら P % n が答なので、それを関数値として返す。% は Javascript の剰余演算子で、P mod n と同じ意味。

② e が 1 でないときは、e を半分(約半分)にして答を求める。Math.floor() は小数点以下を切り捨てる Javascript の組み込み関数。Javascript では実数と整数の区別がないので必要。

③ その "半分の答" を2乗し、剰余を求めて仮の答 c とする。

④ e が偶数なら c が正しい答。それを関数値として返す。

⑤ e が奇数なら c にさらに P を掛け、剰余を求めて関数値として返す。

e, n, d が10進数で300桁程度の巨大数とします。 2 1000 は約300桁の数なので、"2分割法" を使うと1000回程度の剰余計算を繰り返すこと答が求まります。この程度の計算は現在のコンピュータで可能です。ただし可能といっても 1000回の繰り返しはさすがに大変なので、実用的にはこれを高速化する手法がいろいろと開発されています。

2. ユークリッドの互除法」で、公開鍵 en e と秘密鍵 d について、たとえ巨大数であっても高速に算出できることを書きました。それに加えて、暗号化・複号化で使われる「巨大数の累乗の剰余計算」も算出可能であり、RSA暗号の全体が "計算可能" であることが証明できました。


今までのまとめ


実用的な RSA暗号を構成するときに必要なのは、巨大な素数 p, q (10進数で150桁程度かそれ以上)です。こういった素数をどうやって作り出すか、また素数であることの判定をどうやってするかの計算手法については割愛します。

今までのRSA暗号についての説明全体をまとめると、以下の2点になるでしょう。

◆ RSA暗号は数論(整数論)の基礎から構成されている(合同、ユークリッドの互除法、フェルマの小定理、・・・・・)。

◆ RSA暗号における公開鍵・秘密鍵の生成式、暗号化・復号化の式は、実用的に計算可能である。

RSA暗号は現代の情報化社会にとって必須のものであり、社会インフラの重要な構成要素です。それは、数学が実用的に、かつ直接的に社会に役立っている例なのでした。

 
RSA暗号とオイラー関数・オイラーの定理 
 

RSA暗号の成立性の証明はこれまでで尽きていますが、以降はRSA暗号と関係が深い「オイラー関数」を説明し、次に「オイラーの定理」を導いて、そこからRSA暗号の原理を導出します。まずその前提としての「中国剰余定理」です。


5. 中国剰余定理


5~6世紀頃の中国で成立した算術書『孫子算経』に、

3で割ると2余り
5で割ると3余り
7で割ると2余る数は何か

という問題が書かれています。答は23ですが、これを一般化した定理を「中国剰余定理」と呼んでいます。

5.1  中国剰余定理

与えられた k 個の整数、 m1 , m2 , , mk は、どの2つをとっても互いに素とする。このとき任意に与えられた k 個の整数、 a1 , a2 , , ak についての k 個の式、

xa1 mod m1 xa2 mod m2  ⋮ xak mod mk

同時に満たすx が存在し、この解は M=m1 m2 mk を法として唯一である。


x1 x2 の2つの解があったとします。すると、 mod m1 の式から、

x1a1 mod m1 x2a1 mod m1

となり、1.1b により、

x1 - x2 0 mod m1

となります。同様に、 mod m2 の式から、

x1 - x20 mod m2

が言えます。 m1 m2 は互いに素なので、ここで 1.5 を適用すると、

x1 - x2 0 mod m1 m2

となります。以上のことは m3 から mk までの全ての式についても言えるので、1.5 を順次適用することにより、

x1 - x20 mod m1 m2 mk

となります。つまり、

x1 x2 modM

です。従って、解 x が複数あったとしても、それらは全て M を法として合同になります(= 解は M を法として唯一)。



ここで

Mi = M m i

とおくと、 gcd mi Mi = 1 なので、2.3 により、

Mi · Ni 1 mod mi

となる Ni が存在します。これを使って、

x = i=1 k ai Mi Ni

とおくと、それが解になります。なぜなら Mi の作り方から i 番目の項以外の項は mi で割り切れるので、i 番目の項単独で「 mi を法として x と合同」になります。つまり、

x ai Mi Ni mod mi

です。一方、合同の性質の 1.4 において y=1 とおくと 1.4 は、

axb modm かつ、
ax1 modm のとき、
axb modm

となります。1.4 の「xm と互いに素」という条件は、 x1 modm で満たされています。このことを適用すると、

x ai Mi Ni mod mi Mi · Ni 1 mod mi

という2つの条件から、

x ai mod mi

となります。これが全ての i について成り立つ。従って x が解であることが証明できました。また前段で証明したように全ての解は M を法として合同なので、x が唯一の解です。



中国剰余定理の意味を直感的に理解するために、 k=2 m1 =3 m2 =4 M=12 とし、x の全て解についての対応表を作ってみると次の通りになります。

xmod3mod4 000 111 222 303 410 521 602 713 820 901 1012 1123

この表をみると、 0   1   2 を繰り返し並べ( mod3 の列)、 0   1   2   3 を繰り返し並べると( mod4 の列)、34 が互いに素の関係にあるために、 0 0 3 × 4 = 12 回繰り返さないと現れないことが分かります。その間、x は12未満の全ての数をとり mod3 mod4 全ての組み合わせが現れる。このため、 mod3 mod4 の1つの組み合わせに対して解 x が唯一になるわけです。この状況は k がどんな数であっても、 mk どの2つをとっても互いに素である限り変わらない。

「互いに素」なゆえに成立するこのイメージは、次のオイラー関数の証明に役立ちます。


6. オイラー関数


Leonhard_Euler.jpg
レオンハルト・オイラー
(Wikipediaより)
オイラー(1707-1783)はスイスのバーゼルに生まれた18世紀ヨーロッパの大数学者です。その業績は多岐に渡り、オイラー ・・・(何とか)という定理や公式、関数、数式、等式、図などがどっさりとあります。

以下の「オイラー関数」は、一般に関数名をギリシャ文字の φ (ファイ)で表記するので「オイラーの φ 関数」とも呼ばれています。数論ではたびたび出てくる関数です。

余談ですが、オイラーは20歳台後半で右目を失明しました。ここに掲載した肖像画にもそれが現れています。


6.1  オイラー関数

オイラー関数 φ の定義は以下のとおり。

φ m  : m 以下で、m とは互いに素な自然数の個数

pq を相異なる素数とするとき、オイラー関数は次の性質をもつ。

(素数のオイラー関数値)

  6.1a  φ p=p-1

(素数の積のオイラー関数値)

  6.1b  φ pq=p-1q-1

(素数の累乗のオイラー関数値)

  6.1c  φ pα = pα - pα-1

なお「互いに素」は、すなわち「最大公約数が 1」であり、 gcd 11 = 1 なので、 φ 1 = 1


まず 6.1a ですが、素数 pp 未満のすべての自然数と互いに素です。従って、 φ p = p-1 です。

次に pq 以下の数で、p で割り切れるのは pq を含んで q 個、q で割り切れるのは pq を含んで p 個です。 pq 以下の数の全体は pq 個なので、 pq 以下の数で p でも q でも割り切れない数の個数(= pq と互いに素な数の個数)は、

φ pq = pq-p-q+1 φ pq = p-1q-1

です(6.1b)。上の式の1行目で、 -p -q には pq の分が重複しているので +1 してあります。

さらに、 pα 以下の数で、p の倍数は全て pα と共通の約数 p を持ちます。 pα 以下の p の倍数の個数は pα を含んで、

p α p = pα-1

なので、 φpα は、

φ pα = pα-pα-1

となります(6.1c)。このオイラー関数に関しては、次の「乗法性」が重要です。


6.2  オイラー関数の乗法性

gcd mn = 1 mn は互いに素 )のとき

φmn=φmφn


一般に、関数のこのような性質を "乗法性"、このような関数を "乗法的関数" と呼んでいます。証明は3段階で行います。キーワードは「中国剰余定理」と「1対1対応」です。

 第1段 

0 i < m 0 j < n である数を選び ij のペアを作ります。i の選択肢は m 個、j の選択肢は n 個で、それぞれ独立して選ぶので、相異なる ij のペアの数は mn 個です。

仮定により mn は互いに素です。従って、それぞれの ij のペアについて中国剰余定理 5.1 により、

x i modm x j modn

を同時に満たす x が、 mn を法として唯一存在します。つまり 0 x < mn の範囲では x が一意に決まります。これは ij のペアに x を対応づけられることを意味します。

逆に、 0 x < mn である x を1つ選ぶと、それに対して mod m mod n を求めて ij のペアと対応づけられる。つまり、

mn 個の ij のペアと mn 個の x の間に1対1対応が作れる

ことになります。

 第2段 

第1段の方法で作った「1対1に対応する ij のペアと x」については、

im と素であるなら、xm と素

になります。なぜなら、もし xm に共通の約数 a があったとすると(= a|x でかつ a|m )、中国剰余定理の前提から

x = km + i

と表せるので a|i となり、aim の共通の約数にもなってしまって「im と素」という仮定に反するからです。全く同様に、

jn と素であるなら、xn と素

です。この2つを合わせると、

ij のペアにおいて「im と素」で、かつ「jn と素」であれば、「1対1対応がつけられた xmn の2つの数と素」

になります。「xmn の2つの数と素」であることは「x mn と素」ということにほかなりません。つまり、

ij のペアで「im と素」であり、かつ「jn と素」であれば「 ij と1対1対応がつけられた x mn と素」

です。その逆に「x mn と素」であるなら「xmn の2つの数と素」です。そうすると中国剰余定理の前提から「im と素」でかつ「jn と素」になります。つまり、まとめると、

ij のペアのうち「im と素で、jn と素であるペア」は、「 mn と素である x」と1対1の対応関係がつけられる

ことになります。そして1対1の対応関係がつく集合の要素の数は等しい。ここが証明の根幹です。

 第3段 

オイラー関数の定義により、

m と素である i の個数は φm
n と素である j の個数は φn

です。ij は独立に選んでいるので、

ij のペアのうち、「im と素」で「jn と素」のペアの個数は、 φm φn

です。さらにオイラー関数の定義により、

mn と素な x の個数は φ mn

になります。第2段で証明したように「im と素」で「jn と素」である ij のペアと、 mn と素である x は1対1の対応関係にあります。従ってその個数は等しく、

φmn = φm φn

となって、証明が完成しました。オイラー関数の乗法性を直感的に理解するために、中国剰余定理のところであげた表を使って φ 12 = φ3 φ4 のイメージを示したのが次です。 印を付けたのはそれぞれ、 12 3 4 とは素な数です。

mn=12 m=3 n=4 0  0  0  ●1  ●1  ●1  2  ●2  2  3  0  ●3  4  ●1  0  ●5  ●2  ●1  6  0  2  ●7  ●1  ●3  8  ●2  0  9  0  ●1  10  ●1  2  ●11  ●2  ●3 



このオイラー関数の乗法性(6.2)と素数の累乗のオイラー関数値(6.1c)を用いると、一般の自然数 N のオイラー関数値を求めることができます。つまり素因数分解の一意性により、 pi を素数として、

N= p1 α1 p2 α2 pr αr

と表現できます。ここでオイラー関数の乗法性(6.2)を繰り返して使うと、

φ N= φ p1 α1 φ p2 α2 φ pr αr

となります。また、素数の累乗のオイラー関数値(6.1c)によって、

φ pi αi = pi αi - pi αi - 1

です。以上を合わせると、任意の数 N のオイラー関数値を求める公式は、

φ N = p1 α1 - p1 α1 - 1 ·· pr αr - pr αr - 1 = p1 α 1 p 1 p1 - 1 ·· p r α r p r pr - 1 = N p 1 p 2 p r · p1 - 1 ·· pr - 1

となります。つまり、N の素因数分解ができれば φ N は簡単に求まります。逆に言うとN の素因数分解が困難なら φ N を求めるのも困難になる。このことが RSA暗号が成立する背景となっています。

ちなみに、上のオイラー関数の公式の末尾の形(色を塗った部分)は、オイラーより以前に江戸時代の和算家・久留島くるしま義太よしひろ(? - 1758)が発見しています。久留島義太は、関孝和、建部たけべ賢弘かたひろとともに三大和算家と呼ばれた人ですが、自分では書物を残すことがなかったので、業績は知人や弟子がまとめたものにしかありません。その一人、仙台藩の天文学者・戸板保佑やすすけの『久氏遺稿』の中に公式の記述ができます(鳴海 風「小説になる江戸時代の数学者」- 日本数学会「市民講演会」2007.3.31 による)。

その書物には φ 360 を求める例示があります(これは暗算でも出来ます)。つまり 360 = 6·6·10 なので素因数は 2 3 5 だけです。従って 360 2·3·5 = 30 で割って(答は 12 )、 1·2·4 = 8 を掛けると φ 360 = 96 が求まる。このことが書かれています。この公式には pi の累乗の部分( αi )が全く現れません。ちょっと不思議な感じもする公式です。

日本の数学者の中には「久留島・オイラーの関数」と呼ぶ人もいます。"オイラー何とか" という名前の定理や公式はいろいろあるので、その方が分かりやすいかもしれません。


7. オイラーによるフェルマの小定理の一般化(オイラーの定理)


オイラー関数を使うと、オイラーが発見した「一般化されたフェルマの小定理」の証明ができます。

7.1  オイラーの定理

am とは素な数とするとき

a φ m 1 modm


am に何らかの制約があるわけではなく、2つの数が「互いに素」という条件だけで成立する美しい定理です。これがフェルマの小定理の一般化であることは、p を素数として m=p とおけばフェルマの小定理そのものになることから分かります。

この証明を2段階に分けて行います。まず第1段階で m が素数の累乗の時に成立することを証明し、第2段階でその結果を使って m が一般の数の場合を証明します。

7.2  

p を素数とする。

m= pα のとき、7.1 は成り立つ。


α についての数学的帰納法で証明します。まず α=1 のときはフェルマの小定理そのものなので成立します。次に α=k-1   k 2 のときに成立すると仮定します。つまり、

a φ p k-1 1 mod pk-1

が成り立つとします。そうすると、ある数 b が存在して、

a φ p k-1 = 1 + b pk-1

と表現できます。この式の左辺に 6.1c(素数の累乗のオイラー関数値)を適用すると、

a p k-1 - p k-2 = 1 + b pk-1

となります。この両辺を p 乗し、右辺は2項定理で展開すると、

a pk - p k-1 = 1 + b pk-1 p = 1 + C1p b pk-1 1 = 1+ C2p b pk-1 2 +

が得られます。この展開した右辺において、第2項は C1p = p なので b pk となり、 pk で割り切れます。また第3項以降は 2ip として Cip bi p k-1i と表せますが、 k i 2 のとき k-1 i-1 1 であり、この式を変形すると k-1i k となるので、第3項以降も pk で割り切れます。つまり、展開した第1項の 1 以外は pk で割り切れることになります。従って、

a pk - p k-1 1 mod pk a φ p k 1 mod pk

となります。この結果、7.2 α=k-1 のときに成立するなら α=k のときにも成立することが証明でき、数学的帰納法が完成しました。



7.2 を使って 7.1 を証明します。 pi を相異なる素数とし、任意の数 m を、

m= p1 α1 p2 α2 pr αr

とおきます。すると 7.2 により、 1ir のそれぞれの i において、

a φ p αi 1 mod p αi  ⋯ (1)

が成立します。ここで、

ni = m p αi   m = ni · p αi

とおくと、オイラー関数の乗法性(6.2)により、

φ m = φ ni φ p αi

となります。ここで、この式と合同式の累乗(1.2)を使って (1) 式の両辺を φ ni 乗すると、

a φ m 1 mod p αi  ⋯ (2)

が得られました。 (2) 式は 1ir i においてそれぞれ成立します。 pi は相異なる素数だったので、ここで 1.5 を順次適用すると、

a φ m 1 modm

となり、7.1 が正しいことが証明されました。



7.1 の証明の過程を振り返ってみると、次の 7.3 が成り立つことが分かります。


7.3  オイラーの定理・その2

任意の数 m の素因数分解を、相異なる素数 pi 1 i r を使って、

m= p1 α1 p2 α2 pr αr

と表す。 ψ m r 個の φ pi αi の最小公倍数とする( ψ はギリシャ文字のプサイ)。つまり、

ψ m = LCM φ p1 α1 φ pr αr

とすると、m と素である数 a について、

a ψ m 1 modm

が成り立つ( LCM= 最小公倍数)。


これは 7.1 の証明の後半(= 7.2 を使って証明する部分)からすぐに分かります。 ψ m の定義から、

ψ m = ki · φ pi αi 1 i r

と書き表すことができます。一方 7.2 より、

a φ pi αi 1 mod pi αi

が成り立ちます。この合同式の両辺を 1.2(合同式の累乗) に従って ki 乗すると、

a ki φ pi αi 1 mod pi αi

となり、これから、

a ψ m 1 mod pi αi

が得られます。この式は 1 i r であるすべての i について成立し、また pi αi は互いに素なので、1.5 を順次適用することで、

a ψ m 1 mod m

となり、7.3 が証明できました。この証明の過程から、 ψ m が最小公倍数でなくても、公倍数であれば成立することが分かります。なお ψ m は一般的な表記ではなく、ここで便宜上使った記号です。



オイラーの定理(7.1)と、オイラーの定理・その2(7.3)を

m = 3·7 = 21 a = 2

として具体的に書いてみると次の通りです。

φm = φ3 · φ7 =2·6 =12 212 =4096 =195 ·21 + 1 1 mod21 ψm = LCM φ3 φ7 =LCM 2 6 =6 26 =64 =3 ·21 + 1 1 mod21

 オイラーの定理の別証明 

いままでは「オイラー関数の乗法性」を導出して、それをもとにオイラーの定理(とその最小公倍数版)を証明しました。しかし単にオイラーの定理だけを証明したいのなら、以下のようにフェルマの小定理(3.1)のときと同じ論法で可能です。



n 以下の自然数で n と互いに素である φn 個の数を、数列として、

b1 ,   b2 ,   b3 , b φn

と並べます。これらはすべて相異なる数です。次に n とは素な数 a を選び、数列の全部にかけ算をして新たな数列、

a b1 ,   a b2 ,   a b3 , a b φn

を作ります。そして、それぞれの数を n で割った剰余を ri とします。つまり、

a b1 r1 modn a b2 r2 modn a b2 r3 modn a b φn r φn modn

です。a bi n と素なので ri 0 になることはなく、 1 ri < n です。そして、このようにすると ri は全て n と素になります。なぜなら、剰余の式を、

a bi = ki n + ri

とするとき、 ri n に共通の約数があるなら、その約数は abi の約数にもなり「a bi n と互いに素」という、そもそもの仮定に反するからです。

さらに、 1 i ,   j φn である ij について、

i j であれば、必ず ri rj

になります。なぜなら、もし ri = rj とすると、1.1b(合同式の減算)より、

a bi - bj 0 modn

です。仮定より an と互いに素なので 1.3 により(1.3 で b=0 の場合)、

bi - bj 0 modn

となりますが、 1 bi ,   bj n なので、

bi=bj

となり、 b1 ,   b2 ,   b3 , b φn が相異なる数という仮定に反してしまうからです。つまり i j であれば、必ず ri rj です。

ということは、 φn 個の数、 ri は「すべてが n とは素である、相異なる数」であり、つまり φn 個の数、 bi を並び替えたものです。従って、

ri を全部かけ算したものを R
bi を全部かけ算したものを B

と書くとすると、

R=B r1 r2 r φn = b1 b2 b φn

となります。そこで、1.1c(合同式の乗算)を上の φn 個の合同式に適用して左辺と右辺を全てかけ合わせると、

a φn ·B R modn  つまり、
a φn ·B B modn

が得られます。ここで、そもそもの定義から Bn と素なので 1.3 を使うと、

a φn 1 modn

となって証明が完成しました。


8. RSA暗号の一般形


オイラー関数とオイラーの定理(オイラーによるフェルマの小定理の一般化)を用いると、RSA暗号(4.1)の一般形を次のように記述できます。

8.1  RSA暗号の一般形

n を任意の自然数とし、e φn と素な数、d de 1 mod φ n を満たす数とする。この前提で、

暗号化: P e C modn ならば
複号化: C d P modn である。


一般形にしてしまうと、複号化の式の証明はいたってシンプルになります。 de=kφn + 1 とおくと、

C d P de modn C d = P kφn+1 C d = P · P φn k C d P modn

となり証明できました。最後の式の変形のところで 7.11.2(合同式の累乗)を使っています。また 7.3 で証明したように、 φn の代わりに ψn (= n の素因数それぞれのオイラー関数値の最小公倍数)としても、RSA暗号の一般形は成立します。

実際のRSA暗号は pq を素数として n=pq とおいたものですが(6.1b)、数学的には n の素因数分解が分かると(素因数の累乗があってもよい) φn はすぐに計算できるので(6. オイラー関数)暗号が構成できることになります。それが 8.1 の一般形の意味です。

しかし実用的な暗号のためには、素因数分解が困難であり(= n の素因数ができるだけ大きな数であり)、また暗号化・複号化の高速計算のためには n が小さいほど良いので、RSA暗号がその最適解なのでした。


全体のまとめ


最後に、RSA暗号についての説明全体をまとめると、以下のようになるでしょう。

◆ RSA暗号は数論(整数論)の基礎から構成されている。その基礎には、ユークリッド、孫子算経、フェルマ、オイラーなどによる数学史の重要な発見が詰まっている。

◆ RSA暗号における公開鍵・秘密鍵の生成式、暗号化・復号化の式には巨大数の演算が現れるが、それは実用的に計算可能である。

◆ RSA暗号の原理は、整数の "加減乗除" と "累乗(冪乗)" の知識をベースとして、そこから論理を積み重ねることで理解可能である。つまり「高校数学程度の知識で理解」できる。

この最後の点が、ここに「RSA暗号の数理」を掲載した目的でした。




nice!(0) 

nice! 0