Research on State of Art Cryptographic Algorithms and Their Mathematical Backgrounds

Mehmet Ariman June 9, 2011

1
1.1

HASH Algorithms
SHA-1

HASH is a table representation of a message. This representation is always created using a pre-dened scheme which means that message is processed according to this scheme. This scheme has to satisfy two important goals. These goals are to make it infeasible to nd a message to a given digest, HASH table, and to supply an algorithm in which it should be almost impossible to nd two messages with the same digest. One of the strongest HASH algorithms that satises these goals is called SHA-1. The outcome of the processed message in SHA-1 is a 160-bit message digest which is created by processing original message according to some complex logical operations. This 160-bit message digest is both a powerful mechanism to hide the unprocessed message and maintains a fast way if it is used in a Digital Signature Algorithm as it is just 160-bits. This section will introduce the algorithm that is explained in the FIPS 180-1 standard. After this point this paper will rst represent the preliminaries. Then the algorithm to create SHA-1 will be introduced afterwards. First of all it is essential to know the data types that will be used during 1

the computation of message digest. Data types that are going to be used in this computation are as followed: Bit : 1 bit Byte : 8 bits Word : 4 bytes Integer : 4 bytes SHA-1 algorithm computes the digest using bitwise operations. Bitwise operations that is used with this algorithms are logical AND, logical OR, logical XOR, logical COMPLEMENT and Circular Shift, this circular shift operation is where SHA-1 differs from SHA-0 which means that this is the part that is added to supply extra security, operations. It also use the addition operator on 32-bit integer in mod 232 . SHA-1 processes a predened block size which is 512-bits for this standard. In addition, this block size is crucial and if message contains elements which is not a multiple of 512-bits message padding is needed. Furthermore, when message padding is used, padding scheme should not only add 0 to the end of the original message. It should contain some random scheme so that the output can be more secure and can be protected from cryptanalysis. It is time to introduce the maximum bit length for message to be used in SHA1. It is 264 -bits. Thats why message length can be expressed with 64-bits as the bit representation is in base-2. The message padding scheme will be given below:

Padding Scheme If message is not a multiple of 512-bits after adding the length of the message to the end of the original message than add 1 after the original message. Then add 0 until it is a multiple of 512-bits. Original Message : 01101 that is 5 bits Length of the message : 5 bits which can be represented as 00000000 00000005 in HEX format when it is paddded it is going to be 64-bits After adding 1 : 011011 that is 6 bits

Message should be 512-bits for this case and we have 64-bits l and 6 bits of message as of now So we should add 512-(64+6) = 442 bits of 0 before adding l to complete the padding. The padded message :
442 61

011011 000 . . . 000 . . . 101 After padding the message is ready to be processed. To compute the message digest SHA-1 uses 80 steps for each block to create a temporary messsage digest until every-block is processed. These functions and the constants will be given below: Functions For 0 i 19 For 20 i 39 60 i 79 f (X, Y, Z) = (XY) (XZ) f (X, Y, Z) =XYZ

For 40 i 59 f (X, Y, Z) = (XY) (XZ) (Y Z) For simplication and optimization in hardware implementations X Y can be calculated once and used in both functions 1 and 3. More optimization issues will be handled after the end of research period for the algorithms.

Constants For 0 i 19 K = 5A827999 For 20 i 39 K = 6ED9EBA1 For 40 i 59 K = 8F1BB0DC For 60 i 79 K = CA62C1D6 3

Initial Values H0 H1 H2 H3 H4 = 67452301 = EF CDAB89 = 98BADCF E = 10325476 = C3D2E1F 0

Computation process starts with these initial conditions and constants. Then I will use the PSEUDO Code that is given in FIPS 180-1 standard then talk about the space requirements of the algorithm. Suppose that message M consist of n blocks. Each with the block size of 512-bits. Scatter Mi into W0 to W15 For 16 j 79 do Wj = S 1 (Wj3 Wj8 Wj14 Wj16 ) A = H0 , B = H1 , . . . , E = H4 For 0 j 79 do T EM P = S 5 (A) + f (B, C, D) + E + Wj + K E = D, D = C, C = S 30 (B), B = A, A = T EM P H0 = H0 + A, . . . , H4 = H4 + E 1 After that it is time to talk about required buffers for the implementation of the algorithm. First, there is a need for 5-words buffer as it is obvious that we have to store message digest in H sequence. Then we need additional 5-words buffer copy the values of H sequence so that we can process them without losing the initial values of the sequence as we need this initial values at the end of 80-steps loop to update message digest.There is also need for 80-word buffer for W. We also need a one word buffer for the variable TEMP as it is later going to be assigned to A at the end of every loop.
This algorithm is taken from FIPS 180-1 standard which can be obtained from the link http://www.itl.nist.gov/pspubs/p180-1.htm .
1

2
2.1

Asymmetric Ciphers
RSA

Main objective of this approach is to keep secret key hidden from other users. Whoever wants to send a message to the server should use public key to encrypt the message. Secret key is the asymmetric key that allows cipher text encrypted with the according public key to be decrypted. By this way secret key is not shared with anyone else. This is the main idea behind the asymmetric ciphers. RSA is the most popular asymmetric cipher. It nds two extremely large random prime numbers, p and q. Calculation pq=n is easy using calculator. However it is not feasible to retrieve p and q by just having n. It selects two more numbers related to p and q called d and e. Encryption = m e mod(n) Decryption = c d mod(n) RSA with keys shorter than 1024 bits is no longer safe but keys with 2048 bit are offered for long term applications as it is supposed to remain safe in this time. 2

This one is taken from the Webinar called Cryptology for Engineers of Jerry Kaczyn-

ski