st15_Cryptography.md

<!-- [Doesn't seem to reference what's in the course map - i.e. MD5 hash algorithm, SSL, RSA etc. Do we need to go into this level of detail and history into crypto for undergraduates new to cyber? Perhaps we can provide a more concise history/definition of the term? We could introduce this as something like: "This week we turn our attention to Cryptography - which is the (insert definition) - in this section we'll give you some historical background on Cryptography, before we consider this in relation to modern day communications and passwords."]() -->

This week we turn our attention to Cryptography -- which is the
practice of turning data into an unintelligible form in a way that
only the *right* person can reverse it.  In this section we'll give
you some historical background on Cryptography, before we consider
this in relation to modern day communications and passwords.

# Secrets

"Keeping secrets" sounds like a furtive activity, exhibited by thieves
and criminals as they go about their shady business, and yet secrecy
has been of critical importance in civilisation for thousands of
years.  Confidentiality and privacy, two concepts that most of us
would agree are reasonable and expect them to apply to our daily
lives, are built on the idea that some things are secret.

Confidentiality is the idea that a secret can be shared with only
those with whom we choose to share it.

Privacy is built on preventing others from knowing something about us,
our lives, our business and so on.

Throughout history, this need for secrecy has been growing and so the
science of cryptography was born.

Today, cryptography allows us to have private telephone conversations,
send data securely, use on-line banking and prove the ownership and
authenticity of digital assets.

Understanding the core principles of cryptography is important in the
modern world and we hope by the end of this topic you will not only
have understood the key concepts, but feel more confident about ideas
such as digital certificates, electronic signatures and even how to
choose a good password.

# Early Cryptography

Cryptography has been around for a long time. Even the word
'cryptography' is ancient Greek and translates to "hidden writing".

In ancient Egypt, 4000 years ago and not long after the first written
language appeared, hieroglyphs were scribed to include some partial
substitutions of lesser-known symbols, possibly as a form of "secret
writing" that would confound a casual reader. In Messapotamia around
1500 BC, similar examples of the partial substitution of characters is
observed in early impressions on clay tablets.

Around about 500 to 600 BC, Hebrew scribes developed a mono-alphabetic
substitution cipher known as Atbash.  The process used a reverse
alphabet to encrypt text by substituting A for Z and B for Y and so
on.  As this method employed a direct substitution it was largely
insecure because anyone who knows the method could decipher the text.
At the time, this may have been acceptable, since not everyone would
be able to read the message and it would take more than a quick glance
to decipher it, making it a great improvement on sending a message by
telling it to someone who can travel and repeat it.

The problem with using a cipher such as Atbash is that it is not
possible to encrypt a message for a specific recipient.  It is similar
to a lock that anyone can open.  What is needed is some sort of "key",
so that only those with the key can decipher the message.

Perhaps the first use of a key occurred in the fifth century BC. The
ancient Greeks developed a tool known as a scytale, a hexagonal staff
wound by a long leather strip upon which a message was
written. Unraveled, the message would form a seemingly random string
of characters allowing the message to only be decrypted by the
recipient if they were in possession of a staff with the same
dimensions as the original used to encrypt the message. Re-binding the
scytale would then revealed the content of the original message.

The need for cryptography has grown ever since, and in India between
the first and fourth centuries AD Vatsayana’s Karma Sutra identified
cryptography as the 44th and 45th of the 64 arts that men and women
should study: 'The art of understanding writing in cipher and the
writing of words in a peculiar way. The art of speaking by changing
the forms of words'.


# The Rise of Cryptanalysis

As the need for cryptography increased and the prevalence of encrypted
information grew, the desire to uncover encrypted secrets also
grew. Many of the encryption methods developed throughout history
turned out to be secure only to a casual reader.  The art of
cryptanalysis quickly began to overtake the abilities of
cryptographers, and it started to look like there would be no way to
be completely confident about the secrecy of encrypted information.

Businesses would seek to discover the secrets of their rivals, armies
would attempt to discover the plans of their opponents, and queens
were executed based on the content of deciphered messages.

Today, the reliance on secure communication and storage of data to
protect us all from having our identity and money stolen or our
private lives exposed means that the prizes for nefarious
cryptanalysts and the stakes for users of cryptography are higher than
ever before.

Fortunately, cryptography regained the lead in the second half of the
20th century and today we are (mostly) sure that we can send data
without fear of an eavesdropper being able to decode it.

