Темы заданий

$(n,n)$-схема и булевы формулы
- A1 (0.30): Восстановить секрет по простейшей $(n,n)$-схеме.
- A2 (0.45): Разделить длинный секрет
- A3 (0.70): Разделить секрет в соответствии с булевой формулой
Схема Блэкли
- B1 (0.30): Разделить секрет по схеме Блэкли.
- B2 (0.45): Схема Блэкли реализована по википедии. Надо «взломать».
- B3 (0.70): Один участник из пяти испортил свой секрет и называет не ту плоскость.
Схема Шамира
- C1 (0.30): Восстановить секрет по схеме Шамира
- C2 (0.45): Выяснить четность секрета
- C3 (0.70): Изменить своё значение так, чтобы повлиять на секрет определённым образом

Чтобы раскрыть вариант, кликните по заголовку.

Вариант 1

Задание A1¹ (0.3)

Секрет разделён при помощи простейшей $(n,n)$-схемы, $n = 4$. Необходимо его восстановить. В качестве поля используется кольцо многочленов степени не выше $2$ над кольцом $\ZZ_{43}$

Дано:

$ s = 34 x^{2} + 19 x + 4 $
$ v_{1} = 37 x^{2} + 4 x + 39 $
$ v_{2} = 17 x^{2} + 35 x + 3 $
$ v_{4} = 28 x^{2} + 13 x + 29 $

Найти: $ v_{3} $

Ответ: $ v_{3} = 38 x^{2} + 10 x + 19 $

Задание A2¹ (0.45)

Вам дана ASCII строка: maths. Необходимо её при помощи простейшей $(n,n)$ схемы разделить между $n=4$ участниками.

Использовать для вычислений модуль более $10000$ не допускается.

Выпишите какой набор чисел получит каждый из участников.

Авторское решение: Переведём строку в байты по таблице ASCII: $\left[109, 97, 116, 104, 115\right]$.

Теперь разделим: $\left(\begin{array}{rrrrr} 53 & 242 & 238 & 140 & 27 \\ 24 & 219 & 218 & 14 & 218 \\ 2 & 196 & 65 & 3 & 21 \\ 30 & 208 & 107 & 203 & 105 \end{array}\right)$

Каждый участник получает одну из строк таблицы, и сумма элементов в каждом столбце даёт соответсвующий символ строки.

Задание A3¹ (0.7)

Есть четыре участника: $a, b, c, d$. Вам дана булева формула $(((d\vee a)\wedge b)\wedge ((c\vee b)\wedge d))\vee (b\vee c)$. Ваша задача — разделить секрет $s = 14$ при помощи простейшей $(n, n)$-схемы над полем $\ZZ_{47}$ таким образом, чтобы его могли восстановить тогда и только тогда, когда эта функция, будучи применена к присутствующим участникам, принимает значение истины.

Необходимо описать какие числа получит каждый из участников и описать как происходит восстановление секрета.

Возможный ответ:

Секретная информация:

Участник a знает: $s_4 = 20$
Участник b знает: $s_1 = 2$, $s_6 = 32$, $s_7 = 25$
Участник c знает: $s_5 = 17$, $s_8 = 34$
Участник d знает: $s_3 = 29$, $s_1 = 2$

Переменные объявлены так, что:

$s = s_1 + s_2$
$s_1 = s_3 + s_4$
$s_1 = s_5 + s_6$
$s_2 = s_7 + s_8$

И тогда: $s_1 = 2$, $s_2 = 12$, $s_3 = 29$, $s_4 = 20$, $s_5 = 17$, $s_6 = 32$, $s_7 = 25$, $s_8 = 34$

Задание B1¹ (0.3)

Необходимо разделить секрет $s = 17, s \in \ZZ_{47}$ между $5$ участниками так, чтобы любые $3$ могли его восстановить. Выпишите, что каждый участник знает.
Затем выбрать любых $3$ участников и восстановить секрет обратно.

Нужно использовать схему Блэкли.

Авторское решение:

Секрет поместим в точку $\left(17,\,11,\,23\right)$. Он находится в первой её координате.

Проведём через эту точку плоскости. Здесь и далее $\vec{x}$ - вектор-столбец

$ \left(\begin{array}{rrr} 46 & 37 & 12 \end{array}\right) \vec{x} = 8 $
$ \left(\begin{array}{rrr} 25 & 10 & 16 \end{array}\right) \vec{x} = 10 $
$ \left(\begin{array}{rrr} 39 & 2 & 31 \end{array}\right) \vec{x} = 35 $
$ \left(\begin{array}{rrr} 43 & 29 & 40 \end{array}\right) \vec{x} = 43 $
$ \left(\begin{array}{rrr} 12 & 31 & 28 \end{array}\right) \vec{x} = 14 $

Тогда каждый участник обладает следующим набором чисел:

$ \left[46, 37, 12, 8\right] $
$ \left[25, 10, 16, 10\right] $
$ \left[39, 2, 31, 35\right] $
$ \left[43, 29, 40, 43\right] $
$ \left[12, 31, 28, 14\right] $

Чтобы восстановить секрет достаточно решить СЛАУ, после чего извлечь секрет из первой координаты.

\[\left(\begin{array}{rrr}12 & 31 & 28 \\46 & 37 & 12 \\25 & 10 & 16\end{array}\right) \vec{x} = \left(\begin{array}{r}14 \\8 \\10\end{array}\right) \implies \vec{x} = \left(\begin{array}{r}17 \\11 \\23\end{array}\right) \implies s = 17\]

Задание B2¹ (0.45)

Человек по неосторожности реализовал схему Блэкли, описанную на криптовики. От схемы из презентации она отличается тем, что секрет распределяется между всеми координатами секретной точки. Засчёт этого, говорится, схема идеальна.

Для вычислений использовалось поле $\ZZ_{7}$.

В схеме секрет разделяется так, что лишь трое могут его восстановить. Вам даны две плоскости:

$ 6x_1 + 0x_2 + 4x_3 = 0 $
$ 4x_1 + 6x_2 + 5x_3 = 3 $

Необходимо перечислить все 7 точек, в которых может находиться секрет.

Авторское решение

Составим и решим СЛАУ на координаты точек пересечения:

\[\left(\begin{array}{rrr} 6 & 0 & 4 \\ 4 & 6 & 5 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \\ 3 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 4 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ 0 \\ 2 \end{array}\right), t \in \ZZ_{7}\]

Остаётся перебрать все значения $t$ и получить следующие варианты: $\vec{x} \in \left[\left(\begin{array}{r} 0 \\ 4 \\ 0 \end{array}\right), \left(\begin{array}{r} 1 \\ 4 \\ 2 \end{array}\right), \left(\begin{array}{r} 2 \\ 4 \\ 4 \end{array}\right), \left(\begin{array}{r} 3 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{r} 4 \\ 4 \\ 1 \end{array}\right), \left(\begin{array}{r} 5 \\ 4 \\ 3 \end{array}\right), \left(\begin{array}{r} 6 \\ 4 \\ 5 \end{array}\right)\right]$

Задание B3¹ (0.7)

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

Участники назвали следующие гиперплоскости:

$30x_1 + 3x_2 = 33$
$38x_1 + 16x_2 = 8$
$33x_1 + 41x_2 = 31$
$38x_1 + 25x_2 = 23$
$22x_1 + 5x_2 = 36$

Для вычислений использовалось поле $\Z_{43}$

Авторское решение:

Переберём все пары участников, для каждой вычислим секрет:

1 и 2: $\left(\begin{array}{rr} 30 & 3 \\ 38 & 16 \end{array}\right) \vec{x} = \left(\begin{array}{r} 33 \\ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 19 \\ 36 \end{array}\right) \implies s = 19$
1 и 3: $\left(\begin{array}{rr} 30 & 3 \\ 33 & 41 \end{array}\right) \vec{x} = \left(\begin{array}{r} 33 \\ 31 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 1 \\ 1 \end{array}\right) \implies s = 1$
1 и 4: $\left(\begin{array}{rr} 30 & 3 \\ 38 & 25 \end{array}\right) \vec{x} = \left(\begin{array}{r} 33 \\ 23 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 34 \end{array}\right) \implies s = 2$
1 и 5: $\left(\begin{array}{rr} 30 & 3 \\ 22 & 5 \end{array}\right) \vec{x} = \left(\begin{array}{r} 33 \\ 36 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 36 \\ 38 \end{array}\right) \implies s = 36$
2 и 3: $\left(\begin{array}{rr} 38 & 16 \\ 33 & 41 \end{array}\right) \vec{x} = \left(\begin{array}{r} 8 \\ 31 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 41 \\ 16 \end{array}\right) \implies s = 41$
2 и 4: $\left(\begin{array}{rr} 38 & 16 \\ 38 & 25 \end{array}\right) \vec{x} = \left(\begin{array}{r} 8 \\ 23 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 41 \\ 16 \end{array}\right) \implies s = 41$
2 и 5: $\left(\begin{array}{rr} 38 & 16 \\ 22 & 5 \end{array}\right) \vec{x} = \left(\begin{array}{r} 8 \\ 36 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 41 \\ 16 \end{array}\right) \implies s = 41$
3 и 4: $\left(\begin{array}{rr} 33 & 41 \\ 38 & 25 \end{array}\right) \vec{x} = \left(\begin{array}{r} 31 \\ 23 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 41 \\ 16 \end{array}\right) \implies s = 41$
3 и 5: $\left(\begin{array}{rr} 33 & 41 \\ 22 & 5 \end{array}\right) \vec{x} = \left(\begin{array}{r} 31 \\ 36 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 41 \\ 16 \end{array}\right) \implies s = 41$
4 и 5: $\left(\begin{array}{rr} 38 & 25 \\ 22 & 5 \end{array}\right) \vec{x} = \left(\begin{array}{r} 23 \\ 36 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 41 \\ 16 \end{array}\right) \implies s = 41$

