Handbook of Applied Cryptography


: Overview of CryptographyIntroductionInformation security and cryptographyBackground on functionsFunctions (1-1, one-way, trapdoor one-way)PermutationsInvolutionsBasic terminology and conceptsSymmetric-key encryptionOverview of block ciphers and stream ciphersSubstitution ciphers and transposition ciphersComposition of ciphersStream ciphersThe key spaceDigital signaturesAuthentication and identificationIdentificationData origin authenticationPublic-key cryptographyPublic-key encryptionThe necessity of authentication in public-key systemsDigital signatures from reversible public-key encryptionSymmetric-key vs. public-key cryptographyHash functionsProtocols and mechanismsKey establishment, management, and certificationKey management through symmetric-key techniquesKey management through public-key techniquesTrusted third parties and public-key certificatesPseudorandom numbers and sequencesClasses of attacks and security modelsAttacks on encryption schemesAttacks on protocolsModels for evaluating securityPerspective for computational securityNotes and further references: Mathematical BackgroundProbability theoryBasic definitionsConditional probabilityRandom variablesBinomial distributionBirthday problemsRandom mappingsInformation theoryEntropyMutual informationComplexity theoryBasic definitionsAsymptotic notationComplexity classesRandomized algorithmsNumber theoryThe integersAlgorithms in ZThe integers modulo nAlgorithms in ZnThe Legendre and Jacobi symbolsBlum integersAbstract algebraGroupsRingsFieldsPolynomial ringsVector spacesFinite fieldsBasic propertiesThe Euclidean algorithm for polynomialsArithmetic of polynomialsNotes and further references: Number-Theoretic Reference ProblemsIntroduction and overviewThe integer factorization problemTrial divisionPollard’s rho factoring algorithmPollard’s p − 1 factoring algorithmElliptic curve factoringRandom square factoring methodsQuadratic sieve factoringNumber field sieve factoringThe RSA problemThe quadratic residuosity problemComputing square roots in ZnCase (i): n primeCase (ii): n compositeThe discrete logarithm problemExhaustive searchBaby-step giant-step algorithmPollard’s rho algorithm for logarithmsPohlig-Hellman algorithmIndex-calculus algorithmDiscrete logarithm problem in subgroups of Z*pThe Diffie-Hellman problemComposite moduliComputing individual bitsThe discrete logarithm problem in Z*p — individual bitsThe RSA problem — individual bitsThe Rabin problem — individual bitsThe subset sum problemSolving subset sum problems of low densitySimultaneous diophantine approximationFactoring polynomials over finite fieldsSquare-free factorizationBerlekamp’s Q-matrix algorithmNotes and further references: Public-Key ParametersIntroductionApproaches to generating large prime numbersDistribution of prime numbersProbabilistic primality testsFermat’s testSolovay-Strassen testMiller-Rabin testComparison: Fermat, Solovay-Strassen, and Miller-Rabin(True) Primality testsTesting Mersenne numbersPrimality testing using the factorization of n – 1Jacobi sum testTests using elliptic curvesPrime number generationRandom search for probable primesStrong primesNIST method for generating DSA primesConstructive techniques for provable primesIrreducible polynomials over ZpIrreducible polynomialsIrreducible trinomialsPrimitive polynomialsGenerators and elements of high orderSelecting a prime p and generator of Z*pNotes and further references: Pseudorandom Bits and SequencesIntroductionBackground and ClassificationRandom bit generationPseudorandom bit generationANSI X9.17 generatorFIPS 186 generatorStatistical testsThe normal and chi-square distributionsHypothesis testingGolomb’s randomness postulatesFive basic testsMaurer’s universal statistical testCryptographically secure pseudorandom bit generationRSA pseudorandom bit generatorBlum-Blum-Shub pseudorandom bit generatorNotes and further references: Stream CiphersIntroductionClassificationFeedback shift registersLinear feedback shift registersLinear complexityBerlekamp-Massey algorithmNonlinear feedback shift registersStream ciphers based on LFSRsNonlinear combination generatorsNonlinear filter generatorsClock-controlled generatorsOther stream ciphersSEALNotes and further references: Block CiphersIntroduction and overviewBackground and general conceptsIntroduction to block ciphersModes of operationExhaustive key search and multiple encryptionClassical ciphers and historical developmentTransposition ciphers (background)Substitution ciphers (background)Polyalphabetic substitutions and Vigen`ere ciphers (historical)Polyalphabetic cipher machines and rotors (historical)Cryptanalysis of classical ciphers (historical)DESProduct ciphers and Feistel ciphersDES algorithmDES properties and strengthFEALIDEASAFER, RC5, and other block ciphersSAFERRC5Other block ciphersNotes and further references: Public-Key EncryptionIntroductionBasic principlesRSA public-key encryptionDescriptionSecurity of RSARSA encryption in practiceRabin public-key encryptionElGamal public-key encryptionBasic ElGamal encryptionGeneralized ElGamal encryptionMcEliece public-key encryptionKnapsack public-key encryptionMerkle-Hellman knapsack encryptionChor-Rivest knapsack encryptionProbabilistic public-key encryptionGoldwasser-Micali probabilistic encryptionBlum-Goldwasser probabilistic encryptionPlaintext-aware encryptionNotes and further references: Hash Functions and Data IntegrityIntroductionClassification and frameworkGeneral classificationBasic properties and definitionsHash properties required for specific applicationsOne-way functions and compression functionsRelationships between propertiesOther hash function properties and applicationsBasic constructions and general resultsGeneral model for iterated hash functionsGeneral constructions and extensionsFormatting and initialization detailsSecurity objectives and basic attacksBitsizes required for practical securityUnkeyed hash functions (MDCs)Hash functions based on block ciphersCustomized hash functions based on MD4Hash functions based on modular arithmeticKeyed hash functions (MACs)MACs based on block ciphersConstructing MACs from MDCsCustomized MACsMACs for stream ciphersData integrity and message authenticationBackground and definitionsNon-malicious vs. malicious threats to data integrityData integrity using a MAC aloneData integrity using an MDC and an authentic channelData integrity combined with encryptionAdvanced attacks on hash functionsBirthday attacksPseudo-collisions and compression function attacksChaining attacksAttacks based on properties of underlying cipherNotes and further references: Identification and Entity AuthenticationIntroductionIdentification objectives and applicationsProperties of identification protocolsPasswords (weak authentication)Fixed password schemes: techniquesFixed password schemes: attacksCase study – UNIX passwordsPINs and passkeysOne-time passwords (towards strong authentication)Challenge-response identification (strong authentication)Background on time-variant parametersChallenge-response by symmetric-key techniquesChallenge-response by public-key techniquesCustomized and zero-knowledge identification protocolsOverview of zero-knowledge conceptsFeige-Fiat-Shamir identification protocolGQ identification protocolSchnorr identification protocolComparison: Fiat-Shamir, GQ, and SchnorrAttacks on identification protocolsNotes and further references: Digital SignaturesIntroductionA framework for digital signature mechanismsBasic definitionsDigital signature schemes with appendixDigital signature schemes with message recoveryTypes of attacks on signature schemesRSA and related signature schemesThe RSA signature schemePossible attacks on RSA signaturesRSA signatures in practiceThe Rabin public-key signature schemeISO/IEC 9796 formattingPKCS #1 formattingFiat-Shamir signature schemesFeige-Fiat-Shamir signature schemeGQ signature schemeThe DSA and related signature schemesThe Digital Signature Algorithm (DSA)The ElGamal signature schemeThe Schnorr signature schemeThe ElGamal signature scheme with message recoveryOne-time digital signaturesThe Rabin one-time signature schemeThe Merkle one-time signature schemeAuthentication trees and one-time signaturesThe GMR one-time signature schemeOther signature schemesArbitrated digital signaturesESIGNSignatures with additional functionalityBlind signature schemesUndeniable signature schemesFail-stop signature schemesNotes and further references: Key Establishment ProtocolsIntroductionClassification and frameworkGeneral classification and fundamental conceptsObjectives and propertiesAssumptions and adversaries in key establishment protocolsKey transport based on symmetric encryptionSymmetric key transport and derivation without a serverKerberos and related server-based protocolsKey agreement based on symmetric techniquesKey transport based on public-key encryptionKey transport using PK encryption without signaturesProtocols combining PK encryption and signaturesHybrid key transport protocols using PK encryptionKey agreement based on asymmetric techniquesDiffie-Hellman and related key agreement protocolsImplicitly-certified public keysDiffie-Hellman protocols using implicitly-certified keysSecret sharingSimple shared control schemesThreshold schemesGeneralized secret sharingConference keyingAnalysis of key establishment protocolsAttack strategies and classic protocol flawsAnalysis objectives and methodsNotes and further references: Key Management TechniquesIntroductionBackground and basic conceptsClassifying keys by algorithm type and intended useKey management objectives, threats, and policySimple key establishment modelsRoles of third partiesTradeoffs among key establishment protocolsTechniques for distributing confidential keysKey layering and cryptoperiodsKey translation centers and symmetric-key certificatesTechniques for distributing public keysAuthentication treesPublic-key certificatesIdentity-based systemsImplicitly-certified public keysComparison of techniques for distributing public keysTechniques for controlling key usageKey separation and constraints on key usageTechniques for controlling use of symmetric keysKey management involving multiple domainsTrust between two domainsTrust models involving multiple certification authoritiesCertificate distribution and revocationKey life cycle issuesLifetime protection requirementsKey management life cycleAdvanced trusted third party servicesTrusted timestamping serviceNon-repudiation and notarization of digital signaturesKey escrowNotes and further references: Efficient ImplementationIntroductionMultiple-precision integer arithmeticRadix representationAddition and subtractionMultiplicationSquaringDivisionMultiple-precision modular arithmeticClassical modular multiplicationMontgomery reductionBarrett reductionReduction methods for moduli of special formGreatest common divisor algorithmsBinary gcd algorithmLehmer’s gcd algorithmBinary extended gcd algorithmChinese remainder theorem for integersResidue number systemsGarner’s algorithmExponentiationTechniques for general exponentiationFixed-exponent exponentiation algorithmsFixed-base exponentiation algorithmsExponent recodingSigned-digit representationString-replacement representationNotes and further references: Patents and StandardsIntroductionPatents on cryptographic techniquesFive fundamental patentsTen prominent patentsTen selected patentsOrdering and acquiring patentsCryptographic standardsInternational standards – cryptographic techniquesBanking security standards (ANSI, ISO)International security architectures and frameworksU.S. government standards (FIPS)Internet standards and RFCsDe facto standardsOrdering and acquiring standardsNotes and further referencesA: Bibliography of Papers from Selected Cryptographic ForumsA.1 Asiacrypt/Auscrypt ProceedingsA.2 Crypto ProceedingsA.3 Eurocrypt ProceedingsA.4 Fast Software Encryption ProceedingsA.5 Journal of Cryptology papersIndex
 
Next >