Консультация № 185145
11.01.2012, 15:06
51.94 руб.
0 47 1
Уважаемые эксперты! Пожалуйста, ответьте на вопрос:

Есть алгоритм ЭЦП RSA, его краткое описание (m - документ, N - некое известное всем большое число):
1. Абонент А: вычисление хеш-образа документа: h(m)
2. Абонент А: подписывает хеш-образ документ, зашифровывая полученный хеш-образ на своем секретном ключе d: sign_A(m)=(h(m))^d mod N
3. Абонент А формирует пару документ-подпись и отправляет абоненту B: {m, sign_a(m)}
4. Абонент B вычисляет хэш-образ полученного сообщения h(m’)
5. Абонент B расшифровывает подпись на открытом ключе e отправителя (абонента A): (sign_A(m))^e mod N = h(m)
6. Абонент B сравнивает две хэш-функции - если они равны, то значит подпись подлинная.

У меня спросили - зачем в данном алгоритме используем хэш-функцию, почему нельзя сразу шифровать сообщение m^e, и это будет подписью, и в итоге просто сравнивать полученное m и расшифрованную подпись m'.

Я пытался ответить:
1) Быстродействие - хэш-образ шифруется быстрее, т.к. он фиксированной длины, и шифровать удобнее, чем исходный текст.
Но это оказалось неверным с тем обоснованием, что быстродействия нет, что есть процессоры, которые сначала выполняют операцию m mod N, а потом результат шифруют. То есть и по длине, и по времени шифротекст практически равен в обоих случаях.
2) Было высказано предположение о контрольной сумме - но тоже неверно.

Так зачем же вообще используется хэш-функция в данном алгоритме?

Обсуждение

Неизвестный
11.01.2012, 21:51
общий
Не знаю, возможно ли такое. Число N простое, как и число e и d. По схеме шифрования-расшифрования, которую прилагаю, вроде как такая штука невозможна.
В любом случае - подобрать два текста, дающие одинаковый хеш-образ, тоже можно.
Прикрепленные файлы:
861b1626b5f7dc39b1f0546ff8822e9c.png
Неизвестный
11.01.2012, 21:59
общий
Данная схема выполняется при оригинальном сообщении меньше N. Так и предполагается, что N равно несколько десятков десятичных знаков, а x < N.
Неизвестный
12.01.2012, 06:34
общий
Смотрите, к примеру есть два документа:
4564545412787864540000000000000000
и
4712131484531231515000000000000000

и N = 10000000
Получаем mod N в обоих случаях равным нулю.

При этом Если мы применим хеш функцию к каждому документу, к примеру MD5(m),
то получим вот такие хеши:
ef97a615d464d1226d1ef89a6a413722
и
ca67598b79258ff444941abb5e00b089

и соответственно mod N получим разные.
Найти коллизию хеш-функции гораздо сложнее, а порой и нереально.
Неизвестный
12.01.2012, 11:20
общий
По алгоритму вроде как выбирают так, чтобы число N было больше исходного текста. Шифротекст может быть и больше N, но оригинал обязательно меньше. Тода не возникнет коллизии. А если N оказалось меньше исходного текста, то текст разбивается на несколько частей. Поправьте, если не так, но вроде так должно быть.
Неизвестный
12.01.2012, 11:32
общий
Текст нигде не разбивается ни на какие части. В алгоритме применяется хеширование полностью всего документа: h(m). Результат хеш-функции обычно 16 байт для многих алгоритмов хеширования, но бывают и другие по длине. Далее возводим в степень и берем mod N. Где N - некое произведние двух простых чисел p и q. Да, p и q выбираются большими, но они все равно по разрядности гораздо меньше, чем большинство документов.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 11:57
общий
Не согласен с Вашим ответом, Вы приводите частный случай, который не соответствует полноценному ответу на вопрос, помоему автор вопроса в мини-форуме правильно сам сформулировал ответ.
Об авторе:
to live is to die
Неизвестный
12.01.2012, 12:02
общий
Адресаты:
Ваше право не соглашаться. Я лишь дал ответ на конкретный вопрс, а именно, для чего используется хеш-функция и почему нельзя формировать ЭЦП напрямую из исходного документа.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 12:19
общий
так объясните, почему m^e не является подписью????
в Вашем ответе этого нет!
Об авторе:
to live is to die
Неизвестный
12.01.2012, 12:22
общий
Адресаты:
Вопрос был не в том, является это или нет подписью. А в том, для чего используется хеш-функция и почему нельзя формировать ЭЦП напрямую из исходного документа.

В моем ответе все подробно описано, почему именно так. В мини-форуме также привел дополнительный пример для автора вопроса.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 12:36
общий
вот выдержка из вопроса:
почему нельзя сразу шифровать сообщение m^e, и это будет подписью


про mod ничего не сказано, поэтому m^e может являться подписью!

