The following outline contains my notes taken while reading Bruce Schneiers book on Applied Cryptography. They are meant only to give a brief overview of each section. (JLD 12/2002)
1. Chapter 1 Foundations
1.1.
Terminology Discussion of different terms
1.2.
Classical
Cryptography
1.2.1.
Substitution
Ciphers and Transposition Ciphers Substitution is when each character in
plaintext is substituted for another in the ciphertext. Transposition is when
the characters remain but the order is shuffled.
1.2.2.
Computer
Algorithms Three most popular are RSA, DES and DSA.
1.2.3.
Simple XOR
Very simple method of encrypting.
1.2.4.
One Time Pads
A large non-repeating set of truly random key letters that are used only one
time.
1.3.
Large Numbers Encryption traditionally uses large
numbers.
2. Chapter 2 Protocol Building Blocks
2.1.
Introduction to
Protocols A protocol is a series
of steps involving two or more parties. Further discussion of cryptography,
purpose, arbitration, adjudication, self-enforcing and attacks against
protocols is given.
2.2.
Communications
Using Symmetric Cryptography Uses
the same key to both encrypt and decrypt. Since the key must be kept secret, an
adversary can decrypt all messages if the key is compromised. Also keys must be
distributed in secret.
2.3.
One-Way
Functions A function that is
relatively easy to compute but significantly harder to reverse. They are a
fundamental building block for many cryptographic protocols.
2.4.
One-Way Hash
Functions Takes an input string
and converts it to a fixed size output string.
2.5.
Communications
Using Public-Key Cryptography
Anyone with a public key can encrypt a message but not decrypt it. Only a
person with the private key can do that.
2.6.
Digital
Signatures Much like handwritten
signatures, they provide proof of ownership. Further discussion of signing
documents with Symmetric Cryptosystems, with Public Key Cryptography, with
Timestamps and with One way hash functions is also given.
2.7.
Digital
Signatures with Encryption By
combining the two, we can gain the security of encryption with the authenticity
of digital signatures.
2.8.
Random and
Pseudo-Random Sequence Generation
Cryptography is extremely sensitive to the properties of random number
generators.
2.8.1.
Pseudo Random
Sequences A sequence is considered if it can pass all the statistical tests
of randomness we can find.
2.8.2.
Cryptographically
Secure Pseudo Random Sequences These sequences need to computationally
unfeasible to predict what the next random bit will be.
2.8.3.
Real Random
Sequences The generator never produces the same sequence twice.
3. Chapter 3 Basic Protocols
3.1.
Key Exchange A common cryptographic technique is to
encrypt each individual conversation between two people with a separate key.
Further discussion of Key exchange with Public Keys (with or without a
database) and digital signatures, Man in the middle attack, Interlock protocol,
and Key/Message Transmission and Broadcast are also given.
3.2.
Authentication
Determining someone is who they say
they are. Further discussions of Dictionary Attacks, User ID with public key
crypto, Mutual auth. using the interlock protocol and SKID are also given.
3.3.
Authentication
and Key Exchange When two
entities want to exchange a secret key and at the same time, how do they know
they are talking to the right party. Further discussion of the Wide mouth frog,
Yahalom, Needham/Schroeder, Otway/Rees
Kerberos, SPX, and other protocols are also given.
3.4.
Multiple-Key
Public-Key Cryptography Having
more keys than just Public and Private keys. Can be helpful when broadcasting a
key to multiple people in the field.
3.5.
Secret Splitting
Ways of taking a message and
dividing it up into sections so that each piece by itself means nothing.
Altogether, however, they reconstruct the message.
3.6.
Secret Sharing -
Ways of taking a message and
dividing it up into sections so that each piece by itself means nothing. A
certain number of shadows can be used to reconstruct the message. There are
ways the cheat this scheme.
3.7.
Cryptographic
Protection of Databases Encrypting
a database in a way such that it is easy to extract a small piece of
information (ex. a persons address) and difficult to extract the entire
database (ex. everyones address)
3.8.
Timestamping
Services Deals with situations
where the date of something may need to be verified (ex. a copyright). This can
be overcome with a timestamp. Further discussion of an arbitrated solution, a
linking protocol and a distributed protocol are also given.
4. Chapter 4 Intermediate Protocols
4.1.
Subliminal
Channel Creating a covert
communications channel between two entities even in full view of others with
unencrypted messages (ex. number of words in a sentence). Further discussion of
Applications and Subliminal-free signatures is also given.
4.2.
Undeniable
Digital Signatures A signature
that depends on the signers document and the signers private key, and cant
be verified without the signers consent.
4.3.
Fail-Stop
Digital Signatures Since there
are many possible private keys that will work with a private key, only the correct
private key will produce a certain signature.
4.4.
Group Signatures
Only group members can sign.
Receiver can verify if it is valid. Signature can be opened to reveal the
signer. Can also be used with a trusted arbitrator.
4.5.
Computing with
Encrypted Data Deals with issues
related to the problem of computing f(x) without telling someone what x is.
4.6.
Bit Commitment
Deals with issues related to
committing to a prediction but not wanting to reveal the prediction until a
later date. Further discussion of bit commitment using symmetric crypto, one
way functions and pseudo-random sequence generators is also give.
4.7.
Fair Coin Flips
Discussion of flipping a coin
over a communication channel by committing to a random bit. Further discussion
of coin flips using one way functions, public key cryptography, flipping into a
well and using coin flipping to generate keys is also given.
4.8.
Mental Poker Similar to coin flipping protocol but instead
multiple messages are generated. Further discussion of mental poker with three
players, attacks against poker protocols and anonymous key distribution is also
given.
5. Chapter 5 Advanced Protocols
5.1.
Fair
Cryptosystems For this the
private key is broken up into pieces and distributed to different authorities.
These authorities can reconstruct the key if needed.
5.2.
All-or-Nothing
Disclosure of Secrets Example of
Bob obtaining secrets from Alice but not wanting to tell her which secrets he
wants. Once he has gained information about one secret, then he can no longer
gain access to information about any other secrets.
5.3.
Zero-Knowledge
Proofs of Knowledge One party
proving to another they have knowledge of a secret without revealing to secret
itself. Further discussion of basic zero knowledge protocols, Hamiltonian
cycles, Graph isomorphisms, Parallel zero knowledge proofs, Convincing a third
party, Noninteractive zero knowledge proofs, and Generalities is also discussed.
5.4.
Zero-Knowledge
Proofs of Identity In the real
world, we use physical tokens as proof of identity. A private key can be used
as a token of identity. Further discussion of the grandmaster problem and the
Shifting identities problem is also provided.
5.5.
Blind Signatures
There are times when we want
someone to sign a document without seeing its contents. Further discussion of
completely and partially blind signatures and envelopes is also provided.
6. Chapter 6 Esoteric Protocols
6.1. Oblivious Transfer Alice knows the factor of on of the numbers. She wants to sell it to Bob. He needs proof.
6.2. Simultaneous Contract Signing - Alice and Bob want to enter into a contract but neither wants to sign unless the other signs as well.
6.2.1. Contract signing with an Arbitrator They can use an arbitrator (Trent)
6.2.2. Simultaneous Contract Signing without an Arbitrator (face to face) Alice signs a letter of her name, Bob signs a letter of his name (and so on).
6.2.3. Simultaneous Contract Signing without an Arbitrator (not face to face) Alice and Bob take baby steps toward a signed contract until both have signed. Use probabilities.
6.2.4. Simultaneous Contract Signing without an Arbitrator (using cryptography) Same as above using DES for protocol
6.3. Digital Certified Mail Simultaneous oblivious transfer protocol used for contract signing can be modified for computer certified mail. For this, DES is used.
6.4. Simultaneous Exchange of Secrets Previous two protocols are implementations of a more general protocol one that lets two people exchange secrets simultaneously.
6.5. Secure Elections Need a protocol that prevents cheating and maintains individual privacy. Possible solutions include the following:
6.5.1. Simplistic Voting Protocol #1 Voters use public key to encrypt vote.
6.5.2. Simplistic Voting Protocol #2 CTF (Central Tabulating Facility) knows who voted for whom.
6.5.3. Voting with Blind Signatures Dissociates the vote from voter.
6.5.4. Voting with Two Central Facilities Divide the power of the CTF between two parties. Uses CLA (Central Legitimization Agency)
6.5.5. Voting with a Single Central Facility CLA and CTF are one organization to overcome possibility of collusion. Uses ANDOS for key distribution.
6.5.6. Improved Voting with a Single Central Facility Uses ANDOS as well.
6.5.7. Voting without a Central Tabulating Facility Self adjudicating but too impractical to use.
6.5.8. Other Voting Schemes Others beyond the scope of this book.
6.6. Secure Multiparty Computation A protocol in which a group of people can get together and compute a function of each of their inputs in a special way.
6.6.1. Protocol #1 Example of a group calculating average salary without giving away individual salaries.
6.6.2. Protocol #2 Example of two people wanting to determine which person is older.
6.6.3. Protocol #3 Example of a private dating service.
6.6.4. Protocol #4 Example of a voting process with Super Votes
6.6.5. Secure Circuit Evaluation Inputs a and b. Want to securely compute f(a,b).
6.7. Digital Cash For people who need to exchange money without a trace.
6.7.1. Protocol #1 Simplified physical protocol for anonymous money orders.
6.7.2. Protocol #2 To prevent using a photocopied money order twice.
6.7.3. Protocol #3 Identifies the person cheating
6.7.4. Protocol #4 Also identifies the person cheating using secret splitting. Prevents collusion between person and bank as well.
6.7.5. Other Digital Cash Protocols Ideal cash system requires : Independence, Security, Privacy, Off Line Payment, Transferability and Divisibility
6.7.6. Digital Cash and the Perfect Crime Example of kidnapping and money orders
6.8. Anonymous Message Broadcast Example of Cryptographers anonymously paying a dinner bill. Unconditional Sender and Recipient Untraceability. Multiparty Unconditional Secure Protocols.
7. Chapter 7 Keys
7.1. Key Length The Security of a symmetric cryptosystem is a function of two things : the strength of the algorithm and the length of the key. The security of a cryptosystem should rest in the key, not in the details of the algorithm.
7.1.1. Time and Cost Estimates for Brute-Force Attack There is no better way to break a cryptosystem than to try every possible key (brute-force attack). This is the most efficient attack possible. A large number of special processors could crack a key given a reasonable amount of time. It seems prudent to try to estimate the value of a key (i.e. how much value can be trusted to a single key before it makes economic sense to try to break
7.1.2. Software Crackers Software is so slow that economic brute-force attacks will not be unfeasible for years to come. The real threat of software-based brute-force attacks is that its essentially free (no setup cost involved). A software crack is based on sheer luck.
7.1.3. Viruses Idea of a virus that does brute-force cryptanalysis during machine idle time.
7.1.4. The Chinese Lottery High speed cracking chip is installed into every TV and radio. When govt. wants to break a key, it broadcasts the data. Eventually the correct will appear on someones screen in the country.
7.1.5. Biotechnology Using biochips or genetically engineered cryptanalytic algae. Nonsense.
7.1.6. How Long Should a key be How long does your data need to be secure?
7.2. Key Management Key management is the hardest security problem. Designing secure cryptographic algorithms and protocols isnt easy, but making sure keys stay secret is even harder.
7.2.1. Generating Keys If you are using a cryptographically weak process to generate your keys, then your whole system is weak. Dont reduce your keyspaces (ex. Allow only lower case). Choose good keys (ex. Not words/names). Generate good keys or use X9.17 key generation.
7.2.2. Transferring Keys Method for sending keys securely from one person to another. It uses a master key and a daily key scheme. In large networks, create a central key server.
7.2.3. Verifying Keys Key verification ultimately relies on trust of the user. It is also important to use error detection/correction in case the key gets garbled.
7.2.4. Using Keys In a preemptive multitasking computer environment, you should set your encryption operation with a high enough priority that it will not be interrupted (i.e. swapped out to disk). Hardware implementations are easier.
7.2.5. Storing Keys Keys can be stored in a ROM key or magnetic strip card.
7.2.6. Backup Keys In order to backup keys, they should be divided and sent to multiple people.
7.2.7. Compromised Keys Protect private keys in a system above all else. They are more permanent.
7.2.8. Lifetime of Keys No encryption key should be used for an indefinite period. Session keys should be replaced daily. Private keys have varying lifetimes but should be changed at least every few years.
7.2.9. Destroying Keys Old keys have value since someone can read old encrypted messages with them. Keys must be destroyed securely.
7.3. Public Key Management Public key cryptography has its own unique set of problems (see section 2.5). Using Public key certificates (certs) or Distributed Key Management (ex. PGP) can help alleviate problems.
8. Using Algorithms
8.1.
Block Cipher
Modes Operate on blocks of plaintext and ciphertext
8.1.1. Electronic Codebook (ECB) Mode The most obvious way to use a block cipher is to encrypt each block of plaintext into a block of ciphertext. Typical block size is 64 bits.
8.1.2. Block Replay Intercepting messages between two parties and substituting some desired data by a third party. Example of Mallet and two banks.
8.1.3. Cipher Block Chaining (CBC) Mode The results of encryption of previous blocks are fed back into the encryption of the current block. Each block depends on all the previous blocks.
8.1.4. Cipher Feedback (CFB) Mode With CBC, encryption cannot begin until a complete has been received. For this mode, data is encrypted in units smaller than the block size.
8.1.5. Output Feedback (OFB) Mode Similar to CFB except part of the previous output block is moved into the right-most positions of the queue.
8.1.6. Counter Mode Similar to OFB except the input to the register is a counter.
8.1.7. Other Modes Discussions of Block Chaining (BC), and Propagating Cipher Block (PCBC) as well as others.
8.1.8. Choosing a Cipher Mode ECB is simplest and fastest (also the weakest though). Use CBC, CFB or OFB.
8.2. Multiple Encryption When you encrypt the same plaintext block multiple times.
8.2.1. Double Encryption Encrypting a block twice with different keys.
8.2.2. Triple Encryption Encrypting three times with two different keys.
8.2.3. Triple Encryption with Padding Text is padded with a string of random bits between the encryptions.
8.2.4. Doubling the Block Length You can double the blocking length and use multiple encryptions.
8.2.5. Multiple Encryption with Multiple Algorithms There may be subtle interactions between algorithms that may decrease security.
8.3. Stream Ciphers Algorithms that convert plaintext to ciphertext one bit at a time (using a keystream generator).
8.3.1. Synchronous Stream Ciphers The keystream is generated independent of the message stream.
8.3.2. Self-Synchronous Stream Ciphers Each keystream bit is a function of a fixed number of previous ciphertext bits. Commonly operate in cipher-feedback mode.
8.3.3. Using Block Ciphers as Stream Ciphers Block algorithms can be used as key stream generators.
8.4. Stream Ciphers vs. Block Ciphers Stream Cipher : suitable for software, easier to analyze, smaller error propagation. Block Cipher : easy to implement in software, more general, small errors can cause big problems.
8.5. Public-Key Cryptography vs. Symmetric Cryptography Public Key : good for key distribution and providing authentication. Symmetric : very fast, good for encrypting files and communication channels. They work best together.
8.6. Encrypting Communications Networks Encryption can take place at any layer in the OSI model. It can be done at the physical layer (link-by-link encryption) or between the network and transport layers (end-to-end encryption). The two may also be combined.
8.7. Encrypting Data for Storage Encrypting data for storage is a different issue from encrypting for communication. The issue becomes how long the data is valuable for.
8.8. Hardware Encryption vs. Software Encryption Hardware is still the mode of choice for most commercial and military applications. Common reasons include speed, security and ease of installation. Software solutions are flexible and portable.
8.9. File Erasure To erase a computer file, you must physically write over all the files bits on the disk.
8.10. Choosing an Algorithm Alternatives : use published algorithm (preferred), trust a manufacturer, trust private consultant, trust the government or write your own.
9. Mathematical Background
9.1. Information Theory Defines the amount of information in a message as the minimum number of bits needed to encode all possible meanings of that message (ex. Days of the week need 3 bits). Concepts of Entropy, Rate of Language, Unicity, Confusion and Diffusion discussed.
9.2. Complexity Theory Compares cryptographic algorithms/techniques and determines their security. Order of magnitude (O(n)) is just the term of the function that grows the fastest as n gets larger. Example if the complexity of an algorithm is 4n^2 + 7n + 12, the order of magnitude is on the order of n^2 (O(n^2)). Includes discussion of Complexity of Algorithms, Complexity of Problems and NP-Complete Problems.
9.3. Number Theory Includes discussion of Modular Arithmetic, Prime Numbers, GCD, Inverse Modulo, Solving for Coefficients, Fermats Little Theorem, Eulers Totient Function, Chinese Remainder Theorem, Quadratic Residues, Legendre Symbols, Jacobi Symbols, Blum Integers, Generators, and Galois Fields.
9.4. Factoring Factoring means finding its prime factors. Includes discussion of Quadratic Sieve, Number Field Sieve, Elliptic Curve Method, Monte Carlo Algorithm, Continued Fraction Algorithm, Trail Division and Square Roots Mod-N.
9.5. Prime Number Generation Public key cryptography uses prime numbers. Includes discussion of Solovay, Rabin and Lehmann algorithms as well as strong primes.
9.6. Discrete Logarithms in an Finite Field The inverse problem of modular exponentiation (a one way function used in cryptography) is finding the discrete logarithm. Three methods for computing linear sieve, Guassian integer scheme and the number field sieve.
10. Data Encryption Standard (DES)
10.1. DES A block cipher that encrypts data in 64 bit blocks. 64 bit plaintext in, 64 bit cyphertext comes out. Also discussed are Development of the standard, Adoption of the standard, Validation, 5 year reviews, Overview and Outline of algorithm, Permutations and transformations, Modes, Hardware vs. Software, Security, Keys, Iterations, and Differential/Related Key/Linear Cryptanalysis.
10.2. DES Variants There are other DES protocols. Includes discussion on Multiple DES, Independent Subkeys, Alternate and Variable S-Boxes, Crypt(3) and Generalized DES (GDES).
11. Other Block Algorithms
11.1. Lucifer Block algorithm designed by IBM in the 1970s. DES was based on this algorithm.
11.2. Madryga Block algorithm where all operations work on 8-bit chucks of data (i.e. bytes).
11.3. NewDES Designed as a possible DES replacement. Operates on 64 bits of plaintext but uses a 120 bit key.
11.4. Feel-N Similar to DES but uses 64 bit blocks and 64 bit keys.
11.5. Redoc Has 80 bit block and 160 bit key. All operations are performed on bytes. Includes Redoc II and Redoc III.
11.6. Loki Australian alternative to DES. Uses 64 bit blocks and 64 bit keys. Includes Loki89 and Loki91.
11.7. Khufu and Khafre (named after two Egyptian pharaohs) Proposed as a DES replacement. Khufu uses 64 bit blocks and 512 bit keys. Its S-boxes are generated. Khafre is similar to the other algorithm except is uses a standard set of S-boxes (thus requiring no precomputation time).
11.8. RC2 and RC4 Variable key size block ciphers that were meant to replace DES. Both are proprietary.
11.9. Idea International Data Encryption Algorithm is a block cipher operating on 64-bit blocks. The key in 128 bits
11.10. MMB (Modular Multiplication Block cipher) Based on the same idea as Idea (mixing operations of different algebraic groups). Has 128 bit block size and 128 bit key.
11.11. CA-1.1 A block cipher built on cellular automata. Encodes 384 bit plaintext and uses 1088 bit keys. Uses authentication.
11.12. Skipjack NSA Developed Algorithm for the clipper and capstone chips. Classified as Secret. Symmetric and uses an 80 bit key.
11.13. Using one-way hash functions Discussion of Karn, Luby-Rackoff and MDC are included.
11.14. Other Block Algorithms There are many more block algorithms available. Some of them are proprietary.
11.15. Which block algorithm is best DES is still secure. For a more secure algorithm, use Triple-DES. IDEA is also recommended.
12. Public-Key Algorithms
12.1. Background Invented by Diffie and Hellman. Only two algorithms are suitable for encryption and digital signatures: RSA and EkGanal. Susceptible to chosen ciphertext attacks.
12.2. Diffie-Hellman First public key algorithm invented. Can be used for key distribution, not for encrypting and decrypting. Can be used with three or more parties also
12.3. Knapsack Algorithms Algorithm for generalized public key encryption. Based knapsack problem (items with different weights in a knapsack).
12.4. RSA Named after Rivest, Shamir and Aldeman. Gets its security from the difficulty of factoring large numbers. Much slower than DES.
12.5. Pohlig-Hellman Similar to RSA (non-symmetric). Encryption and Decryption keys must be kept secret. Does not use large prime numbers.
12.6. Rabin Gets its security from the difficulty of finding square roots modulo a composite. Decryption produces 4 results (1 of which is the correct one). Must be determined by context. Attempts were made to eliminate shortcomings.
12.7. Feige-Fiat-Shamir Uses an arbitrator who generates a modulus (the product of two large primes). Uses quadratic residue. Identification protocol is single accreditation.
13. More Public-Key Algorithms
13.1. Guillou-Quisquarter zero-knowledge identification algorithm suited applications in the real world (ex. Smart cards)
13.2. Ong-Schnorr-Shamir A class of signature schemes using polynomials modulo n.
13.3. ElGamal Variant of Rabin. Can be sued for both digital signatures and encryption. Security based on calculating discrete logarithms.
13.4. Schnorr This authentication and signature scheme combines ideas from ElGamal, Fiat-Shamir and an interactive protocol. . Security based on calculating discrete logarithms.
13.5. Digital Signature Algorithm (DSA) Used for DSS (Digital Signature Standard). DSA is the algorithm and DSS is the standard. It is a variant of the Schnorr and ElGamal signature algorithms. It also makes use of a one way hash. Precomputation can be used.
13.6. Ensign Digital Signature Scheme. Uses large prime numbers for keys. Precomputation can be used.
13.7. McEliece Public key cryptosystem based on algebraic coding theory. Makes use of error correcting codes called Goppa codes.
13.8. Okamoto 92 Signature scheme that gets its security from discrete logarithms.
13.9. Cellular Automata Could possibly be used in Public Key Cryptosystems. CA have the property they it is impossible to calculate the predecessor of an arbitrary state by reversing the rule for finding the successor.
13.10. Elliptic Curve Cryptosystems Implemented using existing public key algorithms in elliptic curves over finite fields.
13.11. Other Public Key Algorithms Many other algorithms have been proposed and broken over the years. Most are based on different mathematical tools. Most public key algorithms are based on one of three problems : napsack problem, discrete logarithm and factoring. Strength of the algorithm depends more on the computational complexity of the problem upon which it is based.
13.12. Which Public Key Algorithm is best RSA is easiest to implement> ElGamal works well for encryption and DSA works well for signatures. Diffie-Hellman is the easiest for key-exchange.
14. One-way Hash Functions
14.1. Background One way hash functions operate on an arbitrary length and returns a fixed length hash value. Also given are discussions of Birthday attacks, Length of one way functions and an overview of one way functions.
14.2. Snerfru Hashes arbitrary length messages into 128 or 256 bit values.
14.3. N-Hash Uses 128 bit message blocks and produces 128 bit hash values.
14.4. MD4 (MD = Message Digest (i.e. a hash)). Developed by Rivest. Produces 128 bit hash values.
14.5. MD5 Improved version of MD4. Similar in design. Also produces 128 bit hash values.
14.6. MD2 Similar to MD4/5 structures. Slower and less secure.
14.7. Secure Hash Algorithm (SHA) Takes a message of any length and produces a 160 bit output (which is longer than any other hash). Very similar to MD4.
14.8. RIPE-MD Developed for European RACE project. MD4 variant.
14.9. HAVAL Modification of MD5 (faster than MD5). Produces variable length hash values.
14.10. Other One Way Hash Functions Discussion of various hash functions.
14.11. Using Symmetric Block Algorithms It is possible to use a symmetric block cipher algorithm as a one way hash. Discussion of various methods using ciphers to produce hash values.
14.12. Using Public Key Algorithms It is possible to use a public key algorithm in block chaining mode as a digital signature. This solution would be slow however.
14.13. Which One Way Hash is best SHA recommended.
14.14. Key Dependent One Way Hash Functions Often called a MAC (Message Authentication Code). Have same properties as one way hash functions but they also include a key. Further discussion of Block Cipher MACs, One way hash function MACs and Stream Cipher MACs.
15. Random Sequence Generators and Stream
Ciphers
15.1. Pseudo-Random Sequence Generators Further discussion of Linear Congruential Generators, Combining of Linear Congruential Generators, Linear Feedback Shift Registers and Modified LFSRs is provided.
15.2. Stream Ciphers There are four practical approaches to constructing secure pseudo-random sequence generators : Information-theoretic, System-theoretic, Complexity-theoretic and Randomized-theoretic.
15.3. Real Random Sequence Generators A random sequence generators sequences cannot be reproduced by anyone. Discussion of RAND tables, Using the computers clock, Measuring keyboard latency, Using random noise, Biases and correlations and Diffusing randomness with a one way hash are also given.
15.4. Generating Numbers and Non-uniform Distributions - To be used if your needs for pseudo-random or random numbers are more complicated.
15.5. Generating Random Permutations - Using a random number generator to create a random permutation generator is sometimes called shuffling.
16. Special Algorithms for Protocols
16.1. Key Exchange Discussion of Shamirs three-pass protocol (enables two people to communicate securely without any advance exchange of their secret keys) and COMSET (allows two people to identify themselves and exchange a secret key by first using a public key) are given.
16.2. Encrypted Key Exchange Provides security and authentication by using both symmetric and public-key cryptography. A shared secret key is used to encrypt a randomly generated public key. Further discussion of The Basic Protocol, Implementing EKE with RSA, ElGamal, and Diffie-Hellman, Strengthening EKE and Applications of EKE are given.
16.3. Multiple-Key Public-Key Cryptography A generalization of RSA using multiple keys.
16.4. Secret Broadcasting Discussion of three ways to broadcast a message where a select set of listeners are able to decode it.
16.5. Secret Sharing Algorithms Also called a threshold scheme. A message is divided into n pieces (shadows) where m shadows can be used to reconstruct the message. Further discussion of the Lagrange interpolating polynomial scheme, the Vector scheme, the Asmuth-Bloom scheme, the Karnin Greene Hellman scheme, the Advanced Threshold schemes, Sharing a secret without revealing the shares, Sharing a secret with cheaters and Secret sharing schemes with prevention are also given.
16.6. Subliminal Channel Sending a subliminal message by means of an innocuous message. Further discussion of the Ong-Schnorr-Shamir scheme, the ElGamal scheme, the ESIGN scheme, the DSA scheme and other schemes is also provided. In fact, any digital signature scheme can be converted into a subliminal channel.
16.7. Undeniable Digital Signatures A protocol that provides confirmation that a signature is valid as well as a disavowal protocol (using a zero knowledge interactive protocol). Sometimes they can be converted to a conventional digital signature as well.
16.8. Computing with Encrypted Data Discussion of the discrete logarithm problem (factoring a large prime number).
16.9. Fair Coin Flips Example where Person A knows the outcome first and Person B can verify it later. Further discussion of coin flipping using square roots, Exponentiation Modulo p and Blum integers is also given.
16.10. Fair Cryptosystems Uses a KDC to reconstruct a private key if needed (using Diffie-Hellman)
16.11. All-or-nothing Disclosure of Secrets Allows multiple parties to obtain/buy individual secrets from a provider/seller.
16.12. Zero Knowledge Proofs of Knowledge Proving to someone you know a value without actually revealing it. Further discussion of Zero knowledge proof of a discrete logarithm and the ability to break RSA
16.13. Blind Signatures One party wants another party to blindly a message (uses RSA).
16.14. Oblivious Transfer One party wants to send another party two primes and needs verify if they were sent correctly.
16.15. Secure Multiparty Computation Two parties want to know if an integer that only each one knows is greater-than/less-than the other parties integer.
16.16. Probabilistic Encryption The most secure cryptosystem invented. The encryption algorithm is probabilistic rather than deterministic (there are a large number of ciphertexts that correspond to a given plaintext)
16.17. Quantum Cryptography Creates a communications channel in which it is impossible to eavesdrop without disturbing the transmission.
17. Example Implementations
17.1. IBM Secret Key Management protocol Complete key management system for communications and file security on a network using only symmetric cryptography. Designed in the 1970s.
17.2. Mitrenet Mitres internal network that supported their secure email (Memo).
17.3. ISDN A secure terminal developed by Bell that can transmit and receive voice and data at 64kbps. It uses Diffie-Hellman, RSA and DES.
17.4. Kerberos A trusted third party authentication protocol designed for Unix TCPIP. Acts as a trusted arbitrator. Further discussion of the kerberos model, software modules, how kerberos works, credentials, getting an initial ticket, getting server tickets, requesting a service, kerberos version 4, the security of kerberos, and the future of kerberos are also provided.
17.5. Kryptoknight An authentication and key distribution system designed by IBM.
17.6. ISO Authentication Framework Also known as X.509. It provides for authentication across networks (although no specific protocol has been specified). It is certificate based.
17.7. Privacy Enhanced Mail (PEM) Allows secure email over the Internet. Provides encryption, authentication, message integrity and key management. It is a superset of X.509. Further discussion of PEM documents, Certificates, PEM Messages, Security of PEM, TIS-PEM and RIPEM are also provided.
17.8. Message Security Protocol The military equivalent of PEM. X.400 Compatible.
17.9. Pretty Good Privacy (PGP) Public domain encryption program that uses IDEA for data encryption, RSA for key management and MD5 as a one way hash function.
17.10. Clipper A NSA designed, tamper resistant VLSI chip. It uses the Skipjack encryption algorithm.
17.11. Capstone Same as the clipper chip with the addition of DSA, SHA as well as other algorithms.
18. Politics
18.1. National Security Agency (NSA) The official security body for the government. Mandate is to listen in on and decode all foreign communications of interest to the security of the United States.
18.2. National Computer Security Center (NCSC) Branch of the NSA that is responsible for the governments trusted computer program. They publish the orange book The DoD Trusted Computer Evaluation Criteria.
18.3. National Institute of Standards and Technology (NIST) Formerly the NBS, they promote open standards and interoperability that they hope will be adopted by all the computer systems in the U.S. They issue standards for cryptographic functions.
18.4. RSA Data Security Inc Develop, license and market the RSA patent (as well as RC2 and RC4).
18.5. International Association of Cryptographic Research (IACR) Worldwide cryptographic research organization whos purpose is to advance the theory and practice of cryptology and related fields.
18.6. Sci.Crypt Internet newsgroup for cryptography.
18.7. Cypherpunks An informal group of people interested in teaching and learning about cryptography.
18.8. Research and development in Advanced Communication Technologies in Europe (RACE) Launched by the European Community for work in communications standards and technologies. Established RIPE.
18.9. Electronic Frontier Foundation (EFF) Civil liberties group that believes information and access to cryptography are fundamental rights.
18.10. Computer Professionals for Social Responsibility (CPSR) Concerned with the application of technology and its social implications.
18.11. Patents Almost every public key algorithm is patented.
18.12. Export Rules Cryptography is treated as a munition. Selling cryptography overseas without a proper export license is considered arms trafficking.
18.13. Legal Issues It is believed that digital signatures would meet the requirements of legally binding signatures for most purposes (even though it has not been challenged in court).