Міністерство освіти і науки України
Національний університет “Львівська політехніка”
Кафедра ІСМ
Звіт
до лабораторної роботи №6
з дисципліни
“Технології захисту інформації”
на тему:
“Ключовий обмін Діффі-Хеллмана”
Мета роботи: освоїти методи генерації великих простих чисел і методи перевірки великих чисел на простоту. Ознайомитися з теоремою Ейлера, навчитися будувати початкові корені по модулю n. Вивчити схему обміну ключами Діффі-Хеллмана.
Індивідуальне завдання:
1. Написати програму на мові програмування, яка надає засоби:
1.1. генерації великих простих чисел, які перевищують 264 .Програма за заданими t (кількість перевірок за тестом Рабіна-Міллера) та n (кількість біт) повинна генерувати просте n-бітне число, відображаючи при цьому кількість ітерацій алгоритму генерації простого числа, які необхідно виконати для його генерації та час який для цього був необхідний;
1.2. програма за заданими межами діапазону повинна виводити всі прості числа з цього діапазону, відображаючи час, витрачений на генерацію всіх чисел;
1.3. визначити для заданого числа перші 100 початкових коренів, відображаючи при цьому сумарний час витрачений програмою на їх пошук;
2. Змоделювати ключовий обмін між абонентами за схемою Діффі-Хеллмана. Програма повинна отримувати великі прості числа Xa, Xb та n випадковим чином з допомогою алгоритму генерації простого числа, а також надавати засоби з їх завдання користувачем.
Короткі теоретичні відомості:
/
/
Результати роботи:
1.1. Генеруємо велике просте число, відображаючи при цьому кількість ітерацій алгоритму генерації простого числа, які необхідно виконати для його генерації та час який для цього був необхідний.
Код програми:
import java.math.BigInteger;
public class Lab_062 {
public static boolean isPrime(BigInteger n, int precision) {
if (n.compareTo(new BigInteger("341550071728321")) >= 0) {
return n.isProbablePrime(precision); }
int intN = n.intValue();
if (intN == 1 || intN == 4 || intN == 6 || intN == 8) return false;
if (intN == 2 || intN == 3 || intN == 5 || intN == 7) return true;
int[] primesToTest = getPrimesToTest(n);
if (n.equals(new BigInteger("3215031751"))) {
return false; }
BigInteger d = n.subtract(BigInteger.ONE);
BigInteger s = BigInteger.ZERO;
while (d.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
d = d.shiftRight(1);
s = s.add(BigInteger.ONE); }
System.out.println("Кількість перевірок за тестом Рабіна-Міллера");
System.out.println("t = " + t);
System.out.println("Кількість ітерацій алгоритму генерації простого числа");
System.out.println(m);
System.out.println("Згенероване просте число");
System.out.println(k);
return true; }
private static int[] getPrimesToTest(BigInteger n) {
if (n.compareTo(new BigInteger("3474749660383")) >= 0) {
return new int[]{2, 3, 5, 7, 11, 13, 17}; }
if (n.compareTo(new BigInteger("2152302898747")) >= 0) {
return new int[]{2, 3, 5, 7, 11, 13}; }
return new int[]{2, 3}; }
private static boolean try_composite(int a, BigInteger d, BigInteger n, BigInteger s) {
BigInteger aB = BigInteger.valueOf(a);
if (aB.modPow(d, n).equals(BigInteger.ONE)) {
return false; }
for (int i = 0; BigInteger.valueOf(i).compareTo(s) < 0; i++) {
if (aB.modPow(BigInteger.valueOf(2).pow(i).multiply(d), n).equals(n.subtract(BigInteger.ONE))) {
return false; } }
return true; } }
Результати виконання програми:
/
Здійснюємо написання програми, яка за заданим діапазоном виводить всі прості числа, окрім цього відображається час на генерацію цього діапазону.
Код програми:
public class Lab_063 {
public static void main(String[] args) {
IsPrime myIsPrime = new IsPrime();
System.out.print("Введіть ліву межу діапазону чисел: ");
...
