Introdução à Computabilidade, Complexidade e Criptografia

Objectives

To know the basic models of computation, the limits of what can be computed, and the basic notions of complexity theory. To understand the fundamental concepts of modern cryptography, and the cryptographic systems and protocols in use.

Syllabus

Algorithms and programs. Turing machines and non-determinism. The Church- Turing thesis. Computable function. Languages and decidability. Undecidability of the halting problem. Recursion and the universal computable function. Rice's theorem and applications. Program efficiency. From program efficiency to complexity classes. The classes P and NP. Symmetric cryptographic systems, iterated and block ciphers. Cryptanalysis, perfect secrecy and Shannon's theorem. The standards DES and AES. Asymmetric cryptographic systems, computational security. The RSA and ElGamal cryptosystems. Digital signatures. The DSA signature scheme. Hash functions. Digital certificates. Key agreement and key distribution protocols. The Diffie-Hellman scheme, Kerberos. Insecure channels, passive and active adversaries.

Cross Competence Component

The UC promotes the media literacy, as well as inter and intra-personal competences, including writing of reports and presentation of results, and critical reasoning, via de development of presentations and assignments, individually and in groups, with multiple valid solutions.