情報数理：暗号理論入門
高畑弘

2006 年 4 月 14 日

目次
第1章
1.1
1.2
1.3
1.4

初等整数論のまとめ
ユークリッドの互助法と合同式 . . . . . . . . . . . . . . . . . . . . .
フェルマーの定理とオイラーの定理 . . . . . . . . . . . . . . . . . . .
有限体 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
演習問題 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
2
4
5
9

第2章
2.1
2.2
2.3
2.4
2.5
2.6

現代暗号の基礎
暗号入門 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
RSA 暗号システム . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ディジタル署名 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
エルガマル暗号システム . . . . . . . . . . . . . . . . . . . . . . . . .
認証 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
暗号鍵交換システム . . . . . . . . . . . . . . . . . . . . . . . . . . .

10
10
12
14
16
19
22

1

第1章
1.1

初等整数論のまとめ

ユークリッドの互助法と合同式

定義 1.1 2 つの整数 a, b の正の公約数の最大値を a, b の最大公約数といい、(a, b)で表す。(a, b) = 1 のとき、a と b は互いに素であるという。
定理 1.1 2 つの整数 a, b (a2 + b2 6= 0) について、(a, b) = d ならば au + bv = d を満たす整数 u, v が存在する。b 6= 0 ならば、u として 0 5 u < |b| なるようなものを選ぶことができる。
定理 1.2 互いに素な 2 つの整数 a, b についてax ≡ 1 (mod b) (0 < x < |b|)を満たす整数 x が存在し、ただ一つである。
系 1.1 p を素数とする。p - a ならば

ax ≡ 1(mod p) (0 < x < p)を満たす整数 x が存在し、ただ一つである。
定理 1.3 (中国人の剰余定理) r 個の正の整数 p1 , p2 , . . . , pr は互いに素であるとする。また、r 個の整数 a1 , a2 , . . . , ar は任意の i (1 5 i 5 r) について (ai , pi ) = 1 であるとする。このとき、任意の整数の組 b1 , b2 , . . . , br に対して合同連立方程式

a1 x ≡ b1(mod p1 )a2 x ≡ b2..
.

(mod p2 )ar x ≡ br(mod pr )は解をもち、その解は法 M = p1 p2 · · · pr に関して一意である。

2

定義 1.2 正の自然数 n に対して、n 以下の正の自然数のうち、n と互いに素であるものの個数を ϕ(n) で表し、この関数 ϕ(n) をオイラー関数という。
定理 1.4 n の素因数分解を pα1 1 pα2 2 · · · pαk k とすると、

ϕ(n) = (pα1 1 − pα1 1 −1 )(pα2 2 − pα2 2 −1 ) · · · (pαk k − pkαk −1 )
¶µ
¶
µ
¶
µ
1
1
1
1−
··· 1 −
= n 1−p1p2pkが成り立つ。とくに、n が素数の場合は ϕ(n) = n − 1 であり、ϕ(na ) = na − na−1となる。
系 1.2 2 つの正の整数 a, b が互いに素ならば ϕ(ab) = ϕ(a)ϕ(b) である。
定理 1.5 正の自然数 n について

n=

X

ϕ(d)

d|n

が成り立つ。
証明 右辺を f (n) で表す。まず、(n, m) = 1 ならば f (mn) = f (m)f (n) であることを示す。d | mn ならば d = d1 d2 (d1 | m, d2 | n) と書ける。従って、系 1.2 を考慮してXX
ϕ(d1 d2 )f (mn) =d1 |m d2 |nXX=

ϕ(d1 )ϕ(d2 )d1 |m d2 |n


= 

X





ϕ(d1 ) 

X

ϕ(d2 )

d2 |n

d1 |m

= f (m)f (n)ところで、素数 p に対してkf (p ) =kX

ϕ(pi )

i=0

= 1+

k
X

(pi − pi−1 )

i=1
k

= p

であるから、自然数の素因数分解を考慮するならば、証明は終わる。

3

¤

1.2

フェルマーの定理とオイラーの定理

定理 1.6 (フェルマーの定理) 正の整数 p を素数とする。整数 a が p - a であるとき

ap−1 ≡ 1(mod p)が成り立つ。
系 1.3 素数 p と任意の整数 a に対して

ap ≡ a (mod p)が成り立つ。
定理 1.7 (オイラーの定理) n を正の整数、a を n と互いに素である整数とする。このとき
aϕ(n) ≡ 1 (mod n)が成り立つ。
証明 M = {r1 , r2 , . . . , rϕ(n) } を n 以下の n と互いに素である正の整数の集合とすると、あきらかに M = {Mod(ar1 , n), Mod(ar2 , n), . . . , Mod(arϕ(n) , n)} である。よって

aϕ(n) r1 r2 · · · rϕ(n) ≡ r1 r2 · · · rϕ(n)従って、aϕ(n) ≡ 1 (mod n) を得る。

(mod n)¤系 1.4 n を平方自由な（任意の素数の 2 以上のベキを因数としない）整数とする。
d と e を正の整数とし、de − 1 は n のすべての素因数 p に対して、p − 1 の倍数であるとする（例えば、de ≡ 1 (mod ϕ(n)) ）。このとき、任意の整数 a について、
ade ≡ a (mod n) が成り立つ。
証明 証明すべきことは任意の n の素因数 p に対して ade ≡ a (mod p) であることである。素数 p を固定する。もし、p | a ならば ade ≡ a (mod p) は明らかである。
p - a とすると、de − 1 = k(p − 1) であるから、定理 1.6 より、ade = {ap−1 }k a ≡ a(mod p) が得られる。よって、証明が終わる。
¤

