Статьи

НОУ ІНТУЇТ | лекція | Алгоритми тестування на простоту і факторизации

  1. 2.3 Комп'ютерні обчислення з великими числами Як ми побачимо в третьому розділі, складні для завдання,...
  2. 2.3.2 Програмування з великими числами в C / C ++

2.3 Комп'ютерні обчислення з великими числами

Як ми побачимо в третьому розділі, складні для завдання, на яких засновані сучасні системи захисту інформації, є важковирішуваними тільки при використанні дійсно великих чисел - розміром в тисячі довічних знаків. У цьому параграфі ми розглянемо деякі інструменти програміста, корисні для роботи з такими числами.

2.3.1 Калькулятор для великих чисел

При налагодженні будь-якої програми, що працює з великими числами, часто доводиться проводити будь-які обчислення вручну, порівнюючи їх з результатами програми, і в цьому допоміг би калькулятор, який працює з великими числами. Стандартний калькулятор Windows непридатний для цих цілей.

Грати роль калькулятора для великих чисел добре можуть системи комп'ютерної алгебри. Крім комерційних систем, таких як Maple або Mathematica, існують системи комп'ютерної алгебри з відкритим вихідним кодом, що цілком підходять для наших цілей. Розглянемо як приклад систему комп'ютерної алгебри Maxima, яку у вигляді дистрибутива для Windows, або у вигляді вихідних кодів можна завантажити з її офіційного сайту http://maxima.sourceforge.net/ .

Maxima може працювати як інтерактивне середовище командного рядка, в режимі зошити (відрізняється від попереднього тим, що введені раніше команди можна поправляти і запускати заново) так і у вигляді неінтерактивному інтерпретатора мови програмування Maxima, що є надбудовою над мовою Lisp.

Як приклад розглянемо роботу з Maxima в режимі зошити. Після установки Maxima такий режим доступний з-під будь-який з двох графічних оболонок Maxima: wxmaxima і xmaxima. На малюнку Мал. 2.1 показаний приклад сеансу в графічному середовищі wxmaxima.

У рядках% i9,% i22, і т.д. користувач вводив команду і після натиснення Shift + Enter отримував відповідь у відповідних рядках% o9,% o22, ...

Відзначимо лише деякі корисні для нас команди. Їх докладний опис можна знайти в продукції, що поставляється з maxima документціей.

  • \ Verb | chinese | - рішення системи рівнянь за допомогою китайської теореми про залишки.
  • \ Verb | igcdex | - розширений алгоритм Евкліда.
  • \ Verb | inv_mod | - знаходження числа, зворотного до заданого числа по модулю.
  • \ Verb | jacobi | - символ Якобі.
  • \ Verb | lcm | - найменше спільне кратне чисел.
  • \ Verb | power_mod | - зведення в ступінь по модулю.
  • \ Verb | primep | - тестування числа на простоту за допомогою тесту Рабіна-Міллера і Лукаса.
  • \ Verb | zn_log | - дискретного логарифмування, що використовує алгоритм поліг-Хеллмана і Ро-алгоритм Полларда.
  • \ Verb | zn_order | - обчислення мультиплікативного порядку числа по модулю.
  • \ Verb | zn_primroot | - знаходження примітивного кореня по модулю.

2.3.2 Програмування з великими числами в C / C ++

При написанні складних систем захисту інформації не обійтися без компилируемого мови програмування високого рівня, наприклад, C ++. Стандартний тип цілих чисел в C / C ++ дозволяє працювати з числами не більше 64 довічних знаків, чого мало для криптографічних додатків. Існують бібліотеки для C / C ++, що реалізують операції з великими числами і інші корисні криптографічні функції. Відзначимо лише деякі з них, що надаються безкоштовно з відкритим вихідним кодом:

  • openssl - бібліотека, яка реалізує криптографічний протокол SSL. У бібліотеці реалізовані операції і багато алгоритми роботи з великими числами, з ними і все реальні криптографічні алгоритми, що розглядаються в даному посібнику. В силу збільшення кількості випадків виявлення вразливостей в openssl, в тому числі, можливо, навмисне внесених спецслужбами окремих країн, був створений окремий проект libressl, що ставить собі за мету провести аудит вихідних кодів і створити більш налагоджену і вивірену версію бібліотеки SSL. Написана на мові C, тому при програмуванні звичні формули, наприклад, x = y + z, пишуться в процедурному стилі:
  • GMP (GNU Multiple Precision) - бібліотека, яка реалізує операції як з цілими числами більших розмірів, так і з числами з плаваючою точкою високої точності. Чи не реалізує ніяких криптографічних алгоритмів.
  • Crypto ++ - криптографічний бібліотека з інтерфейсом на мові C ++. У ній реалізовані більшість популярних криптографічних алгоритмів (російські стандарти блочного шифрування, цифрового підпису та хеш-функції не потрапили в їх число). Як перевага можна відзначити перевантаження стандартних операторів, що дозволяє переводити програми, вже написані на C ++ з використанням типів int, простою заміною типів int на CryptoPP :: Integer.

