СПРОСИ ПРОФИ
👍
+1
👎 113

RSA

На занятии по разбору криптостойкости системы RSA студент(слушатель) задал интересный(с моей точки зрения) вопрос, который выкладываю здесь.
Пусть получили шифрованное сообщение системы RSA, открытый ключ знаем, зашифруем им это шифрованное сообщение, потом снова зашифруем и т.д. Что увидим в этом процессе?
криптография информатика обучение     #1   10 ноя 2014 09:41   Увидели: 32 клиента, 7 специалистов   Ответить
👍
+1
👎 1
Раз никто, то я:
Зашифруем и расшифруем сообщение "САВ" по алгоритму RSA. Для простоты возьмем небольшие числа — это сократит наши расчеты.
 Выберем p=3 and q=11.
 Определим n= 3*11=33.
 Hайдем (p-1)*(q-1)=20. Следовательно, d будет равно, например, 3: (d=3).
 Выберем число е по следующей формуле: (e*3) mod 20=1. Значит е будет равно, например, 7: (e=7).
 Представим шифруемое сообщение как последовательность чисел в диапозоне от 0 до 32 (не забывайте, что кончается на n-1). Буква А =1, В=2, С=3.
Теперь зашифруем сообщение, используя открытый ключ {7,33}
C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Теперь расшифруем данные, используя закрытый ключ {3,33}.
M1=(9^3) mod 33 =729 mod 33 = 3(С);
M2=(1^3) mod 33 =1 mod 33 = 1(А);
M3=(29^3) mod 33 = 24389 mod 33 = 2(В);

Данные расшифрованы!
Теперь 9(это шифрованная С) шифруем открытым ключом (7,33) – (9^7)mod33=15, (15)^7mod33=27, (27^7)mod33=3, (3^7)mod33=9. Получили повторение шифрованного текста, значит на предыдущем шаге был открытый текст.
Таким образом, ПОЛУЧЕН ОТКРЫТЫЙ ТЕКСТ БЕЗ ЗНАНИЯ ЗАКРЫТОГО КЛЮЧА!!!!
👍
+1
👎 1
Хотелось бы узнать у миносователей. Они поставили минусы потому, что:
-данный факт не интересен, не представляет научного и практического интереса,
-он уже хорошо известен
-прочее.
Думаю, что , если бы я здесь выложил решение гипотезы Кука, то все равно получил бы минусы.
Может не надо прятаться.
👍
0
👎 0
2-й и 3-й посты минусовал я, т.к. во втором Вы ничего не доказали (доказать нужно в общем случае, а не на примере конкретных чисел), а третий т.к. я считаю приведенную задачу неинтересной (RSA ИМХО самая скучная тема классического курса теории чисел).
👍
0
👎 0
Андрей Михайлович, а Вы могли бы доказать, что это не всегда. Хотя бы один противоречащий пример.
👍
0
👎 0
Мне задача не нравится, думать я над ней не хочу, как следствие привести контрпример не могу, но из этого, разумеется, ничего не следует.
👍
0
👎 0
Все равно спасибо.
👍
0
👎 0
И сколько ж раз нужно шифровать? Уж не получится ли, что быстрее n факторизуется?
👍
0
👎 0
>> -данный факт не интересен, не представляет научного и практического интереса <<

Никакого.
👍
+1
👎 1
Теоретически это может представлять практический интерес, но только в одном случае — если противник идиот (и сгенерил плохой публичный ключ) или сознательно подкладывает дезу.

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

В качестве упражнения для проверки студенческого идиотизма может и сгодится.
  #12   21 ноя 2014 21:44   Ответить
👍
+1
👎 1
Я немного о другом. Нет научного интереса в том, что кольцо вычетов по модулю n когда-то исчерпается. Про практический интерес возведения в степень и хранения остатков (по сравнению с тривиальной факторизацией n) — это вообще без комментариев.
👍
0
👎 0

Well... Putting this mash in simple terms, assuming that $m\in Z/p+Z/q$ is invertible, you just saying that a cyclic subgroup of $(Z/p+Z/q)^$ generated by $e$ is finite. Surely, its order divides $l.c.m(p-1,q-1)=|(Z/p+Z/q)^|$. Thus, after that number of steps, the sequence, you will see, starts to repeat. Abstractly $(Z/p+Z/q)^*$ is isomorphic to $Z/(p-1)+Z/(q-1)$ and for general primes $p,q>2$ $g.c.d(p-1,q-1)=2$, hence there is a message $m$ for which you have to run your procedure $(p-1)(q-1)/2$ times until you reach the original message and find the closed key using this particulal $m$.
You may ask then, what is expected number of steps for various m's. Again, abstractly $(Z/p+Z/q)^*$ is isomorphic to $Z/(p-1)+Z/(q-1)$ and the mean size of a cyclic subgroup generated by $m$, though has no closed expression, has an order equal to O(pq) (whatsever this mean for $p,q$ being fixed).

👍
+1
👎 1
Спасибо за ответ.
В практическом криптоанализе ничего доказывать не надо. Все строится на нахождении ошибок противника. Получил открытый текст-получи орден.
👍
+6
👎 6
А потом в открытом тексте обнаруживается деза и орденоносца отправляют в ссылку на остров Ратманова — крики чаек дешифровывать.
  #6   13 ноя 2014 15:49   Ответить

Задайте свой вопрос по информатике
профессионалам

Сейчас онлайн 75 репетиторов по информатике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
−1
👎 -11

Виженер   1 ответ

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

Проверьте   15 ответов

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

Задача ИКСИ   10 ответов

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

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

Восстановите исходное сообщение и ключевое слово.
  24 фев 2016 13:55  
👍
+2
👎 212

Еще криптозадача   12 ответов

Условие:
Каждую букву исходного сообщения заменили ее двузначным порядковым номером в русском алфавите согласно таблице
А Б В Г Д Е Ё Ж З И Й К Л М Н О П
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17
Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

Полученную цифровую последовательность разбили (справа налево) на трехзначные цифровые группы без пересечений и пропусков. Затем, каждое из…
  01 дек 2010 13:48  
ASK.PROFI.RU © 2020-2021