def sha1(m):
    """
    berechnet zu der Bytefolge m den sha1-Hash als Bytefolge
    """
    # Hilfsfunktion
    def leftrotate(i,n):
        """
        rotiert die Bits der 32-Bit-int-Zahl i um n Stellen nach links
        """
        binstring = bin(i)[2:].zfill(32)
        return int(binstring[n:]+binstring[:n],2)
    # Konstanten
    h0 = 0x67452301
    h1 = 0xEFCDAB89
    h2 = 0x98BADCFE
    h3 = 0x10325476
    h4 = 0xC3D2E1F0
    # padding
    mbits = ''
    for b in m:
        mbits = mbits + bin(b)[2:].zfill(8)
    mlaenge = len(mbits)
    # print(m,mlaenge,mbits) # DEBUG
    mbits = mbits+'1'
    diff448 = 448 - (mlaenge+1)%512
    # print(diff448) # DEBUG
    if diff448 < 0:
        anzahl0 = 512 + diff448
    else:
        anzahl0 = diff448
    # print(anzahl0) # DEBUG
    mbits = mbits + anzahl0*'0' + bin(mlaenge)[2:].zfill(64)
    # print(mbits,len(mbits)) # DEBUG
    # Unterteilung in 512-Bit-Bloecke M
    M = []
    while len(mbits) > 0:
        M.append(mbits[0:512])
        mbits = mbits[512:]
    # print(len(M)) # DEBUG
    for block in M:
        # print(block) # DEBUG
        w = []
        for i in range(16):
            w.append(int(block[i*32:(i+1)*32],2))
        # print(w) # DEBUG
        for i in range(16,80):
            w.append(leftrotate(w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16],1))
        a = h0
        b = h1
        c = h2
        d = h3
        e = h4
        for i in range(80):
            if 0 <= i <= 19:
                f = (b & c) | ((~b) & d)
                k = 0x5A827999
            elif 20 <= i <= 39:
                f = b ^ c ^ d
                k = 0x6ED9EBA1
            elif 40 <= i <= 59:
                f = (b & c) | (b & d) | (c & d)
                k = 0x8F1BBCDC
            elif 60 <= i <= 79:
                f = b ^ c ^ d
                k = 0xCA62C1D6
            temp = (leftrotate(a,5) + f + e + k + w[i])%4294967296
            e = d
            d = c
            c = leftrotate(b,30)
            b = a
            a = temp
        h0 = (h0 + a)%4294967296 # 2**32 = 4294967296
        h1 = (h1 + b)%4294967296
        h2 = (h2 + c)%4294967296
        h3 = (h3 + d)%4294967296
        h4 = (h4 + e)%4294967296
    return bytes(ntob(h0)+ntob(h1)+ntob(h2)+ntob(h3)+ntob(h4))

if __name__ == '__main__':
    m0=bytes('abc','ascii')
    h = sha1(m0)
    hexh = ''.join([hex(x)[2:].zfill(2) for x in h])
    fips1 = 'A9993E364706816ABA3E25717850C26C9CD0D89D'.lower()
    if hexh == fips1:
        print('fips1 ok', hexh)
    else:
        print('Fehler bei fips1')
        print(hexh)
        print(fips1)
    m1=bytes('abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq','ascii')
    h = sha1(m1)
    hexh = ''.join([hex(x)[2:].zfill(2) for x in h])
    fips1 = '84983E441C3BD26EBAAE4AA1F95129E5E54670F1'.lower()
    if hexh == fips1:
        print('fips2 ok', hexh)
    else:
        print('Fehler bei fips2')
        print(hexh)
        print(fips1)
    m2=bytes('a'*1000000,'ascii')
    h = sha1(m2)
    hexh = ''.join([hex(x)[2:].zfill(2) for x in h])
    fips1 = '34AA973CD4C4DAA4F61EEB2BDBAD27316534016F'.lower()
    if hexh == fips1:
        print('fips3 ok', hexh)
    else:
        print('Fehler bei fips3')
        print(hexh)
        print(fips1)
    m1=bytes('Franz jagt im komplett verwahrlosten Taxi quer durch Bayern','ascii')
    h = sha1(m1)
    hexh = ''.join([hex(x)[2:].zfill(2) for x in h])
    wikipedia = '68ac906495480a3404beee4874ed853a037a7a8f'
    if hexh == wikipedia:
        print('wikipedia ok', hexh)
    else:
        print('Fehler bei wikipedia')
        print(hexh)
        print(wikipedia)