317 courses ePortfolio Forums Blog FAQ

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 non-repudiation.  To meet these security requirements, we employ secret key (or symmetric) cryptography, public-key (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 symmetric-key encryption adopted by the U.S. government.  We will also learn about the important MD5 and SHA-1 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 Diffie-Hellman 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

Upon successful completion of this course, students will be able to:
  • 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 substitution-permutation networks.
  • Describe the algorithms for data encryption and the advanced encryption standard.
  • Describe and use the MD5 and SHA-1 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 Diffie-Hellman key exchange.
  • Describe the most common signature and autokey identity schemes.
  • Describe the conceptual workings of public key infrastructure.

Course Requirements  showclose

In order to take this course you must:
 

√    Have access to a computer.

√    Have continuous broadband Internet access.

√    Have the ability/permission to install plug-ins 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


Expand All Resources Collapse All Resources
  • Unit 1: Introduction into Cryptography  

    This unit provides an overview of cryptography, the study of information-hiding and verification.  Cryptography insures the confidentiality/privacy, message integrity, authentication, and non-repudiation 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. 

    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 Time Advisory   show close
    Unit 1 Learning Outcomes   show close
  • 1.1 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  
  • 1.3 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  
  • 1.4.1 Monogram, Bigram, and Trigram Frequency Counts  
  • 1.5 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. 

  • 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, Four-Square, Hill, Playfair, Polybius Square, Rail-fence, 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.

  • 2.1.2 Affine Cipher  
  • 2.1.3 Beaufort Cipher  
  • 2.1.4 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.

  • 2.1.6 Columnar Transposition Cipher  
  • 2.1.7 Four-Square Cipher  
  • 2.1.8 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.

  • 2.1.10 Polybius Square Cipher  
  • 2.1.11 Rail-fence Cipher  
  • 2.1.12 Simple Substitution Cipher  
  • 2.1.13 Straddle Checkerboard Cipher  
  • 2.1.14 Vigenere, Gronsfeld and Autokey Cipher  
  • 2.2 Mechanical Ciphers  
  • 2.2.1 Enigma Cipher  
  • 2.2.2 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 herePlease note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder. 

  • Unit 3: Block Ciphers  

    In this unit, we will start with an explanation of the substitution-permutation network, which works through the series of linked mathematical operations used in block cipher algorithms.  Note that substitution-permutation 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. 

    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 symmetric-key encryption adopted by the U.S. government.

    Unit 3 Time Advisory   show close
    Unit 3 Learning Outcomes   show close
  • 3.1 Substitution-permutation 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. 

  • 3.3 Advanced Encryption Standard  
  • 3.4 Abstraction in Cryptography  
  • Unit 4: Hash Functions  

    This unit will introduce the concept of “hash” and then present the important MD5 and SHA-1 hash functions.  (MD5 is a widely used cryptographic hash function with a 128-bit hash value, and SHA-1 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  
  • 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  
  • 4.2.2 SHA-1  
  • 4.2.3 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.   

  • 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. 

  • 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. 

  • 5.1.2 Primality Testing  
  • 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.

  • 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. 

  • 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. 

  • 5.2.4 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. 

  • 5.3 Prime Factorization Algorithms (More Math)  
  • 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. 

  • 5.3.2 The Pollard p-1 Algorithm  
    • Reading: PlanetMath: John Smith’s “Pollard p-1 Algorithm”

      Link: PlanetMath: John Smith’s “Pollard p-1 Algorithm (PDF)
       
      Instructions: Read the linked webpage to learn how to factor an integer with Pollard's p-1 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. 

  • 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. 

  • 5.3.4 Shanks' Square Forms Factorization  
  • 5.3.5 The Solovay-Strassen Algorithm  
    • Reading: PlanetMath: Christoph Bergemann’s “Solovay-Strassen Test”

      Link: PlanetMath: Christoph Bergemann’s “Solovay-Strassen Test (PDF)
       
      Instructions: Read the linked webpage to learn the how Solovay-Strassen 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. 

  • 5.3.6 Strong Pseudoprimes  
  • 5.3.7 Miller-Rabin Prime Test  
    • Reading: PlanetMath: Christoph Bergemann’s “Miller-Rabin Prime Test”

      Link: PlanetMath: Christoph Bergemann’s “Miller-Rabin Prime Test (PDF)
       
      Instructions: Read the linked webpage to learn the how Miller-Rabin 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. 

  • 5.4 Miller-Rabin Primality Test in Code  
    • Activity: LiteratePrograms’s “Miller-Rabin Primality Test”

      Link: LiteratePrograms’s “Miller-Rabin Primality Test (PDF)
       
      Instructions: Create a java language program that performs Miller-Rabin 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. 

  • Unit 6: Elliptic Curve Cryptography  

    This unit will cover elliptic curve cryptography.  This approach to public-key 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 Diffie-Hellman 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 present-day elliptic curve cryptography.

    Unit 6 Time Advisory   show close
    Unit 6 Learning Outcomes   show close
  • 6.1 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. 

  • 6.2.1 Diffie-Hellman Key Exchange  
    • Reading: PlanetMath: Cameron McLeman’s “Diffie-Hellman Key Exchange”

      Link: PlanetMath: Cameron McLeman’s “Diffie-Hellman Key Exchange (PDF)
       
      Instructions: Read the linked webpage to learn how to exchange the keys with Diffie-Hellman 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. 

  • 6.2.2 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. 

    The unit will then cover five additional schemes (trusted certificates, private certificates, a modified Schnorr algorithm, a modified Guillou-Quisquater algorithm, and a modified Mu-Varadharajan algorithm) before ending with an overview and discussion of public key infrastructure and a lecture by James Massey.

    Unit 7 Time Advisory   show close
    Unit 7 Learning Outcomes   show close
  • 7.1 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. 

  • 7.3 The 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  
  • 7.4.1 Introduction  
  • 7.4.2 Private Certificate Cryptosystem  
  • 7.4.3 Schnorr Cryptosystem  
  • 7.4.4 Guillou-Quisquater Cryptosystem  
  • 7.4.5 Mu-Varadharajan Cryptosystem  
  • 7.5 Public Key Infrastructure  
  • 7.6 Cryptography - Science or Magic?  
  • Final Exam  

« Previous Unit Next Unit » Back to Top