现代密码学教程—分组密码

作业(尚未订正)

第二节:

  1. 证明3DES的穷举攻击复杂度为:$Time=2^{112}, space ≈ 2^{56}$。

            以DES-EEE3为标准时,加密K1-加密K2-加密K3,密钥总长度为168 bit,利用中途相遇攻击,将明文穷举两次加密后存储,共占$space ≈ 2^{56}$,密文穷举解密后与存储相对应,对应上则可确定K1,K2,K3,其计算复杂度为$Time=2^{112}$。

            以DES-EEE2为标准,加密K1-加密K2-加密K1,密钥总长度为112 bits,虽然第一次和第二次加密使用相同的密钥,但是在穷举攻击时并不能最先确定出其密钥,因此普通的穷举攻击和中途相遇攻击均需要计算复杂度为$Time=2^{112},space ≈ 2^{56}$。

  2. 如果16轮使用的子密钥$K_{16} = K_1,K_{15}=K_2,…, K_9=K_8$,则加密所用的子密钥与解密所用的子密钥相同,对一个明文X加密两次,得到的还是明文X。弱密钥的定义:若k使得加密函数与解密函数一致,则称k为弱密钥。证明下列密钥为弱密钥(偶校验:就是让原有数据序列中(包括你要加上的一位)1的个数为偶数):

    (1) 0x00000000000000

            加入偶校验位后为0x0000000000000000,C,D存数编号(00,00),其中56位有效密钥全为0,在通过密钥编排时,无论密钥如何移位得到的子密钥均为0,从而使得在F函数中使用密钥加无任何意义,因此该密钥为弱密钥。

    (2)0x1E1E1E1E0F0F0F0F

            写成二进制形式,通过PC-1置换后,C,D存数编号(00,11),即得到的C中元素全部为0,得到的D中元素全部为1,从而所有的子密钥相同,并且 DES 是 Feistel 网络的结构,因此其为弱密钥。

    (3)0xE1E1E1E1F0F0F0F0

            同(2)写成二进制形式,通过PC-1置换后,C,D存数编号(11,00),即得到的C中元素全部为1,得到的D中元素全部为0,从而所有的子密钥相同,并且 DES 是 Feistel 网络的结构,因此其为弱密钥。

    (4)0xFFFFFFFFFFFFFF

            同(1),C,D存数编号(11,11),因此子密钥均为1,使得在F函数中使用密钥加无任何意义,因此该密钥为弱密钥。

