情報システム工学科における数理情報教育の講義例

情報システム工学科における数理情報教育の講義例

情報システム工学科 工 藤 愛 知

[email protected]‑u.ac.jp  はじめに 情報システム工学科に「数理・応用ソフトウェア工学講座Jがあり平成 1 0 年度の入 門科目の当講座の受け持ち日に簡単な符号と暗号の話を 1 回ずつ行った.

線形代数もまだ十分に学んでいない時期なので，それは使わず，できれば逆にこれから学ぶ線 形代数や応用代数学の必要性を印象づけるものになればという構成にした.

入門科目とはいえ工学の専門につながる講義を担当したのは始めてなのでまだまだ試行段階で あるが，講義で使用した資料をもとに数理情報教育のったない講義例としてその内容を紹介させ て頂くことにした.

第 1 部が誤り訂正符号の話で，第 2 部が暗号の話である.第 1 部は学生の理解もなかなかよかっ たと記憶している. 0と 1 だけでする数学が意外な応用面を持っていることが新鮮に映ったのか もしれない.しかし第 2 部はよく考えてみると 3 回分位の内容だったこともあり十分に理解して もらえたとは思っていない.再度これを取り上げるならば，工夫したいと思っている.

工学部へ入学した新入生がなるべく抵抗なく数理の世界を訪れ，忍耐を苦にせず専門の課題に 取り組んで行けるようになることが，私たちの望みである.ここで取り上げた話が数理情報のす べてでないことはいうまでもないが，入り口から少し内側を覗くことが隣接分野を知る手がかり になると信じて講義を行った.当学科で「新しい情報教育」となれば非常に重い問題である.そ こでの一導入教育例としてご覧いただければ幸いである.

第 1 部 誤り訂正符号入門

~ 1 . 1 情報の符号化

情報源符号化 情報の送受信，保存・再生には，符号化・復号化という操作が含まれる.符号 化とはここでは情報源の情報を 0と 1 の系列に変換することを指すことにする.復号化は， 0と 1 の系列をもとの情報源の情報に戻すことである.情報源は，画像であったり，音声であったり，

普通のアルファベットで書かれた文書情報であったりする.これらを 0 と 1の系列に変換するこ とを，情報源符号化という.そこでは，画質や音質を損なわない符号化は何かとか，符号系列が 長くなり過ぎない効率のよい符号化は何かとかが問題となる.

情報源符号化には，効率のよい符号化のために統計学や動的計画など，波形・パターンの再現 のために解析学や物理学など，視覚・聴覚の特性との関連で医学や心理学なども動員される.圧 縮・展開もこの情報源符号化の理論に含まれるといえる

通信路符号化 次に，これらの問題をクリアして作り出された Oと 1 の系列を，通信路を通し て送受信することを考える.そこでは，何らかの原因で 0が 1 に，あるいは 1 が 0に誤って伝 えられることがある.保存・再生においても，磁気の劣化や盤面の傷や壊によって閉じことが起 きる.これらはどうしても避けることはできない.そのような誤りのできるだけ多くを検出した り訂正したりできるように，符号化された情報源(情報源符号)をさらに符号化することを，通 信路符号化という.

ここでは，通信路符号化に導入されるアイデアのごく初歩を紹介したい.

1

想像に難くないように，ここまでの段階で技術は細分化され専門化される.誤り訂正符号や暗号の数理はこれらの

分野でも利用可能な知識やアイデアを提供すると思われる.

9 1 . 2 誤りの検出・訂正 情報源符号化された O と 1 の系列 0110100111001 ・ .. 

が送信され，

0110000111001. . .  

を受信したとする.誤りをチェックするには，プロックを設けて検査するのがよい.例えば，上 の例では，

0110 1 1 0 0 1  11100 11

が送信され，

0110 1  0001 11100 1  1

を受け取ったとみる.この場合は 2 番目のプロックの最初に誤りがある.しかし，受け手は受信 情報しか見ることができないので，誤りがあったかどうかわからない.もちろん訂正もできない.

そこで次のような方策を考える.

白 プ ロ ッ ク を 2回ずつ繰り返し送信する.

例えば 1100111001 1  ( 4個の情報ヒ

ツトと 4個の検査ビット)を送信して， 11001 1  0001 1 を 受信したとすれば，この 8 ピットの送信中のどこかで誤りが起きたことがわかる.どのピットが 誤りかはわからないが，可能ならば再送要求を出すことができる.ただし 2回誤るとそれを検出 できないことがある.