Теперь заметим, что $s = 41$ встретилось чаще всего, а значит это и будет правильным секретом.

Врёт участник №1

Задание C1¹ (0.3)

Секрет разделили при помощи схемы Шамира над полем $\ZZ_{13}$. Нужно его восстановить.

Даны следующие точки: $ \left(1, 6\right), \left(2, 2\right), \left(3, 0\right) $

Ответ: $s = 12$, причём $f(x) = x^{2} + 6 x + 12$

Задание C2¹ (0.45)

Для реализации схемы Шамира в качестве поля взяли $\ZZ_{16}$. Восстановить секрет могут $3$ участников, но вам известны лишь $3 - 1$ точка: $\left(2, 9\right), \left(3, 9\right)$

Необходимо выяснить чётность секрета.

Авторское решение

Пусть $y = c_0 + c_1x + c_2x^2$

Составим СЛАУ и решим её: $\left(\begin{array}{rrr} 1 & 2 & 4 \\ 1 & 3 & 9 \end{array}\right) \vec{c} = \left(\begin{array}{r} 9 \\ 9 \end{array}\right) \implies \vec{c} = \left(\begin{array}{r} 9 \\ 0 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ -\frac{5}{6} \\ \frac{1}{6} \end{array}\right)$ Здесь видно, что $t$ должно делиться на $ 6 $, иначе результат не будет представим в кольце вычетов. Следовательно $t$ будет чётно, а значит сам секрет будет нечётен

P.S. Секрет был $s=5$

Задание C3¹ (0.7)

При помощи схемы Шамира был разделён секрет. Вам, как участнику схемы, досталась точка $\left(1, 20\right)$. Точки других участников вы точно не знаете, но уверены, что они имеют $x\in{ 2, 3, 4 }$.

Необходимо, чтобы в результате восстановления значение секрета изменилось на $11$. Какую точку вы должны назвать?

Решение:

Проведём многочлен через точки $\left[\left(2, 0\right), \left(3, 0\right), \left(4, 0\right), \left(0, 11\right)\right]$: в нуле равен $11$, в точках остальных участников равен нулю. Получим многочлен $12 x^{3} + 7 x^{2} + 13 x + 11$ (искать целиком не обязательно на самом деле)

Нам нужно только его значение в точке $x=1$; там он равен $20$.

Теперь прибавим это к известному выданному $y$ и получим $y’ = 20 + 20 = 17$.

Значит нужно назвать точку $(1, 17)$

P.S. Процесс восстановления:

Через точки $\left[\left(1, 20\right), \left(2, 19\right), \left(3, 0\right), \left(4, 21\right)\right]$ проходит $f(x) = 2 x^{3} + 2 x^{2} + 2 x + 14$

Но в результате атаки через $\left[\left(1, 17\right), \left(2, 19\right), \left(3, 0\right), \left(4, 21\right)\right]$ был проведён $f’(x) = 14 x^{3} + 9 x^{2} + 15 x + 2$.

Получили: $s = f(0) = 14$ и $s = f’(0) = 2$, что и требовалось

Вариант 2

Задание A1² (0.3)

Секрет разделён при помощи простейшей $(n,n)$-схемы, $n = 4$. Необходимо его восстановить. В качестве поля используется кольцо многочленов степени не выше $4$ над кольцом $\ZZ_{37}$

Дано:

$ v_{1} = 11 x^{4} + 26 x^{3} + x^{2} + 4 x + 26 $
$ v_{2} = 8 x^{4} + 35 x^{3} + 15 x^{2} + 30 x + 7 $
$ v_{3} = 2 x^{4} + 20 x^{3} + 22 x^{2} + 26 x + 36 $
$ v_{4} = 5 x^{3} + 23 x^{2} + 17 x + 28 $

Найти: $ s $

Ответ: $ s = 21 x^{4} + 12 x^{3} + 24 x^{2} + 3 x + 23 $

Задание A2² (0.45)

Вам дана ASCII строка: ba/cs. Необходимо её при помощи простейшей $(n,n)$ схемы разделить между $n=5$ участниками.

Использовать для вычислений модуль более $10000$ не допускается.

Выпишите какой набор чисел получит каждый из участников.

Авторское решение: Переведём строку в байты по таблице ASCII: $\left[98, 97, 47, 99, 115\right]$.

Теперь разделим: $\left(\begin{array}{rrrrr} 12 & 32 & 126 & 140 & 141 \\ 77 & 56 & 151 & 250 & 95 \\ 41 & 206 & 41 & 123 & 214 \\ 230 & 212 & 129 & 165 & 73 \\ 250 & 103 & 112 & 189 & 104 \end{array}\right)$

Задание A3² (0.7)

Есть четыре участника: $a, b, c, d$. Вам дана булева формула $((d\vee a)\vee (b\wedge d))\wedge ((c\vee b)\wedge d)$. Ваша задача — разделить секрет $s = 31$ при помощи простейшей $(n, n)$-схемы над полем $\ZZ_{47}$ таким образом, чтобы его могли восстановить тогда и только тогда, когда эта функция, будучи применена к присутствующим участникам, принимает значение истины.

Возможный ответ:

Секретная информация:

Участник a знает: $s_4 = 17$
Участник b знает: $s_2 = 3$, $s_6 = 16$
Участник c знает: $s_5 = 15$
Участник d знает: $s_3 = 11$, $s_2 = 3$, $s = 31$

Переменные объявлены так, что:

$s = s_1 + s_2$
$s_1 = s_3 + s_4$
$s = s_5 + s_6$

И тогда: $s_1 = 28$, $s_2 = 3$, $s_3 = 11$, $s_4 = 17$, $s_5 = 15$, $s_6 = 16$

Задание B1² (0.3)

Необходимо разделить секрет $s = 14, s \in \ZZ_{29}$ между $5$ участниками так, чтобы любые $4$ могли его восстановить. Выпишите, что каждый участник знает.
Затем выбрать любых $4$ участников и восстановить секрет обратно.

Нужно использовать схему Блэкли.

Авторское решение:

Секрет поместим в точку $\left(14,\,15,\,14,\,20\right)$. Он находится в первой её координате.

Проведём через эту точку плоскости. Здесь и далее $\vec{x}$ - вектор-столбец

$ \left(\begin{array}{rrrr} 27 & 18 & 11 & 11 \end{array}\right) \vec{x} = 7 $
$ \left(\begin{array}{rrrr} 22 & 5 & 13 & 11 \end{array}\right) \vec{x} = 2 $
$ \left(\begin{array}{rrrr} 21 & 0 & 22 & 16 \end{array}\right) \vec{x} = 23 $
$ \left(\begin{array}{rrrr} 18 & 10 & 2 & 18 \end{array}\right) \vec{x} = 7 $
$ \left(\begin{array}{rrrr} 4 & 9 & 26 & 11 \end{array}\right) \vec{x} = 21 $

Тогда каждый участник обладает следующим набором чисел:

$ \left[27, 18, 11, 11, 7\right] $
$ \left[22, 5, 13, 11, 2\right] $
$ \left[21, 0, 22, 16, 23\right] $
$ \left[18, 10, 2, 18, 7\right] $
$ \left[4, 9, 26, 11, 21\right] $

Чтобы восстановить секрет достаточно решить СЛАУ, после чего извлечь секрет из первой координаты. $\left(\begin{array}{rrrr} 22 & 5 & 13 & 11 \\ 18 & 10 & 2 & 18 \\ 21 & 0 & 22 & 16 \\ 27 & 18 & 11 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 2 \\ 7 \\ 23 \\ 7 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 14 \\ 15 \\ 14 \\ 20 \end{array}\right) \implies s = 14$

