暗号の中の数学
計算可能性について

澤田秀樹
はじめに
インターネット（IlltCI・Ilet）という言葉はもうすっかり私たちの日常生活に定着している。この世界中の大学や研究機関，企業等の内部ネットワークを互いに結ぶ巨大なネットワークほ，世界150か国以上にわたって2000万台以上のコンピュータが関係しているのにもかかわらず，特定の管理者によって運営されているわけではないという特徴をもっている。このような，技術的な約束ごとと少しずつ整備されつつある法律のもとでなんとか運営されている，ネットワーク上を第三者によって改変や盗聴が可能なデジタル情報が行き交っているわけだから当然そこにはさまざまな問題が生じている。
今日ここに来られた皆様には暗号理論がデジタル情報の保護に有効であることを新聞や雑誌ですでに何回か目にされ，公開鍵暗号とか素因数分解とかいった暗号理論や初等整数論の用語に親しまれた方も多いとおもう。この講演ではまず・暗号について概説し，つぎに・その基礎にある「計算する」ことについて考え，さらに● 数ある暗号の中からRSA暗号やEIG之tlflal暗号といった公開鍵暗号をとりあげて説明したい。

1 暗号とは何か「暗号（cl・yptogl・apIly）とは情報の交換や記憶集積に際して，第三者にそれが知られることや，あるいはさらに当事者をも含めて故意による情報の改変を防ぐために，その対象となる情報を秘匿する技術や方法のことである。このような暗号について研∫ 〃α（Jα：暗号の中の数学

究する数理情報科学を暗号理論（cI・yPtOlogy）と呼ぶわけであるが，その中には暗号の組立（cllCl・yptioll），翻訳（dccryptioIl），解読（cryptaIlalysis）や暗号鍵の管理（kし一yIIlaIlagCrnCIlt）や暗号発信者等の認証（atltllCll捕catiorl）などが含まれる。」と言った

りすると，なんだかとても難しいことのように聞こえるかも知れない。
要するに暗号と言うのは，情報を伝えたり記録したりするときにその内容が第三者にはわからないようにする手段のことであり，もっと広く解釈して内容が不明でその解読には特別な方法を用いるものも指す。ではさっそく暗号の実例をあげよう。
［宰例］転置式暗弓−（Tl・皿SpOSitiollCipllCl・）

原文に現れるビット列1や文字列の順序を入れかえて暗号化する方法を転置式暗号と呼ぶ。この方式ではたとえば次のレールフェンス暗弓・（R之tilfbIICCCipllげ）が有名である。
YAMAGATA UNIVERSITY

Y

G

U

E

T

A A A A N V R I Y

M

T

I

S

YGUETAAAANVRIYMTIS
鍵は柵の深さすなわち3である。

次のようにしても簡単に文字の順序を入れ換えることができる。
［実例］転置式暗号

原文：「数学の期末試験には関数の最大最小値問題が出そうだね」を5文字ずつ改行して書いて
数学の期末
試験には関
数の最大最
小値問題が
出そうだね

1ビット（bit．Bi11aryDigit）＝0あるいは1のいずれか一方のこと．
バイト（1−γtぐ）：一まとまりのビットの札通常は8佃のビットを1単位とする。

∫α棚（上（gα：暗号の中の数学としてからこれを縦に読んで暗文：「数試数小出学験の値そのに最問う期は大題だ未開最がね」とすればよい。これを解くには再び5文字ずつ改行して書いて
数試数小出
学験の催そ
のに最問う
期は大題だ
未開最がね

を縦に読めば良い。

この暗号は使用される言語の特性を調べることにより解読できる（［18］p．59）。
［実例］換字式暗号（SubstitutiorlCipllCr）

原文に現れるビットや文字を他のビットや文字に書き換えたり，あるいはいくつかのビットや文字をまとめてブロックごとに他のビット列や文字列に書き換えて暗号化す
る方法を換字式暗号と呼ぶ。
たとえば文中のアルファベットを∬文字づつ前へずらして（Zまで来たら一回りしてAに戻る）書き換えていく換字式暗号があるが7鍵が打＝3のときはジュリアス
シーザー（JuliusCacsaI・100−44I3・C・）が使用したためシーザー暗号（CacsarcipllCr）と呼ばれる。
シーザー

暗号

〃＝3

0Ⅰノ Y M P I A D
R O B P S Iノ D G

上のシーザー暗号をもう少し発展させると次のような暗号が得られる。
［実例］換字式暗号

暗号化したい文章たとえば「秋になったら芋煮会をしましょうか」

AKININATTARAIMONIKAIWOSHIMASHOUKAに対してなにかある本から一節たとえば「古池やかわず飛び込む水の音」を引用して

AKININATTARAIMONIKAIWOSHIMASHOKA（原文）HURUIKEYAKAWAZUTDBIKOMUMIZUNOOTO（鍵）IF．…．．．……………‥．…．P（暗文）∫ 〃αdα：暗号の中の数学とするのである。ここでの鍵の役割は，アルファベットの表
A B C D E F G H I J K L M
1 2 3 4 5 6 7 8 910111213
N O P Q R S T U V W X Y Z
141516171819 20 2122 23 24 25 26に基づいて，Hが8だからAを1＋8＝9文字目のⅠにUが21だからKを
11＋21−26＝6文字目のFに……．0が15だからAを1＋15＝16文字目のPに書き換えることを表している。

［実例］換字式暗号

戦国時代の武将上杉謙信（1530−1578）は座標式暗号と呼ばれる次のような換字式暗号を使ったと言われる（［7］Ⅰ，p34）。

れ く ふ ゆ の き あ＼ゑ あ や ら よ ち い 同
ひ さ ま む た り ろ れも き け う れ ぬ は な
せ ゆ ふ ゐ そ る にす め こ の つ を ほ み
ん み え お ね わ へ へ
し て く な か と し
この表を使うと原文：「川中島に行かむ」は暗文「きしきへのしきしくしふれあくあつきしゆれ」となる。

これらの暗号も使用される言語の特性を調べることにより解読できる（［18］p鳶3）。
【実例］換字式暗号

コード（co（1c）はコードブックを鍵とする特別な換字式暗号である。例えばコンピュータ内部ではA，BrC，…は次のような数値として扱われている。
アスキーコード
ASCIIco（1し！

∫ 〃（JJ（l：暗号の中の数学（AIrlCrica11StaIldar〔1Co〔1eforIIlfbI・111atiollIntel・CharlgC）

A B C …‥ Ⅹ Y Z
65 66 67 …‥ 88 89 90
I

A M

A

B O Y

7332 65 77 32 65 3266 79 89 46［実例］点暗号

これまでの例とはまったく異なるが，文字のそばに針等で小さな印を付けその印をたどると通信文がでてくるという，点暗号と呼ばれるものもある。たとえば「お父さんお母さん，おげんきですか？市内はも−毎日むし暑くて困ります。
部活が終わるお盆にはネちらへ帰ります。ふるさとがなつかしいです。」とすれば「ゲームソフト」を催促していることになる。

1．1 近代暗号第二次世界大戦以前と以後の1970年代半ばまでの暗号は，近代暗号と呼ばれていて．
以下のような特徴を持っている。
1．暗号の作り方も鍵も秘密にする。

2．暗号の安全性を言語の統計的特徴を基に議論する。
3．暗号を便用するのが主に軍事と外交である。

前節で紹介した転置式暗号，換字式暗号やコードを複雑に組み合わせた暗号を使用していたが，どの様な場合も作り方と鍵の秘密を守ることが最も重要な課題であった。
（［7］，Ⅰ）に基づいて2，3の例をあげてみよう。

