Cryptography
Purpose of Course showclose
Cryptography is essentially the science of writing in secret code. In data and telecommunications, cryptography has specific security requirements, such as authentication, privacy or confidentiality, integrity, and nonrepudiation. To meet these security requirements, we employ secret key (or symmetric) cryptography, publickey (or asymmetric) cryptography, and hash functions.
In the first part of the course, we will review a number of different ciphers that were used before World War II. These ciphers would be easily broken nowadays, since cryptography has advanced quickly over the past couple of decades with the advent of modern computers. We will cover block cipher algorithms and describe the advanced encryption standard for a symmetrickey encryption adopted by the U.S. government. We will also learn about the important MD5 and SHA1 hash functions as well as the message authentication code.
This course will focus on public key cryptography, which is best exemplified by the RSA algorithm (named after the algorithm inventors Rivest, Shamir, and Adleman). The RSA algorithm is considered particularly strong due to the fact that it relies on prime factorization, a computationally difficult process. We will take a careful look at this algorithm in this course. We will also learn about elliptic curves, another important mathematical function in cryptography, as well as the DiffieHellman key exchange and the elliptic curve discrete logarithm problem.
In the final part of the course, we will cover key exchange methods, study signature schemes, and provide an overview and discussion of public key infrastructure.
Note: It is strongly recommended that you complete Abstract Algebra I (MA231) before taking this course.
Learning Outcomes showclose
 Explain how symmetric and asymmetric key ciphers work.
 List and define cryptography’s goals.
 List and define the most common classical ciphers.
 Explain the workings of mechanical ciphers Enigma and Lorenz.
 Describe the principles of substitutionpermutation networks.
 Describe the algorithms for data encryption and the advanced encryption standard.
 Describe and use the MD5 and SHA1 hash functions.
 Explain the idea behind public key cryptography.
 Use the RSA cryptography system by applying it to practical problems.
 Test whether the large integer is prime with the mathematical tools presented in this course.
 Define the elliptic curve and use it in cryptography.
 Explain the DiffieHellman key exchange.
 Describe the most common signature and autokey identity schemes.
 Describe the conceptual workings of public key infrastructure.
Course Requirements showclose
√ Have access to a computer.
√ Have continuous broadband Internet access.
√ Have the ability/permission to install plugins or software (e.g., Adobe Reader or Flash).
√ Have the ability to download and save files and documents to a computer.
√ Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).
√ Be competent in the English language.
√ Have read the Saylor Student Handbook.
Unit Outline show close

Unit 1: Introduction into Cryptography
This unit provides an overview of cryptography, the study of informationhiding and verification. Cryptography insures the confidentiality/privacy, message integrity, authentication, and nonrepudiation of information. There are two basic types of ciphers used: the symmetric key cipher, which uses the same key for the same message, and the asymmetric key cipher, which uses different keys for encoding and decoding the same message.
Unit 1 Time Advisory show close
This unit will also go over the basics of information theory so that students can get a feel for message encoding before addressing various classical ciphers, which can now be easily cryptanalyzed and broken. Lastly, we will take a look at the methods and techniques used to cryptanalyze any algorithm that enciphers text.
Unit 1 Learning Outcomes show close

1.1 Introduction
 Reading: Wikibooks’ “Cryptography: Introduction”
Link: Wikibooks’ “Cryptography: Introduction” (PDF)
Instructions: Read the article for a general introduction to cryptography. Learn the terms in bold font and familiarize yourself with the common goals and forms of cryptography. This reading covers subunits 1.1.1 through 1.1.3.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikibooks version of this article here.
 Reading: Wikibooks’ “Cryptography: Introduction”
 1.1.1 Basic Vocabulary
 1.1.2 Common Goals in Cryptography
 1.1.3 Common Forms of Cryptography

1.2 History of Cryptography
 Reading: Wikibooks’ “Cryptography: History”
Link: Wikibooks’ “Cryptography: History” (PDF)
Instructions: Read this article to familiarize yourself with cryptography’s history.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikibooks version of this article here.
 Reading: Wikibooks’ “Cryptography: History”

1.3 Basics of Information Theory
 Reading: Computer Science at Carnegie Mellon: David Touretzky’s “Basics of Information Theory”
