Mathematical Background of Public Key Cryptography

Endrôdi Csilla <csilla@mit.bme.hu>

BME MIT

Hornák Zoltán-Selényi Endre <hornak@mit.bme.hu>

BME MIT

The science of public key cryptography provides the theoretical background for several data security services, which became indispensable in as much as the electronic communication in common practice widespread in our days. Therefore it is of great importance that the protocols being developed employing mathematically clarified algorithms must function adequately. This rises several implementational questions, which could lead to weakness in the whole system in case of improper treatment (e.g. if those special cases, which can be attacked by known algorithms, are not eliminated). Further vulnerabilities may occur, if the communication protocol is used with inefficient parameters (e.g. too short key size).

• How can we know for sure that the program we use is appropriate?

• What are the risk factors? Can it occur that our system, which is reckoned as secure, becomes crackable all at once?

• Is it sufficient, if we always select the appropriate key size according to the development of the world, or is it possible that somebody once find an attack method, which is efficient irrespectively of the key size?

• Is there any other public key algorithm besides RSA?

• What kinds of proofs exist for the security of the currently used algorithms?

The questions above have practical notability, but for answering them, deeper knowledge of public key cryptography is required.

In my lecture I aim to present a scientific level introduction to the mathematical background of public key cryptography. I represent the method of constructing public key algorithms, the so-called ”hard problems” in mathematics and their relation to the strength of the algorithms. I review the presently known “hard problems” and the algorithms, which can be derived from them. I unfold which of them are panned also in the practical usage. I delineate the method of determining the strength of an algorithm (namely the required average number of steps for resolution). I introduce the different ways of attacking, and resume those methods, which have became public until now. Finally on the basis of the discussed information, I present the theoretical comparison of those three public key cryptography algorithms, which have practical relevance today.