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

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

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

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

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

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

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

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

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

Верченко 2020

Верченко 2021

Верченко 2022

Верченко 2023

Верченко 2024

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

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

Задача 1#68238

Найдите все восьмизначные числа $A = aa-...a-, 12 8$ $a ∈ {1,2,...,9} i$ такие, что $8⋅A+ a = B, 8$ где $B =b-b-...b 12 8$ , $b = 10 − a . i i$ Решение обоснуйте.

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

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

Подсказка 1

Мы понимаем, как устроены цифры B относительно цифр A. Какое выражение с использованием A и B можно составить, которое не будет зависеть от конкретных цифр в числе А?

Подсказка 2

A+B! А дальше просто решается задачка, нахождением последней цифры числа A)

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

Заметим, что

108−-1- A+ B =1◟1.◝.◜.1 ◞0 = 9 ⋅10. 8

Тогда из условия $8⋅A +a8 = B$ получим

9A +a8 = 11...10. ◟-◝8◜ ◞

Следовательно, по признаку делимости на 9

a8 = 1◟+1-+◝.◜..+-1◞= 8. 8

Разделим число $1◟1.◝8.◜.1 ◞0 − 8$ на $9$ . Получим число $12345678.$

Ответ: 12345678

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

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

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

Задача 2#68239

На координатной плоскости в точках $A(2,4),B(8,8),C(8,0),D (14,1)$ и $E(8,1)$ расположены вышки сотовой связи. Будем говорить, что абонент находится в зоне действия данной вышки, если расстоянии до неё меньше, чем до любой другой вышки. Найдите площадь зоны действия вышки $E.$

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

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

Подсказка 1

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

Подсказка 2

Можно посмотреть на отрезок между этими двумя вышками и просто посмотреть на серединный перпендикуляр к нему: это геометрическое место точек, такое что расстояние от одной и другой вышек одинаковые до них. И если сместиться в одну сторону - то ближе будет одна вышка, в другую - другая) Попробуйте применить серединные перпендикуляры для вышки E и всех остальных!

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

Для начала требуется отобразить точки на координатной плоскости. Так как по условию задачи требуется найти площадь зоны действия вышки $E$ , то соединим отрезками точку $E$ с точками $A,B,C,D$ . Далее проведём через полученные отрезки серединные перпендикуляры и выделим область, полученную пересечением таких перпендикуляров (отмечены на рис. оранжевым цветом). Таким образом, получаем трапецию (см. рисунок ниже), которая демонстрирует область зоны действия вышки $E$ :

$PIC$

Осталось посчитать площадь полученной трапеции. Пересечение срединных перпендикуляров дало нам 4 точки с координатами $F(6,4.5),H (11,0.5),K(4,0.5),G(11,4.5)$ . Площадь данной трапеции

S = 12 ⋅(HK + FG)⋅HG = 12 ⋅(5+ 7)⋅4= 24

Ответ: 24

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

Задача 3#68240

Пароли в системе составляются из букв английского алфавита (26 букв) и цифр. При этом требуется, чтобы в пароле содержались цифра и заглавная буква. Пользователь допускается в систему, если предъявленный им пароль отличается от установленного не более чем в одном символе. Сколько паролей, соответствующих требованиям составления, позволят войти в систему, если для пользователя был установлен пароль Tw38dttf (не совпадающих с установленным паролем)?

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

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

Подсказка 1

Посмотрите, сколько способов есть заменить маленький символ в пароле? А цифру? А заглавную букву? И помните про условие, что обязательно должна быть заглавная буква и цифра)

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

Раскладываем пароль "по слоям": цифра + заглавная + строчная и смотрим, какие ограничения есть по замене в каждой позиции. Цифр две, поэтому одну из них можно заменить произвольно на любой знак из $26+ 26+ 10 − 1= 61$ . Если менять заглавную T, то только на заглавную: $26− 1= 25$ вариантов. Строчные можно на любые, это ещё $5⋅61= 305$ вариантов. Итого $2⋅61+ 25+5 ⋅61 =452$ вариантов.

