# Module MA346A: Cryptology

Credit weighting (ECTS)
5 credits
Semester/term taught
Michaelmas Term 2013-14
Contact Hours
11 weeks, 3 lectures including tutorials per week
Lecturer
Dr. Michael Purser
Learning Outcomes

Module Content
• Introduction
• The security of computer-based information, stored or transmitted.
Threats: Modification, Masquerade, Leakage, Replay, Repudiation, Traffic analysis, etc.
Services: Confidentiality (message, traffic),
Authenticity (Integrity, Proof and Non-repudiation of Origin or Reception or Delivery, etc.)
Identification: What you know, what you have, what you are.
Secure access management (handshakes), Biometrics.
Secret keys versus secret algorithms.
Generation, storage and transmission of secret keys.
Examples:  Symmetric encryption: Caesar’s cypher
Integrity: CRC/Hash
Authentication: Keyed hash, DES MAC
Other aspects: Steganography, Threshold crypto.
Standard attacks: Known plaintext/cyphertext; Chosen plaintext/cyphertext; Brute force.
Long messages, All-or-nothing transform.

• Concepts
• Shannon’s theories: Unicity key lengths and distances, Perfect secrecy.
Symmetric key cryptography: Encryption and MACs (message authentication checks).
Asymmetric Key cryptography: Encryption and digital signatures.
Distribution and certification of public keys.
Time-stamping.
Trusted third parties (TTPs).
Anonymity

• Symmetric or Secret Key Cryptology
• History: Substitution, permutation, involution.
Vigenere, Beaufort, Polyalphabetic, Jefferson Wheel, Wheatstone Disc, Enigma
DES (Data encryption standard), Triple-DES, IDEA etc.
The AES Project: Mars, Twofish, RC6, Serpent
The winner Rijndael
Encryption modes: ECB, CBC, CFB, etc.
Integrity checks: MACs
Stream cyphers.
Statistical crypt-analysis, shift-and-correlate.

• Random numbers and sequences
• For symmetric keys; as ideal cyphertext.
Random number generators: LCGs, LFBSRs and MLSs, BBS, de Bruin sequences.
Tests for randomness: String lengths, Chi-square.

• Asymmetric Public Key Cryptography
• Concept and invention of public-key crypto (Ellis, Cocks)
Certification of public keys
Bi-prime crypto
Modular arithmetic: Fermat, Euler, primitivity, totient function
The discrete logarithm (DL) problem
Diffie-Hellman and RSA
Rabin encryption
Very large integers and their implications.

• Asymmetric system techniques
• RSA parameters and frustrating attacks.
Primality testing: Rabin, Carmichael numbers
RSA security: order of the group.
Modular inverses, Euclid, continued fractions.
Chinese remainder theorem (CRT)
Speeding up the arithmetic: Karatsuba, Montgomery, small exponents.
Other algorithms: DSA/SHA-1 signature standard.
RPK, MTI/A0, MTI/C0, MQV, Quadratic residues, Fiat-Shamir, Elgamal
Other techniques: Knapsack, Lucas series, elliptic curves, finite quaternions, affine maps
Holding private keys securely.

• Hash functions
• Desiderata
SHA-1, square-mod, MDC, RIPE-MD, RIPE-160
The competition for replacing SHA
Keyed hash functions

• More crypt-analysis
• Differential crypt-analysis (Bihar-Shamir)
Linear crypt-analysis (Matsui)
Factorising: Fermat, the birthday paradox and Pollard Monte Carlo, Pollard (p+1).
Sub-exponential complexity and the use of factor bases:
Dixon’s method, Quadratic sieve, Continued fractions, Introduction to the Number Field Sieve.
The DL problem, Coppersmith et al.

Module Prerequisite
None
Assessment Detail
This module will be examined in a 2 hour examination in Trinity term. Supplementals exams if required will consist of 100% exam.