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

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

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

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

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

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

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

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

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

Верченко 2021

Верченко 2022

Верченко 2023

Верченко 2024

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

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

Задача 1#71011

Дана последовательность $a,b ,a ,b,...,a,b 1 1 2 2 k k$ , состоящая из $0$ и $1.$ Пусть $N$ — количество чисел $i$ от $1$ до $k$ таких, что $a = 0 i$ и $bi = 1.$ Докажите, что число последовательностей указанного вида, для которых $N$ нечетно, находится по формуле $2k−1 k−1 2 − 2 .$

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

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

Применим метод математической индукции по параметру $k$ . При $k= 1$ формула очевидна. Докажем, что если она верна при $k − 1$ , то верна и при $k.$

Искомое число равно числу последовательностей

a1,b1,a2,b2,...,ak−1,bk−1,

(1)

в которых количество $i= 1,2,...k− 1,$ таких, что $ai = 0$ и $bi = 1$ четно (в этом случае пара $(ak,bk)$ может быть только $(0,1))$ плюс количество последовательностей вида (1) в которых количество чисел $i= 1,2,...k− 1,$ таких, что $ai = 0$ и $bi = 1$ нечетно, умноженному на 3 (так как пара $(ak,bk)$ может быть любой из пар $(0,0),(1,0),(1,1)).$ В итоге по предположению индукции нужное число последовательностей будет удовлетворять равенству

( ( )) ( ) 22(k−1)− 22(k−1)−1 − 2k−2 + 3 22(k−1)−1− 2k−2 =22k−1− 2k−1

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

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

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

Задача 2#71012

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

( ) 1 2 3 4 5 6 3 6 4 5 1 2

То есть первый символ ставится на третье место, второй - на шестое и так далее. В своем пароле для почты qwerty Петя переставил буквы по правилу из книжечки, а затем, для большей надежности переставил буквы по этому же правилу еще раз. (Если использовать правило как в примере, то из qwerty после первой перестановки получится tyqerw, а после второй — rwtqey).

a) Какие из нижеследующих комбинаций


yetrqw	eyrtqw	yrwteq	rewqyt	qwtyre	tywreq

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

б) Петя потерял книжечку! Он помнит, что первоначально пароль был qwerty, но правило, по которому были в нём дважды переставлены буквы, не помнит. За какое наименьшее число попыток можно с гарантией подобрать утерянный пароль?

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

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

Приведенное в условии правило перестановки букв, или перестановку, будем обозначать греческой буквой $σ.$ Перестановку $σ$ можно интерпретировать как отображение множества цифр ${1,2,3,4,5,6}$ в себя. Например, тот факт, что первая буква перешла на третье место, можно записать как $σ(1)= 3,$ а также изобразить стрелочкой из 1 в 3:

$PIC$

Видно, что если бы мы перестановку $σ$ применяли многократно, то буквы на 2-й и 6-й позициях постоянно менялись бы местами, а буквы на позициях 1, 3, 4, 5 переставлялись бы по циклу. Поэтому перестановка $σ$ может символически быть записана в виде произведения циклов:

( ) σ = 1 2 3 4 5 6 = (1345)(26)= 4∗2 3 6 4 5 1 2

Запись $4∗ 2$ отражает цикловую структуру перестановки $σ,$ показывая, что в ней один цикл длины 4 и один цикл длины 2.

Посмотрим теперь более детально на то, что произойдет, если по правилу $σ$ переставить буквы еще раз. Так 1 при первом применении правила $σ$ перешла в 3: $σ(1)=3,$ а при повторном применении 3 перешла в 4: $σ(3)= 4.$ Значит, в результате двойной перестановки 1 переходит в 4. Будем это записывать как $σ(σ(1))= 4$ или же $2 σ (1) =4.$ Поэтому правило двойной перестановки букв, представляющее собой квадрат перестановки $σ,$ выглядит так:

$PIC$

Заметим, что после повторной перестановки 2 и 6 вернутся на свои места, то есть цикл $(2,6)$ распадется на два тривиальных цикла $(2)$ и $(6),$ а цикл $(1345)$ превратится в два цикла $(1,4)$ и $(3,5).$ Таким образом, при повторном применении перестановки циклы четной длины $2n$ распадаются на два цикла, длины $n$ каждый. Несложно проверить, что при этом циклы нечетной длины сохраняются. Справедливо утверждение.

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

