РОЗДІЛ 2
розробка та дослідження удосконаленого методу криптоаналізу на основі
використання ресурсів комп’ютерних мереж
2.1. Удосконалення методу загального решета числового поля
Алгоритм решета числового поля містить чотири стадії [64]: вибір поліному,
просіювання, перетворення лінійної алгебри, визначення квадратного кореня.
2.1.1. Оптимізація вибору поліному
Подамо число n у формі [25]
n = , (2.1)
де ;
При цьому і є достатньо малими.
Виберемо мінімальні і , такі, що . Звідси випливає, що
(2.2)
Нехай , . Тоді
. (2.3)
Сформуємо многочлен
, (2.4)
де – буде дійсним коренем многочлена;
a0=c.
Поліном (2.4) повинен мати такі властивості:
- f(x) – незвідний, примітивний;
- ;
- коефіцієнти поліному f гладкі по базі .
Для чисел довжиною менше 60 десяткових знаків використаємо поліном степеня 3.
Коли довжина числа більша 60 і менша 180 десяткових знаків, то степінь полінома
дорівнює 5. Виберемо ціле число і, таке, що і виконується рівність ,
коефіцієнти полінома знаходяться в межах . Отже, отримано множину многочленів
виду (2.4).
Нехай - корінь многочлена f. Необхідно сформувати алгебраїчний многочлен з
цілими коефіцієнтами. Нехай . Тоді отримуємо число , таке, що і . Оскільки g -
первісний корінь, - ціле число, то справедливим є співвідношення . Пошук
коефіцієнтів ведеться за допомогою декомпозиції ідеалів простої норми, елементи
котрих мають вигляд . Декомпозиція головних ідеалів знаходиться за допомогою
значень виразу , де r - просте число і не є дільником ідеалу . Визначення числа
r для дільників другого порядку дискримінанта поліному f ведеться за допомогою
тесту Дедекінда. Загальну кількість поліномів, породжених числом p, визначають
m значень коефіцієнтів полінома з відрізка . Таким чином сформовано матрицю М,
рядки котрої є векторами, координати яких є всеможливими коефіцієнтами поліному
. Необхідно вибрати такі коефіцієнти для f, щоб час роботи алгоритму ЗРЧП був
мінімальним і тест Дедекінда давав позитивний результат. Оскільки поліном f
повинен бути незвідним, то під час аналізу можна скористатися наступним
критерієм [9] Ензейштейна. Якщо існує р – просте, що в многочлені коефіцієнт an
не ділиться на р, а вільний член a0 не ділиться на р2, то цей многочлен не
звідний над Z.
Результати чисельних експериментів можна знайти в табл. 2.1.
Таблиця 2.1
Формування коефіцієнтів поліному
Степінь
многочлена
Значення дескримінанту
Тест Дедекінда
80
2572
2432
1424
2580
2856
1210
2410
2720
1174
155
2721
2528
1350
2755
2911
988
2604
2849
1215
165
3020
2731
1326
3215
29865
1145
3128
2835
1265
Для порівняння удосконаленого та класичного методів скористаємось діаграмою в
якій представлені дані про кількість відсіяних векторів за допомогою
удосконаленого та класичного алгоритмів формування поліному (рис. 2.1). У
першому випадку з матриці H, порядок якої 102, відсіяно приблизно однакову
кількість векторів обома методами відповідно. Аналогічна ситуація для другого
та третього випадків де розмірності матриць 103 та 104. Найбільший ефект
спостерігається у четвертому та п’ятому випадках коли сформований поліном за
допомогою критерію Ензейштейна відсіює значно більшу кількість векторів.
Рис. 2.1. Порівняння поліномів за кількістю відсіяних векторів
Отже дослідження показали, що на практиці доцільно скористатися критерієм
Ензейштейна, оскільки зменшено кількість операцій алгоритму ЗРЧП на 6%.
2.1.2. Скорочення часу етапу просіювання
Побудуємо гомоморфізм такий, що відображає в . Відомо з класичної алгебри, що
всякий ізоморфізм множини самої на себе є автоморфізмом [78]. Будь - який
автоморфізм поля К, який залишає на місці всі елементи поля , це автоморфізм
поля К над полем . Тут К – деяке розширення поля . Сукупність всіх
автоморфізмів будь – якої алгебраїчної структури утворює комутативну групу.
Якщо поле К нормальне над , то підгрупа автоморфізмів поля К над полем
становить групу Галуа .
Використовуючи низку тверджень з теорії Галуа дослідимо властивості
відображення .
Нехай має в нормальному полі К корінь К та . Тоді справедливою буде наступна
рівність . Оскільки - ізоморфізм, то . Отже відображення переводить корінь в 1
– корінь того самого многочлена. Таким чином, кожному автоморфізму відповідає
деякий корінь многочлена і кожному кореневі відповідає деякий автоморфізм групи
Галуа. Група Галуа може описуватись підстановками. Оскільки поле К – скінченне,
то група Галуа є скінченною і будь - якому проміжному полю L відповідає якась
підгрупа групи Галуа (відповідність Галуа) [48].
Метод решета поля дозволяє відшукати пару цілих алгебраїчних чисел a і b, які
зустрічаються в співвідношенні
. (2.5)
Отримані числа a і b використовують для знаходження розв’язку конгруенції
. (2.6)
Під час пошуку можна обмежитись головними ідеалами Z[] простої норми, бо вони
єдині містять алгебраїчні цілі числа форми . Тут a і b - взаємопрості числа
[37].
Множину головних ідеалів Z[] простої норми визначають пари чисел p і c, де p -
просте число і c. Число c повинне задовольняти умову . Під час пошуку пар чисел
можна використовувати головні ідеали норми p, які породжені p, і або
еквівалентні головні ідеали Z[], що перетворюються гомоморфізмом в і
відображається в c. Зокрема, число знаходиться в головному ідеалі, що
відповідає парі чисел p і c, якщо тільки . Головний ідеал характеризується
нормою , де a і b - взаємопрості числа [42].
Для того, щоб знайти конкретні значення чисел a і b, поступають таким чином:
фіксують b і перевіряють a+mb на гладкість за допомогою решета поля [39]. Для
простого числа p стартова точка для
- Київ+380960830922