Розглянемо налаштування оточення програміста для використання бібліотеки Cryptopp.

Приклад 2.3 Написати програму, приймаючу два цілих позитивних числа A і B і обчислює символ Якобі Приклад 2 .

Рішення.

а) За допомогою середовища програмування Visual Studio 2010

Для Visual Studio доведеться збирати бібліотеку Cryptopp з вихідних кодів, доступних на офіційному сайті: http://www.cryptopp.com/ .

Після розпакування архіву з вихідними кодами потрібно відкрити і зібрати рішення cryptest.sln.

Нам знадобляться наступні файли:

  • cryptopp.dll - динамічно довантажувати бібліотека cryptopp. Бібліотека містить всі функції cryptopp, і може бути довантажуючи нашою програмою для їх використання.
  • cryptopp.lib - бібліотека імпорту. Вона містить інформацію, необхідну для приєднання cryptopp.dll до нашої програми. Файли dll і lib можна знайти в директорії збірки рішення cryptest.sln.
  • Всі заголовки, що входять в архів вихідних текстів.

Створимо в Visual Studio 2010 року проект "Win32 Console Application". Для того, щоб в нашій програмі використовувати cryptopp, необхідно зайти в властивості нашого проекту (див. Мал. 2.2 )


Мал.2.2.

Для підключення cryptopp в Visual Studio необхідно зайти в властивості проекту

і вказати

Файл cryptopp.dll необхідно скопіювати в папку, в якій буде розміщуватися виконуваний файл нашої програми.

Тепер можна зібрати рішення з нашим проектом і перевірити, що все зроблено правильно. Можна приступати до написання вихідного коду.

Код нашого проекту буде виглядати наступним чином:

#include <dll.h> // Цей файл повинен бути включений до всіх // інших заголовків файлів бібліотеки #include <iostream> // Модуль введення / виводу стандартної бібліотеки // C ++ #include <integer.h> // У цьому заголовному файлі визначається // клас Integer великих чисел using namespace std; using namespace CryptoPP; // Все функції cryptopp знаходяться в // просторі імен CryptoPP // Функція, що обчислює символ Якобі int JacobiSymbol (Integer A, Integer P) {// На самому початку P> 2 і непарній (перевіряється в main ()) int result = 1; while (true) {// Статичний метод Gcd класу Integer обчислює найбільший // спільний дільник; якщо він не дорівнює одиниці, то символ Якобі // дорівнюватиме нулю (легко випливає з визначення) if (Integer :: Gcd (A, P)> 1) return 0; // Тепер P> 1, НСД (A, P) = 1 // Рівні по модулю P числа є або не є // квадратичними відрахуваннями одночасно if (A> = P) A = A% P; // Тепер 1 <A <P, P> 1, НСД (A, P) = 1 // Відокремити парну частину числа A. Визначимо, на яку // ступінь двійки ділиться число A, і символ Якобі 2 по P // знайдемо по властивості. int pwr_ = 0; while (A.GetBit (pwr_) == false) pwr _ ++; if (pwr_> 0) {A >> = pwr_; // Поділити A на ступінь двійки int pwroftwo = pwr_% 2; if (pwroftwo == 1) if ((P * P-1)% 16! = 0) result * = -1; continue; } // Тепер A непарній, P> 1, A <P, НОД (A, P) = 1 if (A == 1) break; // Тепер A, P непарні, більше 1 і взаємно прості. Тому // можна застосувати квадратичний закон взаємності. if (((A - 1) * (P - 1))% 8! = 0) result * = -1; A.swap (P); // Тепер знову P> 1 і непарній, тому можна // повертатися в початок циклу. } Return result; } Int main (int argc, char ** argv) {if (argc == 3) {// Перевірити коректність аргументів командного рядка bool correctnumbers = true; for (int j = 1; j <= 2; j ++) for (int i = 0; argv [j] [i]! = '\ 0'; i ++) if ((argv [j] [i] < '0 ') || (argv [j] [i]>' 9 ')) correctnumbers = false; // Якщо аргументи коректні, порахувати їх символ Якобі if (correctnumbers == true) {Integer a (argv [1]); Integer b (argv [2]); if (b <3) cout << "Jacobi symbol (a / b) is not defined for b =" << b << endl; else {cout << JacobiSymbol (a, b) << endl; return 0; }}} Cout << "Expected two positive integer numbers" << endl; return -1; } \ End {verbatim}

