Difference between revisions of "MAT5123"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Better formatting reference.)
 
(5 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
== Catalog entry ==
 
MAT 5123. Introduction to Cryptography. (3-0) 3 Credit Hours.
 
MAT 5123. Introduction to Cryptography. (3-0) 3 Credit Hours.
  
 
Prerequisite: MAT 4213. Congruences and residue class rings, Fermat’s Little Theorem, the Euler phi-function, the Chinese Remainder Theorem, complexity, symmetric-key cryptosystems, cyclic groups, primitive roots, discrete logarithms, one-way functions, public-key cryptosystems, digital signatures, finite fields, and elliptic curves. Differential Tuition: $150. Course Fees: GS01 $90.
 
Prerequisite: MAT 4213. Congruences and residue class rings, Fermat’s Little Theorem, the Euler phi-function, the Chinese Remainder Theorem, complexity, symmetric-key cryptosystems, cyclic groups, primitive roots, discrete logarithms, one-way functions, public-key cryptosystems, digital signatures, finite fields, and elliptic curves. Differential Tuition: $150. Course Fees: GS01 $90.
  
Textbook: J. Hoffstein, J. Pipher, J. H. Silverman, ''An Introduction to Mathematical Cryptography'' (2nd Ed.) Springer Undergraduate Mathematics Series, Springer-Verlag (2014). ISBN: 978-1-4939-1711-2.
+
== Textbook ==
 +
J. Hoffstein, J. Pipher, J. H. Silverman, ''An Introduction to Mathematical Cryptography'' (2nd Ed.) Springer Undergraduate Mathematics Series, Springer-Verlag (2014). ISBN: 978-1-4939-1711-2.
  
 
{| class="wikitable sortable"
 
{| class="wikitable sortable"
Line 10: Line 12:
 
|1
 
|1
 
||
 
||
1.2 & 1.3
+
1.2, 1.3
 
||
 
||
 
Substitution ciphers and basic theory of divisibility.
 
Substitution ciphers and basic theory of divisibility.
Line 28: Line 30:
 
* Modular arithmetic and shift ciphers.
 
* Modular arithmetic and shift ciphers.
 
* Modular rings and finite fields 𝔽ₚ.
 
* Modular rings and finite fields 𝔽ₚ.
* Powers and primitive roots in finite fields.
+
* Powers and primitive roots in finite fields. Fermat's Little Theorem.
 
* Fast exponentiation.
 
* Fast exponentiation.
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
Line 36: Line 38:
 
1.7, 2.1–2.3.
 
1.7, 2.1–2.3.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
Public and private-key cryptosystems. Cyclic groups. Discrete Logarithms. Diffie-Hellman key exchange.
+
Public and private-key cryptosystems.
 +
 
 +
Cyclic groups.
 +
 
 +
Discrete Logarithms.
 +
 
 +
Diffie-Hellman key exchange.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
 
* Symmetric and asymmetric ciphers.
 
* Symmetric and asymmetric ciphers.
Line 50: Line 58:
 
2.4, 2.5. 2.6, 2.7.
 
2.4, 2.5. 2.6, 2.7.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
Elgamal public-key cryptosystem (EGPKC). Cyclic groups. Collision algorithms.
+
Elgamal public-key cryptosystem (EGPKC).
 +
 
 +
Cyclic groups.
 +
 
 +
Collision algorithms.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
 
* Theory of finite cyclic groups.
 
* Theory of finite cyclic groups.
Line 61: Line 73:
 
2.8, 2.9, 2.10
 
2.8, 2.9, 2.10
 
||  <!-- Topics -->
 
||  <!-- Topics -->
Rudiments of ring theory. The Chinese Remainder Theorem. The Pohlig-Hellman Algorithm.
+
Rudiments of ring theory.
 +
 
 +
The Chinese Remainder Theorem.
 +
 
 +
The Pohlig-Hellman Algorithm.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
 
* Rings. Polynomial rings. Quotient rings.
 
* Rings. Polynomial rings. Quotient rings.
Line 80: Line 96:
 
3.1, 3.2, 3.3.
 
3.1, 3.2, 3.3.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
Modular groups of units. The RSA cryptosystem. Practical considerations of security in implementation.
+
Modular groups of units.
 +
 
 +
The RSA cryptosystem.
 +
 
 +
Practical considerations of security in implementation.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
 
* Modular groups 𝑈ₙ.
 
* Modular groups 𝑈ₙ.
 +
* Euler's “totient” function 𝜑. Euler's Theorem.
 
* Powers and roots modulo 𝒑𝒒.
 
* Powers and roots modulo 𝒑𝒒.
 
* The Rivest-Shamir-Adleman (RSA) cryptosystem.
 
* The Rivest-Shamir-Adleman (RSA) cryptosystem.
Line 148: Line 169:
 
6.4, 6.7
 
6.4, 6.7
 
||  <!-- Topics -->
 
||  <!-- Topics -->
Elliptic-Curve Cryptography (ECC). Elliptic curves in characteristic 2.
+
Elliptic-Curve Cryptography (ECC).
 +
 
 +
Elliptic curves in characteristic 2.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
 
* EC Diffie-Hellman key exchange.
 
* EC Diffie-Hellman key exchange.
Line 161: Line 184:
 
6.6
 
6.6
  
Atkin-Morain's “ECs and Primality Proving” (Math. Comp. 61 (1993) 29-68.)
+
Atkin-Morain's “ECs and Primality Proving” (Math. Comp. 61 (1993) 29–68.
[https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1199989-X/]
+
[https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1199989-X/])
 
||  <!-- Topics -->
 
||  <!-- Topics -->
 
EC-based primality testing and factorization techniques.
 
EC-based primality testing and factorization techniques.

Latest revision as of 22:06, 25 March 2023

Catalog entry

MAT 5123. Introduction to Cryptography. (3-0) 3 Credit Hours.

Prerequisite: MAT 4213. Congruences and residue class rings, Fermat’s Little Theorem, the Euler phi-function, the Chinese Remainder Theorem, complexity, symmetric-key cryptosystems, cyclic groups, primitive roots, discrete logarithms, one-way functions, public-key cryptosystems, digital signatures, finite fields, and elliptic curves. Differential Tuition: $150. Course Fees: GS01 $90.

Textbook

J. Hoffstein, J. Pipher, J. H. Silverman, An Introduction to Mathematical Cryptography (2nd Ed.) Springer Undergraduate Mathematics Series, Springer-Verlag (2014). ISBN: 978-1-4939-1711-2.

Week Sections Topics Student Learning Outcomes
1

1.2, 1.3

Substitution ciphers and basic theory of divisibility.

  • Caesar’s and more general substitution ciphers.
  • Greatest common divisor. The extended Euclidean algorithm.

2

1.4, 1.5.

Modular arithmetic and finite fields.

  • Primes and integer factorizations.
  • The Fundamental Theorem of Arithmetic.
  • Modular arithmetic and shift ciphers.
  • Modular rings and finite fields 𝔽ₚ.
  • Powers and primitive roots in finite fields. Fermat's Little Theorem.
  • Fast exponentiation.

3

1.7, 2.1–2.3.

Public and private-key cryptosystems.

Cyclic groups.

Discrete Logarithms.

Diffie-Hellman key exchange.

  • Symmetric and asymmetric ciphers.
  • Encoding schemes.
  • Perfect secrecy. Vernon’s cipher.
  • Examples of symmetric ciphers.
  • Discrete Logarithms.
  • The Diffie-Hellman key exchange.

4

2.4, 2.5. 2.6, 2.7.

Elgamal public-key cryptosystem (EGPKC).

Cyclic groups.

Collision algorithms.

  • Theory of finite cyclic groups.
  • The Discrete Logarithm Problem (DLP).
  • Shanks’ Babystep-Giantstep DLP algorithm.

5

2.8, 2.9, 2.10

Rudiments of ring theory.

The Chinese Remainder Theorem.

The Pohlig-Hellman Algorithm.

  • Rings. Polynomial rings. Quotient rings.
  • Systems of congruences. The Chinese Remainder Theorem.
  • The Pohlig-Hellman Algorithm.

6

None

Review. First midterm exam.

7

3.1, 3.2, 3.3.

Modular groups of units.

The RSA cryptosystem.

Practical considerations of security in implementation.

  • Modular groups 𝑈ₙ.
  • Euler's “totient” function 𝜑. Euler's Theorem.
  • Powers and roots modulo 𝒑𝒒.
  • The Rivest-Shamir-Adleman (RSA) cryptosystem.
  • Implementation and security issues of cryptosystems: Kerchoff's Principle, Known- and Chosen-Plaintext attacks, Man-in-the-Middle attacks, obfuscation (Random-Oracle) attacks, parameter reuse.

8

3.4, 3.5.

Primality testing and factorization attacks on RSA.

  • Distribution of primes. The Prime Number Theorem.
  • Fermat's Little Theorem and Carmichael numbers.
  • The Miller-Rabin probabilistic primality test.
  • Pollard's “𝒑−𝟣” factorization algorithm.

9

4.1, 4.2, 4.3

Digital Signatures.

  • Definition and uses of digital signatures.
  • RSA digital signatures.
  • Elgamal digital signatures and DSA.

10

5.1, 5.3, 5.6, 5.7.

Probability, entropy, information theory and complexity.

  • Rudiments of combinatorics and probability.
  • Bayes's Formula.
  • Random variables and expected values.
  • Entropy of a probability distribution.
  • Perfect secrecy.
  • Complexity theory and 𝒫 versus 𝒩𝒫.

11

None

Review. Second midterm exam.

12

6.1, 6.2., 6.3

Elliptic curves and discrete logarithms.

  • Introduction to elliptic curves (ECs).
  • Elliptic curves over finite fields.
  • Fast multiples (“powers”) in ECs. The Double-and-Add algorithm.
  • The Elliptic Curve Discrete Logarithm Problem (ECDLP).

13

6.4, 6.7

Elliptic-Curve Cryptography (ECC).

Elliptic curves in characteristic 2.

  • EC Diffie-Hellman key exchange.
  • EC Elgamal PKC.
  • EC digital signature.
  • Definition and construction of finite (Galois) fields 𝐺𝐹(2ⁿ).
  • Elliptic curves over 𝐺𝐹(2ⁿ).

14

6.6

Atkin-Morain's “ECs and Primality Proving” (Math. Comp. 61 (1993) 29–68. [1])

EC-based primality testing and factorization techniques.

  • Lenstra's EC factorization algorithm.
  • EC primality certification.

15

None.

Student Presentations. Wrap-up and review.