History of cryptography behind your cryptowallets
A journey of two enigmatic medieval women trying to share a secret with each other
Could you guess what these women are up to in the picture? That’s right — it’s hard to tell. Cryptanalysis has been trying to crack this 15th century manuscript since it was found in 1912. Even professional cryptographers and historians couldn’t decode it. A number of suggestions has been made, though — all of them proved false or groundless. The best educated guesses were either based on recognition of familiar patterns from other medieval manuscripts or on counting the most frequent alphabetic sequences.
The latter method is called frequency analysis which is a brute force search used to decode substitution ciphers such as the Caesar cipher — a symmetric encryption performed by shifting letter positions in the original message to form a code.
What if two of the women in the picture — let’s call them Agnes and Isabel — wanted to share a secret with each other without anyone else hearing them? Caesar cipher would be the easiest pen and paper solution for them.
It is a monoalphabetic substitution cipher that can be used by simply shifting each letter down the alphabet by any preset number of letters. Because it shifts letters of the same alphabet, the sequences of letters are decipherable by counting each letter and finding the most frequent one. In English, it is highly likely that it would be ‘e’. This is a typical distribution of letters in English according to their frequency.
Knowing what letter ‘e’ has become in the code, we can easily count the positions of other letters.
A slightly more complicated encryption method based on substitution is polyalphabetic cipher which employs mixed alphabets to substitute letters. For example, one of its special cases — Vigenère cipher — was indecipherable for three hundred years. It used a keyword and a table (tabula recta) for encryption and decryption of words.
A keyword, also known as a shift word, is juxtaposed with the text we want to encrypt. Let’s say Agnes and Isabel choose ‘rainbow’ as a shift word. Agnes wants to tell Isabel that all her money is taped to the back of her toilet tank. She copies the word ‘rainbow’ as many times as her text is long:
Allmymoneyistapedtothebackofmytoilettank
Rainbowrainbowrainbowrainbowrainbowrain
Now, to encrypt this sentence using a keyword, she then needs to put letters from the table in place of the original letters. Rows are determined by the keyword, and columns — by the letters in her sentence. For example, to substitute ‘a’ she looks in row ‘r’ under column ‘a’. According to tabula recta, that would be ‘r’. The next letter would be ‘l’, then ‘t’, and so on.
The resulting encrypted text would be — RLTZZAKEEGVTHWGELGPHDVBIPLCBDYBBJZAKTIAL
However, this message would be easy to decipher if one of their friends — Eva — intercepted a letter containing the shift word.
Agnes and Isabel obviously need something more reliable than that.
A new step in encryption was reached in the 19th century with one-time pad which used a similar principle as the previous cipher — but instead of a shift word, a whole sequence of random letters was used that was as long as the original message. One-time pads were a breakthrough in cryptography since they involved the idea of pseudorandomness that Claude Shannon (the father of information theory) called perfect secrecy.
A brute force attack is powerless with one-time pads since it would require processing too many options for a human. For example, for a message of 371 letters there would be a 371-letter key where each character could take 26 values. Therefore, the number of possible keys is 26^371, or 10^525. If we say that one billion computers that can each decode 1018 per second engages in this task, it would take 10^490 years to search through all variants. Tough, ha?
The wars of the past century boosted development of cryptography and not only led to creation of the famous Enigma machines but also inspired a new generation of mathematical encryption, namely asymmetric cryptography.
But first about Enigma machines. Design of these machines was absolutely state of the art development that was still based on the principle of symmetric keys. Combined with the human factor in operation, it was one of the reasons of their downfall. Seriously though — passing the starting positions for the rotors on pieces of paper…
Another important reason was that a letter could not be encrypted as itself — it always had to be another letter.
Today, there are so many solutions to cracking symmetric codes that you can do it online. Therefore, none of those methods is involved in securing cryptowallets. They are protected by a much stronger system of asymmetric cryptography that involves a pair of public and private keys that are used diversely in encryption and decryption.
To put it simply, if one enigmatic woman wanted to send a message to another, with asymmetric encryption, she would use a public key to lock information. To decode the message, her friend would use her private key that corresponds to the public key she received. However, this is a bit more complicated than that.
Diffie-Hellman algorithm solved the problem of Enigma machine — now the keys would not need to be transmitted in physical form (as a list on a paper, for example).
To exchange the keys with the help of Diffie-Hellman method, Agnes and Isabel first need to agree on a prime modulus and a generator. They agree it’s 17 and 3 accordingly. Then Agnes chooses her private number and calculates the generator (3) to the power of 15. She can openly send the result (6) to Isabel. When Isabel gets it, she selects her own random private number. Isabel takes 13. She calculates the generator (3) to the power of 13 with modulus 17 and sends the result (12) publicly back to Agnes.
This is the cunning part. Agnes takes the result she received and raises it to the power of her private number to get the secret message (which is number 10). Isabel takes Agnes’ public result and raises it to the power of her private number and gets the same secret information which is number 10.
They did the same calculation with the exponents in different order (both calculated 3 raised to the power of their private numbers). If you swap the places of the exponents, the result will not change.
RSA uses a key pair of public and private keys where the first is used for encryption and second — for decryption. That is why it is called asymmetric algorithm. It uses a trapdoor function which is a one-way function that is easy to perform but difficult to reverse. In other words, it is a mathematical lock that requires the second one-way function (or special information called trapdoor) to decrypt the message.
First, Agnes and Isabel agree on two prime numbers p and q. Their multiplication gives them the modulus n.
Then, they calculate the totient which is found according to the formula and choose the exponents:
As Diffie-Hellman algorithm, RSA uses modular exponentiation. The public key is generated using the modulus (n) and the exponent (e) which is used for encryption. The private key is generated from the modulus (n) and the secret private exponent (d) which is used for decryption.
Integers used in the calculation are prime numbers, which makes decryption a hard time-consuming task because of the difficulty of factorization of large prime numbers — the so-called factoring problem.
Those are the basic tricks of cryptographic algorithms. Agnes and Isabel, of course, need to be computers to use asymmetric algorithms because of the high computational power required to solve the problem of prime numbers factorization. Although it seems like the enigmatic women from the 15th century were able to hide their secrets so well that cryptographers of today are still trying to crack them, asymmetric cryptography would be an equally reliable solution for them. That is why cryptowallets choose this method to keep your money safe.