［実例］日露戦争日本海海戦で哨戒艦信濃は「夕」という1文字で「敵艦見ゆ」と伝えることになっていたし，太平洋戦争開戦時の「新高L上」登れ」は「真珠湾を攻撃せよ」であった。

［実例］1942年頃の陸軍の第一戦部隊では00t）0．001アイ．002極九003河（川），004上等兵．005アテ，006命令…………‥064
通信所，…
といった1000語ほどの表に基づいて文章を数値に変換し．それをさらに暗号化していた。

∫（川ノ（上（んl：暗号の中の数学［実例］一方外交用コードとしては先ほどの上杉謙信が使用したのと同じ種類の座標式
暗号が使われていたが．次の1931年頃の外務省の暗号はアメリカに解読されていた。

fb

ノ CW

gc gtllly iflIl

ak 相成 l勺話 的確
aV
lJ之l

（：〔†

これらの暗号にはすべて一般的な解読方法が見つかっている。情報理論の一般論から暗号は鍵が長いほど安全であり，その一方暗文が長いほど元の正しい原文を一つに限定できる可能性の高いことが知られている。しかしバーナム暗弓 （Vd・11alllCipll−−1・）と呼ばれる乱数式検字暗号は唯一熊条件に安全な暗号である。
［実例］バーナム暗号（Gilt）（−1・tⅥモ1・Ilalll，1917）この晴引ま1回限りの傾い捨て鍵（011（）
tiIll（二pヱL（1s）を使用するのが特徴である。たとえば原文が11Cllol であるとき，1回限りの使い捨て鍵Kとして完全にランダムで長さが原文と同じ文字列たとえば iwpbll ，をとりシーザー暗号と同じような方法を使ってJ′・〃り ・−・ ｛J…ノ壱′り′〆てlただし／′ ■・リt（11から9番「lの文字）と昭文 ，qbl叫j に変検する。鍵 iwI）l川 がわかっていれば原文、つll（封0 は昭文−つ（1l）t）11．j より直ちに得ることができるが7この鍵についての情報がなければどんな5文字の文字列も鍵となる可能性があるのでT以下のようなことも起こってしまい，決して正しく翻訳されることはない。
／・‥い ・・ ｛J…ト（川J〃ん（ヱ∫（川ノ ん：暗号の中の数学

1．2 現代暗号
さて1970年代後半から現在までの暗号は，現代暗号と呼ばれているが．以■Fのような特徴を持っている。
1．暗号の作り方は公開され鍵のみを秘密にする。
2．暗号の安全性は計算量理論を基に議論する。

3．暗号を使用するのが軍事と外交だけではなく，→般社会において民間で使われる。
4．公開鍵暗号（I）ublic−kcysystcIll）が使用される。

この現代暗号を代表するものにデータ暗号化規格（DES）2 やRSA暗号がある。
DES暗号（DataEIICryptiorlStaIldarLl）は転置式と換字式を組み合わせた混合式暗号と呼ばれるもので，その基本的な考え方は1940年代の終わり頃シャノン（Cllatltlしモ
Sll〜tIlllOll）によって提案され，その後1970年代にIBMによって開発された。標準

暗号，データ暗号規格として1977年米国商務省標準局によって米国連邦政府機関の標準として公開されたものである。さらにこのDES暗号は標準化の為に．そのアルゴリズムが完全に公開されると言う当時としては画期的なものであった。これは暗号の安全性をアルゴリズムの秘匿性よりも鍵の秘匿性におくという考えに基づいている。アルゴリズムの公開については今も問題点が多く指摘されているものの，この考え方は暗号の商用化を促進するうえで，重要な役割を果たした。
一方RSA暗号というのはいくつかある公開鍵暗号を代表する暗号である。では公開鍵暗号とは何だろう。

定義1．1次の5つの集合ルt（1八∴と．pの組を暗号系（cl・yptOSyStClIl）とよび5で表す。すなわち
5＝（ノu，C，疋，ど，p），（i）平文（Ⅰ〕1aillt（−Ⅹt）の集合．ノu．

（ii）昭文（cipIICrt（−Ⅹt）の集合．c．
（iii）鍵（kcy）の集合，疋．
（iv）組立関数（し†11CiI〕11（！1・illgtl・之tllSfbl・11川tioll）の集合．ど＝（且〟l∬∈疋卜
ガム「：ノリ ー→ C．ただし ∬∈疋（Ⅴ）翻訳関数（し1ccipllし−1・illgtl・allドfbl・111山ioll）の集合p＝岬〟l打∈疋ト

βム・：C −→ 力㌧ ただし ∬∈疋
2この唱号についてはすでに鍵の大きさを現在の計算機の能力が越えているので次世代の規格が検討されている。

∫ 〃α血：暗号の中の数学である。ただしノuとCは長さ有限な記号列よりなる有限集合で互いに等しい数の元を含む。ノM＝Cと仮定することが多い。丘 〟（〟∈忙）は〟からCへの仝単軌

すなわち1対1上への写像で，且∬の連写像は刀五である。

平文
この 現代の 暗号系には

1．どの鍵に対しても組立関数，翻訳関数ともに効率的に計算できる。
2．使用方法が易しい。

3．暗号系の安全性が鍵を秘匿することのみによっていて，組立関数や翻訳関数の計算法を秘匿することにはよらない。
ことと言った3つの一般的要件が求められている。さらに以下のような守秘性（sccI・（−Cy）
や正当性（と1tltllⅧticity）に関する要請もある。
守秘性に関しては：

1．暗号の解読を試みようとして，たとえ暗文やさらに暗文とそれに対応する平文の組を手にいれても，それから翻訳関数β五を体系的に決定することが暗号解読者（cI・yPtan之11yst）には計算的に実行不可能であること。

2．入手した昭文Cから対応する平文〃を体系的に決定することが暗号解読者には計算的に実行不可能であること。
守秒性の確保には翻訳関数を秘匿すれば良いことになる。
〃

盗掛ヲ／

秘匿
正当性に関しては：

1．暗号解読者が，たとえ昭文やさらに暗文とそれに対応する平文の組を手にいれても．それから組立関数且五を体系的に決定することが計算的に実行不可能であること。

∫αて〟α血：暗号の中の数学

2．翻訳したときに，その暗号系において，正当な平文〃′となる暗文C′を体系的に見つけることが暗号解読者には計算的に実行不可能であること。
であり．この正当性の確保には組立関数を秘匿すれば良いことになる。

秘匿暗号系（〟，C，疋，ど，p）を使って相互に通信するとき，すでに述べたように古代から20世紀半ば頃までは，組立関数且〟，翻訳関数刀五ともに秘匿するのが常識であった。暗号通信が少数の当事者間で交わされる特殊なものであった場合はこれでも良いのだが，簡単な計算からわかるようにこのような暗号系ではノ化人の間の交信に
γ小一1）
γ〜C2＝

個以上の鍵が必要となってしまう。これではたった1000人の当事者間の通信にも鍵は499500個以上必要となる。
しかしW．DifficとM．Hellmallは公開鍵暗号系と呼ばれる新暗号孔NcwDirectiollS
i11Cryptograplly・IEEE7Tans・UnIrLfo・T7＝㍑ ・y仇J・IT−22（6）（Nuv．1D76）644−654を提唱し，r上人の間の暗号通信が2・r↓ 個の鍵でできることを示した。この公開鍵暗号系の実現にとってなくてはならないのがいわゆる一方向関数（011C−WayfllllCtioIl）と呼ばれる関数である。

