index.pdf

This is a Chapter from the Handbook of Applied Cryptography, by A. Menezes, P. van

Oorschot, and S. Vanstone, CRC Press, 1996.

For further information, see www.cacr.math.uwaterloo.ca/hac

CRC Press has granted the following specic permissions for the electronic version of this

book:

Permission is granted to retrieve, print and store a single copy of this chapter for

personal use. This permission does not extend to binding multiple chapters of

the book, photocopying or producing copies for other than personal use of the

person creating the copy, or making electronic copies available for retrieval by

others without prior permission in writing from CRC Press.

Except where over-ridden by the specic permission above, the standard copyright notice

from CRC Press applies to this electronic version:

Neither this book nor any part may be reproduced or transmitted in any form or

by any means, electronic or mechanical, including photocopying, microlming,

and recording, or by any information storage or retrieval system, without prior

permission in writing from the publisher.

The consent of CRC Press does not extend to copying for general distribution,

for promotion, for creating new works, or for resale. Specic permission must be

obtained in writing from CRC Press for such copying.

1997 by CRC Press, Inc.

Index

Symbols

jSj (cardinality of a set S ), 49

2 (set member), 49

(subset), 49

(proper subset), 49

\ (set intersection), 49

[ (set union), 49

− (set difference), 49

(Cartesian product), 49

; (empty set), 50

O -notation (big-O), 58

-notation (big-omega), 59

-notation (big-theta), 59

o -notation (little-o), 59

de = (by deﬁnition), 213

L q [ ; c ] (subexponential notation), 60

P (polytime reduction), 61

(asymptotic equivalence), 134

(mathematical constant pi), 49

e (base of natural logarithms), 49

P (sum), 50

Q (product), 50

! (factorial), 50

bc (ﬂoor), 49

de (ceiling), 49

(Euler phi function), 65, 286

( n ) (Mobius function), 154

lg (base 2 logarithm), 50

ln (natural logarithm), 50

[ a; b ] (interval of integers), 49

j (divides relation), 63, 79

(congruence relation), 67, 79

(much less than), 529

(much greater than), 170

Z (the integers), 49

Z n (integers modulo n ), 68

Z n (multiplicative group of Z n ), 69

Q n (quadratic residues modulo n ), 70

Q n (quadratic non-residues modulo n ), 70

F q (ﬁnite ﬁeld of order q ), 81

F q (multiplicative group of F q ), 81

R [ x ] (polynomial ring), 78

_ (inclusive-OR), 213

(exclusive-OR), 20

^ (AND), 213

(addition mod 2 n ), 263

(subtraction mod 2 n ), 270

(modiﬁed multiplication mod 2 n +1), 263

- (left rotation), 213

(right rotation), 213

A ! B

(message transfer), 396

Abelian group, 75

Abstract Syntax Notation One (ASN.1), 660

Access control, 3

Access control matrix, 387

Access matrix model, 569

Access structure, 526

monotone, 527

Accredited Standards Committee (ASC), 648

Active adversary, 15, 37

Active attack, 41, 495

Ad hoc security, 43

Adaptive chosen-ciphertext attack, 42

Adaptive chosen-message attack, 433

Adaptive chosen-plaintext attack, 41

Addition chains, 621, 633

Adversary, 13, 495

active, 15

insider, 496

one-time, 496

permanent, 496

outsider, 496

passive, 15

Afﬁne cipher, 239

Algebraic normal form, 205

Algorithm

deﬁnition of, 57

k (binomial coefﬁcient), 52

p (Legendre symbol), 72

<> (inner product), 118

kxk

(length of a vector

), 118

a b

(assignment operator), 66

akb (concatenation of strings a , b ), 38

f 0 ; 1 g k (bitstrings of bitlength k ), 447

f 0 ; 1 g (bitstrings of arbitrary bitlength), 447

Q (the rational numbers), 49

R (the real numbers), 49

755

756

Index

deterministic, 62

exponential-time, 59

polynomial-time, 59

randomized, 62

expected running time, 63

running time, 58

asymptotic, 58

average-case, 58

worst-case, 58

subexponential-time, 60

Alphabet of deﬁnition, 11

Alternating step generator, 209–211, 220

Anonymity, 3

ANSI standards, 648–651, 660

ordering and acquiring, 656

ANSI X9.17 pseudorandom bit generator, 173

Anti-palindromic keys of DES, 257

Appended authenticator, 361

Arbitrated signature scheme, 472–473

Arithmetic

integer, see Multiple-precision integer arithmetic

modular, see Multiple-precision modular arith-

metic

Arthur-Merlin games, 421

ASN.1, see Abstract Syntax Notation One (ASN.1)

Asymmetric cryptographic system, 544

Asymptotic running time, 58

Atkin’s primality test, 145

implementation report, 166

Attack

active, 41, 495

adaptive chosen-ciphertext, 42

adaptive chosen-message, 433

adaptive chosen-plaintext, 41

chosen-ciphertext, 41, 226

chosen-message, 433

chosen-plaintext, 41, 226

chosen-text, 417

ciphertext-only, 41, 225

dictionary, 42, 392

differential cryptanalysis, 258

differential-linear, 271

exhaustive key search, 233–234

forced delay, 417

forward search, 42, 288, 420

impersonation, 42, 417

interleaving, 42, 417, 531, 540

intruder-in-the-middle, 530, 540

key-only, 432

known-key, 42, 496, 534

known-key triangle, 538

known-message, 432

known-plaintext, 41, 225

linear cryptanalysis, 258

local, 419

meet-in-the-middle, 235

misplaced trust in server, 531

non-interactive, 419

off-line, 419

on-line, 419

passive, 41, 495

pre-play, 397

reﬂection, 417, 530, 540

related-key, 226

remote, 419

replay, 42, 417

time-memory tradeoff, 236

truncated differentials, 271

universal forgery, 482

Attacker, 13

Attacker (alternate names), 495

see also Entity authentication

explicit key, 492

key, 492

message, 361

mutual, 494

protocol, 493

transaction, 362

unilateral, 494

see also Entity authentication (and Identiﬁca-

tion)

Authentication code, 376, 382

Authentication path, 557

Authentication server, 491, 549

Authentication tree, 466–468, 485, 556–559, 587

Authority revocation list (ARL), 577

Authorization, 3

Authorized subset, 527

Auto-key cipher, 242

Autocorrelation function, 180

Autocorrelation test, 182

Auxiliary-input zero-knowledge, 423

Avalanche effect, 277

Average-case running time, 58

Baby-step giant-step algorithm, 104–106, 128

1997 by CRC Press, Inc. — See accompanying notice at front of chapter.

Index

757

BAN logic, 420, 534, 541

Bandwidth efﬁciency, 437

Barrett reduction, 603–605, 631

Base b representation, 592

Basis, 80

Bayes’ theorem, 51

BEAR block cipher, 282

Beaufort cipher, 241

Beller-Yacobi key transport

2-pass, 514

4-pass, 513

Berlekamp’s Q -matrix algorithm, 124, 132

Berlekamp-Massey algorithm, 200–201

next discrepancy, 200

Bernoulli trial, 52

Biased, 172

Big-endian, 344

Big-O notation, 58

Big-omega notation, 59

Big-theta notation, 59

Bijection, 7, 50

Binary additive stream cipher, 194

keystream generator, 194

running key generator, 194

Binary alphabet, 11

Binary Euclidean algorithm, 632

Binary extended gcd algorithm, 608–610, 632

Binary gcd algorithm, 606–607, 632

Binary operation, 75

Binary representation, 592

Binary tree, 557

balanced, 558

children, 557

depth of, 558

internal vertex, 557

leaf, 557

parent, 557

root vertex, 557

Binomial

coefﬁcient, 52

distribution, 52

theorem, 52

Biometrics, 387, 420

Birthday attack, 352, 369

Birthday problem, 53

Birthday surprise, 53

Bit commitment, 421

Bitzer’s hash function, 374

Black-box, 329, 341, 369, 378

Blakley’s threshold scheme, 538

Blind signature scheme, 475, 487

based on DSA, 487

based on Nyberg-Rueppel, 487

Chaum, 475

fair, 487

Blinded message, 475

Blinding function, 475

based on RSA, 475

Blob, 421

Block cipher, 223–282

3-WAY, 281

attacks on

differential cryptanalysis, 258

differential-linear, 271

exhaustive key search, 233–234, 273

key clustering attack, 281

linear cryptanalysis, 258

meet-in-the-middle attack, 235

related-key attack, 226, 281

time-memory tradeoff, 236, 273

truncated differentials, 271, 280

BEAR, 282

Blowﬁsh, 281

CAST, 281

classical cipher, 237–250

deﬁnition of, 16, 224

DES, 250–259

double DES, 235

FEAL, 259–262

GOST, 282

IDEA, 263–265

iterated, 251

Khafre, 271

Khufu, 271

LION, 282

LOKI’91, 270

Luby-Rackoff, 282

Lucifer, 276

modes of operation, 228–233, 272

ANSI X3.106 standard, 649

ANSI X9.52 standard, 651

CBC with checksum (CBCC), 367

cipher feedback mode (CFB), 231

cipher-block chaining mode (CBC), 230

counter mode, 233

electronic codebook mode (ECB), 228–

230

FIPS 81 standard, 654

ISO 8372 standard, 645

ISO/IEC 10116 standard, 647

output feedback mode (OFB), 232–233

plaintext-ciphertext block chaining

(PCBC), 368

Randomized DES (RDES), 278

RC2, 282

RC5, 269–270

round function, 251

SAFER, 266–269

Handbook of Applied Cryptography by A. Menezes, P. van Oorschot and S. Vanstone.

758

Index

semi-weak keys (of DES), 257

anti-palindromic keys (of DES), 257

SHARK, 281

SKIPJACK, 282, 584

TEA, 282

triple DES, 272

WAKE, 282

Block of a sequence, 180

Blocklength, 224

Blom’s KDS bound, 505

Blom’s key pre-distribution system, 506, 536

Blowﬁsh block cipher, 281

Blum integer, 74–75

Blum-Blum-Shub pseudorandom bit generator, 186–

187, 308

Blum-Goldwasser probabilistic public-key encryp-

tion, 308–311

decryption algorithm, 309

encryption algorithm, 309

key generation, 308

security of, 310

Blum-Micali pseudorandom generator, 189

Blundo’s conference KDS bound, 529

Boolean function, 202

algebraic normal form of, 205

correlation immune, 207

nonlinear order of, 205

BPP ,63

Break-backward protection, 496

Brickell-McCurley identiﬁcation protocol, 423

Broadcast encryption, 528

Bucket hashing, 382

Burmester-Desmedt conference keying, 528

Burst error, 363

CBC-MAC, 353–354, 367

ANSI X9.9 standard, 650

ANSI X9.19 standard, 650

FIPS 113 standard, 654

ISO 8731-1 standard, 652

ISO 9807 standard, 652

ISO/IEC 9797 standard, 646

Cellular automata stream cipher, 222

Certiﬁcate

ANSI X9.45 standard, 651

ANSI X9.55 standard, 651

ANSI X9.57 standard, 651

caching, 576

chain, 572

directory, 549

pull model, 576

push model, 576

forward, 575

on-line, 576

public-key, see Public-key certiﬁcate

reverse, 575

revocation, 566, 576–577

RFC 1422, 655

secret-key, see Secret-key certiﬁcate

symmetric-key, see Symmetric-key certiﬁcate

X.509 standard, 660

Certiﬁcate of primality, 166

Certiﬁcate revocation list (CRL), 576–577

Certiﬁcation, 3

path, 572

policy, 576

topology, 572

Certiﬁcation authority (CA), 491, 548, 556, 559

Certiﬁcational attack, 236

Certiﬁcational weakness, 285

CFB, see Cipher feedback mode

CFB-64 MAC, 650

Challenge, 397, 409

Challenge-response identiﬁcation, 397–405, 420–

421

public-key, 403–405

ISO/IEC 9798-3, 404–405

modiﬁed Needham-Schroeder, 404

X.509, 404

symmetric-key, 400–403

ISO/IEC 9798-2, 401–402

SKID2, 402

SKID3, 402

Channel, 13

physically secure, 13

secure, 13

secured, 13

unsecured, 13

Characteristic of a ﬁeld, 77

CA, see Certiﬁcation authority (CA)

CA-certiﬁcate, 572

Caesar cipher, 239

CALEA, 590

Capability (access control), 570

Capstone chip, 589

Cardinality of a set, 49

Carmichael number, 137

Carry-save adder, 630

Cartesian product, 49

Cascade cipher, 234, 237

Cascade generator

m -sequence, 221

p -cycle, 220

Cascading hash functions, 334

CAST block cipher, 281

patent, 659

CBC, see Cipher-block chaining mode

1997 by CRC Press, Inc. — See accompanying notice at front of chapter.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: