• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Приклад|зразок| 8.4.

Приклад|зразок| 8.3.

,

,

.

Функція: – називається функцією Ейлера. Якщо – просте число, то , і взагалі .

Можна показати, що

,

де – всі прості дільники n.

,

, .

,

, .

Теорема 8.1. (Ейлера). Якщо , то .

Приклад|зразок| 8.5.Хай|нехай| n=10. Тоді і .

,

,

,

.

З|із| теореми Ейлера безпосередньо виводиться

Теорема 8.2. (мала теорема Ферма). Якщо , то .

Має місце наступне|таке| твердження|затвердження|

Теорема 8.3. Якщо числа попарно взаємно прості, число – їх добич|добуток|, x і а – цілі числа, то .

Останнє твердження|затвердження| є|з'являється,являється| слідством|наслідком| теореми, яка відома як «китайська теорема про залишки».

Приклад|зразок| 8.6.Хай|нехай| n=10=; x=81; a=61. Тоді

, , ,

, , .

8.3. Шифрування з|із| відкритим|відчиненим| ключем|джерелом|

Шифрування з|із| відкритим|відчиненим| ключем|джерелом| проводиться|виробляється,справляється| таким чином.

1. Одержувачем повідомлень|сполучень| проводиться|виробляється,справляється| генерація відкритого|відчиненого| ключа|джерела| (пара чисел n і e) і закритого|зачиненого| ключа|джерела| (число d). Для цього:

· вибираються два прості числа p і q;

· визначається перша частина|частка| відкритого|відчиненого| ключа|джерела| n=pq;

· визначається друга частина|частка| відкритого|відчиненого| ключа|джерела| – вибирається невелике непарне число e, взаємно простої з|із| числом (відмітимо|помітимо|, що );

· визначається закритий|зачинений| ключ|джерело|: .

Після чого відкритий|відчинений| ключ|джерело| (числа n і e) повідомляється всім відправникам повідомлень|сполучень|.

2. Відправник шифрує повідомлення|сполучення| (розбиваючи його, якщо потрібно, на слова завдовжки менш розрядів):

,

і відправляє|відряджає| одержувачу.

3. Одержувач розшифровує повідомлення|сполучення| за допомогою закритого|зачиненого| ключа|джерела| d:

.

Теорема 8.4. Шифрування з|із| відкритим|відчиненим| ключем|джерелом| коректно, тобто|цебто| в прийнятих позначеннях .

Доказ. Очевидно, що . Покажемо, що . Дійсно числа d і e взаємно зворотні по модулю, тобто|цебто|

при деякому. Якщо , то по малій теоремі Ферма маємо:

.

Якщо , то порівняння , очевидно, виконується. Таким чином

.

Абсолютно|цілком| аналогічно маємо

.

І по слідству|наслідку| до китайської теореми про залишки

.

Оскільки і , укладаємо|ув'язнюємо,замикаємо,поміщаємо|, що .

Приклад|зразок| 8.7.Генерація ключів|джерел|:

1. p=3, q=11;

2. n=;

3. , e=7;

4. d=, ().

Хай|нехай| =3, =1, =2 (). Тоді код визначається таким чином:

;

;

.

При розшифровці маємо:

,

,

.

Шифри з|із| відкритим|відчиненим| ключем|джерелом| порівняно прості в реалізації, дуже практичні (оскільки немає необхідності пересилати по каналах зв'язку закритий|зачинений| ключ|джерело| і можна безпечно зберігати його в одному місці) і в той же час володіють високою криптостійкістю.

Здається|видається|, що дешифрувати повідомлення|сполучення| нескладно: досить розкласти відкрито|відчинений| опубліковане число n на множники, відновивши числа p і q, і далі можна легко обчислити|обчисляти,вичислити| секретний ключ|джерело| d.

Проте|однак| справа|річ| полягає в наступному|слідуючому|. В даний час|нині| відомі ефективні алгоритми визначення простоти чисел, які дозволяють за декілька хвилин підібрати|добрати| пару дуже великих простих чисел (по 100 і більше цифр в десятковому записі). В той же час невідомі ефективні алгоритми розкладання дуже великих чисел на множники. Розкладання на множники числа в 200 і більше цифр зажадало б сотень років роботи найкращого суперкомп'ютера. При практичному застосуванні|вживанні| шифрів з|із| відкритим|відчиненим| ключем|джерелом| використовують дійсно великі прості числа (не менше 100 цифр в десятковому записі, а звичайно – значно більше|значно більший|). В результаті розкрити|розітнути| цей шифр виявляється|опиняється| неможливо, якщо не існує ефективних алгоритмів розкладання на множники.

Втім, можливість|спроможність| відкриття|відчинення| таких алгоритмів існує, хоча цей факт і не доведений строго|суворо|.

Читайте також:

1. Приклад|зразок| 8.1.

Переглядів: 625