Рассмотрим первую комбинацию уеqwrt из пункта а). Она получена из qwerty перестановкой $( ) 1 2 3 4 5 6 = (1324561), 3 4 2 5 6 1$ которая представляет собой цикл длины 6. Поскольку циклов четной длины здесь нечетное количество (всего один), то, согласно утверждению, такая комбинация двойной перестановкой букв получиться не могла. Аналогично исследуются и остальные комбинации в пункте а).

Проведем подсчет общего числа перестановок, являющихся полными квадратами. Их цикловые структуры могут быть следующие:

$1∗ 1∗1∗1∗ 1∗1.$ Это перестановка, оставляющая все на своих местах (тождественная перестановка). Она единственна.
$1∗ 5.$ Мы должны выбрать 5 элементов из шести, чтобы составить цикл дины 5. Это можно сделать 6-ю способами. Из пяти элементов цикл длины 5 можно организовать $(5− 1)!$ способами (действительно, организуем цикл из пяти элементов $a1,a2,a3,a4,a5;$ элемент $a1$ может перейти в любой из четырех (т.к. в себя нельзя), элемент $a2$ переходит в один из оставшихся трех и т.д. В итоге получаем $4 ⋅3 ⋅2 ⋅1$ способов). Таким образом, здесь $6⋅4!= 144$ перестановок.
$2∗ 2∗1∗1.$ Выбрать два элемента из шести для первого цикла длины 2 можно $2 C6$ способами. Для второго цикла длины 2 есть $2 C4$ способа. Итого $2 2 C 6 ⋅C4 = 90.$ От порядка следования циклов результат не зависит, поэтому 90 еще следует разделить на два. Всего 45 перестановок с такой структурой.
$3∗ 3.$ Здесь мы 6 элементов десятью способами $( ) 12C36 = 10$ разбиваем на две тройки и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.
$3∗ 1∗1∗1.$ Здесь мы двадцатью способами $( ) C36 = 20$ выбираем тройку и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.

В итоге, имеется $1+144+ 45+40+ 40= 270$ перестановок длины 6, представляющих собой полный квадрат.

Ответ:

a) yetrqw, tywreq;

б) 270

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

Задача 3#71013

На вход устройства подается лента с записанными на ней нулями и единицами:

$PIC$

За один такт устройство считывает с ленты с позиций $μ1,μ2,μ3$ (на первом такте $μ1 = 1$ ) три значения $x,y,z$ . Если $x+ y+z ≥2,$ то устройство на новой ленте печатает 1 , иначе — 0 . Затем устройство сдвигается на одну позицию вправо, и процедура повторяется. Найдите разности $d1 = μ2− μ1$ и $d2 = μ3− μ2,$ если известно, что $d1 +d2 ≤ 10,$ а на новой ленте было напечатано следующее: $0001000010111111000111010111011010101001 ...$ (для примера на рисунке изображен случай $d1 = 3,d2 =5).$

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

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

Число возможных вариантов $d 1$ и $d :10+ 9+ ⋅⋅⋅+1 =55 2$ , можно для каждого варианта проверять, что соответствие входных и выходных символов, а можно предложить более быстрый способ, заключающийся в нахождении сначала $d1$ (максимум 10 вариантов), а затем $d2$ . Для этого достаточно заметить следующее.

Если рассмотреть систему, соответствующую выходным знакам на расстоянии $d1$ вида $1...1$ в произвольном такте работы $μ1 :$

xμ1 + xμ1+d1 − xμ1+d1+d2 ≥ 1,

xμ1+d1 +xμ1+2d1 − xμ1+2d1+d2 ≥ 1,

то если $x = 0 μ1+d1$ , то $x = 1,x = 1. μ1 μ1+2d1$

Это позволяет отбраковать опробуемый вариант $d . 1$ Устанавливаем, что $d = 2. 1$

Аналогично, если рассмотреть систему, соответствующую выходным знакам на расстоянии $d2$ вида $0...1$ в произвольном такте работы $μ1 :$

xμ1 + xμ1+d1 − xμ1+d1+d2 ≤ 0,

xμ1+d2 +xμ1+d1+d2 − xμ1+d1+2d2 ≥1,

тогда если $xμ1+d1+d2 = 0,$ то $xμ1+d1 = 0,xμ1+d1+2d2 = 0.$

