Cryptography

You are already familiar with a similar task from the chapter on word machines.

Investigate the different machines by entering a few words. Select three machines, briefly describe their effects in your workbook, and write down the word you entered and the result.

Think about this: In order to communicate securely, an encrypted message must also be able to be decrypted. Review your results: Is it possible to decipher all the cards clearly? Explain your decision in your notebook and list at least one counterexample.

Ciphers transform messages. One of the most famous ciphers was used over 2,000 years ago - the Caesar cipher. In this process, each letter of the alphabet is shifted by a fixed number of positions.

Build a replica of the Caesar machine using the card titled Alphabetic Jump. Explain what happens to the word MATH when each letter is shifted two places to the right, and write the resulting word in your workbook. Determine whether this process can always be reversed to produce the original word, and explain your reasoning in writing.

Determine how many cards of the type Alphabet Countdown you need to chain together to reconstruct the original word and write down that number.

Good to know: The Caesar Cipher is what is known as a monoalphabetic substitution cipher. This means that only one cipher alphabet is used for encryption, which in this case is shifted by 2 positions relative to the original.

Previously, the offset was fixed in the machine. Now we use a slider for this, the parameter a. The word MATH is already set on your screen. The Text to Numbers machine automatically converts your letters into a sequence of numbers. Now we want to control the offset flexibly.

Connect the output of the Text to Numbers card to input A of the Operation (Addition) card, and connect the parameter card to input B.

X-ray vision: Connect the output of the Operation to the Numbers Output card. Move the parameter slider systematically and observe the number output. Write down the number output for \(a=3\). Also connect the Operation to the text output via the Numbers to Text card.

Examine both outputs. For which values of a do the letters of the word MATH turn into special characters? Write down your findings in your notebook.

Addition alone, as in Task 3, is not enough: When we shift numbers in the range from 0 to 28, they quickly exceed the bounds of our character set. This is where the modulo operation (mod) comes in. It brings these numbers back into the set of 29 characters.

First, explore the modulo principle using an analog method. To do this, draw a clock below the explanation of modulo calculation in your notebook and write the numbers from 0 to 28 around the edge. Then use the clock to calculate which numbers the pointer lands on for the values 50 and 110. Draw the path of the pointer for the value 50 on the modulo clock. Write down the corresponding mathematical expression as a division with a remainder (example: \(35 : 29 = 1\) with a remainder of 6, so \(35 \pmod {29} = 6\)). Then check both results using the machine.

Now it's time to put your technical skills to the test: Assemble all the building blocks into a complete encryption machine.

Connect the cards so that your text is first converted into numbers, then added to the parameter a, secured using the modulo operation, and finally converted back into text. Test the finished machine with the word MATH when \(a=23\) and note which numbers differ before and after the modulo operation.

For code specialists: In Task 3, you already discovered that there are not only letters here, but also special characters when you set a to certain values. Find out which specific numbers are hidden behind the letters and which are hidden behind the special characters.

The Caesar cipher has a major weakness: Since each letter is always shifted by the same amount, the shift can be easily guessed. The solution: A changing keyword!

Here you can see a system where two messages come together: your text and a key. The partial translations are already connected. All you have to do is integrate the key into the system. To do this, connect the second Text Input (your keyword) to the card Repeat Text, and then connect that to Text to Numbers. Now combine the number sequences of your plaintext and the repeated key in the Operation (Addition).

Why Repeat Text? If your key is shorter than your text, not all the letters in the message will be encrypted. Therefore, you must repeat the key as many times as necessary until it is long enough to cover every character in your message.

Test the system: What is the result of encrypting the word MATHEMATICS with the key ABCDE? After that, try other texts and keys as well. Write down the ciphertext and the corresponding sequence of numbers.

Encryption is one thing, but how does the intended recipient get the original message back? To do this, you have to logically reverse the encryption process.

All the components are here, but they are not yet connected and have been reset to their default settings. There is already some secret text on your screen. Build the decryption machine based on the model from Task 6.

Decide: Which mathematical operation do you need to select on the Operation card to subtract the key from the ciphertext? Write down the symbol for it in your notebook.

If your connections are correct, the ciphertext will be decrypted in a flash. Indicate how many times the key must be repeated so that the entire word can be decrypted. Write down the number and the solution word you found in your notebook.

The RSA algorithm uses a public key \((e,n)\) for encryption, which anyone can know.

Step 1: The Foundation. Choose two small prime numbers \(p\) and \(q\) (e.g., 3 and 11) and set them on the parameter cards. Connect the card Prime Number p to input a and Prime Number q to b on the cards Free Calculation Rule. Use these to calculate the modulus \(n = p \cdot q\) and the phi function \(\phi = (p-1) \cdot (q-1)\). Since the calculation card only understands its own connections a through d, the formulas must also speak the card’s local language. That is why it says \(a \cdot b\) instead of \(p \cdot q\).

Step 2: The key. Choose a number \(e\) as the key that is relatively prime to \(\phi\) (\(ggT(e,\phi) = 1\)). Only then is your lock secure!

\textbf {Step 3: The message. } Enter your message \(x\) as a number (it must be smaller than \(n\)). Now combine your message \(x\) with the input a and the key value \(e\) with input b in the exponentiation (\(x^e\), in the local language \(a^b\)). Combine the result of the exponentiation and your calculated modulus \(n\) in the modulo operation (\(mod n\)) to secure the encryption.

Write down your chosen parameters, the intermediate steps for \(n\) and \(\phi(n)\), and your resulting secret value \(c\) in your workbook.

You have converted a message into the number \(c\). But how does the recipient retrieve the original text from it? Simply working backwards does not work here, since the modulo machine only displays remainders. You need the trapdoor: the private key \(d\).

Step 1: Find the code. Calculate your private key \(d\) by determining the Euclidean inverse of your encryption value \(e\) modulo \(\phi\) using the online calculator linked in the workbook. Write down your value \(d\) in the workbook.

Step 2: The Decryption Machine. Wire up the decryption machine on the screen according to the formula \(m = c^d \pmod n\). To do this, use the Free Calculation Rule for exponentiation and the Operation for the subsequent modulo operation. Enter your secret value \(c\) as the message and use your newly calculated \(d\) as the parameter. Then feed the result of the exponentiation (Port A) together with the modulus \(n\) (Port B) into the modulo-operation.

Success Check: If your original message reappears in the Numbers Output at the end, you have successfully cracked RSA. Write down your result.