Is Theory

CEASAR CIPHER In cryptography, a Caesar cipher, also known as a Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a shift of 3, A would be replaced by D, B would become E, and so on. The method is named after Julius Caesar, who used it to communicate with his generals.

The encryption step performed by a Caesar cipher is often incorporated as part of more complex schemes, such as the Vigenère cipher, and still has modern application in the ROT13 system. As with all single alphabet substitution ciphers, the Caesar cipher is easily broken and in practice offers essentially no communication security. The transformation can be represented by aligning two alphabets; the cipher alphabet is the plain alphabet rotated left or right by some number of positions. For instance, here is a Caesar cipher using a left rotation of three places (the shift parameter, here 3, is used as the key): Plain: Cipher:

ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC

To encrypt a message, simply look up each letter of the message in the "plain" line and write down the corresponding letter in the "cipher" line. To decipher, do the reverse. Plaintext: the quick brown fox jumps over the lazy dog Ciphertext: WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ The encryption can also be represented using modular arithmetic by first transforming the letters into numbers,

according to the scheme, A = 0, B = 1,..., Z = 25. Encryption of a letter x by a shift n can be described mathematically as,

Decryption is performed similarly.

(Note, There are different definitions for the modulo operation. In the above, the result is in the range 0...25. I.e., if x+n or x-n are not in the range 0...25, we have to subtract or add 26.) The replacement remains the same throughout the message, so the cipher is classed as a type of monoalphabetic substitution, as opposed to polyalphabetic substitution.

RAIL-FENCE CIPHER The Rail Fence Cipher is a form of transposition cipher that derives its name from the way in which it is encoded. In the rail fence cipher, the plaintext is written downwards and diagonally on successive "rails" of an imaginary fence, then moving up when we reach the bottom rail. When we reach the top rail, the message is written downwards again until the whole plaintext is written out. The message is then read off in rows. For example, if we have 3 "rails" and a message of 'WE ARE DISCOVERED. FLEE AT ONCE', the cipherer writes out: W . . . E . . . C . . . R . . . L . . . T . . . E . E . R . D . S . O . E . E . F . E . A . O . C . . . A . . . I . . . V . . . D . . . E . . . N . . Then reads off to get the ciphertext: WECRL TEERD SOEEF EAOCA IVDEN The rail fence cipher is not very strong; the number of practical keys is small enough that a cryptanalyst can try them all by hand.

THE RSA ALGORITHM In cryptography, RSA is an algorithm for public-key cryptography. It was the first algorithm known to be suitable for signing as well as encryption, and one of the first great advances in public key cryptography. RSA is widely used in electronic commerce protocols, and is believed to be secure given sufficiently long keys and the use of up-to-date implementations. The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. RSA involves a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys for the RSA algorithm are generated the following way: 1. Choose two distinct large random prime numbers p and q 2. Compute a.

is used as the modulus for both the public and private keys

3. Compute the totient:

.

4. Choose an integer e such that 1 < e < φ(n), and

and φ(n) share no factors other than 1 (i.e. e and φ(n) are coprime) a. e is released as the public key exponent

5. Compute d to satisfy the congruence relation

; i.e. de = 1 + kφ(n) for some integer k. a. d is kept as the private key exponent

The public key consists of the modulus (or encryption) exponent .

and the public

The private key consists of the modulus and the private (or decryption) exponent which must be kept secret.

Encrypting messages Alice transmits her public key to Bob and keeps the private key secret. Bob then wishes to send message M to Alice. He first turns M into a number < by using an agreedupon reversible protocol known as a padding scheme. He then computes the ciphertext corresponding to:

This can be done quickly using the method of exponentiation by squaring. Bob then transmits to Alice.

Decrypting messages Alice can recover from by using her private key exponent by the following computation:

Given

, she can recover the original message M.

