Тема Верченко (криптография)

Верченко - задания по годам → .03 Верченко 2021

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела верченко (криптография)

Разделы подтемы Верченко - задания по годам

Верченко 2019 и ранее

Верченко 2020

Верченко 2021

Верченко 2022

Верченко 2023

Верченко 2024

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#99574

Найдите наибольшее пятизначное число, которое в $51$ раз больше квадрата суммы своих цифр. Решение обоснуйте.

Источники: Верченко - 2021, 11.1 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Давайте введём переменные и составим уравнение из условия. Решать мы должны в целых числах, значит, имеет смысл зацепиться за делимость!

Подсказка 2

Наше число должно делиться на 3. Но как это может повлиять на сумму?

Подсказка 3

Сумма тоже будет делиться на 3. Продолжая рассуждать, сможем оценить сумму цифр и разобраться, какие значения она может принимать ;)

Показать ответ и решение

Обозначим $x$ — искомое число, $s$ - сумма его цифр. Тогда $x =3⋅17⋅s2.$ Следовательно, $x$ делится нацело на $3.$ По признаку делимости на $3,$ число $s$ делится на $3.$ Но тогда $x$ делится на $9.$ По признаку делимости на $9,s$ делится на $9.$ Так как искомое число пятизначное, то для $s$ возможны $5$ вариантов: $s =9,s= 18,s= 27,s =36,s= 45.$ Для каждого $s,$ соответственно, находим: $x =4131,x =16524,x= 37179,x= 66096,x= 103275.$ Первое и последнее — не пятизначные, у четвёртого сумма цифр не равна $36.$ Подходящие: $x= 16524,x =37179.$

Ответ:

$37179$ или $16524$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#99580

На координатной прямой отмечены $9$ точек с координатами $2;25;7;−3;12;19;−5;8;9.$ Найдите координату точки, сумма расстояний от которой до указанных $9$ точек минимальна. Ответ обоснуйте.

Источники: Верченко - 2021, 11.2 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Попробуйте упорядочить точки и предположить, каким может быть ответ. Как изменится сумма расстояний, если точку подвинуть совсем на немного?

Подсказка 2

Если искомую точку подвинуть так, чтобы она не «перепрыгнула» через одну из наших точек на прямой, то как изменится сумма расстояний?

Подсказка 3

Сумма расстояний только увеличится! Значит, имеет смысл рассмотреть искомую точку так, чтобы она совпадала с одной из данных на прямой ;)

Показать ответ и решение

Расположим числа в порядке возрастания: $− 5;− 3;2;7;8;9;12;19;25.$ Покажем, что медиана этого ряда - число $8$ - является искомым. Обозначим $s(y)$ — сумма расстояний от числа $y$ до остальных чисел.

Рассмотрим число $y = 8+ x.$ Если $x∈ (0;1),$ то сумма расстояний от $y$ до первых четырёх чисел увеличится на $4x,$ а до последних четырёх — уменьшится на $4x$ (по сравнению с числом $8$ ), и при этом до самого числа $8$ расстояние равно $x,$ то есть $s(y)= s(8)+ x.$ Если $x =1$ , то есть $y = 9$ , то сумма расстояний от $y$ до всех чисел будет равна $s+ 1.$ Рассуждая аналогично при $x∈ (1;+∞ ),$ получим вывод: минимальное значение $s(y)$ достигается при $y = 8.$ При отрицательных значениях $x$ рассуждения ничем не отличаются.

Ответ:

$8$

Ошибка.
Попробуйте повторить позже

Задача 3#99581

Ключом шифрсистемы служит таблица $4 ×4,$ в каждую ячейку которой записана одна из цифр $0,1,2.$ При этом должны делиться на $3$ сумма цифр в каждой строке, сумма цифр в каждом столбце, а также суммы цифр на каждой из двух диагоналей таблицы $4× 4.$

Один из возможных вариантов ключа:


1	1	2	2