第三节:

  1. 尝试推导AES的列混合操作转化为矩阵乘法$b(x)=a(x)*c(x) mod(x^4+1),c(x)= 03x^3+01x^2+01x+02$

            列混合的定义为:将状态矩阵的每一列看成$GF(2^8)$上的多项式,并和一个固定的多项式$c(x)=03x^3+01x^2+01x+02$相乘再模$x^4+1$。例如:对于状态矩阵的某一列$\begin{bmatrix}a_0 & a_1 & a_2 & a_3\end{bmatrix}^T$看为$a(x)=a_3x^3+a_2x^2+a_1x+a_0$,从而列混合可表示为:$a(x)*c(x) mod(x^4+1)$。

            对于任意$x^i$,有$x^imod(x^4+1)=x^{i(mod4)}$,因此可以在计算多项式相乘再取模的结果时进行简化,例如:$x^6=x^2,x^5=x,x^4=1$。

    上述公式表达的即为题中所示的矩阵乘法。

  2. 快速计算法,计算0x87乘以0x03模$m(x)=x^8+x^4+x^3+x+1$的值。

  3. 调研SM4算法,其迭代结构属于何类型?并详细描述加解密及密钥编排的步骤。

            SM4算法是一种分组密码算法。其分组长度为128bit,密钥长度也为128bit。加密算法与密钥扩展算法均采用32轮非线性迭代结构,以字(32位)为单位进行加密运算,每一次迭代运算均为一轮变换函数F。SM4算法加/解密算法的结构相同,只是使用轮密钥相反,其中解密轮密钥是加密轮密钥的逆序。

    加/解密:

            算法由32次迭代算法和1次反序变换R组成。设明文输入为$(X_0,X_1,X_2,X_3)\in(Z_2^{32})^4$,密文输出为$(Y_0,Y_1,Y_2,Y_3)\in(Z_2^{32})^4$,轮密钥为$rk_i\in Z_2^{32},i=0,1,2,…,31$。加密运算过程为:

    1. 32次迭代运算:$X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i),i=0,1,2,…,31$

    2. 反序变换:$(Y_0,Y_1,Y_2,Y_3)=R(X_{32},X_{33},X_{34},X_{35})=(X_{35},X_{34},X_{33},X_{32})$

    3. 迭代运算中轮函数F:

      设输入为$(X_0,X_1,X_2,X_3)\in(Z_2^{32})^4$,轮密钥为$rk_i\in Z_2^{32},i=0,1,2,…,31$,则轮函数F为:$F(X_0,X_{1},X_{2},X_{3},rk_i)=X_0\oplus T(X_1 \oplus X_2 \oplus X_3 \oplus rk)$。

    4. 轮函数F中合成置换T

      T:$Z^{32}_2→Z^{32}_2$是一个可逆变换,由非线性变换τ和线性变换L复合而成,即T(.)=L(τ(.))。非线性变换τ由4个并行的S盒构成。设输入为$A=(a_0,a_1,a_2,a_3)∈(Z^8_2)^4$,输出为$B=(b_0,b_1,b_2,b_3)∈(Z^8_2)^4$,则:$(b_0,b_1,b_2,b_3)=τ(A)=(Sbox(a_0),Sbox(a_1),Sbox(a_2),Sbox(a_3))$。Sbox为固定的16进制置换表。

    5. 合成置换T中线性置换L

      非线性变换τ的输出是线性变换L的输入.设输入为$B∈Z^{32}_2$,输出为$C∈Z^{32}_2$,则:$C=L(B)=B \oplus (B<<<2) \oplus (B<<<10) \oplus (B<<<18) \oplus(B<<<24)$

            解密时只是将轮密钥的使用顺序进行逆向进行。

    密钥编排:

            已知加密密钥为$MK=(MK_0,MK_1,MK_2.MK_3)$,系统参数$FK=(FK_0,FK_1,FK_2,FK_3)$,固定参数$CK=(CK_0,CK_1,…,CK_{31})$。$rk_i$为轮密钥,轮密钥由加密密钥生成。

            首先:$(K_0,K_1,K_2,K_3)=(MK_0 \oplus FK_0,MK_1 \oplus FK_1,MK_2 \oplus FK_2,MK_3 \oplus FK_3)$对$i=0,1,2,…,31$:$rk_i=K_{i+4} \oplus T’(K_{i+1} \oplus K_{i+2} \oplus K_{i+3} \oplus CK_i)$,改变换与加密中的T变换基本相同,只是将其中的线性变换改为:$L(B)=B \oplus (B<<13) \oplus (B<<23)$,由于系统参数个固定参数是已知的,轮密钥即可求得。

  4. (选作)使用乘法逆元及仿射方法实现AES字节代换操作的快速运算方法。

    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
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    # S盒乘法逆元及仿射实现
    # 求最高幂次数
    def Nonzero_MSB(value):
    v2str = '{:09b}'.format(value)
    for i in range(9):
    if int(v2str[i]):
    return 9 - i

    # 模2除法:m为被除数。b为除数,q为商,r为余数
    def Mode2_div(fx, gx):
    n = Nonzero_MSB(fx)
    m = Nonzero_MSB(gx)
    if n < m:
    return [0, fx]
    deg = n - m
    fx = fx ^ (gx << deg)
    [q, r] = Mode2_div(fx, gx)
    return [(1 << deg) | q, r]

    # 多项式乘法
    # v3 = v1 - q3 * v2
    def Calculate(v1, q3, v2):
    value = 0
    for i in range(32):
    if (q3 & (1 << i)):
    value = value ^ (v2 << i)
    return v1 ^ value

    # 欧几里得算法
    def poly_gcd(r1, r2, v1=1, v2=0, w1=0, w2=1):
    if r2 == 0 or r2 == 1:
    return w2
    q3, r3 = Mode2_div(r1, r2) # q3(x)=r1(x)|r2(x), r2(x)=r1(x) mod r2(x)
    v3 = Calculate(v1, q3, v2) # v3 = v1 - q3 * v2
    w3 = Calculate(w1, q3, w2) # w3 = w1 - q3 * w2
    return poly_gcd(r2, r3, v2, v3, w2, w3)

    def sym2int(sym):
    power = [sym[i + 2] for i in range(len(sym)) if sym[i] == 'x']
    if '+1' in sym: power.append('0')
    data = 0
    for p in power:
    data = data | (1 << int(p))
    return data

    def int2sym(data):
    int2str = '{:09b}'.format(data)
    sym = ''
    for i in range(9):
    if int(int2str[i]) == 1:
    if 8 - i:
    sym += '+x^%d' % (8 - i)
    else:
    sym += '+1'
    return sym[1:]

    def xor(a, b):
    if a == b:
    return '0'
    else:
    return '1'

    def fangshe(a):
    a = a[::-1]
    c = '11000110'
    b = ''
    for i in range(7, -1, -1):
    b += xor(xor(xor(xor(xor(a[i], a[(i + 4) % 8]), a[(i + 5) % 8]), a[(i + 6) % 8]), a[(i + 7) % 8]), c[i])
    return b

    if __name__ == '__main__':
    bi = bin(int(input('请输入两位16进制数:'), 16))[2:]
    print("16进制转为为2进制为:{}".format(bi))
    xstr = ''
    for i in range(len(bi)):
    if bi[i] == '1':
    if i < len(bi) - 1:
    xstr += "+x^{}".format(len(bi) - i - 1)
    elif i == str(len(bi)):
    xstr += '+1'
    xstr = xstr[1:]
    inverse = int2sym(poly_gcd(283, sym2int(xstr)))
    data = hex(sym2int(inverse))
    print('你输入的多项式 :', xstr)
    print('默认既约多项式 :', int2sym(283))
    print('乘法逆元为 :', inverse)
    print('乘法逆元的16进制:', data)
    print('---- 多项式乘法逆元求解完成 ----')
    data = bin(int(data, 16))[2:].zfill(8)
    print('最终结果为:', fangshe(data))
    print('16进制表示为', hex(int(fangshe(data), 2)))

第四节:

  1. 调研OFB模式及CCM模式,并分析其各自性质。

            OFB模式(输出反馈模式):密码算法的输出会反馈到密码算法的输入当中。其是将“明文分组”和“密码算法的输出”进行XOR来产生“密文分组”。优点:传输过程中密文在某位上发生的错误不会影响解密后明文其他位。缺点:失去同步,如果加密端和解密端移位寄存器不同步,那么恢复的明文将是一些无用的杂乱数据,任何使用OFB的系统必须有检测失步的机制,并用新的初始向量IV填充双方移位寄存器重新获得同步;抗消息流篡改攻击能力不如CFB。

            CCM模式(认证保密模式):CCM是CTR加密模式和CMAC认证算法的混合使用,常用在需要同时加密和认证的领域,比如WiFi安全中的WPE协议,它就使用了AES-CCM模式。其首先使用CBC-MAC模式来认证传输帧,然后使用CTR模式来加密帧。

鸣谢❀参考大佬文章