Ahmed HEZZAH, 9425396

Cryptography
from
Foundations of Computing
Josef Gruska

Author: Josef Gruska

Josef Gruska is a Professor of Computer Science at Masaryk University in Brno, at the Slovak Academy of Sciences, Bratislava and at Commenius University in Bratislava. He has held numerous positions and visiting professorships across North America and Europe, including the European Association of Theoretical Computer Science (EATCS) . He was founding Chair of the IFIP Specialist Group on Foundations of Computer Science.

Cryptosystems and Cryptology

Cryptography is the art of providing secure communication over insecure channels
Cryptoanalysis is the art of breaking into such communications
Cryptology is the combined art of cryptography and cryptoanalysis.

• Cryptosystems

• Encryption and decryption always take place within a specific cryptosystem. Each cryptosystem has the following components:
Plaintext-space P: a set of words over an alphabet called plaintexts (or cleartext) or sentences in a natural language
Cryptotext-space C: a set of words over an alphabet called cryptotext
Key-space K: a set of keys
Examples: CAESAR cryptosystem, POLYBIOS cryptosystem, HILL cryptosystem

• Cryptoanalysis

• The aim of cryptoanalysis is to get as much information as possible about the plaintext or the key.
The main types of cryptoanalytic attacks are:
- Cryptotexts-only attack
- Known-plaintexts attack
- Chosen-plaintexts attack
- Known-encryption-algorithm attack
- Chosen-cryptotext attack

Secret-key Cryptosystems

A cryptosystem is called a secret-key cryptosystem if some secret piece of information, the key, has to be agreed upon ahead of time between two parties the want or need to communicate through the cryptosystem. CAESER, POLYBIOS and HILL are examples.

• Mono-alphabetic Substitution Cryptosystems: the substitution rule remains unaltered during encryption.
• Poly-alphabetic Substitution Cryptosystems: many substitution rules are used during encryption
• Transposition Cryptosystems: like permuting the plaintext. Example: DES cryptosystem

Public-Key Cryptosystems

The key observation leading to public-key cryptography is that whoever encrypts a plaintext does not need to be able to decrypt the resulting cryptotext. In such a case each user U can choose a private and a public key as well as an encryption and a decryption algorithm, make the encryption algorithm public and keep secret the decryption algorithm. In  such a case anybody can send messages to U, and U is the only one capable of decrypting them using his secret key and his decryption algorithm.
Examples: Trapdoor one-way functions, Knapsack cryptosystems and RSA cryptosystems.

Digital Signatures

Digital signatures are one of the most fundamental and important inventions of modern cryptography. They help to verify that a received message that claims to be from a certain user is really from this user and that not anybody else pretending to be this user has sent it.
A public-key cryptosystem, in which plaintext and cryptotext space are the same and each user makes his encryption function public and keeps his decryption function secret, can be used for this purpose, for e.g. the RSA cryptosystem. However not all public-key cryptosystems are equally good for this. In addition there are some signatures-only (crypto)schemes.