Mki's Blog

密码学: 国密标准SM3的实现

简介

SM3是一种密码散列函数标准,其安全性及效率与SHA-256相当。通俗点说,就是把一个任意位数的字符串转化为一个固定长度的杂凑值,并且不可还原。

原理

图解

建议配合这张图和官方文档一起食用。后面的细节描述略有繁琐(没错,我就是干不过官方文档)

sm3.png

消息填充

显然,我们会有一个要加密信息,暂且用英文字母来表示,比如password这个单词

首先,把字符信息转换为ascii码的形式

password => 112 97 115 115 119 111 114 100

然后把ascii码转换为二进制的形式

password => 112 97 115 115 119 111 114 100 => 1110000 1100001 1110011 1110011 1110111 1101111 1110010 1100100

然鹅,这里就会有一个问题,就是每个ascii码二进制的位数问题(事实上这个问题在后面会多次出现),为了方便后面的各种操作,这里我们统一把二进制位数定为8位(也就是一个字的大小)。在不足8位的二进制码前面补0,此时,整个二进制串的长度 L = 8x8 = 64

password => 112 97 115 115 119 111 114 100 => 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100

接着,我们在末尾添加一个1,没错…..就是添加一个1

password => 112 97 115 115 119 111 114 100 => 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100 1

然后,在尾部疯狂添加k个0,使得 (L + 1 + k) mod 512 = 448

password => 112 97 115 115 119 111 114 100 => 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100 1 000000······

最后,添加一个比特串,内容是长度L的二进制表示,但是一共64位,在这里是

比特串 => 0000000 00000000 00000000 00000000 00000000 00000000 00000000 01000000  // 一共64位

此时 (L + 1 + k + 64) mod 512 = 0

也就是说,我们现在把原始的字符串信息传换成了 n个512bit的比特串m(n = 0,1,2 ······),这个过程,我们把它叫做填充

转化为16进制(偷个懒,二进制实在是太长了)

70617373 776f7264 80000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000040

消息拓展

然后,我们把这512n位的比特串分成n组,每一组是512位,那么原始比特串m就被分成了 B[0] B[1] B[2] ······B[n-1]个分组

对于每一个分组B[i],这里以第一个分组为例(事实上对于password这个例子我们也只有这一组)进行扩展.

拓展分为 w 和 w’ 两个部分

首先,对于w部分

第0-15分组是原消息本身

70617373 776f7264 80000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000040

第16-67个分组,对于这个范围内的分组w[j]

1555073095942.png

对于w’部分

第0-63个分组,对于这个范围内的分组w’[j]

1555073071108.png

其中,≪ 符号表示移位运算,⊕ 符号表示异或运算,P1 是一个函数

1555073004975.png

经过拓展,得到

{
0: '70617373', 1: '776f7264', 2: '80000000', 3: '00000000', 4: '00000000', 5:'00000000', 6: '00000000', 7: '00000000', 
8:'00000000', 9: '00000000', 10: '00000000', 11: '00000000', 12:'00000000',13:'00000000', 14:'00000000',15:'00000040',
16:'7060fbfa', 17: 'fc66fe6a', 18: '80605010', 19: 'f9dbf852', 20: 'd9935b16', 21: '10045054', 22: '44c16dbd', 23: '835f81d0', 
24: '8d7f5943', 25:'decb9dbb', 26: '58613dcb', 27: 'a0043050', 28: 'e3c74202', 29: '1ce4130e', 30: '9d037e7d', 31: '0a5e1b0b', 
32: '59744189', 33: 'c73da633', 34: 'd4aa9e3d', 35: '587ddb04', 36: 'b0740ce7', 37: 'f4f0f25c', 38: '6681c791', 39: 'b7cbff8c', 
40: 'acdaf6c6', 41: 'd120bc8b', 42: 'cc59b6d9', 43: '8685d588', 44: 'dfcabec5',45: 'e44e8767', 46: 'e74e7a3a', 47: '91f4d659', 
48: '68ffa877', 49: '52fbd36e', 50: '9a041ed5', 51: 'd943b995', 52: 'ac9180a8', 53: '55808efc', 54: '5b20ec1c', 55: 'f8464cf7', 
56: '882c45e4', 57: 'd91c6d62', 58: '359d9a6e', 59: 'aef4ba3a', 60: '4b84af23', 61: '8c385cb8', 62: '15bfcf49', 63: '4a5bf445', 
64: 'b5b5dfbd', 65: '7ff3d50e', 66: '14e8c665', 67: 'f35faa48', 68: '70617373', 69: '776f7264', 70: '80000000', 71: '00000000', 
72: '00000000', 73: '00000000', 74: '00000000', 75: '00000000', 76: '00000000', 77: '00000000', 78: '00000000', 79: '00000040', 
80: '7060fbfa', 81: 'fc66fe6a', 82: '80605010', 83: 'f9dbf812', 84: 'a9f3a0ec', 85: 'ec62ae3e', 86: 'c4a13dad', 87: '7a847982', 
88: '54ec0255', 89: 'cecfcdef', 90: '1ca05076', 91: '235bb180', 92: '6eb81b41', 93: 'c22f8eb5', 94: 'c56243b6', 95: 'aa5a2b5b', 
96: 'bab3038b', 97: 'dbd9b53d', 98: '49a9e040', 99: '5223c00f', 100: 'e9004d6e', 101: '33cd546f',102:'b22b59ac',103:'efb62488',
104: '1caefa21', 105: '25d04ed7', 106: 'aad87148', 107: '314e2a04', 108: '73104803', 109: '356e3bec',110:'2b17cce3',111:'177103d1',
112: 'b73516b2', 113:'b6b55409', 114: '7d4a64ef', 115: '48b76fcc', 116: 'c46e28df', 117: '077b5d92', 118:'c124f2c9',119:'2105f562',
120: '24bdc54c', 121: '8c9ce39e', 122: '6ebd7672', 123: '56b2f6cd', 124: 'c3a8eac7', 125: '552431da',126:'20225527',127:'e4af4e7f', 
128: 'fe31709e', 129: 'f3cb89b6', 130: '0157092c', 131: 'b9045e0d'
}