2	1	1	2

0	0	1	2

0	1	2	0

А сколько всего существует различных ключей?

Источники: Верченко - 2021, 11.3 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

В таких задачах зачастую удобно бывает найти параметры, которые, как в геометрии, фиксируют картинку. То есть, если какие-то числа в табличке определены, то и вся остальная таблица определяется однозначно. При этом, хотелось бы минимизировать число таких параметров, а также что-то понять про множество их значений. Всё это выше рассказано таким общим языком не чтобы вас напугать, а чтобы вы в аналогичных задачах видели схожие паттерны. Так какие же числа можно зафиксировать, чтобы все остальное у нас определялось единственным образом, а также, желательно, чтобы для любого набора параметром у нас восстанавливалась однозначно картинка?

Подсказка 2

Заметим, что если мы определили числа в верхнем левом квадрате 3 на 3, то мы определили всю таблицу. Понятно, что картинка тогда восстанавливается, но не будет ли противоречий при каких-то заполнениях квадрата 3 на 3 на диагонали?

Подсказка 3

Конечно, противоречия могут быть. Поэтому надо добавить еще два линейных равенства на диагонали. А значит, у нас есть 9 переменных и два равенства. Отсюда 7 свободных переменных, а потому вариантов 3⁷.

Показать ответ и решение

Указанную в условии таблицу $4 ×4$ , можно построить следующим образом: положим элементы верхнего левого угла размеров $3× 3$ произвольным образом, после чего заметим, что все оставшиеся элементы определяются однозначно из линейных (по модулю $3$ ) соотношений для строк и столбцов (при этом элемент в правом нижнем углу будет равен сумме по модулю $3$ всех остальных элементов квадрата). Плюс к этому имеем два линейных соотношения для элементов диагоналей. Таким образом, общее число независимого выбора переменных $ai,j,i,j = 1,2,3$ равно $7.$ Следовательно, общее число ключей равно $7 3 = 2187.$

Ответ:

$2187$

Ошибка.
Попробуйте повторить позже

Задача 4#99583

Целое число $s∈ {0,...,30}$ может быть преобразовано следующим образом. Пусть, например, $s= 9.$ Представим его в двоичной системе счисления пятизначным числом: $s= 9= 010012.$ Теперь выберем какое-нибудь целое число $c≥ 0$ и сдвинем получившуюся строку $01001$ циклически на $c$ позиций влево. Например, при $c= 1$ получится строка 10010, представляющая собой двоичную запись числа 18. Значит, сдвигом на одну позицию из числа 9 получается число $18;$ будем это записывать так: $9 ⋘ 1= 18.$

(Если $01001$ сдвинуть влево на две позиции, то получится $00101,$ то есть $9 ⋘ 2= 5.$ )

Итак, $s≪ c$ — это число, получившееся сдвигом числа $s$ на $c$ позиций влево.

Для зашифрования осмысленного слова выбирается секретный ключ — набор из $64$ чисел

k1,...,k32 ∈{0,...,30} и c1,...,c32 ∈{0,1,2,3}.

Затем с каждой буквой слова (по отдельности) проделывается следующее.

Букву заменяют числом $a$ по таблице

$|---|---|---|---|----|---|----|---|---|---|----|---|----|---|---|---|----|---|---|----|---|---|---|----|----|---|----|---|---|----|----| |А--|Б--|-В-|-Г-|-Д--|Е--|Ж---|З--|И--|-К-|-Л--|М--|-Н--|О--|-П-|-Р-|-C--|Т--|У--|-Ф--|Х--|Ц--|-Ч-|-Ш--|-Щ--|-Б-|-Ы--|-Б-|-Э-|-Ю--|-Я--| -0----1---2---3---4---5----6---7----8---9---10--11---12--13--14---15---16--17--18---19---20--21---22---23---24---25---26--27---28---29---30--$

и последовательно вычисляют