定義1．2集合Aからβへの1対1上への写像ノーが擬一方向関数（ps（−tltloollC−W之1yf−tlllCtioIl）であるとはAの元∬∈Aが与えられたときにはノー（㍑）∈βは容易に計算できても，逆にノや）からはを求める計算が容易ではないことを言う。すなわち．／ （㍊）の計算法で多項式時間内のものがあっても．／ ￣1（㍑）の計算法で多項式時間内におさまるものは知られていないような関数のことである。
擬一方向関数は擬を省略して単に一方向関数と呼ばれることが多い。
注意1．3（i）現在 ㍑∈Aが与えられたときにノ●（∬）の計算は多項式時間内にできてもタブ￣1（ェ）の計算が多項式時間内にできない ことが数学的に証明されているような関数は見つかっていない。

∫ 〃（上d（上：暗号の中の数学

こういった 真に数学的な一方向関数は存在するであろう というのがP≠NP予想である。この問題について深く知りたい読者は［2］等を参照してほしい。
（ii）擬一方向関数は経験上よく知られている。解くのは難しいが，与えられた答が正しいかどうかは比較的簡単に確かめられる，といったことはしばしば経験することである。たとえば与えられた自然数を素因数分解することは，得られた素因数分解が正しいかどうか検算することよりも難しいことは誰もが経験したことであろう。

（iii）日常生活でも「覆水盆に帰らず」「落花枝に帰らず破鏡再び照らさず」といった故事に擬一方向関数の考え方を見つけることができる。

定義1．4（公開鍵暗号系）ル1＝Cなる暗号系（ルイ，C，疋，ど，か）において．鍵の空
間疋がユーザ達の集合A，月，C，…‥，すなわちに＝（A，刀，C，…‥）

であって，各ユーザAが一方向関数から作られた組立関数且A及び翻訳関数βAの組を所有し且Aは公開登録しβAは他に公開せず秘匿して，しかも公開された組立関数からその翻訳関数を体系的に決定することが計算的に実行不可能で，Aからおくられた暗文はAの翻訳関数でしか容易には翻訳できないとき，このような暗号系を公開鍵暗号系という。

公開鍵暗号系では且Aから刀Aを得ることは容易ではないと仮定しているので．この2つを区別して，EJ4を公開鍵（publick（，y），DAを秘密鍵（pI・ivatck（！y）と呼ぶ。
公開鍵暗号系に対して組立関数（公開鍵）且Aと翻訳関数（秘密鍵）月Aが本質的に同じで，すなわち一方から他方が容易に得られて，その安全性を鍵の秘匿性に大きく依存している，従来から使われてきた暗号系を慣用暗号系（（二OrlVClltiorlalcryptosystclrl）
あるいは対称暗号系（sylnHl（血iccI・yptosystcIrl）という。公開鍵暗号系では守秘性と正当性を以下のように実硯する。
守秘性を保つには：

ユーザAはユーザβに平文〟∈ノuを送るときβの公開鍵且βを使って暗文
C＝且β（〟）を刀に送れば良い。βはこの暗文を自分自身の秘密鍵かβを使って解くことになるが．それができるのほ月のみなので守秒性は保たれることになる。
ββ（C）＝ββ（月月（〟））＝几す公開秘匿∫ 〃（上d（上：暗号の中の数学

どのユーザもβの公開鍵を知っていて昭文Cのかわりに別の平文凡才′から作られた昭文C′＝且月（〃′）をβに送ることができるので上の方法では暗文Cの発信者は確かにAであるという正当性は主張できない。
正当性を主張するには：

Aは自分自身の秘密鍵βAを使って暗文C＝ガム（〃）をβに送れば良い。βはAの公開鍵且Aをイ吏って〟を求めるわけであるが．且．4で復号できる昭文を作れるのはAしかいないので，Aは自分が正当な発信者であると主張できる。
且A（C）＝旦4（かA（几弟）＝ルr

秘匿

公開

どのユーザもAの公開鍵旦4を知っていて平文〃＝且A（C）を知ることができる
ので上の方法で秘密を守ることはできない。

公開鍵暗号系において守秘性と正当性を同時に実現するには発信者A受信者βのそれぞれが「重の変換をしなければならない。Aが平文几すをβに送りたいときはて

まず〃をA自身の秘密鍵βAで変換し次にその結果をβの公開鍵且βで暗号化しC＝且月（刀．4（凡才））をβに送る。βは初めに自分の秘密鍵β夙次にAの公開鍵且Aを使ってルタを求める。．4の公開鍵を使うことにより正当性が確かめられる。
且A岬月（C））＝旦4（ββ岬β（か．4（凡才））））＝旦4（刀β（几す））＝凡才A「 ≡≡：ニ≡−「「β
［

秘匿

公開

秘匿

公開

公開鍵暗号系と良く似た者えかたを日常の書留郵便や電子メールのなかに見いだすことができる（［10］）。

∫ 〃（l血：暗号の中の数学［実例］Aからβに書留郵便を送るとする。Aは手跡こ署名（捺印）し郵便局で登録した後，それをβに送ればよい。この場合Aの署名がAの秘密鍵サ右月の住所がβの公開鍵且月に対応する。

A「 ≡芸：芸√「
署名

登録

合法的受取人［実例］Aからβに電子メールを送るとする。ノ4は手元の計算機システムに自分のパスワードでログインし，βにメールを送る。この場合AのパスワードがAの秘密鍵

刀A，メールリストに公表されたβの住所が刀の公開鍵且βに対応する。ただし，これは公開鍵暗号の考えかたを説明するための例であり実際の電子メールシステムは

安全とはいえない。

A「 ≡芸：ニ≡÷￣「

βAのパスワードβの住所 βのパスワード Aの住所

以l二が公開鍵暗号系の概念であるが，W．Difhし！とM．Hc11111；ulがこの暗号系を発表したとき，それを非常に高く評価したのがG．］．SilIllllOllS（S〜ul（liaNatiollalLatJOl・atol・i（一S）
だと言われている（W．Dif恥TllL−Natioll礼1Scc111・ityEstal）lisllIllClltall（1tll（一D（、Ⅴ（，1olナ

1IIL，ntOfPublic−KcyCl・yptOgl・aplly・D（さSiylLS，CodcsaJL／（lCryptL・yraPhy．7「1996）0−12
参照のこと）。彼が公開鍵暗号系を評価したのはそれが核兵器の管理と深く関わってくるからであった。すなわち現地司令官が大統領から重大な命令を受けた場合に．確かにその命令が大統領からのものであると確認できる．通信手段がどうしても必要になるからである。

∫α棚αdα：暗号の中の数学

このように一方向関数の存在が証明できないにも関わらず，応用上公開鍵暗号系はきわめて重要である。正当性を証明する問題は通信だけではなくコンピュータシステ
ムを不正な進入者から守る為にも研究されているが，現在よく話題になる電子マネーも公開鍵暗号の応用である。
ではこの公開鍵暗号系という 都合のよい話 ，を実現するにはどうしたらよいのだろうか？

2 NP問題について
この節では［2］に基づいて計算機科学の基礎理論から，一方向関数の存在証明に密接に関連するNP問題，すなわち非決定性計算モデルにより多項式ステップで解くことのできる問題について概説する。NP問題を知ることは現代暗号を理解する上で大切である。計算モデルと呼ばれる仮想コンピュータを定義し計算できるとは何かについて考えよう。

2．1 計算モデル
定義2．1記憶領域を無限に使えるコンピュータを考え，計算モデルと呼ぶ。小数は浮動小数点表示によって自然数に関する演算でできるので、この計算モデルでの演算は

■・t

・l

■
l

︵

■・t

︶ ■l
●l
●l

′−−−1

●l

︶

