Материалы что дал Мухачев / Материалы что дал Мухачев / Білети_коротки_відповіді / Білети_відпові_БСДМ / Mg_Vidp59

59. Визначення геш-функції. Необхідність застосування геш-функцій у схемах цифрового підпису на прикладі .

Геш-функція - це перетворення бітового рядка довільної довжини у рядок (блок) фіксованої довжини (зазвичай, 160-512 битів), яке має наступні властивості.

1. Відновлення виходячи із співвідношення , обчислювально неможливо.

2. Вимагається обчислювальна неможливість знаходження довільної колізії, тобто пари різних повідомлень , таких, що . Подібні геш-функції називаються вільними від колізій.

Значення називається геш-кодом повідомлення , а величина - довжиною геш-коду.

Геш-функція використовуються для ускладнення підробки підпису.

Наприклад, підписаний блок даних на основі RSA з параметрими можна було б формувати у виді , а для перевірки підписаного повідомлення обчислювати значення і приймати підпис, якщо порівнювати .

Але якщо вибрати блок даних виду , то підписаний блок матиме вигляд , тобто підпис підроблено.

При реальний підпис RSA має вид . При перевірці отримуемо і приймаємо підпис, якщо .

59. Надати запис відстані від функції до пари афінних функцій через .

Відстанню Хемінга від булевої функції до заданої множини булевих функцій називається значення.

Відстань від функції до множини можна записати через коефіціент Уолша-Адамара у виді.

.