Cryptography Exercises
These are optional exercises for students who want to go beyond the material in the handout. They are arranged in a progression, so it will be easiest to do them in the order listed.
The Vigenère Cipher
The Vigenère cipher was once thought to be unbreakable. In 1863 a Prussian cavalry officer, Freidrich Kasiski, devised a method of breaking the Vigenère cipher. Watch the , read about the cipher on , then download the exercise sheet.
Exercise Sheet
The One-Time Pad
The One-time pad cipher is an extension of the Vigenère cipher that actually is unbreakable; it has the property of being "information theoretically secure," which is a very strong statement. That was proven by in 1949. You can read more about the , then download the exercise sheet.
Exercise Sheet
Public Key Cryptography
Although Bill can send an unbreakable message to Alice using a one-time pad, there's a problem: Bill has to get the key to Alice in a secure way. If Bill has a secure way of sending the key to Alice, he could potentially send the message in the same way. This is called the . To be useful, keys had to be distributed in advance, such as by a diplomat taking a code book when traveling to an overseas post.
In the 1970s, three groups of researchers independently invented a mechanism called public key cryptography that uses two different keys with the same message, one to encrypt and one to decrypt.
The key usually used for encrypting is called the public key, and the key usually used for decrypting is called the private key. Here's what's important: a message encrypted with one's public key can only be decrypted using the corresponding private key. You can give the public key to anyone, and they will not be able to decrypt messages that others may have encrypted with the same public key. This solves the key exchange problem. However, public key cryptography is only computationally secure; given enough computing power, it is possible to crack a message encrypted this way. With modern public key cryptography, even supercomputers would take decades to crack a single message.
You can read more about , then download the exercise sheet.
Exercise Sheet
Copyright © 2018 by ÈâÈ⴫ý. Last updated: 2020-03-28 16:45. Originally published: 2018-10-29
|