Introduction to Cryptography: Road to Bitcoin Smart Contracts #2

Objective

This article hopes to: 

1) Provide an introduction to cryptography in a manner that is self-contained.

2) Explore cryptographic concepts and problems through visual aids without assuming advanced knowledge of the mathematics underlying the subject. 

Hear the Mathematics

Math is similar to music. 

Very few individuals have the experience and skill necessary to interpret the sound, emotion, or impact of a song from sheet music. 

For a vast majority, music must be played! To hear and feel the song is to understand the piece and its significance. 

Math can be very difficult for many individuals to interpret if it is presented in standard symbolic notation. Thus, math must be “played” via illustration for a vast majority of individuals to “hear” the mathematics. 

In the Road to Bitcoin Smart Contracts article series, we will attempt to “play” the mathematics whenever possible in order to help you better understand the formal mathematical and technical details. 

For those who would like to follow along with greater emphasis on symbolic mathematical notation, some good resources that supplement this article (and can easily be found online) are:

• Chapter 1 in An Introduction to Mathematical Cryptography by Hoffstein 2014 [1]

• Chapter 1 in Understanding Cryptography by Paar 2010 [2]

Secrets and Privacy

Secrets

Have you ever kept a secret hidden from your family or friends? Most, if not all, of us will answer “yes” to the aforementioned question. Indeed, the framing of such a question may sound anywhere between silly to conspiratorial or even downright sinister; however, secrets are not inherently negative. Let us provide an operational definition of secret that will help inform our later conversation involving cryptography:

Secret: A piece of information that is known to one party and is unknown to another. 

Using this definition, we see that all information that is asymmetrically shared is essentially a composition of secrets. 

Suppose Alice and Bob are best friends. Alice knows that Bitcoin exists while Bob does not. Under our definition, in relation to Bob, Alice knows a secret that is shared amongst all other individuals who are aware of Bitcoin’s existence. The knowledge of Bitcoin’s existence is asymmetric in Alice’s and Bob’s relationship.

Secrets shift our worldview. Take Alice and Bob once more. How different are Alice’s and Bob’s worldviews? However far you have fallen down the Bitcoin rabbit hole, you are able to empathize with Bob: at one point in time, Bitcoin was a secret between a group of individuals – and you were not in that group. Alice’s worldview is fundamentally different than Bob’s because of all the secrets she holds that he does not and vice versa.

What are the values of secrets?

This question motivates the remainder of this section where we explore privacy as well as the consequences of a lack of privacy.  

Privacy

We can adjust the International Association of Privacy Professionals’ definition of privacy to better fit our definition of secret: [3]

Privacy: The right to hold a secret with freedom from intrusion or interference.

In essence, privacy is a promise that you are able to keep secrets without punishment. Privacy entails that you do not have to notify everyone around you of what you are thinking and what you know at all times. It provides us the ability to select which thoughts and feelings we want to express and to whom we want to express them. 

Now that we understand the general concept of privacy, let us delve deeper into more formal definitions of privacy rights. William Prosser defined four privacy rights in his 1955 book entitled Handbook of the Law of Torts: [4]

1. Intrusion upon a person’s seclusion or solitude, or into his private affairs.

2. Public disclosure of embarrassing private facts about an individual.

3. Publicity placing one in a false light in the public eye.

4. Appropriation of one’s likeness for the advantage of another

To expand on Prosser’s privacy rights, the first right refers to the right of a person to be alone or conduct actions without the knowledge of others. In essence, a person has the right to keep secrets using our definition of the word. Prosser’s second and third rights protect individuals from analog or digital doxing. The fourth right protects against identity theft in the broadest sense. 

Prosser’s privacy rights are not in themselves complete and create more questions than they answer. For an entire review of Prosser’s privacy rights as well as more modern approaches to privacy theory, see DeCew 2018. [5] 

Consequences of a Lack of Privacy

Like running water and stable electricity, the value of privacy is constantly taken for granted when it is present. In order to better understand the value of privacy, we will analyze a recent event where privacy has very clearly been taken away from individuals. 

As Hong Kong protests continued throughout June 2019,6 many protestors were forced to switch to analog measures in order to avoid being tracked by the Chinese government. With the implementation of several severe cybersecurity laws and facial-recognition software by the Chinese government in 2018, Hong Kong protestors were forced to adapt: wearing masks and umbrellas to block cameras, disabling location tracking on smartphones, and completing purchases with cash. 

