MATH222 - Number Theory and Cryptography

Year

Credit points

Campus offering

Prerequisites

MATH107 Introduction to Logic and Algebra

Incompatible

MATH108, MATH208, MATH308 - Number Theory and Cryptography

Unit rationale, description and aim

With the development of modern electronic cryptographic methods, Number Theory has evolved from a purely abstract subject into one of crucial economic importance securing the vast majority of funds transfers across the world every day. Essentially all secure electronic communication now relies upon elementary number theory results. The unit also considers the ethics surrounding the use of strong cryptography and the tension between the needs of vulnerable and sometimes oppressed peoples and the need to restrict criminal behaviour. The widespread use and application of cryptocurrencies to support vulnerable and oppressed peoples will be contrasted to the current restricted use as a simple commodity.

This unit uses the mathematical knowledge and understanding developed in earlier units to introduce some of the ideas and applications of Cryptography. The study of cryptographic algorithms such as RSA is supported by consideration of topics from number theory including congruences, primality and factorisation. Digital signature schemes will be introduced, including the need for such schemes. The ethics surrounding the use of cryptographic systems will be considered, as well as the counter-intuitive idea that a study of cryptanalysis strengthens cryptography.

The aim of this unit is to provide students with an understanding of the central role number theory has in modern cryptography and knowledge of a wide variety of number theoretic ideas and techniques. Students will also have an appreciation of the risks and benefits of and some of the requirements needed to support secure cryptography. The applications of cryptography will support a consideration of how careful use of these tools can promote social good, but also how careless use can result in significant harm.

Learning outcomes

To successfully complete this unit you will be able to demonstrate you have achieved the learning outcomes (LO) detailed in the below table.

Each outcome is informed by a number of graduate capabilities (GC) to ensure your work in this, and every unit, is part of a larger goal of graduating from ACU with the attributes of insight, empathy, imagination and impact.

Explore the graduate capabilities.

On successful completion of this unit, students should be able to:

LO1 - Use arithmetic modulo an integer to solve simple problems and prove simple results (GA5)

LO2 - Successfully factorise relatively small integers and explain the problems involved with this process for large integers (GA5)

LO3 - Solve simple Diophantine equations (GA5)

LO4 - Apply the Chinese Remainder Theorem to relevant problems (GA4, GA5)

LO5 - Explain the basic problems involved with cryptography and cryptographic schemes (GA3, GA4)

LO6 - Demonstrate understanding of the RSA scheme or a similar public-key cipher scheme (GA4, GA5, GA7)

LO7 - Demonstrate some understanding of the ethical and social issues involved with implementing cryptographic schemes taking local, indigenous and international perspectives into account (GA1, GA3, GA4, GA6)

Graduate attributes

GA1 - demonstrate respect for the dignity of each individual and for human diversity

GA3 - apply ethical perspectives in informed decision making

GA4 - think critically and reflectively 

GA5 - demonstrate values, knowledge, skills and attitudes appropriate to the discipline and/or profession 

GA6 - solve problems in a variety of settings taking local and international perspectives into account

GA7 - work both autonomously and collaboratively 

Content

Topics will include:

1. Type of numbers from counting to complex numbers, including motivations for extending the idea of number
2. Divisibility results, primes
3. Greatest common divisor, Euclid’s algorithm
4. Introduction to Congruences – definitions and arithmetic
5. Euler’s -function, powers, logs and squares modulo m, Fermat’s little Theorem
6. Diophantine equations.
7. The Chinese Remainder Theorem
8. Introduction to cryptography the problems and solutions
9. RSA
10. Digital signatures and key exchange problems, including the Diffie-Hellman algorithm for publicly exchanging a private key

Learning and teaching strategy and rationale

As is common in Mathematics a variety of Active Learning approaches promote the best acquisition of skills and understanding. Lectures will typically be structured to provide explanations of the material to be covered, along with examples of the applications of that material, as well as formal and informal tasks for students that will reinforce that learning. Splitting the taught content of the lectures into short topics will ensure increased student engagement with the material, as well as providing opportunities for students to consolidate their learning before new material is covered. This allows students to learn the skills and then build understanding, competence and confidence via (ideally, face-to-face) tutorials involving cooperative groups, peer review and other relevant strategies. In all cases this should be supported using available online technology.

This unit will normally include the equivalent of 24 hours of lectures (typically 2 hours per week for 12 weeks) together with 24 hours attendance mode tutorials. Lectures will also be recorded and, where possible or required, students may have access to an online tutorial.

150 hours in total with a normal expectation of 48 hours of directed study and the total contact hours should not exceed 48 hours. The balance of the hours becoming private study.

Assessment strategy and rationale

To successfully complete an undergraduate Mathematics sequence, students need an understanding of a variety of basic Mathematical topics and an ability to apply that understanding to a variety of problems. To succeed at problem solving in Mathematics, students must have these skills at their fingertips and be able to recall them and choose an appropriate approach under some pressure. The assessment strategy chosen, while traditional, tests and supports student learning by providing opportunities to develop and test their problem-solving skills through the unit.

Any detailed discussion of cryptography is obliged to address the ethical and social aspects of using and of not using those techniques. Virtually all applications of cryptography involve striking a balance between supporting the individual’s (or group’s or company’s or country’s) right to privacy and the risk of concealing criminal (or despotic) activity. The assessment schedule includes a group project that will require students to develop arguments for or against the use of cryptography in a recent historical event and to critically analyse another such argument. These reports will be submitted via Turnitin.

The examination components ensure that students have fully integrated the learning and can bring a variety of strategies to bear under pressure.

Typing of Mathematical notation either requires a significant investment of time, or knowledge of advanced Mathematical typesetting software. Neither of those skills are suitable for an undergraduate course in Mathematics. Consequently, assignments, tests and examinations are typically handwritten and either submitted as hardcopy or scanned and submitted to a dropbox, rather than through Turnitin. Students may choose to type their responses and submit them electronically, but this is not a requirement of the unit.

Overview of assessments

Representative texts and references

Baldoni, M., Ciliberto, C., Cattaneo, G., & Gewurz, D. (2009). Elementary number theory, cryptography and codes. London: Springer.

Bruen, A. (2011). Cryptography, information theory and error correction: A handbook for the 21st century. Hoboken, NJ: Wiley-Blackwell.

Donovan, P., & Mack, J. (2014). Code breaking in the Pacific. Heidelberg: Springer Verlag.

Herkommer, M. (1998). Number theory: A programmer’s guide. New York: Osborne/McGraw-Hill.

Hoffstein, J., Pipher, J., & Silverman, J. (2014). An introduction to mathematical cryptography (2nd ed.). London: Springer Verlag.

Jones, G. (1998). Elementary number theory. London: Springer Verlag.

Kahn, D. (1997). The codebreakers: The comprehensive history of secret communication from ancient times to the internet. New York: Simon & Schuster.

Koblitz, N. (1994). A course in number theory and cryptography. London: Springer Verlag.

Rosen, K. H. (2010). Elementary number theory and its applications. New York: Pearson/Addison Wesley.

Swenson, C. (2008). Modern cryptanalysis: Techniques for advanced code breaking. New York: John Wiley & Sons.

Wagstaff, S. (2019). Cryptanalysis of Number Theoretic Ciphers. Chapman and Hall/CRC.