a1 = (a+ k1)⋘ c1,a2 =(a1+ k2)⋘ c2,...,a32 =(a31+k32)⋘ c32.

Исходную букву затем заменяют на букву, соответствующую числу $a32.$

(Если в процессе вычислений получается число, превышающее $30,$ то оно заменяется остатком от деления на $31.$ Так, сумму $20+ 17$ следует заменить на $6.$ )

В результате зашифрования получился набор букв ЯГКЫНИ.

Найдите исходное слово, если известно, что при зашифровании на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е.

Источники: Верченко - 2021, 11.4 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

В таких задачах, где идёт сложный процесс, хорошей идеей будет посмотреть на первые несколько шагов. Вдруг обнаружится цикличность, или можно будет заметить явную закономерность и вывести общую формулу. Попробуйте посмотреть, как меняется для чисел, которые записываются в виде пяти знаков (может быть с нулями в начале) в двоичной системе счисления, значение при операции левого циклического сдвига (то есть при с=1).

Подсказка 2

Заметим, что s « 1 = 2s (mod 31) (для этого надо разобрать два случая, чему равна первая цифра в двоичной системе счисления). Тогда s « c = 2^c * s (mod 31). А это значит, что мы стали чуть больше понимать, как работает процесс. Однако, все ещё не представляется возможным решить задачу, потому что даже сейчас непонятно, как явным образом ввести ограничения на k_i и c_i. Каким свойством обладает преобразование s « c? А что будет, если сделать не s « c, а (k + n) « c? Чему равно такое выражение?

Подсказка 3

Преобразование линейно, а значит и композиция преобразований тоже линейна. Значит оно записывается в виде kx + b. Что тогда можно сказать про k и b, если у нас есть значения на двух разных аргументах?

Показать ответ и решение

Покажем, что

c (s ≪ c)= r31(s⋅2 ).

Заметим, что достаточно доказать для $c= 1.$ Пусть $s= (s4s3s2s1s0) . 2$ Если $s4 = 0$ , то равенство ( $∗)$ очевидно. Если $s4 = 1,$ то

3 2 s= 16+ 2 ⋅s3+ 2 ⋅s2+2⋅s1+ s0.

Тогда

r31(s⋅2)= 24⋅s3+23⋅s2+ 22⋅s1+ 2⋅s0+ 1=(s≪ c),

и равенство $(∗)$ доказано. Следовательно,

a1 =((a+k1)≪ c1)=r31((a+ k1)⋅2c1)= r31(a⋅2c1 + k1⋅2c1).

То есть, на одном шаге шифрования — линейное преобразование числа $a.$ Так как композиция линейных преобразований есть линейное преобразование, то $a32 =(a⋅x+ k)$ , где $x$ и $k$ — неизвестные.

Воспользуемся тем, что на этом ключе буква Ъ переходит в букву Ь, а буква П — в Е:

27 ≡ (25⋅x +k), 5 ≡ (14⋅x+k) 31 31

Вычитая из первого равенства второе, получим: $22= 11⋅x.$ Отсюда $x= 2.$ Тогда

27 ≡ (25⋅2+ k) 31

и, следовательно, $k= 8.$ Окончательно получили:

a32 =(a⋅2+ 8)

Тогда

a= 2−1(a − 8)=16⋅a + 27 32 32

Последовательно подставляя буквы шифрованного текста ЯГКЫНИ, получим исходное слово МОСКВА.

Ответ:

МОСКВА

Ошибка.
Попробуйте повторить позже

Задача 5#99588

Для зашифрования осмысленного слова его буквы заменили числами $x ,x ,...,x 1 2 n$ по таблице.

Затем выбирали четные натуральные числа $p$ и $q$ и для каждого числа $xi$ из соотношений

xi = yi+ pzi,zi =yi+ qxi

нашли целые числа $yi$ и $zi$ .

Потом по формулам

′ zi = r32(zi),i= 1,...,n

получили числа