消息压缩

然后,对拓展后的消息进行压缩处理

压缩处理有 A B C D E F G H 八个字寄存器, SS1 SS2 TT1 TT2 四个中间变量,压缩函数为

1555073181828.png

其中CF的具体过程为

FOR j=0 TO 63 
    SS1 ← ((A ≪ 12) + E + (Tj ≪ j)) ≪ 7 
    SS2 ← SS1⊕(A ≪ 12) 
    TT1 ← FFj(A,B,C) + D + SS2 + W′ j 
    TT2 ← GGj(E,F,G) + H + SS1 + Wj 
    D ← C 
    C ← B ≪ 9 
    B ← A 
    A ← TT1 
    H ← G 
    G ← F ≪ 19 
    F ← E 
    E ← P0(TT2) 
ENDFOR 
V (i+1) ← ABCDEFGH ⊕V (i) 

其中 FF和 GG 函数分别为

1555069085288.png

迭代压缩之后,得到散列值

08594e140bcc046e345325435218f67a85c38c63de6443b197b544d70ee62f26

代码

一些小函数

FF(x,y,z,j)  # FF布尔函数
GG(x,y,z,j)  # GG布尔函数
OtoH(text)   # 字符串 10进制转16进制
OtoB(text)   # 字符串 10进制转16进制
HtoB(text)   # 字符串 16进制转2进制
BtoH(text)   # 字符串 2进制转16进制(任意长度)
ZtoH(text)   # 字符串 2进制转16进制(字专用)
Not(a)       # 字符串 非函数
And(a,b)     # 字符串 与函数
And3(a,b,c)  
Or(a,b)      # 字符串 或函数
Or3(a,b,c)   
Xor(a,b)     # 字符串 异或函数
Xor3(a,b,c)
Move(text, num) # 循环位移函数
Mod32(a,b)      # mod2^32

填充代码

def Fill(text):
    text_bin = ''
    # text to bin
    for ch in text:
        ascii_ch = ord(ch)
        text_bin = text_bin + '0' + bin(ascii_ch)[2:]

    # add 1
    length = len(text_bin)

    text_bin = text_bin + '1'

    # add 0
    while len(text_bin)%512!=448:
        text_bin += '0'
    length_bin = bin(length)[2:]

    while len(length_bin)<64:
            length_bin = '0' + length_bin

    text_bin = text_bin + length_bin

    return text_bin

拓展代码

def Substitute(x, mode):
    """
    置换函数 done
    """
    if mode == 0:
        ans = Xor3(x,Move(x,9),Move(x,17))
    else:
        ans = Xor3(x,Move(x,15),Move(x,23))
    return ans
def Expand(b):
    """
    拓展函数
    """
    w = {}
    for i in range(16):
        w[i] = b[i*32:(i+1)*32]
    for j in range(16, 68):
        tmp = Xor3(w[j-16],w[j-9],Move(w[j-3],15))
        tmp = Substitute(tmp, 1) 
        w[j] = Xor3(tmp, Move(w[j-13],7), w[j-6])
    for j in range(64):
        w[j+68] = Xor(w[j],w[j+4])
    for i in w:
        w[i] = ZtoH(w[i])
    return w

压缩代码

def Compress(w,IV):
    """
    消息压缩
    """
    A = IV[0:8]
    B = IV[8:16]
    C = IV[16:24]
    D = IV[24:32]
    E = IV[32:40]
    F = IV[40:48]
    G = IV[48:56]
    H = IV[56:64]

    SS1 = ''
    SS2 = ''
    TT1 = ''
    TT2 = ''

    for j in range(64):
        if int(j)<=15:
            T = '79cc4519' 
        else:
            T = '7a879d8a'

        tmp = int(Move(HtoB(A),12), 2) + int(HtoB(E), 2) + int(Move(HtoB(T),j%32), 2) 
        tmp = Mod32(tmp, 0)
        SS1 = Move(OtoB(tmp), 7)
        SS2 = Xor(SS1, Move(HtoB(A),12))

        tmp = int(FF(HtoB(A),HtoB(B),HtoB(C),j),2) + int(HtoB(D),2) + int(SS2,2) + int(HtoB(w[j+68]),2)
        tmp = Mod32(tmp,0)
        TT1 = int(tmp,10)

        tmp = int(GG(HtoB(E),HtoB(F),HtoB(G),j),2) + int(HtoB(H),2) + int(SS1,2) + int(HtoB(w[j]),2)
        tmp = Mod32(tmp,0)
        TT2 = int(tmp,10)

        D = C

        C = ZtoH(Move(HtoB(B),9))

        B = A

        A = OtoH(TT1)

        H = G

        G = ZtoH(Move(HtoB(F),19))

        F = E

        E = ZtoH(Substitute(OtoB(TT2),0))

    r = A+B+C+D+E+F+G+H
    r = HtoB(r)
    v = HtoB(IV)
    return BtoH(Xor(r,v))

小结

密码学老师好凶啊,唔。