Розглянуто задачу факторизації, на якій базуються багато класичних асиметричних систем (RSA, Рабіна, інші) та криптографічно сильних генераторів псевдовипадкових послідовностей (BBS). Описано методи, які послугували прообразами методу Лєнстра, та запропоновано метод факторизації чисел, який є аналогом методу Лєнстра на кривих Едвардса. Спочатку для обгрунтування коректності методу розроблено відповідний математичний апарат. Далі, з використанням цього апарату, побудовано аналог методу Лєнстра на кривих Едвардса та розроблено відповідний алгоритм факторизації чисел. Математично обгрунтовано коректність методу, коректність роботи алгоритму; отримано та строго доведено верхні аналітичні оцінки для його швидкодії та нижні оцінки імовірності успіху. Наведено та строго обгрунтовано переваги розробленого методу у порівнянні з класичним методом Лєнстра, який застосовує еліптичні криві у формі Вейєрштраса. Проведено порівняльний аналіз нового та класичного алгоритмів. За результатами досліджень отримано строгі доведення того, що новий алгоритм на повних кривих Едвардса, у порівнянні з класичним, має переваги у швидкодії приблизно у 1,5 разу. Наведено експериментальні результати, які показують, що швидкодія зростає ще більше (до 30 відсотків), якщо замість повних кривих Едвардса використовувати скручені та квадратичні криві. Показано, що оцінка ймовірності успіху нового методу зросте за рахунок появи нових умов, які приводять до успіху алгоритму та які не існують для класичного алгоритму Лєнстра на кривих Вейєрштраса. Отримані результати надають можливість зменшити час, необхідний для розв'язку задачі факторизації, приблизно у 1,5 разу, а, отже, надають можливість швидше зламувати криптосистеми, що базуються на цій задачі.

  Повний текст PDF - 393.047 Kb    Зміст випуску     Цитування публікації

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"