Link: Computer Science at Carnegie Mellon: David Touretzky’s “Basics of Information Theory” (HTML)
Instructions: Read this webpage to learn about information theory and get a feel for how messeges can be encoded. Make sure you do the exercise listed on the page under “Variable Length Codes” section. This reading covers subunits 1.3.11.3.4.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Computer Science at Carnegie Mellon: David Touretzky’s “Basics of Information Theory”
 1.3.1 Efficient Encodings
 1.3.2 Variable Length Codes
 1.3.3 Measuring Information Content
 1.3.4 The Intuition Behind the P log P Formula

1.4 Basic Cryptanalysis
 Reading: Practical Cryptography’s “Cryptanalysis”
Link: Practical Cryptography’s “Cryptanalysis” (HTML)
Instructions: Read the webpage to learn about the basic cryptanalysis techniques.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Cryptanalysis”

1.4.1 Monogram, Bigram, and Trigram Frequency Counts
 Reading: Practical Cryptography’s “Monogram, Bigram, and Trigram Frequency Counts”
Link: Practical Cryptography’s “Monogram, Bigram, and Trigram Frequency Counts” (HTML)
Instructions: Read the webpage to learn about various cryptanalysis techniques.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Monogram, Bigram, and Trigram Frequency Counts”

1.5 Alice and Bob Go to Washington: A Cryptographic Theory of Politics and Policy
 Lecture: CRYPTO: Edward Felten's “Alice and Bob Go to Washington: A Cryptographic Theory of Politics and Policy”
Link: CRYPTO: Edward Felten's “Alice and Bob Go to Washington: A Cryptographic Theory of Politics and Policy” (Flash)
Also available in:
Mp4 Video
Instructions: Watch this 1hour video about cryptography and politics. It discusses the choices national leaders are making about technology.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: CRYPTO: Edward Felten's “Alice and Bob Go to Washington: A Cryptographic Theory of Politics and Policy”

1.6 Stats in Code
 Activity: home.cogeco.ca: John Russell’s “Frequency Counting”
Link: home.cogeco.ca: John Russell’s “Frequency Counting” (PDF)
Instructions: If you do not have java compiler on your computer, install Java on your computer via www.java.com. Then, create a java language program that performes a frequency counting. You can see how to compile a java code via the java tutorials provided at download.oracle.com. One possible solution can be found via the link above, under the Frequency Counting section. Study the solution code only after you have solved the problem or spent a substantial amount of time working on it (it could take you up to 9 hours).
Terms of Use: The linked material above has been reposted by the kind permission of John Russell, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Activity: home.cogeco.ca: John Russell’s “Frequency Counting”

Unit 2: Classical Cryptography
In this unit, we will learn to describe and analyze the following classical ciphers: ADFGVX, Affine, Beaufort, Bifid, Caesar, Columnar Transposition, FourSquare, Hill, Playfair, Polybius Square, Railfence, Simple Substitution, Straddle Checkerboard, Vigenere, Autokey, Enigma, and Lorenz ciphers.nz ciphers. These ciphers are intuitively easy to understand and seem to encrypt the message well, but they have many shortcomings, which we will discuss as we work through this unit. By studying these classical ciphers, you will learn to avoid poor cipher design.
Unit 2 Time Advisory show close
Unit 2 Learning Outcomes show close
 2.1 Classical Ciphers and Their Cryptanalysis

2.1.1 ADFGVX Cipher
 Reading: Practical Cryptography’s “ADFGVX Cipher”
Link: Practical Cryptography’s “ADFGVX Cipher” (HTML)
Instructions: Read the webpage to learn about the ADFGVX Cipher. Learn the algorithm, go through the JavaScript example, and read through the cryptanalysis to learn how you would break this cipher.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “ADFGVX Cipher”

2.1.2 Affine Cipher
 Reading: Practical Cryptography’s “Affine Cipher”
Link: Practical Cryptography’s “Affine Cipher” (HTML)
Instructions: Read the web page to learn about the Affine Cipher. Learn the algorithm, go through the JavaScript example, and read through the cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Affine Cipher”

