.:: || Modern Cryptography || ::.

Modern Cryptograpy Algorithm

Most modern ciphers use a sequence of binary digits (bits), that is, zeros and ones such as ASCII.

This bit sequence representing the plaintext is then encrypted to give the ciphertext as a bit sequence.

Stream Ciphers



A Stream Cipher is a symmetric key cipher where plaintext bits are combined with a pseudorandom cipher bit stream (keystream), typically by an exclusive-or (xor) operation. In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption. An alternative name is a state cipher, as the encryption of each digit is dependent on the current state. In practice, the digits are typically single bits or bytes.

Stream ciphers represent a different approach to symmetric encryption from block ciphers. Block ciphers operate on large blocks of digits with a fixed, unvarying transformation. This distinction is not always clear-cut: in some modes of operation, a block cipher primitive is used in such a way that it acts effectively as a stream cipher. Stream ciphers typically execute at a higher speed than block ciphers and have lower hardware complexity. However, stream ciphers can be susceptible to serious security problems if used incorrectly: see stream cipher attacks — in particular, the same starting state must never be used twice.

Type of Stream Ciphers

1.Synchronous stream ciphers

In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher.

In a synchronous stream cipher, the sender and receiver must be exactly in step for decryption to be successful. If digits are added or removed from the message during transmission, synchronisation is lost. To restore synchronisation, various offsets can be tried systematically to obtain the correct decryption. Another approach is to tag the ciphertext with markers at regular points in the output.

2.Self-synchronizing stream ciphers

This is a another approach uses several of the previous N ciphertext digits to compute the keystream. Such schemes are known as self-synchronizing stream ciphers, asynchronous stream ciphers or ciphertext autokey (CTAK). The idea of self-synchronization was patented in 1946, and has the advantage that the receiver will automatically synchronise with the keystream generator after receiving N ciphertext digits, making it easier to recover if digits are dropped or added to the message stream. Single-digit errors are limited in their effect, affecting only up to N plaintext digits.

An example of a self-synchronising stream cipher is a block cipher in cipher-feedback mode (CFB).

Block Ciphers

A block cipher is a symmetric key cipher operating on fixed-length groups of bits, termed blocks, with an unvarying transformation. A block cipher encryption algorithm might take (for example) a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext. The exact transformation is controlled using a second input — the secret key. Decryption is similar: the decryption algorithm takes, in this example, a 128-bit block of ciphertext together with the secret key, and yields the original 128-bit block of plaintext.

To encrypt messages longer than the block size (128 bits in the above example), a mode of operation is used.

Block ciphers can be contrasted with stream ciphers; a stream cipher operates on individual digits one at a time, and the transformation varies during the encryption. The distinction between the two types is not always clear-cut: a block cipher, when used in certain modes of operation, acts effectively as a stream cipher.

An early and highly influential block cipher design was the Data Encryption Standard (DES), developed at IBM and published as a standard in 1977. A successor to DES, the Advanced Encryption Standard (AES)

A block cipher consists of 2 paired algorithms, one for encryption, E, and another for decryption, E-1. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits, yielding an n-bit output block. For any one fixed key, decryption is the inverse function of encryption, so that

E_K^{-1}(E_K(M))=M

for any block M and key K.

Data Encryption Standard(DES)



The Data Encryption Standard (DES) is a block cipher (a form of shared secret encryption) that was selected by the National Bureau of Standards as an official Federal Information Processing Standard (FIPS) for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is based on a symmetric-key algorithm that uses a 56-bit key. The algorithm was initially controversial with classified design elements, a relatively short key length, and suspicions about a National Security Agency (NSA) backdoor. DES consequently came under intense academic scrutiny which motivated the modern understanding of block ciphers and their cryptanalysis.



DES is now considered to be insecure for many applications. There are also some analytical results which demonstrate theoretical weaknesses in the cipher, although they are unfeasible to mount in practice. The algorithm is believed to be practically secure in the form of Triple DES, although there are theoretical attacks. In recent years, the cipher has been superseded by the Advanced Encryption Standard (AES).

Advanced Encryption Standard

the Advanced Encryption Standard (AES) is an encryption standard adopted by the U.S. government. The standard comprises three block ciphers, AES-128, AES-192 and AES-256, adopted from a larger collection originally published as Rijndael. Each AES cipher has a 128-bit block size, with key sizes of 128, 192 and 256 bits, respectively. The AES ciphers have been analyzed extensively and are now used worldwide, as was the case with its predecessor,[3] the Data Encryption Standard (DES).

AES was announced by National Institute of Standards and Technology (NIST) as U.S. FIPS PUB 197 (FIPS 197) on November 26, 2001 after a 5-year standardization process in which fifteen competing designs were presented and evaluated before Rijndael was selected as the most suitable. It became effective as a standard May 26, 2002. As of 2009[update], AES is one of the most popular algorithms used in symmetric key cryptography.[citation needed] It is available in many different encryption packages. AES is the first publicly accessible and open cipher approved by the NSA for top secret information.

