The Series: Quadrans Essentials challenges you with Crypto-Puzzles
Welcome back to the Series: Quadrans Essentials. In this fourth episode of the series, we will be taking a dive into cryptographic puzzles and ciphers.
In the previous articles, we’ve talked about encryption schemes and their usage — now let’s get more practical with a few simple examples of cryptography applied to cryptograms.
Cryptograms are very similar to puzzles, but instead of using shaped tiles, they are usually based on words and letters.
To get to the solution of the cryptogram, users need to understand the correct cipher and find the magic keyword which reveals the information hidden beneath the encrypted text.
Cryptograms are based on ciphers (also called codes) — algorithms that allow to encrypt and decrypt a piece of information by following a well-defined sequence of steps and using well-defined sets of input parameters.
The difficulty of a cryptogram is determined by the complexity of the used cipher and the used parameters. Let’s get started!
Cryptograms
Cryptograms are classified into several categories according to how they can be used to encrypt information. Let’s look at a couple of examples together.
Mono-alphabetic substitution ciphers
The categories of ciphers used in the past were relatively simple, the oldest being substitution ciphers. The principle behind substitution ciphers is elementary: “units of text” (single letters or sequence of them) are substituted with the cipher-text.
In the simplest case of single letter substitution, the cipher-text is a shuffled version of the common alphabet obtained by shifting or mixing it.
We’ve talked about this in the third episode of the Series: Quadrans Essentials titled The Beauty and Magic of Public-Key Cryptography. If you missed it, you can read it here.
Caesar cipher dates back to Roman Age and consists in simply shifting all symbols of the common alphabet by a selected number of steps (rotation number).
In this case, the encryption only makes sense if this number is between 1 and the length of the alphabet minus one.
Who wants to decrypt the text needs to know or guess the rotation number used in the encryption.
Another technique used in mono-alphabetic substitution is called the mixed alphabet. Its principle is very simple: choose a keyword or key-phrase and remove all spaces and duplicate letters from it.
Then, place the result letters of this operation at the beginning of the new alphabet and continue with all the remaining symbols of the alphabet (generally using normal alphabetical order). Just like this:
Poly-alphabetic substitution ciphers
In the 13th century, things started to get a little more challenging with the introduction of a new category of codes — the polyalphabetic substitution ciphers.
The most famous code belonging to this category is the Vigenère cipher.
First described by Giovan Battista Bellaso in 1553, the cipher is easy to understand and implement, but it resisted all attempts to break it until 1863 — three centuries later! Fun fact: in the 19th century, this scheme was misattributed to Blaise de Vigenère (1523–1596) and so acquired its present name.
The code takes up the substitution principle used by the Caesar Cipher, but instead of using a single translated alphabet, it uses a set of them — poly in fact means many in Greek — plus an encryption keyword.
The basic element of the Vigenère cipher is called the tabula recta — a set of rows (26 for the normal Latin alphabet) in which the original alphabet is shifted by one position in each subsequent row.
Then a keyword is used to index the alphabet, among those in the matrix, for the substitution of a specific symbol in the text.
Let’s try and build a Vigenère code step-by-step:
- Compute the tabula recta;
- Select your keyword;
- Create an “intermediate-text” obtained by repeating the keyword for the whole length of the plaintext;
- Use each letter of the intermediate-text to select the alphabet to be used from the tabula-recta, then get the letter of the plaintext occupying the same position and substitute it according to the selected alphabet;
- In the end, the encrypted text is obtained.
Reshaping the world with crypto puzzles
The cryptograms we’ve seen are great brain exercises for human beings, but computers need something more complex to entertain themselves.
One of the most interesting, challenging and as of now high-rewarded cryptograms that a computer would be challenged to solve nowadays was first described by Adam Back in its Hashcash protocol proposal (1997) and known as Proof-Of-Work.
The same cryptographic puzzle was then recalled in the Bitcoin protocol, proposed in 2008 by the mysterious Satoshi Nakamoto, as part of the distributed consensus mechanism.
Let’s see what this is all about in a simple way.
As many of us already know, computer language is made up of “1's” and “0's” (bits) — with the combination of them in sequences of various lengths being able to represent almost any information in digital form.
Thanks to cryptography we are able to compute a unique fingerprint for every digital information, which we call hash. Hashes have some interesting properties:
- They have always a fixed length, independently from the length of the original information from which they are calculated;
- The probability of having the same hash for two different input data decreases exponentially with the length in bits of the hash;
- Even small changes in the input data will result in a very different hash as the output;
- Knowing the output, it is computationally not possible to invert the hash function and find the original input;
Thus, if we compute hashes having a reasonable bit-length (typically 256-bits, 512-bits are used as of today), we can uniquely identify each piece of information in digital form.
Let’s imagine that you are able to grasp the sequences of bits at first sight and calculate their fingerprints (hashes) in a matter of seconds, would you be able to solve this challenge?
Take a well-defined input sequence (block) to which you can add a fixed bytes-sequence (nonce). Find a valid nonce, to be added to the initial data-set, such that the hash of the resulting data (block + nonce) has exactly a given number of leading zeroes. The number of the leading zeros to be reached is the so-called difficulty.
Sounds difficult, doesn’t it? Thanks to properties related to the hashing algorithms there is no immediate mathematical solution to this problem and the only way you can deal with it is to use all of your brute force — computationally speaking of course.
Plus, the problem becomes exponentially more difficult as the requested number of leading zeroes grows.
Disclaimer: no electronic device has been mistreated for writing this article 😊
So even if you are the best and fastest human hash-solver in the world, you won’t stand a chance in this game even with a 30-year-old PC. When complexity grows, this cryptographic puzzle begins to be unsolvable even for most modern powerful PCs.
However, looking at the statement of the problem it is somewhat easy to see that, regardless of the complexity required, counting the number of leading zeros is sufficient to verify the correctness of the solution…
As of now, Bitcoin’s Proof-Of-Work solving process (mining) requires the usage of specialised hardware called miners which use specific electronic chips (Application Specific Integrates Circuits — ASICs) that are designed and intended only for computing hashes as fast as possible.
At the moment of writing, in June 2022, high-end Bitcoin miners are able to compute hundreds of thousands of billion hashes per second (~ 100 TH/s) and absorb kilowatts of electrical power.
The Proof-Of-Work crypto-puzzle is a crucial component of Bitcoin and its combination with other cryptographic primitives, game theory concepts and blockchain data structure makes the magic happen.
Roughly speaking, solving the crypto-puzzle represents a way for miners within the peer-to-peer network to “invest” their computational power in the validity of a new block of the blockchain.
If a miner tries to cheat, other nodes can reject its new block of the blockchain (containing a double spending transaction for example) and all the “invested” power on that version will be wasted. On the contrary, if a miner behaves honestly, it will be rewarded with newly emitted bitcoins.
Bitcoin’s crypto-puzzle was the first to be applied to address the problem of distributed consensus, yet it is not the only one — other ecosystems in the crypto-world like Ethereum, Monero, Dash, and many more make use of slightly modified versions of the original Satoshi’s Proof-Of-Work.
And what about Quadrans?
As described in the Quadrans Yellow Paper, Quadrans 2.0 will use a bit of Proof-of-Work too... All the features of Quadrans innovative consensus algorithm are included in the Yellow Paper, which we encourage you to check out.
But let’s talk about this for a moment with an example involving an object you all know.
You have two Rubik’s cubes at your disposal: the first one is not necessarily solved — let’s call it target; the second Rubik’s cube is not solved and has some missing tiles — this one we call target-prime.
The crypto-puzzle consists in finding the correct colour of each missing tile, such that after a certain number of rotations of the target-prime cube, with no more missing tiles, the result is as similar as possible to the target.
Target and target-prime are two sequences of bytes that are related to the whole context (time, network status, blockchain status) in which the puzzle is executed and that the missing tiles represent the nonce that the solver can add, as we have seen for Bitcoin.
Each rotation you make on the cube represents the execution of a computational-intensive function on the target-prime bit-sequence. Such functions can be chosen pseudo-randomly among a set of pre-defined functions — not a fixed hash function as it happens in Bitcoin.
To check the validity of the solution, count and compare the different tiles at each position of the two cubes — in mathematics, this operation is equivalent to calculating the so-called Hamming distance between sequences of two bits.
So far, then, it would appear that Quadrans’ Proof-of-Work is no different from Bitcoin and is equal in computational intensity… so where does the Quadrans blockchain energy efficiency lie?
Finding out takes a little more patience as we walk this path together, and you will see that all the pieces will fall into place...— some answers will come in the next few episodes of this Series: Quadrans Essentials.
In the meantime, check out Quadrans’ latest Sustainability Report. The report is based on public data extracted from Quadrans Network Status and reveals that Quadrans is a sustainable blockchain that performs energy-efficient transactions.
TIP For code lovers
Let’s play with some Python code! Try the snippets below and have fun modifying them to build complex ciphers ;)
This first snippet implements a Caesar cipher in Python.
Looking at the code, the cipher algorithm is fairly easy to understand: we first rotate the base alphabet by a given number of rotations and then replace each letter in the plain-text with the letter that occupies the same index as that letter in the rotated alphabet.
Next, let us examine the implementation of the mixed-alphabet cipher.
In this case the implementation is similar to that of Caesar’s Cipher.
The difference lies in the way the alphabet is generated. As described earlier, mixed-alphabet ciphers are based on a keyword that is prefixed to the base alphabet.
So, as you can see in lines 15–26, we simply clean up the keyword of duplicates and prepend it to the basic alphabet —being careful to consider only the letters in the latter that do not appear in the former.
Finally, we have the Vigenere Cipher’s implementation.
