Атака с открытым текстом на потоковый шифр на основе LFSR
Я читаю книгу о криптографии, и я застрял в вопросе. Я действительно пытаюсь решить это неделями. Но я думаю, что проблема в том, что я не мог понять всю картину. Вопрос был такой:
Мы проводим атаку с использованием открытого текста на потоковый шифр на основе LFSR. Мы знаем, что отправленный открытый текст был:
1001 0010 0110 1101 1001 0010 0110
При нажатии на канал мы наблюдаем следующий поток:
1011 1100 0011 0001 0010 1011 0001
1- What is the degree m of the key stream generator?
2- What is the initialization vector?
3- Determine the feedback coefficients of the LFSR.
4- Draw a circuit diagram and verify the output sequence of the LFSR.
Большое спасибо за вашу помощь, чтобы понять криптографию и LFSR.
2 ответа
Вы имеете в виду " Понимание криптографии" Паара и Пелзи, верно? Вторую главу можно найти в Интернете на сайте Springer, который должен быть законным, если Springer является издателем.
Я бы сказал, что второй список - это зашифрованный текст, то есть обычный XOR с потоком ключей. Тогда ключевой поток будет
1001 0010 0110 1101 1001 0010 0110
XOR 1011 1100 0011 0001 0010 1011 0001
= 0010 1110 0101 1100 1011 1001 0111
или же
0010111 0010111 0010111 0010111
сгруппированы в блоки по 7 бит. Учитывая теорему 2.3.1 "Максимальная длина последовательности, генерируемая LSFR степени m, равна (2^m)-1", вы можете догадаться, что степень может быть равна 3, поскольку длина последовательности LSFR представляется равной 7. Обратите внимание, что Степень подсчитывает внутренние состояния LSFR и не относится к степени полинома. Согласно формуле (2.1) его степень на единицу меньше.
Итак, что вы хотите рассчитать, это решение уравнений
p(0,0,1)=0
p(0,1,0)=1
p(1,0,1)=1
за p(s_0,s_1,s2)=p_0*s_0+p_1*s_1+p_2+s_2 и проверьте, что остальная часть потока ключей также соответствует этой формуле. Делая это, вы получаете следующую матрицу:
0 0 1 | 0
0 1 0 | 1
1 0 1 | 1
Так p_0=1, p_1=1 а также p_2=0, Который соответствует остальной части ключевого потока.
Вопрос предоставляет недостаточную информацию. Есть несколько решений.
Шаг первый - определить ключевой поток. Поскольку вы знаете открытый текст и зашифрованный текст, это должно быть легко. Просто сделайте два раза.
Стандартным способом для LFSR является использование примитивного полинома степени m над полем с двумя элементами, 0 и 1. В таком случае длина последовательности до повторения составляет 2^m -1. Здесь у вас есть 28 бит. Таким образом, предполагаемое решение состоит в том, чтобы иметь m = 3. Действительно, вы можете разбить 28 битов ключевого потока, разбитых на 3 повторных экземпляра первых 7 битов.
В предположении, что m = 3, первые 3 бита ключевого потока являются вектором инициализации. Из этого вы должны быть в состоянии определить ответвления в LFSR. Вы можете проверить свой ответ с тем фактом, что есть только два примитивных полинома степени 3 над полем с двумя элементами: x^3 + x^2 + 1 и x^3 + x + 1.
Причина в том, что информации недостаточно, в том, что поток ключей может быть первыми 28 битами LFSR степени 5 или степени 6 или степени 7... Вы понимаете.
ДОБАВЛЕНО Предположим, у вас есть LFSR степени m с вектором инициализации 0000...01. Я делаю левый сдвиг. Теперь сделайте один шаг из LFSR. Самый левый бит отбрасывается, оставшиеся m-1 биты сдвигаются влево, а новый самый правый бит - это xor всех ответвлений. Следовательно, учитывая вектор инициализации, новый самый правый бит равен единице тогда и только тогда, когда в самой правой ячейке имеется ответвление. Теперь сделайте еще одну смену. Новый крайний правый бит представляет собой комбинацию xors двух крайних правых ячеек. Из предыдущего шага вы знаете, есть ли постукивание по последней ячейке. Следовательно, после двух смен вы знаете, есть ли какие-либо постукивания по двум самым правым ячейкам. Продолжая таким образом, вы можете определить все краны.