回 プ ロ ッ ク を 3 回ずつ繰り返し送信する.

例えば 11 0 0 1  1  1001 1  1001 1  ( 4個の情報ヒ・ットと 8個の検査ピット)を送信して， 1  1 0 0 1  1  0001 11001 1 を受信したとすれば，この 1 2 ピットの送信中のどこかで誤りが起きたことがわか

るだけなく，多数決により 1 0 0 1が送信されたものと推定できる.

考察 4個の情報ピットを送る聞に誤りが起きる確率より，検査ピットを含む 1 2ピットを送る 聞に誤りが起きる確率のほうが当然大きい.しかし，誤りの少ない送信路では， 4個の情報ピッ トを正しく送れる確率は単純に送るよりは大きくなる.問題は送信量が 3 倍にもなることである.

4 個の情報ピットに 3 個の検査ピットを付け加えるだけで， 1 個の誤りまでなら訂正できる符号 化法の最も簡単なもののひとつをのちに囚として紹介する.

回 lの個数が偶数になるように検査ヒ

ットを l個つける.

例えば 1 0 0 1は 10010 ，1000 は 1 0 0 0 1と符号化して送信する. 1の個数が奇数であるような 5 ピットを受け取ったら，送信中に誤りが起きたとわかる. .5ピットの送信中に 2箇所または 4箇 所で誤るとそれを見過ごしてしまうが，囚の方法よりも考えられた方法であるといえ，実用化も

されている.

問 o を 1と . 1 を Oと誤る確率がともに 0 . 1 =  1 / 1 0の送信路を通して. 4 個の情報ピットを単純 に送るとき.どこかで誤りがあっても検出できず受け入れてしまう確率はいくらか.囚の方法を使うと，

それはどうなるか.

k個の情報ピットに，一次式を用いた一定の仕方で η ‑k 個の検査ピットを付加して作れるよ

うな長さ η のピット列全体 C を線形 π [ ， k ] 符号という . C に含まれるピット列は C の符号語と

呼ばれる.

先に図で述べたようにしてできる長さ 5のピット列の全体を α としよう . α は線形[.5， 4 ]   符号である.それは 4 個の情報ピット XIX2X3X4 (Xi は O または 1 ) に，一次式

Xl  +  X2  +  X3  +  X4  +  X5  =  0 

で定まる検査ピット X5 ( 0 または 1 ) を付加してできるピット列 XIX2X3X4X5 の全体だからであ る.ただし，集合 { O ， l } 上の足し算は

￨ +  1 101 11  1 o  1 10  1 1  1 

￨ 1  1 1 1   1  0  1 

で与えられるものとする.すなわち，例えば，

1  +  0  +  1  +  1  +  0  =  1 ，  1  +  0  +  1  +  1  +  1  =  0 ， 

などとなる.さらに，集合 { O ， l } 上の掛け算を

￨110 1 1  1 

￨ 0 1 1 0 1 0 1 ・

1 1 1 1 0  1 1  1 

と定める.このような足し算と掛け算をそなえた集合 { O ， l } をこれからは F とかくことにしよ う. Fでは X + X = O だから ‑ X = X であることに注意する.

長さ η のピット列 XIX2 ・ ・ ・ z π をベクトノレのように:z: =  (Xl ， X2 ， ・ . ・ ， X π ) と表すこともある(た だしもとの記法も併用する).その全体を F =  {(Xl ， X2 ， ・ . ・ ， _Xn) I  Xl ， X2 ，. ・ • ， _Xn  E  F} とかく.

F 司にはあきらかに 2 ⁿ 個のピット列が含まれる.

ベクトノレの記号を用いたついでにピット列 : z : =  (Xl ，  X2 ， ・ . .， Xn) とピット列 y =  ( Y l ，  Y2 ， ・ . ・ ， Yn) 

の和を，

: Z : + ν = (Xl  +  Yl ，  X2  +  Y2 ，  ・ ・ ・ ， X π+Yn) ， また内積:z: .y を ，

: z :   .  y  =  ^XIYl  +  X2Y2  + ・ ・ ・ + X πYn

で定める.この和と内積については:z:.  ν ( +  z )   =  : z :   .  y  +  : z :   .  zが成り立ちすぐ後で利用される.

これらの取り決めのもとでは，回を次のように述べることができる.