Это позволяет отбраковать опробуемый вариант $d 2$ (с учётом найденного ранее $d =2). 1$ Находим $d = 6. 2$

Ответ:

$d = 2,d =6 1 2$

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

Задача 4#71370

Знаками открытого и шифрованного текстов являются пары целых от 0 до 31. Для зашифрования используется секретный ключ $k$ (целое число от 0 до 31), заданная таблично функция $h,$ а также функция $g(c,d),$ которая паре целых чисел $(c,d)$ ставит в соответствие пару $(d,c+ h(d+k))$ (причем если число $d +k$ или $d+ h(d+ k)$ превышает 31 , то их заменяют остатком от деления на 32 $).$ Знак шифрованного текста $(b1,b2)$ получается из знака открытого текста $(a1,a2)$ путем 128-кратного применения функции $g :$

(b1,b2)= g128(a1,a2)= g(...g(g(a1,a2)))

Известно, что знак открытого текста $(21,0)$ преобразовался в знак зашифрованного текста $(15,25),$ знак $(7,3)$ преобразовался в $(29,5),(0,17)$ — в $(25,4)$ и, наконец, $(5,21)−$ в $(22,9).$ Найдите ключ $k.$


$i$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

$h(i)$	9	1	30	4	24	12	8	23	18	7	16	15	21	26	10	17	19	22	13	28	14


21	22	23	24	25	26	27	28	29	30	31

11	2	29	3	6	27	0	5	25	31	20

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

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

Необходимо заметить, что из равенств

128 (b1,b2)= g (a1,a2)

( ′ ′) 128( ′ ′) b1,b2 = g a1,a2

(a′,a′)= g(a,a ) 1 2 1 2

следует равенство

(b′,b′)= g(b,b ) 1 2 1 2

Необходимым условием выполнения равенств $(a′1,a′2)= g(a1,a2),(b′1,b′2)= g(b1,b2)$ являются равенства $a′1 = a2,b′1 = b2.$ Среди приведенных в задаче пар знаков открытого и шифрованного текстов есть знаки, удовлетворяющие этому условию: одна пара $(21,0),(0,17)$ и вторая пара $(29,5),(5,21).$ То есть

(15,25)=g128(21,0)

(25,4)= g128(0,17)

Из условия задачи возможность найти ключ — воспользоваться равенствами

(0,17)= g(21,0), (25,4)= g(15,25)

Убедимся, что при этих условиях оба равенства дают одинаковое значение ключа $k.$

$PIC$

Получаем, что $k= 19.$

Ответ: 19

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

Задача 5#71371

В Криптоландии используется алфавит, состоящий из четырёх латинских букв $a,b,c,d.$ Любая последовательность букв алфавита будет словом криптоландского языка при выполнении единственного ограничения: если в последовательности есть хоть одна буква " $a$ то тогда в ней обязательно должны встретиться две буквы " $a$ "подряд.

Например, последовательности $baacda,aabb,ddd$ являются словами, а последовательности $bcadda,abba$ — не являются. Найдите число слов длины 8 в криптоландском языке.

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

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

Множество всех последовательностей длины $8$ состоит из $48$ последовательностей. Это множество разбивается на три непересекающихся между собой подмножества:

1.: Последовательностей, не содержащих $a.$
2.: Последовательностей, содержащих $a,$ но не содержащих двух подряд идущих таких букв.
3.: Последовательностей, содержащих $a$ , в которых встречаются две подряд идущие такие буквы.

Чтобы решить задачу, нужно найти число последовательностей во втором подмножестве и вычесть его из числа $48.$

В свою очередь, множество последовательностей второго типа можно разбить на непересекающиеся подмножества, в которые входят последовательности, содержащие $1,2,3,4$ букв " $a$ ".

Поскольку число последовательностей длины $8$ , содержащих ровно $t$ отдельно стоящих букв $a$ , равно $Ct8+1−t(4− 1)8−t,$ то общее число последовательностей второго типа будет равно

4∑ t 8−t C9−t3 =38070 t=1

В итоге получаем

48 − 38070 =27466

Ответ: 27466

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

Задача 6#75003

Подписью битового сообщения $(a,...,a ) 1 5$ является любой битовый набор $(x ,...,x ), 1 10$ при котором

$pict$

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

Найдите какую-нибудь подпись для сообщения $(0,1,0,0,0).$

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

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

