я строго довести, що ця залежність не може бути поліноміальної. Якщо раптом завтра який-небудь геніальний математик знайде швидкий спосіб факторизації великих чисел, то може статися так, що ми опинимося без асиметричної криптографії. Хоча ймовірність цієї події математики оцінюють як близьку до нульової. Використовуючи асиметричну криптографію, корисно пам'ятати про такому собі "дамоклів меч". [6]
6. Хеш-функції і трохи про електронний підпис
Як зазначено у вступі, криптографічними методами можна забезпечити не тільки конфіденційність, а й проконтролювати цілісність переданих або збережених даних. Контроль цілісності, в основному, здійснюється шляхом розрахунку деякої "контрольної суми" даних. Математиками і інженерами, що працюють в області передачі даних і теорії кодування, розроблено безліч алгоритмів, які розраховують контрольні суми переданих даних. Для багатьох додатків простий контрольної суми (наприклад, відомого алгоритму crc32 або послідовного побайтного або послівного складання вихідного тексту з відомою константою) виявляється достатньо, особливо тоді, коли важлива швидкість обробки даних і не відомий заздалегідь обсяг даних (типовий випадок - передача даних по каналах зв'язку ).
Проблема простих алгоритмів обчислення контрольної суми в тому, що досить легко підібрати кілька масивів даних, що мають однакову контрольну суму. Криптографічно стійкі контрольні суми обчислюються як результат застосування до вихідного тексту так званої хеш-функції. [5]
Одним з результатів теорії складності теорії функцій є гіпотеза про існування односторонніх функцій. Під односторонньою функцією розуміється функція, певна (наприклад) на безлічі натуральних чисел і не вимагає для обчислення свого значення великих обчислювальних ресурсів. Але обчислення зворотної функції (тобто, за відомим значенням функції відновити значення аргументу) виявляється неможливо теоретично або (в крайньому випадку) неможливо обчислювально. Суворе існування односторонніх функцій поки не доведено. Тому всі використовувані в даний час хеш-функції є лише "кандидатами" в односторонні функції, хоча і мають досить хороші властивості. p align="justify"> Основними властивостями криптографически "хорошою" хеш-функції є властивість розсіювання, властивість стійкості до колізій і властивість незворотності. Про незворотності ми вже говорили. p align="justify"> колізія хеш-функції H називається ситуація, при якій існують два різних тексту T 1 і T 2 , але H (T 1 ) = H (T 2 ). Значення хеш-функції завжди має фіксовану довжину, а на довжину вихідного тексту не накладається ніяких обмежень. З цього випливає, що колізії існуют...
