Тема Межрегиональная им. И. Я. Верченко (криптография)

Уравнения и системы на Верченко

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

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

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

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

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

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

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

Задача 1#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)

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

Подсказка 1

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

Подсказка 2

Мы понимаем, что складывая одинаковые переменные они уничтожаются, поэтому полезно поскладывать уравнения в этой системе, тем самым, упростив её.

Подсказка 4

Сложите первые 3 уравнения, используя полученные знания, сложите 4-ое и 5-ое уравнения.

Подсказка 5

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

Подсказка 6

Давайте перейдём от квадратичной системы к линейной, зафиксировав значения (x7,x8,x9,x10)=(1,1,0,0), и попробуем решить систему попроще.

Подсказка 7

Не забываем, что помимо действий с уравнениями мы можем делать действия внутри уравнения, давайте избавимся от 1, добавив их к обеим частям. Посмотрите на уравнения 2,4 и 1,3, дальше уже можно найти решение и радоваться победе!

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

Для начала, используя $(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$