系 1.5 異なる二つの素数 p, q について、n = pq とおく。正の整数 d, e について、de ≡ 1 (mod ϕ(n)) ならば、任意の整数 a に対して ade ≡ a (mod n) が成り立つ。

4

1.3

有限体

大雑把に言って体とは四則演算が自由にできる代数系である。また有限体とは、元の個数が有限個である体である。そんなものがあるのか？という疑問がおきるだ
ろう。これからその重要な例を説明していく。時間があまりないので、よっく聴いてくださいよ。Z 上の関係 a ≡ b mod m は同値関係であるから、2 以上の整数 m について、この関係による Z の類別ができる．各類は m で割ったときの余りによって特徴付けられので、それらそれぞれの類を法 m による剰余類と呼ぶ．この剰余類の
集合を
Z/mZ
または
Zm
で表す．明らかに、Zm の元の個数は m 個である．それぞれの類の代表元として{0, 1, 2, 3, . . . , m − 1} がとれる．従って、Zm を{[k] | 0 5 k 5 m − 1}と表すことができる．
さて、Zm の元の間に加算、乗算を定義しよう．まず、加算はつぎのように定義する．
def[k] + [j] = [Mod(k + j, m)](0 5 k, j 5 m − 1).
乗算はつぎのように定義する．
def[k] × [j] ([k][j]) = [Mod(kj, m)](0 5 k, j 5 m − 1).

加算に関して、簡略のためつぎのような記法を用いる
n個

}|
{
z
[k] + [k] + · · · + [k] = n[k],[k] = 1 · [k],0[k] = [0]同様に乗算に関してもつぎのような記法を用いる．
n個

z
}|
{
[k] × [k] × · · · × [k] = [k]n ,[k] = [k]1 ,[k]0 = [1].

最後の記法 [k]0 = [1] は k > 0 の場合について使用する．
定理 1.8 Zm は上で定義した加算乗算に関して可換環 (commutative ring) をなす．
すなわち

(1) 加算乗算に関して可換である
5

(2) 加算に関して群 (group) をなす(3) 加算乗算に関して結合法則が成り立つ(4) 分配法則が成り立つ
定理 1.9 0 < k 5 m − 1 である k について [j][k] = [1] を満たす 0 < j 5 m − 1 が存在するための必要充分条件は (k, m) = 1 である．
証明 （充分性） 定理 1.2 より、1 5 j < m で kj ≡ 1 (mod m) が存在する．
（必要性） [j][k] = [1] を満たすということは、jk + `m = 1 を満たす j, ` が存在するということであるから、(k, m) = 1 となる．
¤

定義 1.3 [1] ∈ Zm を単位元といい、少々紛らわしいが 1 で表す．また、α ∈ Zm に対して、βα = 1 を満たす β を α の（乗法に関する）逆元といい、α−1 で表す．
定理 1.10 Z∗m = {[k] | 1 5 k < m, (k, m) = 1} とおくとき、Z∗m は乗算に関して群(group) をなす．
証明 (k, m) = (j, m) = 1 とする。` = Mod(kj, m) とおき、(`, m) = 1 を示せばよい。(`, m) = d > 1 とする。このとき、kj = tm + ` = k 0 d となるので、(k, m) = (j, m) = 1 に矛盾する。
¤

定義 1.4 一般に、可換群 G の元 a について an = e (G の単位元) を満たす自然数
が存在するとき、そのうち最小の n を a の位数 (order) という．
定理 1.11 可換群 G の元 a の位数を n とする。ar = e ならば n | r である。
証明 r = qn + i (0 5 i < n) とすると、an = e より、ai = e となるが、n が a の位数であることから、i = 0 でなければならない。
¤

定理 1.12 可換群 G の二つの元 a, b のそれぞれの位数 m, n が互いに素ならば、abの位数は mn である。

6

証明 ab の位数を d とすると、定理 1.11 より d | mn である．d < mn とする。このとき mn = kd となる。d = d1 d2 (d1 | m, d2 | n), k = k1 k2 (m = d1 k1 , n = d2 k2 )と書ける。まず、d2 = n であることを示す。

¡¢d2
e = (ab)dk1 = (ab)d1 d2 k1 = ad1 k1 bd1 d2 k1 = bd1 d2 k1であるから、前定理 1.11 より、n | d1 d2 k1 であるから n | d2 となり、n = d2 を得る。
次に、d1 = m であることを示す。

¡¢d1
e = (ab)dk2 = (ab)d1 d2 k2 = ad1 d2 k2 bd2 k2= ad1 d2 k2であるから、前定理 1.11 より、m | d1 d2 k2 であるから m | d1 となり、m = d1 を得る。したがって、d = mn となる。
定理 1.13 可換群 G の元の位数の最大値を M とする．任意の元の位数は M の約数である。
証明 a ∈ G の位数を g とし、位数 M をもつ元を b とする。いま、g - M としよう。K = {g, M } とおく。もちろん K > M となる。

K = d1 d2 ,d1 | g, d2 | M,

(d1 , d2 ) = 1を満たす d1 , d2 が存在する。このとき、h1 = ag/d1 , h2 = bM/d2 とおくと、h1 , h2のそれぞれの位数は d1 , d2 であり、仮定によって、(d1 , d2 ) = 1 であるから、前定理 1.12 によって、h1 h2 ∈ G の位数は d1 d2 = {g, M } = K = に等しい。これは Mが最大位数であることに矛盾する。
¤

定義 1.5 p を素数とす。Zp を Fp で、Z∗p を Fp∗ で表す。
定理 1.14 p を素数とすると、Fp は 0 以外の元はすべて逆元をもつ可換環つまり可換体 (commutative field) である。Fp∗ は p − 1 個の元からなる。Fp∗ には p − 1 のすべての約数それぞれを位数とする元が存在する。さらに位数 d の元は ϕ(d) 個ある。
（この定理以降は体といえば可換体を意味することにする）
証明 定理の前半は明らか。後半を証明する。フェルマーの定理 1.6 によって、任意の a ∈ Fp∗ に対して ap−1 = 1 であるから、定理 1.11 によって Fp∗ の任意の元の位数
は p − 1 の約数である。a ∈ Fp∗ の位数を d とする．このとき、A = {aj | 1 5 j 5 d}

7

はすべて異なる．Fp∗ の中で位数 d をもつのは B = {aj | 1 5 j 5 d, (j, d) = 1} のϕ(d) 個のみである．なぜならば、位数 d を持つ元は方程式 X d − 1 = 0 の解であるがXd − 1 =dY(X − ai )i=1であるから、位数 d の元の集合は A の部分集合である。しかし、aj (j, d) = k > 1 については j = kj1 と書けて、{aj }d/k = {ad }j1 = 1 となるので、位数は d/k 以下となる。一方、(j, d) = 1 とすると、ju+dv = 1 を満たす整数 u, v が存在する。aj の位数を
0
0
0
0
0
0
d0 < d と仮定してみよう。このとき、ad = ad (ju+dv) = ad ju ad dv = (ajd )u (ad )d v = 1となり、a の位数が d 未満になってしまい、矛盾である。上述のことから、d | p − 1なる d に対して次の二つの場合が可能である：(a) 位数 d の元が存在し、その個数は ϕ(d)(b) 位数 d の元は存在しない。
ところで、Fp∗ の元はすべて位数をもつ。d | p − 1 なる d に対して Ad = { 位数 d を持つ元の全体 } とすると、Ad ∩ Ad0 = φ iff d 6= d0 であり、
[
Ad .
Fp∗ =
d|p−1

ところで、もし、d を位数とする元が存在するならば ](Ad ) = ϕ(d) であり、定理 1.5
Pによって p − 1 = ](Fp∗ ) =d|p−1 ϕ(d) であるから、すべての d | p − 1 に対して](Ad ) = ϕ(d) でなければならない．すなわち、任意の d | p − 1 に対して Ad 6= φ．¤
系 1.6 Fp∗ には位数 p − 1 の元が存在して、その個数は ϕ(p − 1) である。
定義 1.6 Fp∗ の位数 p − 1 の元を Fp∗ の原始元という。
系 1.7 Fp∗ の原始元を g とすると g j がまた原始元であるための必要十分条件は(j, p − 1) = 1 である。
定理 1.15 異なる素数 p, q に対して n = pq と置くとき、

