Cryptography 101

Topics

encryption decryption aes blockchain bitcoin cryptography 101

Cryptography

A blockchain is a chain of blocks (an array of data) linked together through clever use of cryptography. To truly appreciate the design of blockchain, one is well served by his/her understanding of the cryptographic primitives underlying blockchain.

Caesar Cipher

Most textbooks begin their introduction to classical cryptography with the Caesar cipher. The idea being that the ciphertext is a modified version of the plaintext, where each letter is shifted by a fixed number of places. The shift is determined by the key. Put simply, one replace each letter in the plaintext with a different letter that is a fixed number of places away in the alphabet.

The effect of a left rotation of 3 places can be seen as follows:

Plaintext:  THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

Expressed mathematically, this gives us the following formula for an encryption:

And the following formula for decryption:

This is a very simple encryption scheme named after Julius Caesar, said to use it with a right shift of three ( ) to protect messages of military significance.

2000 years larer, fugitive Mafia boss Bernardo Provenzano (capo dei capi, "the boss of bosses") uses a variation known as the pizzini code which right-shift each letter by three places before replacing each letter with numbers corresponding to the new position. One such note (out of at least 350 recovered) read "I met 512151522 191212154 and we agreed that we will see each other after the holidays..." (decoded as "Binnu Riina"). Provenzano is perhaps the most elusive fugitive of the Mafia, having evaded capture several times after being involved in two high-profile bombings that killed prosecutors, eliminating rival bosses and having spent 43 years living as a fugitive.

In 2011, Rajib Karim was convicted in the United Kingdom of terrorism offences after using the Caesar cipher to communicate with Bangladeshi Islamic activists discussing plots to blow up British Airways planes.

If he had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the fourth letter of the alphabet, namely D, for A, and so with the others.
Life of Julius Caesar Suetonius

The focus of the following sections are on modern ciphers and cryptography. Broadly speaking, we can classify modern cryptography into one of two forms: symmetric and asymmetric cryptography.

Symmetric cryptography

Also called secret key cryptography or shared key cryptography, symmetric cryptography uses a key to encrypt the data and the same key for decrypting the data. This key must be agreed on before the data exchange take place between the communicating parties.

To understand this, move onto the first experiment to see how we can use the XOR Cipher to build a simple cryptography model that provides an encryption / decryption service. Since computer store text as numbers, our plain string

Experiment 1

The XOR Cipher is one of the most common cryptographic technique that sits right at the heart of many modern day ciphers
XOR is a logical operator, which transforms binary digits through an "Exclusive OR" filter ("logic gate", with the symbol ⊕)
Each key on the keyboard is already represented by a number known as the ASCII code. Since there's 8 bits to a byte, this means each key is a combination of 8 binary code. This includes characters accented characters such as é even if such a character key may not be present on your keyboard

Instructions

Go ahead and write a plain text message (keep it to within 12 characters for this exercise). This may be a keyphase to your security safe somewhere, or it could be a secret code to a vault that nobody else should have access to.
Now, enter an 8-bit binary key, which in layman terms, mean a string of 8-digit 0s and 1s. This key is used to perform the XOR cipher, and nobody else should know this key except for its intended audience (sender and receiver).
Notice how your string is first converted into ASCII, and then its binary representation. When you hit encrypt, the XOR Cipher is performed, resulting in our cipher text. We can thus mail this message out over an email service, chat provider, or just any other communication medium ("channel").
The intended receiver of this cipher text would have the key you entered in (3), allowing him/her to perform the XOR cipher, in effect reversing the encryption process. This decryption process works because XOR is an involutory function, or "self-inverse" function. Any other person (whether a malicious adversary or not) might intercept the message but would have to also know the key in order to correctly decipher the mssage or risk entering an incorrect password.