( l ， l ， l ， l ， l ) . : Z :   =  0 をみたすヒーット列:z: =  (Xl ， X2 ， X3 ， X4 ， X5) の全体が，先に述べた C ₅ である.

F5 には 2 ⁵ =  3 2 個 ， C 5 には 2 ⁴ =  1 6 個のピット列が含まれる. C 5 の符号語 z を送信する . C ₅  の符号語でない長さ 5 のピット列 _U εF5 _{，すなわち，} ( 1 _， 1 ， 1 ， 1 ， 1 ) .   _Y  = f .   ^{0 なる} U を受信したら，

通信路で誤りが混入したことがわかる.正確に伝えられたのなら， y= : z : で ( 1 _， 1 ， 1 ， 1 ， 1 ).  _Y  =  0 

のはずだからである.

囚 長 さ 4のヒ

ット列 Z 向 ^Z 山に，検査ピ・ット Z 向 ^Xr を，次の一次式

X2  +  ^X3  +  ^X4  +  ^X5  =  ⁰ 

Xl  +  ^X3  +  ^X4  +  ^{X6  =}  0 

Xl  +  ^X2  +  X4  +  ^Xr  =  ⁰ 

で定め，長さ 7 のピット列 x =  ^{(Xl ，  X2 ，  . ・ " Xi)} にする.このようにしてできたヒ'/ト列 zの全 体を C 7 とかく. C7 ^{は線形 [ 7 ， 4 ] 符号で， 2 元ハミング [ 7 ， 4 ]} 符号として知られるものである.

例えば 1 0 0 1 に付け加える検査ビット XSX6X7 は， Xl  =  1 ，  X2  =  0 ，  X3  =  0 ，  X4  =  1 であること から，上の式を用いて

Xs  =  X2  +  X3  +  X4  =  1 ，  X6  =  Xl  +  X3  +  X4  =  0 ，  ^{Xi  =  Xl}  +  ^{X2 十 X4 =}  0  と計算でき， 1 0 0 1 は ， 1 0 0 1 1 0 0  E  C i と符号化される.

いま，

p =   ( 0 ， 1 ， 1 ， 1 ， 1 ， 0 ， 0 )   q=  ( 1 ， 0 ， 1 ， 1 ， 0 ， 1 ， 0 )  

r  =  ( 1 ， 1 ， 0 ， 1 ， 0 ， 0 ， 1 )   とおく.すると， C _s を内積により表したように ， C 7 ^も

C 7   =  {  x  E  F ⁷  I  p  .  x  =  q ・ x=r ・ x =  O }  

と表すことができる . F ⁷ の 2 7 _{=  1 2 8個の長さ 7のピット列中， 2} ⁴  _{=  1 6個が} C 7 の符号語で ある.

C ₇ の符号語 x を送信するとき Uを受信したとする.正しく送られたのなら ， y=x だから

︑ ︑

︑

. E

・

・

‑ ‑E E

︐ ︐ ︐ ︐ ︐

nununU 

︐ ︐

︐

I l l i

‑ ‑ ︑

一 一

︑

EE

EE

Et

gF

J

uuu 

p q T  

J 't e a ‑‑ ‑

‑ ‑E E

‑ ‑

・ ・ ︑ ︑

のはずである.

さて，今度は ν が 1 ピットの誤りを含んだとする.

el  =  ( 1 ， 0 ， 0 ， 0 ， 0 ， 0 ， 0 )  

e2  =  ( 0 ， 1 ， 0 ， 0 ， 0 ， 0 ， 0 )  

e 7   =  ( 0 ， 0 ， 0 ， 0 ， 0 ， 0 ， 1 )  

とおく . x  E  C 7 の第 t座標が誤って伝えられたとすると ，y  =  x+e.i である.したがって

︑ ︑ 1 2 1 1 1

S‑zez 

e e e   p q T  

/t ts 'E I‑

‑1  

一 一

︑ ︑ 1

2 1 1 1

﹄

F

f

︑

︑ .

︐

F

︑

‑S

・

g

z

e e e  

+++ 

2 2 2  

( ( (   p q T  

/I

EB

EB

EE

‑‑

︑

一 一

¥21111/  uuu 

p q T  

/ 1 1 1 1 2 1 ︑ ︑

3  4  . J   6  7 

が得られる. 誤りが l箇所だけなら，この表をみて，次の例のように訂正できる.すなわち，

情報ピット ( 1 ， 0 ， 1 ， 1 )   ー → ^{ε =} ( 1 ， 0 ， 1 ， 1 ， 0 ， 1 ， 0 ) 符号化)

一 → y =  ( 1 ， 0 ， 1 ， 0 ， 0 ， 1 ， 0 ) 受信)

の場合，

且 畠 守

Bム

句

aム

〆I tE tt E1 1¥

一 一

︑ ︑

︑

EBEE‑‑‑EZ

︐ ︐ ︐ ︐ ︐

uuu 

p q T  

ff

﹄t

EZ EE

‑¥

であるから，表により，第 4 座標を訂正すればよく，

ド ( 1 ， 0 ， 1 ， 0 ， 0 ， 1 ， 0 ) → ( 1 ， 0 ， 1 ， 1 ， 0 ， 1 ， 0 )

→ ( 1 ， 0 ， 1 ， 1 )  

(訂正) (復号化)

となる. しかし， 7ピットの送信中 2箇所で誤りを発すると情報 4 ピットを誤って復号する.

問 2 次を符号化せよ.

( 1 )   1 0 0 0   ( 2 )   0 1 0 0   ( 3 )   0 0 1 0   ( 4 )   0 0 0 1   ( 5 )   1 0 1 0   ( 6 )   1 1 0 1   問 3 次の受信ベクトルを復号化せよ.

( 1 )   1 0 0 1 0 1 1   ( 2 )   0 1 0 0 0 1 1  

この間 2 の ( 1 ) ^ー ( 4 ) を符号化するだけで ( 5 ) ， ( 6 ) の符号化にそれを利用できるのが線形符号の特 長であることや， π誤り訂正符号が別の理論により構成されることに触れてこの日は終った.

第 2 部 暗 号 の 話

基本概念 情報を盗聴から保護したり，ネットワークへの不正な侵入を防ぐ技術が暗号である.

情報は文章とは限らないがここでは話をしやすくするため文字で書かれたメッセージとしておく.

送りたいメッセージを平文と呼ぶ.そしてこれを第三者には読めない文に変換したものを暗号文 と呼ぶ.平文を暗号文に変換する操作を暗号化といい，暗号文を平文に戻す操作を解読という.暗 号化・解読に必要な鍵 (Key) を暗号化鍵・解読鍵という.

~ 2 . 1 簡単な暗号系 最も単純な暗号系は文字 A‑Z とその順序をランダムに入れかえたものと の対照表を用いるものであろう.この対照表がこの場合の暗号化鍵・解説鍵である.しかしこれは 鍵を外部に漏らさずに保有するのが難しい.それよりもむしろ， A‑Z を並びのまま 3 字うしろ へずらす(うしろへはみ出した x‑Z は A‑C に対応させる)ほうが機動性に富んでいる 2 例 えば， YES は BHV と暗号化するのである.これは古代ローマにおいて J u l i u sC a e s a r が実際に 考え使用した方法と言われている.

シフト暗号系 この J u l i u sC a e s a r の暗号系を数理化してみよう.そのために次のような簡単 な代数系 Z26 を考える . Z26 は集合

{O ，  1 ，  2 ，  3 ，  " ' ，   24 ， 25} 

の上に ， a ，  b  E  Z26 に対して，

α +b は，通常の ^α +b を 26で寄 l った余り，

αbは，通常の αbを 2 6で割った余り

なる足し算と掛け算を定義したものである .Aには 0，Bには 1，C には 2 ， ・ ・ Zには 25 を対応 させておく.文字に対応する数値 zに対して Z26 で y=x+3 を行うのが暗号化， x= ν+23  =  y‑3  を行うのが解読である.例えば，

Y  →  24  →  24  +  3  =  ¹  →  B 暗号化) B  →  1  →  1  +  2 3   =  24  →  Y 解読)

2

少し時間を稼げばよい場合は.

となる.この場合，KE=3 ε Z26が暗号化鍵，K D   =  ‑3  =  2 3 ε Z26が解読鍵である.これは シフト暗号と呼ばれる.

アフィン暗号系 文字に対応している Z ε Z26に対して

ν = α x 十 b (

α ，  b は Z26の定数)なる変換を行って暗号化する.そして，

x = α 一 1 ( y̲ b )   = α‑1u‑α 一 1 b

で解読する.もちろん a‑1は Z26 の α c=  1 なる

のことである.これができるためには，

g c d ( α ， 2 6 )   =  1 としておけばよい.ここに， g c d ( s ，  t ) は s と t の最大公約数を表し， g c d ( s ，  t )   =  1  のとき s と t は互いに素， s は t と素，あるいは， t は s と素という.この方法では， K E =   ( α ，  b )   が暗号化鍵，KD  =  α ( ‑ 1 ，  ‑a‑1b)が解読鍵である.これはアフィン暗号と呼ばれる.

通常，メッセージは単語と単語の問のスペースがなければ読みにくいし，コンマやピリオド，数 字や記号文字も必要だろう.以下では，これらも加えた N 文字に， 0 から N ‑ 1までの数値が 対応しているものとする.さらに，これまでのおのところを一般化して m とした， Zm とかく 代数系を，同様に定義し使用する ³

さて，上のどの方法で得られた暗号文でも，平文がどの国の言葉で書かれたものかがわかって いれば，文字の出現頻度分析によって解読されてしまうことがある.

h 字組 スペースも 1 字と見て，平文を例えば 3 字単位で分割する ( k=  3 ) . このひと区切りの 文字列 AoA1A2 に数値 α 0 ， α 1 ，向が対応するとき 4 この区切りに x = α 2 N2+ α 1 N + α 。なる数 値 Z を対応させる.長さ 3 の区切りは N ³ 通りあるが，こうすれば，それらに ON 2+ON +0  =  0  から (N‑1)N2  +  (N  ‑ l)N  +  (N ‑ 1 )   =  N ³  ‑ 1 までの N ³ 通りの数値が 1 対 1 に対応する.

α が N と素であるような α ，b  ξ Z ( N 3 )を一組決めておいて ，Z ( N 3 )で y = ω +bを計算する.

次に， ν(0 ~ y  <  N ³ ) の 3 桁の N 進表示 y=  b 2 N2  +  ^b 1 N  +  ^b o  =  ( b 2 b 1 b o)Nを求めて，数値 b o ^{，  b} 1 ，  ~に対応する文字列 BoB1B2 に暗号化する.こうすれば文字の頻度分析はかなり難しく なる.これが 3 字組に拡張されたアフィン暗号化である.

この方法を多くの人が使えるためには，少なくとも，使用できる N 文字の指定と， 0 から N‑1 までの数値との対応表は，規格として認められている必要がある.その上で，例えば k字組に拡 張されたアフィン暗号ならば， α が N と素であるような α ，b  ε Z(Nk)を他人に知られないよう に選び，暗号化鍵 K E =( α ， b ，  k ) と解読鍵 KD =  (α‑1α ‑1b ， k ) をメッセージの送り手・受け手 共通の秘密にすればよし、 5 α一 1 および一 α ‑1b は，もちろん，Z(Nk)で求めた値である.

秘密鍵暗号 方法は違っても上述のような暗号化鍵・解読鍵を当事者間だけの秘密にしておく タイプの暗号は，秘密鍵暗号または古典暗号と呼ばれる.秘密鍵暗号においては，鍵の受け渡し にもまた暗号が必要で，そのための特別な暗号も考察されている.

問1 Z lOにおいて 3 ‑ ¹ および ‑3‑ ¹ 2 は何か.

問 2 あるとき B が A からアフィン暗号化法における暗号化鍵を受け取り， A に暗号化メッセージを送っ た.その後 A が同じ暗号化鍵を用いて C に暗号化メッセージを送った場合 B がそれを傍受すれば解読で きてしまう.なぜか.

3

第 1 部の F はあに他ならない.

4

スペースも含む N 文字に 0 から N ‑ l までの数値をあらかじめ対応させてあるものとする.

5

この場合は当然 k 桁の N 進表示を介して暗号化と解読を行う.なお N と素"は N

と若者"に同値である.

これらの聞から，アフィン暗号系では暗号化鍵から解読鍵が簡単に計算されてしまうこと尺およ び，使用する際にはどんな注意が必要かがわかる.

S  2 . 2 公開鍵暗号 A ，  B ，  C がそれぞれ自分宛ての暗号化メッセージのための暗号化鍵 Ifr) ， kg) ， Kg) を公開し， A は CI こ解説されずに B へ ま た ， B' こ解読されずに C へ暗号文を送る

