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

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

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

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

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

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

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

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

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

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

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

Задача 1#90274Максимум баллов за задание: 7

Катя и Юра играют в следующую игру. Имеется пустая таблица из одной строки, состоящая из $k= 20232$ пустых ячеек: ( $a ,...,a 1 k$ ), которые игроки заполняют числами от 0 до 2022. Первым ходит Юра, который выбирает число $t$ такое, что $1≤t≤ k− 1$ и заполняет $t$ ячеек. Второй ходит Катя, которая заполняет оставшиеся ячейки. Победитель определяется по следующему правилу: если в результате получается «счастливая» комбинация чисел - полностью заполненная таблица, в которой числа можно разбить на две непересекающиеся группы, суммы чисел в которых одинаковы, то выигрывает Катя, в противном случае выигрывает Юра. Например, комбинация ( $7,5,3,4,6$ ) не является «счастливой», так как в ней присутствует нечетное число нечетных чисел. С другой стороны, комбинация $(4,5,1,6,8)$ является «счастливой», так как $4 +8= 5+ 1+ 6$ . У кого из игроков имеется выигрышная стратегия? Ответ обосновать.

Источники: Верченко - 2024, 11.1 (см. ikb.mtuci.ru)

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

Подсказка 1.

Сразу поймём, что нет никакого смысла рассматривать случаи, когда первый игрок заполняет ячеек меньше, чем k-1. Ведь Юра может оставить Кате всего лишь одну ячейку. Так что будем считать, что если он заполнил меньше k-1 ячейки, то Катя заполняет оставшиеся ячейки, кроме последней, нулями.

Подсказка 2.

Теперь если мы докажем, что числа на k-1 ячейках можно разбить на такие 2 группы, что суммы чисел в них будут отличаться не менее чем на 2022, то Катя сможет победить, поставив в последнюю ячейку число, уравнивающее суммы этих групп. Сейчас работать с числами не очень удобно. Попробуйте упорядочить их и разбить на подходящие группы.

Подсказка 3.

Если мы упорядочим числа и распределим в группы через один, то сумма в группах будет отличаться не более чем на 2022. Победа!

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

Очевидно, что достаточно рассмотреть случай, когда игрок, делающий первый ход, заполняет максимально возможное число ячеек, равное $k− 1$ . Расположим эти $k− 1$ число в порядке не убывания: $ai1 ≤ai2 ≤ ⋅⋅⋅≤ aik−1$ . Здесь в индексах указаны номера позиций, на которых стоят эти числа в таблице. Образуем два множества позиций, которые заполнены: ${i1,i3,...}$ и ${i2,i4,...}$ , беря указанные числа через одно. Тогда суммы чисел на этих позициях могут отличаться друг от друга не более, чем на 2022. Поэтому оставшуюся незаполненной позицию можно заполнить числом от 0 до 2022 так, чтобы получилась «счастливая» комбинация.

Ответ: Катя

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

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

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

Задача 2#90275Максимум баллов за задание: 7

Каждый из трех владельцев криптокошельков имеет на своем счету по 10 криптокойнов. Каждый из двух дней ими совершаются по две транзакции: по переводу части криптокойнов со своего криптокошелька на криптокошелек другого владельца и по возврату оставшихся криптокойнов обратно на свой кошелек. У каждого имеется свой секретный ключ $S ∈{1,2,...,28}$ . При совершении транзакции указываются три числа $(X,a,b)$ , где $X$ - число переводимых криптокойнов, $(a,b)$ - электронная подпись перевода.

$PIC$

Электронная подпись находится по правилу: выбираем произвольное $k ∈{1,2,...,28}$ , затем находим $a= r29(2k) ,b= r28(Xa +Sk)$ , где $rN(M )−$ остаток от деления числа $M$ на $N$ . На рисунке указаны совершенные транзакции (пронумерованы числами в кружках) за два дня. Сколько будет криптокойнов у каждого владельца криптокошелька по окончании двух дней?

Источники: Верченко - 2024, 11.2 (см. ikb.mtuci.ru)

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

Подсказка 1:

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

Подсказка 2:

Запишем уравнения из криптокошелька владельца 1 на 1 день, владельца 1 на 2 день, владельца 2 на 2 день, владельца 3 на 2 день. Какие ещё уравнения можно написать?

Подсказка 3:

Мы знаем, что транзакции 1 и 8 осуществлены одним и тем же владельцем, и в электронной подписи одинаковое. Можем получить из этого уравнение. Для этого вспомните сравнение по модулю. Из каких транзакций можно получить ещё уравнение?

Подсказка 4:

Транзакции 5 и 12! Теперь из полученных уравнений можем найти Y₁ и Y₅. Мы можем найти количество криптокойнов у первого владельца. Какие ещё уравнения можно получить из условия, чтобы решить задачу?

Подсказка 5:

Посмотрим на транзакции 9 и 10. Для них использовались одинаковые k, но с разными знаками. Какие уравнения можно получить из этих транзакций?

Подсказка 6:

Получаем, что Y₄ = 1. Сумма криптокойнов была равна 30 и останется такой же, 30.

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

Сначала по рисунку выпишем очевидные соотношения:

X1+ X2 = 10 (1)

Y1+ Y2 = X1+ 3 (2)

8+ Y = X + 5 (3) 4 2

Y5+ Y6 = 12 (4)

Необходимо найти:

Σ1 = Y1+ 8+Y5,Σ2 = Y4,Σ3 = Y2 +Y6

Далее, заметим, что транзакции №1 и №8 осуществлены одним и тем же владельцем владельцем 1. То есть использовался один и тот же секретный ключ $S1$ , при этом использовалось одно и то же значение $k$ в подписи, поэтому

9≡ (18X1 +S1k) (mod28)

1 ≡(18Y2 +S1k) (mod28)

Отсюда получим

8≡ 36≡ (18(X1− Y2)) (mod28)

Следовательно, $X − Y = 2 1 2$ . С учетом (2) имеем: $Y = X − Y + 3= 5 1 1 2$ .

Аналогичное свойство замечаем у транзакций №5 и №12:

18≡ (27⋅3+ S3k) (mod28)

20≡ (27Y + Sk) (mod28) 6 3

Отсюда получим

−2 =54≡ (27 (3− Y6)) (mod28)

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

3− Y6 = 2,Y6 = 1

С учетом (4) имеем: $Y5 = 11$ и уже находится $Σ1 =5 +8+ 11= 24$ . Теперь обратим внимание на транзакции №9 и №10, осуществленные владельцем 2 , для которых, как нетрудно заметить, использовались одинаковые $k$ , но с разными знаками, т.к. $(2⋅15) ≡1 (mod29)$ .

Поэтому:

11≡ (2 ⋅8 +S2k)(mod28)

20≡ (15Y4− S2k)(mod28)

Отсюда получим:

15Y4 ≡ 31− 16 ≡15(mod28),Y4 = 1= Σ2

Т.к. исходная сумма криптокойнов была равна 30 , то

Σ3 =30− Σ1− Σ2 = 5

Ответ:

$(24,1,5)$

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

Задача 3#90278Максимум баллов за задание: 7

a) перестановка $f$ чисел ${0,1,...,6}$ задана таблицей:


$x$	0	1	2	3	4	5	6

$f(x)$	3	2	4	0	5	6	1

Например, $f(2)= 4$ . Найдите две различные перестановки $g$ и $h$ такие, что для всех $x ∈{0,1,...,6}$ выполняется

f(x)≡ (g(x)+h(x))(mod7)

b) перестановка $f$ задана на чётном количестве чисел ${0,1,...,2n− 1}$ таблицей:


$x$	0	1	2	..	$2n− 2$	$2n− 1$

$f(x)$	$i0$	$i1$	$i2$	..	$i2n−2$	$i2n−1$

Здесь $(i0,i1,...,i2n−1)$ - перестановка чисел ${0,1,...,2n− 1}$ .

Докажите, что не существует перестановок $g$ и $h$ таких, что для всех $x∈ {0,1,...,2n− 1}$ выполняется $f(x)≡(g(x)+ h(x))(mod (2n))?$

Источники: Верченко - 2024, 11.3 (см. ikb.mtuci.ru)

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

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

Просто пытаться найти перестановки функции перебором очень тяжело. Однако можно заметить, что если мы домножим каждое значение перестановки f(x) на число взаимно простое с 7 и возьмём от получившихся чисел остатки при делении на 7, то мы получим перестановку. Попробуйте найти такие перестановки, подходящие под условие.

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

Нужно взять два числа, взаимно простых с 7, чтобы их сумма имела остаток 1 при делении на 7. Тогда, умножив f(x) на эти числа, мы получим перестановки g(x) и h(x). Они подходят под условие.

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

Мы почти ничего не знаем про расположение элементов перестановки. Однако точно знаем, чему равна сумма значений перестановки. Ведь её значения - 0,1,...,2n-1. То же самое можно сказать про перестановки g(x) и h(x). Попробуйте доказать требуемое от противного, записав условие через сумму перестановки.

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