As we've seen from the experiment above, symmetric cryptography ("secret key cryptography", "shared key cryptography") requires that the sender and receiver have agreed on the key. Once that is established, it did not matter that the adversary have undesired knowledge of other pieces of the encryption algorithm because they would still need to expend considerable effort into decrypting the message without knowing the key. In the experiment above, we could have chosen for the hexadecimal notation instead of ASCII representation as they also, conveniently, provides a one-to-one correspondence between the hex digit and a 4-bit string ("nibble"). The adversary, having learned of this, would still require knowledge of the key or resort to using other methods such as through a brute force algorithm.

Block ciphers and stream ciphers are two categories of symmetric cryptography. Popular examples of block ciphers include the Data Encryption Standard (DES) and Advanced Encryption Standard (AES), the latter of which is used by Bitcoin Core (and many other cryptocurrency services) to encrypt its wallet.

Asymmetric cryptography

In the experiment we see earlier, the sender and receiver has to first establish and agree upon a key in advance. Therein lies a problem: what if the sender's message gets intercepted, along with the key, in its transmission to the receiver?

In 1977, Ron Rivest, Adi Shamir and Leonald Adleman proposed the RSA algorithm, and with it, the use of two different keys: one for encryption and the other for decryption.

Private key is a randomly generated key used to decrypt messages and is held privately by the user. In RSA, a private key of 1024-bit or 2048-bit is used, while other asymmetic cryptography schemes may choose different lengths.
Public key is the counterpart of a private-public key pair that is published by the key owner to be known publicly. Anyone wishing to send a message to the key owner do so by encrypting the message using the published public key before sending it. For each encryption key, there would only be one corresponding decryption key.
Nobody else is capable of decrypting the message as long as the corresponding private key is kept securely by the intended recipient.

Supposed Alice would like to receive private messages from her friends, she could generate two keys: public and private. She could then broadcast her public key to her friends, and each of her friends would then be able to encrypt messages using her public key to her friends. It doesn't matter if the public key is known by anyone who is not the intended recipient, as long as the private key is kept secret. Support Bob, a friend of Alice would like to send a message, Bob would first encrypt the message using Alice's public key, and then send it to Alice. Again, it does not matter if the message was intercepted by anyone who is not the intended recipient, since the private key is kept secret and hasn't left Alice's computer -- and only the private key can decrypt the message.

RSA Algorithm

Can the reader say what two numbers multiplied together will produce the number 8,616,460,799? I think it unlikely that anyone but myself will ever know.
Principles of Science, 1874 William Stanley Jevons

If you're wondering, the answer to Jevon's number is 89,681 and 96,079 as factored by Charles J. Busk in 1889.

You can try and do a quick experiment by picking two prime numbers, let's say 29 and 43.

1,247 isn't exactly a difficult number to factor (it should still take a person with a calculator a respectable amount of time), but when a sufficiently large prime number such as 6,284,963 is presented then this is a much harder problem.
When you start to consider finding the factors of the number 35,452,590,104,031,691,935,943, we're now exceeding the limits of what computers can handle in any reasonable amount of time.

RSA builds on the idea of what is known as the integer factorization problem, which states that the multiplication of two large prime numbers is easy but factoring (returning it back to two original numbers) it is computationally difficult. Prime numbers, as you may recall from Math class, are numbers greater than 1 with exactly two factors, 1 and itself (e.g 2,3,5,7,11,13...). Another idea we'll borrow from number theory is Euler's function, which is described below.

Euler's Totient Function

Theorem: if is prime, and is any positive integer, then .

For quick reference, here's a handy table:

integer n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
φ(n)	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8

because there are 4 positive integers less than 8 that are coprime to 8, i.e 1, 3, 5 and 7 shares only a factor of 1. 6 is not included because it shares a common factor of 2.
because the distinct prime factors of 20 are 2 and 5; half of the integers between 1 and 20 are divisible by 2 (leaving ten), and from the remaining odd numbers, two out of ten are divisible by 5 (5, 10, 15...) so 20-10-2=8. - The co-prime of 20 is hence 1,3,7,9,11,13,17,19. Notice that 9 is included because it doesn't share a factor with 20 that is greater than 1.

The points at the top line that looks linear represent when is a prime number, which works out to be . Since prime numbers have no factors greater than 1, . In other words, all integer between to are co-prime to .
Another interesting fact is that the Phi function is also multiplicative: if P and Q are co-primes. So if we know is a product of two primes and , then .