не буду больше спорить, пусть автор вопроса или другие эксперты решают о правильности Вашего ответа.
Об авторе:
to live is to die
Неизвестный
12.01.2012, 12:41
общий
Адресаты:
Я и написал почему нельзя... потому что в этом случае будет множество коллизий, т.е. одинаковых подписей для разных документов.
Кстати, с днем рождения!
давно
Мастер-Эксперт
325460
1469
12.01.2012, 12:48
общий
Спасибо за поздравления :)


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

По определению цифровая подпись - это хеш зашифрованный на секретном ключе, тут спорить не буду.

Но кто мешает сказать, что хеш это m^e?
Об авторе:
to live is to die
Неизвестный
12.01.2012, 12:52
общий
Адресаты:
Пусть m = 4356432654625600000000000000000000
Некий документ с нулями в конце. Тогда в какую бы целую степень мы его не возвели, нулей в конце только больше станет.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 12:55
общий
а начало то разное всегда!
причем тут конец?
Об авторе:
to live is to die
Неизвестный
12.01.2012, 12:59
общий
Адресаты:
Если взять mod N, где N к примеру равно 1000, мы получим одинаковую подпись для разных документов, равную 0. Я првел простой пример с нулями в конце для лучшего понимания.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 13:01
общий
вот я Вам и пытаюсь сказать, что преподаватель про mod N ничего не говорил!
поэтому подписи разные!
Об авторе:
to live is to die
Неизвестный
12.01.2012, 13:03
общий
Адресаты:
Как это не говорил? Посмотрите 2 и 5 пункт в исходном вопросе автора, там именно применена операция mod N.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 13:10
общий
Вопрос
почему нельзя сразу шифровать сообщение m^e, и это будет подписью, и в итоге просто сравнивать полученное m и расшифрованную подпись m'.

это значит второй пункт алгоритма будет выглядеть так
sign_A(m)=m^e
абоненту отправляется B: {m, sign_a(m)}

так что... все же думаю вряд ли с коллизиями связано.
Надо уточнить у преподавателя что он имел ввиду.
Об авторе:
to live is to die
Неизвестный
12.01.2012, 13:14
общий
Адресаты:
Если Вы возведете в степень ВЕСЬ документ, без применения операции mod N, то это будет не подпись, а документ в степени! И размером во много раз больше исходного документаПричем во много много раз больше по размеру, т.к. степень обычно большая выбирается.
давно
Мастер-Эксперт
325460
1469
12.01.2012, 13:24
общий
вот и я о том же!
Об авторе:
to live is to die
Неизвестный
12.01.2012, 13:47
общий
m^e тоже берётся по модулю N, просто не дописал в вопросе. Вы правильно поняли.

Тогда вопрос такой - как же шифр RSA вообще работает, если существует такая проблема?
Неизвестный
12.01.2012, 13:52
общий
Вы имеете ввиду ЭЦП RSA ? Если да, то там как раз хеш-функция применяется. И проблем с коллизиями не возникает.
Неизвестный
12.01.2012, 13:55
общий
Я имею в виду просто алгоритм шифрования/расшифрования RSA. Когда требуется просто засекретить сообщение на открытом ключе и рассекретить тому, для кого это сообщение предназначается. Получается та же проблема, но шифр-то используют.
Неизвестный
12.01.2012, 14:01
общий
Само шифрование документа по алгоритму RSA выполняется блочно, размер блока равен N.
Неизвестный
12.01.2012, 14:24
общий
Но получается, что можно так и подпись составить Просто зашифровать, расшифровать и сравнить с переданным текстом безо всяких коллизий.
Неизвестный
12.01.2012, 14:28
общий
Вы имеете ввиду без хеширования? блочно шифровать документ по RSA? Какая же это подпись будет, если ее размер будет равен размеру файла? Подпись на то и подпись, что служит только для проверки подлинности документа, а не для того, чтобы в подписи хранился весь документ, который можно из нее расшифровать.
Неизвестный
12.01.2012, 14:37
общий
Подпись не будет ведь равна размеру файла за счёт mod N
Неизвестный
12.01.2012, 14:42
общий
Вы можете сформулировать свой вопрос? На тот вопрос, который в самом начале, я уже ответил.
Если использовать хеширование, то подпись получится уникальной (без коллизий).
Если не использовать хеширование, при этом применяя mod N, мы получаем сплошные коллизии, о которых я писал выше.
Если же Вы хотите составить подпись поблочно для всего документа, разбив его на блоки по N, то коллизий не будет, подпись будет уникальна, но при этом она будет размером с исходный документ, так как для каждого куска документа размером N будет как бы своя подпись.
Неизвестный
12.01.2012, 15:14
общий
Теперь ответ понятен
Неизвестный
12.01.2012, 15:16
общий
Неплохо бы оценить тогда мой ответ...
Форма ответа