自然数のみに限り，以下の条件を仮定する。
→走の長さのビット数ごとの記憶領域とのアクセスが1ステップでできる。
四則演算，シフト，判断などの基本命令も1ステップでできる。
■lで定められた長さを越えるビット数の演算は1ステップではできない。

この計算モデルで，定まったビット数を越えるデータを扱う場合は，複数の定まったビット数を使用する多倍長形式と呼ばれるものを用いる。この場合四則演算等は1ス
テップではできず，データの長さに応じたステップ数（計算時間）がかかるとする。計算量をはかる場合は計算時間の定数倍は無視する。
計算モデル上のプログラミング言語∠を以下のように定める。

定義2・2L：は（代人丈while文．if文，入力丸yes丸no文）で構成される。変数や定数は計算モデルによって定められたビット数で表硯され，配列変数も使用できる。Ⅹ，y，Zを変数、aを走乳s，Sl，S2を1個以上の実行文の列，r（c）を条件式cの判定に要するステップ数．r（s）をsの実行に要するステップ数とする。それぞれの実行文は以下の形式．意味，ステップ数を持つ。

∫α仙αJα：暗号の中の数学

代入文
ステップ数

形式

意味

Ⅹ＝a

定数aの値をⅩに代人する 0（1）ステッフ

Ⅹ＝y＋z

yとzの四則演算等の値を 0（1）ステップ

Ⅹ＝y￣Z

Ⅹに代人する

Ⅹ＝y＊z

Ⅹ＝ydivz
Ⅹ＝ymOdz

while文，if文
ステップ数

形式

意味

while c do s end

条件式cが真の間 γイア（c）＋ア（β））

sを繰り返し実行 ステップ，ただしする

条件式cが真なら cが真なら

if c then sl

else s2 endif slを，
if c then slendif

偽ならs2を実行
する

形式

γ・は繰り返しの回数
r（c）＋ア（ぷ1），

偽ならr（c）＋r（㌶）
ステップ

ステップ数

意味

竺utX 1個のデータを変数Ⅹに読み込む 1ステッフ
yes丸no文
形式 意味

ステップ数

yeS 人力に対しyesと答えて停止する 1ステップ
nO 入力に対しnoと答えて停止する 1ステップ
注意2．3上の表中の記号0（1）は計算に要するステップ数が1の定数倍であることを意味する。入力データに多倍長形式も含めるのでこのように書く。
代入文中の演算の順序は括弧により指定できる。括弧の内部等特に指定されていない場合は＊，div，mOdを＋，一に優先させる。文には空文も許し，実行文の列sを使った手続き文：

procedure手続き名；S endprocedure
も書けることとする。

∫ 〃α（ん：暗号の中の数学

定義2．4Ⅹを変乱yを変数または定数とする。このときⅩ＝＝y，Ⅹ！＝y，Ⅹ＞y，Ⅹ＞＝y．
x＜y，Ⅹく＝yを基本条件式といいフこれらの基本条件式を弧d，Or，nOtの演算子で結合したものを条件式と呼ぶ。基本条件式cの判定に要するステップ数r（c）は1とし，条件式cl，C2に対してはT（cland c2）＝ T（cl）＋T（c2）

T（clor c2）＝ T（cl）＋T（c2）
T（not cl）＝ T（cl）＋1であるとする。

2．2 問題とアルゴリズム
定義2．5問題とはある関数が与えられた人力に対してyesあるいはnoと出力するかどうかを決定することをいい，その出力を計算する方法をアルゴリズムという。また
入力する記号列の長さを人力のサイズと呼ぶ。
定義2．6ある問題に村してそれを解くアルゴリズムが存在するときフその間題を計算可能（coIrlptltablc）または決定可能（（1ccitlablc）といい，アルゴリズムが存在しないとき計算不能（urlCOInP11table）または決定不能（urldccidablc）という。
［実例］ナップザック問題（KllapS之ICkpI・OblclIl）
人力：自然数の列（g，〃1，〟2，…，叫′）決定すること：0，1を要素とする列（ん1，む2，．．．，h）で∫＝ん1〃1＋む2几先＋‥・＋ん′‖叫↓となるものが存在するか。

［解答例］入力のサイズr↓が小さければ容易に解ける。

r息＝1：∫＝0またはg＝〟1ならばyesっ∫≠0かつ5≠〟1ならばno．
γ↓＝2：∫∈（U，〃1，爪先，〃1＋〃2）ならばyesっ∫≠†0，〟1，几わ，〟1＋爪先）ならばno．

入力（21，9，7，23，2，3）に対しては21＝9＋7＋2＋3が見つかるからyes，一方入力†22†9，7，23．2，3〉に村しては式

22 ＝ ん19＋〜ノ27＋ん323＋ん42＋む53を変形して22−〜ノ42 ＝ む19＋む27＋む323＋ん53

∫（上Ⅷ（エ血：暗号の中の数学とすれば左辺は22≧22−わ42≧20で右辺は23以上か19以下だからnoとなる。
ナップザック問題ほ効率が悪くてもそれを解くアルゴリズムを考えられるので計算吋能であるといえる。

計算不能な問題の例としてつぎのようなものがある。詳しくは［2］等を参照してほしい。
［実例］プログラム停止問題（ProgralnlIICtCrminalityprobleIrl）
入力：プログラムPと人力データェ
決定すること：入力諾に対してP（諾）は停止するか，ただしP（㍑）はデータ諾がプログラムPに人力された状態を示す。

2．3 多項式時間と指数時間
定義2．7人力のサイズγとに対してある定数んが存在して0（γ↓た）3ステップ以下で解く
アルゴリズムが存在する問題のクラスを決定性多項式時間（dctcrlnirlisticpolyrlOIIlial

til−1C）あるいは単に多項式時間といいPで表す。またある定数んが存在して0（2㌦）
ステップ以下で解くアルゴリズムが存在する問題のクラスを指数時間（cxpoIIC11tial
tiIllC）といいEXPTIMEで表す。
定義よりP⊂EXPTIMEであるがP≠EXPTIME
であることが知られている。
［実例］「ナップザック問題

人力‥自然数の列（∫，咄，A毎，…†叫，1
決定すること：0，1を要素とする列†ん1，む2，…，h）で∫＝ん1凡才1＋ん2几毎＋・‥＋んr′几弟〜となるものが存在するか。」は2γ〜通り考えられる列†ん1，ん2，…，ん‖）のすべてについてのSの値を調べて解くことができるからEXPTIMEに属することになる。

定義2．8 自然数γJ′のビット数をγ↓の人力のサイズと呼びsiz（−γJ′と書く。
3れ一たの正志数倍以下におさまるステップ数を0（㌦）と書く。

∫ 〃αdα：暗号の中の数学

補題2．9 自然数γ1に対してそのサイズはsi∠Cr↓＝1＋［log2γ↓］

で与えられる。ただし［］はガウス記号と呼ばれ小数謹0．諾1∬2‥．（≧0）の整数部分を表す．すなわち［ェ0・∬1㍑2‥・］＝諾0である。
［証明］いまγ1＝（エf2f−1＋叫し12オー2＋…＋（122＋叫となっていたとする。ただし叫＝0または1で化t≠0とする。
2f−1＜rl＜2f−1＜2fだからモー1≦log2m＜≠となりsizcr〜′＝1＋［log2γ↓］であることがわかる。
［証明終］

自然対数を111とすれば
si∠Clけ＝1＋［log2γ↓］＝1＋

であり小数∬に村して［㌶］≦㍑＜［㍑］＋1が成り立つから，自然数れの入力サイズ
si∠C〃′は0（1Ⅰ川′）であると考えてよいことになる。2進数の加軋乗払除法はそれ
ぞれ
11001＋ 1111101000
11001
1101