2.1.3 Beaufort Cipher
 Reading: Practical Cryptography’s “Beaufort Cipher”
Link: Practical Cryptography’s “Beaufort Cipher” (HTML)
Instructions: Read the webpage to learn about the Beaufort Cipher. Go through the algorithm and JavaScript example.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Beaufort Cipher”

2.1.4 Bifid Cipher
 Reading: Practical Cryptography’s “Bifid Cipher”
Link: Practical Cryptography’s “Bifid Cipher” (HTML)
Instructions: Read the webpage to learn about the Bifid Cipher. Learn the algorithm, go through the JavaScript example, and read through the cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Bifid Cipher”

2.1.5 Caesar Cipher
 Reading: Practical Cryptography’s “Caesar Cipher”
Link: Practical Cryptography’s “Caesar Cipher” (HTML)
Instructions: Read the webpage to learn about the Caesar Cipher. First, go through the mathematical description and JavaScript example. Then, read through the cryptanalysis to learn how to break the cipher.
Terms of Use: Please respect the copyright and terms of use displayed on the webpages above.
 Reading: Practical Cryptography’s “Caesar Cipher”

2.1.6 Columnar Transposition Cipher
 Reading: Practical Cryptography’s “Columnar Transposition Cipher”
Link: Practical Cryptography’s “Columnar Transposition Cipher” (HTML)
Instructions: Read the webpage to learn about the Columnar Transposition Cipher. Go through the written example as well as the JavaScript example, and then read about the cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the web pages above.
 Reading: Practical Cryptography’s “Columnar Transposition Cipher”

2.1.7 FourSquare Cipher
 Reading: Practical Cryptography’s “FourSquare Cipher”
Link: Practical Cryptography’s “FourSquare Cipher” (HTML)
Instructions: Learn the algorithm and cryptanalysis of FourSquare Cipher. Go through the Javascript example.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “FourSquare Cipher”

2.1.8 Hill Cipher
 Reading: Practical Cryptography’s “Hill Cipher”
Link: Practical Cryptography’s “Hill Cipher” (HTML)
Instructions: Go through the written example and JavaScript example of Hill Cipher and then read about its cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpages above.
 Reading: Practical Cryptography’s “Hill Cipher”

2.1.9 Playfair Cipher
 Reading: Playfair Cipher
Link: Practical Cryptography’s “Playfair Cipher” (HTML)
Instructions: Read about Playfair’s algorithm and cryptanalysis and then go through the JavaScript example.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Playfair Cipher

2.1.10 Polybius Square Cipher
 Reading: Practical Cryptography’s “Polybius Square Cipher”
Link: Practical Cryptography’s “Polybius Square Cipher” (HTML)
Instructions: Go through both examples (written and JavaScript) of the Polybius Square Cipher, and then read about its cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Polybius Square Cipher”

2.1.11 Railfence Cipher
 Reading: Practical Cryptography’s “Railfence Cipher”
Link: Practical Cryptography’s “Railfence Cipher” (HTML)
Instructions: Go through both examples (written and JavaScript) of the Railfence Cipher and then read about its cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Railfence Cipher”

2.1.12 Simple Substitution Cipher
 Reading: Practical Cryptography’s “Simple Substitution Cipher
Link: Practical Cryptography’s “Simple Substitution Cipher” (HTML)
Instructions: Go through both examples (written and JavaScript) of the Simple Substitution Cipher and then read about its cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Simple Substitution Cipher

2.1.13 Straddle Checkerboard Cipher
 Reading: Practical Cryptography’s “Straddle Checkerboard Cipher”
Link: Practical Cryptography’s “Straddle Checkerboard Cipher” (HTML)
Instructions: Learn the algorithm and check out the JavaScript example.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Straddle Checkerboard Cipher”

2.1.14 Vigenere, Gronsfeld and Autokey Cipher
 Reading: Practical Cryptography’s “Vigenere and Gronsfeld Cipher”
Link: Practical Cryptography’s “Vigenere and Gronsfeld Cipher” (HTML)
Instructions: Read the webpage to learn the algorithm for the Vigenere, Gronsfeld and Autokey Cipher. Then go through the JavaScript example and read the cryptanalysis.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Vigenere and Gronsfeld Cipher”
 2.2 Mechanical Ciphers

