Тема базові математичні основи криптографічних засобів захисту інформації



Download 157,5 Kb.
bet2/4
Sana25.04.2022
Hajmi157,5 Kb.
#581295
1   2   3   4
Bog'liq
ТЕМА 1

2. Прості і взаємно прості числа. Дискретний логарифм і первісні корені. Будуть потрібні для розуміння і дослідження двоключових (несиметричних) криптоалгоритмів і криптосистем, а також криптографічних протоколів на їх основі.
2.1. Прості числа.
Натуральне число а, більше 1, називається простим, якщо воно не має натуральних дільників, відмінних від 1 і самого числа а. Кількість простих чисел нескінченна.
Приклад. Початок множини простих чисел, які менші за 100:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, . . . . .
Взагалі, кількість Р простих чисел, менших N, приблизно дорівнює
N / (In N).
Як видно з наведеного вище прикладу, при N = 100, кількість простих чисел, менших 100 дорівнює точно 25 (від 2 до 97). А за оціночною формулою маємо:
N = 100, In N  4.6, Р = N / (In N)  22
Ще приклади:
N = 1000, In N  4.6, Р = N / (In N)  145
N = 10000, In N  9.2, Р = N / (In N)  1087
Доведено, що будь-яке натуральне число, відмінне від 1, є або простим, або може бути представлено у вигляді добутку простих чисел однозначно з точністю до порядку співмножників в добутку (це – так звана основна теорема арифметики).
Приклад: 969 = 3*17*19;
Звернімо особливу увагу на таке. Навіть якщо співмножники – дуже великі числа, обчислення їх добутку принципово не складна задача: існують і розроблені ефективні алгоритми її вирішення.
Але на сьогодні поки що не винайдено достатньо ефективних алгоритмів розкладання довільного цілого числа на прості множники навіть тоді, коли відомо, що воно розкладається в добуток двох простих простих чисел.
Відсутність ефективних алгоритмів з доказовими оцінками складності дозволило покласти проблему розкладання натуральних чисел на прості множники в основу деяких несиметричних криптографічних систем, зокрема, RSA і обґрунтувати їх практичну криптостійкість.
Підмножину простих чисел, які не перевищують заданого N, починаючи з 2, можна сформувати з множини натуральних чисел, використовуючи алгоритм, який відомий як Решето Ератосфена. За допомогою цього алгоритму можна створити таблицю простих чисел потрібного розміру. Подивитися наочне графічне пояснення роботи Решета Ератосфена і приклади його реалізації на Java та Python можна за адресою https://habr.com/ru/post/333350/
При реалізації несиметричних криптоалгоритмів для забезпечення їх надійності (криптостійкості) потрібні дуже великі прості числа. Тому на практиці для вибору простого числа потрібного розміру можна послуговуватися не таблицею простих чисел, а діяти в інший спосіб.
Припустимо, потрібно обрати просте число Р певної розрядності. Для цього можна обирати непарне число N відповідної розрядності і перевірити, чи є воно простим. Для цього застосовуються так звані тести на простоту.
Один з тестів виконується шляхом повного перебору всіх можливих потенційних дільників даного обраного числа N. Якщо при виконанні тесту окрім 1 і самого N знайдеться хоча-б ще один дільник, то N не просте. Тоді слід обирати інші числа N', N'', N'''. . . і тестувати їх доти, доки не поточне з них не пройде тест.
Опис простішого алгоритму.
Виконується перебір усіх цілих чисел від 2 до числа j, яке дорівнює квадратному кореню з N (з округленням у більшу сторону) і обчисленні залишку від ділення N на кожне з цих чисел j. Якщо залишок від ділення на поточне число j дорівнює 0, то j є дільником N. У цьому випадку N оголошується не простим (складеним), і алгоритм закінчує роботу. Після досягнення j значення квадратного кореня з N і виявленій неможливості скоротити N ні на одне з чисел j, N оголошується простим і алгоритм закінчує роботу.
Завдання 4. Розробіть на Python:
1) допоміжну функцію testprime (N), де N – число, яке перевіряється на простоту. Функція повинна повертати ознаку простоти n, наприклад 0, якщо N – непросте, або 1, якщо N – просте.
2) функцію theprime (N1, N2) пошуку простого числа Р, яка виконує цикл перевірки чисел на простоту з використанням функції testprime (N) в межах діапазону [N1, N2] доти, доки не буде знайдено перше ж просте Nі [N1, N2], яке і буде прийматися як шу́кане Р.
2.2. Взаємно прості числа.
Два числа називаються взаємно простими, якщо вони не мають жодного спільного дільника окрім одиниці.
Приклад. Числа 27 і 28 взаємно прості (у них немає спільних дільників крім одиниці), а числа 27 і 33 - ні (у них є спільний дільник 3).
Нехай а і b - два цілих позитивних числа. Найбільший спільний дільник (НСД) чисел а і b є найбільше число с, яке ділить і а і b:

Download 157,5 Kb.

Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish