Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN:
0849385210
Pub Date:
03/17/95
Table of Contents
Index
abelian group,
4
, 116, 184
accept,
385
access structure,
331
threshold,
332
, 333
active adversary,
258
additive identity,
3
additive inverse,
3
adjoint matrix,
16
adversary
active,
258
passive,
258
Affine Cipher,
8
, 8-12
cryptanalysis of, 26-27
affine function,
8
Affine-Hill Cipher,
41
algorithm
deterministic,
129
Las Vegas,
139
, 171, 234
Monte Carlo, 129,
129
probabilistic,
129
associative property,
3
of cryptosystems,
66
authentication code,
304
, 304-323
combinatorial bounds, 311-313
deception probability,
305
, 306-313, 319-323
entropy bounds, 321-323
impersonation attack,
305
, 306-308
orthogonal array characterization, 319-320
substitution attack,
305
, 307-309
authentication matrix,
306
authentication rule,
305
authentication tag,
305
authorized subset,
331
minimal,
332
Autokey Cipher, 23,
23
basis,
332
Bayes Theorem,
45
, 60, 135, 340, 341
binding,
399
binomial coefficient,
31
birthday paradox,
236
bit commitment scheme,
399
, 398-401, 405-407
blob,
399
block cipher,
20
Blom Key Predistribution Scheme,
261
, 260-263
Blum-Blum-Shub Generator,
371
, 370-377, 379
Blum-Goldwasser Cryptosystem,
380
, 379-382
boolean circuit, 333
fan-in,
333
fan-out,
333
monotone,
333
boolean formula,
333
conjunctive normal form,
337
disjunctive normal form,
334
Bos-Chaum Signature Scheme,
216
, 215-217
Brickell Secret Sharing Scheme,
344
, 343-348
Caesar Cipher,
4
certificate,
264
challenge,
385
challenge-and-response protocol,
217
, 283, 385
Chaum-van Antwerpen Signature Scheme,
218
, 217-223
Chaum-van Heijst-Pfitzmann hash function,
238
, 238-241
Chinese remainder theorem,
122
, 119-122, 142, 166, 380
Chor-Rivest Cryptosystem, 115
chosen ciphertext cryptanalysis,
25
chosen plaintext cryptanalysis,
25
cipher
block,
20
stream,
20
, 20-24, 360
cipher block chaining mode, 83,
83
, 267
cipher feedback mode,
83
, 85
ciphertext,
1, 20, 378
ciphertext-only cryptanalysis,
25
closure,
332
closure property,
3
code,
194
distance of,
194
dual code,
194
generating matrix,
194
Goppa code,
195
Hamming code,
196
nearest neighbor decoding,
194
parity-check matrix,
194
syndrome,
194
syndrome decoding,
195
coin-flipping by telephone,
400
commutative cryptosystems,
66
commutative property,
3
complete graph,
346
complete multipartite graph,
346
, 352, 353
completeness,
286, 386
Composites, 129,
130
computational security,
44
concave function,
56
strictly,
56
concealing,
399
conditional entropy,
59
conditional probability,
45
congruence,
3
conjunctive normal form boolean formula,
337
cryptanalysis,
6
chosen ciphertext,
25
chosen plaintext,
25
ciphertext-only,
25
known-plaintext,
25
cryptogram, 7
cryptosystem,
1
endomorphic,
64
idempotent,
66
iterated,
66
monoalphabetic,
12
polyalphabetic,
13
private-key,
114
probabilistic public-key,
378
product,
64
, 64-67
public-key,
114
cyclic group,
123
, 183, 187
Data Encryption Standard, 51,
70
description of, 70-78
differential cryptanalysis of,
89
, 89-104
dual keys,
110
exhaustive key search,
82
expansion function,
71
, 73
initial permutation,
70
, 73
key schedule,
71
, 75-78
modes of operation,
83
, 83-86
S-boxes,
72
, 73-75, 82
time-memory tradeoff,
86
, 86-89
dealer,
326
deception probability,
305
decision problem,
129
, 190
decomposition construction,
354
,
355
, 353-357
decryption rule,
1, 21, 378
determinant,
16
deterministic algorithm,
129
differential cryptanalysis,
89
characteristic,
98
filtering operation,
101
input x-or,
89
output x-or,
89
right pair,
100
wrong pair,
100
Diffie-Hellman Key Exchange,
270
, 270-271
Diffie-Hellman Key Predistribution Scheme,
265
, 263-267
Diffie-Hellman problem,
266
, 265-267, 275
Digital Signature Standard, 205,
211
, 209-213
digram,
25
disavowal protocol,
217
Discrete Logarithm Generator,
383
Discrete Logarithm problem, 162,
163
, 164-177, 206, 207, 210, 238, 263, 266, 276, 287, 290, 362, 397, 400, 406
bit security of, 172-177, 400
elliptic curve, 187
generalized,
177
, 177-180
in Galois fields, 183
index calculus method, 170-172
i
th Bit problem,
173
Pohlig-Hellman algorithm,
169
, 166-170
Shanks algorithm,
165
, 165-166
disjunctive normal form boolean formula,
334
distinguishable probability distributions,
364
distinguisher,
364
distribution rule,
338
distributive property,
4
electronic codebook mode, 83,
83
ElGamal Cryptosystem, 115,
163
, 162-164, 266-267
elliptic curve, 187-190
generalized,
178
, 177-178
ElGamal Signature Scheme, 205, 205-209
elliptic curve,
183
, 183-187
point at infinity, 183
Elliptic Curve Cryptosystem, 115, 187-190
encryption matrix,
47
encryption rule,
1, 21, 378
endomorphic cryptosystem,
64
entropy,
52
, 51-52
conditional,
59
of a natural language,
61
of a secret sharing scheme, 349-352
of authentication code, 321-323
properties of, 56-59, 349
Euclidean algorithm, 116-120, 140, 179, 181
extended, 117,
119
running time of, 128
Euler phi-function,
9
Euler pseudo-prime,
132
Eulers criterion, 130,
131
, 173
exclusive-or,
21
exhaustive key search,
6
, 13
of DES,
82
factor base, 171
factoring, 150-156
factor base,
153
number field sieve, 155
p
- 1 algorithm,
151
, 151-152
quadratic sieve, 154
trial division,
150
fan-in,
333
fan-out,
333
Fermats theorem,
122
, 137
Fibonacci number,
128
field,
10
, 181
forging algorithm,
390
for Graph 3-colorability,
405
for Graph Isomorphism,
391, 394
Galois field, 180-183
Girault Key Agreement Scheme,
278
, 276-279
Goldwasser-Micali Cryptosystem,
379
, 378-379, 399
graph, 346
complete,
346
complete multipartite,
346
, 352, 353
induced subgraph,
352
isomorphic,
386
proper 3-coloring,
401
Graph 3-colorability,
401
Graph 3-colorability Interactive Proof System,
402
, 400-404, 406-407
Graph Isomorphism,
386
Graph Isomorphism Interactive Proof System,
389
, 388-395
Graph Non-isomorphism, 386
Graph Non-isomorphism Interactive Proof System,
387
, 386-388, 395-396
group,
4
abelian,
4
, 116, 184
cyclic,
123
, 183, 187
order of element in,
122
Guillou-Quisquater Identification Scheme,
296
, 295-299
identity-based,
300
Hamming distance,
194
hash function, 203,
232
, 232-254
birthday attack, 236-237
collision-free, 233-236
constructed from a cryptosystem, 246
extending, 241-246
one-way,
234
strongly collision-free,
233
weakly collision-free,
233
Hill Cipher, 13-17,
18
cryptanalysis of, 36-37
Huffman encoding, 53-56
Huffmans algorithm,
55
ideal decomposition,
353
ideal secret sharing scheme,
343
, 344, 346-348
idempotent cryptosystem,
66
identification scheme, 282-300
converted to signature scheme, 300
identity-based,
299
, 299
identity matrix,
14
impersonation,
305
implicit key authentication,
276
, 278
independent random variables,
45
index of coincidence,
31
mutual,
33
indistinguishable probability distributions, 363-370, 378, 404
induced subgraph,
352
information rate,
342
monotone circuit construction,
343
injective function,
2
interactive argument
perfect zero-knowledge,
407
zero-knowledge,
406
, 405-407
interactive proof,
385
, 385-397
computational zero-knowledge, 398,
404
, 400-404
perfect zero-knowledge,
393
, 388-397
perfect zero-knowledge for Vic,
391
zero-knowledge, 385
intruder-in-the-middle attack,
271
, 305
inverse matrix,
15
inverse permutation,
7
isomorphic graphs,
386
iterated cryptosystem,
66
Jacobi symbol,
132
, 132-134, 370, 379
Jensens Inequality,
56
, 63, 316
joint probability,
45
Kasiski test,
31
Kerberos,
268
, 267-270
key lifetime,
268
session key, 267
timestamp,
268
Kerckhoffs principle,
24
key,
1, 20, 203, 305, 326, 378
key agreement,
258
authenticated,
271
key confirmation,
269
key distribution,
258
on-line,
259
key equivocation,
59
key freshness,
267
key predistribution,
259
, 260-267
key server,
259
keystream,
20
keystream alphabet,
21
keystream generator,
21
keyword,
12
known-plaintext cryptanalysis,
25
Lagrange interpolation formula,
329
, 329-330
Lagranges theorem,
122
Lamés theorem,
128
Lamport Signature Scheme,
213
, 213-215
Las Vegas algorithm,
139
, 171, 234
Legendre symbol,
131
, 131-132
Linear Congruential Generator,
360
, 360
linear feedback shift register,
22
, 360, 362
linear recurrence,
21
linear transformation,
14
m
-gram Substitution Cipher,
68
matrix product,
14
McEliece Cryptosystem, 115,
196
, 193-198
MD4 Hash Function,
248
, 247-250
MD5 Hash Function, 247, 250
memoryless source,
53
Menezes-Vanstone Cryptosystem,
189
, 188-190
Merkle-Hellman Cryptosystem, 115,
193
, 190-193
message,
203, 305
message authentication code,
86
, 304
message digest,
232
Miller-Rabin algorithm, 129, 130,
137
, 136-138
error probability of, 138
mod operator,
3
modular exponentiation,
127
square-and-multiply algorithm, 127,
127
, 131
modular multiplication,
126
modular reduction,
3
modulus,
3
monoalphabetic cryptosystem,
12
monotone circuit,
333
monotone circuit construction, 333,
335
information rate,
343
monotone property,
332
Monte Carlo algorithm, 129,
129
, 374
error probability of,
129
no-biased,
129
unbiased,
374
, 374-377
yes-biased,
129
MTI Key Agreement Protocol,
274
, 273-276
Multiplicative Cipher, 65,
65
multiplicative identity,
4
multiplicative inverse,
10
mutual index of coincidence,
33
next bit predictor, 365-370
NP-complete problem, 44, 191, 193, 400, 404
Okamoto Identification Scheme,
291
, 290-295
One-time Pad, 50,
50
one-way function,
116
, 213, 234
trapdoor,
116
oracle,
139
orthogonal array,
314
, 313-320
bounds, 315-318
constructions, 318-319
output feedback mode,
83
, 85, 362
passive adversary,
258
perfect secrecy,
48
, 44-51
perfect secret sharing scheme,
332, 339, 349
periodic stream cipher,
21
permutation,
2
Permutation Cipher,
18
, 17-20
permutation matrix,
19
plaintext,
1, 20, 378
polyalphabetic cryptosystem,
13
polynomial
congruence of,
180
degree of,
180
division,
180
irreducible,
181
modular reduction of,
181
polynomial equivalence,
126
prefix-free encoding, 54
previous bit predictor,
373
primality testing, 129-138
prime,
9
Prime number theorem,
129
, 135
primitive element,
123
principal square root,
373
, 379
private-key cryptosystem,
114
probabilistic algorithm,
129
probabilistic encryption, 377-382
probabilistic public-key cryptosystem,
378
probability, 45
conditional,
45
joint,
45
product cryptosystem,
64
, 64-67
proof of forgery algorithm,
224
proof of knowledge,
285
proper 3-coloring,
401
protocol failure, 156,
158
, 208
prover,
385
pseudo-random bit generator,
359
, 359-377
pseudo-square,
370
public-key cryptosystem,
114
probabilistic,
378
quadratic non-residue,
130
Quadratic Non-residues Interactive Proof System,
408
quadratic reciprocity, 132
quadratic residue,
130
Quadratic Residues, 130,
130, 371
, 370-371, 374, 375, 377, 396, 399, 406
Quadratic Residues Interactive Proof System,
396
, 396-397
Rabin Cryptosystem,
147
, 145-150
security of, 149-150
rank,
226
redundancy of a natural language,
61
reject,
385
relative shift,
33
relatively prime,
9
replay attack,
269
response,
385
ring,
4
, 180
round,
385
RSA Cryptosystem, 114,
124
, 124
attacks on, 138-145
bit security of, 144-145
implementation of, 125-128
RSA Generator,
362
, 362-363
RSA Signature Scheme, 203,
204
Schnorr Identification Scheme,
286
, 284-289, 295
Schnorr Signature Scheme,
301
search problem,
190
secret sharing scheme, 326-357
decomposition construction, 353-357
ideal,
343
, 344, 346-348
information rate,
342
, 341-343, 349-355
monotone circuit construction, 333-338
threshold scheme, 326-331
Secure Hash Standard, 247, 250-252
security parameter,
284, 378
seed,
359
self-certifying public key,
276
session key,
259
Shamir Threshold Scheme,
327
, 327-330, 343, 346
share,
326
Shift Cipher,
4
, 3-7
Shrinking Generator, 362
signature,
203
signature scheme,
203
, 202-229
constructed from identification
scheme, 300
fail-stop, 224-229
one-time, 213-217, 228
undeniable, 217-223
signing algorithm,
203
simulator,
390
Solovay-Strassen algorithm,
133
, 129-136
error probability,
136
, 134-136
soundness,
288, 386
source state,
304
Sperner property,
215
spurious keys,
61
, 59-64
expected number of, 63
square-and-multiply algorithm,
127
, 127, 131
Station-to-station Protocol,
272
, 271-273
Stirlings formula,
68
, 216
stream cipher,
20
, 20-24, 360
cryptanalysis of, 37
synchronous,
21
, 85
Subgroup Membership,
397
Subgroup Membership Interactive Proof System,
398
Subset Sum problem,
190
, 190-191
modular transformation,
192
superincreasing,
191
substitution,
305
Substitution Cipher, 7, 7, 7-8
cryptanalysis of, 27-31
m
-gram,
68
synchronous stream cipher,
21
, 85
threshold scheme,
326
, 326-331
timestamping, 252-254
transcript,
390
Transposition Cipher, 17
trapdoor,
116
trigram,
25
trusted authority,
258
unconditional security,
45
unicity distance,
63
, 59-64
van Heyst-Pedersen Signature Scheme,
225
, 224-229
Vandermonde matrix, 329
determinant of, 329
verification algorithm,
203
verifier,
385
Vernam One-time Pad, 50,
50
Vigenere Cipher,
12
, 12-13, 40
cryptanalysis of, 31-36
zero-knowledge interactive argument,
406
, 405-407
perfect,
407
zero-knowledge interactive proof, 385
computational, 398,
404
, 400-404
perfect,
393
, 388-397
perfect, for Vic,
391
Table of Contents
Copyright ©
CRC Press LLC