Cryptography

Hash&MAC

notes for learning Hash function & Message Authetication Code

click me to go to the pdf

Python implementation of SHA1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from bitstring import  BitArray
from hashlib import sha1

# ----------------------------------------------------------------------- set up the stage ----------------------------------------------------------------------- 

def add(a:BitArray , b:BitArray)->BitArray:
    return BitArray(uint = (a.uint + b.uint) % 2 ** 32 , length=32)

def left_rotate(x:BitArray , number : int)->BitArray:
    return (x << number)|(x >> (32 - number))

# ----------------------------------------------------------------------- set up the stage ----------------------------------------------------------------------- 
def padding(m:str)->BitArray:
    message_bits = BitArray()
    # 1. break message into bits
    for i in m:
        message_bits += BitArray(uint = ord(i),length=8)
    ml = len(message_bits)
    message_bits += '0b1'   # 2. append the bit '1' to the message
    while message_bits.len % 512 != 448 : message_bits.append(1) # 3. append 0 ≤ k < 512 bits '0', such that the resulting message length in bits is congruent to −64 ≡ 448 (mod 512)
    message_bits += BitArray(uint = ml , length=64 ) # 4. append ml, the original message length in bits, as a 64-bit big-endian integer
    return message_bits

def compress(message_bits : BitArray)->BitArray:
    f1 = lambda b,c,d : (b&c)|(~b&d)
    f2 = lambda b,c,d : b^c^d
    f3 = lambda b,c,d : (b&c)|(b&d)|(c&d)
    f4 = f2

    constants = [BitArray(uint = x, length=32) for x in (0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,0xC3D2E1F0)]
    round_functions = (f1, f2 ,f3 ,f4)
    round_parameters = tuple(BitArray(uint=x , length=32) for x in (0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xCA62C1D6))

    hashvalue = BitArray()

    for j in range(0,message_bits.len,512): # each 512 long block go through 80 rounds
        block  = message_bits[j:j+512]
        message_words = []
        a,b,c,d,e = constants # for each block a,b,c,d,e must be reinitialized

        for i in range(80):
            # select round arguments
            f , k = round_functions[i//20] , round_parameters[i//20]
            if 0<= i <= 15 :
                message_words.append(block[i*32:i*32+32])
            else:
                # SHA-0 differs by not having this leftrotate.
                message_words.append(left_rotate((message_words[i-16] ^ message_words[i-14] ^ message_words[i-8] ^ message_words[i-3]),1))
            
            # fistel-style structure
            temp = add(add(add(add(left_rotate(a,5) , f(b,c,d)) , e) , k) , message_words[i])
            a, b, c, d, e = temp, a, left_rotate(b,30), c, d

            # print('round[{}]:A={},\tB={},\tC={},\tD={},\tE={}'.format(i,a.uint,b.uint,c.uint,d.uint,e.uint)) uncomment this line if you want step by step output
        
        for index , value  in enumerate([a,b,c,d,e]): # update constants after 80 rounds
            constants[index] = add(constants[index] , value)

    hashvalue = sum(constants) # concatenate the five 32-bits long changed constants and get the result
    return hashvalue

def sha_one(message:str)->str:
    return compress(padding(message)).hex

message = 'hello'*300
print(sha_one(message))
print(sha1(message.encode('ascii')).hexdigest())

Validation