During the protests, digital privacy was largely disrupted by the surveillance of the Chinese state. Just the knowledge of the potential of being digitally tracked forced the protestors into behaviours that would otherwise appear odd in a different context. For example, why would you pay with cash if you could just use the more efficient Octopus smart card? 

Excluding all of the human rights and legal issues that arise when privacy is explicitly taken away in such a form, perhaps the greatest and most negative consequence of a lack of privacy is the way in which a lack of privacy contains the way people think and, in turn, behave. 

An open question to drive further exploration: If you knew that all of your Google searches were being tracked by a state and the wrong search would have severe negative consequences on the life of you and your family, how would that limit your ability to think and express yourself? 

One-Way Functions

How do we ensure privacy and secure communication in a digital space? This question motivates us to look towards mathematics, specifically cryptography, for a solution. 

What is a Function?

In mathematics, mappings (more commonly known as functions) can be defined in the following manner: 

Mapping (Function): A relation between an input to an output. A mapping can be more easily understood as an action that transforms an input into an output. 

This definition may be confusing to some of you so we will clarify it with an unexpected example:

Get a single blank paper. Lay out the blank paper in portrait and write “Front” on one side of the paper. Now flip the paper along its length and write “Back”. Looking at our definition, the input is the front of the paper. The output is the back of the paper. The flip alongside the length is the relation between the front and the back of the paper. We have created a mapping:

g : F—>B

where F is the front of the paper, B is the back of the paper, and g is the flip alongside the paper’s length that maps the front of the paper to the back of the paper. The above notation can be read as g is defined (“defined” is represented by the colon) as a mapping from F to B. 

Now, let us define the inverse of a mapping:

Inverse (of a Mapping): Suppose g is a mapping from F to B i.e g : F—>B

The inverse of g denoted g^-1 is the following mapping:

g^-1 : B —> F

In essence, the inverse of a mapping is 1) itself a mapping and 2) is the relation between the output and the input of the mapping.  

For clarification, we will continue with our paper-flipping example. Ensure that you are looking at the front of your paper. Flip the paper along its length so that you are now looking at the back of the paper. You have now performed the mapping g. Flip the page once more. You have now performed the mapping g^-1. 

In this example, g and g^-1 are the same mapping: they are both a flip along the length of the paper. This is not always the case for mappings as we will see in the next section: some maps do not have inverses that are easily performed or computable.

One-Way Mappings

In mathematics, one-way mappings can be defined as follows:

One-Way Mapping: A mapping where it is very easy to compute the output from the input, but it is very difficult to compute the input from the output. In essence, a one-way mapping is defined as a mapping whose inverse is extremely difficult to compute or perform in a short period of time.

Let us go back to our paper-flipping example once more. Imagine that you have a shredder, and you shred your piece of paper. Again, we have created a mapping:

s : W—>P

where W denotes the paper when it is whole, and P denotes the paper when it is in tiny pieces. The mapping from W to P is s which denotes shredding the paper.

What is the inverse of s (i.e., s^-1)? Let us look at the notation for a clue:

s^-1 : P—>W

where again P denotes the paper when it is in tiny pieces, and W denotes the paper when it is whole. We see that the mapping from P to W is s^-1. Thus, s^-1 must be a relation (or action) that takes the tiny pieces of shredded paper and turns them back into the whole page.

So, we see that s^-1 can be something like gluing or taping together the fragments of paper so that they identically match the whole page we had before we shredded it. If the shredding was completed successfully, putting back together the whole page from the shredded pieces would take an enormous amount of time. Thus, shredding paper can be seen as an example of a one-way mapping.

In mathematics, trapdoor mappings can be defined as follows:

Trapdoor Mapping: A one-way mapping where it is very easy to compute the output from the input, but it is very difficult to compute the input from the output unless you know the “trapdoor” (a special piece of information). In essence, a trapdoor mapping is defined as a mapping whose inverse is extremely difficult to compute or perform in a short period of time unless one has special information that is typically kept secret.

We will thoroughly explore examples of Trapdoor Mappings in the following section on cryptography. 

Cryptography

Principal Goal of Cryptography

The principal goal of cryptography is to allow two or more parties to exchange confidential information with one another in a manner where even if the message is intercepted by an adversary, it cannot be understood. 

