CORE 139 Methods and Issues in Cryptology Spring 2004

Review Guide

Exam 1

The exam will cover material from the first four weeks, both from the readings and from class. It is closed notes/closed book. You will be provided with any tables you might need (e.g. a Vigenère tableau or a frequency table). You should bring a calculator, though you are not permitted to pre-program it with any formulas that might be relevant.

Definitions

You should be able to define various terms used in the reading and in class, giving examples where appropriate. Examples of terms include but are not limited to cryptography, cryptology, steganography, cryptanalysis, cipher, code, transposition, substitution, monoalphabetic, polyalphabetic, nomenclator, perfect cipher, algorithm, key, known plaintext attack, chosen plaintext attack, chosen ciphertext attack, ciphertext-only attack, Kerckhoffs' Principle, digraph, trigraph, traffic analysis.

History / Names & Dates

You should know about the major historical figures, events, and things described in the readings and in class, their significance to cryptology, and approximate dates when they lived/occurred. Historical figures include, but are not limited to, Auguste Kerckhoffs von Nieuwenhof, Charles Babbage, al-Kindi, Giovanni Soro, Philibert Babou, Francois Viete, Leon Battista Alberti, Blaise de Vigenere, Etienne Bazeries, Sir Charles Wheatstone, Friedrich Wilhelm Kasiski, Baron Lyon Playfair, Thomas J. Beale, Georges Painvin, Major Joseph Mauborgne, William Friedman. Events/things include, but are not limited to, the Zimmermann Telegram, invention of the telegraph, invention of the radio, the Babington Plot, the Black Chambers, Xerxes' attack on Greece.

Possible questions might include matching names to contributions or dates, stating what someone's contribution was, naming the person associated with a particular thing, or describing the importance/cryptographic relevance of a particular event.

Ciphers

You should know about each of the following ciphers, where "know about" includes knowing when it was invented/used, who is responsible for its invention, its historical significance, how to encrypt/decrypt using it, what its keys are and how many there are, what its strengths are (in terms of security), and what tactics are used to break it.

Techniques

You should know about the following techniques for code-breaking, including how to apply them (knowing formulas as necessary) and when they are appropriate to use. You won't be asked to break a complex cipher (too time-consuming for an exam), but questions you might be asked include applying one specific step of a cryptanalysis or one specific technique, or describing what technique would be appropriate for a given circumstance.

You should also be familiar with the tools you used for lab #1 and how to interpret the output. For example, if you are given the output from the additive cipher tool, you should know how to interpret that.

Exam 2

The exam will primarily cover material from weeks 6-12, both from the readings, from class, and from the two videos, though it is possible that some topics from the first four weeks will appear. It is closed notes/closed book. You may not use a calculator.

Definitions

You should be able to define various terms used in the reading and in class, giving examples where appropriate. Examples of terms include but are not limited to ASCII, symmetric keys, asymmetric keys (public-key encryption), one-way functions, block cipher.

History / Names & Dates

You should know about the major historical figures, events, and things described in the readings and in class, their significance to cryptology, and approximate dates when they lived/occurred. Historical figures include, but are not limited to, Arthur Scherbius, Edward Hebern, Hans-Thilo Schmidt, Rex, Marian Rejewski, Asche, Alan Turing, Athanasius Kircher, Thomas Young, Jean-Francois Champollion, Sir Arthur Evans, Alice Kober, Michael Ventris, John Chadwick, Tommy Flowers, Horst Feistel, Whitfield Diffie, Martin Hellman, Ralph Merkle, Diego de Landa, Constantine Samuel Rafinesque-Smaltz, John Stephens, Frederick Catherwood, J. Eric S. Thompson, Yuri Valentinovich Knorosov, Tatiana Proskouriakoff. Events/things include, but are not limited to, Biuro Szyfrow, Rejewski's bombes, Turing's bombes, Ultra, Rosetta Stone, Colossus, ENIAC, invention of the transistor, creation of Fortran, the NSA.

Possible questions might include matching names to contributions or dates, stating what someone's contribution was, naming the person associated with a particular thing, or describing the historic/cryptographic importance of a particular event.

Mathematics

You should know how to apply the XOR operation (or mod 2 addition) and how to convert between binary and decimal. You should know how to apply a permutation specified in the form (2, 4, 3, 1, 5) and how to compute the inverse of a permutation.

You should be able to convert text to a binary string and vice versa. You will be provided with an ASCII table as needed.

Ciphers

You should know about each of the following ciphers, where "know about" includes knowing when it was invented/used, who is responsible for its invention, its historical significance, how to encrypt/decrypt using it, what its keys are and how many there are, what its strengths are (in terms of security), and what tactics are/were used to break it.

Enigma

Things to know about Enigma: when it was invented, who invented it, when it was used, its history (such as struggles to sell the machine, changes in its usage and how that ties into the story of breaking the cipher, etc), its historical significance.

