Foundations of Computer Science/Encryption

Encryption

In order to ensure secure communication takes place encryption methods must be used. Secure communication over the web is important for areas such as e-commerce. Encryption is used to encode messages ensuring no one, but the intended recipient knows the content of the message.

The messages that are transferred over the Internet in the form of packets. When you think about packets, they are more like postcards than letters. The content of each packet are plaintext (exposed for all to see) as the bits are transmitted.

The best way to protect these packets during transmission and after reception is using encryption techniques. Encryption is simply the process of converting information (plaintext) into unintelligible text (ciphertext) to avoid unwanted parties from intercepting the message. In order for the recipient to understand the ciphertext they must use a decryption method. Decryption reverses the process of ciphertext back into plaintext.

The two parts: encryption and decryption are part of what is known as cryptography. Cryptography (secret writing) is the practice and study of techniques for secure communication in the presence of third parties. It is not a new practice and has been around since early 2000 B.C..

Caesar Cipher

The Caesar cipher is an example of a substitution cipher. This cipher uses a letter-by-letter translation to encrypt messages. A cipher is simply a method (algorithm) used to transform a message into an obscured form and reversing the transformation. An example of this particular cipher can be seen below where you replace each letter in the top row by the corresponding letter on the bottom row:

With the Caesar cipher there are 25 possible variations representing one for each different amount of shifting. The key to remember about the encryption and decryption rule is the amount of the shift. If we know the Caesar cipher is used then we could try all possible 25 shifts of the alphabet to decrypt the message. However, tools have been created to encrypt and decrypt messages created using this cipher.

Substitution Ciphers

Substitution ciphers are ciphers that use one symbol is substituted for another according to a uniform rule. The example below shows a substitution table that defines a rule for reordering letters in the alphabet. How many possible reordering possibilities can be performed using the example below?

These type of ciphers appear to be unbreakable, but that is not true. Frequency analysis is used to decode substitution ciphers . This technique used to break general substitution ciphers uses frequencies letters that appear in a language.The image below shows the original message with symbols. We will use frequency analysis to decode the cipher.

After we have replaced the most used characters with E and T we can begin using other common symbols and sentence structure to fill in the gaps.

Finally, after replacing symbols with frequently used letters we see the entire message displayed below.

Vigenère Cipher

The Vigenere cipher is similar to the Caesar cipher, but it uses multiple Caesar ciphers to encode a message. For a long time the Viegenere cipher was considered unbreakable until the 1800s when Charles Babbage discovered a way.

This table shows the key to the cipher thomasbbryan. This cipher was used by an attorney named Thomas B. Bryan in 1894 to communicate with his client.

The substitution table used above encrypts and decrypts messages. We use the second column, "thomasbbryan", to uniquely identify the table. This key is used to specify which cipher is used.

The Vigenere cipher was unbreakable until the method to decode this cipher was discovered in 1863. Although the cipher is no longer secure, it was at the time a great enhancement to secure communications.

Vernam Cipher

The weakness discovered with the Vigenere cipher is the repeated use of the same key. In order to combat this problem the Vernam cipher was created. The key is as long as the plaintext so that no repetition is needed. For example, if we wanted to use the Vernam cipher to encrypt the message the length of 100, we might use 100 Caesar ciphers extended to 100 rows. This was a one-time pad used to encrypt messages. The Vernam cipher was used widely during World War II and the Cold War.

In principle, the one-time pad is as good as it gets when it comes to cryptography. This process is mathematically provable. The Vernam cipher operates in a similar fashion to the Caesar cipher. Wherein the Caesar cipher one number key is used as the shift cipher, the Vernam cipher operates through the use of many different shift ciphers being used, a unique one for each letter in the key. This is done by shifting the character according to the value of the letter it corresponds to in the alphabet. For example if the letter of the key was 'A' that would lead to a shift of 1.

When used correctly, the one-time pad is unbreakable, but it is difficult to transmit the one-time pad between the parties without interception. Another challenge is that the cipher (one-time pad) is impractical. If there is a way to transmit the message, then the person might as well send the message itself due to the length and complexity.

Today, we use more innovative practices to secure communication. Sophisticated ciphers (programs) use shorter keys and these keys are sequences of bits on which both parties agree to keep secret. This process works because computers divide ASCII-coded plaintext messages into blocks. The bits that make up that block are transformed according to a specific method that depends on the secret key created.

There are no known shortcuts for breaking secret key ciphers. Even using a brute-force attack is difficult because it requires guessing all possible keys but as the attack occurs the process grows exponentially in time based on the size of the key. Increasing the key length by only one bit doubles the work required to break the cipher. By creating longer keys it makes it possible to have the work outgrow the actual computing power. Due to this, breaking these ciphers is possible, but computationally infeasible, taking hundreds of years or more to crack.

The challenges that come with using secret key encryption is that the number of keys required increases as the number of network members increases. For each pair of members a new shared secret key must be created. Creating unique keys becomes more complicated as more combinations are needed. Another challenge is securely establishing a secret key between two parties when a secure channel does not exist between them.

Public Key Encryption

In 1976, Whitfield Diffie and Martin Hellman proposed the idea of public-key encryption. The idea is of two mathematically related keys a public key and a private key. The keys are paired, but computationally infeasible to connect to each other. A message encrypted using the private key can only be decrypted by the public key and vice versa.

When a user picks a secret key and encrypts the message with the recipient's public key and sends the ciphertext to the recipient. The recipient then uses their private key to decrypt the ciphertext to get the secret key. The private keys are kept secret and never sent to the other user. The two can communicate using the secret key (also known as a session key). The confidentiality of the message is ensured due to no one except the recipient being able to decrypt the message from the initiator.

The way to ensure the message is from the sender is to use digital signature schemes. Signatures should be easy for a user to produce, but difficult for anyone else to forge. Digital signatures can also be tied to the content of the message being signed. Authenticity of the message is verified due to the ciphertext only being decrypted with the intended party's private key.