×

11001
11001
11001
101000101

∫α棚α血：暗号の中の数学

1101

111）1011101−111000
100101−111001001−11110のようにするから

命題2．10 自然数†rl，†↓の加法に要するステップ数は0（IllaX（1Ⅰ川り11可）乗法に要するステップ数は0（1nγnlIl可除法に要するステップ数はm≧mと仮定してrr↓をγ↓で割った商をヴとすれば0（111−rr11Ⅰ川）となる。
それでは実例によってステップ数を計算してみよう。はじめに変換器と呼ばれる計算モデルを定義しておく。
定義2．11（変換機）決定性計算モデルとその上のプログラミング言語∠′を組にしたものを変換機と呼ぶ。ただし￡′は（代人丸while文，if丈入力文，出力文，halt
文）で情成され出力文．halt文以外の実行文の形式，意味，ステップ数は定義2．2と同じものとする。
出力文，halt文
形式

意味

ステップ数

Output X 変数または定数Ⅹの価を出力 1ステツフ
halt

計算を停止する

1ステップ［実例］ユークリッドの互除法（EtlCli（1（湖1之11gol・itllIll）

ユークリッドの互除法とは，2つの自然数（↓†むの最大公約数（ ，ん）を求める計算法であり．次の2つの補題より導かれた。

∫ 〃（1血暗号の中の数学

補題2．12（エ，むを整数とする。ん＞0かつむい↓ならば（む，（り＝ん・補題2．13町むを整数とする。ん＞0かつある整数ヴ，Cがあって（↓＝甘ん＋c ならば（ ，ん）＝（む，C）．

どんな初等整数論の教科書にも書いてあるが復習すれば以下のようになる。
〟，むを自然数とし，化≧んと仮定する。
〟＝γ・0，む＝γ・1

とおき をむで割った軌余りをそれぞれ鮎γ一2とする。
化＝γ・0＝恥†・1＋γ・2 0≦ノ／・2＜γ・1γ・2≠0の場合にはγ・1をγ・2で割り商をり1余りをγ3とする。
γ・1＝り1γ・2＋γ・3 0≦γ・3＜γ・2γ・3≠0の場合にはγ・2をr・3で割り商をリ2余りをγ・4とする。
†・2＝ヴ2γ3＋γ・4 0≦r・4＜γ・3†・4≠0の場合にはさらに同じような計算を行う。この結果は
γ・1＞一′・2＞・・・＞γ・ん＞‥（＊）（＊）の数列のうち正の数であるものを元とする集合∫を考えれば，∫の元はすべて自然数であるから，∫には最小数がある。それをγ・ん。とすれば
γ一た0−1＝恥0−1γ・ん0＋γ・た0＋1†γ・んD＋1＝0となっている。もし0くγ・ゎ＋1くγ・ん。とすれば，γ・た。が∫の最小数であることに矛盾する。
ところで′′・ん。＝（ ，りとなっている。なぜならば補題2．13より（〟，ん）＝（r加r・1）＝（γ1，γ一2）＝（†・2，γ・3）…
＝（γ・ゎー1，γ・ん。）・∫ 〃α（ん：暗号の中の数学

一方γ・ん。−1＝恥。−1γ・ん。だから補題2・12より（γ・ふ。−1ゥγ・ん。）＝γ・ん。となり（什，ん）＝γ・た。を得る。このアルゴリズムを流れ図にすれば次のようになる。

さらに変換機（定義2．11）でのプログラムは

PrOCedure GCD；
1：a＝0

2：b＝0
3：r＝0

4：1nput x
5： a＝Ⅹ

6：inp11t y
7： b＝y8：r＝ⅩmOd y
9：While r！＝O dolO： a＝bll：

b＝rgα棚α（k暗号の中の数学

12：

r＝a mOd b

13：end

14：Ontput b
15：halt

endproceudreとなる。最大公約数γ・ん。を見つけるまでにん0回割算を実行していて各割算のステッ
プ数の合計は0（1Ⅰ用ぃ11恥＋1Ⅰ川1＋‥・＋1Il鮎。｝1））以下だから

1Il恥＋1明1＋…＋111鮎。−1＝1Iln恥≦11川よりユークリッド互除法のステップ数は0（111化hl り以下であり効率の良いことがわかる。人力のサイズ11川に対してステップ数が0（1112（りとなったのだからこのアルゴリズムはPに属することになる。

［実例］素因数分解のアルゴリズム

自然数γ↓を素因数分解する以下のようなアルゴリズムを考察しよう。

自然数†1≠0の最小の真の約数は素数であるから，れ′が合成数ならば，γJ′を2および′トさい順に奇数（gで割っていくと，やがて最小の真の約数にたどりつく。
γJ一＝句 1＜（g≦ヴ＜γんとすれば㌦≦句＝γ〜′となっているから最小の真の約数を見つけるには（g≦、布まで調べればよい。
J≦ノ元まで調べたかどうか判定するにはr↓を Jで順に
rl＝扉＋γ・，0≦γ・＜（g．ヴ≦（Jとなるまで割っていけば（（g＋1）2＝ J2＋2 g＋1＞ヴ g＋γ・＝rlすなわち 〟＋1＞、㍍であるから g≦、布まで調べたことがわかる。
さらにこのとき一け＝リ（g＋γ・，1＜r・＜（J．ヴ≦（J∫ 〃αdα：暗号の中の数学

であれば，r〜′は、布以下の数で割れていないので素数と判定してよい。この計算では入力した数γ↓を順に2，3，5，7，…，［ノ可と割っていくのだから各割算のステップ数を合計すると0（1Ilr坤1q2＋111炬＋・・・＋1Il叫、句））となる，ただしヴ J（ g＝2，3，…，［、声］）はr〜′を（Jで割ったときの商である。ところで

1明2＋1明3＋…＋1町仇句＜mhlγ↓であるから，ステップ数の上界の一つは0（吊I12可となる。γ↓＝ClI川であるからこのアルゴリズムの上界が指数時間でとらえられたことになる4。変換機（定義2．11）でのプログラムはPrOCedure Factoriztion；
1：1nput n
2：if n＜2 then halt endif
3：d＝2
4：Vhile d＊d＜＝n do

5： if n mod d＝＝O then6：

Output d

7：n＝n div d8：else d＝d＋1

9： endiflO：endll：Outpnt n
12：halt

endprocedureとなる。

一般に指数時間かかるアルゴリズムは効率が悪くて実際には計算が不可能といえるほど時間がかかるといえる。

2．4 非決定性計算モデル
定義2．1で定義された計算モデル上のプログラミング言語では文れかを選択して，その結果としてyes文を最も速く実行するというような計算はでき
4素因数分解の解法は着実に進歩していて現在は準指数時間でとらえられている。

slとs2のいず∫ 川dα：暗号の中の数学ない。Slとs2をともに実行して初めてyes文が実行できることになる。このような決定性の計算モデル（通常のコンピュータ）に対し非決定性計算モデルを以下のように定義する。
定義2．14（非決定性計算モデル）文slとs2のいずれか一方を選択して，その結果としてyes文を最も速く実行するようにeither slor s2文を使用する計算モデル

を非決定性計算モデルと呼ぶ。ただしslは1個以上の文の列，S2は0個以上の文の列である。