2.2.1 Enigma Cipher
 Reading: Practical Cryptography’s “Enigma Cipher”
Link: Practical Cryptography’s “Enigma Cipher” (HTML)
Instructions: Read the web page to learn about the Enigma Cipher. Go through the JavaScript example and read about mathematical description.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Enigma Cipher”

2.2.2 Lorenz Cipher
 Reading: Practical Cryptography’s “Lorenz Cipher”
Link: Practical Cryptography’s “Lorenz Cipher” (HTML)
Instructions: Read the webpage to learn about the Lorenz Cipher and go through the Javascript example.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Practical Cryptography’s “Lorenz Cipher”

2.3 Ciphers in Code
 Activity: home.cogeco.ca: John Russell’s “Cryptology Programs”
Link: home.cogeco.ca: John Russell’s “Cryptology Programs” (PDF)
Instructions: If you do not have java compiler on your computer, install Java on your computer via www.java.com. Then, create Caesar cipher with java. You can see how to compile a java code via the java tutorials provided at download.oracle.com. One possible solution can be found via the link above, under the Caesar section. Study the solution code only after you have solved the problem or spent a substantial amount of time working on it (it could take you up to 9 hours).
Terms of Use: The linked material above has been reposted by the kind permission of John Russell, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Activity: home.cogeco.ca: John Russell’s “Cryptology Programs”

Unit 3: Block Ciphers
In this unit, we will start with an explanation of the substitutionpermutation network, which works through the series of linked mathematical operations used in block cipher algorithms. Note that substitutionpermutation networks take a block of plain text and the key as inputs and then apply several alternating rounds of substitution and permutation boxes to encipher the data.
Unit 3 Time Advisory show close
This unit also uses the complete mathematical algorithm to describe the data encryption standard before finishing with a description of the advanced encryption standard for a symmetrickey encryption adopted by the U.S. government.
Unit 3 Learning Outcomes show close

3.1 Substitutionpermutation Network
 Reading: Wikipedia’s “SubstitutionPermutation Network”
Link: Wikipedia’s “SubstitutionPermutation Network” (PDF)
Instructions: Read this article to learn about substitutionpermutation network.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “SubstitutionPermutation Network”

3.2 Data Encryption Standard
 Reading: www.itl.nist.gov’s “Data Encryption Standard”
Link: www.itl.nist.gov’s “Data Encryption Standard” (PDF)
Instructions: Carefully read the webpage to learn about the encryption standards given by National Institute of Standards and Technology. Learn in detail the material under the “Data Encryption Algorithm” section. Spend time on this important reading and make sure you know how the encryption algorithm works.
Terms of Use: This material is in the public domain.
 Reading: www.itl.nist.gov’s “Data Encryption Standard”

3.3 Advanced Encryption Standard
 Reading: Wikipedia’s “Advanced Encryption Standard”
Link: Wikipedia’s “Advanced Encryption Standard” (PDF)
Instructions: Read the article about advanced encryption standard. Focus on the description of cipher.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Advanced Encryption Standard”

3.4 Abstraction in Cryptography
 Lecture: CRYPTO: Ueli Maurer's “Abstraction in Cryptography”
Link: CRYPTO: Ueli Maurer's “Abstraction in Cryptography” (Flash)
Also available in:
Mp4 Video
Instructions: Watch this 1hour video about layers of abstraction in cryptography.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: CRYPTO: Ueli Maurer's “Abstraction in Cryptography”

Unit 4: Hash Functions
This unit will introduce the concept of “hash” and then present the important MD5 and SHA1 hash functions. (MD5 is a widely used cryptographic hash function with a 128bit hash value, and SHA1 is a cryptographic hash function designed by the National Security Agency.) We will finish the unit with a look at message authentication code, sometimes called a “keyed hash function.”
Unit 4 Time Advisory show close
Unit 4 Learning Outcomes show close

4.1 Cryptographic Hash
 Reading: Unixwiz’s “An Illustrated Guide to Cryptographic Hashes”