Zn ∼= Zp × Zqが成り立つ。

8

証明 Zn の各元 m に Zp × Zq の元 (Mod(m, p), Mod(m, q)) を対応させればよい。
Zp × Zq における演算の定義は各成分ごとの演算である。この対応を f (m) で表す
とき、次の事柄を証明すればよい。詳細は演習問題とする。

1. f は Zn からに Zp × Zq への全単射である。全射の証明には Chinese Remainder
Theorem を用いる。
2. 写像 f が環 Zn から環 Zp × Zq への準同型である。
¤

定理 1.16 異なる素数 p, q に対して n = pq と置くとき、乗法群 Z∗n の最大位数は
g = LCM(p − 1, q − 1) に等しい。
証明 Zp と Zq のそれぞれの任意の元を a, b とすると、(a, b)g = (1p , 1q ) であることは明らかであるから、前定理によって、Z∗n の最大位数 g 0 は g の約数である。g 0 < gとしよう。ap , aq をそれぞれ Zp , Zq の原始元とする。g 0 の定義によって、
000(ap , aq )g = (1p , 1q ) = (agp , agq )が成立していなければならないのだが、ap , aq の定義によって、p − 1 | g 0 , q − 1 | g 0が成立している筈である。しかし、これは g 5 g 0 を意味するので矛盾になる。ゆえに g 0 = g である。
¤

注意 1.1 これらの定理を複数個の異なる素数 p1 , p1 , . . . , pk とその積 n = p1 p2 · · · pkの場合に拡張するのは容易である。即ち、まずZn ∼= Zp1 × Zp2 × · · · × Zpk
である。また、乗法群 Z∗n の最大位数は g = LCM(p1 − 1, p2 − 1, . . . , pk − 1) に等
しい。

1.4

演習問題

9

第2章
2.1

現代暗号の基礎

暗号入門

