Sunday, 6 June 2021

Looking Deeper Into the World of Cryptography

Looking Deeper Into the World of Cryptography

Although the words cryptology, cryptography and cryptanalysis are used interchangeably - strictly speaking - they mean different things. Nowadays, practically we only use the word cryptography for everything. Today’s post not only aims to point out the differences among them but also to show their connections to each other.

To begin with, cryptology is the mathematics, algorithms, and the applications of formulas that underpins cryptography and cryptanalysis. The world of cryptology goes from basic foundations in cryptography (code-making) to modern algebraic cryptanalysis (code-breaking). So, cryptology is clearly divided into two major parts: cryptography and cryptanalysis, and there are strong connections to each other. Basically, the most important topics related to each other include cryptographic applications, types of cryptography and their algorithms, code-breaking techniques, information theory, number theory and mathematical applications to encrypt data and also break ciphers.

To illustrate, some main cryptography topics are about legal and ethical issues, types of cryptographic algorithms, cryptosystem components, cryptographic applications, classical cryptographic algorithms and their methods of breaking, number theory and information theory; whereas cryptanalysis include code-breaking algorithms for block ciphers, stream ciphers, hash functions and message authentication codes, and finally goes a bit deeper into algebraic cryptanalysis on modern approach such as algebraic coding and optimization, algebraic attacks, polynomial systems and satisfiability, Boolean functions, and algorithms for solving polynomial systems.

Note that there a lot of research being undertaken out there about post-quantum computing and its use for code-breaking. By using post-quantum computing will be highly likely possible to break any modern cypher, but there is no proof of that yet. The best is yet to come!

Cryptography has raised many human rights issues, ethical issues and also legal issues due to the fact that it can be used for good purposes but also for bad ones. You can read more about this on this post: Cryptography is Everywhere.

With respect to classical algorithms, some can be done by hand allowing to get a a better understanding of what is involved, such as shift cipher, substitution cipher, Vigenère cipher and permutation cipher. Most of them are outdated, however, many ideas are still used as components of modern ciphers and also many of methods of breaking these ciphers are valid for modern ciphers as well, for instance, exhaustive key search, letter frequency and other statistical properties of the text, and known/guessed plaintext.

It is widely agreed that cryptographic algorithms are basically classified into two big categories depending on the number of keys that are used for encryption and decryption, that is, symmetric cryptography and public-key (asymmetric) cryptography. The first one uses only one secret key for encryption and decryption, whereas the latter uses two keys, a public key for encryption and a private key for decryption. This aspect is particularly important when it comes to working on breaking cryptographic algorithms because it is assumed some things in terms of what is available to the attacker such as the algorithm in use and whether the key is the same or not.

Similarly, symmetric cryptography can be classified into two parts: block ciphers and stream ciphers. They mostly recommend using the block cipher AES, and explains the uses of stream cipher in different applications. For example, RC4 for WEP, WAP, SSL, TLS1.2, A5 for GSM mobile phones SNOW and ZUC for 4G LTE, ChaCha20 for TLS1.3. Some big names in cryptography such as Golbreich and Stallings clearly mention in their books the importance of having a good understanding of the different operation modes of symmetric cryptography such as ECB, CBC, OFB, CFB, CTR, and GCM.

Block ciphers and stream ciphers have to face multiple types of attacks such as differential attacks and algebraic attacks, respectively. Also, several works have been done to prevent differential, the cube and the AIDA attacks, many other types of attacks, the vast majority of which are painstakingly detailed in Antoine Joux’s book “Algorithm Cryptanalysis”.

Stream ciphers have strongly relationship with certain concepts such as one-time pad, perfect secrecy, pseudo-random numbers generators, linear feedback, theory about shift registers (LFSR), NLFSR, shrinking generator, T-function, and IV. There is a special book that presents these aspects in a very detailed manner such as Stallings’ book in which he goes much deeper (Stallings, 2017).

Besides, hash functions and message authentication codes (MAC) are also crucial in cryptography. They are used in tandem with symmetric and public-key cryptography to achieve confidentiality, authentication, integrity, non-repudiation. In fact, Douglas Stinson in his book “Cryptography: Theory and Practice” explains clearly and concisely about hash functions and MAC, giving theorems and algorithms along with other related-mathematical applications.

Talking of public-key cryptography, algorithms in this area are classified depending on the number theory they use. For instance, RSA uses integer factorization whereas Diffie Hellman (DH) uses discrete logarithm and Elliptic Curve (ECC) is based on elliptic curves over finite fields. Actually, Antoine Joux explains RSA, DH and ECC from the mathematical and algorithmic cryptanalysis perspective (Joux, 2009). In addition, it is vital to have a very good understanding of number theory when working with public-key cryptography because the implementation of this type of cryptosystem is entirely based number theory, so, for example, breaking RSA is all about finding solutions for integer factorization.

With regard to cryptanalysis, it is all about understanding cryptographic algorithms and finding solutions to break them. In this area, the most famous techniques to attack all the types of ciphers go from the very classical approach to the most sophisticated and modern techniques which make use of algebraic cryptanalysis and mostly based on Polynomial Systems (especially Multivariate Quadratic), Algebraic coding and optimization.

Essentially, algebraic attack is based on the main idea of finding and solving a system of multivariate polynomial equations over a finite field, for example, some algebraic attacks have been successfully carried out against various stream ciphers based on LFSRs. In addition, Gregory V. Bard in his book “Algebraic Cryptanalysis”, details all the mathematical aspects behind it, particularly topics such as Gröbner bases algorithms, linearization, the XL algorithm, complexity calculation, converting ANF to CNF, NP-Complete problem, MQ Problem, linear algebra over GF(2), Boolean matrices, and GF(2)-Matrix Operations.

It's all for now. I do hope to have cleared some things up. If you have any questions please do let me know in the comment section below. Have a good day!

No comments:

Post a Comment

Let me know any remarks or questions you may have. Please write down your name.