DATA ENCRYPTION STANDARD [DES] The Data Encryption Standard (DES) is a cipher (a method for encrypting information) selected as an official Federal Information Processing Standard (FIPS) for the United States in 1976, and which has subsequently enjoyed widespread use internationally. DES is now considered to be insecure for many applications. This is chiefly due to the 56-bit key size being too small; in January, 1999, distributed.net and the Electronic Frontier Foundation collaborated to publicly break a DES key in 22 hours and 15 minutes. DES is a block cipher bases on the Fiestal-Network. The block size of DES is 64bits. The length of the key which is used to customize the transformation (the algorithm being constant) is 64bits. However only 56bits are used as the key and the remaining 8bits are used for checking the parity. Hence the effective key lengh is only 56bits. The algorithm's overall structure is shown in Figure 1: there are 16 identical stages of processing, termed rounds. There is also an initial and final permutation, termed IP and FP, which are inverses (IP "undoes" the action of FP, and vice versa). Before the main rounds, the block is divided into two 32-bit halves and processed alternately; this criss-crossing is known as the Feistel scheme. The Feistel structure ensures that decryption and encryption are very similar processes — the only difference is that the subkeys are applied in the reverse order when decrypting. The rest of the algorithm is identical. This greatly simplifies implementation, particularly in hardware, as there is no need for separate encryption and decryption algorithms. The red ⊕ symbol denotes the exclusiveOR (XOR) operation. The F-function scrambles half a block together with some of the key. The output from the F-function is then combined with the other half of the block, and the halves are swapped before the next round. After the final round, the halves are not swapped; this is a feature of the Feistel structure which makes encryption and decryption similar processes.

Fiestal Function

Key Schedule

DIFFIE HELLMAN KEY EXCHANGE

Diffie-Hellman (D-H) key exchange is a cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.

1. Alice and Bob agree to use a prime number p=23 and base g=5. 2. Alice chooses a secret integer a=6, then sends Bob (ga mod

p) 

56 mod 23 = 8.

3. Bob chooses a secret integer b=15, then sends Alice (gb mod

p) 

515 mod 23 = 19.

4. Alice computes (gb mod p)a mod p 

196 mod 23 = 2.

5. Bob computes (ga mod p)b mod p 

815 mod 23 = 2.

Both Alice and Bob have arrived at the same value, because gab and gba are equal. Note that only a, b and gab = gba are kept secret. All the other values are sent in the clear. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a, b, and p would be needed to make this example secure, since it is easy to try all the possible values of gab mod 23 (there will be, at most, 22 such values, even if a and b are large). If p were a prime of at least 300

digits, and a and b were at least 100 digits long, then even the best algorithms known today could not find a given only g, p, and ga mod p, even using all of mankind's computing power. The problem is known as the discrete logarithm problem. Note that g need not be large at all, and in practice is usually either 2 or 5.

BUFFER OVERFLOW AND FORMAT STRING ATTACKS Buffer overflows are a favorite exploit for hackers. The vast majority of Microsoft's available patches fix unchecked buffer problems -- but what about applications developed inhouse? They are just as susceptible as commercial applications to buffer-overflow attack. It is therefore critical that you understand how they work and perform vulnerability testing on your home-grown applications prior to deployment. A buffer overflow is an exploit that takes advantage of a program that is waiting on a user's input. In C this is generally done with its inability to check array bounds. Common attack procedurs include corrupting the data by entering data (especially strings) larger than allocated space when the program is waiting for the user input or otherwise using the inbuilt function sprintf() – a function to generate formatted strings. There are two main types of buffer overflow attacks: stack based and heap based. Heap-based attacks flood the memory space reserved for a program, but the difficulty involved with performing such an attack makes them rare. Stack-based buffer overflows are by far the most common In a stack-based buffer overrun, the program being exploited uses a memory object known as a stack to store user input. Normally, the stack is empty until the program requires user input. At that point, the program writes a return memory address to the stack and then the user's input is placed on top of it. When the stack is processed, the user's input gets sent to the return address specified by the program. However, a stack does not have an infinite potential size. The programmer who develops the code must reserve a specific amount of space for the stack. If the user's input is longer than the amount of space reserved for it within the stack, then the stack will overflow. This in itself isn't a huge problem, but it becomes a huge security hole when combined with malicious input. For example, suppose a program is waiting for a user to enter his or her name. Rather than enter the name, the hacker would enter an executable command that exceeds the stack size. The command is usually something short. In a Linux Environment, for instance, the command is typically EXEC("sh"), which tells the system to open a command prompt window, known as a root shell in Linux circles.