z′,...,z′ 1 n

(где $r32(a)$ — остаток от деления числа $a$ на 32), которые вновь заменили буквами согласно таблице:

$|---|---|---|---|----|---|----|---|---|---|----|---|----|---|---|---|----|---|---|----|---|---|---|----|----|---|----|---|---|----|----| |А--|Б--|-В-|-Г-|-Д--|Е--|Ж---|З--|И--|-К-|-Л--|М--|-Н--|О--|-П-|-Р-|-C--|Т--|У--|-Ф--|Х--|Ц--|-Ч-|-Ш--|-Щ--|-Б-|-Ы--|-Б-|-Э-|-Ю--|-Я--| |0 | 1 | 2 | 3 | 4 |5 | 6 |7 | 8 | 9 | 10 |11 | 12 |13 |14 | 15 | 16 |17 |18 | 19 |20 |21 | 22 | 23 | 24 | 25 | 26 |27 | 28 | 29 | 30 | ----------------------------------------------------------------------------------------------------------------------------------------$

В результате получили вот что: ЖЯЮЦКР.

Найдите исходное слово, если известно, что оно начинается на букву В.

Источники: Верченко - 2021, 11.5 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Нам надо явным образом связать x и z’ по модулю 32. Давайте тогда вычтем из первого равенство второе, чтобы у нас лишняя переменная y ушла. Тогда как можно связать x и z’?

Подсказка 2

Тогда выходит, что x(1 + q) = z’(1 + p) (mod 32). Если мы выразим (1 + q) через (1 + p) по модулю 32 с некоторыми константными коэффициентами, то мы сможем домножить на это модульное равенство наше равенство выше и после сокращения (1 + q) и (1 + p) в обеих частях мы получим явную связь x и z’. Стоит вспомнить, что мы ещё не использовали условие на первую букву!

Подсказка 3

Давайте теперь возьмем условие для первой буквы и посмотрим, что оно дает. Получается, что (1 + q) = 3(1 + p) (mod 16). Помножим на 3^-1 mod 16, и получим некоторое равенство, где коэффициент теперь у (1 + q). Тогда выходит, что c(1 + q) = (1 + p) (mod 32), где c = 11 или 27. А значит, получили явную связь на x и z’. Осталось проверить дешифровку на осмысленность и задача решена!

Показать ответ и решение

Рассмотрим произвольную букву открытого и шифрованного текстов. Для соответствующих им (по таблице) чисел $x$ и $z′$ выполняются равенства $x= y+ pz$ и $z =$ $y+ qx$ , при некотором $y,p$ и $q$ . При этом по условию $′ z= r32(z)$ . Используя свойство сравнений по модулю целого числа, получим: $′ ′ x − z = pz− qx(mod32)$ или $x(1+ q)=$ $′ z(1+p)(mod32)$ . Для дальнейшего решения будем пользоваться следующим свойством: если наибольший общий делитель чисел $a$ и $n$ равен $1,$ то сравнение $x= y(modn )$ равносильно $ax=$ $ay(modn)$ . Используя условие задачи для первой буквы открытого и шифрованного текста, получим равенство $2(1+q)= 6(1 +p)(mod32)$ . Заметим, что сравнение $6t= 2(mod32)$ имеет 2 решения по модулю $32:t= 11(mod32)$ , $t= 27(mod32)$ . Тогда получим, что $11⋅(1+q)= (1+p)(mod32)$ или $27⋅(1+ q)= (1+ p)(mod32)$ для каждого $t$ . Таким образом, $′ x =11z(mod32)$ или $′ x =27z(mod32)$ соответственно. Остается воспользоваться полученными соотношениями для остальных букв.

Осмысленное слово получается только при втором варианте. А значит, исходное слово ВЕКТОР.

Ответ:

ВЕКТОР

Ошибка.
Попробуйте повторить позже

Задача 6#99591