RSA Key Generation

An RSA key pair is generated in the following procedure:

Select and , two large prime numbers.
Multiply and together to get .
Let . This is known as the Euler Totient Function, which we explored above.
Choose two numbers, and , such that . is for encryption (the public key), and is for decryption (the private key).
1. and must be coprime to , and must be less than .
Publish and as the public key, and keep as the private key.

Let's begin by picking two prime numbers; let's say 3 and 11. Following the procedure above,

and are 3 and 5 respectively.
= 3 * 11 = 33
Since and must be co-prime to , and must be prime and less than (20) and not a factor of ,
1. the candidates for are 3,7,9,... (greater than 1, less than 20)
2. 2, 4, 6, 8, 10 are ruled out because they are not co-prime to 20 (they have shared factors).
3. If we pick 3 from the candidate pool above, possible values of , such that it satisfies , is selected. 7 qualifies (7 * 3 mod 20 = 1).
4. We hence pick 7 for and 3 for
Publish (3, 33) as the public key, and keep (7, 33) as the private key.

Experiment 2

Encrypt a Message with RSA

Decrypt a Message with RSA

RSA in Practice

Be reminded that calculating is easy but the inverse is very difficult for a sufficiently large number of . The problem becomes easy, if we are able to factor into a product of two primes, using what we've learned in Euler's Totient Function.

In practice, a modulus of size in the thousands is not feasible to factor, and we often pick a value such as 1,024 bits (309 decimal digits). A large number allow us to encode a full-length message in a single block, convert it to hexadecimal and then convert it into a decimal.

Often, we also generate a random session key and use that to encrypt the plaintext with a computationally efficient, symmetrical algorithm like DES or AES-128. We then use the more computationally expensive public key encryption algorithm to encrypt the session key.

The receiver, upon receiving the packet, decrypts it with the private key ((d,n)) and in turn, uses the session key that was extracted to decrypt the ciphertext for the plain text message. The transmission may include in plaintext details of the encryption algorithm, encoding, zero-padding, and other details. As long as the secret key is kept private by the intended recipient, only the receiver can decrypt the message.

A note on modern cryptography

At this point, I should stress that the XOR Cipher experiment you've seen are merely illustrative and greatly simplified for pedagogical reasons. With a longer input (eg. plain text), our key would now have to be repeated such that patterns may emerge to any adversary. If the key is exactly of the same length as the input, then there would be no repeats (one-time padding), meaning that with sufficient randomness and key length, the XOR that we implemented would still present a rather formidable challenge.

Almost all of modern ciphers (including AES, Keccak and SHA-2) feature the use of XOR Cipher as a key component but techniques such as permutations and confusions lend the algorithm other much-desired features that we will discuss in details in the following section.

In the second experiment, I've implemented an RSA algorithm with e, d and N being 29, 41 and 133 respectively. This is grossly insecure, but with sufficiently large prime numbers, our experiment is a good example of how modern cryptography is built. Over the years, cryptographers have created new challenges in this field, leading up to the 617-digit RSA-2048, which isn't thought "to be factorizable for many years to come" unless enormous advances are made in computational power or algorithms / number theory. As of this writing, only up to RSA-250 (250 digits) has been factored (February 2020) using approximately 2700 CPU core-years on a 2.1GHz Intel Xeon Gold 6130 CPU.

The factoring of RSA-200 (200 decimal digits) by a collection of parallel computers took approximately the equivalent of 75 years of work for a single 2.2 GHz Opteron-based computer. The factoring of RSA-768 (232 decimal digits) by a collection of parallel computers took approximately the equivalent of 2,000 years of computing for the same computer.

RSA-250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447
          1401366433455190958046796109928518724709145876873962619215573630474547705208
          0511905649310668769159001975940569345745223058932597669747168173806936489469
          9871578494975937497937

RSA-250 = 6413528947707158027879019017057738908482501474294344720811685963202453234463
          0238623598752668347708737661925585694639798853367
        × 3337202759497815655622601060535511422794076034476755466678452098702384172921
          0037080257448673296881877565718986258036932062711

