Space & Time Complexity of SHA-2

Question

I am wondering what the space and time complexity of SHA-2 is. I tried looking around, didn't really get a straight forward answer. Can anyone help me out? Thanks very much!

Answer 1

For example, let's consider SHA-256.

Based on the description of the algorithm given here, main steps are:

1. Initialise h1,..,h8 (first 32 bits of the fractional parts of the square roots of the first 8 primes 2..19).
2. Initialise k1,...,k64 (first 32 bits of the fractional parts of the cube roots of the first 64 primes 2..311).

Since their number is fixed, then the time complexity and space complexity needed for their initialisation is constant.

3. Break the message into 512- bit parts and for each 512- bit part do the following:

   3.1 Calculate a 1536 - bit number in 48 iterations by using a constant number of bitwise and arithmetic operations. Several temp variables may be used in between.

   3.2 Set additional 8 variables a1,...,a8 equal to h1,...,h8

   3.3 Keep updating a1,...,a8 in a loop 64 times by using a fixed number of variables and performing the fixed number of bitwise and arithmetic operations.

   3.4 Add a1,...,a8 to h1,...,h8

4. Concatenate h1,...,h8.

As seen above, the time and space complexity of 1) and 2) is O(1). Then, for each isolated step from 4.1) to 4.4) they're also fixed. The only thing which is not constant is a size of the input message, and so the time complexity for 4) as a whole is O(n). The space complexity is O(1) because there's always a fixed number of temp variables used, and a 1536 - bit variable used in 3) can be re-used for each iteration.

Other SHA-2 based algorithms like SHA-512 or SHA-384 have the same complexity since they're different mostly by the number of iterations in 3.3) or word sizes.

Thereof, time complexity is O(n) and space complexity is O(1).