ことができ， B ，  C もそれぞれ同じことができる方法がある.それを公開鍵暗号という.

これは，暗号化鍵 KE と解読鍵 KD をセットで作るのは容易で，暗号化鍵を知ってもそれから 解読鍵を作るのがたとえ計算機を使っても困難であるような方法があれば実現できる.秘密鍵暗 号は暗号化鍵から解読鍵が容易に計算できてしまうために暗号化鍵を公開できない種類の暗号と いうことができる.

公開鍵暗号の一つに， R i v e s t ，  S h a . m i r ，  Adlem a . n の 3 人が作った RSA 暗号がある.それは，

整数に関する次の有名な定理に基づくものである.

フヱルマ・オイラーの定理 1 ， 2 ，  ・ . n の中の z で g c d ( x ， n ) =  1 をみたすものの個数を t . p ( η ) とかく.すると， g c d ( α ， n )   =  1 をみたす任意の整数 α に対して a

( n ) ー 1 は π で割り切れる 1

問 3 P が素数のとき t . p ( p ) =  p  ‑ 1 を示せ.

問4 p ，  qが相異なる素数のとき t . p ( p q ) =  ( p  ‑ l ) ( q  ‑1 )を示せ.

t . p ( π ) はオイラーの関数とよばれ， g c d ( m ， π )   =  1 ならば ψ (mn) =  t . p ( m ) t . p ( n ) という性質も持つ ている.

