Дифференциальный и линейный криптоанализ блочных шифров

 

 

 

Рис.5

 

Рис.6

Рис. 7

 

Рис. 8

 

Искомый ключ: 1111 1010 0110 1011 0000 0000 (FA6B00)

 

Вывод:

     В ходе выполнения курсовой работы, мы изучили метод дифференциального и линейного криптоанализа блочных алгоритмов шифрования.

     Выяснили, что дифференциальный криптоанализ делится на 3 основных этапа:

1. Анализ (теоретический) исследуемого алгоритма шифрования и определение наиболее вероятной характеристики.
2. Поиск (практический) правильных пар текстов.
3. Анализ правильных пар текстов и накопление статистики о возможном значении секретного ключа.

    

    Линейный криптоанализ заключается в двух этапах.

    1. Построение соотношений между открытым текстом, шифртекстом и ключом, которые встречаются с высокой вероятностью.

     2. Использование этих соотношений вместе с известными парами открытый текст - шифротекст для получения битов ключа.

    Затем происходит построение линейный уравнений:  Xn+C_nⁱ=Kn,

где n-ые биты текста, шифротекста и ключа, i-номер раунда шифрования. 

    Для составления уравнений мы берем наибольшее отклонение от значения 0.5

    Основываясь на входных данных и количествах текстах мы можем найти сумму бит ключа, а следовательно и сам ключ.

 

ПРИЛОЖЕНИЕ  A

Листинг программы:

Программы на писаны на языке программирования python.

1. Lab_1.1

def print_chart(lst):

    for val in lst:

        print val

 

def RES(T, chart):

    if T == 1:

        RES = [[0 for j in range(4)] for i in range(16) ]

    else:

        RES = [[0 for j in range(8)] for i in range(16) ]

 

    for i in range(16):

        for j in range(16):

            deltaA = i^j

            deltaC = chart[i]^chart[j]

            RES[deltaA][deltaC] += 1

 

    RES[0][0] = 0

    print_chart(RES)

 

    max_val = 0

    for val in RES:

        max_str_val = max(val)

        if max_str_val > max_val:

            max_val = max_str_val

 

    print max_val

 

    for dAi, RESStr in enumerate(RES):

        for dCi, val in enumerate(RESStr):

            if val == max_val:

                print dAi, dCi

 

if __name__ == '__main__':

 

    substitute_chart1 = [2,1,0,4,1,2,6,5,4,7,3,5,7,6,0,3]

    substitute_chart2 = [2,4,2,7,0,6,0,6,5,3,4,3,5,1,7,1]

    substitute_chart3 = [1,1,3,2,2,1,2,1,3,2,3,0,0,0,0,3]

 

    RES(0, substitute_chart1)

    RES(0, substitute_chart2)

    RES(1, substitute_chart3)

 

2. Lab_1.2

def print_list(lst):

    for val in lst:

        print val

 

def rearrangement1(table_rearrangement1, Message):

 

    RES = [[[0 for a in range(3)] for j in range(2)] for i in range(len(Message)) ]

 

    for i, text in enumerate(Message):

        for j, delta_text  in enumerate(text):

            X = ''

            for a, swap in enumerate(table_rearrangement1):

                X = X + delta_text[swap-1]

 

            for t in range(3):

                RES[i][j][t] = int(X[(0+4*t):(4+4*t)],2)

 

    print_list(RES)

    print ' '

 

def rearrangement2(table_rearrangement, Message):

 

    RES = [[0 for a in range(3)] for i in range(len(Message)) ]

 

    for i, text in enumerate(Message):

        dY = ''

        for t in range(8):

            for j, swap in enumerate(table_rearrangement):

                if swap == t+1:

                    dY = dY + text[j]

                    break

        for t in range(3):

            RES[i][t] = int(dY[(0+3*t):(3+3*t)],2)

    print ' '

    print_list(RES)

 

 

if __name__ == '__main__':

 

    table_rearrangement1 = [4,3,1,6,8,7,2,5,4,3,6,7]

    table_rearrangement2 = [8,7,3,2,5,4,1,6]

 

 

    MessageX = [['00100001','01110111'],

                ['11011000','10001110'],

                ['11110111','10100001'],

                ['10010011','11000101'],

                ['01001110','00011000'],

                ['11010000','10000110'],

                ['01010000','00000110']]

 

    MessageY = [['00010010','01000100'],

                ['10100101','11110011'],

                ['00111111','01101001'],

                ['00011101','01001011'],

                ['00100011','01110101'],

                ['11011100','10001010'],

                ['11110110','10100000']]

 

    delta_Message = ['10111010','01101010','10101010','01101010','10100011','01100011','10111010']

 

    rearrangement1(table_rearrangement1, MessageX)

    rearrangement1(table_rearrangement1, MessageY)

    rearrangement2(table_rearrangement2, delta_Message)

 

