SHA (Secure Hash Algorithm)
Description
The Secure Hash Algorithm (SHA) is a family of cryptographic hash functions designed by the National Security Agency (NSA). These functions take an input of arbitrary length and produce a fixed-size output, making them ideal for digital signatures, message authentication, and data integrity verification.
- Produces fixed-length output regardless of input size
- One-way function (computationally infeasible to reverse)
- Small changes in input produce large changes in output
- Multiple variants with different security levels
History
The SHA family began with SHA-0, published by the NSA in 1993. It was quickly replaced by SHA-1 in 1995 due to a significant flaw in the original algorithm. As computing power increased and cryptographic attacks evolved, the need for stronger hash functions led to the development of SHA-2 in 2001.
In 2015, SHA-3 was standardized, becoming the latest member of the SHA family. Unlike its predecessors, SHA-3 uses a completely different internal structure (Keccak) and was selected through a public competition run by NIST.
Today, while SHA-1 is considered cryptographically broken, SHA-2 and SHA-3 remain secure and are widely used in various security applications and protocols.
How It Works
- Message Preprocessing
- Padding the message to a multiple of block size
- Adding length information
- Breaking into fixed-size blocks
- Initialize Hash Values
- Set initial hash values (constants)
- Different for each SHA variant
- Process Message Blocks
- Message schedule generation
- Compression function application
- State update after each block
- Final Output
- Concatenate final state values
- Truncate to desired output size
Visualization
Click Start to begin SHA hashing
Implementation
def sha256(message: bytes) -> bytes:
"""Implementation of SHA-256 hash function"""
# Initial hash values (first 32 bits of the fractional parts of the square roots of the first 8 primes)
h0 = 0x6a09e667
h1 = 0xbb67ae85
h2 = 0x3c6ef372
h3 = 0xa54ff53a
h4 = 0x510e527f
h5 = 0x9b05688c
h6 = 0x1f83d9ab
h7 = 0x5be0cd19
# Round constants (first 32 bits of the fractional parts of the cube roots of the first 64 primes)
k = [
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
# ... (remaining constants omitted for brevity)
]
def right_rotate(n: int, d: int) -> int:
"""Rotate a 32-bit integer n right by d bits"""
return (n >> d) | (n << (32 - d)) & 0xffffffff
def process_block(block: bytes) -> None:
"""Process a 512-bit block"""
nonlocal h0, h1, h2, h3, h4, h5, h6, h7
# Create message schedule
w = [0] * 64
for i in range(16):
w[i] = int.from_bytes(block[i*4:(i+1)*4], 'big')
for i in range(16, 64):
s0 = right_rotate(w[i-15], 7) ^ right_rotate(w[i-15], 18) ^ (w[i-15] >> 3)
s1 = right_rotate(w[i-2], 17) ^ right_rotate(w[i-2], 19) ^ (w[i-2] >> 10)
w[i] = (w[i-16] + s0 + w[i-7] + s1) & 0xffffffff
# Initialize working variables
a, b, c, d, e, f, g, h = h0, h1, h2, h3, h4, h5, h6, h7
# Main loop
for i in range(64):
S1 = right_rotate(e, 6) ^ right_rotate(e, 11) ^ right_rotate(e, 25)
ch = (e & f) ^ ((~e) & g)
temp1 = (h + S1 + ch + k[i] + w[i]) & 0xffffffff
S0 = right_rotate(a, 2) ^ right_rotate(a, 13) ^ right_rotate(a, 22)
maj = (a & b) ^ (a & c) ^ (b & c)
temp2 = (S0 + maj) & 0xffffffff
h = g
g = f
f = e
e = (d + temp1) & 0xffffffff
d = c
c = b
b = a
a = (temp1 + temp2) & 0xffffffff
# Update hash values
h0 = (h0 + a) & 0xffffffff
h1 = (h1 + b) & 0xffffffff
h2 = (h2 + c) & 0xffffffff
h3 = (h3 + d) & 0xffffffff
h4 = (h4 + e) & 0xffffffff
h5 = (h5 + f) & 0xffffffff
h6 = (h6 + g) & 0xffffffff
h7 = (h7 + h) & 0xffffffff
# Preprocess message
message_len = len(message)
message = bytearray(message)
message.append(0x80)
while (len(message) + 8) % 64 != 0:
message.append(0x00)
message.extend((message_len * 8).to_bytes(8, 'big'))
# Process message in 512-bit blocks
for i in range(0, len(message), 64):
process_block(message[i:i+64])
# Produce final hash value
return b''.join(x.to_bytes(4, 'big') for x in [h0, h1, h2, h3, h4, h5, h6, h7])#include <vector>
#include <string>
#include <cstring>
#include <openssl/sha.h>
class SHA256 {
private:
SHA256_CTX ctx;
unsigned char hash[SHA256_DIGEST_LENGTH];
public:
SHA256() {
SHA256_Init(&ctx);
}
void update(const void* data, size_t len) {
SHA256_Update(&ctx, data, len);
}
void update(const std::string& data) {
update(data.c_str(), data.length());
}
std::vector<unsigned char> final() {
SHA256_Final(hash, &ctx);
return std::vector<unsigned char>(hash, hash + SHA256_DIGEST_LENGTH);
}
static std::vector<unsigned char> hash(const std::string& data) {
SHA256 sha;
sha.update(data);
return sha.final();
}
};using System;
using System.Security.Cryptography;
using System.Text;
public class SHA256Hash
{
private SHA256 sha256;
public SHA256Hash()
{
sha256 = SHA256.Create();
}
public byte[] ComputeHash(string input)
{
return ComputeHash(Encoding.UTF8.GetBytes(input));
}
public byte[] ComputeHash(byte[] input)
{
return sha256.ComputeHash(input);
}
public string ComputeHashString(string input)
{
byte[] hashBytes = ComputeHash(input);
StringBuilder builder = new StringBuilder();
for (int i = 0; i < hashBytes.Length; i++)
{
builder.Append(hashBytes[i].ToString("x2"));
}
return builder.ToString();
}
public void Dispose()
{
sha256.Dispose();
}
}Complexity Analysis
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Hash Computation | O(n) | O(1) |
| Block Processing | O(1) | O(1) |
The time complexity is linear in the size of the input because each byte must be processed exactly once. The space complexity is constant because SHA uses a fixed amount of memory regardless of input size.
Advantages and Disadvantages
Advantages
- Strong collision resistance
- Widely adopted and standardized
- Multiple variants for different security needs
- Fast hardware implementations available
- Deterministic output
Disadvantages
- SHA-1 is no longer secure
- Slower than non-cryptographic hashes
- Complex implementation
- Fixed output size may be too large for some uses