Cryptography for the clueless – Orbifold Consulting

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:

the function is easy to compute
the inverse function is difficult to compute (non-polynomial
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.

# to install use `pip install pycryptodome==3.4.3`

#========================================
# create public and private keys
#========================================

from Crypto.PublicKey import RSA

key = RSA.generate(2048)
private_key = key.exportKey()
with open("./private.pem", "wb") as f:
    f.write(private_key)

public_key = key.publickey().exportKey()
with open("receiver.pem", "wb") as f:
    f.write(public_key)

#========================================
# encrypt
#========================================
from Crypto.PublicKey import RSA
from Crypto.Random import get_random_bytes
from Crypto.Cipher import AES, PKCS1_OAEP

data = "Time is a thief.".encode("utf-8")
with open("encrypted_data.bin", "wb") as f:

    recipient_key = RSA.import_key(open("./receiver.pem").read())
    session_key = get_random_bytes(16)

    # Encrypt the session key with the public RSA key
    cipher_rsa = PKCS1_OAEP.new(recipient_key)
    enc_session_key = cipher_rsa.encrypt(session_key)

    # Encrypt the data with the AES session key
    cipher_aes = AES.new(session_key, AES.MODE_EAX)
    ciphertext, tag = cipher_aes.encrypt_and_digest(data)
    [ f.write(x) for x in (enc_session_key, cipher_aes.nonce, tag, ciphertext) ]    
#========================================
# decrypt
#========================================
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES, PKCS1_OAEP

with open("encrypted_data.bin", "rb") as f:

    private_key = RSA.import_key(open("private.pem").read())

    enc_session_key, nonce, tag, ciphertext = \
       [ f.read(x) for x in (private_key.size_in_bytes(), 16, 16, -1) ]

    # Decrypt the session key with the private RSA key
    cipher_rsa = PKCS1_OAEP.new(private_key)
    session_key = cipher_rsa.decrypt(enc_session_key)

    # Decrypt the data with the AES session key
    cipher_aes = AES.new(session_key, AES.MODE_EAX, nonce)
    data = cipher_aes.decrypt_and_verify(ciphertext, tag)
    print(data.decode("utf-8"))