AEP 3: Public-key cryptography

Overview

In this AEP, you will apply the concepts of modular arithmetic to learn about the powerful concept of public key encryption –- a method of encrypting and decrypting messages without sharing private information beforehand. The successful implementation of public-key encryption in the 1980's is widely considered one of the greatest scientific innovations of the last few centuries, and we use it every day without realizing it. And it all boils down to arithmetic!

Deadline: This AEP should be submitted on or before Sunday, June 5 at 11:59pm ET. If you need an extension on this deadline, contact the professor and explain why you need the extension, and when you plan on turning in the work.

Background

This AEP focuses on another method for encrypting and decrypting messages that has a fundamental difference from the other methods we've seen in class and in AEP 1: Encrypting messages with binary. Before going any farther, please review AEP 1 for an overview of basic terminology and concepts from cryptography such as encryption, decryption, and key.

When we've encountered cryptosystems in the course, Alice is trying to send a message to Bob, but she doesn't want an evil eavesdropper Eve to be able to read it, even if the message is intercepted. So Alice encrypts the message and sends it to Bob. Simple, right? But there's one problem: In all of those earlier systems, Alice and Bob have to share the key. It's a lot like if I wanted to grant you access to my office –- I'd need to somehow get you my physical key. But…

• …What if sharing the key for encryption and decryption was problematic? For example, what I believed that "Eve" might be eavesdropping on the channel I am using to send you the key? I could encrypt the key, but that doesn't solve the problem, because how will I get you the second key that encrypts the first one, in a way that convinces me Eve hasn't stolen it or tampered with it?

• …What if I wanted to send you a message but also wanted to remain anonymous –- like a whistleblower who wants to send an encrypted message to a reporter? Traditional cryptosystems fail on this front because they require that I reveal my identity to you in order to send the message.

What solved both of these problems was a mathematical innovation discovered in the late 1970s and early 1980s called public key encryption.

In a public key system, each user creates two keys: one that is kept private, and another that is made 100% public. If Bob is a user, and Alice wants to send him a message, Alice looks up his public key information and uses it along with an algorithm to encrypt the message. Then, when Bob receives the message, he uses his private key to decrypt it. Public key system are made in such a way that the mathematical combination of the public and private keys will decrypt the message.

Another important facet of public-key encryption is that a person can send an encrypted message to another, without having to make up their own key. As you'll see, if Alice wants to send Bob a message, only Bob needs to have public and private keys; Alice does not need to register with the system.

