Difference between revisions of "MAT 5123"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Created page with "Introduction to the theory of finite-dimensional vector spaces. '''Catalog entry''' ''Prerequisite'': Prerequisite: MAT 3233 or MAT 4233, or CS 2233 and CS 2231, , or inst...")
 
 
Line 1: Line 1:
−
Introduction to the theory of finite-dimensional vector spaces.
 
  
−
'''Catalog entry'''
+
== Catalog entry ==
 +
MAT 5123. Introduction to Cryptography. (3-0) 3 Credit Hours.
  
−
''Prerequisite'':  Prerequisite: MAT 3233 or MAT 4233, or CS 2233 and CS 2231, , or instructor consent.
+
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.
  
−
''Contents''
+
== Textbook ==
−
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 (Diffie-Hellman key exchange, RSA, Rabin, El Gamal); digital signatures; and other groups (finite fields, elliptic curves). Generally offered: Spring.
+
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"
 +
! 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.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
2
 +
|| <!-- Sections -->
 +
1.4, 1.5.
 +
||  <!-- Topics -->
 +
Modular arithmetic and finite fields.
 +
||  <!-- SLOs -->
 +
* 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.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
3
 +
|| <!-- Sections -->
 +
1.7, 2.1–2.3.
 +
||  <!-- Topics -->
 +
Public and private-key cryptosystems.
 +
 
 +
Cyclic groups.
 +
 
 +
Discrete Logarithms.
 +
 
 +
Diffie-Hellman key exchange.
 +
||  <!-- SLOs -->
 +
* Symmetric and asymmetric ciphers.
 +
* Encoding schemes.
 +
* Perfect secrecy. Vernon’s cipher.
 +
* Examples of symmetric ciphers.
 +
* Discrete Logarithms.
 +
* The Diffie-Hellman key exchange.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
4
 +
|| <!-- Sections -->
 +
2.4, 2.5. 2.6, 2.7.
 +
||  <!-- Topics -->
 +
Elgamal public-key cryptosystem (EGPKC).
 +
 
 +
Cyclic groups.
 +
 
 +
Collision algorithms.
 +
||  <!-- SLOs -->
 +
* Theory of finite cyclic groups.
 +
* The Discrete Logarithm Problem (DLP).
 +
* Shanks’ Babystep-Giantstep DLP algorithm.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
5
 +
|| <!-- Sections -->
 +
2.8, 2.9, 2.10
 +
||  <!-- Topics -->
 +
Rudiments of ring theory.
 +
 
 +
The Chinese Remainder Theorem.
 +
 
 +
The Pohlig-Hellman Algorithm.
 +
||  <!-- SLOs -->
 +
* Rings. Polynomial rings. Quotient rings.
 +
* Systems of congruences. The Chinese Remainder Theorem.
 +
* The Pohlig-Hellman Algorithm.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
6
 +
|| <!-- Sections -->
 +
None
 +
||  <!-- Topics -->
 +
Review. First midterm exam.
 +
||  <!-- SLOs -->
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
7
 +
|| <!-- Sections -->
 +
3.1, 3.2, 3.3.
 +
||  <!-- Topics -->
 +
Modular groups of units.
 +
 
 +
The RSA cryptosystem.
 +
 
 +
Practical considerations of security in implementation.
 +
||  <!-- SLOs -->
 +
* 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.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
8
 +
|| <!-- Sections -->
 +
3.4, 3.5.
 +
||  <!-- Topics -->
 +
Primality testing and factorization attacks on RSA.
 +
||  <!-- SLOs -->
 +
* Distribution of primes. The Prime Number Theorem.
 +
* Fermat's Little Theorem and Carmichael numbers.
 +
* The Miller-Rabin probabilistic primality test.
 +
* Pollard's “𝒑−𝟣” factorization algorithm.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
9
 +
|| <!-- Sections -->
 +
4.1, 4.2, 4.3
 +
||  <!-- Topics -->
 +
Digital Signatures.
 +
||  <!-- SLOs -->
 +
* Definition and uses of digital signatures.
 +
* RSA digital signatures.
 +
* Elgamal digital signatures and DSA.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
10
 +
|| <!-- Sections -->
 +
5.1, 5.3, 5.6, 5.7.
 +
||  <!-- Topics -->
 +
Probability, entropy, information theory and complexity.
 +
||  <!-- SLOs -->
 +
* Rudiments of combinatorics and probability.
 +
* Bayes's Formula.
 +
* Random variables and expected values.
 +
* Entropy of a probability distribution.
 +
* Perfect secrecy.
 +
* Complexity theory and 𝒫 versus 𝒩𝒫.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
11
 +
|| <!-- Sections -->
 +
None
 +
||  <!-- Topics -->
 +
Review. Second midterm exam.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
12
 +
|| <!-- Sections -->
 +
6.1, 6.2., 6.3
 +
||  <!-- Topics -->
 +
Elliptic curves and discrete logarithms.
 +
||  <!-- SLOs -->
 +
* 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).
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
13
 +
|| <!-- Sections -->
 +
6.4, 6.7
 +
||  <!-- Topics -->
 +
Elliptic-Curve Cryptography (ECC).
 +
 
 +
Elliptic curves in characteristic 2.
 +
||  <!-- SLOs -->
 +
* EC Diffie-Hellman key exchange.
 +
* EC Elgamal PKC.
 +
* EC digital signature.
 +
* Definition and construction of finite (Galois) fields 𝐺𝐹(2ⁿ).
 +
* Elliptic curves over 𝐺𝐹(2ⁿ).
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
14
 +
|| <!-- Sections -->
 +
6.6
 +
 
 +
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/])
 +
||  <!-- Topics -->
 +
EC-based primality testing and factorization techniques.
 +
||  <!-- SLOs -->
 +
* Lenstra's EC factorization algorithm.
 +
* EC primality certification.
 +
|-  <!-- START ROW -->
 +
| <!-- Week# -->
 +
15
 +
|| <!-- Sections -->
 +
None.
 +
||  <!-- Topics -->
 +
Student Presentations. Wrap-up and review.
 +
||  <!-- SLOs -->
 +
|-
 +
|}

Latest revision as of 10:59, 30 August 2025

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.

Retrieved from "https://mathresearch.utsa.edu/wiki/index.php?title=MAT_5123&oldid=5398"