Link: Unixwiz’s “An Illustrated Guide to Cryptographic Hashes” (HTML)
Instructions: Read the web page about cryptographic hashs. Understand what hash is, how hash works, how to use it with UNIX, and issues related to collisions. This reading covers subunits 4.1.1 through 4.1.8.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Unixwiz’s “An Illustrated Guide to Cryptographic Hashes”
 4.1.1 What Is a Cryptographic Hash?
 4.1.2 Hashes Are Digests, Not Encryption
 4.1.3 How Are Hashes Used?
 4.1.4 But What About Collisions?
 4.1.5 What's inside a Cryptographic Hash?
 4.1.6 Collision Resistance in More Detail
 4.1.7 So What's the Big News?
 4.1.8 What Does This Mean?
 4.2 Cryptographic Hash Functions

4.2.1 MD5
 Reading: Wikipedia’s “MD5”
Link: Wikipedia’s “MD5” (PDF)
Instructions: Read about the MD5, which is a widely used cryptographic hash function. Make sure you understand the MD5 algorithm.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “MD5”

4.2.2 SHA1
 Reading: Wikipedia’s “SHA1”
Link: Wikipedia’s “SHA1” (PDF)
Instructions: Read about the cryptographic hash function designed by the National Security Agency. Make sure you understand SHA1 pseudo code.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “SHA1”

4.2.3 Message Authentication Code
 Reading: Wikipedia’s “Message Authentication Code”
Link: Wikipedia’s “Message Authentication Code” (PDF)
Instructions: Read the linked article about message authentication code. Make sure you understand the example given on the web site.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Message Authentication Code”

4.3 Cryptographic Hashing Function in Code
 Reading: OWASP’s “Cryptographic Hashing Function”
Link: OWASP’s “Cryptographic Hashing Function” (PDF)
Instructions: Create a Java language program that runs cryptographic hashing function. One possible solution can be found via the link above. Study the solution code only after you have solved the problem or spent a substantial amount of time working on it (it could take you up to 9 hours).
Terms of Use: The linked material above has been reposted by the kind permission of OWASP, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: OWASP’s “Cryptographic Hashing Function”

Unit 5: The RSA Cryptosystem and Factoring Integers
In this unit, we will learn the basic idea behind public key cryptography and explain in detail RSA as the most important example of public key cryptography. Next, we will discuss the algorithms used to determine whether an input number is prime. As noted earlier, these algorithms are important in public key cryptography because encryption depends on the factorization of prime numbers. This unit will present the mathematical background you need in order to understand these algorithms and in turn get a better picture of public key cryptography.
Unit 5 Time Advisory show close
Unit 5 Learning Outcomes show close

5.1 Introduction
 Reading: PlanetMath: Andrew Ross’s “Public Key Cryptography”
Link: PlanetMath: Andrew Ross’s “Public Key Cryptography” (PDF)
Instructions: Read the linked webpage for introduction to public key cryptography.
Terms of Use: The linked material above has been reposted by the kind permission of Andrew Ross, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Andrew Ross’s “Public Key Cryptography”

5.1.1 Example of Public Key Cryptography
 Reading: PlanetMath: Andrew Ross’s “RSA”
Link: PlanetMath: Andrew Ross’s “RSA” (PDF)
Instructions: Read the linked webpage above to learn whatRSA is. Take for granted the Chinese Reminder theorem, which is explained in a later subunit.
Terms of Use: The linked material above has been reposted by the kind permission of Andrew Ross, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Andrew Ross’s “RSA”

5.1.2 Primality Testing
 Reading: Wikipedia’s “Primality Test”
Link: Wikipedia’s “Primality Test” (PDF)
Instructions: Read this article on primality testing, which is crucial to the security of publickey cryptography. Make sure you understand the naive tests, probabilistic tests, and fast deterministic tests.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Primality Test”
 5.2 Math Background

5.2.1 Euclid's Algorithm
 Reading: PlanetMath: Robert Milson’s “Euclid's Algorithm”
Link: PlanetMath: Robert Milson’s “Euclid's Algorithm” (PDF)
Instructions: Read the linked webpage above to learn how Euclid's algorithm works. Work through the given example.
Terms of Use: The linked material above has been reposted by the kind permission of Robert Milson, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Robert Milson’s “Euclid's Algorithm”

