Difference between revisions of "MAT5123"

From Department of Mathematics at UTSA
Jump to navigation Jump to search
(Crypto contents weeks 1-3.)
 
(12 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.
 
||
 
||
−
* Caesar's and more general substitution ciphers.
+
* Caesar’s and more general substitution ciphers.
 
* Greatest common divisor. The extended Euclidean algorithm.
 
* Greatest common divisor. The extended Euclidean algorithm.
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
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.
 
* Encoding schemes.
 
* Encoding schemes.
−
* Perfect secrecy. Vernon's cipher.
+
* Perfect secrecy. Vernon’s cipher.
 
* Examples of symmetric ciphers.
 
* Examples of symmetric ciphers.
−
* Cyclic groups. The Discrete Logarithm Problem.
+
* Discrete Logarithms.
 
* The Diffie-Hellman key exchange.
 
* The Diffie-Hellman key exchange.
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
Line 48: Line 56:
 
4
 
4
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
4.2
+
2.4, 2.5. 2.6, 2.7.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Examples of power series and their formal manipulation.
+
Elgamal public-key cryptosystem (EGPKC).
 +
 
 +
Cyclic groups.
 +
 
 +
Collision algorithms.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Review of Taylor coefficients and Taylor series. Radius of convergence.
+
* Theory of finite cyclic groups.
−
<!-- * Differentiation of Taylor series. -->
+
* The Discrete Logarithm Problem (DLP).
−
* Power series of rational functions.
+
* Shanks’ Babystep-Giantstep DLP algorithm.
−
* Power series defining the complex exponential, trigonometric and hyperbolic functions.
 
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
5
 
5
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
4.3, 4.5 & 4.5
+
2.8, 2.9, 2.10
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Complex natural logarithms. Multivalued holomorphic functions. Singularities.
+
Rudiments of ring theory.
−
<!-- * Linear Diophantine equations in two variables. -->
+
 
 +
The Chinese Remainder Theorem.
 +
 
 +
The Pohlig-Hellman Algorithm.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Definition of the multivalued complex natural logarithm, its principal branch, and other branches.
+
* Rings. Polynomial rings. Quotient rings.
−
<!-- * Derivatives of inverse functions. Derivative of the complex natural logarithm. -->
+
* Systems of congruences. The Chinese Remainder Theorem.
−
* Complex powers via logarithms.
+
* The Pohlig-Hellman Algorithm.
−
* Definition of branch point and branches.
 
−
* Functions holomorphic in punctured neighborhoods. Poles and other singularities.
 
−
* Examples of branching and singularities (complex logarithms, inverse trigonometric/hyperbolic functions, and complex powers).
 
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
Line 83: Line 94:
 
7
 
7
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
5.2 & 5.3  
+
3.1, 3.2, 3.3.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Parametric curves. Line integrals.
+
Modular groups of units.
 +
 
 +
The RSA cryptosystem.
 +
 
 +
Practical considerations of security in implementation.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
<!-- * Compact subsets of the complex plane. -->
+
* Modular groups 𝑈ₙ.
−
<!-- * The Heine-Borel Theorem. -->
+
* Euler's “totient” function 𝜑. Euler's Theorem.
−
* Parametric representation of piecewise smooth curves.
+
* Powers and roots modulo 𝒑𝒒.
−
* Arc-length. Rectifiable curves.
+
* The Rivest-Shamir-Adleman (RSA) cryptosystem.
−
* Line integrals: Definition, examples, and elementary properties.
+
* 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.
−
* Line integrals of holomorphic functions. Fundamental Theorem.
 
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
8
 
8
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
5.4 & 5.5
+
3.4, 3.5.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Estimation and convergence of line integrals.
+
Primality testing and factorization attacks on RSA.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Majorization of path integrals by arclength and bound on magnitude of integrand.
+
* Distribution of primes. The Prime Number Theorem.
−
* Antiderivatives of complex functions with path-independent line integrals.
+
* Fermat's Little Theorem and Carmichael numbers.
−
* Uniform and non-uniform convergence of sequences and series of complex functions.
+
* The Miller-Rabin probabilistic primality test.
−
* Continuous uniform limits of continuous sequences and series, and their integrals.
+
* Pollard's “𝒑−𝟣” factorization algorithm.
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
9
 
9
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
6.1, 6.2, 6.3
+
4.1, 4.2, 4.3
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Cauchy's Theorem and its basic consequences.
+
Digital Signatures.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Statement of Cauchy's Theorem.
+
* Definition and uses of digital signatures.
−
* Proof of Cauchy's Theorem.  
+
* RSA digital signatures.
−
* The Deformation Theorem.
+
* Elgamal digital signatures and DSA.
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
10
 
10
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
7.1 & 7.2
+
5.1, 5.3, 5.6, 5.7.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Cauchy's Integral Formula. Taylor series.
+
Probability, entropy, information theory and complexity.
−
<!-- Liouville's Theorem. The Fundamental Theorem of Algebra. -->
 
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Statement and proof of Cauchy's Integral Formula.
+
* Rudiments of combinatorics and probability.
−
* Existence, uniqueness, and general theory of Taylor series of holomorphic functions.
+
* Bayes's Formula.
−
* Rigorous definition of and proof that complex logarithms are holomorphic.
+
* Random variables and expected values.
 +
* Entropy of a probability distribution.
 +
* Perfect secrecy.
 +
* Complexity theory and 𝒫 versus 𝒩𝒫.
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
Line 139: Line 155:
 
12
 
12
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
8.1–8.3
+
6.1, 6.2., 6.3
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Isolated singularities and Laurent series. The Residue Theorem.
+
Elliptic curves and discrete logarithms.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Definition of Laurent series about an isolated singularity. Examples.
+
* Introduction to elliptic curves (ECs).
−
* Types of isolated singularities: Removable, polar, essential. The Cassorati-Weierstrass Theorem.
+
* Elliptic curves over finite fields.
−
* Statement and proof of the Residue Theorem.
+
* Fast multiples (“powers”) in ECs. The Double-and-Add algorithm.
−
* Elementary techniques to evaluate residues.
+
* The Elliptic Curve Discrete Logarithm Problem (ECDLP).
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
13
 
13
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
Chapter 9.
+
6.4, 6.7
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Calculus of residues.
+
Elliptic-Curve Cryptography (ECC).
 +
 
 +
Elliptic curves in characteristic 2.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Evaluation of integrals of real analytic functions using residues.
+
* EC Diffie-Hellman key exchange.
−
* Evaluation of series of real analytic functions using residues.
+
* EC Elgamal PKC.
 +
* EC digital signature.
 +
* Definition and construction of finite (Galois) fields 𝐺𝐹(2ⁿ).
 +
* Elliptic curves over 𝐺𝐹(2ⁿ).
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
14
 
14
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
11.1–11.3
+
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 -->
 
||  <!-- Topics -->
−
Conformal mappings.
+
EC-based primality testing and factorization techniques.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Preservation of angles and conformal mappings of the plane.
+
* Lenstra's EC factorization algorithm.
−
* Conformal mappings yield pairs of conjugate harmonic functions.
+
* EC primality certification.
−
* Dirichlet's Problem on a planar region.
 
−
* The Riemann Mapping Theorem.
 
−
* Möbius transformations and their use in solving elementary Dirichlet Problems.
 
 
|-  <!-- START ROW -->
 
|-  <!-- START ROW -->
 
| <!-- Week# -->
 
| <!-- Week# -->
 
15
 
15
 
|| <!-- Sections -->
 
|| <!-- Sections -->
−
Chapter 10. (At instructor's discretion, week 15 may be used to wrap-up and review instead.)
+
None.
 
||  <!-- Topics -->
 
||  <!-- Topics -->
−
Complex integration and geometric properties of holomorphic functions 
+
Student Presentations. Wrap-up and review.
 
||  <!-- SLOs -->
 
||  <!-- SLOs -->
−
* Rouché's Theorem.
 
−
* The Open Mapping Theorem.
 
−
* Winding numbers.
 
 
|-
 
|-
 
|}
 
|}

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.

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