RSA-260, RSA-270 and onwards have not been factored so far.

Another thing to note is that as long as advances in computing hardware along with availability of computational power do not catch up with the magnitude of the cryptographic puzzles, we can have good faith in the security systems of modern cryptography. In any case, scaling the difficulty of math problems a computer need to solve is certainly a lot more attainable than scaling the computational power of a computer.

In practice, we use a modulus of size in the order of 1024 bits. That is over 300 decimal digits.

Hexadecimals

Text to Hexadecimals

Supposed we'd like to substitute parts of the Experiment 1, to use Hexadecimal instead of ASCII, we will first convert our plain text into hexadecimal, and then perform the hexadecimal-to-binary conversion before applying the key to product our cipher text.

To illustrate, a input of (plain text) of Supertype will output 53 75 70 65 72 74 79 70 65. The first character of the hex 53 will output a binary of 1010011, and so on and so forth.

The mapping of 53 to 1010011 isn't arbitrary. The 5 in Hex correspond to the 4 binary digits 0101 and the 3 correspond to 0011. Together, they form 01010011, and without the leading zeros that would be 1010011.

Note that the hex value of the uppercase S symbol is 53 but the lowercase s is 73.

Decimal to Hexadecimal

Hexadecimal is also a way of storing integers in base 16 rather than the usual decimal base that we commonly use. We commonly use a 10-digit system, but with hexadecimal we have 16-digit -- the numbers 0 through 9 as well as the letters A through F. These 16 hexadecimal digits correspond to a different value in the range of 0 to 15. As mentioned in the earlier section, each hexadecimal digit also has a one-to-one correspondence to a 4-bit binary string. These correspondences, as we've also learned above, are not arbitrary. 5 in in Hex correspond to the 4 binary digits 0101 and the 3 correspond to 0011.

To compute from the 4-digit binary to decimal, we take the sum of binary digits () multiplied by :

The letter E, with the binary string of 1110 is hence .

So in the case of our familiar base 10 decimal system, each position of a digit has 10 times the value of the previous position, in the binary each position of a digit has value 2 times that of the previous position. In hexadecimal, each position of a digit has 16 times the value of the previous position. We can therefore expand on the examples and perform a hexadecimal-to-decimal conversion.

Hexadecimals are often prefixed with 0x to indicate that it's in hexadecimal format. When we see a hexadecimal like 0x20, the arithemtic we perform would be .

To convert the hexadecimal 0xDE we would apply the same formula, noting that D and E correspond to 13 and 14 respectively:

We can also very quickly refer to the table and see that D corresponds to 1101 and E corresponds to 1110, giving us a binary of 11011110.

Private Keys in Hexadecimal

A randomly generated private key for Bitcoin is a 256-bit (32 bytes) number, or 64 characters in the range of 0-9 or A-F. They are 256-bit numbers randomly chosen in the range specified by the secp256k1 ECDSA curve recommendation. An example private key is:

E9873D79C6D87DC0FB6A5778633389F4453213303DA61F20BD67FC233AA33262

Nearly every 256-bit number is a valid ECDSA private key. Specifically, any 256-bit number from 0x1 to 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140 is a valid private key. This is due to the requirement of the key being smaller than n, the size of the group specified by ECDSA. There is a small space of numbers that fit within 256 bits but is greater than n. So the private key space is (or ), an astronomically large amount. The visible universe is estimated to contain 10^80 atoms.

AES

Vincent Rijmen and Joen Daemen submitted an entry to the National Institute of Standard and Technology's (NIST) competition to select an Advanced Encryption Standard that would replace DES. Their submission won and was thus selected as the Advanced Encryption Standard.

Depending on the key sizes (128, 192 and 256 bits), we get different variants of AES. All three variants use a 128-bit block size, which means it produces 128 bits of cipher text along with a key from a given 128-bit of input message.

16 bytes (128 bits) conveniently fits a 4x4 grid, and AES hence uses a 4x4 column-major order matrix as representation for its internal state ("state array").