Задание B2² (0.45)

Для вычислений использовалось поле $\ZZ_{7}$.

В схеме секрет разделяется так, что лишь трое могут его восстановить. Вам даны две плоскости:

$ 3x_1 + 4x_2 + 4x_3 = 6 $
$ 3x_1 + 4x_2 + 5x_3 = 2 $

Необходимо перечислить все 7 точек, в которых может находиться секрет.

Авторское решение

Составим и решим СЛАУ на координаты точек пересечения:

\[\left(\begin{array}{rrr} 3 & 4 & 4 \\ 3 & 4 & 5 \end{array}\right) \vec{x} = \left(\begin{array}{r} 6 \\ 2 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 5 \\ 0 \\ 3 \end{array}\right) + t\left(\begin{array}{r} 1 \\ 1 \\ 0 \end{array}\right), t \in \ZZ_{7}\]

Остаётся перебрать все значения $t$ и получить следующие варианты: $\vec{x} \in \left[\left(\begin{array}{r} 5 \\ 0 \\ 3 \end{array}\right), \left(\begin{array}{r} 6 \\ 1 \\ 3 \end{array}\right), \left(\begin{array}{r} 0 \\ 2 \\ 3 \end{array}\right), \left(\begin{array}{r} 1 \\ 3 \\ 3 \end{array}\right), \left(\begin{array}{r} 2 \\ 4 \\ 3 \end{array}\right), \left(\begin{array}{r} 3 \\ 5 \\ 3 \end{array}\right), \left(\begin{array}{r} 4 \\ 6 \\ 3 \end{array}\right)\right]$

Задание B3² (0.7)

Участники назвали следующие гиперплоскости:

$3x_1 + 17x_2 = 21$
$8x_1 + 19x_2 = 0$
$18x_1 + 13x_2 = 20$
$16x_1 + 23x_2 = 8$
$8x_1 + 7x_2 = 25$

Для вычислений использовалось поле $\Z_{31}$

Авторское решение:

Переберём все пары участников, для каждой вычислим секрет:

1 и 2: $\left(\begin{array}{rr} 3 & 17 \\ 8 & 19 \end{array}\right) \vec{x} = \left(\begin{array}{r} 21 \\ 0 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 13 \\ 19 \end{array}\right) \implies s = 13$
1 и 3: $\left(\begin{array}{rr} 3 & 17 \\ 18 & 13 \end{array}\right) \vec{x} = \left(\begin{array}{r} 21 \\ 20 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 28 \\ 20 \end{array}\right) \implies s = 28$
1 и 4: $\left(\begin{array}{rr} 3 & 17 \\ 16 & 23 \end{array}\right) \vec{x} = \left(\begin{array}{r} 21 \\ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 27 \\ 22 \end{array}\right) \implies s = 27$
1 и 5: $\left(\begin{array}{rr} 3 & 17 \\ 8 & 7 \end{array}\right) \vec{x} = \left(\begin{array}{r} 21 \\ 25 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 7 \\ 0 \end{array}\right) \implies s = 7$
2 и 3: $\left(\begin{array}{rr} 8 & 19 \\ 18 & 13 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \\ 20 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 16 \end{array}\right) \implies s = 24$
2 и 4: $\left(\begin{array}{rr} 8 & 19 \\ 16 & 23 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \\ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 16 \end{array}\right) \implies s = 24$
2 и 5: $\left(\begin{array}{rr} 8 & 19 \\ 8 & 7 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \\ 25 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 16 \end{array}\right) \implies s = 24$
3 и 4: $\left(\begin{array}{rr} 18 & 13 \\ 16 & 23 \end{array}\right) \vec{x} = \left(\begin{array}{r} 20 \\ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 16 \end{array}\right) \implies s = 24$
3 и 5: $\left(\begin{array}{rr} 18 & 13 \\ 8 & 7 \end{array}\right) \vec{x} = \left(\begin{array}{r} 20 \\ 25 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 16 \end{array}\right) \implies s = 24$
4 и 5: $\left(\begin{array}{rr} 16 & 23 \\ 8 & 7 \end{array}\right) \vec{x} = \left(\begin{array}{r} 8 \\ 25 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 16 \end{array}\right) \implies s = 24$

Теперь заметим, что $s = 24$ встретилось чаще всего, а значит это и будет правильным секретом.

Врёт участник №1

Задание C1² (0.3)

Секрет разделили при помощи схемы Шамира над полем $\ZZ_{13}$. Нужно его восстановить.

Даны следующие точки: $ \left(1, 10\right), \left(2, 4\right), \left(3, 3\right) $

Ответ: $s = 8$, причём $f(x) = 9 x^{2} + 6 x + 8$

Задание C2² (0.45)

Для реализации схемы Шамира в качестве поля взяли $\ZZ_{256}$. Восстановить секрет могут $3$ участников, но вам известны лишь $3 - 1$ точка: $\left(2, 240\right), \left(3, 189\right)$

Необходимо выяснить чётность секрета.

Авторское решение

Пусть $y = c_0 + c_1x + c_2x^2$

Составим СЛАУ и решим её: $\left(\begin{array}{rrr} 1 & 2 & 4 \\ 1 & 3 & 9 \end{array}\right) \vec{c} = \left(\begin{array}{r} 240 \\ 189 \end{array}\right) \implies \vec{c} = \left(\begin{array}{r} 342 \\ -51 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ -\frac{5}{6} \\ \frac{1}{6} \end{array}\right)$ Здесь видно, что $t$ должно делиться на $ 6 $, иначе результат не будет представим в кольце вычетов. Следовательно $t$ будет чётно, а значит сам секрет будет чётен

P.S. Секрет был $s=140$

Задание C3² (0.7)

При помощи схемы Шамира был разделён секрет. Вам, как участнику схемы, досталась точка $\left(3, 40\right)$. Точки других участников вы точно не знаете, но уверены, что они имеют $x\in{ 1, 2, 4 }$.

Необходимо, чтобы в результате восстановления значение секрета изменилось на $34$. Какую точку вы должны назвать?

Решение:

Проведём многочлен через точки $\left[\left(1, 0\right), \left(2, 0\right), \left(4, 0\right), \left(0, 34\right)\right]$: в нуле равен $34$, в точках остальных участников равен нулю. Получим многочлен $31 x^{3} + 18 x^{2} + 11 x + 34$ (искать целиком не обязательно на самом деле)

Нам нужно только его значение в точке $x=3$; там он равен $32$.

Теперь прибавим это к известному выданному $y$ и получим $y’ = 40 + 32 = 25$.

Значит нужно назвать точку $(3, 25)$

P.S. Процесс восстановления:

Через точки $\left[\left(1, 2\right), \left(2, 30\right), \left(3, 40\right), \left(4, 28\right)\right]$ проходит $f(x) = 15 x^{3} + 42 x^{2} + 32 x + 7$

Но в результате атаки через $\left[\left(1, 2\right), \left(2, 30\right), \left(3, 25\right), \left(4, 28\right)\right]$ был проведён $f’(x) = 46 x^{3} + 13 x^{2} + 43 x + 41$.

Получили: $s = f(0) = 7$ и $s = f’(0) = 41$, что и требовалось

Вариант 3

Задание A1³ (0.3)

Дано:

$ s = 6 x^{2} + 10 x + 20 $
$ v_{1} = 14 x^{2} + 32 x + 6 $
$ v_{2} = 27 x^{2} + 22 x + 34 $
$ v_{4} = 10 x^{2} + 5 x + 6 $

Найти: $ v_{3} $

Ответ: $ v_{3} = 29 x^{2} + 25 x + 11 $

Задание A2³ (0.45)

Вам дана ASCII строка: C#>Java. Необходимо её при помощи простейшей $(n,n)$ схемы разделить между $n=3$ участниками.

Использовать для вычислений модуль более $10000$ не допускается.

Выпишите какой набор чисел получит каждый из участников.

Авторское решение: Переведём строку в байты по таблице ASCII: $\left[67, 35, 62, 74, 97, 118, 97\right]$.

Теперь разделим: $\left(\begin{array}{rrrrrrr} 141 & 197 & 49 & 88 & 132 & 229 & 50 \\ 36 & 155 & 7 & 237 & 193 & 164 & 230 \\ 146 & 195 & 6 & 5 & 28 & 237 & 73 \end{array}\right)$

Задание A3³ (0.7)

Есть четыре участника: $a, b, c, d$. Вам дана булева формула $((a\vee c)\vee ((b\wedge d)\vee c))\wedge (b\wedge a)$. Ваша задача — разделить секрет $s = 12$ при помощи простейшей $(n, n)$-схемы над полем $\ZZ_{47}$ таким образом, чтобы его могли восстановить тогда и только тогда, когда эта функция, будучи применена к присутствующим участникам, принимает значение истины.