5.2.2 Chinese Remainder Theorem
 Reading: PlanetMath: Chi Woo’s “Chinese Remainder Theorem”
Link: PlanetMath: Chi Woo’s “Chinese Remainder Theorem” (PDF)
Instructions: Read the linked webpage to learn how Chinese Remainder theorem works.
Terms of Use: The linked material above has been reposted by the kind permission of Chi Woo, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Chi Woo’s “Chinese Remainder Theorem”

5.2.3 Legendre Symbol
 Reading: PlanetMath: Alvaro Lozano Robledo’s “Legendre Symbol”
Link: PlanetMath: Alvaro Lozano Robledo’s “Legendre Symbol” (PDF)
Instructions: This reading will define the Legendre symbol.
Terms of Use: The linked material above has been reposted by the kind permission of Alvaro Lozano Robledo, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Alvaro Lozano Robledo’s “Legendre Symbol”

5.2.4 Calculating the Jacobi Symbol
 Reading: PlanetMath: Christoph Bergemann’s “Jacobi Symbol” and “Calculating the Jacobi Symbol”
Link: PlanetMath: Christoph Bergemann’s “Jacobi Symbol” (PDF) and “Calculating the Jacobi Symbol” (PDF)
Instructions: Read these webpages.
Terms of Use: The linked material above has been reposted by the kind permission of Christoph Bergemann, and can be viewed in its original from here and here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Christoph Bergemann’s “Jacobi Symbol” and “Calculating the Jacobi Symbol”

5.2.5 Subgroup
 Reading: PlanetMath: Yann Lamontagne’s “Subgroup”
Link: PlanetMath: Yann Lamontagne’s “Subgroup” (PDF)
Instructions: Read the linked webpage above to learn the definition of a subgroup.
Terms of Use: The linked material above has been reposted by the kind permission of Yann Lamontagne, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Yann Lamontagne’s “Subgroup”

5.3 Prime Factorization Algorithms (More Math)
 Reading: Wolfram Mathworld: Eric Weisstein's “Prime Factorization Algorithms”
Link: Wolfram Mathworld: Eric Weisstein’s “Prime Factorization Algorithms” (HTML)
Instructions: Read the linked webpage for an introduction to prime factorization.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: Wolfram Mathworld: Eric Weisstein's “Prime Factorization Algorithms”

5.3.1 Integer Factorization
 Reading: PlanetMath: John Smith’s “Integer Factorization”
Link: PlanetMath: John Smith’s “Integer Factorization” (PDF)
Instructions: Read the linked webpage to learn about integer factorization.
Terms of Use: The linked material above has been reposted by the kind permission of John Smith, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: John Smith’s “Integer Factorization”

5.3.2 The Pollard p1 Algorithm
 Reading: PlanetMath: John Smith’s “Pollard p1 Algorithm”
Link: PlanetMath: John Smith’s “Pollard p1 Algorithm” (PDF)
Instructions: Read the linked webpage to learn how to factor an integer with Pollard's p1 algorithm.
Terms of Use: The linked material above has been reposted by the kind permission of John Smith, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: John Smith’s “Pollard p1 Algorithm”

5.3.3 The Pollard Rho Algorithm
 Reading: PlanetMath: John Smith’s “Pollard Rho Algorithm”
Link: PlanetMath: John Smith’s “Pollard Rho Algorithm” (PDF)
Instructions: Read the linked webpage to learn how to factor an integer with Pollard's Rho algorithm.
Terms of Use: The linked material above has been reposted by the kind permission of John Smith, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: John Smith’s “Pollard Rho Algorithm”

5.3.4 Shanks' Square Forms Factorization
 Reading: Wikipedia’s “Shanks' Square Forms Factorization”
Link: Wikipedia’s “Shanks' Square Forms Factorization” (PDF)
Instructions: Read the linked article to learn about Shanks' square forms factorization. Make sure you understand the algorithm and the examples given.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Shanks' Square Forms Factorization”

5.3.5 The SolovayStrassen Algorithm
 Reading: PlanetMath: Christoph Bergemann’s “SolovayStrassen Test”
