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

Теория чисел на Верченко

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

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

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

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

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

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

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

Задача 1#90275

Каждый из трех владельцев криптокошельков имеет на своем счету по 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)$

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

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

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

Задача 2#90279

В криптосистеме 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)$

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

Задача 3#90281

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

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

Задача 4#68238

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

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

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

Подсказка 1

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

Подсказка 2

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

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

Заметим, что

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

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

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

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

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

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

Ответ: 12345678

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

Задача 5#99574

Найдите наибольшее пятизначное число, которое в $51$ раз больше квадрата суммы своих цифр. Решение обоснуйте.

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

Подсказка 1

Давайте введём переменные и составим уравнение из условия. Решать мы должны в целых числах, значит, имеет смысл зацепиться за делимость!

Подсказка 2

Наше число должно делиться на 3. Но как это может повлиять на сумму?

Подсказка 3

Сумма тоже будет делиться на 3. Продолжая рассуждать, сможем оценить сумму цифр и разобраться, какие значения она может принимать ;)

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

Обозначим $x$ — искомое число, $s$ - сумма его цифр. Тогда $x =3⋅17⋅s2.$ Следовательно, $x$ делится нацело на $3.$ По признаку делимости на $3,$ число $s$ делится на $3.$ Но тогда $x$ делится на $9.$ По признаку делимости на $9,s$ делится на $9.$ Так как искомое число пятизначное, то для $s$ возможны $5$ вариантов: $s =9,s= 18,s= 27,s =36,s= 45.$ Для каждого $s,$ соответственно, находим: $x =4131,x =16524,x= 37179,x= 66096,x= 103275.$ Первое и последнее — не пятизначные, у четвёртого сумма цифр не равна $36.$ Подходящие: $x= 16524,x =37179.$

Ответ:

$37179$ или $16524$

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

Задача 6#99588

Для зашифрования осмысленного слова его буквы заменили числами $x ,x ,...,x 1 2 n$ по таблице.

Затем выбирали четные натуральные числа $p$ и $q$ и для каждого числа $xi$ из соотношений

xi = yi+ pzi,zi =yi+ qxi

нашли целые числа $yi$ и $zi$ .

Потом по формулам

′ zi = r32(zi),i= 1,...,n

получили числа

z′,...,z′ 1 n

(где $r32(a)$ — остаток от деления числа $a$ на 32), которые вновь заменили буквами согласно таблице:

$|---|---|---|---|----|---|----|---|---|---|----|---|----|---|---|---|----|---|---|----|---|---|---|----|----|---|----|---|---|----|----| |А--|Б--|-В-|-Г-|-Д--|Е--|Ж---|З--|И--|-К-|-Л--|М--|-Н--|О--|-П-|-Р-|-C--|Т--|У--|-Ф--|Х--|Ц--|-Ч-|-Ш--|-Щ--|-Б-|-Ы--|-Б-|-Э-|-Ю--|-Я--| |0 | 1 | 2 | 3 | 4 |5 | 6 |7 | 8 | 9 | 10 |11 | 12 |13 |14 | 15 | 16 |17 |18 | 19 |20 |21 | 22 | 23 | 24 | 25 | 26 |27 | 28 | 29 | 30 | ----------------------------------------------------------------------------------------------------------------------------------------$

В результате получили вот что: ЖЯЮЦКР.

Найдите исходное слово, если известно, что оно начинается на букву В.

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

Подсказка 1

Нам надо явным образом связать x и z’ по модулю 32. Давайте тогда вычтем из первого равенство второе, чтобы у нас лишняя переменная y ушла. Тогда как можно связать x и z’?

Подсказка 2

Тогда выходит, что x(1 + q) = z’(1 + p) (mod 32). Если мы выразим (1 + q) через (1 + p) по модулю 32 с некоторыми константными коэффициентами, то мы сможем домножить на это модульное равенство наше равенство выше и после сокращения (1 + q) и (1 + p) в обеих частях мы получим явную связь x и z’. Стоит вспомнить, что мы ещё не использовали условие на первую букву!

Подсказка 3

Давайте теперь возьмем условие для первой буквы и посмотрим, что оно дает. Получается, что (1 + q) = 3(1 + p) (mod 16). Помножим на 3^-1 mod 16, и получим некоторое равенство, где коэффициент теперь у (1 + q). Тогда выходит, что c(1 + q) = (1 + p) (mod 32), где c = 11 или 27. А значит, получили явную связь на x и z’. Осталось проверить дешифровку на осмысленность и задача решена!

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

Рассмотрим произвольную букву открытого и шифрованного текстов. Для соответствующих им (по таблице) чисел $x$ и $z′$ выполняются равенства $x= y+ pz$ и $z =$ $y+ qx$ , при некотором $y,p$ и $q$ . При этом по условию $′ z= r32(z)$ . Используя свойство сравнений по модулю целого числа, получим: $′ ′ x − z = pz− qx(mod32)$ или $x(1+ q)=$ $′ z(1+p)(mod32)$ . Для дальнейшего решения будем пользоваться следующим свойством: если наибольший общий делитель чисел $a$ и $n$ равен $1,$ то сравнение $x= y(modn )$ равносильно $ax=$ $ay(modn)$ . Используя условие задачи для первой буквы открытого и шифрованного текста, получим равенство $2(1+q)= 6(1 +p)(mod32)$ . Заметим, что сравнение $6t= 2(mod32)$ имеет 2 решения по модулю $32:t= 11(mod32)$ , $t= 27(mod32)$ . Тогда получим, что $11⋅(1+q)= (1+p)(mod32)$ или $27⋅(1+ q)= (1+ p)(mod32)$ для каждого $t$ . Таким образом, $′ x =11z(mod32)$ или $′ x =27z(mod32)$ соответственно. Остается воспользоваться полученными соотношениями для остальных букв.