Суммы значений всех трёх перестановок равны (2n+1)*n. Тогда, используя условие пункта b, получаем, что (2n+1)*n = (2n+1)*n+(2n+1)*n(mod 2n). Попробуйте получить противоречие, рассматривая по модулю 2n.

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

а) Так как $НОД (2,7) =НО Д(6,7)=1,$ то $g(x)≡ 2f(x)(mod7)$ и $h(x)≡ 6f(x)(mod7)$ являются перестановками. Но тогда, например, $g(x)=2f(x),h(x)=6f(x)$ и выполняется

g(x)+ h(x)=2f(x)+6f(x)≡f(x)(mod7)

b) Из условия получим

2∑n− 1 2n∑−1 f(x)= x = (2n+ 1)n =n(mod(2n)) i=0 i=0

С другой стороны, если указанное условии пункта b) представление существует, то

2∑n−1 2∑n− 1 2n∑−1 f(x)= g(x)+ h(x)=2(2n+ 1)n≡ 0(mod(2n)), i=0 i=0 i=0

а это доказывает невозможность указанного представления.

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

Задача 4#90279Максимум баллов за задание: 7

В криптосистеме RSA (знания алгоритма шифрования не требуется для решения задачи) элементы надёжности определяются несколькими параметрами. В частности, выбором числа $N =p⋅q$ , где $p,q$ — различные нечётные простые числа, и значением

φ(N)= (p− 1)⋅(q− 1)

Известна следующая теорема (малая теорема Ферма): если $p$ — простое число, $a$ — целое число, не делящееся на $p$ , то

p−1 a ≡1(modp)

Используя это:

a) докажите, что

φ(N2)+1 x ≡x(modN )

для всех $x ∈{1,2,...,N − 1}$ .

b) найдите $p$ и $q$ , если известно, что

N =42494861 и x21240913 ≡x(modN )

для всех $x ∈{1,2,...,N − 1}.$

Источники: Верченко - 2024, 11.4 (см. ikb.mtuci.ru)

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

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

Возведите сравнение aᵖ⁻¹ ≡ 1 (mod p) в нужные степени, и, совместив два сравнения, получите искомое.

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

Мы знаем сравнение из пункта a, тогда хочется, чтобы 21240913 было равно φ(N) / 2 + 1. Давайте предположим это и найдём такие p и q, нужно только решить систему от двух переменных.

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

a) из условия задачи и равенства $ap−1 ≡1 (modp)$ следует

k(p−1)+1 a ≡ a (modp)

для любого натурального $k$ . Тогда при $k = q−1- 2$ получим

φ(N2-)+1 a ≡a (modp)

Аналогично

aφ(N2-)+1 ≡a (modq)

Так как $p,q$ - простые числа, то из этих полученных выше равенств следует

aφ(N2)+1 ≡ a (modN )

b) из доказанного в пункте (а) получим $φ(2N)+ 1= 21240913,$ а отсюда систему

{ p⋅q = 42494861 (p− 1)⋅(q− 1) =(21240913− 1)⋅2

Решением в нечётных простых числах является неупорядоченная пара $(6469,6569).$

Ответ:

b) $(6469,6569)$

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

Задача 5#90280Максимум баллов за задание: 7

Четыре компьютера, расположенные в вершинах квадрата $ABCD$ , соединены прямолинейными отрезками проводов с сервером, который находится в точке пересечения диагоналей $O$ . Сторона квадрата равна 2 м. Несложно заметить, что для такого подключения потребуется $√- 4 2$ метров провода. Чтобы уменьшить длину проводов, вам разрешается передвинуть сервер из точки $O$ в любую другую точку $O1$ , а также компьютер из точки $A$ в любую другую точку $A1$ так, чтобы новая суммарная длина проводов $S =O1A1 +O1B + O1C+ O1D$ была как можно меньше. Разрешается компьютеры и сервер размещать в одной точке (например, точка $A1$ может совпасть с точкой $B$ ). Компьютеры в вершинах $B,C,D$ двигать нельзя. Чему равно минимальное значение $S$ ?

Источники: Верченко - 2024, 11.5 (см. ikb.mtuci.ru)

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

Подсказка 1

Что можно сказать о А₁ и O₁? Они совпадают, если мы ищем минимальное значение S(почему?). Тогда пусть А₁ = O₁ = K. Что можно сказать о расположении K? Где она должна лежать?

Подсказка 2

Симметричность расположения точек B и D, подсказывает, что сумма DK + KB наименьшая, когда K лежит на диагонали AC. Предположим обратное. Тогда нам нужна какая-то точка на диагонали, чтобы показать, что для неё S меньше. Какую бы выбрать?