High-level description of the algorithm

• KeyExpansion using Rijndael's key schedule


• Initial Round

1. AddRoundKey

• Rounds

1. SubBytes — a non-linear substitution step where each byte is replaced with another according to a lookup table.
2. ShiftRows — a transposition step where each row of the state is shifted cyclically a certain number of steps.
3. MixColumns — a mixing operation which operates on the columns of the state, combining the four bytes in each column
4. AddRoundKey — each byte of the state is combined with the round key; each round key is derived from the cipher key using a key schedule.

• Final Round (no MixColumns)


• 1. SubBytes


• 2. ShiftRows


• 3. AddRoundKey

The SubBytes step

In the SubBytes step, each byte in the array is updated using an 8-bit substitution box, the Rijndael S-box. This operation provides the non-linearity in the cipher. The S-box used is derived from the multiplicative inverse over GF(28), known to have good non-linearity properties. To avoid attacks based on simple algebraic properties, the S-box is constructed by combining the inverse function with an invertible affine transformation. The S-box is also chosen to avoid any fixed points (and so is a derangement), and also any opposite fixed points.

The ShiftRows step

The ShiftRows step operates on the rows of the state; it cyclically shifts the bytes in each row by a certain offset. For AES, the first row is left unchanged. Each byte of the second row is shifted one to the left. Similarly, the third and fourth rows are shifted by offsets of two and three respectively. For the block of size 128 bits and 192 bits the shifting pattern is the same. In this way, each column of the output state of the ShiftRows step is composed of bytes from each column of the input state. (Rijndael variants with a larger block size have slightly different offsets). In the case of the 256-bit block, the first row is unchanged and the shifting for second, third and fourth row is 1 byte, 3 bytes and 4 bytes respectively - this change only applies for the Rijndael cipher when used with a 256-bit block, as AES does not use 256-bit blocks.

The MixColumns step

In the MixColumns step, the four bytes of each column of the state are combined using an invertible linear transformation. The MixColumns function takes four bytes as input and outputs four bytes, where each input byte affects all four output bytes. Together with ShiftRows, MixColumns provides diffusion in the cipher. Each column is treated as a polynomial over GF(28) and is then multiplied modulo x4 + 1 with a fixed polynomial c(x) = 3x3 + x2 + x + 2. The MixColumns step can also be viewed as a multiplication by a particular MDS matrix in Finite field. This process is described further in the article Rijndael mix columns.

The AddRoundKey step

In the AddRoundKey step, the subkey is combined with the state. For each round, a subkey is derived from the main key using Rijndael's key schedule; each subkey is the same size as the state. The subkey is added by combining each byte of the state with the corresponding byte of the subkey using bitwise XOR.

Message Authentication Code

A message authentication code (often MAC) is a short piece of information used to authenticate a message.

A MAC algorithm, sometimes called a keyed (cryptographic) hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC (sometimes known as a tag). The MAC value protects both a message's data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the message content.

Message Authentication Code Flow



the sender of a message runs it through a MAC algorithm to produce a MAC data tag. The message and the MAC tag are then sent to the receiver. The receiver in turn runs the message portion of the transmission through the same MAC algorithm using the same key, producing a second MAC data tag. The receiver then compares the first MAC tag received in the transmission to the second generated MAC tag. If they are identical, the receiver can safely assume that the integrity of the message was not compromised, and the message was not altered or tampered with during transmission.

Hash Function

A hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the (cryptographic) hash value, such that an accidental or intentional change to the data will change the hash value. The data to be encoded is often called the "message", and the hash value is sometimes called the message digest or simply digest.

The ideal cryptographic hash function has four main properties:

• it is easy to compute the hash value for any given message,


• it is infeasible to find a message that has a given hash,


• it is infeasible to modify a message without changing its hash,


• it is infeasible to find two different messages with the same hash.

A cryptographic hash function (specifically, SHA-1) at work. Note that even small changes in the source input drastically change the resulting output, by the so-called avalanche effect.

RSA( Rivest, Shamir & Adleman)

RSA (which stands for Rivest, Shamir and Adleman who first publicly described it) is an algorithm for public-key cryptography. It is 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.

RSA Key Setup Example :

• 1.Select primes: p=17 & q=11


• 2.Compute n = pq =17 x 11=187


• 3.Compute ø(n)=(p–1)(q-1)=16 x 10=160


• 4.Select e: gcd(e,160)=1; choose e=7
• 
  
• 5.Determine d: de=1 mod 160 and d < 160 Value is d=23


• 6.Publish public key PU={7,187}


• 7.Keep secret private key PR={23,187}

RSA Key Generation

users of RSA must:
determine two primes at random - p, q
select either e or d and compute the other

primes p,q must not be easily derived from modulus n=p*q
means must be sufficiently large
typically guess and use probabilistic test

exponents e, d are inverses, so use Inverse algorithm to compute the other