一般にeitber slor s2文を1回実行するにはslまたはs2を実行する2通りの場合があるから，ん回では2ん通りの実行の仕方があることになる。非決定性計算モデルの特徴はこれらの実行の場合の選択をyes文を最も速く実行するよう都合良く選択すると言う点にある。このようにslまたほs2を非決定的に推測して実行した場
合のeither slor s2文の実行に要するステップ数はそれぞれslまたはs2を選択した場合に応じて
r（誼）＋1またはr（㌶）＋1
ステップとなる。非決定性計算モデル上でナップザック問題を解こう。
［実例］非決定性計算モデル上でのナップザック問題‥
人力：自然数の列（∫，〟1，叫z，…，九九）
決定すること‥0，1を要素とする列（〜畑ん2，…，んバで∫＝〜り〃1＋ん2城＋‥・＋む‖几れjとなるものが存在するか，は計算可能か。

［解答例］either or文を使って以下のようなprocedureを考える。

PrOCed11re Knapsack；1：Snm＝0

2：1nput S
3：WIlile 人力データ存在do

4： inputIq
5： either sum＝Su皿＋H or
6： end7‥if S＝＝Sumthen yes else no

endproced11re∫ 〃αdα：暗号の中の数学（g7〃ト〟2，…，丸久l）＝†21，9，7，23，2，3）が人力されたとしよう。2行目でS＝21とな
り3行目から6行目では順にsu皿＝SIUⅥ＋9，Sum＝stun＋7，空文，Sum＝Sum十2，Su皿＝sum＋3と人力データ存在が存在しなくなるまでsumの計算が繰り返され7行目に来て21＝9十7十0十2十3を判定してyesを出力する。つまりこの非決定性計算モデルでは
either or文を使ってれ＋1個のデータのナップザック問題を0（γl）ステップで解いたことになる。

分割問題と呼ばれる問題も人力のサイズが〃′ならば非決定性計算モデル上で0（ノrりステップで解ける。
［実例］非決定性計算モデル上で分割問題‥

入力‥自然数の列（〃1，Aわ，・．・，〃γ上）決定すること‥部分集合A⊂（1，2，…，γりが存在して

∑叫＝∑叫
f∈A

メ≠A

となるものが存在するか．は計算可能か。

［解答例］either or文を使って以l：のようなprocedureを考える。
PrOCedure Partition；
1：Suml＝0
2：Sl皿2＝0

3：Wllile 人力データ存在do
4： inp11t M
5： either su皿1＝Suml＋M or snm2＝Sum2＋M
6： end7：if suml＝＝Sum2then yes else no
endprocedure（〟1，A杢7．．．，几釆′‡＝（1，3，7，11，13714っ15）が人力されたとしよう。1行軋2行目
でsunl，S皿∬2に初期値0が与えられ3行目から 6行目では順にsu山＝SⅦnl＋1，
slm2＝Sum2＋3，Suml＝Suml＋7，Su皿1＝Sunl＋11，Su皿1＋13，S心m2＋147S心m2＋15 と入力
データ存在が存在しなくなるまでsu皿1あるいはsum2を非決定的に推測して実行し7行目に来てstunl＝1＋7＋11十13＝sum2＝3・14・15を判定してyesを出力する。すなわち
この非決定性計算モデルでほeither or文を使ってγ↓個のデータの分割問題を0（γりステップで解くことになる。

∫α棚αdα：暗号の中の数学

定義2．15（非決定性多項式時間）非決定性計算モデルによって多項式ステップで解くことのできる問題のクラスを非決定性多項式時間（110IldeterIIliIlisticpolyllOIrlialtiI上1C）とよびNPで表す。
つまり（i）与えられた解が正しいかどうかは多項式時間で計算できても（ii）解の候補数が指数関数的に増加するので，1つ1つの解の候補をチェックするというプログラムでは解くことができない。
というような問題と思えばよい（［16］）。この定義より決定性計算モデルによって多項式ステップで解ける問題のクラスPは当然NPに属することになる。
P⊂NP

しかしP＝NPかP≠NPであるかは重要な未解決問題である。
ところで非決定性計算モデルでの計算を決定性計算モデルに移行して行なう場合
either slor s2文を決定性計算モデルではsl，S2の両方を計算してからyes，nOを出力するから，もとの非決定性計算モデルのプログラムのステップ数まにeither orがγ↓回使用されていれば決定性計算モデルでのステップ数は2γ∫＋（トγりとなり

NP⊂EXPTIME
であることがわかる。

3 RSA暗号とEIGamal暗号
公開鍵暗号の考え方が提唱されて以来具体的な暗号系が数多く考案されてきた。しかしそれらの大部分は安全かつ実用的であるとはされていない（［22］）。さまざまな問
題点が指摘されているものの，現在広く使用されているRSA暗号とEIGaIrlal暗号の原理について解説する。これらの暗号はその安全性の根拠を素因数分解や離散対数問
題といったNP問題においている（［20］）。

3．1 合同式（Congruenceexpression）
定義3．1整数化とゎに対して化−んが自然数川．で割り切れるとき，（lとんはγr↓を法として合同であると言い，〃≡む（TIlOdrrり∫ uαdα：日音号の中の数学と書く。つまり（↓≡〜ノ（1flOdγrり ⇔ γ付いい−ん．

合同でないときは， ↓≠ん（1IlO（1γr↓）と書く．
命題3．2整数（l，ん，C，（g自然数一rrと（≠0）に対して以下のことが成り立つ．
（i）（l＝ 上（ⅠIlOd肌）・（ii）化≡む⇒ん≡（l（1IlO（lγrり．
（iii）（l≡ん，ム≡c⇒（l≡c（ⅠIlOdγrり・（iv） ≡ん，C≡（g（1IlO（1γrり⇒
上＋c ≡ ん＋（J（ⅠIlO（1川′）（l−C ≡ む−（J（1IlO（1川′）αC ≡ む（g（ⅠIlO（1γJ↓）．
（Ⅴ）もし（上C≡んc（1IlO（1m）かつ（c，m）＝1ならば化≡む（1IlO（1〝り．
定理3．3（フェルマーの小定理）（Pi（汀1・C（1cFcl・1Ilat160ト1665）

pを素数化を整数とするとき（i） γ≡ （lIlO（1p）・（ii）（フェルマーの小定理）p／付ならば化p￣1≡1（1IlO（1p）．
となる。

［証明］（i）pを素数とする。二項係数p（p−1）・‥（p−f＋1）J（1−1・2・‥J（1≦よ≦f′）は，ノ＜pのとき分母は∫Jで割れないのでf′」pCノ（立＝1，2，…・ダー1）となる。ただしpCo＝1丹q＝1。
化に関する帰納法で証明する。化＝2の場合は，2p ＝（1＋1）γ＝∫ノCo＋〃Cl＋…＋ブノq−1＋〃qノ≡（1＋1）（1110dp）≡ 2（1110〔りノ）∫ 〟（上dα：暗号の中の数学となる。一般に（化−1）p≡ −1（＝10（1p）と仮定すれば，（ユダ（（㍑−1）＋1〉p（α−−1）p＋〃Cl（化−1）γ￣1＋γC2（ −1）p−2＋…＋pq−1（ −1）＋1（（l−1）＋1（rllO←1fノ）〃（1rlO（lp）となっている。

（ii）pJ（エかつpl化（ エp￣1−1）であるからpl〃p1−1．故に（エp￣1≡1（1IlOdp）．
（証明終）系3．4（フェルマーテスト）γ↓＞2なる自然数があって・r↓が素数か否かわからない

とき，γ1の倍数でない化を用いて
γ上1≠1（ⅠIlOtlγりとなればγJ．は合成数である。

［証明］γ↓が合成数でない，すなわち素数であると仮定すると，γ↓J であるからフェルマーの小定理より㌦￣1≡1（1110（l可となってしまう。

（証明終）

参考までにフェルマーの大志理とは：「脊索数pを固定したとき：rγ＋〃γ＝Zpとなる自然数諾，〃，Z＞0は存在しない。」であった。