This AEP will focus on a simple (but vulnerable, as you'll see) public-key system that uses the modulus ("mod") function. Here's how it works:

• To generate the keys, first choose four positive integers:
  $a$,
  $b$,
  $A$, and
  $B$. These are preferably random, but they can be anything as long as they are positive integers. The capitalization is important.
• Then do four computations:
  • $M=ab-1$
  • $e=AM+a$
  • $d=BM+b$
  • $n={\displaystyle \frac{ed-1}{M}}$
• The public key for the user is the pair of numbers
  $(n,e)$. The user puts this key next to their name in a public place (a server, Google Doc, skywriting, etc.)
• The private key for the user is the number
  $d$. The user keeps this private under all circumstances.

Bob is making a key. He randomly generates the numbers

$a=86$,

$b=62$,

$A=26$, and

$B=34$. Then he computes:

• $M=ab-1=(86)(62)-1=5331$
• $e=AM+a=(26)(5331)+86=138692$
• $d=BM+b=(34)(5331)+62=181316$
• $n={\displaystyle \frac{ed-1}{M}}=\frac{(138692)(181316)-1}{5331}=4717141$

The pair

$(4717141,138692)$ is the public key; Bob decides to get it put onto a T-shirt that he wears when he's going out. The number

$181316$ is private, so Bob tells nobody what it is.

If Alice wants to send Bob a message, she does the following:

• Alice looks up Bob's public key
  $(e,n)$. (Notice, Alice herself does not need a key –- just Bob.)
• Alice takes her plaintext message –- which for this AEP we will assume is just a string of capital letters without punctuation or other symbols –- removes all spaces, and converts each letter to numbers
  $00$ through
  $25$ according to its position in the alphabet. This produces a long string of decimal integers.
• Alice then breaks that string up into equal-sized blocks, each of which is an integer less than
  $n$ (from Bob's public key), and adds zeroes to the end of the final block if needed to make it the same length as the others.

Example: Alice wants to send the message AM ON MY WAY. Converting this to integers 00-25 gives 00 12 14 13 12 24 22 00 24 and stripping out the spaces gives 001214131224220024. Bob's value of

$n$ is 4717141. So Alice breaks her message up into blocks less than 4717141 –- for example, into blocks four digits long: 0012 1413 1224 2200 24. To get that last block to be exactly four digits, she pads it with a couple of zeroes to get 0012 1413 1224 2200 2400. (She could also have chosen blocks five digits long, or shorter.)

Now to encrypt this message, Alice goes through the message one block at a time. For each block

$P$, Alice computes:

$C=(e\cdot P)\mathrm{\%}n$. Once each block has been encrypted, the chain of blocks is the ciphertext that is sent to Bob.

Example: The second block in the plaintext is 1413. To encrypt it, Alice takes Bob's public key –- which is the pair

$e=138692$ and

$n=4717141$ –- computes

$$(e\cdot P)\mathrm{\%}n=(138692\cdot 1413)\mathrm{\%}4717141=195971796\mathrm{\%}4717141=2569015$$
And that's the encrypted version of that block that gets sent to Bob. Repeat this computation for each of the other blocks.

When Bob receives the ciphertext, which is a string of blocks of integers, for each encrypted block

$C$, he computes:

$(C\cdot d)\mathrm{\%}n$. This produces the decrypted blocks that Alice sent. Bob can then separate the blocks into two-digit units and convert back to letters, and read the message.

Example: Bob receives Alice's incoming encrypted message, which looks like a sequence of fairly large integers. The second one in the sequence is

$2569015$. This represnts two encrypted text characters. To decrypt, Bob pulls up his private key

$d$ along with

$n$ from his public key and computes:

$$(C\cdot d)\mathrm{\%}n=(2569015\cdot 181316)\mathrm{\%}4717141=465803523740\mathrm{\%}4717141=1413$$
Bob can then tell that these are the characters O (14) and N (13). Bob can continue doing this with each encrypted block until he has Alice's original message.

Notice that Bob's private key was never communicated; and Alice needed no key of her own to send the message.

Tasks for this AEP

1. Generate a set of keys for yourself using the method above method. Keep the private key
   $d$ completely private, but take your public key pair
   $(e,n)$ and put it on this spreadsheet along with your name: https://docs.google.com/spreadsheets/d/1CO4W3wmT8fE_WrCHlJ9SIQv8HWNQHqJ8S8bL8Lv0_gw/edit?usp=sharing
   Don't put any more details on the spreadsheet, but do show all of the work you did to generate the keys in your final writeup.
2. Make up a short message, encrypt it using my public key, and email it to me. This message should be sent to me by email and does not go in your writeup. However, please do put your original decrypted message in your writeup along with the math work you did to get create the message. (You should never include the unencrypted message in real life!) Remember since you are sending me the message, you have to use my public key –- not yours. (It's like calling someone on the phone –- you look up their number, not yours.)
3. Once you have posted your public key, I will send you an encrypted message by email. It will be something where it's obvious if you've decrypted it correctly. When you get it, put all your math work used to decrypt the message in your writeup.
4. For the final task, you have two options.
   • Option 1: Hack the professor. As you saw, my public key information is public, there for the world to see on an open spreadsheet. In a secure system, a hacker should find it difficult or impossible to figure out my private key even if my public key is exposed. However, this system has some holes in it. Figure out what my private key,
     $d$, is –- using only my public key, and knowledge of the formulas used to generate the keys. Obviously in your writeup, you'll need to state my private key and then clearly explain how you got it, in complete detail.
   • Option 2: Explain how all this works. Give a clear, correct mathematical explanation for two parts of this process that aren't totally obvious: First, explain why
     $n=\frac{ed-1}{M}$, although defined as a fraction, will always work out to be an integer; and second, explain why for any positive integer
     $x$, if we perform the math operations to encrypt
     $x$, and then perform the math operations to decrypt the result of the encryption step, we will end up with
     $x$ each time. (In other words, explain why this system will always "work" in the sense that the decryption of an encrypted message is the plaintext.) For this option, the explanations will involve quite a bit of algebra and computation –- but be sure to add English to help the reader understand.

Expectations and Grading Criteria

AEPs are graded using the "EMRN" rubric found in the syllabus. Make sure you review the Standards for Assessments in MTH 225 document before you submit any work, so you're fully aware of the expectations for the different marks. In particular:

• All work needs to be shown and your thought processes clearly expressed in all of the tasks of the assignment. The results also need to be correct. You are not just doing math; you are explaining things to a reader, so a mix of math and English is needed.
• All the information needed for an "outsider" to understand your work needs to be self-contained within the work. The reader should not have to do any work to fill in gaps.

Please note, it is the case with all AEP's that your grade is primarily based on your explanations and writing, and only secondarily on the precision and correctness of your computations. Correct computations with insufficient explanation will need to be revised and may receive an "N" grade.

A grade of "E" is given if all of the above expectations are met, and the work is of superior quality in terms of the clarity of explanations and work, appearance of the writeup, and precision of the mathematics.

Submitting your work

AEP submissions must be typewritten and saved as either a PDF or MS Word file. No part of your submission may involve handwriting; work that is submitted that contains handwriting will be graded N and returned without feedback. This includes electronic handwritten docments, for example using a stylus and a note-taking app. To type up your work, you can use MS Word or Google Docs (both of which have equation editors for mathematical notation) or any other computer-based math typesetting tool. Just make sure you save your work as a Word document or PDF (no .odt, .rtf, or other file extensions are allowed).

When you have your work typed up, double-check it for neatness, correctness, and clarity. Then simply submit your document on Blackboard, in the AEP area, in the AEP 3 assignment.

Getting Help

You may ask me (Talbert) for help on this assignment in the form of specific mathematical or technical questions, or clarifying questions about the instructions. If I cannot answer a question because it would give too much away, I'll tell you so. However please note: I will not "look over your work" before you submit it to give you feedback on the overall submission. I have made the expectations clear, so just follow those directions and submit your best work, and you'll be allowed to revise it if needed.

For AEPs, the syllabus policy on collaboration is:

No collaboration is allowed at all — with other people, or with print or electronic sources other than your textbook, the video playlist, or your notes.

You can ask technology related questions to anyone at any time. For example if you need help figuring out how to type up your work, there are no restrictions on that.