The concept of securing messages through cryptography has a long history. Indeed, Julius Caesar is credited with creating one of the earliest cryptographic systems to send military messages to his generals.
Throughout history, however, there has been one central problem limiting
widespread use of cryptography. That problem is key management. In
cryptographic systems, the term key refers to a numerical value used by an algorithm
to alter information, making that information secure and visible only to individuals
who have the corresponding key to recover the information. Consequently, the term
key management refers to the secure administration of keys to provide them to users
where and when they are required.
Historically, encryption systems used what is known as symmetric cryptography.
Symmetric cryptography uses the same key for both encryption and decryption.
Using symmetric cryptography, it is safe to send encrypted messages without fear of
interception (because an interceptor is unlikely to be able to decipher the message);
however, there always remains the difficult problem of how to securely transfer the
key to the recipients of a message so that they can decrypt the message.
A major advance in cryptography occurred with the invention of public-key
cryptography. The primary feature of public-key cryptography is that it removes the
need to use the same key for encryption and decryption. With public-key
cryptography, keys come in pairs of matched “public” and “private” keys. The
public portion of the key pair can be distributed in a public manner without
compromising the private portion, which must be kept secret by its owner. An
operation (for example, encryption) done with the public key can only be undone
with the corresponding private key.
Prior to the invention of public-key cryptography, it was essentially impossible to
provide key management for large-scale networks. With symmetric cryptography, as
the number of users increases on a network, the number of keys required to provide
secure communications among those users increases rapidly. For example, a network
of 100 users would require almost 5000 keys if it used only symmetric cryptography.
Doubling such a network to 200 users increases the number of keys to almost
20,000. Thus, when only using symmetric cryptography, key management quickly
becomes unwieldy even for relatively small-scale networks.
Cryptography Algorithms
Classified along three independent dimensions:
· The number of keys used
o symmetric (single key, or private-key encryption)
ü Private Key encryption, also referred to as conventional, single-key or symmetric encryption was the only available option prior to the advent of Public Key encryption in 1976. This form of encryption has been used throughout history by Julius Caesar, the Navaho Indians, German U-Boat commanders to present day military, government and private sector applications. It equires all parties that are communicating to share a common key.
A conventional encryption scheme has five major parts:
Plaintext - this is the text message to which an algorithm is applied.
Encryption Algorithm - it performs mathematical operations to conduct substitutions and transformations to the plaintext.
Secret Key - This is the input for the algorithm as the key dictates the encrypted outcome.
Ciphertext - This is the encrypted or scrambled message produced by applying the algorithm to the plaintext message using the secret key.
Decryption Algorithm - This is the encryption algorithm in reverse. It uses the ciphertext, and the secret key to derive the plaintext message.
When using this form of encryption, it is essential that the sender and receiver have a way to exchange secret keys in a secure manner. If someone knows the secret key and can figure out the algorithm, communications will be insecure. There is also the need for a strong encryption algorithm. What this means is that if someone were to have a ciphertext and a corresponding plaintext message, they would be unable to determine the encryption algorithm.
There are two methods of breaking conventional/symmetric encryption - brute force and cryptanalysis. Brute force is just as it sounds; using a method (computer) to find all possible combinations and eventually determine the plaintext message. Cryptanalysis is a form of attack that attacks the characteristics of the algorithm to deduce a specific plaintext or the key used. One would then be able to figure out the plaintext for all past and future messages that continue to use this compromised setup.
o asymmetric (two-keys, or public-key encryption)
ü Public-key cryptography is a cryptographic approach, employed by many cryptographic algorithms and cryptosystems, whose distinguishing characteristic is the use of asymmetric key algorithms instead of or in addition to symmetric key algorithms. Using the techniques of public key-private key cryptography, many methods of protecting communications or authenticating messages formerly unknown have become practical. They do not require a secure initial exchange of one or more secret keys as is required when using in symmetric key algorithms. It can also be used to create digital signatures.
Public key cryptography is a fundamental and widely used technology around the world, and is the approach which underlies such Internet standards as Transport Layer Security (TLS) (successor to SSL), PGP and GPG.
The distinguishing technique used in public key-private key cryptography is use of asymmetric key algorithms because the key used to encrypt a message is not the same as the key used to decrypt it. Each user has a pair of cryptographic keys a public key and a private key. The private key is kept secret, whilst the public key may be widely distributed. Messages are encrypted with the recipient's public key and can only be decrypted with the corresponding private key. The keys are related mathematically, but the private key cannot be feasibly (ie, in actual or projected practice) derived from the public key. It was the discovery of such algorithms which revolutionized the practice of cryptography beginning in the middle 1970s.
- · The type of operations used for transforming plaintext to ciphertext
o Substitution
· monoalphabetic substitution - Formed by shifting the letters of the original alphabet
· polyalphabetic substitution - Extension of monoalphabetic substitution system and using Vigenere Tableau
o Transposition / Product
· unkeyed transposition - Rearrange letters by using matrix
· keyed transposition - Rearrange letters by using matrix where the size of matrix is determined by the length of the key used
· The way in which the plaintext is processed
o Block/Stream
Some Subtitution Techniques
In cryptography, a substitution cipher is a method of encryption by which units of plaintext are replaced with ciphertext according to a regular system; the "units" may be single letters (the most common), pairs of letters, triplets of letters, mixtures of the above, and so forth. The receiver deciphers the text by performing an inverse substitution.
Substitution ciphers can be compared with transposition ciphers. In a transposition cipher, the units of the plaintext are rearranged in a different and usually quite complex order, but the units themselves are left unchanged. By contrast, in a substitution cipher, the units of the plaintext are retained in the same sequence in the ciphertext, but the units themselves are altered.
There are a number of different types of substitution cipher. If the cipher operates on single letters, it is termed a simple substitution cipher; a cipher that operates on larger groups of letters is termed polygraphic. A monoalphabetic cipher uses fixed substitution over the entire message, whereas a polyalphabetic cipher uses a number of substitutions at different times in the message, where a unit from the plaintext is mapped to one of several possibilities in the ciphertext and vice-versa.
Monoalphabetic Subtitution Cipher
The ciphers in this substitution section replace each letter with another letter according to the cipher alphabet. Ciphers in which the cipher alphabet remains unchanged throughout the message are called Monoalphabetic Substitution Ciphers.
If we permit the cipher alphabet to be any rearrangement of the plain alphabet, then we can generate an enormous number of distinct modes of encryption. There are over 400,000,000,000,000,000,000,000,000 such rearrangements, which gives rise to an equivalent number of distinct cipher alphabets. Each cipher alphabet is known as a key. If our message is intercepted by the enemy, who correctly assumes that we have used a monoalphabetic substitution cipher, they are still faced with the impossible challenge of checking all possible keys. If an enemy agent could check one of these possible keys every second, it would take roughly one billion times the lifetime of the universe to check all of them and find the correct one.This simple brute force approach clearly will not work.
Plaintext alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ
Ciphertext key DEFGHIKLMNOPQRSTUVWXYZABC
A brute-force cryptanalysis is easily performed by trying all the keys available.
Polyalphabetic Substitution Cipher
This cipher ensures greater secrecy than Caesar cipher. 2 or more cipher alphabet which usually are interrelated are used to encipher a massage. An extension of the monoalphabet system through 26 alphabet can be formed.
How this Cipher Works
1. Pick a keyword (for our example, the keyword will be "MEC").
2. Write your keyword across the top of the text you want to encipher, repeating it as many times as necessary.
3. For each letter, look at the letter of the keyword above it (if it was 'M', then you would go to the row that starts with an 'M'), and find that row in the Vigenere table.
4. Then find the column of your plaintext letter (for example, 'w', so the twenty-third column).
5. Finally, trace down that column until you reach the row you found before and write down the letter in the cell where they intersect (in this case, you find an 'I' there).
Example:
| Keyword: | M E C M E C M E C M E C M E C M E C M E C M |
| Plaintext: | w e n e e d m o r e s u p p l i e s f a s t |
| Ciphertext: | I I P Q I F Y S T Q W W B T N U I U R E U F |
Thus, the urgent message "We need more supplies fast!" comes out:
I I P Q I F Y S T Q W W B T N U I U R E U F
So, as you can see, the letter 'e' is enciphered sometimes as an 'I' and sometimes as a 'Q'. Not only that, but 'I' represents two different letters, sometimes a 'w' and sometimes an 'e'. This renders our favorite tool, frequency analysis, nearly useless. Even though 'e' is used very often in the plaintext, the letters that replace it ('I' and 'Q') don't show up as frequently. Also, now if we check doubled letters in the ciphertext (say 'II' or 'WW'), these are not doubled letters in the plaintext.
You may, then, ask yourself "is there any hope?" Fortunately, there is! Given a long enough piece of ciphertext, certain words or parts of words (like "the") will line up with the keyword several times, giving rise to a repeated string of letters in the ciphertext ("the" may be enciphered as "KPQ" more than once). This can give us a clue as to the length of the keyword. After that, we can use frequency analysis on each piece that was enciphered with the same letter to crack the code. Consequently, cracking these ciphers hinges on finding repeated strings of letters in the ciphertext.
How to crack this cipher:
1. Search the ciphertext for repeated strings of letters; the longer strings you find the better (say you find the string "KPQ" four times). Note where they are by circling them or highlighting them in some manner.
2. For each occurrence of a repeated string, count how many letters are between the first letters in the string and add one (for example, if our ciphertext contains KPQRE IIJKO KPQAE, we count that there are nine letters between the first 'K' in the first "KPQ" and the first 'K' in the second "KPQ"; adding one yields ten).
3. Factor the number you got in the above computation (2 and 5 are factors of 10)
4. Repeat this process with each repeated string you find and make a table of common factors. The most common factor is probably the length of the keyword that was used to encipher the ciphertext (in our case, assume it was five). Call this number 'n'.
5. Do a frequency count on the ciphertext, on every nth letter. You should end up with n different frequency counts.
6. Compare these counts to standard frequency tables to figure out how much each letter was shifted by.
7. Undo the shifts and read off the message!
Examples
1. Encipher the following message using the Vigenere cipher and the keyword "IHS":
there is a secret passage behind the picture frame
Answer:
BOWZLAAHKMJJMAHIZKINWJLZQUVBOWXPUBBJMMJITW
2. There is an easier way to use the Vigenere cipher, using modular arithmetic. Discuss how you might do this (hint: represent each letter by a number, starting with 'a' = 0). Using this method, encipher the above message using the key 19, 15, 22
Answers
Encipher the following message using the key 19, 15, 22:
there is a secret passage behind the picture frame
Answer:
To do this, start by representing each letter of your plaintext by a number from 0-25 ('a' = 0, 'b' = 1, ..., 'y' = 24, 'z' = 25). Do the same for your key (unless, as in this case, it is already given by numbers). Then, write out the key over your plaintext just like you did for the letter-key. Finally, add the two numbers in each column. If this number is between 0 and 25, write down the corresponding letter. If it is bigger than 25, simply subtract 26 from that and write down the letter that corresponds to the number you get. Here's the first part of the example worked out:
"there is a secret passage" becomes:
19 07 04 17 04 08 18 00 18 04 02 17 04 19 15 00 18 18 00 06 04
We then write out the key repeatedly and put the message underneath:
| KEY: | 19 15 22 19 15 22 19 15 22 19 15 22 19 15 22 19 15 22 19 15 22 |
| MES: | 19 07 04 17 04 08 18 00 18 04 02 17 04 19 15 00 18 18 00 06 04 |
| | -------------------------------------------------------------- |
| SUM: | 38 22 26 36 19 30 37 15 40 23 17 39 23 34 37 19 33 40 19 21 26 |
| -26: | 12 22 00 10 19 04 11 15 14 23 17 13 23 08 11 19 07 14 19 21 00 |
| LET: | _M _W _A _K _T _E _L _P _O _X _R _N _X _I _L _T _H _O _T _V _A |
The whole answer is:
MWAKTELPOXRNXILTHOTVAUTDBCZMWAIXYMJNXUNTBA
3. Decipher the following message (work as a team!):
I C J E V A Q I P W B C I J R Q F V I F A Z C P Q Y M J A H N G F
Y D H W E Q R N A R E L K B R Y G P C S P K W B U P G K B K Z W D
S Z X S A F Z L O I W E T V P S I T Q I S O T F K K V T Q P S E O
W K P V R L J I E C H O H I T F P S U D X X A R C L J S N L U B O
I P R J H Y P I E F J E R B T V M U Q O I J Z A G Y L O H S E O H
W J F C L J G G T W A C W E K E G K Z N A S G E K A I E T W A R J
E D P S J Y H Q H I L O E B K S H A J V Y W K T K S L O B F E V Q
Q T P H Z W E R Z A A R V H I S O T F K O G C R L C J L O K T R Y
D H Z Z L Q Y S F Y W D S W Z O H C N T Q C P R D L O A R V H S O
I E R C S K S H N A R V H L S R N H P C X P W D S I L P L Z V Q L
J O E N L W Z J F S L C I E D J R R Y X J R V C V P O E O L J U F
Y R Q F G L U P H Y L W I S O T F K W J E R N S T Z Q M I V C W D
S C Z V P H V C U E H F C B E B K P A W G E P Z I S O T F K O E O
D N W Q Z Q W H Y P V A H K W H I S E E G A H R T O E G C P I P H
F J R Q
Answers
Decipher the following message (work as a team!):
I C J E V A Q I P W B C I J R Q F V I F A Z C P Q Y M J A H N G F
Y D H W E Q R N A R E L K B R Y G P C S P K W B U P G K B K Z W D
S Z X S A F Z L O I W E T V P S I T Q I S O T F K K V T Q P S E O
W K P V R L J I E C H O H I T F P S U D X X A R C L J S N L U B O
I P R J H Y P I E F J E R B T V M U Q O I J Z A G Y L O H S E O H
W J F C L J G G T W A C W E K E G K Z N A S G E K A I E T W A R J
E D P S J Y H Q H I L O E B K S H A J V Y W K T K S L O B F E V Q
Q T P H Z W E R Z A A R V H I S O T F K O G C R L C J L O K T R Y
D H Z Z L Q Y S F Y W D S W Z O H C N T Q C P R D L O A R V H S O
I E R C S K S H N A R V H L S R N H P C X P W D S I L P L Z V Q L
J O E N L W Z J F S L C I E D J R R Y X J R V C V P O E O L J U F
Y R Q F G L U P H Y L W I S O T F K W J E R N S T Z Q M I V C W D
S C Z V P H V C U E H F C B E B K P A W G E P Z I S O T F K O E O
D N W Q Z Q W H Y P V A H K W H I S E E G A H R T O E G C P I P H
Transposition
Transposition Cipher
This mapping is achieved by performing some sort of permutation on the plaintext letters. On this method, the letters are not replace, but rearranged. The letters are retained but moved from is position.
How the scytale cipher works
1. Get a scytale and a strip of parchment.
2. Wrap your parchment around your scytale until the stick is covered. Try to avoid overlapping and gaps.
3. Write your message along the length of the stick, one character per pass of the paper. If you need more space, rotate the stick away from you and keep writing.
4. Unwrap the scytale and send the scrambled message to a friend with the same-diameter stick.
5. The friend then wraps his scytale with the encoded parchment. Since the diameters are the same, the message is clearly legible!
This technique was very useful in ancient battles; the Spartans are known to have used this rather extensively. Each general was given a stick of uniform diameter so that he could quickly encipher and decipher any message sent from other generals. Notice how quick and easy this is to use!
However, it is also rather easy to crack. In a battle situation, the most likely way to crack this would be to steal a general's scytale. Then, each message could be read easily. However, it can be cracked even without stooping to theivery. As it ends up, the scytale is just a very old (and rather simple) version of a greater class of ciphers called matrix transposition ciphers. The way the simplest of these works is by picking a matrix of a fixed size (say, 6x10) and then writing your message across the rows. The encipherment step consists of writing down the letters in the matrix by following the columns. Here's a simple 6x10 example:
| T | R | O | O | P | S | H | E | A | D |
| I | N | G | W | E | S | T | N | E | E |
| D | M | O | R | E | S | U | P | P | L |
| I | E | S | S | E | N | D | G | E | N |
| E | R | A | L | D | U | B | O | I | S |
| M | E | N | T | O | A | I | D | | |
Where we've written the message:
troops heading west need more supplies. send general dubois' men to aid
row by row into the matrix. Then, to encipher this, we simply read off the columns to get:
TIDIE MRNME REOGO SANOW RSLTP EEEDO
SSSNU AHTUD BIENP GODAE PEIDE LNS
The scytale cipher is just like one of these. Note that the number of "rows" in your message is determined by the diameter of your stick and the size of your writing. Cracking them, as you may guess, is just a matter of systematic guess-and-check.
How to crack the simple matrix transposition ciphers:
1. Count how many letters are in the ciphertext (for this example, assume the ciphertext is 99 letters long)
2. Make all of the matrices that would fit such a length (e.g. 2x50, 3x33, 4x25, 5x20, 6x17, 7x15, 8x13, 9x11, 10x10). Use TWO of each size.
3. For each size matrix, write out the ciphertext across the rows on one copy. On the other copy, write out the ciphertext down the columns.
4. At each stage, see if you can find anything legible, reading perpendicular to how you put the ciphertext in.
A harder version of the matrix transposition cipher is the column-scrambled matrix transposition cipher. Just like the ones above, you find a matrix of suitable dimensions and write your text in row-by-row. If there are blank cells left, fill them in with a dummy character (sometimes an 'X'). However, before writing down the ciphertext from the columns, you first scramble the columns. This generates a new matrix of the same size. Now read off the text down the columns, as before. This is a harder cipher, but there is a systematic way to crack it.
How to crack the column-scrambled matrix transposition ciphers:
1. Count how many letters are in your ciphertext (for example, 75) and factor that number (75 =5*5*3).
2. Create all of the possible matrices to fit this ciphertext (in our case, 3x25, 5x15, 15x5, 25x3).
3. Write the ciphertext into these matrices down the columns.
4. For each of your matrices, consider all of the possible permutations of the columns (for n columns, there are n! possible rearrangements). In our case, we hope that the message was enciphered using one of the last two matrices (the 15x5 and the 25x3), since in those cases, we have only 6 and 120 possibilites to check (3! = 6, 5! = 120, 15! ~ 1.31x10^12, 25! ~ 1.55x10^25).
5. Rearrange each matrix to see if you get anything intelligible. Read the message off row-by-row. Note that this is much more easily done by a computer than by hand, but it is doable (for small matrices).
