Отборочный этап олимпиады по математике и криптографии 2024-2025

Наш курс: курсы/осенний-курс/ Календарь олимпиадных событий: Страница олимпиады: олимпиады/олимпиада-по-математике-и-криптограф/ Каждый из трех владельцев криптокошельков имеет на своем счету по 10 криптокойнов. Каждый из двух дней ими совершаются по две транзакции: по переводу части криптокойнов со своего криптокошелька на криптокошелек другого владельца и по возврату оставшихся криптокойнов обратно на свой кошелек. У каждого имеется свой секретный ключ S ∈{1,2,...,28} . При совершении транзакции указываются три числа (X,a,b) , где X - число переводимых криптокойнов, (a,b) - электронная подпись перевода. Электронная подпись находится по правилу: выбираем произвольное k ∈{1,2,...,28} , затем находим a= r29(2k) ,b= r28(Xa Sk) , где rN(M )− остаток от деления числа M на N . На рисунке указаны совершенные транзакции (пронумерованы числами в кружках) за два дня. Сколько будет криптокойнов у каждого владельца криптокошелька по окончании двух дней? Шифрпреобразование простой замены в алфавите A = {a1, a2, ..., an}, состоящем из n различных букв, заключается в замене каждой буквы шифруемого текста буквой того же алфавита, причём разные буквы заменяются разными. Ключом шифра простой замены называется таблица, в которой указано, какой буквой надо заменить каждую букву алфавита A. Если слово СРОЧНО зашифровать простой заменой с помощью ключа: то получится слово ВЗДАБД. Зашифровав полученное слово с помощью того же ключа еще раз, получим слово ЮШЫЧЯЫ. Сколько всего различных слов можно получить, если указанный процесс шифрования продолжать неограниченно Вася хочет заполнить квадратную таблицу (криптографическую мозаику) размера 4× 4 целыми числами от 1 до 16 по следующему правилу. Сначала он выбирает четыре целых числа b1,b2,b3,b4 ∈{0,1,...,16} . Затем первую строку Вася заполняет числами (1) ai ≡ (bi 1)(mod17), i=1,2,3,4; вторую строку — числами (2) ai ≡ (bi 4)(mod17), i=1,2,3,4; третью (3) ai ≡(bi 13)(mod17), i= 1,2,3,4 и, аналогично, четвертую (4) ai ≡ (bi 16)(mod17), i=1,2,3,4. При этом числа b1,b2,b3,b4 Вася выбрать должен так, чтобы все числа в таблице оказались различными. Сумеет ли Вася это сделать? Если да, то чему равны b1,b2,b3,b4 ? Квадратная таблица размером 1997×1997 заполнена натуральными числами от 1 до 1997 так, что в каждой строке присутствуют все числа от 1 до 1997. Найдите сумму чисел, стоящих на диагонали, которая соединяет левый верхний и правый нижний углы таблицы, если заполнение таблицы симметрично относительно этой диагонали. В криптосистеме RSA (знания алгоритма шифрования не требуется для решения задачи) элементы надёжности определяются несколькими параметрами. В частности, выбором числа 𝑁 = 𝑝 ∙ 𝑞, где 𝑝, 𝑞 – различные нечётные простые числа, и значением 𝜑(𝑁) = (𝑝 − 1) ∙ (𝑞 − 1). Известна следующая теорема (малая теорема Ферма): если 𝑝 – простое число, 𝑎 – целое число, не делящееся на 𝑝, то 𝑎 𝑝−1 = 1(𝑚𝑜𝑑 𝑝). Используя это: a) докажите, что 𝑥 𝜑(𝑁) 2 1 = 𝑥(𝑚𝑜𝑑 𝑁) для всех x∈ {1,2, … , 𝑁 − 1}. b) найдите 𝑝 и 𝑞 , если известно, что 𝑁 = 42494861 и 𝑥 21240913 = 𝑥(𝑚𝑜𝑑 𝑁) для всех x∈ {1,2, … , 𝑁 − 1}.