Основы теории конечных полей.

MEPhI Computer Systems and Technologies Department Ivanov Защита M. информации Иванов М.А. Лекция № 21 Основы теории конечных полей http://dozen.mephi.ru 2016 Защита информации Лекция № 21 Группа G Методы защиты - непустое множество элементов , , , … от случайных деструктивных воздействий M. Ivanov http://dozen.mephi.ru MEPhI, 2016 1/12 Защита информации Лекция № 21 Группа G Методы защиты - непустое множество элементов , , , … от случайных деструктивных воздействий • Для элементов множества G определена некоторая операция двух переменных:  +  = , либо  =  M. Ivanov http://dozen.mephi.ru MEPhI, 2016 1/12 Защита информации Лекция № 21 Группа G Методы защиты - непустое множество элементов , , , … от случайных деструктивных воздействий • Для элементов множества G определена некоторая операция двух переменных:  +  = , либо  =  • На множестве G выполняются следующие законы: - в результате применения операции к двум любым элементам G также получается элемент группы (свойство замкнутости) M. Ivanov http://dozen.mephi.ru MEPhI, 2016 1/12 Защита информации Лекция № 21 Группа G Методы защиты - непустое множество элементов , , , … от случайных деструктивных воздействий • Для элементов множества G определена некоторая операция двух переменных:  +  = , либо  =  • На множестве G выполняются следующие законы: - в результате применения операции к двум любым элементам G также получается элемент группы (свойство замкнутости) - для любых трех элементов G справедливо: M. Ivanov ( + ) +  =  + ( + ), либо ()  =  () (ассоциативный закон) http://dozen.mephi.ru MEPhI, 2016 1/12 Защита информации Лекция № 21 Группа G Методы защиты - непустое множество элементов , , , … от случайных деструктивных воздействий • Для элементов множества G определена некоторая операция двух переменных:  +  = , либо  =  • На множестве G выполняются следующие законы: - в результате применения операции к двум любым элементам G также получается элемент группы (свойство замкнутости) - для любых трех элементов G справедливо: M. Ivanov ( + ) +  =  + ( + ), либо ()  =  () (ассоциативный закон) - в G существует единичный элемент, для сложения 0 +  =  + 0 = ; для умножения 1 = 1 =  http://dozen.mephi.ru MEPhI, 2016 1/12 Защита информации Лекция № 21 Группа G Методы защиты - непустое множество элементов , , , … от случайных деструктивных воздействий • Для элементов множества G определена некоторая операция двух переменных:  +  = , либо  =  • На множестве G выполняются следующие законы: - в результате применения операции к двум любым элементам G также получается элемент группы (свойство замкнутости) - для любых трех элементов G справедливо: M. Ivanov ( + ) +  =  + ( + ), либо ()  =  () (ассоциативный закон) - в G существует единичный элемент, для сложения 0 +  =  + 0 = ; для умножения 1 = 1 =  - каждый элемент G обладает обратным элементом, для сложения  + (– ) = (–) +  = 0; для умножения -1 = -1 = 1 http://dozen.mephi.ru MEPhI, 2016 1/12 Защита информации Лекция № 21 Определения • • • • • Методы защиты от для случайных деструктивных воздействий Если любых элементов группы выполняется коммутативный закон, т.е.  +  =  +  (для сложения), либо   =   (для умножения) группа называется коммутативной или абелевой Число элементов группы называется порядком группы (будем рассматривать только конечные группы) Абелева группа относительно операции сложения называется аддитивной абелевой группой, абелева группа относительно операции умножения называется мультипликативной абелевой M. Ivanov группой Некоторое подмножество группы называется подгруппой, если оно удовлетворяет всем свойствам группы Конечная группа, которая состоит из степеней 1, g, g2, g3, … одного из ее элементов g, называется циклической группой. Наименьшее целое число e такое, что ge = 1, называется порядком элемента g. Такие группы всегда коммутативны. Любая группа простого порядка и любая подгруппа циклической группы являются циклическими http://dozen.mephi.ru MEPhI, 2016 2/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий M. Ivanov http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  M. Ivanov http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  • На множестве GF(p) выполняются следующие законы: - в результате применения операции сложения или умножения к двум любым элементам поля также получается элемент поля (свойство замкнутости) M. Ivanov http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  • На множестве GF(p) выполняются следующие законы: - в результате применения операции сложения или умножения к двум любым элементам поля также получается элемент поля (свойство замкнутости) - ( + ) +  =  + ( + ), ()  =  () (ассоциативный закон) M. Ivanov http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  • На множестве GF(p) выполняются следующие законы: - в результате применения операции сложения или умножения к двум любым элементам поля также получается элемент поля (свойство замкнутости) - ( + ) +  =  + ( + ), ()  =  () (ассоциативный закон) M. Ivanov ( + )  =  +  - для любых трех элементов справедливо - существует нулевой элемент:   GF(p) 0 +  =  + 0 =  http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  • На множестве GF(p) выполняются следующие законы: - в результате применения операции сложения или умножения к двум любым элементам поля также получается элемент поля (свойство замкнутости) - ( + ) +  =  + ( + ), ()  =  () (ассоциативный закон) M. Ivanov ( + )  =  +  - для любых трех элементов справедливо - существует нулевой элемент:   GF(p) 0 +  =  + 0 =  - существует единичный элемент:   GF(p) 1 = 1 =  http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  • На множестве GF(p) выполняются следующие законы: - в результате применения операции сложения или умножения к двум любым элементам поля также получается элемент поля (свойство замкнутости) - ( + ) +  =  + ( + ), ()  =  () (ассоциативный закон) M. Ivanov ( + )  =  +  - для любых трех элементов справедливо - существует нулевой элемент:   GF(p) 0 +  =  + 0 =  - существует единичный элемент:   GF(p) 1 = 1 =  -   GF(p) обладает обратными аддитивным и мультипликативным элементами: (–) для сложения, при этом  + (–) = (–) +  = 0; -1 для умножения, при этом -1 = -1 = 1 http://dozen.mephi.ru MEPhI, 2016 3/12 Защита информации Лекция № 21 Конечное поле или поле Галуа GF(p) - конечное множество иззащиты p элементов , , , … Методы (где p = qn, q – простое, n – натуральное) от случайных деструктивных воздействий • Для элементов GF(p) определены две операции двух переменных:  +  = , либо  =  • На множестве GF(p) выполняются следующие законы: - в результате применения операции сложения или умножения к двум любым элементам поля также получается элемент поля (свойство замкнутости) - ( + ) +  =  + ( + ), ()  =  () (ассоциативный закон) M. Ivanov ( + )  =  +  - для любых трех элементов справедливо - существует нулевой элемент:   GF(p) 0 +  =  + 0 =  - существует единичный элемент:   GF(p) 1 = 1 =  -   GF(p) обладает обратными аддитивным и мультипликативным элементами: (–) для сложения, при этом  + (–) = (–) +  = 0; -1 для умножения, при этом -1 = -1 = 1 •   0 может быть представлен в виде степени примитивного элемента g, т.е. в виде gi. Таким образом, GF(p) = { 0, g0, g1, g2 … }, где g0 = 1, g1 = g, gp - 1= 1, gp = g …, а Z*p образует абелеву группу порядка p – 1 http://dozen.mephi.ru MEPhI, 2016 3/12 Пример LFSR φ(x) = x3 + x + 1 1 1 1 1 1 1 1 1 1 1 1 1 φ(x) = x3 + x + 1 Это ГПСЧ, функционирующий в GF(2) !!! 1 1 1 1 1 1 1 1 1 1 1 1 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты от случайных деструктивных воздействий M. Ivanov http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты • 3от + 4случайных = 2 (т. к. 7 mod 5 = 2), 2 + 3 = 0 воздействий (т. к. 5 mod 5 = 0) деструктивных M. Ivanov http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты • 3от + 4случайных = 2 (т. к. 7 mod 5 = 2), 2 + 3 = 0 воздействий (т. к. 5 mod 5 = 0) деструктивных • 3  4 = 2 (т. к. 12 mod 5 = 2), 2  3 = 1 (т. к. 6 mod 5 = 1) M. Ivanov http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты • 3от + 4случайных = 2 (т. к. 7 mod 5 = 2), 2 + 3 = 0 воздействий (т. к. 5 mod 5 = 0) деструктивных • 3  4 = 2 (т. к. 12 mod 5 = 2), 2  3 = 1 (т. к. 6 mod 5 = 1) • (- 2) = 3 (т. к. 2 + 3 = 0) или (т. к. (- 2) = (0 - 2) = = (5 – 2) mod 5 = 3) (- 4) = 1 (т. к. 4 + 1 = 0) или (т. к. (- 4) = (0 - 4) = = (5 – 4) mod 5 = 1) M. Ivanov http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты • 3от + 4случайных = 2 (т. к. 7 mod 5 = 2), 2 + 3 = 0 воздействий (т. к. 5 mod 5 = 0) деструктивных • 3  4 = 2 (т. к. 12 mod 5 = 2), 2  3 = 1 (т. к. 6 mod 5 = 1) • (- 2) = 3 (т. к. 2 + 3 = 0) или (т. к. (- 2) = (0 - 2) = = (5 – 2) mod 5 = 3) (- 4) = 1 (т. к. 4 + 1 = 0) или (т. к. (- 4) = (0 - 4) = = (5 – 4) mod 5 = 1) • 2-1 = 3 (т. к. 2  3 = 1) M. Ivanov или (т. к. 2-1 = 1/2 = (5 + 1)/2 mod 5 = 6/2 mod 5 = 3) 4-1 = 4 (т. к. 4  4 = 1) или (т. к. 4-1 = 1/4 = (15 + 1)/4 mod 5 = 16/4 mod 5 = 4) http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты • 3от + 4случайных = 2 (т. к. 7 mod 5 = 2), 2 + 3 = 0 воздействий (т. к. 5 mod 5 = 0) деструктивных • 3  4 = 2 (т. к. 12 mod 5 = 2), 2  3 = 1 (т. к. 6 mod 5 = 1) • (- 2) = 3 (т. к. 2 + 3 = 0) или (т. к. (- 2) = (0 - 2) = = (5 – 2) mod 5 = 3) (- 4) = 1 (т. к. 4 + 1 = 0) или (т. к. (- 4) = (0 - 4) = = (5 – 4) mod 5 = 1) • 2-1 = 3 (т. к. 2  3 = 1) M. Ivanov или (т. к. 2-1 = 1/2 = (5 + 1)/2 mod 5 = 6/2 mod 5 = 3) 4-1 = 4 (т. к. 4  4 = 1) или (т. к. 4-1 = 1/4 = (15 + 1)/4 mod 5 = 16/4 mod 5 = 4) • 20 = 1, 21 = 2, 22 = 4, 23 = 3; 30 = 1, 31 = 3, 32 = 4, 33 = 2  2 и 3 – примитивные элементы GF(5) http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(5) = {0, 1, 2, 3, 4} Методы защиты • 3от + 4случайных = 2 (т. к. 7 mod 5 = 2), 2 + 3 = 0 воздействий (т. к. 5 mod 5 = 0) деструктивных • 3  4 = 2 (т. к. 12 mod 5 = 2), 2  3 = 1 (т. к. 6 mod 5 = 1) • (- 2) = 3 (т. к. 2 + 3 = 0) или (т. к. (- 2) = (0 - 2) = = (5 – 2) mod 5 = 3) (- 4) = 1 (т. к. 4 + 1 = 0) или (т. к. (- 4) = (0 - 4) = = (5 – 4) mod 5 = 1) • 2-1 = 3 (т. к. 2  3 = 1) M. Ivanov или (т. к. 2-1 = 1/2 = (5 + 1)/2 mod 5 = 6/2 mod 5 = 3) 4-1 = 4 (т. к. 4  4 = 1) или (т. к. 4-1 = 1/4 = (15 + 1)/4 mod 5 = 16/4 mod 5 = 4) • 20 = 1, 21 = 2, 22 = 4, 23 = 3; 30 = 1, 31 = 3, 32 = 4, 33 = 2  2 и 3 – примитивные элементы GF(5) Что такое элемент M. Ivanovполя GF(5)? http://dozen.mephi.ru MEPhI, 2016 4/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты от случайных деструктивных воздействий M. Ivanov http://dozen.mephi.ru MEPhI, 2016 5/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты • Элементами поля являются двоичные многочлены от случайных деструктивных воздействий степени меньше 3 M. Ivanov http://dozen.mephi.ru MEPhI, 2016 5/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты • Элементами поля являются двоичные многочлены от случайных деструктивных воздействий степени меньше 3 • Многочлены могут быть записаны в виде набора своих коэффициентов M. Ivanov http://dozen.mephi.ru MEPhI, 2016 5/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты • Элементами поля являются двоичные многочлены от случайных деструктивных воздействий степени меньше 3 • Многочлены могут быть записаны в виде набора своих коэффициентов • Сложение элементов поля выполняются по обычным правилам сложения многочленов M. Ivanov с приведением подобных по модулю два http://dozen.mephi.ru MEPhI, 2016 5/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты • Элементами поля являются двоичные многочлены от случайных деструктивных воздействий степени меньше 3 • Многочлены могут быть записаны в виде набора своих коэффициентов • Сложение элементов поля выполняются по обычным правилам сложения многочленов M. Ivanov с приведением подобных по модулю два • Произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на (x) http://dozen.mephi.ru MEPhI, 2016 5/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты • Элементами поля являются двоичные многочлены от случайных деструктивных воздействий • • • • степени меньше 3 Многочлены могут быть записаны в виде набора своих коэффициентов Сложение элементов поля выполняются по обычным правилам сложения многочленов M. Ivanov с приведением подобных по модулю два Произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на (x) (x) – неприводимый многочлен степени 3 http://dozen.mephi.ru MEPhI, 2016 5/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 6/12 Защита информации Лекция № 21 Регистр сдвига с линейной обратной связью (РСЛОС или LFSR) - простейший ГПСЧ http://dozen.mephi.ru MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 7/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты деструктивных 2 +случайных • (xот 1) + (x2 + x + 1) = (1  1) x2 + x +воздействий (1  1) = x M. Ivanov http://dozen.mephi.ru MEPhI, 2016 8/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты деструктивных 2 +случайных • (xот 1) + (x2 + x + 1) = (1  1) x2 + x +воздействий (1  1) = x или 101  111 = 010 M. Ivanov http://dozen.mephi.ru MEPhI, 2016 8/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты деструктивных 2 +случайных • (xот 1) + (x2 + x + 1) = (1  1) x2 + x +воздействий (1  1) = x или 101  111 = 010 • (x2 + 1)  (x2 + x + 1) = x4 + x3 + x2 + x2 + x + 1 = = x4 + x3 + x + 1 = ? M. Ivanov http://dozen.mephi.ru MEPhI, 2016 8/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты деструктивных 2 +случайных • (xот 1) + (x2 + x + 1) = (1  1) x2 + x +воздействий (1  1) = x или 101  111 = 010 • (x2 + 1)  (x2 + x + 1) = x4 + x3 + x2 + x2 + x + 1 = = x4 + x3 + x + 1 = ? x4 + x3 + x + 1 x3 + x + 1  x4 + x2 + x x + 1 M. Ivanov x3 + x2 + 1  x3 + x + 1 x2 + x http://dozen.mephi.ru MEPhI, 2016 8/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты деструктивных 2 +случайных • (xот 1) + (x2 + x + 1) = (1  1) x2 + x +воздействий (1  1) = x или 101  111 = 010 • (x2 + 1)  (x2 + x + 1) = x4 + x3 + x2 + x2 + x + 1 = = x4 + x3 + x + 1 = (x2 + x) mod (x3 + x + 1) x4 + x3 + x + 1 x3 + x + 1  x4 + x2 + x x + 1 M. Ivanov x3 + x2 + 1  x3 + x + 1 x2 + x http://dozen.mephi.ru MEPhI, 2016 8/12 Защита информации Лекция № 21 Пример. GF(23) = {0, g0, g1, g2, g3, g4, g5, g6}, g7 = g0 = 1, g3 + g + 1 = 0 Методы защиты деструктивных 2 +случайных • (xот 1) + (x2 + x + 1) = (1  1) x2 + x +воздействий (1  1) = x или 101  111 = 010 • (x2 + 1)  (x2 + x + 1) = x4 + x3 + x2 + x2 + x + 1 = = x4 + x3 + x + 1 = (x2 + x) mod (x3 + x + 1) x4 + x3 + x + 1 x3 + x + 1  x4 + x2 + x x + 1 M. Ivanov x3 + x2 + 1  x3 + x + 1 x2 + x или g5  g6 = g11 = g4 = x2 + x = 110 http://dozen.mephi.ru MEPhI, 2016 8/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный (x + 1) = (x + 1)4 + (x + 1)3 + (x + 1)2 + (x + 1) + 1 = = x4 + x3 + 1 = (x) – примитивный !!! http://dozen.mephi.ru MEPhI, 2016 10/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный (x + 1) = (x + 1)4 + (x + 1)3 + (x + 1)2 + (x + 1) + 1 = = x4 + x3 + 1 = (x) – примитивный !!! http://dozen.mephi.ru MEPhI, 2016 10/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный http://dozen.mephi.ru MEPhI, 2016 11/12 Защита информации Лекция № 21 Пример. GF(24), (x) = x4 + x3 + x2 + x + 1 - не примитивный http://dozen.mephi.ru MEPhI, 2016 11/12 Защита информации Лекция № 21 ГПСЧ, функционирующие в конечном поле GF(p): схема Фибоначчи N   q1 t  1   ai qi t ,  i 1  q j t  1  q j 1 t , j  2, ..., N http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 ГПСЧ, функционирующие в конечном поле GF(p): схема Галуа  q1 t  1  an q N t ,  q t  1  q t   a j 1 N i 1q N t  ,  j  j  2, ..., N  http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Уравнения работы ГПСЧ, функционирующих в конечном поле GF(p) Ф x    i 0 ai x i (GF ( p)) N q1 t  q2 t  Qt   ... qN t  http://dozen.mephi.ru N   q1 t  1   ai qi t ,  i 1  q j t  1  q j 1 t , j  2, ..., N  q1 t  1  an q N t ,  q t  1  q t   a j 1 N i 1q N t  ,  j  j  2, ..., N  Q(t + 1) = T·Q(t) MEPhI, 2016 9/12 Защита информации Лекция № 21 ГПСЧ, функционирующий в конечном поле GF(p): общая схема Q(t + 1) = Tk·Q(t) http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример. LFSR над GF(2) http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 1 программной реализации двоичного LFSR (начало) ;============================================= ;=== lfsr1 - процедура одного такта работы === ;=== двоичного генератора Фибоначчи. ========= ;============================================= ;=== FeedBack - вектор обратных связей, ====== ;=== например, для LFSR на слайде 16 ========= ;=== FeedBack = 0D400h. ====================== ;=== Mask - код, содержащий «1» в первом ===== ;=== значащем разряде, например, для N = 8 === ;=== Mask = 100h. ============================ ;=== На входе в старших разрядах AX находится ;=== «старое» состояние LFSR, на выходе в старших ;=== разрядах AX - «новое» состояние LFSR. === ;============================================= http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 1 программной реализации двоичного LFSR (окончание) lfsr1 Exit: lfsr1 http://dozen.mephi.ru PROC push bx mov bx, ax shl ax, 1 test bx, FeedBack jp Exit or ax, Mask pop bx ret ENDP MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 2 программной реализации двоичного LFSR (начало) ;============================================= ;=== lfsr2 - процедура одного такта работы === ;=== двоичного генератора Галуа. ;============================================= ;=== FeedBack - вектор обратных связей, ====== ;=== например, для LFSR на слайде 16 ========= ;=== FeedBack = 2B00h. ======================= ;=== На входе в старших разрядах AX находится ;=== «старое» состояние LFSR, на выходе в старших ;=== разрядах AX - «новое» состояние LFSR. === ;============================================= http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 2 программной реализации двоичного LFSR (окончание) (такт работы генератора ненулевых элементов поля GF(2q) или умножение на x в поле GF(2q)) Lfsr2 Exit: Lfsr2 http://dozen.mephi.ru PROC shl ax, 1 jnc Exit xor ax, FeedBack ret ENDP MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 3 умножения на (x + 1) в поле GF(28)) ; === На входе в AL находится α, ============= ; === на выходе в AL – α(x + 1) ============== lfsr PROC mov shl jnc xor Exit: xor ret lfsr ENDP ah, al al, 1 Exit al, FeedBack al, ah http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 3 умножения на (x + 1) в поле GF(28)) ; === На входе в AL находится α, ============= ; === на выходе в AL – α(x + 1) ============== lfsr PROC mov shl jnc xor Exit: xor ret lfsr ENDP ah, al al, 1 Exit al, FeedBack al, ah http://dozen.mephi.ru lfsr PROC push cbw mov shl and xor xor pop ret Lfsr ENDP bx bl, al, ah, al, al, bx MEPhI, 2016 al 1 FeedBack ah bl 9/12 Защита информации Лекция № 21 Пример 4 NLFSR (начало) http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Пример 4 NLFSR (окончание) http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 9/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 9/12 Защита информации http://dozen.mephi.ru Лекция № 21 MEPhI, 2016 9/12 Защита информации Лекция № 21 Самопроверяемый LFSR Ф(x) = (x + 1)φ(x), φ(x) - примитивный http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 Самопроверяемый LFSR Ф(x) = (x + 1)φ(x), φ(x) - примитивный http://dozen.mephi.ru MEPhI, 2016 9/12 Защита информации Лекция № 21 The questions are welcome! http://dozen.mephi.ru MEPhI, 2016