TASKS / OFFICIAL SOLUTIONS

Задания и официальные решения

Формулировки условий сохранены по русскому LaTeX-оригиналу. Решения раскрываются отдельно.

I тур · Теоретический

Задание 1 (4 балла). Найдите последние две цифры числа \(88^{1986}\), записанного в системе счисления с основанием 5.

Задание 1 (4 балла). Найдите последние две цифры числа \(88^{1986}\), записанного в системе счисления с основанием 5.

Показать официальное решение

Чтобы найти последние две цифры, находим остаток по \({100}_5=25\): \(88\equiv13\pmod{25}\), \(\varphi(25)=20\), поэтому \(13^{1986}\equiv13^6\equiv9\pmod{25}\). Переводим 9 в пятеричную систему: \(9=1\cdot5+4={14}_5\). Ответ: \(14_5\).

Задание 2 (4 балла). Рассматривается двоичный канал, в котором каждый бит искажается с вероятностью \(p\ (0

Задание 2 (4 балла). Рассматривается двоичный канал, в котором каждый бит искажается с вероятностью \(p\ (0

Показать официальное решение

Правильное восстановление происходит при не более чем одной ошибке: \[P=(1-p)^3+3p(1-p)^2=(1-p)^2(1+2p).\] Для одного бита вероятность равна \(1-p\). Сравнение даёт \((1-p)^2(1+2p)>1-p\Longleftrightarrow p(1-2p)>0\). Следовательно, тройное повторение лучше при \(0

Задание 3 (5 баллов). Булева функция \(f(x_1,x_2,x_3,x_4)\) обладает свойствами: при изменении \(x_1\) или \(x_4\) функция меняется на противоположную; при одновременном изменении \(x_2,x_3\) она также меняется на противоположную. Последовательность задаётся правилом \(s_{k+4}=f(s_k,s_{k+1},s_{k+2},s_{k+3})\), первые элементы: \(0,0,1,1,0,1\). Найдите \(s_7,s_8\) и определите линейность.

Задание 3 (5 баллов). Булева функция \(f(x_1,x_2,x_3,x_4)\) обладает свойствами: при изменении \(x_1\) или \(x_4\) функция меняется на противоположную; при одновременном изменении \(x_2,x_3\) она также меняется на противоположную. Последовательность задаётся правилом \(s_{k+4}=f(s_k,s_{k+1},s_{k+2},s_{k+3})\), первые элементы: \(0,0,1,1,0,1\). Найдите \(s_7,s_8\) и определите линейность.

Показать официальное решение

Свойства дают общий вид \(f=x_1\oplus x_i\oplus x_4\oplus c\), где \(i\in\{2,3\}\). Проверка по \(s_5,s_6\) выбирает \(i=3,c=0\), то есть \(f=x_1\oplus x_3\oplus x_4\). Поэтому \(s_7=f(1,1,0,1)=0\), \(s_8=f(1,0,1,0)=0\). Функция линейна, так как не содержит произведений переменных.

Задание 4 (5 баллов). В системе генерируются 6-битные ключи. Слабый ключ начинается на «00» (A), заканчивается на «11» (B) или содержит ровно четыре единицы (C). Найдите число слабых ключей.

Задание 4 (5 баллов). В системе генерируются 6-битные ключи. Слабый ключ начинается на «00» (A), заканчивается на «11» (B) или содержит ровно четыре единицы (C). Найдите число слабых ключей.

Показать официальное решение

По формуле включений–исключений: \(|A|=16,|B|=16,|C|=\binom64=15\); \(|A\cap B|=4,|A\cap C|=1,|B\cap C|=\binom42=6,|A\cap B\cap C|=1\). Тогда \(N=16+16+15-(4+1+6)+1=37\). Ответ: 37.

Задание 5 (7 баллов). Пусть \(p=2^{13}-1=8191\) — простое число Мерсенна, причём \(p\equiv3\pmod4\). Найдите \(x\), \(0\le x

Задание 5 (7 баллов). Пусть \(p=2^{13}-1=8191\) — простое число Мерсенна, причём \(p\equiv3\pmod4\). Найдите \(x\), \(0\le x<8191\), такое что \(x^2\equiv2\pmod{8191}\). Символ Лежандра показывает, что 2 является квадратичным вычетом по модулю p.

Показать официальное решение

При \(p\equiv3\pmod4\): \(x\equiv2^{(p+1)/4}=2^{2048}\pmod{8191}\). Так как \(2^{13}\equiv1\pmod{8191}\), а \(2048=13\cdot157+7\), получаем \(x\equiv2^7=128\pmod{8191}\). Ответ: \(x=128\).

II тур · Криптоанализ

Задача 1 (10 баллов). NLFSR длины 4: \(s_{t+4}=s_t\oplus(s_{t+1}\cdot s_{t+2})\oplus1\), \(z_t=s_t\oplus s_{t+1}\oplus(s_{t+2}\cdot s_{t+3})\). Первые четыре бита \(Z=(0,1,1,1)\). Найдите ключ \(K=(s_0,s_1,s_2,s_3)\) и \(z_4\).

Задача 1 (10 баллов). NLFSR длины 4: \(s_{t+4}=s_t\oplus(s_{t+1}\cdot s_{t+2})\oplus1\), \(z_t=s_t\oplus s_{t+1}\oplus(s_{t+2}\cdot s_{t+3})\). Первые четыре бита \(Z=(0,1,1,1)\). Найдите ключ \(K=(s_0,s_1,s_2,s_3)\) и \(z_4\).

Показать официальное решение

Из \(z_0=0\) следует \(s_2s_3=s_0\oplus s_1\), поэтому по закону обновления \(s_5=\overline{s_0}\). Проверка случаев даёт \(K=(1,1,0,1)\). Далее \(s_4=0,s_5=0,s_6=1,s_7=0\), откуда \(z_4=s_4\oplus s_5\oplus(s_6s_7)=0\). Ответ: \(K=(1,1,0,1), z_4=0\).

Задача 2 (15 баллов). Гибридный шифр: \(C_i=(aP_i+b+F_{k+i-1})\pmod{26}\), \(\gcd(a,26)=1\), \(F_1=F_2=1\). Первые буквы сообщения ART, шифртекст KLUGMNM. Найдите \(a,b,k\) и расшифруйте сообщение.

Задача 2 (15 баллов). Гибридный шифр: \(C_i=(aP_i+b+F_{k+i-1})\pmod{26}\), \(\gcd(a,26)=1\), \(F_1=F_2=1\). Первые буквы сообщения ART, шифртекст KLUGMNM. Найдите \(a,b,k\) и расшифруйте сообщение.

Показать официальное решение

Из первых трёх букв получаем сравнения \(17a+F_{k-1}\equiv1\pmod{26}\) и \(2a+F_k\equiv9\pmod{26}\). Исключение \(a\) даёт \(4F_k-2F_{k-1}\equiv8\pmod{26}\), откуда \(k=4\). Тогда \(2a+3\equiv9\), допустимое по условию НОД решение \(a=3\), а из первого сравнения \(b=7\). Обратный ключ: \(3^{-1}\equiv9\pmod{26}\). Дешифрование даёт ARTEMIS.

Задача 3 (10 баллов). В Эль-Гамале \(p=23,g=5,y=13\), \(r=g^k\pmod p\), \(s=(h-xr)k^{-1}\pmod{p-1}\). Для последовательных подписей: \((h_1,r_1,s_1)=(10,20,12)\), \((h_2,r_2,s_2)=(12,8,9)\), \(k_2=k_1+1\). Найдите секретный ключ \(x\).

Задача 3 (10 баллов). В Эль-Гамале \(p=23,g=5,y=13\), \(r=g^k\pmod p\), \(s=(h-xr)k^{-1}\pmod{p-1}\). Для последовательных подписей: \((h_1,r_1,s_1)=(10,20,12)\), \((h_2,r_2,s_2)=(12,8,9)\), \(k_2=k_1+1\). Найдите секретный ключ \(x\).

Показать официальное решение

Из формулы подписи: \(sk+rx\equiv h\pmod{22}\). Получаем \(12k_1+20x\equiv10\) и \(9(k_1+1)+8x\equiv12\), то есть \(9k_1+8x\equiv3\). Исключение \(k_1\) даёт \(6x\equiv18\pmod{22}\), поэтому \(x\equiv3\pmod{11}\): кандидаты \(x=3,14\). Проверка \(5^x\equiv13\pmod{23}\) оставляет \(x=14\). Ответ: \(x=14\).