Supposed the message is "SupertypePowered", the hexadecimal would be 53 75 70 65 72 74 79 70 65 50 6f 77 65 72 65 64 and the state array would be:

The encryption process begins by bringing in the initial key (AddRoundKey) and perform the XOR. Since the rest of the algorithm are rather publicly documented, this operation is what actually provides the "secrecy" to our algorithm. This is also the only phase of AES encryption where the key is directly used. After the initial round, the AES Key Schedule produces a set number (10, 12, or 14 for the 128, 192 and 256-bit variants respectively) of round keys from the initial key ("Key Expansion"). These round keys are used as input to the AddRoundKey operations and so a different key is used for each round.

When we start doing our rounds, we begin with (1) confusion through substitution of bytes (SubBytes), and (2) perform permutations by shifting the rows (ShiftRows) and mixing the columns (MixColumns).

SubBytes are performed following the table below. For the first value in our 4x4 matrix (state array), that's 53 (S). Running it through the S-Box would transform this value from 53 to ED (í in ASCII). The last value d, put through SubBytes would be C in ASCII.

This table isn't arbitrary either. It implements multiplication in Galois Field . This is a non-linear function, which is a great property for a cipher; In addition to that, no bytes would result in itself from the substitution and there are also no directly opposite substitutions (meaning all the bytes are switched).

ShiftRows shifts each row to the left by a value corresponding to their row index. The top row is not shifted, and each subsequent row shifted by an increment of one:

Similar to ShiftRows, MixColumns also jumbles the input around but it splits the 4x4 matrix by columns instead of rows. But since this is an iterative process, one round would involving substitution of bytes followed by mixing row-wise in conjunction with column-wise and finally the round key XOR. This would go on for 10 rounds, using 10 different round keys.

One detail here in the MixColumns process is that this multiplication operates independently over each column, so the first column is multiplied by the matrix as per Galois Field to produce resulting first column, and so on and so forth. The resulting 4 columns are concatenated to form the output of a 4x4 matrix.

When permutations is used, its effect is that the adversary must intercept a sufficiently large amount of message to assemble a statistical structure ("pattern"), since its observability is very limited in blocks of very small probability.

Confusion on the other hand mixes the secret key into the state (AddRoundKey and SubBytes operations), and its use of the key schedule also underlines the confusion concept. As we think about it, this is a public, well-documented algorithm meaning an adversary can go from cipher text to plain text by reversing the process if not for the presence of the secret key we incorporate to perform the XOR operation. The confusion and permutations that is incorporated nonetheless make it such that any small change (uppercase S to lowercase S) would result in large changes.

Since AES has become a standard, most CPU hardware and chip vendors have built-in instructions to perform AES and these are implementations that are incredibly efficienct and fast.

The reference of the Bitcoin source code provides implementations of both a node and a wallet. Its implementation of the wallet uses AES-256 and is called crypto/aes. Encryption however isn't part of the Bitcoin protocol as its akin to a public, distributed ledger and data flows within the network unencrypted.

In the Practice Exercises section, you will be asked to perform one of these on your machine.

Knowledge Check

Practical Exercises

Use the XOR Experiment set up above, paste the following value into the plain text field and observe the relationship between the input, the ASCII and the Binary. Compare this to Wikipedia's ASCII control code chart to strengthen your understanding of this subject

You can perform an AES encryption using tools that are probably shipped with your machine already (Linux, MacOS, Windows 11+). If you are on a Linux machine, chances are that OpenSSL is already installed for you (installation guide for Windows 10 and earlier here). Proceed to run the following command (replace LICENSE with a sample text file)

