Cryptomathematics and ComputabilityLaajuus (3 ECTS)

Objective

The student is sufficiently familiar with algebraic theories in order to understand the operation of the most usual encryption algorithms and the basis of encryption. The student understands the basic facts of computational complexity such as the difference between polynomial and superpolynomial work of computation and the idea of probabilistic algorithms.

Content

1) Algebra and number theory
2) Basic Terms in Cryptography
3) Algorithms and computational complexity
4) RSA encryption and factoring problem
5) Discrete Logarithm problem and applying it to cryptography

Assessment criteria, satisfactory (1)

1) The student can operate with integers, knows divisibility, prime numbers and prime factorization of integers. The student knows the rules of modular arithmetic and can operate with remainders. The student knows the Fermat's theorem and the Euler phi function.

2) The student knows the principle of encryption, knows some classical cryptosystems and understands some apparent weaknesses in cryptosystems. The student knows by name some modern cryptosystems. The student understands the difference between private key and public key encryption.

3) The student knows the Euclidean algorithm and, with small numbers, can calculate the inverse in residue class ring. The student can with small numbers quickly calculate the modular exponentiation.

4) The student knows the RSA encryption and can explain the basis of its assumed security. With small numbers the student can encrypt, calculate the private key from the public key and decrypt.

Assessment criteria, good (3)

Besides of the requirements in Satisfactory:

1) The student knows the notion of group, ring and field with some of their basic properties and examples. The student knows the notion of cyclic group and generator and can find a generator for the multiplicative group of a prime field. The student knows the Chinese remainder theorem and can apply it.

2) The student knows the notion of cryptographic fingerprint, certificate and digital signature. The student knows the difference between the use of private key and public key encryption.

3) The student can explain the polynomial time and non-polynomial time algorithm and their meaning in cryptography. The student can estimate the computation time needed for an algorithm. The student knows the difference between a probabilistic and a deterministic algotithm. The student knows the Miller-Rabin primality test and the Pollard p-1 factoring algorithm.

4) The student knows the most important security criterions for primes used in RSA encryption. The student can explain the principle of digital signature based on RSA encryption.

5) The student can describe the Discrete Logarithm problem and knows the prevalent opinion of its hardness. The student knows the general principle of ElGamal encryption. With small integers the student can encrypt, calculate the private key from the public key and decrypt.

Assessment criteria, excellent (5)

Besides of the requirements in Satisfactory and Good

1) The student can operate with polynomials over a prime field. The student can construct the finite field modulo through an irreducible polynomial and can perform concrete operations in this field, when the order is sufficiently small. The student knows the notion of elliptic curve, can explain the group law for the points of the curve and knows the possibility to use them in cryptography.

2) Based on his/her mathematical background, the student can in detail step by step explain the operation of some modern cryptosystem (e.g. AES-encryption or SHA1 fingerprint).

3) The student knows the Euclidean algorithm for polynomials and can calculate inverses in finite fields. The student has facilities to make effective and sufficiently fast computer programs to implement the algorithms considered before.