ії сильним називається просте число p, таке що: досить велікоімеет досить великі прості дільники, тобто q1 в p = a1q1 +1-1 має досить великі прості дільники, тобто q2 в q1 = a2q1 +1 +1 має досить великі прості дільники
Іноді також додають додаткові умови, наприклад a1 = 1, a2 = 2 і т.п.
Такі числа часто використовуються в різних принципах криптографії.
Я пропоную для даної роботи використовувати алгоритм, в якому ми, вибравши початкове q, ми будемо домножать його на інше випадкове число і додавати одиницю і перевіряти на простоту вийшло число.
Також ми повинні ввести перевірку GNFS:
Exp (((64/9) 1/3 + o (1)) (log n) 1/3 (log log n) 2/3) = Ln [1/3, (64/9) 1/ 3]
Отримане число буде одним з критеріїв криптостойкости.
У разі реалізації підписи Шнорр важливим параметром стійкості буде число t про який буде згадано позже.метод Полларда - алгоритм розкладання натурального числа на прості множники. Запропоновано Джоном Поллардом в 1974 році. Алгоритм призначений для знаходження простих дільників p, у яких p-1 добре розкладається на множники, тобто має невеликий максимальний простий дільник. Якщо позначити цей максимальний простий дільник, то алгоритм вимагає (B log B log2N) дій. Метод дуже швидко знаходить прості чинники малої і середньої величини (до 20-25 десяткових цифр). br/>
1.1 Криптографічні хеш-функції
Оскільки документи, які підписували - змінного (і як правило досить великого) обсягу, в схемах ЕП найчастіше підпис ставиться не на сам документ, а на його хеш. Для обчислення хеша використовуються криптографічні хеш-функції, що гарантує виявлення змін документа при перевірці підпису. Хеш-функції не є частиною алгоритму ЕП, тому в схемі може бути використана будь надійна хеш-функція. p> Використання хеш-функцій дає такі переваги: ​​
1. Обчислювальна складність. Зазвичай хеш цифрового документа робиться у багато разів меншого обсягу, ніж обсяг вихідного документа, і алгоритми обчислення хешу є більш швидкими, ніж алгоритми ЕП. Тому формувати хеш документа і підписувати його виходить набагато швидше, ніж підписувати сам документ.
2. Сумісність. Більшість алгоритмів оперує з рядками біт даних, але деякі використовують інші уявлення. Хеш-функцію можна використовувати для перетворення довільного вхідного тексту у відповідний формат.
. Цілісність. Без використання хеш-функції великий електронний документ у деяких схемах потрібно розділяти на досить малі блоки для застосування ЕП. При верифікації неможливо визначити, чи всі блоки отримані і в правильному чи вони порядку.
Варто зауважити, що використання хеш-функції не обов'язково при електронного підпису, а сама функція не є частиною алгоритму ЕП, тому хеш-функція може використовуватися будь-яка ...