Устройство принимает на вход и выдает на выход наборы из $n$ битов (причем $n ≥4$ ). Поданный на вход набор $x = (x ,...,x ) 1 n$ преобразуется в выходной набор

h(x)= (x1⊕ xn−1,x2 ⊕xn,x2⊕x3,x3⊕ x4,...,xn−2⊕ xn−1,x1⊕ xn),

где $⊕$ — стандартная операция сложения битов: $0⊕ 0= 1⊕1 =0,0⊕1 =1 ⊕0= 1$ .

Подав теперь этот набор $h(x)$ на вход, получим на выходе набор $h(h(x ))= h(2)(x)$ , который вновь подадим на вход и получим $h(3)(x)$ и т.д.

Докажите, что если все наборы

(2) (k) x,h(x),h (x),...,h (x)

оказались различными, то $k≤ 2n− 1− 1$ .

Источники: Верченко - 2021, 11.6 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Заметим, что для всех x вектор h(x) содержит четное число единиц. Сколько всего существует векторов, в которых единиц чётное число?

Подсказка 2

Конечно, 2ⁿ⁻¹. Значит, нам нужно улучшить нашу оценку всего на 1. Если встретятся все векторы с чётным число единиц, то встретится и нулевой. Какие векторы с чётным числом нулей могут перейти в него?

Подсказка 3

Если n нечётное, то подойдёт только сам нулевой вектор. Если же n чётное, то есть вектор из всех единиц. Тогда, используя идею чередования, можно найти 2 вектора, которые переходят в (1, 1, ..., 1), что приводит к противоречию.

Показать доказательство

Заметим, что для всех $x$ вектор $h(x)$ содержит четное число единиц, так как

(x1⊕ xn−1)⊕(x2⊕ xn)⊕(x2⊕ x3)⊕ (x3 ⊕x4)⊕...⊕(xn−2⊕ xn− 1)⊕ (x1 ⊕xn)= 0.

Значит, в рассматриваемой последовательности

(2) (k) x,h(x),h (x),...,h (x)

все векторы, начиная со второго, имеют четное количество единиц. Количество всех векторов, имеющих четное количество единиц, равно $2n−1$ . Поэтому претендентом на самое большое количество различных векторов является последовательность (*), начинающаяся с вектора, содержащего нечетное количество единиц и продолжающаяся всеми векторами с четным количеством единиц. Количество векторов в такой последовательности будет $1+ 2n−1$ Таким образом,

n−1 k≤ 2 .

Для получения оценки $k≤ 2n−1− 1$ рассмотрим отдельно случай когда среди векторов последовательности (*) нет нулевого вектора $(0,0,...,0)$ и когда он есть.

Если в последовательности (*) нет вектора $(0,0,...,0)$ , то она содержит не более $1+ (2n−1− 1)= 2n− 1$ векторов и

k≤ 2n−1− 1.

Пусть теперь последовательность (*) содержит вектор ( $0,0,...,0$ ). Рассмотрим два случая.

1) Если $n$ — нечетное число, то

h(0,0,...,0)= h(1,1,...,1)=(0,0,...,0)

и других векторов, переходящих в нулевой нет. При этом не существует векторов $z$ таких, что

h(z)= (1,1,...,1)

Таким образом в этом случае последовательность (*) содержит максимум два вектора и

k≤ 2n−1− 1.

2) Если $n$ — четное число, то

h(0,0,...,0)= h(1,1,...,1)=(0,0,...,0)

и найдутся два вектора

a= (0,0,1,0,1,...,0,1,1) и b= (1,1,0,1,0,1,...,0,1,0,0),

содержащие четное число единиц такие, что

h(a)=h(b)= (1,1,...,1).

Последовательность (*) не может содержать одновременно векторы $a$ и $b$ , поэтому в этом случае она содержит не более $( n− 1 ) n−1 1+ 2 − 1 = 2$ векторов, так что

k≤ 2n−1− 1.

Предыдущая подтема

Следующая подтема