Classic Cryptography
Modern Mathematical Cryptography
Links
Cryptography
Cryptology is the art and science of keeping messages secret. In cryptography, a clear message is called plaintext. Encoding a message in such a way that hides its contents is called encryption: it is simply the scrambling of a plaintext through the use of an algorithm, with a purpose of protecting this data from being eavesdropped. The encrypted message is called the ciphertext which is a series of characters that are impossible to understand. The opposite of this is called decryption, which transforms ciphertext to plaintext.
A method of encryption and decryption is called a cipher: some cryptographic methods, the older ones, rely on the secrecy of the algorithms, but all modern algorithms are accomplished with the assistance of an external piece of data, which often comes in the form of a user-selected password and that is called a key. This not only makes the encryption stronger by enforcing a unique key, but it also keeps anyone who does not know the key from accessing the data.
Classic Cryptography
The history of cryptography dates back thousands of years. Until recent decades, it has been a history of classic cryptography — of methods of encryption that use pen and paper, or perhaps simple mechanical aids. In the early 20th century, the invention of complex mechanical and electromechanical machines, such as the Enigma rotor machine, provided more sophisticated and efficient means of encryption; and the subsequent introduction of electronics and computing has allowed elaborate schemes of still greater complexity.
Caesar Cipher
The Caesar Cipher (Shifting) is one of the simplest monoalphabetic substitutions one may use, and it is also one of the easiest to break.
It is said that Julius Caesar wrote to his friends using a simple substitution cipher,
where the plaintext letter was replaced by the ciphertext three places down the alphabet (+3),
so that the letter M is replaced by P and so on.
It is now the case that any cipher that uses shifting of any length is called a
Caesar cipher. For example, we can shift only one place (+1) down the alphabet, or go back one place (-1)
PLAINTEXT abcdefghijklmnopqrstuvwxyz
CIPHERTEXT DEFGHIJKLMNOPQRSTUVWXYZABC
As there are only 26 Caesar alphabets it is trivial to solve a caesar cipher by
exhaustive search. This is can be done by listing the alphabet under each letter of a
section of the ciphertext. The line which contains legible plaintext is the correct one.
plain text walid
cipher text zdolg
Transposition
Transposition is not really a full-fledged method of cipher in its own, but it can form
and usually is used in a stage of more complex cryptosystems (such as in applying
key-based encryption). Transposition is simply moving the relative positions of letters
within a message. We will discuss a columnar transposition below, so called because the
text is arranged into columns and the columns are transposed.
When performing a columnar transposition, a keyword is first needed. The message is
then written into rows beneath the keyword. The example message which we'll use will be
"SECRET MESSAGES".
e n c r y p t
2 3 1 5 7 4 6
S E C R E T M
E S S A G E S
Adding some numbers beneath the keyword, the numbers refer to the relative positions of
the keyword letters in the alphabet. Having formed the table we can read back the message
in the order of the keyword letters. This message becomes CSETRME SESEASG. The spaces have
been included for clarity, although in practice this will not happen.
Transpositions are often used as part of a more complex system. If a transposition is
used in conjunction with a monoalphabetic substitution then the transposition as above may
be solved, after having first worked out the plaintext letters of the substitution by
looking at letter frequencies. Imagine the possibilities.
As with many cryptographic systems the greater the amount of ciphertext that is
available, the easier the cipher is to solve. Transposition adds some security, however as
with all cryptography, sometimes the solution is easier than one might be inclined to
believe.
Polybius cipher
Polybius was the name of the Greek who invented a system of converting alphabetic
characters into numeric characters. It was devised to enable messages to be easily
signalled using torches.
| # |
1 |
2 |
3 |
4 |
5 |
| 1 |
a |
b |
c |
d |
e |
| 2 |
f |
g |
h |
ij |
k |
| 3 |
l |
m |
n |
o |
p |
| 4 |
q |
r |
s |
t |
u |
| 5 |
v |
w |
x |
y |
z |
Doesn’t that work nicely? Try
the following message:
Ciphertext: 31 44 43 22 24 11 53 32 45 – 42 34 – 12 54 33
Each letter may be represented by two numbers by looking up the row the letter is in
and the column. For instance h=23 and r=42.
The idea was that a message may be transmitted by holding different combinations of
torches in each hand. The chequerboard has other important characteristics, namely the
reduction in the number of different characters, the conversion to numbers and the
reduction of a symbol into two parts which are separately manipulable. As such
chequerboards form the basis for many more ciphers.
Varients of this idea are used to convert a single character into units which may be
manipulated seperately, this can lead to some very strong ciphers.
Modern Cryptography
Modern cryptography is based on complex mathematical concepts
Hash Functions
Hash functions are one-way function H that operates on a message M of any length to produce a hash value h of fixed length. The value h can be considered a fingerprint of M. Therefore, H (M) = h. Hash functions have some important characteristics:
Using these characteristics of hash function, it would take us 1.07 * 1022 years to brute force a 128-bit MD5 (Message Digest 5) hash (collisions in 2128 operations) using a supercomputer that can process 1 billion messages per second. Using the "Birthday attack" reduces the collisions in MD5 to 264 operations, thus reducing the time to brute force an MD5 to almost 584 years!
The most recent attack on SHA-1 (Secure Hash Algorithm-1), a 160-bit hashing function, found collisions in about 263 operations, that is, it requires a computer processing 1 billion messages per second, about 292 years in order to brute force it. This shows the strength of these one-way hashing functions. Some of the hash functions are: Snefru, MD4, MD5, SHA-0 and SHA-1.
Symmetric Encryption
Symmetric encryption and decryption processes, also called private-key cryptography, are both accomplished using the same key. This is the most common form of encryption: the sender encrypts the message using the secret key; the receiver, holding this same key, decrypts the message using it. Symmetric encryption is much faster than asymmetric encryption that we will see later. However, the difficulty with symmetric encryption is that its security depends upon keeping its password, or key, secret. When two parties wish to communicate securely using a symmetric cipher, they first must agree upon the shared secret in a secure fashion: they should find a secure way to share the key. This is the problem of this type of encryption: finding a secure channel to share the secret key.
Examples of popular symmetric encryption algorithms include RC4 (Rivest Cipher 4), DES (Data Encryption Standard), and AES (Advanced Encryption Standard) ciphers. Symmetric ciphers operate in one of two fashions, stream or block. In a stream cipher, such as RC4, each byte of the plaintext (encryption) or ciphertext (decryption) is processed individually, that is, a byte is the basic unit. In a block cipher such as AES, the plaintext or ciphertext is grouped together into blocks of a predetermined and fixed size and then processed as a single unit. It is important to understand the differences and the benefits of how they work in order to understand how RC4 encrypts data.
Asymmetric Encryption
The other type of encryption is known as asymmetric or public-key cryptography. This encryption is much more complex, but it is more secure. A growing number of applications are using this type of security: Email applications, Digital Signatures and many others. Asymmetric encryption requires the use of two keys called key pairs: one of them is the public key that needs not to be secure, and can be widely distributed; and a corresponding key called private key that should remain secret and private only to the party who is involved in decrypting ciphertexts generated from the correspondent public key. In other words, if you want to send an encrypted message to a recipient, you should encrypt this message using his own public key. Later on, this recipient uses his private key in order to decrypt this message; there is no other method to decrypt this ciphertext.
Note that asymmetric encryption requires everyone to have access to a copy of the recipient’s public key for them to send him an encrypted message. The public key is usually shared in the form of a certificate that includes information that uniquely identifies the holder of the key pair as well as the signature of the issuer which is a trusted entity called a Certificate Authority, that makes sure that the identity linked to the public key in the certificate is correct. The process that issues and revokes public key certificates is called a Public Key Infrastructure, or PKI.
This one extra step of sharing the key, as well as the fact that they are much slower than 'comparably' secure symmetric key algorithms, increase the level of complexity just enough to limit the universal adoption of asymmetric encryption. An example of an asymmetric encryption algorithm is the widely used RSA public-key algorithm designed by Rivest, Shamir, and Adleman.
Cryptography Links
Computer Pages
|