誰でも知っているように、暗号は、文を作成するのに利用する文字（日本語ならば漢字、ひらがな、カタカナ、英語ならば普通の意味でのアルファベット）または単語などをそれぞれ別の文字あるいは文字列に変更して、当事者以外の者にはその文の内容が理解できないようにする技術である。
一般に、通信に利用する文の構成要素の全体をアルファベットといい、Ω で表す。
文はアルファベットの列である。コンピュータで処理しやすいように、Ω のそれぞれに自然数を対応させる関数 f : Ω −→ N を符号化という。各 ω ∈ Ω に対する f (ω)
を ω の符号という。もちろん、符号化関数 f : Ω −→ N は単射でなければならない。
例題 2.1 普通のアルファベット Ω1 = {A, B, C, . . . , Z} を考える。文字は大文字のみ使用。空白、コンマ、ピリオド、疑問符、感嘆符などは用いないことにする。このとき、もっとも単純な符号化関数は f1 (A) = 0, f1 (B) = 1, f1 (C) = 2, f1 (D) =3, . . . , f1 (Z) = 25 である。
例題 2.2 前例題のアルファベット Ω1 を用いて、その n 個の直積として新しいアル
ファベット
n個
z
}|
{
Ω2 = Ω1 × Ω1 × · · · × Ω1が定義される。これは Ω1 の元の文字を n 個連ねた文字列の集合であり、](Ω2 ) = 26nである。このアルファベットに対する符号化関数はさまざまなものが考えられる。たとえば、体系的な符号化関数として次に述べるようなものがある。ω̃ = ω1 ω2 ω3 · · · ωn
にたいして符号化 f2 (ω̃) をつぎのように定める

f2 (ω̃) = f1 (ω1 ) + f1 (ω2 )26 + f1 (ω3 )262 + f1 (ω4 )263 + · · · + f1 (ωn )26n−1
上に述べたことで、アルファベットおよびその符号化については理解されたであろう。今後、アルファベットとその符号化とは同じものと考える場合もある。
それでは、簡単な古典的暗号をいくつか紹介する。

10

例題 2.3 (シーザー暗号) アルファベットは Ω1 で、符号化関数は f1 とする。文 P =a1 a2 · · · am に対する暗号文 C = b1 b2 · · · bm を次のように定義する。

bi = ai + 3 mod 26(1 5 i 5 m)

例題 2.4 (ヴィジュネ−ル暗号) アルファベットは Ω1 で、符号化関数は f1 とする。
ひとつの単語 v = v1 v2 · · · vd を決める。文 P = a1 a2 · · · am を d 文字ごとのブロックに分けて、i 番目のブロックを Pi = ai1 ai2 · · · aid とする。これについての暗号化
Ci = bi1 bi2 · · · bid を

bij = aij + vj mod 26(1 5 j 5 d)によって定義し、平文 P の暗号文として、C = C1 C2 · · · を作ればよい。
例題 2.5 (アフィン変換暗号) アルファベットと符号化関数は前例題と同様とする。
自然数 a を 26 未満で (a, 26) = 1 なるものとし、b は 26 未満の任意の自然数とする。このとき、各文字 ω ∈ Ω1 に対する暗号化関数をc = aω + b mod 26で定義する。この暗号化関数が単射であることは仮定 (a, 26) = 1 から明らか。アフィン変換暗号をブロック暗号に拡張することは容易である。
例題 2.6 (転置暗号) 例題 2.4 のヴィジュネ−ル暗号と同じように、文字の d 個づ
つのブロックを考え、それを列ベクトル ai として考える。行列 K をつぎのようなものとする。(1) 要素は 0 かまたは 1 である。(2) 各列に 1 が存在して、一つだけである。(3) 各行に 1 が存在して、一つだけである。暗号化は

bi = Kai
によって行われる。
定義 2.1 アルファベット Ω の有限列の集合 P, C と、或る暗号化機能（K をパラ
メタとする P から C への単射 fK ）の組 (fK , P, C) を K を暗号化鍵とする暗号シ
ステムという。P の元を平文、fK (P) ⊆ C の元を暗号文という。
また、各 P ∈ P に対して fK (P ) ∈ C を計算することを暗号化 (encryption) といい、暗号文 fK (P ) から平文 P を復元することを復号化 (decryption) という。
（ホン
トは復号でよいのですが、慣習に従います）

11

定義 2.2 K を暗号化鍵とする暗号システム (fK , P, C) において、各平文 P ∈ P に対する暗号文 fK (P ) から平文 P を復元する或る機能（D をパラメタとする fK (P)から P への単射 fD ）が存在するとき、そのパラメタ D を復号化鍵という。これを数式で表すと次のようになる。

fD (fK (P )) = P

P ∈P

以上の定義また以下の定義において、K, D が与えられれば、fK (P ), fD (C) を計算することは、カンタンであることが暗黙のうちに了解されているものとする、ことを確認しておきたい。
定義 2.3 暗号化鍵 K と復号化鍵 D について、一方が分かれば他方がカンタンに（多項式時間で）求められるとき、その暗号システムは対称であるという。
上の例題 2.3〜 2.6 はすべて対称暗号システムである。対称暗号システムにおいては、暗号化鍵または復号化鍵のいずれかが第三者にしられてしまうと、その暗号システムが完全に知られることになり、盗聴や成り済ましが可能になる。したがって、
暗号鍵および復号化鍵ともに秘匿されなければならない。このようなシステムでは、暗号を利用するグループの構成員が n 人いれば、n(n − 1)/2 の異なる (K, D) が必要であり、それらはすべて秘匿されなければならない。これが対称暗号システムの最大の欠点である。この欠点を克服するのが、次節以降に解説される、非対称暗号
システムまたは公開鍵暗号システムである。

2.2

RSA 暗号システム