Link: PlanetMath: Christoph Bergemann’s “SolovayStrassen Test” (PDF)
Instructions: Read the linked webpage to learn the how SolovayStrassen test works. If some definitions are not clear, click on the links provided on the website.
Terms of Use: The linked material above has been reposted by the kind permission of Christoph Bergemann, and can be viewed in its original form here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Christoph Bergemann’s “SolovayStrassen Test”

5.3.6 Strong Pseudoprimes
 Reading: Wikipedia’s “Strong Pseudoprime”
Link: Wikipedia’s “Strong Pseudoprime” (PDF)
Instructions: Read the linked article to learn the definitions and properties of pseudoprime numbers. Go through the examples.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Strong Pseudoprime”

5.3.7 MillerRabin Prime Test
 Reading: PlanetMath: Christoph Bergemann’s “MillerRabin Prime Test”
Link: PlanetMath: Christoph Bergemann’s “MillerRabin Prime Test” (PDF)
Instructions: Read the linked webpage to learn the how MillerRabin Primetest works.
Terms of Use: The linked material above has been reposted by the kind permission of Christoph Bergemann, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Christoph Bergemann’s “MillerRabin Prime Test”

5.4 MillerRabin Primality Test in Code
 Activity: LiteratePrograms’s “MillerRabin Primality Test”
Link: LiteratePrograms’s “MillerRabin Primality Test” (PDF)
Instructions: Create a java language program that performs MillerRabin primality test. One possible solution can be found via the link above. Study the solution code only after you have solved the problem or spent a substantial amount of time working on it (it could take you up to 9 hours).
Terms of Use: This material is part of the public domain.
 Activity: LiteratePrograms’s “MillerRabin Primality Test”

Unit 6: Elliptic Curve Cryptography
This unit will cover elliptic curve cryptography. This approach to publickey cryptography is based on the algebraic structure of elliptic curves over finite fields. This unit includes examples of elliptic curves over the field of real numbers. The next unit will explain the DiffieHellman key exchange as the most important example of cryptographic protocol for symmetric key exchange. In the last part of this unit, we will learn about the elliptic curve discrete logarithm problem, which is the cornerstone of much of presentday elliptic curve cryptography.
Unit 6 Time Advisory show close
Unit 6 Learning Outcomes show close

6.1 Elliptic Curve Cryptography
 Reading: Wikipedia’s “Elliptic Curve Cryptography”
Link: Wikipedia’s “Elliptic Curve Cryptography” (PDF)
Instructions: Read the introduction to learn about Elliptic Curve Cryptography.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Elliptic Curve Cryptography”

6.2 Elliptic Curves
 Reading: PlanetMath: David Jao’s “Elliptic Curves”
Link: PlanetMath: David Jao’s “Elliptic Curves” (PDF)
Instructions: Read the “Basics” and “Example” sections of this webpage to learn about elliptic curves. Make sure you understand the examples given. Depending on your mathematics background, you may need to click on the additional links explaining the terminology used.
Terms of Use: The linked material above has been reposted by the kind permission of David Jao, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: David Jao’s “Elliptic Curves”

6.2.1 DiffieHellman Key Exchange
 Reading: PlanetMath: Cameron McLeman’s “DiffieHellman Key Exchange”
Link: PlanetMath: Cameron McLeman’s “DiffieHellman Key Exchange” (PDF)
Instructions: Read the linked webpage to learn how to exchange the keys with DiffieHellman key exchange technique.
Terms of Use: The linked material above has been reposted by the kind permission of Cameron McLeman, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Cameron McLeman’s “DiffieHellman Key Exchange”

6.2.2 Elliptic Curve Discrete Logarithm Problem
 Reading: PlanetMath: Cameron McLeman’s “Elliptic Curve Discrete Logarithm Problem”
Link: PlanetMath: Cameron McLeman’s “Elliptic Curve Discrete Logarithm Problem” (HTML)
Instructions: Read the linked webpage, which introduces elliptic curve discrete logarithm problems. Make sure you know what the problems ask you to solve.
Terms of Use: The linked material above has been reposted by the kind permission of Cameron McLeman, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Cameron McLeman’s “Elliptic Curve Discrete Logarithm Problem”