Yet overflowing the buffer with an executable command doesn't mean that the command will be executed. The attacker must then specify a return address that points to the malicious command. The program partially crashes because the stack overflowed. It then tries to recover by going to the return address, but the return address has been changed to point to the command specified by the hacker. Of course this means that the hacker must know the address where the malicious command will reside. To get around needing the actual address, the malicious command is often padded on both sides by NOP instructions, a type of pointer. Padding on both sides is a technique used when the exact memory range is unknown. Therefore, if the address the hacker specifies falls anywhere within the padding, the malicious command will be executed. The last part of the equation is the executable program's permissions. As you know, most modern operating systems have some sort of mechanism to control the access level of the user who's currently logged on and executable programs typically require a higher level of permissions. These programs therefore run either in kernel mode or with permissions inherited from a service account. When a stack-overflow attack runs the command found at the new return address, the program thinks it is still running. This means that the command prompt window that has been opened is running with the same set of permissions as the application that was compromised. Generally speaking, this often means that the attacker will gain full control of the operating system.

COLUMNAR TRANSPOSITION In a columnar transposition, the message is written out in rows of a fixed length, and then read out again column by column, and the columns are chosen in some scrambled order. Both the length of the rows and the permutation of the columns are usually defined by a keyword. For example, the word ZEBRAS is of length 6 (so the rows are of length 6), and the permutation is defined by the alphabetical order of the letters in the keyword. In this case, the order would be "6 3 2 4 1 5". In a regular columnar transposition cipher, any spare spaces are filled with nulls; in an irregular columnar transposition cipher, the spaces are left blank. Finally, the message is read off in columns, in the order specified by the keyword. For example, suppose we use the keyword ZEBRAS and the message WE ARE DISCOVERED. FLEE AT ONCE. In a regular columnar transposition, we write this into the grid as: 6 W I R E E

3 E S E A Q

2 A C D T K

4 R O F O J

1 E V L N E

5 D E E C U

Providing five nulls (QKJEU) at the end. The ciphertext is then read off as: EVLNE ACDTK ESEAQ ROFOJ DEECU WIREE In the irregular case, the columns are not completed by nulls: 6 W I R E E

3 E S E A

2 A C D T

4 R O F O

1 E V L N

5 D E E C

This results in the following ciphertext: EVLNA CDTES EAROF ODEEC WIREE

To decipher it, the recipient has to work out the column lengths by dividing the message length by the key length. Then he can write the message out in columns again, then re-order the columns by reforming the key word. Columnar transposition continued to be used for serious purposes as a component of more complex ciphers at least into the 1950's.

HASH FUNCTION In cryptography, a cryptographic hash function is a transformation that takes an input and returns a fixed-size string, which is called the hash value. Hash functions with this property are used for a variety of computational purposes, including cryptography. The hash value is a concise representation of the longer message or document from which it was computed. The message digest is a sort of "digital fingerprint" of the larger document. Cryptographic hash functions are used to do message integrity checks and digital signatures in various information security applications, such as authentication and message integrity. A hash function takes a string (or 'message') of any length as input and produces a fixed length string as output, sometimes termed a message digest or a digital fingerprint. A hash value (also called a "digest" or a "checksum") is a kind of "signature" for a stream of data that represents the contents. One analogy that explains the role of the hash function would be the "tamper-evident" seals used on a software package. In various standards and applications, the two mostcommonly used hash functions are MD5 and SHA-1. In 2005, security flaws were identified in both algorithms. In 2007 the National Institute of Standards and Technology announced a contest to design a hash function which will be given the name SHA-3 and be the subject of a FIPS standard.