Возможный ответ:

Секретная информация:

Участник a знает: $s_3 = 12$, $s = 12$
Участник b знает: $s_5 = 31$, $s = 12$
Участник c знает: $s_4 = 35$, $s_6 = 28$
Участник d знает: $s_5 = 31$

Переменные объявлены так, что:

$s = s_1 + s_2$
$s_1 = s_3 + s_4$
$s_2 = s_5 + s_6$

И тогда:$s_1 = 0$, $s_2 = 12$, $s_3 = 12$, $s_4 = 35$, $s_5 = 31$, $s_6 = 28$

Задание B1³ (0.3)

Необходимо разделить секрет $s = 11, s \in \ZZ_{13}$ между $5$ участниками так, чтобы любые $4$ могли его восстановить. Выпишите, что каждый участник знает.
Затем выбрать любых $4$ участников и восстановить секрет обратно.

Нужно использовать схему Блэкли.

Авторское решение:

Секрет поместим в точку $\left(11,\,2,\,3,\,0\right)$. Он находится в первой её координате.

Проведём через эту точку плоскости. Здесь и далее $\vec{x}$ - вектор-столбец

$ \left(\begin{array}{rrrr} 2 & 0 & 12 & 6 \end{array}\right) \vec{x} = 6 $
$ \left(\begin{array}{rrrr} 12 & 5 & 4 & 9 \end{array}\right) \vec{x} = 11 $
$ \left(\begin{array}{rrrr} 9 & 2 & 6 & 2 \end{array}\right) \vec{x} = 4 $
$ \left(\begin{array}{rrrr} 10 & 7 & 7 & 8 \end{array}\right) \vec{x} = 2 $
$ \left(\begin{array}{rrrr} 8 & 6 & 10 & 2 \end{array}\right) \vec{x} = 0 $

Тогда каждый участник обладает следующим набором чисел:

$ \left[2, 0, 12, 6, 6\right] $
$ \left[12, 5, 4, 9, 11\right] $
$ \left[9, 2, 6, 2, 4\right] $
$ \left[10, 7, 7, 8, 2\right] $
$ \left[8, 6, 10, 2, 0\right] $

Чтобы восстановить секрет достаточно решить СЛАУ, после чего извлечь секрет из первой координаты. $\left(\begin{array}{rrrr} 9 & 2 & 6 & 2 \\ 10 & 7 & 7 & 8 \\ 8 & 6 & 10 & 2 \\ 2 & 0 & 12 & 6 \end{array}\right) \vec{x} = \left(\begin{array}{r} 4 \\ 2 \\ 0 \\ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 11 \\ 2 \\ 3 \\ 0 \end{array}\right) \implies s = 11$

Задание B2³ (0.45)

Для вычислений использовалось поле $\ZZ_{7}$.

В схеме секрет разделяется так, что лишь трое могут его восстановить. Вам даны две плоскости:

$ 0x_1 + 3x_2 + 3x_3 = 5 $
$ 3x_1 + 6x_2 + 2x_3 = 4 $

Необходимо перечислить все 7 точек, в которых может находиться секрет.

Авторское решение

Составим и решим СЛАУ на координаты точек пересечения:

\[\left(\begin{array}{rrr} 0 & 3 & 3 \\ 3 & 6 & 2 \end{array}\right) \vec{x} = \left(\begin{array}{r} 5 \\ 4 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 5 \\ 4 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ 1 \\ 6 \end{array}\right), t \in \ZZ_{7}\]

Остаётся перебрать все значения $t$ и получить следующие варианты: $\vec{x} \in \left[\left(\begin{array}{r} 5 \\ 4 \\ 0 \end{array}\right), \left(\begin{array}{r} 6 \\ 5 \\ 6 \end{array}\right), \left(\begin{array}{r} 0 \\ 6 \\ 5 \end{array}\right), \left(\begin{array}{r} 1 \\ 0 \\ 4 \end{array}\right), \left(\begin{array}{r} 2 \\ 1 \\ 3 \end{array}\right), \left(\begin{array}{r} 3 \\ 2 \\ 2 \end{array}\right), \left(\begin{array}{r} 4 \\ 3 \\ 1 \end{array}\right)\right]$

Задание B3³ (0.7)

Участники назвали следующие гиперплоскости:

$6x_1 + 19x_2 = 25$
$26x_1 + 20x_2 = 10$
$6x_1 + 11x_2 = 21$
$6x_1 + 1x_2 = 16$
$9x_1 + 9x_2 = 19$

Для вычислений использовалось поле $\ZZ_{31}$

Авторское решение:

Переберём все пары участников, для каждой вычислим секрет:

1 и 2: $\left(\begin{array}{rr} 6 & 19 \\ 26 & 20 \end{array}\right) \vec{x} = \left(\begin{array}{r} 25 \\ 10 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 16 \end{array}\right) \implies s = 0$
1 и 3: $\left(\begin{array}{rr} 6 & 19 \\ 6 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 25 \\ 21 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 16 \end{array}\right) \implies s = 0$
1 и 4: $\left(\begin{array}{rr} 6 & 19 \\ 6 & 1 \end{array}\right) \vec{x} = \left(\begin{array}{r} 25 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 16 \end{array}\right) \implies s = 0$
1 и 5: $\left(\begin{array}{rr} 6 & 19 \\ 9 & 9 \end{array}\right) \vec{x} = \left(\begin{array}{r} 25 \\ 19 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 16 \\ 24 \end{array}\right) \implies s = 16$
2 и 3: $\left(\begin{array}{rr} 26 & 20 \\ 6 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 21 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 16 \end{array}\right) \implies s = 0$
2 и 4: $\left(\begin{array}{rr} 26 & 20 \\ 6 & 1 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 16 \end{array}\right) \implies s = 0$
2 и 5: $\left(\begin{array}{rr} 26 & 20 \\ 9 & 9 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 19 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 13 \\ 27 \end{array}\right) \implies s = 13$
3 и 4: $\left(\begin{array}{rr} 6 & 11 \\ 6 & 1 \end{array}\right) \vec{x} = \left(\begin{array}{r} 21 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 0 \\ 16 \end{array}\right) \implies s = 0$
3 и 5: $\left(\begin{array}{rr} 6 & 11 \\ 9 & 9 \end{array}\right) \vec{x} = \left(\begin{array}{r} 21 \\ 19 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 28 \\ 12 \end{array}\right) \implies s = 28$
4 и 5: $\left(\begin{array}{rr} 6 & 1 \\ 9 & 9 \end{array}\right) \vec{x} = \left(\begin{array}{r} 16 \\ 19 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 20 \\ 20 \end{array}\right) \implies s = 20$

Теперь заметим, что $s = 0$ встретилось чаще всего, а значит это и будет правильным секретом.

Врёт участник №5

Задание C1³ (0.3)

Секрет разделили при помощи схемы Шамира над полем $\ZZ_{13}$. Нужно его восстановить.

Даны следующие точки: $ \left(1, 12\right), \left(2, 7\right), \left(3, 12\right) $

Ответ: $s = 1$, причём $f(x) = 5 x^{2} + 6 x + 1$

Задание C2³ (0.45)

Для реализации схемы Шамира в качестве поля взяли $\ZZ_{16}$. Восстановить секрет могут $3$ участников, но вам известны лишь $3 - 1$ точка: $\left(2, 11\right), \left(3, 14\right)$

Необходимо выяснить чётность секрета.

Авторское решение

Пусть $y = c_0 + c_1x + c_2x^2$

Составим СЛАУ и решим её: $\left(\begin{array}{rrr} 1 & 2 & 4 \\ 1 & 3 & 9 \end{array}\right) \vec{c} = \left(\begin{array}{r} 11 \\ 14 \end{array}\right) \implies \vec{c} = \left(\begin{array}{r} 5 \\ 3 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ -\frac{5}{6} \\ \frac{1}{6} \end{array}\right)$ Здесь видно, что $t$ должно делиться на $ 6 $, иначе результат не будет представим в кольце вычетов. Следовательно $t$ будет чётно, а значит сам секрет будет нечётен

P.S. Секрет был $s=3$

Задание C3³ (0.7)

При помощи схемы Шамира был разделён секрет. Вам, как участнику схемы, досталась точка $\left(1, 10\right)$. Точки других участников вы точно не знаете, но уверены, что они имеют $x\in{ 2, 3, 4 }$.

Необходимо, чтобы в результате восстановления значение секрета изменилось на $2$. Какую точку вы должны назвать?

Решение:

Проведём многочлен через точки $\left[\left(2, 0\right), \left(3, 0\right), \left(4, 0\right), \left(0, 2\right)\right]$: в нуле равен $2$, в точках остальных участников равен нулю. Получим многочлен $21 x^{3} + 18 x^{2} + 17 x + 2$ (искать целиком не обязательно на самом деле)