Unit 7: Digital Signature and Entity Authentication
This unit begins with a general discussion of key exchange methods, or methods designed to distribute keys securely so that they can be later used in a cryptographic algorithm. This unit also describes the difficult problem of computing the discrete logarithm, which is of greatly interest to cryptologists by virtue of its ElGamal signature scheme.
Unit 7 Time Advisory show close
The unit will then cover five additional schemes (trusted certificates, private certificates, a modified Schnorr algorithm, a modified GuillouQuisquater algorithm, and a modified MuVaradharajan algorithm) before ending with an overview and discussion of public key infrastructure and a lecture by James Massey.
Unit 7 Learning Outcomes show close

7.1 Key Exchange
 Reading: Wikipedia’s “Key Exchange”
Link: Wikipedia’s “Key Exchange” (PDF)
Instructions: Read the linked article to learn how to exchange cryptographic keys between users so a cryptographic algorithm can be used.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Key Exchange”

7.2 Discrete Logarithm
 Reading: PlanetMath: Christoph Bergemann’s “Discrete Logarithm”
Link: PlanetMath: Christoph Bergemann’s “Discrete Logarithm” (PDF)
Instructions: Read about the discrete logarithm problem, which is of great interest in the field of cryptography.
Terms of Use: The linked material above has been reposted by the kind permission of Christoph Bergemann, and can be viewed in its original from here. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
 Reading: PlanetMath: Christoph Bergemann’s “Discrete Logarithm”

7.3 The ElGamal Signature Schemes
 Reading: Wikipedia’s “ElGamal Signature Schemes”
Link: Wikipedia’s “ElGamal Signature Schemes” (PDF)
Instructions: Read the linked article to learn about the system parameters, key and signature generation, verification, correctness, and security of the ElGamal signature scheme. This reading covers subunits 7.3.1 through 7.3.6.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “ElGamal Signature Schemes”
 7.3.1 System Parameters
 7.3.2 Key Generation
 7.3.3 Signature Generation
 7.3.4 Verification
 7.3.5 Correctness
 7.3.6 Security

7.4 Autokey Identity Schemes
 Reading: ECE/CIS labs at the University of Delaware: David Mills’s “Autokey Identity Schemes”
Link: ECE/CIS labs at the University of Delaware: David Mills’s “Autokey Identity Schemes” (HTML)
Instructions: Read the linked webpage to learn about autokey identity schemes. This reading covers subunits 7.4.1 through 7.4.5.
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Reading: ECE/CIS labs at the University of Delaware: David Mills’s “Autokey Identity Schemes”
 7.4.1 Introduction
 7.4.2 Private Certificate Cryptosystem
 7.4.3 Schnorr Cryptosystem
 7.4.4 GuillouQuisquater Cryptosystem
 7.4.5 MuVaradharajan Cryptosystem

7.5 Public Key Infrastructure
 Reading: Wikipedia’s “Public Key Infrastructure”
Link: Wikipedia’s “Public Key Infrastructure” (PDF)
Instructions: Read the linked article for general overview of public key infrastructure.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia’s “Public Key Infrastructure”

7.6 Cryptography  Science or Magic?
 Lecture: Massachusetts Institute of Technology: James Massey's “Cryptography  Science or Magic?”
Link: Massachusetts Institute of Technology: James Massey's “Cryptography  Science or Magic?” (Flash)
Instructions: Watch this 1hour video about cryptography. Professor Massey presents a number of topics, including Nobreak Cryptography, Noleak Secret Sharing, Nokey Cryptography, Nowatch Coin Tossing,
Terms of Use: Please respect the copyright and terms of use displayed on the webpage above.
 Lecture: Massachusetts Institute of Technology: James Massey's “Cryptography  Science or Magic?”

Final Exam
 Final Exam: Saylor Foundation's CS409 Final Exam
Link: Saylor Foundation's CS409 Final Exam
Instructions: You must be logged into your Saylor Foundation School account in order to access this exam. If you do not yet have an account, you will be able to create one, free of charge, after clicking the link.
 Final Exam: Saylor Foundation's CS409 Final Exam