 |
Applied Cryptology
Applied Mathematics 785/885
|
This course is suitable for graduate students on honours level in mathematics, applied mathematics, computer science or
electrical engineering. The only mathematical prerequisite is that the student should have completed the undergraduate course Applied Mathematics 314
(Applied Discrete Mathematics) successfully. Students who have not completed this prerequisite course may still be allowed to enroll for the current graduate course
(Applied Cryptology) with the understanding that any inadequacy in such a student's backgorund (mathematical or otherwise) is to be corrected by the student in his/her
own time by means of additional reading. Computer programming skills are not essential for this course, but are helpful. However, computer literacy skills are essential for
this course.
This course is a follow-up on Applied Mathematics 314 (Applied Discrete Mathematics) and serves as a further (broad)
introduction to the extensive field of cryptographic system design. The primary objective of the course is to equip the student with
number theoretic & algorithmic techniques that may be used to secure information from a mathematical point of view, while the
secondary objective is to introduce the student to the basic building blocks inherent to comprehensive cryptographic systems:
a symmetric key component, a public key component, a hashing component, an authentication component, a verification of
data-integrity component, and an email-interface component. Attention will also be paid to key distribution and key management,
protocols and crypt-analytic attacks, if time permits.
Basic computations
Integer representations in different bases; algorithms for and complexity analyses of basic arithmetic
operations (multiple precision addition, subtraction, multiplication and integer division) on a computer;
modular arithmetic on a computer; algorithm for and complexity analysis of modular exponentiation.
The Primes
The Euclidean algorithm (and its complexity); relative primality; absolute primality; the fundamental theorem
of arithmetic; the infinitude of the primes (proofs of Euclid, Kummer and Polya); the Euler totient; Euler's theorem;
primality testing by trial division; probabilistic tests for primality of Fermat and of Miller & Rabin; the Lucas-Lehmer
primality proving algorithm; the sieve of Erathostenes; the Mersenne primes; the prime number theorem; Chebychev's proof that
x/log(x) is of order the prime number function, and vice versa. The
logarithmic integral as approximation to the prime number function; Riemann's approximation
to the prime number function; the Euler and Riemann zeta functions; the gamma function; the Riemann hypothesis.
Fyundamentals of Complexity Theory
The satisfiability problem; NP-completeness; the Cook-Levine theorem; the great three amongst computationally hard
problems (discrete square roots, prime factorisation, discrete logarithms).
Basic Number Theory
The primitive root theorem; Lagrange's theorem; Quadratic residues; the Legendre symbol and its
properties; the law of quadratic reciprocity; Wilson's theorem; 2-Sylow subgroup of the group of invertible elements modulo a prime; computing discrete square
roots modulo a prime; the Jacobi symbol and its properties; discrete square roots modulo a
composite integer and their computation.
Prime Factorisation
The relationship between the complexities of the discrete square root problem and the problem of prime factorisation;
Fermat's algorithm for prime factorisation; Pollard's p-1 algorithm for prime factorisation; the quadratic sieve.
Discrete Logarithms
Shank's algorithm for discrete logarithms; the Chinese remainder theorem and Gauss' algorithm;
the Pohlig-Hellman algorithm; the relationship between the complexities of the discrete
logarithm problem and the problem of prime factorisation.
Public Key ciphers
Formulation and working of three public key ciphers: the quadratic residue cipher (based on the
presumed intractability of computing disrete square roots in large composite moduli), the ElGamal
cipher (based on the presumed intractability of computing disrete logorithms in large prime moduli)
and the RSA cipher (based on the presumed intractability of factoring large composite integers);
Signature schemes for and known attacks against three public key ciphers: the quadratic residue
cipher, the ElGamal cipher and the RSA cipher.
Block Ciphers
Block ciphers: DES; SAFER+; IDEA; Rijndael.
Hashing
One-way functions; compression functions; strong and weak collision-free hash functions; single
and double length modification detection codes.
Design of a secure communication system
Key distribution; key management; Pretty Good Privacy.
- Prof JH van Vuuren [CGW Schumann Building, Room 602] [Tel: 808-2879] [email lecturer]
Students are welcome to come and see the lecturer if they wish to discuss any aspect of the course. The lecturer sincerely hopes that
students enrolled for this course will enjoy it and that the topics covered during the course will be of future use to them.
The official module material is the following set of notes:
- JH van Vuuren & SG Berjak, Applied Cryptography: A Graduate Text in
Applied Discrete Mathematics, University of Stellenbosch, Stellenbosch,
2002.
A selection of topics from the following texts will also be covered
during the module:
- JA Buchmann, Introduction to Cryptography,
Springer, New York, 2001 (ISBN 0-387-95034-6).
- R Crandall & C Pomerance, Prime Numbers: A
Computational Perspective, Springer, New York, 2001 (ISBN
0-387-94777-9).
- O Goldreich, Foundations of Cryptography: Basic
Tools, Cambridge University Press, Cambridge, 2001 (ISBN
0-521-79172-3).
- AJ Menezes, PC van Oorschot & SA Vanstone, Handbook
of Applied Cryptography, CRC Press, Boca Raton, 1997 (ISBN
0-8493-8523-7).
- RA Mollin, An Introduction to Cryptography,
Chapman & Hall / CRC, Boca Raton, 2001 (ISBN 1-58488-127-5).
- I Niven & HS Zuckerman, An Introduction to the
Theory of Numbers (4th edition), John Wiley & Sons, New
York, 1980 (ISBN 0-471-02851-7).
- B Schneier, Applied Cryptography: Protocols,
Algorithms and Source Code in C, John Wiley & Sons, New York, 1994
(ISBN 0-471-59756-2).
Each student is expected to hand in a semester project, which consists of writing a report of
approximately 10 pages on a topic made available here.
Students may hand in these reports on any date on or before Friday 26 October 2007.
The module consists of three one-hour lectures per week,
for 13 weeks. The module runs from July to October 2006. Students are expected to hand in weekly
assignments (which require approximately 2-5 hours' work at home per week) as well as one semester project,
to be handed in at the end of the module. There are also two written tests: one at the end of the
third term and one at the end of the fourth term. Marks for the weekly assignments collectively
contribute 20% towards the final mark of the module. The semester project also contributes 20%
towards the final mark of the module. The other 60% of the final module mark are made up from the two
semester tests (30% from each).
[2007 Marks] [2006 Marks]
[2005 Marks] [2004 Marks]
[2003 Marks] [2002 Marks]
[in 2007] [in 2006]
[in 2005] [in 2004]
[in 2003] [in 2002]
- The timetable for this module has been fixed. Lectures will take place in Room A409 of the Main Engineering Building during
the following time slots: Mondays 09:00-09:50, Wednesdays 12:00-12:50 and Fridays 10:00-10:50.
- Dates for the two semester tests have been finalised. Test 1 will be taken down on Thursday 6 September 2007, 19:00-10:00.
Test 2 will be taken down on Monday 5 November 2007, 09:00-12:00.
Home