この節で説明する RSA 暗号システムは Rivest, Shamir, Adleman の 3 名によって開発された暗号システムである。
以降、暗号システムの仕組みは周知のことと仮定する。
定義 2.4 暗号化鍵あるいは復号化鍵いずれか一方から他方を導くことが著しく困難である暗号システムを非対称暗号システムという。
以下に説明する RSA 暗号システムは、最初に実用化された非対称暗号システムである。非対称暗号システムはその特性によって、暗号化鍵を公開することができる。従って、非対称暗号システムは別名、公開鍵暗号システムとも呼ばれる。むしろ、この名称の方が一般的である。
まず、RSA 暗号システムの大雑把な内容を述べる。細かいが重要な諸注意は後ほど加えることにする。平文の集合 P は自然数のある集合とする。その最大値を NPで表しておく。

12暗号理論では情報をやりとりする人間として、アリス (Alice)、ボブ (Bob) 等の名
前がよく使用されるので、この講義でもそれを踏襲することにする。
それでは、早速、アリスの暗号化鍵と復号化鍵を作るアルゴリズムを示す。

(A1) アリスは異なる２つの巨大な素数 pA , qA を選ぶ。少なくとも 10 進法で 300 桁
ぐらいで選ぶ。そして、nA = pA qA を計算する。
(A2) アリスは nA に対するオイラー数 ϕ(nA ) = (pA − 1)(qA − 1) を計算する。
(A3) アリスは ϕ(nA ) 以下で、(eA , ϕ(nA )) = 1 となる自然数 eA を探す。eA はある程度大きい方がよい。
(A4) アリスは ϕ(nA ) 以下で、eA dA ≡ 1 (mod ϕ(nA )) を満たす自然数 dA を求める。
（ユークリッドの互除法）(A5) アリスは pA , qA , ϕ(nA ), dA を秘匿して、nA と eA のみを公開する。
この作業を、秘密の通信を行うグループの構成員すべてが行い、電話帳ならぬ暗号帳が出来上がる。そこにはアリスの {nA , eA } が登載されている。
それでは、ボブがアリスに暗号を用いて通信を行うにはどうすればよいかを説明しよう。

(B1) ボブは暗号帳を開いて、アリスの公開鍵 {nA , eA } をみつける。
(B2) ボブがアリスに送りたい平文を P とする。ボブは C = P eA mod nA を計算して、C をアリスへ送る。
暗号文 C を受信したアリスは

D = C dA mod nAを計算する。すると、定理 1.7 の系 1.4 によって、D = P であるから、アリスはボブからの平文 P を入手したことになる。
さて、eA と nA から dA を導くことが難しい理由を説明しよう。eA から dA を導くためには ϕ(nA ) を知らなければならない。ところが ϕ(nA ) を知ることと nA の素因数
分解 pA qA を知ることとは同等なのである。なぜならば、ϕ(nA ) = (pA − 1)(qA − 1) =pA qA − pA − qA + 1 = nA + 1 − (pA + qA ) であるから、ϕ(nA ) がわかれば、pA + qAがわかり、これと公開されている nA (= pA qA ) から、2 次方程式の根の公式によって pA , qA が分かってしまう。ところが、nA の素因数分解 pA qA は極めて困難である
ことが知られている。原理的には素因数分解は可能なのであるが、pA , qA が 10 進13

法で 300 桁ぐらいである場合は実際に nA を、pA , qA を知らずに素因数分解するには天文学的時間が必要なのである。
この暗号システムでは各構成員の数だけ暗号化鍵と復号化鍵の組 {e, d} があればよい。ここが対称暗号システムと大きく異なるところである（前節の終わりの部分
を参照のこと）
RSA 暗号の内容を小さな素数を用いて解説しよう。
例題 2.7 p = 19, q = 31 とすると、n = pq = 589 となる。n = 589 に対するオイ
ラー数 ϕ(n) は eu = 540 である。ここで、暗号化鍵として e = 37 とすると、d = 73
が ed ≡ 1 (mod eu) となり、d = 73 が復号化鍵となる。これらがアリスの暗号のパラメタとして、アリスは n = 589 と暗号化鍵 e = 37 を公開する。ボブはアリスに
文 P L = 375 を送るために、アリスの公開パラメタを使用する。まず、ボブはCY = 375e mod 589を計算する。CY = 451 である。そして、暗号文 CY をアリスへおくる。暗号文 CYを受け取ったアリスは
451d mod n = 375を得ることになる。
注意 2.1 二つの素数 p, q を選ぶとき、|p − q| が小さいものを選んではいけないのである。
注意 2.2 二つの素数 p, q を選ぶとき、一方の素数、例えば p 、について p − 1 が平方自由でその素因数がすべて小さいと n = pq が因数分解されて、暗号が破られる恐れがある。
注意 2.3 ボブがアリスへ送る平文をコード化して得られる自然数は nA より小さく
なくてはいけない。

2.3

ディジタル署名

重要な文書に責任者が署名をすることは日常的なことである。この署名で重要なことは、署名がその文書上に行われ、その文書と切り離せないこと、もうひとつは、その署名が真実、その署名者本人によって行われたことを確認できることである。
最近、インターネットを利用した商取引が盛んに行われている。取引が行われる
場合、署名は欠かせない。ネット通信での商取引において、物理的文書での署名と14

同じ役割を担うのがディジタル署名である。ここでは RSA 暗号システムを用いてその原理を説明することにする。

Case1. アリス (A) が、アリスのフルネーム付きの平文 P をボブ (B) へ送るものとする。アリスは P のフルネームの部分 f n を復号化鍵 dA を用いて暗号化する。そしてできる文書を P 0 とする。P 0 の中にはこれがアリスが作成した文書であることが明記されているものとする。次にe

