Кpиптогpафия от папиpуса до компьютеpа


Задачи и упражнения


Для тех, кого увлекло содержимое этой книги и кто хочет закрепить полученные знания, предлагается ряд задач, самостоятельное решение которых поможет несколько глубже понять криптографическую стряпню и теорию. Задачи повышенной сложности отмечены знаком Т.

1. Докажите, что каждая подгруппа циклической группы сама будет циклической.
     2. Будут ли циклическими группы по умножению целых чисел, вычисляемых по модулям 5,6,7,8? Как цикличность связана со значением модуля? 3. Перестановка двух элементов множества называется транспозицией. Как любую перестановку заменить последовательностью транспозиций? Сколько транспозиций понадобится, если переставляется n элементов?
     4. Любая перестановка Р может быть разложена на непересекающиеся циклы элементов, переходящих друг в друга. Так, цикл (х, у, z) означает, что у=Рх, z=Py и x=Pz. Докажите, что существует целое число k, такое, что при любом х из переставляемого множества, выполняется

     (P**k)*x=x

     5. Вычислите максимальное значение k в предыдущей задаче для перестановки множества из 10 элементов.
     6. Найдите условие, при котором для перестановки Р и любого элемента х будет справедливо (Р**2)*х=х. Что означает это свойство перестановки для криптографии?
     7. Для контроля качества шифрования и расшифровывания в текст сообщения включают так называемую сигнатуру, находящуюся в определенном месте, например, в начале. Если сигнатура фиксированная, например - "ENCRYPTION PROG", то не ослабляет ли это шифр? Как повлияет на криптографическую стойкость шифра сигнатура в виде суммы XOR, выполненная по всем символам текста?
     8. Выпишите все невырожденные матрицы 2х2 над GF(2). Какова их доля от общего числа матриц 2х2? Какое число невырожденных матриц над GF(2) размера 16х16?
     9. Проверьте, образуют ли поле остатки от деления на многочлен х**4+х**2+1.
     10. Докажите, что при положительных целых числах k, m и n число k**n-1 тогда и только тогда делится на k**m-1, когда n делится на m.
     11. Докажите, что многочлен х**5+х**4+х**3+1 имеет порядок 13.
     12. Докажите, что многочлен х**4+х+1 примитивен над GF(2).
     13. Сравните мультипликативные группы, порожденные вычетами по неприводимым над GF(2) многочленам х**3+х**2+1 и х**3+х+1.
     14. Т Доказать, что если многочлен р(х)**n примитивен над GF(2), то многочлен р(х)**k примитивен тогда и только тогда, когда число k взаимно просто с 2**n-1. Оцените число примитивных многочленов над GF(2**n).
     15. T Докажите, что любой многочлен р(х), удовлетворяющий уравнению р(х)**L=1, где L=2 , является степенью примитивного.
     16. Вычислите первые десять членов всех последовательностей, удовлетворяющих следующему рекуррентному соотношению Si+S(i-2)+S(i-3).
     17. Проверьте, что для предыдущей задачи последовательность, начинающаяся с 101, может быть образована как сумма двух последовательностей, начинающихся с 110 и с 011.
    




- Начало -  - Назад -  - Вперед -



Книжный магазин