RSA 暗号における公開鍵の作り方 メッセージに使用できる文字 N 個とそれらの O から N‑1

までの数値との対応付けは規格化されているものとする.さらに ， N ^k ，  N ^l が 1 0 進でそれぞれ

2 0 0 桁位になるような整数 k ， 1  ( k く l ) を，これも規格として，設定しであるものとする.

鍵の作成者は， 1 0 0 桁位の素数の中から N ^k <pq く N ^l をみたす十分に離れた 2 つの素数 p ， q  を密かに選び， π=pq を計算する.

次に，公式 ψ ( n ) =  ( p  ‑ l ) ( q  ‑ 1 ) により t . p ( π ) を計算し， g c d ( e ，  t . p ( n ) )   =  1 なる整数 e( 1 く

e く ψ ( π ) ) を適当に選び， Z (

π ) ) における d =  e ‑ ^{1 を計算する.}

そして，暗号化鍵として KE =  ( e ， η ) を公開し， KD  =  ( d ， n ) の d を鍵の作成者だけの秘密と する.作るときに用いた p や q や t . p ( n ) は忘れてしまってもよい.

以上のことは計算機を使えばすべて容易にでき，一方， KE の e と π から t . p ( n ) を，したがっ て d を求めることが 8 ほとんど絶望的であることがポイントである. 1 0 0 桁位の整数が素数であ るかなし、かを判定するのは計算機を使えば簡単であるのに対して， 1 0 0 桁位の最小素因数をもっ 合成数 η を素因数分解したり，伊 ( n ) の値を求めるのは，よほど幸運なときを除き現在のところ膨 大な計算時間がかかることによる 9 ， 1 0 . したがって暗号化鍵 KE =  ( e ， n ) の公開者が 1(D =  ( d ， η )   の d を秘密にする限り，暗号文は第三者に解読されない.それどころか，送ったメッセージを忘 れてしまったら，あとからそれを確認したいと思っても送り手 1 こさえ解読できない.解読した受 け手に頼み込んであらためて教えてもらうしかない.

ー 問 1 では m = 1 0 だが m がいくら大きくてもユークリッドの互除法を計算機上で実行すればたちどころである.

7

この定理の証明は省略するがそんなに難しくはない.この話での眼目の一方は π が 2 つの素数 p ， q の積であると き p ， q を知っている者(鍵の作成者)にとっては ψ(π) の計算が次の間 4 の公式を使って簡単にできることである.

8 r p ( π ) が知られてしまえば d は e からユークリアドの互除法(これは鍵の作成者が Z (

で d =  e‑I を計算す るのに用いるアルゴリズムである)で簡単に求められてしまう.

9

年の単位である・ ψ ( n ) を見破るために π から p ， q を見つけるのも.定義によって 1 から π までの整数のうち π と素なものを数え上げるのも容易でない.数億，数兆程度の π を考えていると想像もつかな u 、かも知れないが.

10

計算機の性能がアップしでも素因数分解の理論に飛溜的な進展がない限り p ， q の桁数設定をもう少し大きくして

やるだけで足りる.実は素因数分解の理論も進展してきており大きく ても選ぶと危険な素数の組合せはある.

RSA 暗号の仕組み それでは B によって公開された暗号化鍵 KE =  ^{( e} ， n ) を使って， A が B

に暗号文を送り， Bがそれを解説するまでのプロセスを見てみよう.

[送り手 A( の計算機)が行う処理] (暗号化ー送信)

El  送りたい平文メッセージの先頭から長さ k の文字列を読み込む.

E2  ひと区切りの文字列 AoAl...A

1 に対応する数値 α 0 ， a l ， . ・ 1αk‑l から数値 x =α0+

αlN+ ・ ・ ・ +α ト lN k‑1 を計算する o ~三 x <  N ^k  <  n だから Z はそのまま Zn の元とみなせる.

E3  送りたい相手 B の公開した暗号化鍵 KE =  ( e ， n ) を用い， Z π の中で y =  x ^e を計算する 1 1

E4  Y を N 進表示する. 0  ~y < ^{η く} Nl だから ， y  =  ( b l ‑1 ・ ・ ・ b 1 b o ) N =  b o+b1 N + ・ ・ ・+ b l ̲1 N ^I ‑ 1 なる数値 b o ， b 1 ， . . . ， b l ‑1 が得られる.

E5  0  ~三 bj ~ N ‑ 1  ( 0 壬 j ~ 1‑1 ) であることを用いて，数値 b o ， b 1 ， ・ ・ ・ ， b l ‑1 を規格により対 応する文字列 BoBl...B l ‑ l に直し送信する.メッセージがまだ残っていれば El に戻る.

暗号化に Zn での y =  ^{x e} を用いたことに注意しよう.解読には Z π での z =ydを用いるので ある.これらの合成 z =  ( x e ) d   =  xe d が み に お け る 恒 等 変 換

xe d   =  x  ( x   E  Z n )  

になるのがこの暗号のかなめである.これの証明は最後(命題)にまわし，暗号文を受け取った

B  (鍵の作成者)がどのようにしてこれを平文に直すかを見ておこう.

〔受け手 B (の計算機)が行う処理] (受信一解説)

受け手は暗号文の l 文字を受け取るごとに次の操作を行う:

Dl  受け取った長さ l の文字列 BoBl ・ ・ ・ B l ‑ l ( もちろん意味不明の文字列である)を対応する 数値 b o ， b ₁ ，  .  .  .  ， b _{l ‑1} に直す.

D2  数値 y =  b o  +  b 1 N  + ・ ・ ・ + bl̲1N ^I ‑ 1 を計算する.これは A が E3 で作った ν である.

D3  O~y く n となるはずだから，これを Zn の元とみて ， Zπ で z= 〆を計算する.これに 自分だけが知っている解読鍵 KD =  ^{( d} ， n ) の dを用いる.

D4  上に述べた事実から，この z は A が E2 で計算した数値 ^Z となる. 0 孟 z く N ^k のはずだか ら， x の N 進表示 x=( α ト 1 ・ ・ ・ α 1 α O)N =α0+αlN+ ・ ・ ・ +αk̲lNk‑1 を求めて ， 0  ~α<三 N-1 ( 0   _{~三 i ~三 k} ‑ 1 ) なる数値向， α 1 ， ・ . 1 α k‑l を得る.

D5  この数値を対応する k 個の文字よりなる長さ k の文字列 AoAl...Ak‑l に戻す.まだ暗号 文が続くなら次の l 文字を受信して Dl へ戻る.

暗号文らしさを出すために，あたかも暗号化された 文"が送受信されているように述べたが，実 際は，圧縮，暗号化，通信路符号化などを経た符号語が送受信される.

郎 A 暗号では， A ， B， C， ーがそれぞれ暗号化鍵 K k ^{A ) =  ( 白 川A) ，} K k ^{B )  =  (仏句) ，}  K 1 ^{C )  =  ( e c，}  nc)， ...を公開してどの 2人もお互いを除く他人には秘密にメッゼ二一ジをやりとり できる. AIこ暗号文を送るときは皆が K k ^{A )} =  ( e A ， π A ) で暗号化する . Aは誰から暗号文を受け 取っても K 1 ^{A )} =  ( d _A ，  n A ) で解説する. BがAIこ送った暗号化メッセージはAにしか解読できな