3. Lab_1.3

def print_chart(lst):

    for val in lst:

        print val

 

def KEY(A, C, substitute_chart, Message):

 

    Result = [[0 for j in range(3)] for i in range(16)]

 

    for t,text in enumerate(Message):

        for i, ccc in enumerate(C[t]):

            for j in range(16):

                if substitute_chart[i][j]^substitute_chart[i][A[i]^j] == ccc:

                    Result[text[0][i]^j][i] += 1

    print_chart(Result)

 

    max_val = 0

    for val in Result:

        max_str_val = max(val)

        if max_str_val > max_val:

            max_val = max_str_val

 

    print max_val

 

    for deltaAi, res in enumerate(Result):

        for dCi, val in enumerate(res):

            if val == max_val:

                print deltaAi, dCi

 

if __name__ == '__main__':

 

    substitute_chart = [[2,1,0,4,1,2,6,5,4,7,3,5,7,6,0,3],

                        [2,4,2,7,0,6,0,6,5,3,4,3,5,1,7,1],

                        [1,1,3,2,2,1,2,1,3,2,3,0,0,0,0,3]]

 

    rearrangement_X = [[[4, 8, 4], [13, 14, 15]],

                       [[10, 3, 8], [3, 5, 3]],

                       [[15, 14, 15], [6, 8, 4]],

                       [[10, 12, 9], [3, 10, 2]],

                       [[1, 7, 3], [8, 1, 8]],

                       [[10, 2, 8], [3, 4, 3]],

                       [[8, 2, 8], [1, 4, 3]]]

 

    rearrangement_Y = [[[8, 4, 9], [1, 2, 2]],

                       [[7, 8, 6], [14, 14, 13]],

                       [[13, 13, 15], [4, 11, 4]],

                       [[9, 9, 10], [0, 15, 1]],

                       [[4, 12, 5], [13, 10, 14]],

                       [[11, 3, 10], [2, 5, 1]],

                       [[15, 6, 15], [6, 0, 4]]]

 

    rearrangement_dY = [[7, 2, 1],

                        [5, 2, 2],

                        [5, 2, 1],

                        [5, 2, 2],

                        [5, 1, 1],

                        [5, 1, 2],

                        [7, 2, 1]]

 

    A = [9,6,11]

    C = [[5,2,1]for i in range(len(rearrangement_X))]

 

    KEY(A, C, substitute_chart, rearrangement_X)

    KEY(A, rearrangement_dY, substitute_chart, rearrangement_Y)

 

4. Lab_2

def print_table(tab1, tab2):

 

    for i,val in enumerate(tab1):

        print val, "    ", str(tab2[i])

    print "  "

 

def binary_Betta(B_bin):

    B_binary = [0 for i in range(3)]

 

    for i,bin in enumerate(B_binary):

        B_binary[2-i] = (B_bin & 2**i)>>i

 

    return B_binary

 

def binary_Alpha(A_bin):

 

    A_binary = [0 for i in range(4)]

 

    for i,bin in enumerate(A_binary):

        A_binary[3-i] = (A_bin & 2**i)>>i

 

    return A_binary

 

def RES(substitute_chart, size):

 

    N = [ [0 for j in range(size)] for i in range(15) ]

    P = [ [0 for j in range(size)] for i in range(15) ]

 

    for i in range(1,16):

        Abin = binary_Alpha(i)

        for j in range(1,size+1):

            Bbin = binary_Betta(j)

            Q = 0

            for u in range(16):

                XK = binary_Alpha(u)

                Y = binary_Betta(substitute_chart[u])

                X = (Abin[0]&XK[0])^(Abin[1]&XK[1])^(Abin[2]&XK[2])^(Abin[3]&XK[3])^(Bbin[0]&Y[0])^(Bbin[1]&Y[1])^(Bbin[2]&Y[2])

 

                if X == 0:

                    Q += 1

 

            P[i-1][j-1] = Q

            n = 1 - 2*(float(Q)/16)

 

            if n < 0:

                N[i-1][j-1] = -n

            else:

                N[i-1][j-1] = n

 

    print_table(N, P)

 

    for dAi, NStr in enumerate(N):

        for dCi, val in enumerate(NStr):

            if val >= 0.5:

                print val, " - ", dAi+1, dCi+1

    print "  "

 

if __name__ == '__main__':

 

    substitute_chart1 = [1,3,5,7,3,1,7,5,6,2,4,0,4,0,6,2]

    substitute_chart2 = [3,5,0,6,0,6,5,3,2,2,7,7,1,1,4,4]

    substitute_chart3 = [0,0,3,3,3,3,0,0,2,2,1,1,1,1,2,2]

 

    RES(substitute_chart1, 7)

    RES(substitute_chart2, 7)

    RES(substitute_chart3, 3)