Cryptography Understood via a Contrived Example

Alice and Bob are students working together on a competitive group project that awards a large cash prize to the winner. Eve is a member of a competing group. Due to the competition rules, you are unable to leave your desk, but you can pass written notes to your group members. Unfortunately, Alice and Bob are unable to sit beside one another as Eve has taken the desk between them. 

Thus, every message passed from Alice to Bob or from Bob to Alice must be transferred via Eve who has an incentive to look at the message.

In order to keep their group work confidential, Alice and Bob must use an agreed-upon mechanism to disguise their messages so that Eve cannot understand what they wrote even if she reads it. 

This contrived example captures the motivating question behind cryptography: how do we secure communication and ensure private conversations on public channels? We will spend many articles exploring answers to this question and how they relate to Bitcoin smart contracts. 

Now, let us turn to some basic definitions that we will heavily rely on as we continue our discussion of cryptography:

Basic Definitions

Cipher: a mapping from plaintext (input) to ciphertext (output) or vice versa. A cipher can be understood to be the algorithm or method used for enciphering/deciphering messages. 

Plaintext: the message to be transmitted or stored.

Ciphertext: the disguised message.

Key: a secret piece of information used with the cipher to convert plaintext to ciphertext or vice versa. 

Encipher: to convert plaintext into ciphertext via the key. 

Decipher: to convert ciphertext back to plaintext via the key.

Let us return back to our contrived example with Alice, Bob, and Eve. Suppose Alice and Bob want to exchange the following message during the group project:

Plaintext: “LETUSBUILDAROCKET.” (Let us build a rocket)

Of course, Alice and Bob do not want to share this idea with Eve who they are competing against. Luckily, Alice and Bob agreed upon a shared key prior to the event that they can use to encipher the message so that even if Eve looks at the message, she cannot understand it. 

The cipher and key that they agreed upon is to shift each letter (cipher) in the message by one letter (key) down the alphabet. So, to encipher the message:

• A becomes B

• B becomes C

• C becomes D

And so on until,

• Z becomes A

Thus, the disguised message using this cipher and key is:

Ciphertext: “MFUVTCVJMEBSPDLFU.”

When Eve receives this message, she will be very confused for one of two reasons: 1) she does not know the cipher i.e., the method of enciphering/deciphering, and has no idea what algorithm to use to decipher the ciphertext or 2) even if she knows that Alice and Bob are shifting letters to disguise their message, she does not know by how many letters (i.e., the key) they have shifted the original message. 

This cipher is an example of a trapdoor mapping: if one does not know the key, it is very difficult to convert the ciphertext into plaintext.

Practice Problem 1: For those with too much time on their hands, try to decipher the ciphertext below. For context, the cipher that we have used to disguise the message is the same cipher (i.e., shifting of letters) that we used above but with a different key (i.e., number of letters that we shift by). 

Ciphertext: “QXFJANHXD.”

The solution to this problem can be found in the Solutions to Practice Problems section.

For those who have attempted Practice Problem 1, you have suffered through the pain of finding the inverse of a trapdoor mapping without the “trapdoor” or key. If you knew the key, you could decipher the ciphertext in an instant. Without the key (and particularly without a computer), this can take quite a long while to accomplish.  

Admittedly, there are many cryptographic attacks that can be performed on such a simple encryption scheme; this scheme is most definitely not considered to be secure by modern cryptographic standards. We will explore cryptographic attacks as we delve deeper into the specific cryptographic system that underpins Bitcoin. 

Introduction to Private-Key (Symmetric) Cryptography

In both Practice Problem 1 and the extended example with Alice, Bob, and Eve in the previous section, we demonstrated examples of Private-Key (Symmetric) Cryptography. 

Overview

Private-Key (Symmetric) Cryptography requires both parties, Alice and Bob, to share a secret key prior to exchanging messages. This method is called symmetric because both Alice and Bob have the same level of knowledge of the secret key.

General Setup

1. Bob and Alice share a secret key k through a private channel.

2. Bob wants to send a plaintext message m to Alice in a secret manner so that an eavesdropper, Eve, cannot understand the message. 

3. Bob enciphers the message with the shared secret key. I.e., the plaintext turns into ciphertext c. 

4. Bob sends the ciphertext to Alice through a public channel. 