lly

は普通の x . を π で割った余りとなる.普通の x . はとてつもなく大きな値となるので，オーパーフローさせな

いようにプログラムの工夫がここで必要となる.しかしそれは容易.

いのだから， A と B 以外には漏れない.もし何らかの危険を感じたら A は K k ^{A )} =  ^{( e A} ，  n A ) と

K 1 ^A)  =  ^{( d A} ，  nA) を作り直して新しい Kr)を公開すればよい.他の公開鍵暗号でも使い方は同 じである.

命題 p と qを相異なる素数とし， η = ^{p q} とする. e ，  d を Z ( ψ ( π ) ) で ed =  1 なる整数 ( 1 く e く ψ ( π ) ，1 く d く ザ ( π ) ) とする.このとき，任意の整数 x( 0 孟 x <  ^{n )} に対して ， Z π で

x ^ed  =  x が成り立つ.

[証明] dは，Z (

( n ) ) の元として ed =  1 が成り立つようにとったのだから，普通の整数として は ed =  1  +  r . p η ( ) t   ( t は整数)とかける.よって x ^ed =  x

π ) t   =  x ( げ ( π) ) t である.

さて， gcd(x ，  n )   =  1 の場合は，フエノレマ・オイラーの定理から，げ ( π ) =  1  +ns ( s は整数)と かける.これを前の式に代入して t 乗を展開すれば， x ^ed を ^η で劃った余りは x ，すなわち ，Z π