You should be able to describe how Enigma works to encrypt/decrypt messages, including the role of the plugboard, scramblers, and reflector. This role includes how each component contributes to the number of keys and to the relationship between the plaintext and the ciphertext. You should know about major variations in Enigma, such as how the Naval Enigma was different from other versions.

You should know how Enigma and its variations were used in practice to send messages.

Cryptanalysis of Enigma

You should be able to describe various weaknesses found in Enigma, and how they were exploited to break the code. These include: You should also know about other means which were used to break Enigma and how they were important, including:

Navajo Codetalkers

You should know: how the code worked, what its advantages were over mechanical encryption techniques, why Navajo was good choice, the improvements made after the initial version, its historical importance.

Deciphering Ancient Scripts

You should know: the similarities and differences between deciphering ancient scripts and breaking ciphers, and the history of deciphering Egyptian hieroglyphics and Linear B.

You should know the time periods when Egyptian hieroglyphics and Linear B were written/used.

DES

You should know: when it was created, who invented it, what its strengths and weaknesses are.

You should know how to generate the subkeys used by S-DES and how to encrypt and decrypt using S-DES. If asked to perform any of these tasks, you would be given the permutations (labelled as discussed in class e.g. P10, E/P), the contents of the S-boxes, and a sketch of how the Fkey function works - you should know the remaining steps involved and should be familiar enough with the algorithm to be able to apply the Fkey function given just a sketch of the process.

You should also know how DES differs from S-DES.

You should know about the four different ways DES can be used to encrypt a long message.

Key Distribution

You should know what makes key distribution a difficult problem, and why it was important to find a solution.

You should be able to describe how Diffie-Hellman-Merkle key exchange works and apply it to a particular example, when the idea came about, what makes it such an important contribution, and what its drawbacks are.

Public Key Encryption

You should know how public key encryption works (not a specific method, but the role of the public and private keys) and how it could be used for encryption and/or digital signature.

You should know what computational complexity means (big-O notation) and how its helps us estimate how much longer larger problems will take. You should be able to explain why the RSA public key encryption method is secure in terms of computational complexity. You are not required to know the details of RSA beyond the following:

The details of the use of RSA will be covered later.

Final

The exam will be cumulative, with a greater-than-proportional emphasis on the material from weeks 12-14. (That is, there will be an emphasis on the most recent material, but there will be significant coverage of earlier material.) It is closed notes/closed book.

While you shouldn't rule out technical questions (applying particular enciphering/deciphering or cryptanalysis techniques) or name/date/thing fact-recall questions covering the week 1-10 material, you should expect at least some "synthesis" or "bigger picture" questions. These are short answer or "mini-essay" (write a paragraph) questions which involve going beyond just recall - the intent is to test if you understand the technical, social, and historical material covered and can thus apply it in a situation that might not have been explicitly discussed in class.

Definitions

You should be able to define various terms used in the reading and in class, giving examples where appropriate. Examples of terms include but are not limited to public key cryptography, public key, private key, symmetric key algorithm, asymmetric key algorithm, message integrity, message authentication, user authentication, digital signatures, SSL, PGP, strong cryptography, one-way function, trapdoor, key escrow.

History / Names & Dates

You should know about the major historical figures, events, and things described in the readings and in class, their significance to cryptology, and approximate dates when they lived/occurred.

Historical figures include, but are not limited to, Whitfield Diffie, Martin Hellman, Ron Rivest, Adi Shamir, Len Adleman, Phil Zimmermann.

Events/things include, but are not limited to, RSA and PGP, Clipper chip and key escrow controversies.

Public Key Cryptography & RSA

You should know what public key crypto is, why it was such a significant breakthrough, and how it differs from symmetric key crypto.

You should know what properties are required for a mathematical function which is suitable for encryption/decryption in a public key cryptosystem and why those properties are important.

You should know how to encrypt and decrypt a message using RSA given public and private keys, whose key to use for what (e.g. Alice and Bob both have their own public and private keys - which is used when Alice wants to send a message to Bob?). You should know why RSA is (currently) considered to be secure and why it is not a security risk to use the same public key to encrypt many messages.

You should be able to explain why RSA will remain a secure algorithm, even as computers become faster and faster, barring a completely revolutionary advance such as quantum computing.

Message Integrity, Message Authentication, Digital Signatures, User Authentication

You should know how cryptographic techniques are used to ensure message integrity and message authentication, including what is exchanged between Alice and Bob in order to communicate a message. You should know the important properties of a Message Authentication Code (MAC - this is the same as the hash function result that we discussed for digital signatures). You should know what digital signatures are used, and what cryptographic techniques are used to generate them.

You should know how public keys can be securely distributed (including the role of certificates, certificate chains, and certificate authorities) and verified.

PGP

You should know why PGP was a significant contribution. You should know about the history of the release of PGP, and its relevance to the privacy/security debate.

Privacy and Security

You should know about the major points of the privacy/security debate, both for and against the argument of strong crypto being commonly available. You should know about the tactics which have/can be used to control the availability of strong crypto. In particular, you should know about the Clipper chip and key escrow debates in the 90's.