Після складання програму потрібно запускати з консолі. наприклад:

\ Verb | testcrypt.exe 51 343543 |

Звичайно, наша програма допускає обчислення і з куди більшими числами.

Серйозним мінусом даного підходу є необхідність купувати Microsoft Visual Studio для розробки під Windows. Чи не станемо перераховувати причини, за якими в безкоштовній версії Microsoft Visual Studio Express описані нами дії не призведуть до успіху.

б) У операційних системах сімейства linux

В операційних системах сімейства linux величезна кількість бібліотек, доступних розробнику, запаковані в спеціальні архіви, звані пакетами. Відмінність пакета від архіву в тому, що між пакетами існують залежності, що дозволяють програмі установки автоматично встановлювати не тільки бібліотеку або програму, яку попросив користувач, але і всі необхідні для їх роботи додаткові бібліотеки. Зазвичай бібліотека та заголовки до неї запаковуються в різні пакети. Пакет з заголовками файлами, як правило, має суфікс -dev або -devel.

У linux-системах, заснованих на Debian GNU / Linux, для розробки з використанням cryptopp потрібна установка всього двох пакетів. Всі дії можна виконати з командного рядка з правами адміністратора:

# Apt-get install libcrypto ++ - dev

Завдяки автоматичній системі розпізнавання залежностей також буде встановлена ​​потрібна версія бібліотеки libcrypto ++.

Як і в Windows, в Linux є безліч середовищ розробки. Дії, вироблені в середовищі розробки Eclipse (з підключеним розширенням CDT - C Development Tools), аналогічні нашим попереднім діям в Visual Studio.

  1. Створити простий проект C ++
  2. З панелі Project Explorer відкрити властивості проекту
  3. C / C ++ Build Settings Tool Settings GCC C ++ Compiler Includes. У верхньому вікні, Include paths, потрібно додати шлях до заголовним файлів (зазвичай, / usr / include / crypto ++)
  4. З / C ++ Build Settings Tool Settings GCC C ++ Linker Libraries. У верхньому вікні, Libraries (-l), потрібно додати рядок "crypto ++".
  5. Написати вихідний код програми
  6. зібрати проект
  7. Запускати проект, передаючи числа A і B через аргументи командного рядка.

Недолік проектів Eclipse (так само, як і Visual Studio) в тому, що в них явно вказується шлях до заголовним файлів, які на іншому комп'ютері можуть розташовуватися в іншій теці. Поетму рекомендується створити файл проекту, що не залежить від середовища розробки, наприклад, проект в системі збирання Cmake (див. http://www.cmake.org/documentation/ ).

Для автоматичного пошуку заголовків файлів і самої бібліотеки використовується система pkgconfig. Її можна використовувати з cmake-проекту наступним чином.

  1. Створимо файл jacobi.cpp з вихідним кодом нашої програми
  2. У тій же директорії створимо файл CMakeLists.txt наступного змісту: cmake_minimum_required (VERSION 2.4) project (jacobi) INCLUDE (FindPkgConfig) pkg_check_modules (CRYPTOPP REQUIRED libcrypto ++) include_directories ($ {CRYPTOPP_INCLUDEDIR} $ {CRYPTOPP_INCLUDEDIR} / cryptopp) link_directories ($ {CRYPTOPP_LIBRARY_DIRS }) add_executable (jacobi jacobi.cpp) target_link_libraries (jacobi $ {CRYPTOPP_LIBRARIES}) Тут project (jacobi) вказує ім'я cmake-проекту; в наступних чотирьох рядках ми вказуємо системі pkgconfig шукати заголовки та бібліотеки crypto ++. В останніх двох рядках ми вказуємо, який створювати виконуваний файл, і які до нього підключити бібліотеки.
  3. Збірка cmake-проекту здійснюється командами:

Для налагодження програми, забезпеченою файлом Cmake-проекту, можна використовувати інтегровані середовища розробки. Одна з кращих середовищ розробки з підтримкою Cmake - QtCreator.

Список літератури

  1. Черьомушкін А.В. Арифметичні основи криптографії - М .: МЦНМО, 2002. - 104 с.

Новости