Introduction to Cryptography

Cryptography is all about secret messages.

How can we send a message to someone that only they can understand?

A simple method is to change each letter of your message.

Example: "donuts under sink" (for your Sister only)

If anyone else reads your message they will find and eat the donuts before your sister gets home.

Let us try a simple method of raising each letter up one in the alphabet, so we encode:

d→e, o→p, n→o etc and we get: epovut voefs tjol

Looks like nonsense to everyone except your sister who knows the trick and decodes:

e→d, p→o, o→n etc and gets: donuts under sink

You can use Secret Messages for this if you want!

This is a type of "substitution cipher".

More Advanced

But if anyone knows this method they can easily decode your message.

So let's be more clever and go up 2 or 3 or more places in the alphabet.

Or even more clever and have a changing number of places. Maybe choose the number "3142" to mean "raise the first letter 3 spaces, the next letter only 1 space, etc". So even someone who knows your method will have a hard time if they don't know "3142".

Enigma Machine

Kriegsmarine Enigma Machine
by Wikipedia user LukaszKatlewa

The Enigma Machine, developed by the German military in the 1930s for secure communication, uses an advanced method like that.

With a series of rotating wheels, known as rotors, that map each input letter to a different encoded letter. The rotors can be set in different positions, creating a complex encryption process.

Making it even more challenging to crack is its rotor settings. The settings were changed daily, and the Germans had a vast number of possible combinations to choose from. Additionally, as each letter was encoded, the rotor positions rotate, further complicating the encryption.

The early versions were cracked by the Poles who handed on their work to the British during the second World War.

Some very smart people, led by the famous Alan Turing, cracked the newest version and could suddenly read German messages and know, for example, where the U boats were going and avoid or possibly sink them.

This is believed to have shortened the war by 2 years and saved millions of lives.

Cryptography is powerful!

Code Breakers

So how can such codes be broken?

The code breakers have lots of things they can use:

Some letters are much more common, such as e, t and a.
Some letters appear together more often such as th and nd
Some words are also more common
They can also try many combinations to see if any produce actual words.

See Random Words for an interesting look at how often letters and letter combinations appear in English

They can also wait for important news to happen, then look for any of its keywords in the messages.

Beyond Substitution

Modern day cryptography has gone way past all of that.

We now use Prime Numbers!

It is based on the idea that multiplying primes together is much easier than figuring out which primes were multiplied to form a number.

Example: What is 101 × 131?

With a pencil and paper we can get the answer of 13231 in a short while.

But what if the question was "What are the factors of 13231?"

We might be working a long time on that question!

OK, the Prime Factorization Calculator can do that easily, but not when the numbers are huge (like 100s of digits) which might take years or centuries.

RSA

Which brings us to the RSA (Rivest-Shamir-Adleman) Algorithm.

It is a public-key/private-key encryption algorithm that uses two prime numbers p and q.

The public key (which includes p×q) encodes the message so it is very hard for others to read.

But the private key has extra information that allows us to decode the message easily.

You can try our (small number) RSA Interactive

This type of encryption is called "asymmetrical" because it uses two keys (public key for encryption and private key for decryption).

Other Encryptions

Cryptography also includes:

Symmetric-key encryption, where the same key is used for both encryption and decryption. This key is shared between the sender and recipient and must be kept private.
Digital signatures: a way to verify that digital documents are authentic and not changed.
Hashing: fixed-length codes or "fingerprints" of data.
Secure key exchange protocols: ways to ensure that digital keys can be securely distributed between two parties.

Cryptography is a rich and varied field that people with good common sense and an understanding of prime numbers can be very good at.