5. After receiving the ciphertext, Alice deciphers the ciphertext into plaintext via the key. 

6. If the procedure is conducted properly, Eve cannot know the key, cannot guess the key, or cannot convert the ciphertext to plaintext without knowing the key.

Some examples of Private Key Cryptography include: 

• Caesar Cipher (Practice Problem 1) 

• Vigenère cipher

• Advanced Encryption Standard

• Data Encryption Standard

Introduction to Public-Key (Asymmetric) Cryptography

Overview

Public-Key (Asymmetric) Cryptography does not require both parties, Alice and Bob, to share a secret key prior to exchanging messages. In Public-Key Cryptography, Alice has her own secret key and Bob has his own secret key. When combined together by some mathematical operation, these two private keys form the shared secret key. This method is called asymmetric as Alice and Bob have different levels of knowledge of the shared secret key. 

General Setup

1. Bob and Alice do not share a secret key through a private channel.

2. Alice has her own secret key a.

3. Bob has his own secret key b. 

4. Bob wants to send a plaintext message m to Alice in a secret manner so that an eavesdropper, Eve, cannot understand the message. 

5. Bob enciphers the message with his secret key. I.e., the plaintext turns into ciphertext c. 

6. Bob sends the ciphertext to Alice through a public channel. 

7. After receiving the ciphertext, Alice applies her secret key to decipher the ciphertext into plaintext. 

8. If the procedure is conducted properly, Eve cannot know either Alice’s or Bob’s key, cannot guess their keys, or cannot convert the ciphertext to plaintext without knowing either one of their keys. 

You may be asking yourself: if the two secret keys are different, how do we ensure that the plaintext that Bob receives is identical to the plaintext that Alice sent? This is a great question and will be explored in the following article in the series.

Public-Key Cryptography is more complicated and harder to grasp than Private-Key Cryptography. That is okay; we will spend the next article exploring Public-Key Cryptography as well as the specific public-key cryptosystem, Elliptic Curve Cryptography, that underlies the Bitcoin protocol. 

Solutions to Practice Problems

PP 1:

Key: shift by +9 letters (A—>J, B—>K, …, Z—>I)

Plaintext: “HOWAREYOU” (How are you)

Acknowledgements

I want to thank Mason Jappa, Sam Chwarzynski, Tanner Davis, and the Blockware Solutions Team for their continued support and valuable feedback on drafts of this series of articles. 

Disclaimer

The views presented in this article as well as any errors are my own. If you think that any section of this article requires technical revision, please email me at mateusz@blockwaresolutions.com. 

This article is for informational purposes only. It is not intended to be investment advice. Contact a licensed professional for investment advice.

Contact

Mateusz (Matthew) Faltyn

Blockchain Developer | Blockware Solutions LLC

Bitcoin Pool Operator | mine . blockwarepool . com

Proprietary Research | Sign up for our newsletter on our website

Follow us on Twitter | @FaltynMateusz @BlockwareTeam

Join our Telegram Group |  BlockwareSolutionsOfferings

References 

1. Hoffstein J, Pipher J, Silverman JH. An Introduction to Mathematical Cryptography. 2nd ed. New York: Springer-Verlag New York; 2014. doi:10.1007/978-1-4939-1711-2_1

2. Paar C, Pelzl J. Understanding Cryptography. 1st ed. Berlin: Springer-Verlag Berlin Heidelberg; 2010. doi:10.1007/978-3-642-04101-3_1

3. What is Privacy. https://iapp.org/about/what-is-privacy/. Accessed May 11, 2021.

4. Prosser WL. Handbook of The Law of Torts. West Publishing; 1955. https://www.amazon.com/Handbook-Torts-Second-William-Prosser/dp/B0046J8U4O#detailBullets_feature_div. Accessed May 11, 2021.

5. DeCew J. Privacy. The Stanford Encyclopedia of Philosophy. https://plato.stanford.edu/entries/privacy/. Published 2018. Accessed May 11, 2021.

6. Mahtani S. Hong Kong protesters find ways for stealth in age super surveillance. The Washington Post. https://www.washingtonpost.com/world/asia_pacific/masks-cash-and-apps-how-hong-kongs-protesters-find-ways-to-outwit-the-surveillance-state/2019/06/15/8229169c-8ea0-11e9-b6f4-033356502dce_story.html. Published June 15, 2019. Accessed May 11, 2021.