3．2 オイラーの定理（Lcollllar（lEtllu・1707−17幻）定義3．5 自然数γ↓に対して1，2，3，…つγ↓の中でr↓と互いに素な数の個数をァ（可で表す。p（可はオイラー関数と呼ばれている。

∫ 〃rldα：暗号の中の数学［実例］（i）p（1）＝1（ii）pが素数の場合，1，2，．‥，pの中でpと互いに薫な数は1，2，…，p−1であるから
甲（p）＝p−1となる。
（iii）γ〜′＝〆r」（p‥素数，…≧1）のときは‖1．2…．，p，p＋1，．．．，2f′，…，〆の中で〆‖と互いに素な数とは，pで割れない数である。pの倍数はp川■1個
伯一，2p，3pT…，〆′い1再）あるので＝〆‖′（1一）両〆‖・）＝〆‖−〆′一′−1pとなる。
（iv）γ↓＝peヴ・′（外用‥素数かつp≠リ，（ブ7，f≧1）のときは1，2，…，〆ヴ・′の中で′化と素でない数は，pの倍数またはりの倍数である。pの倍数はJ一番日ごとにあるので生 〃個ある。同様にヴの倍数は言個ある。r〜′よりこれらを引くと川の倍数は2回引かれてしまうopqの倍数は品個あるので
rJノ

rl

函↓）＝rい−【＋−＝叫一）（1−
JI り ／りJIとなる。特にや（才一ヴ）＝（ナノ−1）（リー1）となる。

定理3．6一般にr〜′＝p；1p昌2・・・fノ；：ー．ただしpl，…，〃γ■は相異なる素数で．（ノト‥・，（ブ丁・≧1，とするとき甲（ノrり＝叫一）（ト卜‥（1−−）
pl

才一2

1

pγ・

となる。
［証明］

卜・（ト）

小一）（1
pl
γ1

p2
rJ′

†↓ 一 ￣ − ￣

〃T・

‥・一−

JJ

JJ

＋−＋−

p′J・ plp2 plp3

p2

γJ′

−…

J／

＋（−1）T

fJIブタ2‥■p†一

rJ

＋・‥＋
p′r・−1p′r・∫ 〃αdα：暗号の中の数学となっている。ここで芸はplで割れる数の個艶話はplp2で割れる数の個数である。このときたとえばpl，p2，．‥，pf（五≧1）では割れるが，p江1，…，pr．では割れな
い数は何回数えられているか考える。
γ1では1回．

且では旦 且のよ回，つまり豆個の素数より1個選び出す組み合わせの

，…・

回数定Cl

となる。
古，・…

−−−−−−−ヱ」では∠個の素数より2個選ぶ回数パC2となる。

以下同様に考えていき，符号を考慮すれば
1−ノCl＋すC2−ノC3＋…＋（一軒且＝（1−1）∫＝0となり，pl，p2，．．．，pノで割れてpり．1∵‥∴拘・で割れない数は数えられていないことになる。
fり，…，p，・で割れない数は，始めに展開された最初の項〃の中で1回だけ数えられる。つまり小一）（1一）…（1一）
pl

p2

p7・

では〃と素な数が1回だけ数えられている。故にp（γり＝叫一）（1−）…（1一）

pl

ノ

f2

pT・

となる。

（証明終）

定理3．7（オイラーの定理）自然数γ↓に対して1，2，3，…，γ↓の中でγ↓と互いに素な数の個数をや（可とすれば．（化，γり＝1なる整数 に対して
化函）≡1（IHO（1可となる。
上の定理においてm＝♪（素数）とすればァ（♪）＝♪−1であるからフェルマーの小定理㌦￣⊥≡1（1110d♪）が得られる。

［証明］1．2，3‥．．，ハ′の中で一作と互いに素な・′′↓＝や（可個の数を∫ 川血：暗号の中の数学

けぃ〃2，．．．，〃γ‖とする。（ ，γり＝1なる化に対して．化〃ノをγ↓で割った余りをんfとする。ただしγ1で割り切れる場合は余りrJ′と考える。つまり（叫≡んィ（1IlO（1γと）．1≦れ≦mとする。 lノ＝γl≠＋んノただし≠は整数であるから，（仰木可＝（むf，γ↓）となる。（削佑可＝1より（んノ，γり＝1であるから

むf∈（（り，化2，‥．，化γ′一。）となる。一方五≠Jならばむィ≠むノであることは，次のようにしてわかる。
むメ＝んノ＝⇒（叫≡仙勺（1110（lγり＝⇒ 化享≡ ノ（ⅠIlO（1可＝＝争 壱＝．ノ．

故にん1，ん2，．‖，むγ‖．は化1，化2っ…，（1川を並べ換えただけである。よって
化1化2‥・〃川 ＝ む1む2‥・ん川≡（（〟11日 …2）・・・（ 叫什）（rflOdm）＝ 川 1 2‥・化γ化となり（り〃2・・・化…≡（1・川 り12‥・ 川（1110（lγりであることがわかる。ところで（√り12…化…，rり＝1だったから㌦回＝ 川≡1（ⅠIlOtl〃′）となる。

3・3 RSA暗号（Rivest，Shamir，Adleman，1977）

RSA暗号について簡単に説明すると以Fのようになる。参考書によって多少の違いはある。ナノ．りを非常に大きな201桁程度の2つの異なる公表されていない素数（1（証明終）∫αⅧα血：暗号の中の数学

より大きな自然数で，正の約数が1と自分自身のみであるもの）とする。このとき次のような自然数や自然数の集合を用意する。
Ⅳ ＝ 則（このpとヴは非公開とする）
上 ＝ P（pヴ）＝（p−1）（リー1）g ‥ p−1とリー1の最小公倍数〟（＝C）＝†400桁以下の自然数でⅣと互いに素なもの）
上の数を元にしてよ∈Jさんの公開鍵（cf，Ⅳ）秘密鍵† りを1．2，…，gのなかから以下のように作る。
cダ：ムと互いに素な自然数（Jf ＝ Cイ（g・J≡1（1110（lエ）となるような（gノ琉が存在するのは（ごノと上が互いに素であることによる。オイラーの定理より任意の
川ノ∈ル／tに村して・rr上上＝γr↓や（〃）≡1（IllO（lⅣ）（＊）

が成り立っていることに注意してよ∈∫さんの組立関数旦を
旦：ルイ ー→ C
rrよト→ γr↓ビ1（1IlO〔1Ⅳ）

翻訳関数βノを

玖：C →．M（‥ト→（ヰ（1110〔1Ⅳ）と定義する。このとき（ナノ（Jノ≡1（1110（lム）⇔ある自然数fが存在してcノ gf＝1＋はであるから（＊）より
γr↓ビl 才一＝rr↓1＋托＝川ノ・（川ヤ≡r′↓（1110し1Ⅳ）（γ′↓∈〟）となり，任意のγrl∈ノM，（‥∈Cに対して
玖（動（γrり）＝β訂rrん（ 1）＝（…亡 1） J−＝川′仁 −（ノー≡川′（IllO（1Ⅳ）

∫ 〃（〟k暗号の中の数学

且潤子（（二））＝旦（（‥ Jl）＝（（‥（才一）e｝＝C仁一（才一−≡c（1110（1Ⅳ）となっている。大きな自然数Ⅳ（400桁程度）の素因数分解は一般には非常に難しいから．∠∈上さんの鍵として†cノ，Ⅳ）を公開してもそれを解く鍵ぃりはⅣの素因数
分解

．＼−／り
がわからない限り求めらられないこれで公開鍵暗号が実硯できたことになる。
［実例］簡単のため