Нам нужно только его значение в точке $x=1$; там он равен $12$.

Теперь прибавим это к известному выданному $y$ и получим $y’ = 10 + 12 = 22$.

Значит нужно назвать точку $(1, 22)$

P.S. Процесс восстановления:

Через точки $\left[\left(1, 10\right), \left(2, 15\right), \left(3, 17\right), \left(4, 4\right)\right]$ проходит $f(x) = 21 x^{3} + 22 x^{2} + 22 x + 14$

Но в результате атаки через $\left[\left(1, 22\right), \left(2, 15\right), \left(3, 17\right), \left(4, 4\right)\right]$ был проведён $f’(x) = 19 x^{3} + 17 x^{2} + 16 x + 16$.

Получили: $s = f(0) = 14$ и $s = f’(0) = 16$, что и требовалось

Вариант 4

Задание A1⁴ (0.3)

Секрет разделён при помощи простейшей $(n,n)$-схемы, $n = 3$. Необходимо его восстановить. В качестве поля используется кольцо многочленов степени не выше $2$ над кольцом $\ZZ_{19}$

Дано:

$ s = 3 x^{2} + 18 x + 15 $
$ v_{2} = 16 x^{2} + 5 x $
$ v_{3} = 9 x^{2} + 12 x + 11 $

Найти: $ v_{1} $

Ответ: $ v_{1} = 16 x^{2} + x + 4 $

Задание A2⁴ (0.45)

Вам дана ASCII строка: CS HSE. Необходимо её при помощи простейшей $(n,n)$ схемы разделить между $n=4$ участниками.

Использовать для вычислений модуль более $10000$ не допускается.

Выпишите какой набор чисел получит каждый из участников.

Авторское решение: Переведём строку в байты по таблице ASCII: $\left[99, 114, 121, 112, 116, 111\right]$.

Теперь разделим: $\left(\begin{array}{rrrrrr} 232 & 239 & 255 & 27 & 92 & 112 \\ 3 & 50 & 197 & 104 & 51 & 0 \\ 4 & 96 & 41 & 220 & 56 & 121 \\ 116 & 241 & 140 & 17 & 173 & 134 \end{array}\right)$

Задание A3⁴ (0.7)

Есть четыре участника: $a, b, c, d$. Вам дана булева формула $((c\vee a)\vee (b\wedge d))\wedge ((a\vee d)\wedge b)$. Ваша задача — разделить секрет $s = 4$ при помощи простейшей $(n, n)$-схемы над полем $\ZZ_{47}$ таким образом, чтобы его могли восстановить тогда и только тогда, когда эта функция, будучи применена к присутствующим участникам, принимает значение истины.

Возможный ответ:

Секретная информация:

Участник a знает: $s_4 = 27$, $s_5 = 25$
Участник b знает: $s_2 = 20$, $s = 4$
Участник c знает: $s_3 = 4$
Участник d знает: $s_2 = 20$, $s_6 = 26$

Переменные объявлены так, что:

$s = s_1 + s_2$
$s_1 = s_3 + s_4$
$s = s_5 + s_6$

И тогда:$s_1 = 31$, $s_2 = 20$, $s_3 = 4$, $s_4 = 27$, $s_5 = 25$, $s_6 = 26$

Задание B1⁴ (0.3)

Необходимо разделить секрет $s = 24, s \in \ZZ_{47}$ между $4$ участниками так, чтобы любые $4$ могли его восстановить. Выпишите, что каждый участник знает.
Затем выбрать любых $4$ участников и восстановить секрет обратно.

Нужно использовать схему Блэкли.

Авторское решение:

Секрет поместим в точку $\left(24,\,29,\,4,\,16\right)$. Он находится в первой её координате.

Проведём через эту точку плоскости. Здесь и далее $\vec{x}$ - вектор-столбец

$ \left(\begin{array}{rrrr} 11 & 7 & 11 & 40 \end{array}\right) \vec{x} = 23 $
$ \left(\begin{array}{rrrr} 5 & 20 & 44 & 30 \end{array}\right) \vec{x} = 40 $
$ \left(\begin{array}{rrrr} 20 & 15 & 6 & 12 \end{array}\right) \vec{x} = 3 $
$ \left(\begin{array}{rrrr} 31 & 28 & 17 & 27 \end{array}\right) \vec{x} = 35 $

Тогда каждый участник обладает следующим набором чисел:

$ \left[11, 7, 11, 40, 23\right] $
$ \left[5, 20, 44, 30, 40\right] $
$ \left[20, 15, 6, 12, 3\right] $
$ \left[31, 28, 17, 27, 35\right] $

Чтобы восстановить секрет достаточно решить СЛАУ, после чего извлечь секрет из первой координаты. $\left(\begin{array}{rrrr} 11 & 7 & 11 & 40 \\ 20 & 15 & 6 & 12 \\ 5 & 20 & 44 & 30 \\ 31 & 28 & 17 & 27 \end{array}\right) \vec{x} = \left(\begin{array}{r} 23 \\ 3 \\ 40 \\ 35 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 24 \\ 29 \\ 4 \\ 16 \end{array}\right) \implies s = 24$

Задание B2⁴ (0.45)

Для вычислений использовалось поле $\ZZ_{7}$.

В схеме секрет разделяется так, что лишь трое могут его восстановить. Вам даны две плоскости:

$ 0x_1 + 0x_2 + 4x_3 = 5 $
$ 5x_1 + 3x_2 + 0x_3 = 2 $

Необходимо перечислить все 7 точек, в которых может находиться секрет.

Авторское решение

Составим и решим СЛАУ на координаты точек пересечения:

\[\left(\begin{array}{rrr} 0 & 0 & 4 \\ 5 & 3 & 0 \end{array}\right) \vec{x} = \left(\begin{array}{r} 5 \\ 2 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 6 \\ 0 \\ 3 \end{array}\right) + t\left(\begin{array}{r} 1 \\ 3 \\ 0 \end{array}\right), t \in \ZZ_{7}\]

Остаётся перебрать все значения $t$ и получить следующие варианты: $\vec{x} \in \left[\left(\begin{array}{r} 6 \\ 0 \\ 3 \end{array}\right), \left(\begin{array}{r} 0 \\ 3 \\ 3 \end{array}\right), \left(\begin{array}{r} 1 \\ 6 \\ 3 \end{array}\right), \left(\begin{array}{r} 2 \\ 2 \\ 3 \end{array}\right), \left(\begin{array}{r} 3 \\ 5 \\ 3 \end{array}\right), \left(\begin{array}{r} 4 \\ 1 \\ 3 \end{array}\right), \left(\begin{array}{r} 5 \\ 4 \\ 3 \end{array}\right)\right]$

Задание B3⁴ (0.7)

Участники назвали следующие гиперплоскости:

$8x_1 + 19x_2 = 10$
$31x_1 + 22x_2 = 17$
$11x_1 + 15x_2 = 16$
$22x_1 + 8x_2 = 14$
$4x_1 + 6x_2 = 24$

Для вычислений использовалось поле $\ZZ_{37}$

Авторское решение:

Переберём все пары участников, для каждой вычислим секрет:

1 и 2: $\left(\begin{array}{rr} 8 & 19 \\ 31 & 22 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 17 \end{array}\right) \implies \vec{x} = (\begin{array}{r} 11 \\ 29 \end{array}\right) \implies s = 11$
1 и 3: $\left(\begin{array}{rr} 8 & 19 \\ 11 & 15 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 30 \\ 21 \end{array}\right) \implies s = 30$
1 и 4: $\left(\begin{array}{rr} 8 & 19 \\ 22 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 14 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 30 \\ 21 \end{array}\right) \implies s = 30$
1 и 5: $\left(\begin{array}{rr} 8 & 19 \\ 4 & 6 \end{array}\right) \vec{x} = \left(\begin{array}{r} 10 \\ 24 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 30 \\ 21 \end{array}\right) \implies s = 30$
2 и 3: $\left(\begin{array}{rr} 31 & 22 \\ 11 & 15 \end{array}\right) \vec{x} = \left(\begin{array}{r} 17 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 14 \\ 13 \end{array}\right) \implies s = 14$
2 и 4: $\left(\begin{array}{rr} 31 & 22 \\ 22 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 17 \\ 14 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 7 \\ 1 \end{array}\right) \implies s = 7$
2 и 5: $\left(\begin{array}{rr} 31 & 22 \\ 4 & 6 \end{array}\right) \vec{x} = \left(\begin{array}{r} 17 \\ 24 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 10 \\ 22 \end{array}\right) \implies s = 10$
3 и 4: $\left(\begin{array}{rr} 11 & 15 \\ 22 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 16 \\ 14 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 30 \\ 21 \end{array}\right) \implies s = 30$
3 и 5: $\left(\begin{array}{rr} 11 & 15 \\ 4 & 6 \end{array}\right) \vec{x} = \left(\begin{array}{r} 16 \\ 24 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 30 \\ 21 \end{array}\right) \implies s = 30$
4 и 5: $\left(\begin{array}{rr} 22 & 8 \\ 4 & 6 \end{array}\right) \vec{x} = \left(\begin{array}{r} 14 \\ 24 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 30 \\ 21 \end{array}\right) \implies s = 30$