openssl enc -aes-256-cbc -in LICENSE -out tmpmessage.bin
# to convert binary to readable text
openssl enc -base64 -in tmpmessage.bin -out tmpmessage.b64
# print the message
cat tmpmessage.b64
# results: U2FsdGVkX1/Xb7z+bv9Z9ePRO8Jz74JQQEjwCGr0zoSjX1AP6z1H+yqgOFWBKSJwfEvqk1wu1e5Cur3BQAkRCvF1lA2nazXWxsO66d/yn06F4liaziT682zOW7FdfN23hQja1OQMX+DQ7g4S3jamH/VIxR4AkABxlxHR3VMnUxtU2niWMKgne/t+8JHz8cvNSEI1dDk4yvudmypcBImpSrqrJwFq0Q3HjLq9AnYoi0vxlykdSvPE55kqxXrLKUKUWxEu08qJEJE/7izgIyRLwwhigYrpYejRIzWlcluTS9N0EOulQh9Xsuomsxabd4AqgAw8kJwdM7bhaUrtmQk4uJ9ToknxXnXbR1/1

In the following editor, change secretNumber and observe the change in values for encrypted and decrypted. Notice that the encrypted value is different from the original message, but the exact same formula when applied with the corresponding secrete key, result in the original message. You can do this for any valid private-public key pair.

const keys = { publicK: 5, privateK: 11, n: 14};

let {publicK, privateK, n} = keys;

// CHANGE secretNumber to a number between 0 and 13
// must be a number smaller than n
let secretNumber = 2;

const formula = (x, key) => x ** key % n;
let encrypted = formula(secretNumber, publicK);

const elem = (<div>
    <h4>Original Message: {secretNumber}</h4>
    <h4>Encrypted: {encrypted}</h4>
    <h4>Decrypted: {formula(encrypted, privateK)}</h4>
</div>)
render(elem)
const keys = { publicK: 5, privateK: 11, n: 14};

let {publicK, privateK, n} = keys;

// CHANGE secretNumber to a number between 0 and 13
// must be a number smaller than n
let secretNumber = 2;

const formula = (x, key) => x ** key % n;
let encrypted = formula(secretNumber, publicK);

const elem = (<div>
    <h4>Original Message: {secretNumber}</h4>
    <h4>Encrypted: {encrypted}</h4>
    <h4>Decrypted: {formula(encrypted, privateK)}</h4>
</div>)
render(elem)

You can generate a private-public key pair using the following command. Pay special attention to how the public key is derived from the private key due to their mathematical relations.

openssl genrsa -out private.pem 1024
# Generating RSA private key, 1024 bit long modulus (2 primes)
# .................................+++++
# ...+++++
# e is 65537 (0x010001)
openssl rsa -in private.pem -pubout -out public.pem
# output: 
# writing RSA key
# Use `cat` to view the content of our keys:
cat public.pem

And an example output of public.pem:

The .pem extension may make you feel uneasy but it's just a text-based file (it is short for "Privacy Enhanced Mail", initially intended for secure email services).

You could have used .txt instead for this exercise but PEM is a standard format for encoding keys and certificates.

Similarly, in the code examples below you may come across .enc for the first time. This is just a file extension for encrypted files. You can use cat to read the content of the file;

You can then use the following command to encrypt/decrypt a message:

# encrypt with public key
openssl rsautl -encrypt -in message.txt -out message.enc -pubin -inkey public.pem

# decrypt with private key (note: -inkey is the same as -in)
# use pkeyutl to decrypt the message
openssl rsautl -decrypt -in message.enc -inkey private.pem -out message.txt

Knowledge Check

What would be the right decimal value for the hex of 0x22B?

Given the following private key, and this encrypted message, what is the decrypted message (plain text)? Note: you need to keep the line that says ----BEGIN RSA PRIVATE KEY----- as well as the ----END RSA PRIVATE KEY----- at the end of the lines.

Cryptography in Blockchain

Cryptography 101

Topics

Cryptography

Caesar Cipher

Symmetric cryptography

Experiment 1

Instructions

Encryption

Binary Key

➡️ Byte-size Binary Key

Decryption

Asymmetric cryptography

RSA Algorithm

Euler's Totient Function

RSA Key Generation

Experiment 2

RSA in Practice

A note on modern cryptography

Hexadecimals

Text to Hexadecimals

Decimal to Hexadecimal

Private Keys in Hexadecimal

AES

Knowledge Check

Practical Exercises

Knowledge Check