Для начала, используя $(a,a ,a ,a,a )= (0,1,0,0,0), 1 2 3 4 5$ найдем $b,b,b,b ,b . 1 2 3 4 5$ Для этого решим систему:

( b ⊕ b ⊕b = 0 ||||| 3 4 5 |{ b2⊕ b4⊕b5 = 1 ||| b2⊕ b3⊕b5 = 0 |||( b1⊕ b2⊕b3 = 0 b1⊕ b3⊕b5 = 0

Сложив первые три уравнения и преобразовав их, получаем $b = 1. 5$ Подставим это значение в нашу систему:

(| b ⊕ b =1 ||||| b3⊕ b4=0 { b2⊕ b4=1 |||| b2⊕ b3⊕b = 0 ||( 1 2 3 b1⊕ b3 =1

Сложим четвертое и пятое уравнения и получим, что $b2 = 1.$ Тогда из второго уравнения следует, что $b4 = 1,$ а из третьего следует, что $b3 = 0.$ Тогда из пятого получаем $b1 =1.$

Итак, $(b,b ,b ,b,b)= (1,1,0,1,1). 1 2 3 4 5$ Теперь нужно найти набор какой-нибудь $(x ,x,x ,x ,x ,x ,x,x ,x,x ). 1 2 3 4 5 6 7 8 9 10$

Для этого найдем любое решение системы:

(| x x ⊕ x x ⊕ x x ⊕x x ⊕ xx ⊕x x ⊕ xx ⊕ x x = 1 ||||| x1x9⊕ x21x0⊕x 3x 8⊕x4x9⊕ x5x9 ⊕ 6x 8x ⊕7x8x ⊕9x 10x = 1 { x1x8⊕ x29x ⊕ 3x 1x0⊕x4x8⊕ x5x10⊕x 6x10⊕ xx7⊕8x 8x 9⊕x = 0 |||| 1 9 210 3 8 4 7 58 6 8 7 8 8 9 10 ||( x1x7⊕ x2x10⊕ x3x10⊕ x4x7⊕x5x7⊕ x6x10⊕ x7x10⊕ x9x10 =1 x1x8⊕ x2x7 ⊕x3x7⊕ x4x9⊕ x5x9⊕x6x8⊕ x7x8 ⊕x8x10⊕x9 = 1

Решать квадратичную систему с десятью переменными сложно, поэтому попробуем ее как-нибудь упростить. Видно, что если убрать переменные $x ,x ,x ,x , 7 8 9 10$ то получится линейная система. Тогда зафиксируем значения этих переменных так, чтобы в новой системе не было противоречий, например, так: $(x7,x8,x9,x10)= (1,1,0,0).$ Тогда все слагаемые, в которых есть $x9$ или $x10$ пропадут.

После подстановки этих значений в систему получаем:

( ||||| x3⊕ x6 ⊕1= 1 |{ x1⊕ x4 ⊕1= 1 ||| x3⊕ x4 ⊕x5⊕ x6⊕ 1= 0 |||( x1⊕ x4 ⊕x5 = 1 x1⊕ x2 ⊕x3⊕ x6⊕ 1= 1

Далее во всех уравнениях, где есть слагаемое 1 в левой части, прибавим 1 к обеим частям. Тогда справа константа изменится на противоположную, а слева останутся только переменные.

( ||||| x3⊕ x6 = 0 |{ x1⊕ x4 = 0 ||| x3⊕ x4⊕ x5 ⊕x6 = 1 |||( x1⊕ x4⊕ x5 =1 x1⊕ x2⊕ x3 ⊕x6 = 0

Из второго и четвертого уравнений следует, что $x = 1. 5$ Тогда из первого и третьего получаем, что $x = 0. 4$ Теперь подставим эти значения в систему:

( x ⊕ x = 0 ||||| 3 6 |{ x1 = 0 ||| x3⊕ x6 = 0 |||( x1 = 0 x1⊕ x2⊕ x3 ⊕x6 = 0

Итак, $x1 = 0.$ Тогда из первого и пятого получаем, что и $x2 =0.$ Осталось выбрать какие-нибудь значения для $x3x6,$ так как их система однозначно не задает. Пусть $x = x = 0. 3 6$

Получаем следующую подпись: $(0,0,0,0,1,0,1,1,0,0).$

Ответ:

$(0,0,0,0,1,0,1,1,0,0)$

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

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