Neal Koblitz A Course In Number Theory And Cryptography Pdf 11
Beatrix Gerke
The course will study classical and new public key cryptography. Systems, whose hardness is based on factoring, such as RSA; discrete logs in abelian groups , such as the Diffie-Hellman key exchange and El-Gamal with elliptic curves; lattices, such as NTRU and ring learning with errors, will be featured. Featured also will be the standard attacks on these systems.
Contents
- Classical systems like Caesar and Vigenère, some simple cryptanalysis.
- The general structure of block ciphers, Feistel ciphers like DES, AES, the most suitable modes-of-use, e.g. CBC or OFB.
- Shift register sequences (linear and non-linear), the linear complexity of a periodic sequence, the Berlekamp-Massey algorithm.
- The principle of public key cryptography.
- Basics of finite fields and their arithmetic.
- Diffie-Hellman key exchange, El Gamal, several methods to take discrete logarithms (baby-step giant-step method, the Pohlig-Hellman method, Pollard-rho and the index calculus method).
- Elliptic curve cryptosystems.
- The RSA system for encryption and signing, generating prime numbers by means of probabilistic primality tests, several factorization algorithms (Pollard-(p-1), Pollard-rho, the random square method, the quadratic sieve method), and some insecure modes of RSA.
- Hash functions, Message Authentication Codes
Our purpose is to give an overview of the applications of number theory to public-key cryptography. We conclude by describing some tantalizing unsolved problems of number theory that turn out to have a bearing on the security of certain cryptosystems.
08 Dec 2014
Lecture given by Jens Bauch.
Concept of public-key cryptography, some recap of number theorybackground (multiplicative group modulo n, Euler-phi function, Euler'stheorem), public key for RSA is (e,n), private key is d, where n=pqfor two different primes p and q, φ(n)=(p-1)(q-1) and d is theinverse of e modulo φ(n); encryption, decryption, sign,verify. Attention, this is schoolbook RSA, do not usethis in practice. For functionality (and security) we want to sign h(m)and not m.
Exponentiation by square and multiply and how many operations thistakes, examples; can choose small e but d must be large/random. Firstproblem with schoolbook multiplication: we can recover a message thatis sent to multiple people, if they all use the same small exponent.
Jens scanned his class prep for youinstead of pictures.