C = P 0 B mod nBを計算し、これをボブへ送る。これを受信したボブは

D = C dB mod nBを計算すると、P 0 が得られる。ここには、判読不可能な部分 sig がある。この部分に対して、公開されているアリスの暗号パラメタ {eA , nA } を用いて

sig eA mod nA= [f ndA mod nA ]eA mod nA = f nを計算すると、アリスのフルネームが得られることになる。これによって、ボブは
この文書がアリスから発信されたものであることを信じることができる。しかし、これには、問題がある。その問題点とは？
問題点は二つある。一つは、この署名方式では、アリスのフルネームの暗号化が知られて、ボブあるいは第三者によって悪用される可能性がある。この難点を避けるためには、フルネームだけではなく、年月日やその他の冗長文を含めて、暗号化することが必要である。もう一つの難点は、本文と署名部分が分離していることである。普通の署名は本文と切り離せないようになっているが、上のような署名方式
では、本文と署名が分離可能であるから、署名の部分だけ、他の文書に利用される
危険性がある。そのため、署名は隠されていなければならない。

Case 2 ボブはアリスへ、文書 P をディジタル署名付きで送りたいとする。ボブのRSA 暗号システムの鍵パラメタを K = (n, p, q, a, b) ab ≡ 1 (mod ϕ(n)) とする。
ボブは (n, a) を公開している。ボブはsigB (P ) = P b mod nを計算して、アリスへ (P, sigB (P )) をおくる。アリスはボブの公開パラメタ (n, a)を使って
P = {sigB (P )}a mod nを確認する。
ここに、署名方式の形式的な定義を与える。

15

定義 2.5 署名方式 (signature scheme) は、以下の条件を満たす５つの組 (P, A, K, S,V) から構成される。

