Проверьте

Некоторая цифра зашифрована шифрсистемой RSA, получился шифртекст 125. Известен модуль m=391 и открытый ключ е=3. Секретный ключ не известен. Требуется дешифрование. Я сделал, но не уверен-7.
Задача олимпиады ИКСИ.

Ответ будет 5. Где-то у вас ошибка. Все решение расписывать не буду, но 391=17*23. тогда функция Эйлера ф(391)=16*22=352.

3^40 mod 352=1. d=3^39 mod 352 = 235. А теперь осталось только возвести шифр-текст в степень d по mod 391. Получим 5, хотя это и так видно.

Почему 3^40 mod 352=1. По теореме Эйлера 3^f(352)=1mod352,
f(352)=160, а не 40?

Чтобы убедиться в том, что [m]3^{40} =1\pmod{352}[/m] мы можем прибегнуть к более сильной теореме, а именно теореме о строении мультипликативной группы [m]\left ( \mathbb{Z}/n\mathbb{Z} \right )^{\ast}[/m] кольца [m]\mathbb{Z}/n\mathbb{Z}[/m] (эта теорема намного сильнее теоремы Эйлера, которая о самом кольце практически ничего не говорит).

Если [m]n=2^kp_1^{k_1}\cdots p_t^{k_t}[/m] --- представление числа [m]n[/m] в виде произведения примарных чисел, то:

[m]\left ( \mathbb{Z}/n\mathbb{Z} \right )^{\ast}\simeq \left ( \mathbb{Z}/2^k\mathbb{Z} \right )^{\ast}\times\left ( \mathbb{Z}/p_1^{k_1}\mathbb{Z} \right )^{\ast}\times\cdots\times\left ( \mathbb{Z}/p_t^{k_t}\mathbb{Z} \right )^{\ast}.[/m]

Если [m]n=1,2[/m], то [m]\left ( \mathbb{Z}/2^k\mathbb{Z} \right )^{\ast}\simeq \mathbb{Z}/1\mathbb{Z}.[/m]

Если [m]n\ge 3[/m], то [m]\left ( \mathbb{Z}/2^k\mathbb{Z} \right )^{\ast}\simeq \mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2^{k-2}\mathbb{Z}.[/m]

Если [m]p>2[/m], то [m]\left ( \mathbb{Z}/p^k\mathbb{Z} \right )^{\ast}\simeq \mathbb{Z}/(p-1)p^{k-1}\mathbb{Z}.[/m]

В нашем случае [m]\left ( \mathbb{Z}/352\mathbb{Z} \right )^{\ast}\simeq \left ( \mathbb{Z}/2\mathbb{Z} \right )\times \left ( \mathbb{Z}/2^3\mathbb{Z} \right )\times\left ( \mathbb{Z}/10\mathbb{Z} \right ),[/m]

из чего с очевидностью следует, что экспонента этой группы есть 40. Т.е. как только [m](k,352)=1[/m], то [m]k^{40}=1 \pmod{352}[/m].

Вы для кого и зачем это излагаете?

Для Евгения)

Хорошо, быть может Евгению это понятно. Моему Макиму совсем не понятно. А вот мне не понятно следующее. Как Кругликов умудрился получить дешифрование совсем без секретного ключа и без всех Ваших теорий.

> Как Кругликов умудрился получить дешифрование совсем без секретного ключа и без всех Ваших теорий.

Он использует секретную технику КГБ :-)

На его решении можно заряжать воду. Ну тут пример такой попался. Можно придумать такой пример, что Кругликов расшифрует его только лет через 10 своим методом.

Меня удивляют Ваши заявления.
Была запрошена помощь по одной конкретной задаче, задаче, хотя и олимпиадной, но все же школьной. Я показал, как можно решить именно эту задачу не так, как это делают математики, не специалисты в области криптоанализа.
Это небольшая тайна, что существуют математические методы с грифом, её преподают только в ИКСИ, именно поэтому его выпускники делают то, что не делают открытые математики.

(это степень открытой экспоненты в мультипликативной группе кольца [m]\mathbb{Z}_n[/m]) раз считать [m]e[/m]-ю степень по модулю [m]n[/m]. Я думаю, что жутко плохо (хотя я и не знаю как обстоят дела на фронтовой линии атаки на RSA; мне умные люди когда-то сказали, что e должна выбираться с учетом [m]n[/m], а не только взаимной простоты с [m]\varphi(n)[/m] и большого числа единиц в двоичной записи, а [m]e=3[/m] вообще брать нельзя, там есть какой-то хитрый трюк для этого случая).

Так дешифровальные службы только потому и продолжают существовать и работать, что к каждому случаю подходят индивидуально, находя слабости(ошибки) при выборе параметров (ключей) используемых противником шифрсистем.
Вот в данной рассматриваемой задаче я это и использовал, это и требовалось от школьника, желающего стать слушателем ИКСИ. Его же готовят стать криптоаналитиком, а не математиком.
Как известно из истории криптослужб, практических успехов в дешифровании редко добивались успеха «чистые» математики. Этого добивались люди, имеющие в качестве базового образования физику.
Приведу также свой метод факторизации модуля
При известном модуле n=pq и неизвестных простых сомножителях p и q, имея формулу: f(n)=(p-1)(q-1)=n+1-(p+q) , можно образовать систему уравнений:
pq = n и p+q = n+1−f(n). (2)
Для оценки f(n) моно использовать показатель P(2): 2^a=1(mod391) , f(n)= 2kP(2) , где k=1,2,3.… опробываемый множитель. При модуле n=391 Р(2)=176 и к=2.

Дешифрование путём шифрования шифрованного текста открытым ключом (секретный ключ вообще не нужен).
125
80
181
226
74
148
11
158
295
97
79
379
227
318
28
56
57
250
249
5
125-повторился шифробозначение, значит предыдущее значение 5 есть открытый текст
80
181
226

Ой всё. Все бы олимпиады так решали. "А кратчайшее расстояние можно и линейкой посчитать. А площадь под кривой гипсом."

Вы математик, а я практик -криптоаналитик ( с воинским званием и докторской степенью).В этом наше различие, и различие в решениях.

А то, что сделал Б-М Кругликов , как связано со всей этой теорией, которая явно не для школьников. Опять показываете свою ученость шклярам.

На занятии по разбору криптостойкости системы RSA студент(слушатель) задал интересный(с моей точки зрения) вопрос, который выкладываю здесь.
Пусть получили шифрованное сообщение системы RSA, открытый ключ знаем, зашифруем им это шифрованное сообщение, потом снова зашифруем и т.д. Что увидим в этом процессе?

Существует ли метод дешифрования криптограммы, зашифрованной шифром Виженера. Исходные данные: открытый текст-английский (знаю вероятности букв) и имею шифрованный текст криптограммы.

Пошел на олимпиаду ИКСИ без подготовки, получил вот такую задачу, как к ней подходить?
Сообщение было зашифровано шифром Виженера с использованием ключевого слова из пяти букв. Результат зашифрования выглядит так:

мхлщлифцбдюгишсптаивпбьдюолдьуэюыйемхл

Восстановите исходное сообщение и ключевое слово.

ЗАДАЧА. Найти закономерности , использовать теорию полей Галуа.
11101111001010111110111101011111010101001110100111010011101001110100111010011101001
11111010101001001111010111010110010110010001010111101010010010000000010001000101000
01110100110110111011111000010000100001010100000100101100101100110010101111111010010
10100110001101110000111
Это экзаменационная задача 1-шго курса по специальности "криптозащита информации". Почти никто не сделал.