Теперь заметим, что $s = 30$ встретилось чаще всего, а значит это и будет правильным секретом.

Врёт участник №2

Задание C1⁴ (0.3)

Секрет разделили при помощи схемы Шамира над полем $\ZZ_{13}$. Нужно его восстановить.

Даны следующие точки: $ \left(1, 11\right), \left(2, 5\right), \left(3, 7\right) $

Ответ: $s = 12$, причём $f(x) = 4 x^{2} + 8 x + 12$

Задание C2⁴ (0.45)

Для реализации схемы Шамира в качестве поля взяли $\ZZ_{256}$. Восстановить секрет могут $3$ участников, но вам известны лишь $3 - 1$ точка: $\left(2, 64\right), \left(3, 253\right)$

Необходимо выяснить чётность секрета.

Авторское решение

Пусть $y = c_0 + c_1x + c_2x^2$

Составим СЛАУ и решим её: $\left(\begin{array}{rrr} 1 & 2 & 4 \\ 1 & 3 & 9 \end{array}\right) \vec{c} = \left(\begin{array}{r} 64 \\ 253 \end{array}\right) \implies \vec{c} = \left(\begin{array}{r} -314 \\ 189 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ -\frac{5}{6} \\ \frac{1}{6} \end{array}\right)$ Здесь видно, что $t$ должно делиться на $ 6 $, иначе результат не будет представим в кольце вычетов. Следовательно $t$ будет чётно, а значит сам секрет будет чётен

P.S. Секрет был $s=50$

Задание C3⁴ (0.7)

При помощи схемы Шамира был разделён секрет. Вам, как участнику схемы, досталась точка $\left(4, 6\right)$. Точки других участников вы точно не знаете, но уверены, что они имеют $x\in{ 1, 2, 3 }$.

Необходимо, чтобы в результате восстановления значение секрета изменилось на $40$. Какую точку вы должны назвать?

Решение:

Проведём многочлен через точки $\left[\left(1, 0\right), \left(2, 0\right), \left(3, 0\right), \left(0, 40\right)\right]$: в нуле равен $40$, в точках остальных участников равен нулю. Получим многочлен $22 x^{3} + 40 x^{2} + 27 x + 40$ (искать целиком не обязательно на самом деле)

Нам нужно только его значение в точке $x=4$; там он равен $3$.

Теперь прибавим это к известному выданному $y$ и получим $y’ = 6 + 3 = 9$.

Значит нужно назвать точку $(4, 9)$

P.S. Процесс восстановления:

Через точки $\left[\left(1, 21\right), \left(2, 37\right), \left(3, 10\right), \left(4, 6\right)\right]$ проходит $f(x) = 11 x^{3} + 20 x^{2} + 8 x + 25$

Но в результате атаки через $\left[\left(1, 21\right), \left(2, 37\right), \left(3, 10\right), \left(4, 9\right)\right]$ был проведён $f’(x) = 33 x^{3} + 17 x^{2} + 35 x + 22$.

Получили: $s = f(0) = 25$ и $s = f’(0) = 22$, что и требовалось

Вариант 5

Задание A1⁵ (0.3)

Секрет разделён при помощи простейшей $(n,n)$-схемы, $n = 3$. Необходимо его восстановить. В качестве поля используется кольцо многочленов степени не выше $3$ над кольцом $\ZZ_{11}$

Дано:

$ s = 9 x^{3} + 3 x^{2} + 6 x + 9 $
$ v_{2} = 9 x^{3} + x^{2} + 5 x + 7 $
$ v_{3} = 5 x^{3} + 2 x^{2} + 4 x + 8 $

Найти: $ v_{1} $

Ответ: $ v_{1} = 6 x^{3} + 8 x + 5 $

Задание A2⁵ (0.45)

Вам дана ASCII строка: crypto. Необходимо её при помощи простейшей $(n,n)$ схемы разделить между $n=4$ участниками.

Использовать для вычислений модуль более $10000$ не допускается.

Выпишите какой набор чисел получит каждый из участников.

Авторское решение: Переведём строку в байты по таблице ASCII: $\left[99, 114, 121, 112, 116, 111\right]$.

Теперь разделим: $\left(\begin{array}{rrrrrr} 244 & 143 & 145 & 206 & 81 & 201 \\ 130 & 37 & 132 & 69 & 214 & 113 \\ 68 & 4 & 92 & 214 & 169 & 150 \\ 169 & 186 & 8 & 135 & 164 & 159 \end{array}\right)$

Задание A3⁵ (0.7)

Есть четыре участника: $a, b, c, d$. Вам дана булева формула $((d\vee c)\vee ((d\wedge a)\vee b))\wedge (d\wedge c)$. Ваша задача — разделить секрет $s = 29$ при помощи простейшей $(n, n)$-схемы над полем $\ZZ_{47}$ таким образом, чтобы его могли восстановить тогда и только тогда, когда эта функция, будучи применена к присутствующим участникам, принимает значение истины.

Возможный ответ:

Секретная информация:

Участник a знает: $s_5 = 28$
Участник b знает: $s_6 = 23$
Участник c знает: $s_4 = 0$, $s = 29$
Участник d знает: $s_3 = 25$, $s_5 = 28$, $s = 29$

Переменные объявлены так, что:

$s = s_1 + s_2$
$s_1 = s_3 + s_4$
$s_2 = s_5 + s_6$

И тогда:$s_1 = 25$, $s_2 = 4$, $s_3 = 25$, $s_4 = 0$, $s_5 = 28$, $s_6 = 23$

Задание B1⁵ (0.3)

Необходимо разделить секрет $s = 10, s \in \ZZ_{11}$ между $5$ участниками так, чтобы любые $4$ могли его восстановить. Выпишите, что каждый участник знает.
Затем выбрать любых $4$ участников и восстановить секрет обратно.

Нужно использовать схему Блэкли.

Авторское решение:

Секрет поместим в точку $\left(10,\,6,\,0,\,0\right)$. Он находится в первой её координате.

Проведём через эту точку плоскости. Здесь и далее $\vec{x}$ - вектор-столбец

$ \left(\begin{array}{rrrr} 0 & 6 & 0 & 2 \end{array}\right) \vec{x} = 3 $
$ \left(\begin{array}{rrrr} 9 & 9 & 9 & 1 \end{array}\right) \vec{x} = 1 $
$ \left(\begin{array}{rrrr} 4 & 9 & 2 & 7 \end{array}\right) \vec{x} = 6 $
$ \left(\begin{array}{rrrr} 7 & 4 & 7 & 2 \end{array}\right) \vec{x} = 6 $
$ \left(\begin{array}{rrrr} 7 & 5 & 7 & 0 \end{array}\right) \vec{x} = 1 $

Тогда каждый участник обладает следующим набором чисел:

$ \left[0, 6, 0, 2, 3\right] $
$ \left[9, 9, 9, 1, 1\right] $
$ \left[4, 9, 2, 7, 6\right] $
$ \left[7, 4, 7, 2, 6\right] $
$ \left[7, 5, 7, 0, 1\right] $

Чтобы восстановить секрет достаточно решить СЛАУ, после чего извлечь секрет из первой координаты. $\left(\begin{array}{rrrr} 7 & 5 & 7 & 0 \\ 4 & 9 & 2 & 7 \\ 9 & 9 & 9 & 1 \\ 7 & 4 & 7 & 2 \end{array}\right) \vec{x} = \left(\begin{array}{r} 1 \\ 6 \\ 1 \\ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 10 \\ 6 \\ 0 \\ 0 \end{array}\right) \implies s = 10$

Задание B2⁵ (0.45)

Для вычислений использовалось поле $\ZZ_{7}$.

В схеме секрет разделяется так, что лишь трое могут его восстановить. Вам даны две плоскости:

$ 3x_1 + 6x_2 + 2x_3 = 0 $
$ 1x_1 + 0x_2 + 6x_3 = 1 $

Необходимо перечислить все 7 точек, в которых может находиться секрет.

Авторское решение

Составим и решим СЛАУ на координаты точек пересечения:

\[\left(\begin{array}{rrr} 3 & 6 & 2 \\ 1 & 0 & 6 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \\ 1 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 1 \\ 3 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ 5 \\ 1 \end{array}\right), t \in \ZZ_{7}\]