で x ^ed =  x であることがわかる.

gcd(x ， n )   >  1 の場合は. n  =pq であったから x ; 6 0 なら gcd(x ， n )   =  p または gcd(x ， n )   =  q  である .x=O のとき x ^ed =  X はあきらかだから .x ; 6 0 として，例えば. gcd(x ，  n )   =  q とす る.このときあきらかに gcd(x ， p ) =  1 である .ψ ( p ) =  p  ‑ 1 であるからフエノレマ・オイラーの 定理により x p‑ ¹ =  1  +  p 1 1 .   ( 1 1 . は整数)とかける.このことはむしろフェノレマの小定理としてよ く知られている .ψ(π) =  r . p ( p q )   =  ( p  ‑l ) ( q  ‑ 1 ) より， ed  =  1  +  r . p η ( ) t   =  1  +  ( p  ‑l ) ( q  ‑l ) t だ から x ^ed =  x ( ♂ー 1 ) ( q ‑ l ) t   =  x ( l   + 仰 ) ( q ‑ l ) t で，これを展開して z を引けば， Xed ‑ X は p で害 J I

り切れることがわかる.一方， gcd(x ，  n )   =  q なる仮定から ， x は qで割り切れるから x ed‑ x は qで割り切れる.よって x ed̲ X は pq= πで割り切れる.よって x ^ed を nで割った余りは zで ある.すなわち ， Zn で x ^ed =  x である. gcd(x ，  n )   =  p のときもまったく同様である. (証明終)