# Unbreakable Ciphers

The simplest, yet arguably most secure cipher is the One Time Pad
(OTP).  This has been used from before computing and the automation of
encryption and gets its name from that early implementation.  Two
people could exchange encrypted messages with absolute security by
each having a book of random numbers.  Let's imagine a person, Alice,
sending a message to someone, Bob, using this scheme.  Alice writes
her message out letter by letter. For each letter, she adds the first
unused number from the book.  Once used, that number gets crossed out,
so the next letter has the following number added, and so on.
"Adding" here means to move along the alphabet by that amount. So, if
the message has an A at the start and the first number in the book is
3, then Alice writes D in the encoded message.  When Bob receives the
message, he reads each letter and subtracts the numbers from the book.
The books must be identical for this to work.

So, we can see that Alice can encrypt and Bob can decrypt, but why is
it so secure? Well, if the numbers in the book have no pattern, any
randomly picked number from the book has an equal probability of being
every possible number.  Which means when the message is encoded, every
letter is now as likely to be an A as a B or C and so on.  In fact,
any message encoded this way could be decoded as any other message of
the same length if you imagine the right set of numbers from a book.

Electronic messages can be encoded much quicker and without the
laborious process of encrypting each letter individually. And yet
there is a big problem with this method

For it to work, Alice and Bob must each have an identical book of
random numbers.  How do they send these numbers to each other?  If
they are intercepted or read, then the system won't work, or won't be
secure.  You could say that it works perfectly, if only there was a
way to communicate the books securely to begin with, and if we could
do that, we wouldn't need OTP!

# Asymmetric Cryptography

In the early 1970's, James H. Ellis at GCHQ invented a new way to
encrypt data.

The method was ground-breaking because it didn't require the same key
for the sender and recipient, but because the work was kept secret, it
was overtaken by similar methods later in the 1970's and it Ellis's
work was only publicly announced in 1997.

These methods are called *asymmetric* or *public-key* cryptography.

## Verifying the Reader

If Alice wants to send a message to Bob, she can ask Bob for his
*public key* and encrypt the message with it.  It doesn't matter if
other people know this key, because once you have encrypted your data
with it, you can't use that key to decrypt it.

This seems, at first, impossible. Surely, if you know the key and the
method, you could reverse it. A rough analogy is that of the
remainder.  If I have a number representing the data, let's say 27,
and a number representing the key, say 8, then the encryption would be
the remainder of $\frac{27}{8}$, which is 3.  Now, knowing the key (8)
and the result (3) is not enough to reverse the process, because *more
than one input could produce that output*. $\frac{35}{8}$ is 3, as is
$\frac{827}{8}$ and so on.

In public-key cryptography, the data is recoverable, however.  It's
just not recoverable without a second key, known as the *private key*.
The two keys are created as a pair, by Bob.  In fact, either could be
the public key or the private key, but always one or other must remain
secret. Bob can decrypt the message using his private key, but nobody
else.

If Bob wants to reply, he must use Alice's public key, which can only
be decrypted by her own private key.

In this way, it is possible to communicate securely without ever
having to pre-send information such as keys, knowing that only the
intended recipient can read the messages.

## Verifying the Sender

Public-key cryptography can do something more than just ensure the
intended recipient is the only reader.

Because the private key and public key are a pair, encrypted data with
one can only be decrypted with the other *but it doesn't matter which
way around!* So, if I encrypt with my *private key*, only my *public
key* can decrypt it.  Putting this another way, if my public key can
decrypt the data, it *must mean that my private key was used to
encrypt it*.  Going one step further, this means that if we know only
I have access to my private key, we also know that *any message that
can be decrypted by my public key must have been written by me*.

This is a useful property for many reasons, but the two most obvious uses are:

1. We can now send a message that is first encrypted with out private
   key and then the public key of the recipient.  The recipient is the
   only person who can decrypt the message. They they do, they find a
   message that can only be decrypted by the sender's public key,
   verifying the source of the message.
2. We can use our private key to encrypt a message and then send the
   encrypted message *with the unencrypted version*. This is useful
   for creating a public message that can be verified as coming from
   the sender.

The combination of these ideas is the basis of electronic signatures,
secure communication on the internet, certificates for websites and
more.


<!--  LocalWords:  Messapotamia Cryptanalysis cryptanalysis Diffie
 -->