Team 1 (Cathy, Jose, Sarah, Heather)

Use this page to write up your outline and project. Let me know if and when you need help with any wiki and/or $\LaTeX$ formatting.

# Cryptography

## Introduction to Public Key Cyrptosystems

Cryptograhy is the mathematical science of sending and receiving secret messages. There are many different systems of cryptograhpy. This project explores the public key cryptosystem. Public key cryptograhpy involves the use of two keys, i.e. mathematical codes, called the public key and the private key. These mathematical codes used in this system are heavily dependent on abstract algebra and number theory. The public key can be made available to any one wishing to encode and send a private message. The receiver of such a private message has a mathematical code, the private key, that decodes the sender's message. Anyone could share and use the public key. However, only the private key holder knows how to use the private key to decode a message, in other words only the person receiving the message can read it's contents. In classical crytography, both the sender and the receiver know how to decode a message. Caesar Cipher is an example of a one key system in classical crypstography. RSA is an an example of a modern two key system.

## History

Cryptography goes back to ancient Greece and Rome. Julius Caesar used a simple shift code to send and receive messages, this was called the Caesar Cipher. More recently RSA has taken over the encryption process. RSA stands for Rivest, Shamir, and Adleman. These were the people that first publicly described this particular process of cryptography, in 1978. This was the first algorithm suitable for signing and encryption. It was also one the first great advances in public key cryptography. RSA was released to the public in Sept. 2000 by the RSA security, but the National Security Agency wanted to keep it secretive. RSA involves three steps: key generation, encryption, and decryption. There is still the open question on whether or not RSA can be broken, i.e. intercepted and decoded by a math ninja without the decryption key. At the time our book was written the largest factored number is 135 digits long. Today the code is considered "secure" if the key is about 400 digits long and is the product of two 200 digit primes. It is not difficult to find two random primes, but to factor a number, 150 digits long, into the product of two large primes would take 100 million computers operating at 10 million instructions per second about 50 million years under the fastest algorithms currently known. (That's pretty epic!) Factoring a large number into two primes is very difficult because there is no efficient algorithm currently known.

## Caesar Cipher

The Caesar Cipher was originally created by Julius Caesar. The whole purpose to this idea was to relay messages to his allies without worrying about his enemies intercepting the messages and learning their strategies. The Caesar cipher can have a shift of any numbers between 0 and 25. For example, a shift of 5 would make $A \to E$, $B \to F$ and so on. When Julius Caesar used the cipher he used a shift of 3. Let's look at the message "Attack left flank." This message would be encrypted to be "Dwwdfn ohiw iodqn." You might think this would be rather easy to decipher, but you have to remember that not that many people at this time were literate or educated in the first place.

How does this relate to group theory you may ask? Well for starters we can classify the alphabet under $\mathbb{Z(_26)}$ and using the Caesar Cipher we just shift the original letters three spaces. Plus in order to decode the encrypted message we know the inverse of the message so we can "undo" the actual message. This message is not used by major companies and armies for obvious reasons because anyone can decipher the message given enough time since there are only twenty six different possible methods to encrypt the messages.

To demonstrate an example we will go [http://www.simonsingh.net/The_Black_Chamber/caesar.html]

## Alice and Bob

Alice is wise in the ways of RSA. She sends her "friend" Bob a mathematical code called a public key, $(n,e)$. The public key allows Bob to encrypt a secret message (ciphertext, $c$). Alice wants to know what Bob says in the ciphertext she received. She has a mathematical code called a private key. The private key allows Alice to decrypt the ciphertext (ooo la la …).

In order for Alice to create a public key she needs to do some preliminary computations. Yes, she is sort of a math ninja. These computations involve some number theory concepts that we have learned in abstract algebra like modular arithmetic, relatively prime, the Eulcidian algorithm, and the group of units, $U_r$, in $\mathbb{Z}_n$, plus other concepts. Here are some of the computations she makes:

1. To compute $n$, she chooses two prime numbers, $p,q$. Alice chooses $p = 3, q = 11$. In real life, each prime is at least a couple hundred digits long.The longer the primes, the more difficult it is to break the code because it is nearly impossible, even with the most powerful computers, to factor the product, $n$, into the two prime factors.
2. Compute $n = pq$. So, $n = 3 \cdot 11 = 33$.
3. Compute Euler's function, $r$, $r = (p-1)(q-1) = 20$. Alice uses the $r$ to look at $U(20) = \{ 1,3, 5, 7, 9, 11, 13, 17, 19\}.$ From this group, she will choose an $1 < e < 20$ and compute a $d$ such that $de \cong 1 \mod r.$ Alice first chooses an $e \in U(20)$ at random and then computes $d$. In this examples she randomly chooses $e = 17$. Then she computes the multiplicative inverse of $e \in U(20)$, which is the $d$. In this case, $d = 13$. The Euclidean algorithm is often used to compute $d$.We can check this. How? Dang it, do the math… $\frac{13 \cdot 17 }{20}= 11 r1.$
4. Alice uses a scheme that assigned a number to each letter of the alphabet. The scheme she used this time is a=1, b=2, and so on. She used this simple number scheme to translate a message from letters into a simple number message, $p$. The public key encrypts the simple number message to form a ciphertext. The function for encryption is
(1)
\begin{align} c \cong p^e \mod n. \end{align}

So, let's encrypt the message, "Wuzz up." Using the simple number scheme, we get the simple number message, $23,21,26,26,27,21,16.$ By the way, we used $27$ to represent a space between words. Each simple number is a $p.$ We can use Wolfram Alpha or Sage to help with computing each $c.$ To use Sage, the function is written in the form (p^e).(mod n). To use Wolfram Alpha, just type in the function $p^e \mod n.$

The ciphertext message is $23, 21, 5, 5, 3, 21, 25.$ This is what we send to Alice. She now uses this function to decipher the encrypted message:

(2)
\begin{align} p \cong c^d \mod n. \end{align}

She takes all the $p$ values and uses the simple number scheme to convert to letters. Viola, she's received her message.

## References

[http://en.wikipedia.org/wiki/RSA]
Abstract Algebra: Theory and Application, Thomas W. Judson.

page revision: 40, last edited: 11 May 2010 01:29