Остаётся перебрать все значения $t$ и получить следующие варианты: $\vec{x} \in \left[\left(\begin{array}{r} 1 \\ 3 \\ 0 \end{array}\right), \left(\begin{array}{r} 2 \\ 1 \\ 1 \end{array}\right), \left(\begin{array}{r} 3 \\ 6 \\ 2 \end{array}\right), \left(\begin{array}{r} 4 \\ 4 \\ 3 \end{array}\right), \left(\begin{array}{r} 5 \\ 2 \\ 4 \end{array}\right), \left(\begin{array}{r} 6 \\ 0 \\ 5 \end{array}\right), \left(\begin{array}{r} 0 \\ 5 \\ 6 \end{array}\right)\right]$

Задание B3⁵ (0.7)

Участники назвали следующие гиперплоскости:

$36x_1 + 2x_2 = 26$
$20x_1 + 34x_2 = 35$
$24x_1 + 1x_2 = 0$
$8x_1 + 28x_2 = 8$
$18x_1 + 11x_2 = 6$

Для вычислений использовалось поле $\ZZ_{37}$

Авторское решение:

Переберём все пары участников, для каждой вычислим секрет:

1 и 2: $\left(\begin{array}{rr} 36 & 2 \\ 20 & 34 \end{array}\right) \vec{x} = \left(\begin{array}{r} 26 \\ 35 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 11 \\ 0 \end{array}\right) \implies s = 11$
1 и 3: $\left(\begin{array}{rr} 36 & 2 \\ 24 & 1 \end{array}\right) \vec{x} = \left(\begin{array}{r} 26 \\ 0 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 4 \\ 15 \end{array}\right) \implies s = 4$
1 и 4: $\left(\begin{array}{rr} 36 & 2 \\ 8 & 28 \end{array}\right) \vec{x} = \left(\begin{array}{r} 26 \\ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 4 \\ 15 \end{array}\right) \implies s = 4$
1 и 5: $\left(\begin{array}{rr} 36 & 2 \\ 18 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 26 \\ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 17 \\ 3 \end{array}\right) \implies s = 17$
2 и 3: $\left(\begin{array}{rr} 20 & 34 \\ 24 & 1 \end{array}\right) \vec{x} = \left(\begin{array}{r} 35 \ 0 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 4 \ 15 \end{array}\right) \implies s = 4$
2 и 4: $\left(\begin{array}{rr} 20 & 34 \ 8 & 28 \end{array}\right) \vec{x} = \left(\begin{array}{r} 35 \ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 4 \ 15 \end{array}\right) \implies s = 4$
2 и 5: $\left(\begin{array}{rr} 20 & 34 \ 18 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 35 \ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 17 \ 3 \end{array}\right) \implies s = 17$
3 и 4: $\left(\begin{array}{rr} 24 & 1 \ 8 & 28 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \ 8 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 4 \ 15 \end{array}\right) \implies s = 4$
3 и 5: $\left(\begin{array}{rr} 24 & 1 \ 18 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 0 \ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 9 \ 6 \end{array}\right) \implies s = 9$
4 и 5: $\left(\begin{array}{rr} 8 & 28 \ 18 & 11 \end{array}\right) \vec{x} = \left(\begin{array}{r} 8 \ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 13 \ 23 \end{array}\right) \implies s = 13$

Теперь заметим, что $s = 4$ встретилось чаще всего, а значит это и будет правильным секретом.

Врёт участник №5

Задание C1⁵ (0.3)

Секрет разделили при помощи схемы Шамира над полем $\ZZ_{13}$. Нужно его восстановить.

Даны следующие точки: $ \left(1, 12\right), \left(2, 0\right), \left(3, 8\right) $

Ответ: $s = 5$, причём $f(x) = 10 x^{2} + 10 x + 5$

Задание C2⁵ (0.45)

Для реализации схемы Шамира в качестве поля взяли $\ZZ_{256}$. Восстановить секрет могут $3$ участников, но вам известны лишь $3 - 1$ точка: $\left(2, 177\right), \left(3, 40\right)$

Необходимо выяснить чётность секрета.

Авторское решение

Пусть $y = c_0 + c_1x + c_2x^2$

Составим СЛАУ и решим её: $\left(\begin{array}{rrr} 1 & 2 & 4 \\ 1 & 3 & 9 \end{array}\right) \vec{c} = \left(\begin{array}{r} 177 \\ 40 \end{array}\right) \implies \vec{c} = \left(\begin{array}{r} 451 \\ -137 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ -\frac{5}{6} \\ \frac{1}{6} \end{array}\right)$ Здесь видно, что $t$ должно делиться на $ 6 $, иначе результат не будет представим в кольце вычетов. Следовательно $t$ будет чётно, а значит сам секрет будет нечётен

P.S. Секрет был $s=123$

Задание C3⁵ (0.7)

При помощи схемы Шамира был разделён секрет. Вам, как участнику схемы, досталась точка $\left(4, 21\right)$. Точки других участников вы точно не знаете, но уверены, что они имеют $x\in{ 1, 2, 3 }$.

Необходимо, чтобы в результате восстановления значение секрета изменилось на $10$. Какую точку вы должны назвать?

Решение:

Проведём многочлен через точки $\left[\left(1, 0\right), \left(2, 0\right), \left(3, 0\right), \left(0, 10\right)\right]$: в нуле равен $10$, в точках остальных участников равен нулю. Получим многочлен $19 x^{3} + 10 x^{2} + 23 x + 10$ (искать целиком не обязательно на самом деле)

Нам нужно только его значение в точке $x=4$; там он равен $21$.

Теперь прибавим это к известному выданному $y$ и получим $y’ = 21 + 21 = 11$.

Значит нужно назвать точку $(4, 11)$

P.S. Процесс восстановления:

Через точки $\left[\left(1, 27\right), \left(2, 17\right), \left(3, 18\right), \left(4, 21\right)\right]$ проходит $f(x) = 14 x^{3} + 30 x^{2} + 19 x + 26$

Но в результате атаки через $\left[\left(1, 27\right), \left(2, 17\right), \left(3, 18\right), \left(4, 11\right)\right]$ был проведён $f’(x) = 2 x^{3} + 9 x^{2} + 11 x + 5$.

Получили: $s = f(0) = 26$ и $s = f’(0) = 5$, что и требовалось

Вариант 6

Задание A1⁶ (0.3)

Дано:

$ v_{1} = 3 x^{2} + 6 x + 10 $
$ v_{2} = 3 x^{2} + 20 x + 1 $
$ v_{3} = 4 x^{2} + 25 x + 27 $

Найти: $ s $

Ответ: $ s = 10 x^{2} + 22 x + 9 $

Задание A2⁶ (0.45)

Вам дана ASCII строка: Botay. Необходимо её при помощи простейшей $(n,n)$ схемы разделить между $n=5$ участниками.

Использовать для вычислений модуль более $10000$ не допускается.

Выпишите какой набор чисел получит каждый из участников.

Авторское решение: Переведём строку в байты по таблице ASCII: $\left[66, 111, 116, 97, 121\right]$.

Теперь разделим: $\left(\begin{array}{rrrrr} 3 & 198 & 181 & 183 & 222 \\ 224 & 89 & 65 & 0 & 83 \\ 60 & 224 & 54 & 78 & 55 \\ 89 & 47 & 104 & 187 & 25 \\ 202 & 65 & 224 & 161 & 248 \end{array}\right)$

Задание A3⁶ (0.7)

Есть четыре участника: $a, b, c, d$. Вам дана булева формула $((d\vee c)\wedge (a\wedge c))\vee (a\vee b)$. Ваша задача — разделить секрет $s = 31$ при помощи простейшей $(n, n)$-схемы над полем $\ZZ_{47}$ таким образом, чтобы его могли восстановить тогда и только тогда, когда эта функция, будучи применена к присутствующим участникам, принимает значение истины.

Возможный ответ:

Секретная информация:

Участник a знает: $s_1 = 1$, $s_5 = 44$
Участник b знает: $s_6 = 33$
Участник c знает: $s_4 = 33$, $s_1 = 1$
Участник d знает: $s_3 = 15$

Переменные объявлены так, что:

$s = s_1 + s_2$
$s_1 = s_3 + s_4$
$s_2 = s_5 + s_6$

И тогда:$s_1 = 1$, $s_2 = 30$, $s_3 = 15$, $s_4 = 33$, $s_5 = 44$, $s_6 = 33$

Задание B1⁶ (0.3)

Необходимо разделить секрет $s = 12, s \in \ZZ_{13}$ между $5$ участниками так, чтобы любые $3$ могли его восстановить. Выпишите, что каждый участник знает.
Затем выбрать любых $3$ участников и восстановить секрет обратно.

Нужно использовать схему Блэкли.

