Cryptography is the manipulation of information by deterministic mathematical functions. It is common to describe such a function in the form of an algorithm, an unambiguous set of instructions. Such an algorithm is known as a cryptographic algorithm. The enciphering phase of a cryptographic algorithm transposes information into a set of ciphertexts, which obscures the information. When information has gone through the enciphering phase it is enciphered, groups of enciphered symbols are called ciphertext. The deciphering phase of a cryptographic algorithm transposes ciphertext into a set of plaintexts, which reveals the original information. When enciphered information has gone through the deciphering phase it is deciphered, groups of deciphered symbols are called plaintext.
A standard cryptographic algorithm will decide on how to transpose information by consulting a number pattern. There must also exist an algorithm that will restore the original information in a reasonable amount of time. The optimal cryptographic algorithm will have only one decryption algorithm which will execute in a reasonable amount of time for all input sizes. It will become clear, however, that it is difficult to prove that all points of attack on a cryptographic algorithm have been secured. In secret key cryptography, the cryptographic algorithm employs the same pattern of numbers to decide how to encipher and decipher information. This number pattern is known as the secret key. Public key, or asymmetric, cryptography utilizes a different concept for information restoration. A public key is distributed freely and a secret key is kept secret. One would encrypt information using the public key which only the secret key could decrypt. Imagine the symbols of the English alphabet being placed around the perimeter of a circle, each being assigned a successive number ranging from one to twenty six. This simplistic public key algorithm will substitute a symbol from around the circle, and the number pattern, or public key, will dictate by what magnitude, for example 90 spaces. What is needed to complete the decryption is a final number which will push this new symbol around the circle enough spaces that the original symbol will be restored, perhaps 40 spaces. Notice that (90+40)/26 is exactly 5 trips around the circle. This is the concept behind asymmetric cryptography, the keys for encryption and decryption are asymmetric. Public key and Secret key cryptography are the two major paradigms in modern cryptology. Both are built around the premise that a solution without the key will take time, the average amount of which serves as a measure of the algorithm's security. Public key cryptography will be discussed in greater detail later in the section.
Caesar's Cipher:
Caesar’s Cipher transposes symbols of the alphabet by a single interval.
The string "Sensitive Information" could be represented as follows:
"Tfotjujwf Jogpsnbujpo"
We have incremented the initial S by 1 to obtain T, the following e by 1 to
obtain f, and continued in the same fashion until we encountered the end of the
string. In order to decipher we will either decrement each letter by 1 or
increment each letter by -1. The difference between the two approaches is
subtle. If we subtract 1 from each letter we are using the inverse operation
while preserving the integrity of the key, in the latter we are preserving the
integrity of the operation while using the inverse key relative to the
operation of addition, the additive inverse of the original key. Both
approaches effectively transpose each symbol by 0 spaces.
These approaches still do not exhaust all possibilities, adding 25 to each letter will also reveal our original information. This is so since the domain of possible keys is finite, this more closely resembles the public key approach.
If you are asked to pick a password between 4 and 8 characters in length the domain of possible passwords is certainly finite; however, the set of possibilities is extremely large. Let us restrict the alphabet for the password to 26 lowercase letters (a-z), 26 uppercase letters (A-Z), and 10 numbers (0-9). There are 62 elements in the alphabet for the password; therefore, we have 624 + 625 + 626 + 627 + 628 different combinations of alphabet elements. That's more than 221 trillion different possibilities, which in many cases is secure enough. If a processor could attempt 1000 passwords per second it would take 221 billion seconds or about 7000 years to try all possibilities. Probabilistically, a computer (if trying random strings of different lengths between 4 and 8 characters) would have to go through half of the possible strings, so it would take approximately 3500 years to hit the correct password. Though, this is if the password is picked "randomly." If the user picks a password from the dictionary, or if more users pick passwords of length 4 than length 8, or if numbers are more likely found in clusters than distributed randomly throughout the password, than our cryptanalyzer has a vastly reduced set of attempts. This should give you an idea as to some of the hurdles that must be overcome in cryptography.
Since in Caesar's Cipher using the
English alphabet there are only 25 other possibilities for our key, it is very
simple for the cryptanalyzer to decipher our data.
This fact is best shown by demonstrating the process.
"Tfotjujwf Jogpsnbujpo"
+ 1 =
"Ugpukvkxg Kphqtocvkqp"
+ 1 =
.
.
.
"Sensitive Information"
We have run into possible cipher code that resembles English. We can now feel
confident that we have cracked Caesar's Cipher.
Another way to attack the problem of deciphering the string "Tfotjujwf Jogpsnbujpo" is to account for statistical relationships between cipher text and the language in which it is written. If intercepted from a country where English is the standard language, a cryptanalyzer would do well in assuming that the original plaintext was English. After noticing that the letter j appears 4 times the cryptanalyzer should realize that, statistically, i is a very common letter; therefore, if they tried j = i and transposed each letter by (j + x = i) = -1 they would quickly reveal the solution. In a worst case scenario the cryptanalyzer would have to attempt all 25 possible representations of j.
The next hurdle of cryptography is to design algorithms which remove any statistical congruency between language and ciphertext.
Cryptographers very often assume that their encryption algorithm is known by the cryptanalyzers. Arguably, if I am creating an algorithm for widespread use, the algorithm is eventually going to leak, and if all of my encrypted information relies on the secrecy of the algorithm then my secret key is not the only key, now the algorithm becomes a target for cryptanalyzers.
Our initial deciphering attempt on Caesar's Cipher is known as a brute force attack. A brute force attack is an attack on cipher text where the cryptanalyzer tries all possible keys. For Caesar's Cipher applied to the English alphabet, a brute force attack would require an average of 25/2 keys, given that the keys were chosen randomly. When dealing with Caesar's Cipher, a brute force attack is not work intensive for humans. Computers have little trouble dealing with much more complex ciphers using a brute force method.
The method of substituting symbols
for information in a reversible fashion is called substitution. Another
cryptographic method, called transposition, changes the position of symbols
relative to other symbols.
The string "Sensitive Information" could be transposed as follows:
"siftevoinerosimnina t"
"(S)ift(E)voi(N)ero(S)imn(I)na
(T)"
This method does not hide statistical linguistic patterns; in fact, all of the
original symbols are available for analysis. Also, if a cryptanalyzer
was somewhat savvy to the topic of the information their eye might jump at
certain words. 'SENSIT' might give up the word sensitive and the pattern can be
quickly realized by following the rendering of the word sensitive. So one might
attempt to transpose the letters again:
The original string "siftevoinerosimnina t" might be rendered as follows:
"t aninmisoreniovetfis"
One may also attempt to use substitution as well:
"u.bojonjtpsfojpwfugjt"
Now we are approaching a good cipher... even with the power of statistical anaylsis, which still works here since like letters remain
like, a cryptanalyzer has a headache. Perhaps all of
the j's are i's but how did
they get into their positions? A problem of this sort is still easy for a
computer, but if we applied this transposition and substitution method 16 times
to blocks of 64 bits we would not only have an adequate cipher method for
everyday ciphering (throughout the 1970's and 1980's anyhow), but we would also
have the Data Encryption Standard (DES) algorithm.
Although mention Vigenere's Cipher is a bit of a regression, it is important to understand how it hides statistical information. The basic premise to Vigenere's Cipher is that transposition of adjacent symbols takes place by separate intervals determined by multiple keys. In Vigenere's Cipher, this key repeats when the number of letters transposed is equivalent to the keylength.
Given the string "Sensitive Information" and a key of 1,3,4 the cipher text would appear as follows:
Sensitive Information
134134134 13413413413
"Thrtlxjyi Jqjpuqbwmpq"
It is interesting to note that a cryptanalyzer will
not be able to analyze linguistic patterns directly. First, they must attempt
to find the length of the key, and then group letters that have been transposed
by the same interval. Within these groups one would be able to recognize
linguistic patterns. Vigenere's Cipher, as it stands,
is not secure enough for modern times; however, it begins to eliminate the
problem of linguistic analysis from ciphertext. Using
computers, it would require very little time to discover the key length by
searching for small standard words such as of, or, etc. Taking the gcd of the number of symbols between them will very often
reveal the keylength.
As we have seen, we can use the
addition operation to create cipher text, along the same lines we can use
multiplication or the ‘exclusive or’ function (xor).
If two bits encountered by the exclusive or function are equivalent than the
function returns a 0, if those two bits are different, than a 1 is returned.
1 xor 1 = 0 0 xor 1 = 1
0 xor 0 = 0 0 xor 0 = 0
1 xor 0 = 1 1 xor 0 = 1
0 xor 1 = 1 1 xor 1 = 0
If we xor the result of an exclusive or of two bits
with one of the pair of bits we encounter the other bit. In the above example,
1 0 1 0 may be thought of as original plaintext, 1 0 0
1 would then represent our key, and 0 0 1 1 is our cipher text (a). She who has the key, 1 0 0 1 can decipher the ciphertext
into the original plaintext (b).
The one time pad, or Vernan Cipher, which was invented around WWI keeps information perfectly secret. This method employs a book full of random numbers (one way to get fairly good pseudo-random numbers is to count the number of micro-seconds in between cosmic ray emissions detected on a Geiger-counter) of which only the encryptor and the receiving party have a copy. Each unit (bit, character, etc.) is then encrypted using the next unused random number from the pad. If the same book is ever reused than there is a pattern to analyze.
What cryptographers would like to
do is to model the one time pad as closely as possible, while employing a more
practical method of cryptography. The cryptographer searches for a balance
between accessibility and reliability.
Using very good pseudo-random number generators (more simply referred to as
random number generators) the encryption key can be changed every cycle. The
original key would represent the seed to the random number generator's
algorithm, and the algorithm could be reversed in order to decrypt the
information. Larger initial seeds require more work for a brute force attack.
The random number generator produces chunks of bits based upon the initial
seed. If the initial seed is 128 bits long than we refer to our encryption
method as 128 bit encryption.
The secret key paradigm has inherent limitations. For instance, in order to
safely deliver a key to the intended receiving party, it must be hand
delivered. A much more practical method for the mass encryption needs
introduced by the internet is called public key encryption.
Public key encryption employs a
public key, which is distributed freely, and a secret key, which is not. If
there exists an algorithm where one can encipher a
message that can easily be decrypted with a separate key, not the encryption
key, than theoretically anyone in the world can encrypt a message, using the
public key, but only the secret key can decrypt that message. This is much more
useful for applications such as the internet.
The model of public key encryption that we will introduce in this section, RSA,
requires some basic knowledge of modular arithmetic. The
modulo operator, denoted mod, takes a number and a modulus as arguments
and returns the remainder upon division of the number by the modulus.
5 mod 2 = 1 since 2 * 2 = 4 + 1 = 5
2 mod 5 = 2 since 5 * 0 = 0 + 2 = 2
Useful modular identities:
a * b (mod m) = (a mod m) * (b mod m) mod m
Fermat's Little Theorem:
Let:
p = prime number
m = integer
m(p-1) mod p = 1
Euler's Identity:
Let:
p = integer
q = integer
m = integer
Such that p and q are relatively prime (GCD(p, q) = 1).
m(p-1)(q-1) mod (p * q) = 1
With some manipulation we encounter an ingenious public key method...
m * m(p-1)(q-1) mod (p * q) = m
m(p-1)(q-1)+1 mod (p * q) = m
Now let's pick two large prime numbers, p and q: large numbers composed
of two large primes are hard to factor.
Remember the exponent to m in the final manipulation was (p-1)(q-1)+1.
Let's pick two numbers, e and d, such that e * d = (p-1)(q-1)+1,
and a number n such that n = p * q. The numbers e and n can be released as a
public key and d will be the secret key. The routine appears as follows:
Assume m represents the plaintext.
me mod n -> c
cd mod n -> m
Without d, it is a hard problem to
figure out what number completes the modular circle.
Public key encryption allows security over an insecure channel of
communication, and is used extensively over the internet. There are other
algorithms that work in this fashion, though we will not visit them in this
section.