f′ ＝19．ヴ＝23

Ⅳ ＝ 四＝437
上 ＝ や（pヴ）＝396
g ＝ 198

ル1（＝C）＝（1，2，3，…．436）（ただしⅣと互いに素）とする。∠∈Jさんの公開鍵†（∫f，Ⅳ）秘密鍵†（りを以Fのように作ることができる。
（ブイ ＝13（上と互いに素）（gノ ＝ 61

このときたとえば川′＝2とすれば

動ニ2ト→213＝8192≡326（1110（1437）
玖：326 ←→ 32661＝ 20242940758841557382…‥576（154桁）≡ 2（1Il…1437）となって玖（且（2））≡2（1I10し1437）

であることがわかる。

∫（上侶1（Jα：暗号の中の数学

3．4 EIGamal暗号（T．EIGamal，1985）
この暗号は有限体（加減乗除が定義された有限集合）における離散対数（（1iH（∴1℃h−
1（蠍11・itlllll）の計算：「有限体ダの元佑〟が与えられたとき．（： ．り＝J／となるよ：∈Zを見つけること。」の困難さを利用して電子署名と公開暗号を実現するものである。実際には大きな素数J′と 自然数〟＜pに対して，自然数二上‥＜J′が与えられて〃≡〃J：（1110しIp）を計算するのは簡単であるが，逆にJノ†〟，〃から二rを求めるのは困難であるという事実を利用することが多い。

EIG之＝1之11暗号で平文γr↓に署名するには以下のようにする。まず公開鍵として次の3つの整数〃，〃，〃と秘密鍵諾を用意する。すなわち（i）f′は150桁以上の素数。
（iiトヴはランダムな自然数で〃＜fノを満足するもの。
（iii）〃≡〃J＝（Ill（）（1両ただし（iv）諾はランダムな自然数でェ＜pを満足するもの。
（i），（ii），（iii）は特定のグループDで共有され（iv）はそのグループDに署名付きの平文を送りたい者Aに秘密鍵として渡される。Aは（v）p−1と互いに素な自然数んをランダムに選び（拡張）ユーークリッド互除法を使っ
てんの逆数ん」1（1110（1クー1）
ん1ん≡1（l工10tlp−1）を計算し（vi）次の ．〜′を川ノへの署名とみなして（川ノ．隼りをβへ送る。

≡ 〃ん（111U巾′）む ≡ ん1（川ノー∬ ）（1IlOtり巨1）んの定義からγ′↓≡ニ上：（い＋んむ（1IlO（1ヱトー1）

であることに注意してほしい。 7〃を知っていてもんを求めることは困難でありんの
計算には二∫‥を必要としていて，しかも〃から諾を求めることも困難であるから，βでは式〃 ん≡〃 J・〃んん≡〃川＋んムー …

＝．リ（1IlO（りノ）∫ 〃αん：暗号の中の数学を計算することで（rrいl，わ）の送信元はAであると強く推測できる。
EIGとtlllal暗号で乎文川′を暗文cに変換するには以下のようにする。署名するときと同様に公開鍵として次の3つの整数p，．ヴ，〃と秘密鍵二上‥を用意する。すなわち（i）Jノは素数。
（ii）〃はランダムな自然数で〃＜J′を満足するもの。
（iii）〃≡．ワニ上■（1IlOtlJりただし（iv）J‥ほランダムな自然数で諾ニ＜pを満足するもの。
（i）モ（ii），（iii）は特定のグループβで共有され，そのグループβに暗文を送りたい

者Aは（Ⅴ）〃−−1と互いに素な自然数んをランダムに選び（vi）次の ，んを川ノの暗文cとみなしてc＝（隼ん）をβへ送る。

α ≡ 〃ん（1IlOtりノ）
わ ≡ 〃ん・r′↓（IllO（りノ）隼〃を知っていてもんを求めることは困経であり〜ノの計算にもんを必要としているから，βでは式

抑Ⅴ）≡（〃ん叫／（〃ん）訂≡（（．リ：l ）ん川′）川戸 ）≡川′（IllO巾ノ）を計算することで暗文 ‥＝（町りを原文…に翻訳できる。
★★★★★★★
以上がわかりやすい部分だけをとらえた暗号理論のごく一部分の概説であるがT楕「TJ

曲線群といったより複雑な代数的構造を利用する暗号も一般的なものになりつつある。
実用的な暗号理論を基礎から勉強したい却り1］，［叶［叶［6］，［22］などを，数学にも興味のある方は【1叫［2叶［23］などを，実際に僻号を使用しながら学びたい方は［8］や［15】を，計算の基礎について瞑想したい方は［2］．［14］や［16］を参考にするとよいだろう。その前に［3］や［12］などの入門書を読んでおくのも全体像が浮かびLがってよいと思う。［23］の仁1本譜版は共立州版から出ている。

参考文献［1］池野信∴小L1」謙二∴現代暗号理論（第5版）．電子情報通信学会1995［2］岩円茂樹・NP完全問題入門・共立Ⅲ版1995∫ 〃〟Jα：暗号の中の数学［3］太凹和え黒澤諷渡辺治．情朝セキュリティの科学．講談社ブルーバックス1995［4］岡本栄司，暗号理論入門．共立出版1993［5］岡本龍呪太田和夫編，暗号・ゼロ知識証明・数論．共立出版1995【6］岡本龍乳山本博資，現代暗号．産業図書1997［7］加藤正阻基礎暗号学Ⅰ耳サイエンス社19鍋［8］川原私Wllと1tisUllix66−71．仇止c抗削・．Jβββ．2−Jβクβ．7（株）アスキー［9］木Ⅶ祐二牧野潔克UI〕ASICによるコンピュータ整数論．日本評論社1994［10］揮田秀軌暗号理論と代数学，海文堂1997［11］高木貞札初等整数論講義．共立出版19飢［12］一校低唱号の数理．講談社ブルーバックス1980［13］松井甲子雄，コンピュータの為の暗号組立法人門．森北出版1986［14］守屋悦取チューリングマシンと計算量の理論．培風館1997［15］山本和象転ばぬ先のセキュリティ1−26．打√ム立言ニ〟岬上Z云r＝ββイ．5−Jβββ．β（株）アスキー［16］渡辺払計算可能性・計算の複雑さ入門．近代科学社1992［17］和田秀乳コンピュータと素因子分酪遊星社1987［18］D．E．R．Dcllllillg，Cl・yI）tOgl・aPllyallし1（1atasL！（：111・ity．AddisurL・TW（さSl（ざ〝1983［19］N・Kol）1itz，Acoul・S（一illIlu111l）L，rtll（一01■ya11（1cl・yI）tOgraI）11y，211tlc〔1itioll．郎rirL，y（7γ・−11′／中／．／Jりイ［20］N．Koblit∠．Alg（−bl・ヱtic舶Ⅰ）（雨so壬●（二1・yptOglⅥPlly．埠前里旧・−nざ7ん〟．プクββ［21］W・Patt（，1・soll，MatllClllaticalcl・yI）tOIogyfbl・COmI川tCrSCicIltisttHul（1111atll 11；Lti−
ciilllS．月01〃〃川†↓＆上よf町＃（ヱJdJββ7［22］I3．Scl111L，iu・．AI）I）1ic（1clryI）tOgl・叩11y，211（1（一（litioll．JuhlL Wil（：y＆So・rL／S、IrLC．1D96［23］D・G．StillSOll．Cl・yptOgraI）11yrTll（一Ol・yall（1Pl・actiLl∴CRCPr（：S＄．1D95（さわだひでき，山形大学理学部）