Авторское решение:

Секрет поместим в точку $\left(12,\,6,\,3\right)$. Он находится в первой её координате.

Проведём через эту точку плоскости. Здесь и далее $\vec{x}$ - вектор-столбец

$ \left(\begin{array}{rrr} 12 & 0 & 4 \end{array}\right) \vec{x} = 0 $
$ \left(\begin{array}{rrr} 3 & 11 & 3 \end{array}\right) \vec{x} = 7 $
$ \left(\begin{array}{rrr} 4 & 7 & 5 \end{array}\right) \vec{x} = 1 $
$ \left(\begin{array}{rrr} 12 & 12 & 4 \end{array}\right) \vec{x} = 7 $
$ \left(\begin{array}{rrr} 11 & 11 & 3 \end{array}\right) \vec{x} = 12 $

Тогда каждый участник обладает следующим набором чисел:

$ \left[12, 0, 4, 0\right] $
$ \left[3, 11, 3, 7\right] $
$ \left[4, 7, 5, 1\right] $
$ \left[12, 12, 4, 7\right] $
$ \left[11, 11, 3, 12\right] $

Чтобы восстановить секрет достаточно решить СЛАУ, после чего извлечь секрет из первой координаты. $\left(\begin{array}{rrr} 4 & 7 & 5 \\ 3 & 11 & 3 \\ 11 & 11 & 3 \end{array}\right) \vec{x} = \left(\begin{array}{r} 1 \\ 7 \\ 12 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 12 \\ 6 \\ 3 \end{array}\right) \implies s = 12$

Задание B2⁶ (0.45)

Для вычислений использовалось поле $\ZZ_{7}$.

В схеме секрет разделяется так, что лишь трое могут его восстановить. Вам даны две плоскости:

$ 5x_1 + 6x_2 + 2x_3 = 4 $
$ 2x_1 + 4x_2 + 2x_3 = 6 $

Необходимо перечислить все 7 точек, в которых может находиться секрет.

Авторское решение

Составим и решим СЛАУ на координаты точек пересечения:

\[\left(\begin{array}{rrr} 5 & 6 & 2 \\ 2 & 4 & 2 \end{array}\right) \vec{x} = \left(\begin{array}{r} 4 \\ 6 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 1 \\ 1 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ 2 \\ 2 \end{array}\right), t \in \ZZ_{7}\]

Остаётся перебрать все значения $t$ и получить следующие варианты: $\vec{x} \in \left[\left(\begin{array}{r} 1 \\ 1 \\ 0 \end{array}\right), \left(\begin{array}{r} 2 \\ 3 \\ 2 \end{array}\right), \left(\begin{array}{r} 3 \\ 5 \\ 4 \end{array}\right), \left(\begin{array}{r} 4 \\ 0 \\ 6 \end{array}\right), \left(\begin{array}{r} 5 \\ 2 \\ 1 \end{array}\right), \left(\begin{array}{r} 6 \\ 4 \\ 3 \end{array}\right), \left(\begin{array}{r} 0 \\ 6 \\ 5 \end{array}\right)\right]$

Задание B3⁶ (0.7)

Участники назвали следующие гиперплоскости:

$13x_1 + 17x_2 = 3$
$5x_1 + 13x_2 = 1$
$26x_1 + 12x_2 = 17$
$13x_1 + 20x_2 = 16$
$23x_1 + 8x_2 = 13$

Для вычислений использовалось поле $Z_{29}$

Авторское решение:

Переберём все пары участников, для каждой вычислим секрет:

1 и 2: $\left(\begin{array}{rr} 13 & 17 \\ 5 & 13 \end{array}\right) \vec{x} = \left(\begin{array}{r} 3 \\ 1 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 12 \\ 20 \end{array}\right) \implies s = 12$
1 и 3: $\left(\begin{array}{rr} 13 & 17 \\ 26 & 12 \end{array}\right) \vec{x} = \left(\begin{array}{r} 3 \\ 17 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 14 \end{array}\right) \implies s = 2$
1 и 4: $\left(\begin{array}{rr} 13 & 17 \\ 13 & 20 \end{array}\right) \vec{x} = \left(\begin{array}{r} 3 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 14 \end{array}\right) \implies s = 2$
1 и 5: $\left(\begin{array}{rr} 13 & 17 \\ 23 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 3 \\ 13 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 14 \end{array}\right) \implies s = 2$
2 и 3: $\left(\begin{array}{rr} 5 & 13 \\ 26 & 12 \end{array}\right) \vec{x} = \left(\begin{array}{r} 1 \\ 17 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 14 \\ 17 \end{array}\right) \implies s = 14$
2 и 4: $\left(\begin{array}{rr} 5 & 13 \\ 13 & 20 \end{array}\right) \vec{x} = \left(\begin{array}{r} 1 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 25 \\ 15 \end{array}\right) \implies s = 25$
2 и 5: $\left(\begin{array}{rr} 5 & 13 \\ 23 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 1 \\ 13 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 21 \\ 21 \end{array}\right) \implies s = 21$
3 и 4: $\left(\begin{array}{rr} 26 & 12 \\ 13 & 20 \end{array}\right) \vec{x} = \left(\begin{array}{r} 17 \\ 16 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 14 \end{array}\right) \implies s = 2$
3 и 5: $\left(\begin{array}{rr} 26 & 12 \\ 23 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 17 \\ 13 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 14 \end{array}\right) \implies s = 2$
4 и 5: $\left(\begin{array}{rr} 13 & 20 \\ 23 & 8 \end{array}\right) \vec{x} = \left(\begin{array}{r} 16 \\ 13 \end{array}\right) \implies \vec{x} = \left(\begin{array}{r} 2 \\ 14 \end{array}\right) \implies s = 2$

Теперь заметим, что $s = 2$ встретилось чаще всего, а значит это и будет правильным секретом.

Врёт участник №2

Задание C1⁶ (0.3)

Секрет разделили при помощи схемы Шамира над полем $\ZZ_{13}$. Нужно его восстановить.

Даны следующие точки: $ \left(1, 7\right), \left(2, 8\right), \left(3, 3\right) $

Ответ: $s = 0$, причём $f(x) = 10 x^{2} + 10 x$

Задание C2⁶ (0.45)

Для реализации схемы Шамира в качестве поля взяли $\ZZ_{64}$. Восстановить секрет могут $3$ участников, но вам известны лишь $3 - 1$ точка: $\left(2, 61\right), \left(3, 62\right)$

Необходимо выяснить чётность секрета.

Авторское решение

Пусть $y = c_0 + c_1x + c_2x^2$

Составим СЛАУ и решим её: $\left(\begin{array}{rrr} 1 & 2 & 4 \\ 1 & 3 & 9 \end{array}\right) \vec{c} = \left(\begin{array}{r} 61 \\ 62 \end{array}\right) \implies \vec{c} = \left(\begin{array}{r} 59 \\ 1 \\ 0 \end{array}\right) + t\left(\begin{array}{r} 1 \\ -\frac{5}{6} \\ \frac{1}{6} \end{array}\right)$ Здесь видно, что $t$ должно делиться на $ 6 $, иначе результат не будет представим в кольце вычетов. Следовательно $t$ будет чётно, а значит сам секрет будет нечётен

P.S. Секрет был $s=41$

Задание C3⁶ (0.7)

При помощи схемы Шамира был разделён секрет. Вам, как участнику схемы, досталась точка $\left(1, 16\right)$. Точки других участников вы точно не знаете, но уверены, что они имеют $x\in{ 2, 3, 4 }$.

Необходимо, чтобы в результате восстановления значение секрета изменилось на $30$. Какую точку вы должны назвать?

Решение:

Проведём многочлен через точки $\left[\left(2, 0\right), \left(3, 0\right), \left(4, 0\right), \left(0, 30\right)\right]$: в нуле равен $30$, в точках остальных участников равен нулю. Получим многочлен $9 x^{3} + x^{2} + 29 x + 30$ (искать целиком не обязательно на самом деле)

Нам нужно только его значение в точке $x=1$; там он равен $28$.

Теперь прибавим это к известному выданному $y$ и получим $y’ = 16 + 28 = 3$.

Значит нужно назвать точку $(1, 3)$

P.S. Процесс восстановления:

Через точки $\left[\left(1, 16\right), \left(2, 18\right), \left(3, 16\right), \left(4, 39\right)\right]$ проходит $f(x) = 39 x^{3} + 10 x^{2} + 27 x + 22$

Но в результате атаки через $\left[\left(1, 3\right), \left(2, 18\right), \left(3, 16\right), \left(4, 39\right)\right]$ был проведён $f’(x) = 7 x^{3} + 11 x^{2} + 15 x + 11$.

Получили: $s = f(0) = 22$ и $s = f’(0) = 11$, что и требовалось