Ответ: 452

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

Задача 4#68241

Пусть $x =(x ,...,x ) 1 8$ — двоичный вектор длины 8. Обозначим $xd$ — циклический сдвиг вектора $x$ на $d$ позиций вправо. Например, если $x =(1,0,0,0,0,0,0,0),$ то $2 x = (0,0,1,0,0,0,0,0).$ При этом считаем, что $0 x = x.$ Под суммой векторов $x= (x1,...,x4)$ и $y =(y1,...,y4)$ будем понимать вектор

x +y =(x1⊕ y1,x2⊕ y2,x3⊕ y3,x4⊕ y4)

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

1 4 x= v+ v + v

Найдите $d1,...,dn$ такие, что при любом исходном векторе $v$ выполняется равенство

v =xd1 + ⋅⋅⋅+ xdn

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

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

Подсказка 1

Пупупу… Какие-то непонятные векторы, с которыми работать не очень понятно как, да и просто непривычно! На что можно заменить любой вектор, чтобы с этим было удобнее работать?

Подсказка 2

Да, можно заменить любой вектор длины a на многочлен, степени одночленов которого — это числа от 0 до a(включительно)! Подумайте, как можно отобразить операцию циклического сдвига на многочлене?

Подсказка 3

Верно, можно просто умножать все его на одночлены на степень, равную величине сдвига и после этого от каждой степени оставлять только остаток по модулю длины вектора! Тогда какому многочлену соответствует вектор x?

Подсказка 4

Да, это многочлен, который состоит из одночленов со степенями 0, 1, 4. А какое условие должно выполняться, чтобы мы нашли многочлен v?

Подсказка 5

Верно, нужно, чтобы произведение многочлена x на многочлен v равнялось единице(учитывая, что можно заменять степени на остаток по модулю введённой степени многочлена)! Осталось найти такой многочлен v, для которого это выполняется!

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

Заметим, что $xd+8n = xd$ для любого натурального числа $n$ . Вектору $x = (x ,...,x) 1 8$ взаимно однозначно соответствует многочлен

7 8 x(t)= x1+ x2t+ ...+ x7t + x8t

Тогда циклический сдвиг вектора $x$ на $d$ позиций вправо равносилен умножению многочлена $x(t)$ на $td$ и приведению степеней мономов по модулю $8$ .

Вектору $x =v +v1 +v4$ соответствует многочлен $x(t)= 1+ t+ t4$ . Таким образом, нахождение $d ,...,d 1 n$ таких, что $v =xd1 +...+ xdn$ равносильно нахождению многочлена $v(t)= td1 +...+ tdn$ со свойством $x(t)v(t)= 1$ (с учётом приведения степеней мономов по модулю $8$ ). Найти многочлен $v(t)$ можно методом неопределённых коэффициентов, но быстрее из следующего алгоритма:

2 8 2 4 4 8 8 x (t)= 1+t+ t = t, x (t)= t,x (t)= t= 1

Следовательно,

7 3 4 4 2 4 2 6 7 v(t)= x (t)= x(t)x (t)= (1+t+ t)tt = t +t + t

Ответ:

$v =x2+ x6+ x7$

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

Задача 5#68242

Имеется устройство, которое строит последовательность чисел $x,x ,x ,... 0 1 2$ следующим образом: первые два члена $x 0$ и $x 1$ мы задаем самостоятельно, а последующие члены устройство вычисляет так: $x2 =x0+ 13⋅(x1+ k1),x3 = x1+ 13 ⋅(x2+ k2),...$ Здесь $k1,k2,...$ — – некоторая фиксированная ключевая последовательность. При этом все числа $x0,x1,x2,...$ и $k1,k2,...$ являются целыми, лежащими в пределах от 0 до 32 включительно. (Если в процессе вычислений получится число, превосходящее 32, то результат будет заменен его остатком от деления на 33; например, $16+ 13 ⋅2 =9.)$ С помощью этого устройства построили две последовательности $a0,a1,a2,...$ и $b0,b1,b2,...,$ по первым членам $a0 =1,a1 = 3$ и $b0 =1,b1 =12.$ Верно ли, что найдётся ключевая последовательность $k1,k2,...$ и некоторое целое $t,$ большее 0, такие, что выполняются условия:

a) $bt = at,bt+1 =at+1?$

б) $bt = at+1?$

Решение обоснуйте.

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

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

Пункт а), подсказка 1

У вас есть равенство двух членов одной последовательности двум другим. А как можно выразить, например предыдущий член последовательности через два соседних? Попробуйте так прийти к противоречию)

Пункт б), подсказка 1

Мы понимаем, что последовательности устроены одинаковым образом, так еще и ключевая последовательность у них одинаковая. Что можно сделать, чтобы вообще исключить эту последовательность?

Пункт б), подсказка 2

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

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

а) Для всех $t≥1$

at+1 = at− 1+13(at+ kt),at−1 =at+1− 13(at+kt)

Поэтому, если $bt = at,bt+1 =at+1$ , то $bt−1 =at−1,...b1 = a1,b0 = a0$ , что противоречит условию.

б) Удобно перейти к разностям полублоков $zt = bt− at$ (везде далее действия с полублоками (умножение, сложение и вычитание) производятся по модулю $M$ ) и выяснить, может ли 1 появиться в ${z} t$ . Из уравнения шифрования

bt+1 = bt−1+ 13(bt+kt),t≥ 1

a =a + 13(a +k ),t≥ 1 t+1 t−1 t t

получаем после вычитания

zt+1 = zt−1+ 13zt,t≥1,

что последовательность разностей не зависит от ключа $kt$ . По условию $(z0,z1)= (0,9),(z0,z1,M )= 3$ , поэтому все члены последовательности будут делиться на $3$ , и единицы там не будет.

Ответ:

а) нет

б) нет

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

Задача 6#68243

Для входа в университет Криптоландии у каждого студента есть карточка, на которой записана уникальная (у каждого студента своя) последовательность $x1,x2,x3,x4,x5,x6,x7$ из целых чисел от 0 до 5. При входе в университет студент прикладывает карточку к устройству, которое подсчитывает величины $A$ и $B$ по формулам:

A= ((x1 ∗x2)∗ x3)∗x4

B =(x5∘x6)∘x7

Операции $∗$ и $∘$ задаются таблицами (представляющими собой латинские квадраты: у них в каждой строке и каждом столбце числа не повторяются).

$PIC$

Например, $3∗2 =3,$ $2∘ 4=2.$ Студенту разрешат войти, если $A = B.$

Сколько самое большое может быть студентов в таком университете?

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

Подсказка 1

Делать вычисления по этим таблицам точно не хочется, поэтому давайте подумаем. Посмотрите внимательно на строчки и столбцы таблиц...что в них есть примечательного?

Подсказка 2

В каждой строчке и в каждом столбце по одному разу использовано каждое число от 0 до 6) Что это может значить?

Подсказка 3

Например, для любого x от 0 до 6 найдется такой y, что каждая из этих операций с x и y даст результат который мы хотим, причём y будет однозначно задаваться по таблице) Раскрутите эту идею.

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

Если код составлен из чисел от $0$ до $m − 1$ , то для каждого числа

k∈ {0,...,m − 1}

число последовательностей $x1,x2,x3,x4$ , для которых $A = k$ , равно $m3$ , так как при любых заданных $x1,x2,x3$ значение $x4$ определяется в этом случае однозначно.

Аналогично, число последовательностей $x ,x,x 5 6 7$ для которых $B = k$ , равно $m2$ . Тогда общее число последовательностей $x ,x,x ,x,x ,x ,x 1 2 3 4 5 6 7$ , для которых $A= B =k$ , равно $m3m2 = m5$ . Суммируя по $k$ от $0$ до $m − 1$ , получаем ответ: $m6$ .

Ответ:

$66$

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

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