Подсказка 3

Конечно, основание перпендикуляра K на AC, пусть это точка K₁. Если CK > CK₁ (длина наклонной и проекции), то что делать с DK + KB непонятно. Обычно на помощь всегда приходит неравенство треугольника. Но треугольника с необходимыми сторонами нет, значит, его нужно построить!

Подсказка 4

Теперь, когда доказано, что K лежит на диагонали, достаточно обозначит один из отрезков ОK или KC за x. Тогда S превратиться в некоторую функцию от х, у которой нужно будет найти минимум на отрезке [0; √2].

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

Заметим, что точки $A 1$ и $O 1$ совпадают.

Действительно, пусть минимум достигается на конфигурации, где это не так. Но тогда, сдвинув точку $A1$ в точку $O1$ , мы длину проводов уменьшим. Таким образом, компьютер $A1$ и сервер $O1$ должны оказаться в некоторой точке $K (K =A1 =O1).$

Покажем, что $K$ лежит на диагонали $AC$ .

Предположим обратное. Пусть $K1$ — основание перпендикуляра, опущенного из точки $K$ на прямую $AC$ . Покажем, что сумма расстояний от точки $K1$ до вершин $B,C,D$ , которую обозначим $SK1 = K1B + K1C+ K1D$ , меньше аналогичной суммы $SK = KB +KC +KD$ . Длина проекции меньше длины наклонной, поэтому $K1C < KC$ . Чтобы доказать, что

K1D + K1B <KD +KB (1)

отразим отрезок $BD$ относительно прямой $KK1$ (при этом точка $B$ перейдет в точку $B1$ , точка $D$ — в точку $D1$ ).

$PIC$

Точки $B,K1,D1$ окажутся на одной прямой. Тогда $K1D + K1B = K1D1+ K1B =D1B$ , и при этом $KD +KB = KD1 + KB > D1B$ . Неравенство (1) доказано. Следовательно, $SK1 < SK$ , а значит, искомая точка $K$ должна лежать на диагонали.

Пусть $OK =x$ . Рассмотрим функцию

S(x)= KC + KB +KD =2∘x2-+-2+√2-− x

$PIC$

′ ∘ -2--- S(x)= 2x∕ x + 2− 1

На отрезке $[0;√2]$ функция $S(x)$ принимает минимальное значение в точке $x0 =∘2-∕3,$ а само минимальное значение равно

S(x )= 2∘2-∕3+2-+√2-− ∘2-∕3= √6+ √2 0

Ответ:

$√6-+√2$

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

Задача 6#90281Максимум баллов за задание: 7

Вася хочет заполнить квадратную таблицу (криптографическую мозаику) размера $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$ ?

Источники: Верченко - 2024, 11.6 (см. ikb.mtuci.ru)

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

Подсказка 1

Видите вопрос "сможет ли...?" и сразу руки чешутся как-нибудь доказать, что не получится? :) Давайте сначала успокоимся и попробуем посмотреть на то, что от нас просят. В табличке должны получиться различные остатки по модулю 17, причем эти aᵢ очень подозрительно выглядят... 1 и 16 в сумме дают 17, 3 и 14 тоже.... Что можно сказать?

Подсказка 2

Да, в одном столбце получаются числа bᵢ + 1, bᵢ + 4, bᵢ - 4, bᵢ - 1 (mod 17). Полученная симметрия так и бросается в глаза, правда? Вот бы можно было выбрать какое-нибудь b и наглядно видеть остатки от чисел, которые оно образует... Вам же наверняка тоже не хочется долго перебирать и считать аᵢ

Подсказка 3

А что если остатки по модулю 17 изобразить по кругу? И правда, если мы выберем какое-нибудь число b из круга, то число b+r пойдет по кругу на r шагов от него в сторону увеличения, а b-r, на те же r шагов в сторону уменьшения. Получается, если выбрать какое-нибудь число b, то оно вычеркивает два числа рядом с собой и два числа на расстоянии 4. Получится ли у нас подобрать еще 3 числа так, чтобы вычеркнутые числа не пересекались?

Подсказка 4

Да, получится. Если это вызывает затруднения, заметьте, что само число b в табличку не входит, поэтому оно может быть среди вычеркнутых. Если вы пойдете по кругу от самого первого выбранного вами числа и выберете числа на расстоянии 1, 7 и 11, то у вас точно никакие вычеркнутые числа не пересекутся :)

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

Заметим, что

bi+16= bi+1(mod17)

bi+13= bi− 4(mod17)

Представим остатки полученных $a(ij)$ от $bi$ в виде круга остатков. Числа получаются от $bi$ смещением на $1$ или $4$ шага по часовой или против часовой стрелки в зависимости от знака.