~ 2 . 3終りに 秘密鍵暗号系と公開鍵暗号系の中で，代表的かつ比較的やさしいものを紹介した.

話の順序で，公開鍵暗号のほうが秘密鍵暗号より優れたもののような印象を受けたかもしれない が，必ずしもそうではない.例えば RSA 暗号の例では， A以外の者がAになりかわって B にメッ セージを送ることができる. Bがそれによって重大な損害を被るというような状況はいくらでも 考えられる . BがAから受け取る必要があるメッセージを受け取ったときそれが確かにAからのも のであることを検証できる手段も必要であり，デジタノレ署名という考え方で確かに存在する.以 上 2 回にわたって符号および暗号の数理のさわりの話をしたが，興味を持った人はその基礎と なりそうな体系を積極的に勉強しておいてほしい.それらは，たとえどの分野に進もうとも必ず 役に立つはずである.

参考書

ヴェラ・プレス著，伊藤昇訳，符号理論入門，ワイリー・ジャパン， 1 9 8 4  

N. コプリッツ著，樫井幸一訳，数論アルゴリズムと楕円暗号理論入門.シュプリンガー・東京， 1 9 9 7   武田二郎著，代数系と符号理論，槙書庖， 1 9 7 8  

今井秀樹，情報理論，昭晃堂， 1 9 8 4  

藤原良・神保雅一共著，符号と暗号の数理，共立出版， 1 9 9 3  

増田真朗著，応用のための代数系入門.サイエンス社， 1 9 8 1