We're going to build a simple symmetric encryption scheme using the XOR function. And then we'll show how to break this encryption scheme.
This puzzle is heavily influenced by this: https://cryptopals.com/sets/1/challenges/1
If you like this puzzle, see that set of puzzles which goes much deeper into encryption and breaking encryption.
These first set of challenges use the cryptopuzzle.py test
command.
Let's get XOR working.
Throughout this exercise we're going to use the bytes
type in python3
for all of our work. To print the bytes type we'll convert them
to hexadecimal string with bytes.hex()
.
XOR (exclusive or) applies bitwise addition to a sequence of bytes
XOR two sequences of bytes together to get a third sequence of bytes
Do this by implementing the xor()
function.
You may need to lookup the XOR operator for bytes in python3.
If you XOR together these values:
7f3a4f1351f85b0344223e1177e14707190c0e311f4ca633f5f3e9352372
07e32c180dfa56496a461627542115132a4c284050495b23e2245b093159
You should get this result:
78d9630b5c020d4a2e64283623c05214334026714f05fd1017d7b23c122b
If cryptopuzzle.py test
shows this output and Challenge 1 passes,
it's probably working.
Understanding XOR.
Let's play around with properties of XOR.
We'll compute A+B=C
(with +
meaning XOR). Fill in # TODO
in
challenge2()
to compute and print A+C
and compare that to B
. Start by printing these values and comparing them visually. Do the same for C+A
and B
: compute them, print them, and compare them.
Next, think for a minute about how can we use these to build a symmetric encryption scheme. Imagine that A is a message, B is a key, and C is a ciphertext. How do we encrypt and decrypt messages?
By now we hope you see that s XOR is reversible: if A+B=C, then C+A=B and C+B=A.
We'll use this so that: msg+key=ctxt and ctxt+key=msg
This gives us a symmetric encryption scheme.
In challenge2()
write assert statements for the these equations above.
Like the other challenges, it should print "Passed!" only if the equations
match. This is how we know XOR is working well enough to build encryption.
Build a repeating key.
Given a short key like "FETCH"
, and a size of 18 bytes,
make it longer by repeating it multiple times to make
"FETCHFETCHFETCHFET"
. We'll need this for our encryption scheme.
In real-world encryption, keys are short(ish), and messages can be any length.
Implement expandKey()
function for this challenge.
Let's build encryption.
We're going to build a simple encryption scheme called "repeating-key XOR".
The encrypt()
routine will take a short key,
expands it to the length of the message, and then XOR
that long key with the message to produce and return a ciphertext.
Given key "GRETCHEN"
and the message
"They say her hair is so big because it's full of secrets"
.
We should get the ciphertext (in hex) that looks like:
133a202d633b2437673a20266320242735722c27633b2a6e253b2274212d262f322120742a3c623d673430382f682a2867212037312d313d
Implement the encrypt()
function for this challenge.
Build decryption using XOR.
If encryption is working this should be very easy once you've figured out how decryption should work. Look at challenge2/2a for ideas on how decryption should work.
Ask for help if you need a hint.
challenge5()
tests encrypt/decrypt through a simple technique. If we encrypt the message "She doesn't even go here."
with the key "GROOL"
and then decrypt with the same key, we expect to geth original message.
Implement the decrypt()
function for this challenge.
Once it's passing, feel free to change the messages and keys in challenge5
to your own strings.
For the next two challenges we're going to switch the command line we're running. We're going to implement command-ling encryption and decryption by prompting the operator for inputs. This will give us a command line encryption tool.
Command line encryption.
Get runEncrypt()
working. When you run python3 cryptopuzzle.py encrypt
it should work like this:
Enter your message:
<operator types some messge and presses enter>
# Read the message and convert it to bytes
Enter your key:
<some key>
# Read it, convert to bytes, and lengthen the key
382f682a2867212037312d313d
# Print the ciphertext
Implement runEncrypt()
for this challenge. You can use inputs and outputs
from other challenges to test that it's working.
Command line decryption.
We're going to get python3 cryptopuzzle.py decrypt
working.
It should work like this:
Enter your cipertext:
382f682a2867212037312d313<enter>
# Read the hex and convert it to bytes
Enter your key:
<some key>
# Read it, convert to bytes, and lengthen the key
<decrypted message printed>
Implement runDecrypt()
for this challenge. Test it by encrypting/
decrypting messages from the command line.
Hurray! You're a real-world cryptologist now! Go start a blockchain company!
Cracking very simple keys.
For these last two challenges we're going to break our own encryption scheme.
We use python3 cryptopuzzle.py crack
to run these challenges.
This message has been encrypted using single-key XOR and only a 1-character key. Find the key and the original message.
18763c713f3e25713071233436243d3023713c3e3c7d7118763c713071323e3e3d713c3e3c70
Feel free to ask for a hint.
Implement cracking in challenge8()
for this challenge.
Cracking longer keys.
This ciphertext has been encrypted with a 4 letter word. Find the message and the key, both are meaningful.
022b611928212f2b3e2120376a3661392865362b2c37613e242b2a60
Implement challenge9()
for this challenge.
If you've cracked both messages you are a cryptanalyst. Feel free to call the NSA for a job or become a consultant and help tech companies break and fix their own designs.
If you like these kinds of exercises, there are more that go into depth on various parts of encryption and breaking encryption: https://cryptopals.com