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

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

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

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

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

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

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

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

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

Верченко 2021

Верченко 2022

Верченко 2023

Верченко 2024

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

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

Задача 1#99574

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

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

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

Обозначим $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.6 (см. v-olymp.ru)

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

Расположим числа в порядке возрастания: $− 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.5 (см. v-olymp.ru)

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

Указанную в условии таблицу $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.1 (см. v-olymp.ru)

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

Покажем, что

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.3 (см. v-olymp.ru)

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

Рассмотрим произвольную букву открытого и шифрованного текстов. Для соответствующих им (по таблице) чисел $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.2 (см. v-olymp.ru)

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

Заметим, что для всех $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.

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

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