Крестиком выделены полученные числа a(j)то есть столбец в табл&#x0438 i i

$PIC$

Заметим, что важен лишь набор $b1,b2,b3,b4$ , а не их порядок, тогда без ограничения общности выберем пару $b1$ , $b2$ — одно из чисел $(j) a1$ или такое число, которого нет в таблицы. Докажем, что $b2$ тогда обязательно соседняя с $b1$ .

Предположим противное, то есть что ни одна пара $bi$ , $bj$ не являются соседями (так как иначе можем взять их в качестве $b1$ , $b2$ ).

$1$ случай ( $b2 = b1+4(mod 17)$ ): возьмём $b1 =6$ (если все различные числа сдвинуть на одинаковое число по модулю $17$ , то они останутся одинаковыми, а значит мы можем взять $b1 =6$ ), в таблицу уже попали числа: $1,2,3,5,6,7,10,15$ , тогда “запрещённые” позиции — $0,..,11,14,15,16$ (они получены путём прибавления и вычитания $1$ , $4$ по модулю $17$ к полученным клеткам в таблице), а значит, $b3,b4$ — $12,13$ , но тогда они соседи — противоречие.

$2$ случай ( $b2 = b1− 4(mod 17)$ ): переименуем $b1$ , $b2$ в $b2$ , $b1$ и получится случай 1.

$PIC$

$3$ случай ( $b2 = 6$ аналогично, без ограничения общности, не входит в таблицу): Все остальные числа входят, так как с каждой $bi$ в таблицу добавляются по 4 числа. Рассмотрим число $3$ , у нас уже "запрещены"числа $2,5,7,10$ для $b1$ , иначе $b2$ входит в таблицу и $1,3,4,6,8,9,11,15$ , иначе в таблице есть повторяющиеся числа, тогда $b1+ 1!= 3(mod 17)(b1 = 2),b1− 1!= 3(mod 17)(b1 =4),b1− 4!=3(mod 17)(b1 = 7)$ , получается, что $b2+ 4= 3(mod 17)$ , т.е. $b2 = 16)$ .

Посмотрим на “запрещённые” числа для $b3$ : $0,..,12,15,16$ , но $13,14$ снова соседние.

Мы получили, что обязательно должны быть 2 соседних числа. С одной стороны, зачёркнутые ячейки на расстоянии $4$ от $b1$ и $b2$ образуют место для $b 3$ и $b 4$ (поскольку есть две свободные ячейки вокруг двух зачеркнутых чисел). С другой стороны, при выборе двух $b$ , набор двух оставшихся определяется однозначно, поэтому итого вариантов выбора комбинации столько же, сколько и выбор двух подряд идущих чисел в круге, т.е. $17$ .

Один из возмож ных случаев:

$PIC$

Ответ:

$0 1 7 11, 1 2 8 12, 2 3 9 13, 3 4 10 14, 4 5 11 15, 5 6 12 16, 0 6 7 13, 1 7 8 14, 2 8 9 15, 3 9 10 16, 0 4 10 11, 1 5 11 12, 2 6 12 13, 3 7 13 14, 4 8 14 15, 5 9 15 16, 0 6 10 16$

Курсы

Всё необходимое для достижения цели

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

Задача 7#137036Максимум баллов за задание: 7

Найдите пять простых чисел, образующих арифметическую прогрессию с разностью 12. Ответ обоснуйте.

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

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

Подсказка 1

Попробуйте составить несколько арифметических прогрессий с разными первыми членами. Что можно заметить?

Подсказка 2

Остатки при делении на 2, 3, 4 у чисел одной прогрессии будут одинаковы, ведь 12 делится на 2, 3 и 4. Остатки на какое число следует рассмотреть?

Подсказка 3

Остатки при делении на 5 у всех пяти чисел прогрессии будут отличаться между собой, но ведь есть лишь 5 различных остатков при делении на 5.

Подсказка 4

Следовательно, одно из чисел гарантированно делится на 5. Все числа прогрессии простые, тогда число 5 в ней есть. Осталось найти остальные числа прогрессии, зная разность.

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

Посмотрим на остатки по модулю $5,$ заметим что все остатки различны, поэтому из пяти членов арифметической прогрессии обязательно встретится число кратное $5,$ так как оно простое, то оно равно $5,$ поэтому если такая прогрессия существует, то она начинается с $5.$ И вправду в ряду $5,$ $17,$ $29,$ $41,$ $53$ все числа просты.

Ответ: 5; 17; 29; 41; 53

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

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