Cryptography is the study of the principles and techniques by which information can be concealed in ciphertexts and later revealed by legitimate users employing the secret key, but in which it is either impossible or computationally infeasible for an unauthorized person to do so. Cryptanalysis is the science of recovering information from ciphertexts without knowledge of the key. Both terms are subordinate to the more general term cryptology, that is

cryptology = cryptography + cryptanalysis

Cryptography is the study of the processes of encryption (mapping the original message, called the plaintext, into a secret form, called the the ciphertext, using the encryption key), and decryption (inverting the ciphertext back to the plaintext, using the corresponding decryption key), in such a way that only the intended recipients can decrypt and read the original messages.

cryptography = encryption + decryption

The methods of encryption are often also called ciphers. Cryptanalysis, on the other hand, is the study of breaking the encryptions without the knowledge of the key:

cryptanalysis = cryptanalytic Attacks on encryptions

The idea of encryption, decryption, cryptanalysis, and secure communications over an insecure
channel, usually a computer network and particularly the internet, can be depicted as below

In a more mathematical flavor this simple diagram becomes

and cryptography is the study of encryption and decryption to solve the security problems as follows:

  • confidentiality: Eve understanding Bob’s message to Alice even if she can intercept and get the message.
  • integrity: making sure that Bob’s message has not been modified by Eve.
  • authentication or authorization: making sure the message received by Alice is indeed from Bob, not from Eve.
  • nonrepudiation: stopping Bob later denying the sending of his message. Nonrepudiation
    is particularly important in electronic commerce since we need to make sure that a
    consumer cannot deny the authorization of a purchase.

A crypto system \mathcal{K} is formally defined as a system of functions according to the scheme below

with E_k:M\mapsto C the encryption function and C the encrypted message. The decrypted message M obtained from a decryption function D_k:C\mapsto M such that chaining them yields

\displaystyle E_k . D_k=1.

Types of security

The security  or the unbreakability  of any cryptographic system is of paramount importance. There are several different types of security measures for a cryptographic system we list below.

Unconditionally secure A cryptosystem is unconditionally secure if a cryptanalyst cannot determine how to find the plaintext  M regardless of how much ciphertext  C and computer time/resources he has available to him. A one-time pad (OTP) can be shown to be unconditionally secure, as the key is used only one time (i.e., there are at least as many keys as the plaintexts), the key string is a random string, and the key size is at least as long as the plaintext string. Unconditional security for cryptosystems is called  perfect secrecy, or  information-theoretic security. A cryptosystem S is  unconditionally unbreakable if S is unconditionally secure. In general, cryptosystems do not offer perfect secrecy, in particular public-key cryptosystems, such as the RSA cryptosystem, cannot be unconditionally secure/breakable since once a ciphertext  C is given, its corresponding plaintext  M can in principle be recovered by computing all possible plaintexts until  C is obtained, an attack called forward search. Nevertheless, unconditionally unbreakable cryptosystems exist; it was first proved by Shannon in his 1949 seminal paper in modern cryptography “Communication Theory of Secrecy Systems“.

Computationally secure A cryptosystem S is computationally secure or  polynomially secure if a cryptanalyst cannot decrypt  C to get  M in polynomial-time (or space). A cryptosystem S is  computationally unbreakable, if it is unbreakable in polynomialtime, that is, it is computationally secure. According to the Cook–Karp thesis, any problem that cannot be solved in polynomial-time is  computationally infeasible, thus, if the cryptanalytic attack on a cryptosystem is computationally infeasible, then the cryptosystem is computationally secure and computationally unbreakable. There are several types of computationally security:

  • Provably secure: A cryptosystem S is  provably secure if the difficulty of breaking it can be shown to be essentially as difficult as solving a well-known and supposedly difficult mathematical problem such as the Integer Factorization Problem, IFP, or the Discrete Logarithm Problem, DLP. For example, the Rabin cryptosystem is provably secure, as the security of the Rabin cryptosystem is equivalent to the IFP.
  • Practical/conjectured secure A cryptosystem S is  practical secure if the breaking of the system S is  conjectured to be as difficult as solving a well-known and supposedly difficult mathematical problem such as the IFP or the DLP. For example, breaking the most popular public-key cryptosystem, RSA, is conjectured as being as hard as solving the IFP, but so far this has never been proved or disproved. Most of the public-key and secret-key cryptosystems in current use are of this type.

Public key cryptography

 Compared to secret-key cryptography, public-key cryptography , or asymmetric key cryptography, is surprisingly almost the same (although the idea is different) as the secret-key cryptography , or symmetric key cryptography , except that the keys k  for encryption and decryption are different. That is, we need two keys, E_k  and D_k, such that E_k is used for encryption and D_k  for decryption, respectively. As E_k  is only used for encryption, it can be made public; only D_k  must be kept a secret for decryption. To distinguish public-key cryptosystems from secret-key cryptosystems, E_k  is called the public key , and D_k  the private key ; only the key used in secret-key cryptosystems is called the secret key. Remarkably enough, secret-key cryptography has a very long history, almost as long as our human civilization; whereas public-key cryptography has a rather short history. In fact, the official date of birth of public-key cryptography was 1976, when Diffie and Hellman, then both at Stanford University, published their seminal paper “New Directions in Cryptography”. It was in this seminal paper that they first  publicly proposed the completely new idea of public-key cryptography as well as digital signatures.

 The implementation of public-key cryptosystems is based on trapdoor one-way functions. Let S, T be finite sets, a one-way function f: S\mapsto T is an invertible function satisfying:

  1. the function is easy to compute
  2. the inverse function is difficult to compute (non-polynomial
  3. the inverse function is easy to compute when a trapdoor (I,e, some secret piece of information is given) becomes available.

Though it sounds like a curious function there a various simple examples.

  • The mapping pq\mapsto n where p, q are prime numbers is a one-way function.
  • The mapping x\mapsto e^x mod_N is also a one-way function. The inverse is DLP-hard.
  • Finally, the popular example is x\mapsto x^k mod_N with N = pq a product of primes and kk' = 1 mod_{\phi(N)} and \phi is the Euler totient function.

 

RSA

RSA stand for the three inventors of this scheme: Rivest, Shamir and Adleman. It is based on the following observation:

It is easy to find two large prime numbers, but it is hard to factor a large composite number into its prime factorization form.

The RSA scheme consists of the encryption function

C = M^e\; mod_N

and decryption

M = C^d\; mod_N

where as before M is the message, C is the cypher text and n=pq the product of two large prime numbers. The exponent e is the the public key and d is the private key such that

e.d=1 \;mod_{\phi(n)}.

RSA is available in most programming languages, including Python as seen below. Gist available as well.