Intro To Crypto, PT1

Well it will take some work, security is not like what they show on TV. You don’t need green on black text, special goggles or an unlimited enhance function. Instead, it requires sitting down and understanding the history of the field, what it means to be “secure” and what limitations or assumptions you can work under. This summer I have decided to start my journey on the vast field of cryptography and am doing an online course at Stanford University that provides an introduction to cryptography. It is appropriately named “Cryptography I” and is the first part of a two part course, the second part being offered later in the Fall. Both are taught by a really awesome professor Dan Boneh who I find explains the material very well. I decided I would like to make some posts about what I have learned in this course as I go through the material so that I can share my knowledge and get a chance to write it down somewhere for later reference.

The Start

Cryptography provides two important functions, it allows users to have a secret key that they can establish and share, as well as allowing a secure communication that provides confidentiality and integrity of the message. Crypto can also provide authentication, anonymity and even a digital currency!

To begin a journey into the world of crypto we have to understand what the basic steps are to perform accurate research. The course outlines these in 3 basic steps:

Precisely specify a threat model
Example: a digital signature cannot be forged by an adversary

Propose some construction

Prove that breaking the construction threat model will solve the underlying hard problem
Example: any attacker who is able to attack the construction under the threat model is unable to solve the hard problem, the construction cannot be broken

The Basics

Before the real crypto analysis can begin however, there needs to be some understanding of the key concepts that are used in the course. These are Probability Distributions, Events, Randomized Algorithms and Independence.

Probability Distributions

Suppose you have some set U ( our ‘universe’) which is a finite set, for example U = {0,1}^n. What this notation means is that U is a set which can consist of either 0 or 1, n amount of times. So for example if n was 2 then the following values would be present inside of U: {00, 01, 10, 11}.

Now that there is a universe to limit the calculation, the next step is to understand the two types of distribution. Note that the total of the probabilities always adds up to 1.

Uniform Distribution

In a uniform distribution the probability of a certain element of the set being selected is exactly equal to 1/|U|. Note that |U| means the size of the set U. So in the example above, a truly random distribution has probability 1/4 of selecting any specific element.

Point Distribution

In a point distribution the probabilities are not evenly distributed, meaning that some elements have a higher chance of being selected than others. For example in the set U defined above, we could have the following probabilities:

Elements:    00  01  10  11
Probability:  0   0   1   0   = 1

Events

For the set U, our universe, a certain subset of it is called an “Event”. For example if we define A so that it contains all elements which have the last 2 least significant bits equal to 11. What we can then do is use the concept of distribution from above to dermine what the chance of a certain event is.

Lets for example say:

U = {0,1}^8
A = {all x in U such that last 2 LSB(x) = 11}
For a uniform distribution on U: Pr[A] = ?

Well, we can look at U and quickly determine that there are 64 elements inside of it that end in 11. We also know that |U| = 2^8 = 256. We also know that the probability of one of these being selected in 1/256. Therefore we can simply do: 64 * 1/256 = 1/4. This means that Pr[A] = 1/4!

Randomized Algorithms

Lets first look at what a Deterministic Algorithm is before we define what a Randomized Algorithm is. Imagine you have two sets, a set of inputs (which we will call m) and a set of outputs that these inputs map to (which we call A(m)). In a deterministic algorithm, a certain m always maps to a certain A(m). This is because the function A() only takes in m as the input and so will always give the same output.

A Randomized Algorithm on the other hand can be defined in a way that A() takes in two arguments. We can say that m will map to A(m, r) where r is a random sample from a set {0,1}^n. If you are familiar with the concept of a “seed” or “salt” then this is basically what r is, it will allow us to manipulate the result so that even given a consistent value for m, we still output a different value for A(m, r). Note that this assumption relies on r never being repeated.

Independence

If we are concerned about the fact that two events are independent we need some formal definition that we can use. Thus the following will provide this function:

Random variables X,Y take values from the set V and are independent if:
For all a,b in V: Pr[X=a AND Y=b] = Pr[X=a] * Pr[Y=b]

Lets look at an example to make sense of this definition. Suppose you have a coin and you want to know if the first coin flip influences the second. We need to show that these events are independent. Suppose also that we record them in a way that the first result is followed by the second. For example if you got two tails in a row, the result would be: 00 but if you get a tail and then heads: 01.

More formally we can say:

U = {0,1}^2 = {00, 01, 10, 11} and r samples randomly from U.
Pr[X=0 AND Y=0] = Pr[r=00] = 1/4

We also know that if U = {0,1}^1 = {0, 1}:
Pr[X=0] = 1/2, Pr[Y=0] = 1/2

Therefore:
Pr[X=0 AND Y=0] = Pr[X=0] * Pr[Y=0] = 1/2 * 1/2 = 1/4

Thus we can prove that these events are truly independent.

Conclusion

Phew, that was a lot of writing! But that is the basics of the course, in the next post I hope to go over some more material that builds a foundation for the course. If there are any questions, feel free to ask below and if you have not already I highly recommend you check out the course here.

 

Feature Image courtesy of freedooom at FreeDigitalPhotos.net

Advertisements
This entry was posted in Cryptography, Security and tagged , . Bookmark the permalink.

One Response to Intro To Crypto, PT1

  1. Pingback: So You Want To Be A Cool Security Guru? PT. 2 | Information & Technology

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s