1 P は可能性ある文書 (message) の有限集合
2 A は可能性ある署名 (signature) の有限集合
3 K は可能性ある鍵 (key) の有限集合
4 各 K ∈ K に対して、sigK ∈ S となる署名アルゴリズム (signature algorithm)と、対応する確認アルゴリズム (verif ication algorithm) verK ∈ V が存在する。各
sigK : P → A と verK : P × A → {true, false} はすべての文書 P ∈ P とすべての署名 Y ∈ A に対して、つぎの等式を満たすような関数である。
(
true if Y = sig(P )ver(P, Y ) =false if Y 6= sig(P )このように、定義するとき、Case 2 の場合には

Y = sigB (P ) (= P b mod n)⇔

P = Y a mod nであることを証明しなければならない。(⇒) はオイラーの定理の系 1.4 から明らか。
(⇐) も同様である。

2.4

エルガマル暗号システム

RSA 暗号システムは巨大整数の素因数分解の難しさにその基礎を置く。この節ではそれとは異なる整数に関する難しさに基礎を置く暗号システムを紹介する。
現在のところ、楕円曲線まで話しを広げなければ、いずれの対称暗号システムも、
上記二つの整数論の計算困難さにその基礎を置いているといっても過言ではない。
楕円曲線まで取り込んでも、原理的はこの節で述べるものと同じである。
§1.3 の系 1.6 で述べたように、素数 p に対して、乗法群 Fp∗ には原始元（位数 p − 1の元）が存在する。
∗の原始元として、3, 5, 6, 7 など ϕ(16) = 8 個がある。
例題 2.8 p = 17 とすると F17i
ここで、g = 3 として、g (1 5 i 5 16) を計算してみると、次のような結果が得ら
れる。

i
gi

1 2
3 9

3
10

4 5 6 7 8 9 10
13 5 15 11 16 14 8
16

11 12 13
7 4 12

14 15
2 6

16
1

もちろん、原始元 g と i が与えられたとき、g i を計算するのは g, i が巨大でもそんなに時間はかからない。ところが、p が巨大であるとき、原始元 g があたえられ、
1 < y < p を勝手にとり、
y = giを満たす i を求めよとやられると、これは難しいのですよ。たとえば、

p = 374628092193991
g = 465746509としたとき、

g i = 210141791579293
を満たす i を求めよ、とやられたら、皆さんはドーしますか？正解をだしましょう。

i = 46272790174016
デース。
定義 2.6 乗法群 Fp∗ とその原始元 g が与えられたとき、1 < y < p なる y に対して

y = giを満たす i を求める問題を離散対数問題という。

p が巨大、たとえば、10 進法で 500 桁ぐらいになると、離散対数問題はとてつもなく難しいのである。もちろん、原理的には i を小さい順にとり、g i を計算すれば、いつかは辿りつくのであるが、一体どなたがそれを確認するのか？ あるいは、そのときには、すでに地球は宇宙の藻屑となっているかも知れない。
したがって、しばらくは離散対数問題をとくことは不可能であると仮定して話しをしていく。
これらを前置きとして、エルガマル暗号システムを説明しよう。暗号で通信を行いたい独立した構成員の集団を Ω とする。Ω の中ではある巨大な素数 p と乗法群
Fp∗ の原始元 g は共通なもので、構成員は p および g は知っているものとする。まず、各構成員 A は各自、ランダムな大きな自然数 aA (aA < p − 1) を選び
e A = g aAを計算し、eA を公開する。aA は秘匿する。A 以外の人は、eA を知っても aA を計算することはできない。断っておきますが、この「できない」は原理的にできない17

のではなく、実際に、あるいは現実的に「できない」のです。今後、このことについては断りませんので、よろしく。さて、アリス (A) がボブ (B) へ第三者に分からないように平文 P を暗号で送りたいとする。アリスは次の手続きをとる。

(1) 乱数 k を選ぶ。この k は通信の度に異なるものを選ぶ。まず、g k を計算する。
次に、ボブの公開パラメタ eB を探して、ekB を計算し、ついで、P ekB = P g aB k を計算する。
(2) アリスはボブへ組 (g k , P g aB k ) を送る。

この組 (g k , P g aB k ) を受け取ったボブは自分の秘匿パラメタ aB を知っているので{g k }aB = g aB kが計算できる。これから、g aB k の逆数 g −aB k が得られる。この逆数を P g aB k に乗じることにより、平文 P をボブは入手することになる。
今、第三者（オスカーと呼ばれる）がこの組 (g k , P g aB k ) を手に入れたとする。オ
スカーはボブの公開パラメタ eB = g aB を知っているから、k を知ることによって、
g aB k を知ることができるのだが、g k から k をしることは不可能！ 従って、オスカーが手に入れることができるのは g k と g aB だけである。ところが、つぎのよう
な、ほとんど確実と噂されている予想があるのである。

Diffie-Hellman の予想 g k と g aB から g aB k を計算することは不可能である。

よって、オスカーは平文 P を手に入れることはできないのである。
例題 2.9 大きな素数を使うと訳がわからなくなる恐れがありますから、p = 43 とする。原始元として g = 18 をつかう。アリスがボブへ送りたい平文を P = 37 であるとする。アリスは乱数 k として、19 を選んだ。また、ボブの秘匿パラメタは
aB = 25 としよう。そうすると eB = g aB = 30 となる。g k = 1819 = 28 である。
g aB k = 3019 = 29 であるから、P g aB k = 41 。従って、アリスはボブへ組 (28, 41) を送ることになる。これを受け取ったボブは {g k }aB = 29 をえる。これから、g −aB k = 3 を得る。P g aB k = 41 にこの 3 を乗じると P = 37 が得られる筈である。41×3 = 37 = P。得られましたね！
もう少し現実味のある数値の例をあげましょう。

18

例題 2.10 基礎になる素数と原始元をそれぞれ

p = 57390219840184391,

g = 5785576927204とする。ボブの秘匿パラメタと公開パラメタをそれぞれ

aB = 4758509309309,

g aB = 53174298763394825とする。アリスが平文 P = 67847753004982 をボブへ送ろうとしている。そのために使う乱数を k = 4839209303009409 とした。アリスは k とボブの公開パラメタ g aBを用いて
g k = 20471503608461237, g aB k = 48354733724204630
を計算し、ついでP g aB k = 20959492184555032
を得て、アリスはボブへ組 (g k , P g aB k ) を送る。ボブはこれを受け取り、早速自分の秘匿パラメタ aB を用いて

{g k }aB = g aB k = 48354733724204630,

g −aB k = 23183998621650890を得る。この最後の値を P g aB k へ乗じて、元の平文 P = 67847753004982 がボブの手元に入るのである。

2.5

認証

これまでの社会においては、自分が自分であることを証明するには、運転免許証や署名または健康保険証などが使用されてきた。ATM などを利用するには、カードと暗証番号が要求される。暗証番号は別として、その他の証明手段は物理的なものであり、ネットワーク社会においては利用できない。
ネットワーク社会においてはディジタル信号による通信を媒介とする自己証明が不可欠である。ここでは、公開鍵暗号システムを利用しての認証（自己証明）についての初歩を話したい。
署名と認証とは良く似ている。署名は保存される必要があるが、認証は保存される必要はないことが多い。また、署名は文書全体になされる必要があるため、特殊な加工（ハッシュ関数の利用）が要求される一方、認証は概して短い文の処理で達成される。例題をもって具体的にお話ししましょう。

19

例題 2.11 (エルガマル暗号システムによる認証) アリス (A) がボブ (B) に対して、
アリスであることを証明することを考える。アリスのフルネームを P で表す。いま、アリスとボブが利用しているエルガマル暗号システムの基礎になる素数を p とし、Fp∗ の原始元を g とする。構成員 Y の秘匿、公開パラメタをそれぞれ αY , gY = g αYであらわすことにしよう。認証の手続きは次のようになる。

(1) アリスはボブの公開パラメタ gB を探し、自分の秘匿パラメタ αA を用いて、
e(A, B) = {gB }αA を計算する。
(2) ついで、アリスは P e(A, B) を計算して、ボブへ送る。
(3) P e(A, B) を受け取ったボブは、これがアリスから送られたものであることを確認するために、アリスの公開パラメタ gA を探し、e(A, B) = {gA }αB を計算する。
(4) さらに、ボブは inv(A, B) = e(A, B)−1 を計算して、これを P e(A, B) に乗じて P を得る。これで、送り主がアリスであることを承認することになる。
例題 2.12 (RSA 暗号システムによる認証) 前例題と同じ認証の問題を RSA 暗号
システムを利用して考えよう。構成員 Y の秘匿、公開パラメタともに、添字 Y で表すことにする。nA < nB とする。

(1) アリスは自分の秘匿パラメタ dA を用いて、PA = P dA mod nA を計算する。
(2) ついで、アリスはボブの公開パラメタ {nB , eB } をもちいて、P (A, B) = (PA )eB
modnB を計算して、ボブへ送る。
(3) P (A, B) を受け取ったボブは自分の秘匿パラメタ dB を用いて、PA = P (A, B)dB
modnB を計算する。
(4) ついで、ボブはアリスの公開パラメタ {nA , eA } を用いて、P = (PA )eA mod nAを得て、このメッセージがアリスから来たものであることを承認する。
例題 2.13 (エルガマル暗号システムによる認証の実例) アリスとボブが参加する暗号システムがエルガマル暗号システムであるとして、その基礎的パラメタ、および
アリス、ボブの秘匿パラメタを次のように定める。

p = 476929193900483
g = 435707320960
aA = 57832842920927
aB = 24783703804721
20このとき、アリスおよびボブの公開パラメタは次のようになる。

gA = g aA = 193807912723584
gB = g aB = 121037467259902
いま、アリスの自己証明の文を P = 75022090201745 とする。アリスはまずボブの
公開パラメタ gB を見て、自分の秘匿パラメタ aA を用いて

e(A, B) = {gB }aA = 265585636095466を計算して、ついで P e(A, B) = 343821383397651 をボブへ送る。ボブはこのデー
タ C がアリスから送られたものであることを確認するために、アリスの公開パラメ
タ gA をとり、自分の秘匿パラメタを用いて

e(B, A) = e(A, B) = {gA }aB = 265585636095466を計算して、ついで e(B, A)−1 = 395247222995204 を得る。これをデータ C に乗じてC × e(B, A)−1 = 75022090201745 = Pを得て、送り手がアリスであることを確認する。
例題 2.14 (RSA 暗号システムによる認証の実例) アリスとボブの RSA 暗号シス
テムのパラメタ {p, q, n = pq, ϕ(n), e, d, } （n, e のみを公開）をそれぞれ{pA , qA , nA , ϕ(nA ), eA , dA } = {373, 607, 226411, 225432, 35473, 37393}{pB , qB , nB , ϕ(nB ), eB , dB } = {461, 947, 436567, 435160, 73059, 333659}とする。アリスが自己証明の文 P = 170573 をボブに送って自分がアリスであることを証明することを考えよう。まず、アリスは自分の秘匿パラメタ dA を用いて

P dA mod nA = 220750 (= C)を計算し、ついで、ボブの公開パラメタ {nB , eB } を用いて

C eB mod nB = 153359 (= AU )を計算して、ボブへ送る。これを受け取ったボブは自分の秘匿パラメタ dB を用いて

AU dB mod nB = 220750 = C
を得て、ついで、アリスの公開パラメタ {nA , eA } を用いて

C eA mod nA = P dA eA mod nA = Pを得る。これによって、送り手がアリスであることを確認するのであるよ。

21

2.6

暗号鍵交換システム

一般に、公開暗号システムはセキュリティの強いシステムであるが、暗号化や復号化に時間が掛かるという欠点をもつ。処理の速さからすると、§2.1 で述べた古典的暗号システム（対称暗号システム）の方が優れる。従って、長い平文を暗号化するような場合には、認証や重要な部分は公開暗号システムを用いるが、さほど重要ではない部分は対称暗号システムを用いるといった、「日和見主義的」あるいは「ご都合主義的」な方法を用いるのである。いつも一貫性がベストとは限らないのだ。
さて、対称暗号システムを用いるとなると、鍵を交換しなければならない。アリスが用いた暗号化鍵をなんとかボブへ伝えなければならない。ドースルー？郵送するのはかったるい。電話で伝えたくとも、盗聴が怖い。ドースルー？
例えば、アリスがボブへ送る暗号文の一部にヴィジュネ−ル暗号（参照 §2.1）を用いるとする。アリスが用いる暗号化鍵が”dictionary”とすると、これをボブへ伝えなければ、ボブはこの鍵を求めて頻度解析をおこなわなければならない。平文が短
いとそれは不可能である。この暗号化された通信文がラブレターだったらボブにとって悲劇である。もっとも、ボブもアリスを愛しているならば、の話しではあるが・・・
代表的な鍵交換システムを例で説明しましょう。
例題 2.15 (Diffie-Hellman 鍵交換システム) アリスとボブが参加している離散対数を利用した暗号システムの基礎パラメタである素数 p と Fp∗ の原始元をそれぞれ
次のように定める。

p = 5930204048231
g = 65998209817.
アリスとボブの秘匿パラメタをそれぞれ次のように定める。

aA = 5720921092121
aB = 4728182390175.
このとき、アリスとボブの公開パラメタは次のようになる。

gA = g aA = 4571974152858
gB = g aB = 2961999623964.
アリスとボブは対称暗号のパラメタ d(A, B) を次のようにするのである。

d(A, B) = g aA aB = 3384471491518.
22例えば、アリスがボブへ送る文のある部分がヴィジュネ−ル暗号であり、その暗号の暗号化鍵を上の d(A, B) であるとする。アルファベットとして普通の英字アルファ
ベットとすると、d(A, B) を 26 進法表現になおせばよいのだ。これはカンタンな計
算でd(A, B) = (16, 5, 9, 25, 4, 17, 6, 11, 0)26 = QFJZERGLA
であることが分かる。このアリスとボブの共通鍵は、この二人にしか知られない鍵である。なぜなら、Diffie − Hellman の予想 によって、公開されている二人のパラ
メタ g aA , g aB から g aA aB = d(A, B) を求めることは不可能であるからである。

RSA 暗号システムを用いて同じような鍵の交換ができるだろうか？ 考えてみよう。

23