Зміст
Введення.Глава 1. Структура та зміст навчально-методичного посібника.
1.1. Теоретичне наповнення розділу «Операції з великими числами»
1.2. Теоретичне наповнення розділу «Імовірнісні тести на простоту»
1.3. Теоретичне наповнення розділу «доказово прості числа»
1.4. Розробка завдань для лабораторних і самостійних робіт
1.5. Тести для самоперевірки
Глава 2. Апробація методичного посібника.
2.1 Апробація в Тюменському державному університеті
2.2 Апробація в Тюменській державної академії економіки, управління та права
Висновок
Список літератури
Додаток 1
Введення
Актуальність. Структура вищої очної освіти передбачає поєднання різних видів і методів навчання: аудиторні заняття, домашня і самостійна робота студентів, виконання курсових робіт зі спеціальності, з предметів. Аудиторні заняття, у свою чергу, діляться на лекційні, практичні, лабораторні та семінарські заняття. Для вивчення кожного предмета ДОС ВПО (Державний освітній стандарт вищої професійної освіти) за спеціальністю визначає необхідну кількість аудиторних занять кожного виду, а також кількість годин, виділених на самостійну роботу студентів. У навчальному плані спеціальності «Комп'ютерна безпека» Тюменського державного університету на вивчення дисципліни «Криптографічні методи захисту інформації» відводиться 70 годин лекцій і 35 годин лабораторних занять. Обсяг самостійної роботи студента з дисципліни криптографічні методи захисту інформації становить 82 години. На вивчення інших предметів криптографічного спрямованості - «Теоретико-числові методи в криптографії» і «Криптографічні протоколи» - також відведено в сумі 70 годин лекційних 35 годин практичних занять. У цілому, на вивчення криптографії у Тюменському державному університеті відводиться 210 годин аудиторного навантаження. Таким чином, криптографія як общепрофессіональних і спеціальна дисципліна є однією з центральних у навчальному процесі на спеціальності «Комп'ютерна безпека».
Практичні та лабораторні заняття проводяться у вигляді виконання студентами завдань в комп'ютерних класах під керівництвом викладача. Самостійна робота студентів здійснюється у вигляді реалізації криптографічних алгоритмів на якому-небудь мові програмування. Метою практичних, лабораторних занять і самостійної роботи студентів є краще засвоєння матеріалу, яке дається на лекціях, через практику, самостійне, більш глибоке вивчення різних аспектів криптографічного захисту, питань практичного застосування і реалізації криптографічних алгоритмів і протоколів.
Методичне забезпечення навчального процесу є однією з найважливіших складових навчального процесу, особливо в частині самостійної роботи студентів. Зв'язок між викладачем і студентом не повинна обриватися в той момент, коли студент залишає аудиторію. Методичні посібники, вказівки до виконання лабораторних і самостійних робіт, розроблені як додаток до лекційного матеріалу, покликані висвітлити питання, що постають перед студентами в процесі виконання ними самостійної роботи. Матеріал, що дається на лекції, як правило, носить загальний характер, і з-за часових обмежень, а також відмінностей у рівні підготовки студентів, різної мотивації до вивчення предмета, інтересу до різних розділів і аспектів даної дисципліни. У методичному посібнику є можливість розглянути кожен напрямок, кожен алгоритм більш докладно, зупинитися на питаннях його практичної реалізації, обумовити моменти, очевидні для одних студентів, але, можливо, що представляють суттєві труднощі для інших. Важливим моментом є можливість розглянути в методичному посібнику теми, не пов'язані безпосередньо до досліджуваної дисципліни, але використовуються при її освоєнні. Наприклад, у розроблений посібник увійшов розділ «Операції з великими числами», в якому не описано ніяких криптографічних алгоритмів, проте вельми корисний для студента.
Тематика генерації великих простих чисел, обрана для розробленого методичного посібника, є ключовою для вивчення криптографічних методів захисту інформації. Майже кожен криптографічний алгоритм з відкритим ключем вимагає генерації простого числа розміром не менше 512 біт. У процесі використання таких алгоритмів доводиться багато разів створювати такі числа, причому деякі алгоритми вимагають прості числа спеціального виду. Наприклад, алгоритм цифрового підпису (ЦП) стандарту ГОСТ Р 34.11-94 вимагає генерації двох простих чисел p і q таких, що q є дільником числа (p-1). Таким чином, перш ніж приступати до реалізації алгоритмів з відкритим ключем, студент повинен освоїти тему генерації великих простих чисел.
На даний момент існує кілька алгоритмів отримання простого числа. У довідковій літературі, у тому числі такою популярною як [9], розглянуті алгоритми наведені без математичного обгрунтування, що в свою чергу не дозволяє вивчити матеріал у повному обсязі. Для отримання найбільш повних знань слід користуватися навчальною літературою. Більшість видань навчальної літератури містить не тільки опис самих алгоритмів, а також їх математичні обгрунтування, приклади і.т.п.
На даний момент серед навчальної літератури досить слабко представлена тема генерації великих простих чисел. Більшість авторів у своїх роботах не висвітлюють дану тему в повному обсязі, а саме [1] висвітлив цю тему не в повному обсязі, в роботі присутні опис алгоритмів і оцінки їх складності і надійності. [3] висвітлив цю тему не в повному обсязі, в роботі присутні опис алгоритмів їх математичне обгрунтування та приклади, відсутні оцінки складності і надійності алгоритмів. [5] висвітлили тему не в повному обсязі: у роботі відсутня математичне обгрунтування алгоритмів та їх оцінки складності і надійності. [12] висвітлили цю тему досить повно, в роботі присутній опис алгоритмів їх вичерпний математичне обгрунтування, присутні оцінки складності і надійності, приклади.
Таким чином, можна сказати, що для студента є деякою проблемою знайти навчальний або навчально-методичний посібник російською мовою, в якому досить докладно, обгрунтовано були б викладені основні алгоритми генерації простих чисел з прикладами.
Метою даної роботи є:
Розробити методичний посібник на тему «Генерація простих чисел» для спеціальності «Комп'ютерна безпека» Тюменського державного університету, що включає в себе теоретичний матеріал, завдання до практичних робіт, вказівки до їх виконання та матеріали для перевірки якості виконаних завдань.
Для досягнення даної мети довелося вирішити такі завдання:
1. Вивчити матеріал по темах: арифметика великих чисел; асимптотичний закон розподілу простих чисел; імовірнісні тести на простоту і генерація простих чисел випадковим пошуком; доказово прості числа і їх побудова.
2. Визначити структуру та зміст методичного посібника.
3. Оформити теоретичний матеріал відповідно до структури
4. Скласти завдання до лабораторних робіт по темі до кожного з розділів.
5. Скласти завдання для самоперевірки для кожної з глав допомоги.
6. Апробувати складене методичний посібник з метою поліпшення подачі матеріалу.
Апробація роботи:
У 2007-2008 навчальному році дане методичний посібник вперше було запропоновано студентам 4 курсу спеціальності «Комп'ютерна безпека» груп 347 і 347 Інституту математики та комп'ютерних наук Тюменського державного університету для виконання лабораторних робіт з дисципліни «Криптографічні методи захисту інформації».
У вересні - грудні 2008 року за матеріалом розробленого методичного посібника в рамках переддипломної практики в Тюменській державної академії світової економіки, управління і права зі студентами спеціальності «Прикладна інформатика» були проведені практичні заняття з дисципліни «Інформаційна безпека» в обсязі 10 годин аудиторних занять і 12 годин самостійної роботи студентів.
Даний методичний посібник включено в план видання навчально-методичної літератури кафедри Інформаційної безпеки Тюменського державного університету на
Глава 1. Структура та зміст навчально-методичного посібника
Спочатку планувалося включити у посібник 2 розділу - «Імовірнісні тести на простоту» і «доказово прості числа». Це обумовлено тим, що різні криптосистеми використовують різні типи простих чисел. Існує 2 основних підходи до генерації простих чисел: методи, генеруючі число, що є простим з високим ступенем ймовірності (т.зв. probability methods) і методи, генеруючі числа, які є доказовою простими (т.зв. provability methods).У кожному розділі були наведені кілька тестів на простоту.
Після апробації посібник студентами 4 курсу спеціальності «Комп'ютерна безпека» груп 347 і 347 Інституту математики та комп'ютерних наук Тюменського державного університету з'ясувалося, що багато студентів не можуть самостійно описати клас великих чисел, тому було вирішено ввести в курс «криптографічні методи захисту інформації» додаткову тему « Операції з великими числами »і провести по ній лабораторне заняття, а також включити дану тему в методичний посібник.
У кожному розділі виділені теоретична частина, завдання для самостійної роботи, також було вирішено включити в другий і третій розділ тестові дані для програм, розроблених студентами, щоб кожен студент мав можливість самостійно перевірити коректність роботи своєї програми. Спрощено, тестові дані представляють собою дані на вхід програми і дані, які повинні бути отримані на виході. Також до кожної пари «вхід-вихід» докладено можливе визначення помилки алгоритму у випадку розбіжності отриманого результату з очікуваним. Більш докладно ці тестові дані описані в розділі 1.6.
1.1. Теоретичне наповнення розділу «Операції з великими числами»
Більшість сучасних алгоритмів такі як ГОСТ Р34.11-94, ГОСТ Р 34.11-2001, DSA і EСDSA накладають умови на довжину простого числа, наприклад у ГОСТ Р 34.11-2001 довжина простого числа повинна бути більше 255 біт, а за стандартом DSA 512 ≤ | p | ≤ 1024. Для реалізації даних алгоритмів необхідно вміння працювати з «великими» числами, а саме знати, як вони є в пам'яті комп'ютера, і виконувати над ними арифметичні операції.Всі алгоритми, описані в першій частині посібника, наведені для випадку, коли на основі класу 64-бітних цілих чисел описується клас 128-бітних цілих. Користуючись принципами, описаними для цього випадку, студенту надається самостійно побудувати клас 256 - або 512 -, 1024-бітних цілих чисел.
У даній главі описані алгоритми, використовуючи які можна отримати практично будь-яку арифметичну операцію, а саме: додавання, множення двох чисел (методом Карацуби), зведення в квадрат, обчислення залишку від ділення, зведення у ступінь (дихотомічний алгоритм). Всі операції над великими числами описані через такі стандартні операції над 64-бітними цілими числами: додавання, віднімання, обчислення залишку від ділення, зведення в квадрат, зведення в n-ю ступінь.
Операція складання - це перша операція, описувана в посібнику, тому вона розглянута найбільш докладно. Пропонується метод з використанням стандартної операції додавання 64-бітових чисел. Результат додавання двох n-бітних чисел пропонується поміщати в 2n-бітове число з тим, щоб при виконанні криптографічних перетворень проміжний результат не виходив за розміри класу.
Обчислення залишку від ділення. У посібнику пропонується метод Барретта. У даному методі використовуються стандартні 64-бітові операції додавання, множення, віднімання, піднесення до n-й ступінь, обчислення залишку від ділення.
Множення 2х чисел. У посібнику пропонується метод Карацуби. У даному методі використовуються стандартні 64-бітові операції додавання, множення, віднімання, піднесення до n-й ступінь, обчислення залишку від ділення. Даний метод дає перевагу у швидкості обчислення, оскільки дозволяє скоротити кількість операцій множення з 4 до 3 у порівнянні з традиційним підходом. Поряд з методом Карацуби, описується метод множення "стовпчиком" (традиційний підхід) і проводиться порівняння цих двох методів.
Зведення в квадрат. У посібнику пропонується метод, заснований на стандартних 64-бітових операціях додавання, множення і зведення в квадрат. Даний метод є більш обчислювально швидким, ніж зведення в квадрат через множення, так як в даному методі домінує операція зведення в квадрат, яка в свою чергу більш швидка, ніж операція множення.
Піднесення до степеня. У посібнику пропонується дихотомічний алгоритм. Розглядаються два варіанти цього методу - «зліва направо» і «справа наліво». У даному алгоритмі використовуються операції множення і зведення в квадрат для 256 -, 512 - або 1024-бітних цілих чисел.
Виклад кожного з методів супроводжується прикладами.
1.2. Теоретичне наповнення розділу «Імовірнісні тести на простоту»
В основному, підручники з криптографії згадують або призводять саме імовірнісні тести на простоту. Прості числа, побудовані випадковим пошуком з перевіркою імовірнісними тестами, використовуються в криптосистемах RSA, Рабіна (та інших криптосистемах, заснованих на проблемі факторизації).У цьому розділі виділено такі розділи: асимптотичний закон розподілу простих чисел, тест Ферма на простоту, тест Соловея-штрассе, тест Міллера-Рабіна.
Асимптотичний закон розподілу простих чисел. Даний розділ був включений у 2-й розділ для того, щоб дати студентові уявлення про ефективність випадкового пошуку простих чисел, оскільки саме випадковий пошук простих чисел використовується в алгоритмах побудови з використанням імовірнісних тестів на простоту.
Вводиться теоретико-числова функція π (x) - кількість простих чисел, менших x. У посібнику наводиться власне теорема (асимптотичний закон), яка визначає граничні характеристики розподілу простих чисел серед цілих позитивних чисел, а також теорема Чебишова, що визначає межі інтервалу, на якому розташовано π (x) для різних x.
Для ілюстрації використання наведених теорем розглянуто приклад. У прикладі для безлічі цілих позитивних 32-бітових чисел (таких, що старший біт дорівнює 1) з використанням асимптотичного закону обчислена ймовірність того, що навмання вибране з цієї множини число виявиться простим. Така ймовірність прийняла таке значення:
p »
Якщо звузити пошук до непарних чисел, то ймовірність зросте в 2 рази і складе p »
Після чого в методичному посібнику зроблено обгрунтований висновок про те, що випадковий пошук простих чисел доцільний.
Тест Ферма. У даному розділі розглянуто алгоритм тесту Ферма на простоту. Даний тест дозволяє ефективно визначати, чи є дане число простим, однак, з його допомогою не можна строго довести складних чисел.
У основі тесту Ферма лежить теорема Ферма. Її формулювання наведена в тексті посібника (без доведення)
Теорема Ферма (мала)
Якщо р - просте, і p не ділить a
Таким чином, якщо n-просте число, то для будь-якого підстави a буде виконуватися порівняння a n -1 ≡ 1 (mod n). Якщо n - складене число, то таке порівняння буде виконуватися лише для деяких a в силу випадкового збігу. На цьому факті заснований тест Ферма, який перевіряє дане порівняння для випадковим чином вибраних підстав a.
Також у посібнику зазначено той факт що, для даного тесту існують такі складові числа, для яких порівняння a n -1 ≡ 1 (mod n) виконуються при будь-якій підставі a. Тому, яким би не було значення параметра надійності (тобто кількість перебраних підстав a), тест Ферма буде приймати таке складене число за просте. Такі числа називаються числами Кармайкла.
Слід зазначити, що вид чисел Кармайкла визначається теоремою Кармайкла.
Теорема Кармайкла:
n - число Кармайкла
2) (p i - 1) \ (n - 1), i = 1, ..., k;
3) k
Для даного тесту вони наводять оцінку ймовірності помилки, рівна ε t, де ε
Якщо тест показав, що випробувані число є простим, то мається на увазі, що дане число є простим з імовірністю 1 - ε t.
У разі складеного випробуваного числа, що має тільки великі дільники, ε
Як приклад ілюструє роботу тесту були наведені розрахунки, як досліджуваний числа було вибрано просте число 43, параметр надійності був обраний рівний 2, підстави, з яких проводилася перевірка, були рівні 35 і 13. При цьому порівняння * виповнилося по підставі 35 і по підставі 13. Тест, таким чином, видав відповідь «43 - просте число».
Тест Соловея-штрассе. У даному розділі розглянуто алгоритм тесту на простоту Соловея-штрассе. Так само як і тест Ферма, цей тест дозволяє ефективно визначати, чи є дане число простим, однак, з його допомогою не можна строго довести складних чисел.
Цей тест заснований на відмінності між символами Якобі і Лежандра.
Символом Лежандра називається символ
Символ Якобі визначається рівністю:
Властивості символу Лежандра і символу Якобі збігаються, за винятком критерію Ейлера. Критерій Ейлера виконується для символу Лежандра, і не виконується для символу Якобі.
Критерій Ейлера: Для символу Лежандра
Алгоритм обчислення цих двох символів однаковий, тому що він заснований на використанні властивостей символів Якобі і Лежандра.
В алгоритмі тесту зустрічається обчислення символу Якобі (
Для даного тесту вони наводять оцінку ймовірності помилки, рівна ε t, де t - число ітерацій тесту, параметр надійності, а
З даної оцінки надійності тесту зроблено висновок про те, що оцінка надійності для тесту Соловея-штрассе набагато краще, ніж для тесту Ферма, навіть у тому випадку, коли φ (n) ненабагато менше n. Якщо на одній ітерації ймовірність помилкового рішення тесту не перевищує Ѕ, то вже на двох ітераціях - ј, на трьох - 1 / 8, і т. д. Вже на 14 ітераціях ймовірність помилкового рішення на перевищує 0, 0001.
Також студенту представлений приклад, який ілюструє обчислення символу Якобі
Тест Міллера-Рабіна. Тест Міллера-Рабіна, як і тести Ферма і Соловея-штрассе, будує ймовірно прості числа, тобто число, упізнані цим тестом як просте, може з деякою малою ймовірністю виявитися складовим, однак імовірність помилки у тесту Міллера-Рабіна набагато нижче, ніж у перших двох тестів. Як правило, для впізнання простого числа достатньо однієї ітерації тесту, але все ж студенту рекомендується використовувати не менше п'яти ітерацій.
Даний тест заснований на теоремі ферма, яка говорить якщо n - просте число, то для будь-якого a: 0 <a <n виконується a n -1 ≡ 1 (mod n).
У посібнику наведено оцінку ймовірності помилки ε ≤
Студенту роз'ясниться метод побудови послідовності b 0, b 1, ..., b s, а саме те, що кожен наступний член даної послідовності є квадратом попереднього по модулю n, а останній член є ні що інше як a n -1 mod n. Тобто на одному із кроків тесту будуватися послідовність квадратів за модулем n.
Як приклад, що ілюструє роботу тесту, були наведені розрахунки. В якості випробуваного числа було вибрано складене число 65, параметр надійності був обраний рівний 5.
1.3. Теоретичне наповнення розділу «доказово прості числа»
У даному розділі розглянуті алгоритми які дозволяють будувати числа, простота яких не викликає сумнівів, а саме тест Міллера на простоту, тест заснований на теоремі Поклінгтона, Процедура генерації простих чисел заданої довжини ГОСТ Р 34.10-94. Останній алгоритм використовується у вітчизняному стандарті шифрування ГОСТ Р 34.10-94.Дана тема рідко і недостатньо повно порушується в навчально-методичній літературі, незважаючи на досить велику її практичну значимість.
Підхід до отримання доказово простих чисел відрізняється від підходу, розглянутого раніше. Для побудови таких чисел не використовується випадковий пошук. З використанням таблиці простих чисел невеликого розміру, побудованої заздалегідь, будується число m (дорівнює добутку кількох простих чисел або твору простих чисел і випадкового числа), потім число n = 2m +1 перевіряється на простоту одним з нижченаведених тестів.
Тест Міллера. Даний тест, заснований на теоремі Селфріджа, придатний для доказу простоти будь-якого непарного числа, якщо відомо розкладання на прості множники числа, йому майбутнього. Однак цей тест досить трудомісткий. Для деяких чисел особливого виду побудовані спеціальні докази простоти.
Теорема Селфріджа.
Нехай n-1 =
2)
Дана теорема наведена в посібнику без доказу.
Теорема Селфріджа дає зручний критерій для доказу простоти числа. На підставі цієї теореми побудований алгоритм Міллера перевірки чисел на простоту, який вимагають повної факторизації числа n-1.
Алгоритм побудови простого числа за допомогою тесту Міллера наступний:
1. Будується таблиця малих простих чисел q i (або використовується готова таблиця);
2. Будується число m =
3. Обчислюється значення n = 2m +1;
4. Побудоване число n випробовується тестом Міллера із заданим параметром надійності.
Тест Міллера, наведений у посібнику, здійснює перевірку порівнянь (1) і (2) теореми Селфріджа для всіх q i по декількох випадковим підставах a. Якщо для якогось підстави дані порівняння не виконуються, число відкидається (як, можливо, складене). Кількість основ, по яких проводиться перевірка, є параметр надійності.
Слід зауважити, що перевірка умови (2) теореми Селфріджа можлива завдяки тому, що перевіряючому відомі всі прості числа з розкладання числа n-1, а саме числа 2 і q i. Для випадково обраного (а не побудованого) числа n перевірка тестом Міллера була б неможлива.
Числа q i з розкладання числа m не повинні бути відомі нікому крім особи, що побудував дане число, інакше кріпосістеми, побудовані з використанням такого числа, стануть вразливими для атак.
Тест, заснований на Теоремі Поклінгтона. Теорема Селфріджа дає чіткий критерій для перевірки простоти числа n, однак вимагає знання повного розкладання числа (n-1) на прості множники. Наступна теорема дозволяє обмежитися часткової факторизації (n-1).
Теорема Поклінгтона.
Нехай n = RF +1, F =
Якщо
2)
Отже, якщо розкласти n-1 на два співмножники n-1 = RF, де F>
Таким чином, можна значно скоротити кількість перевірок в порівнянні з тестом Міллера.
Алгоритм побудови простого числа за допомогою тесту на підставі теореми Поклінгтона наступний:
1. Будується таблиця малих простих чисел q i (або використовується готова таблиця);
2. Будується число F =
3. Обчислюється значення n = RF +1, де R - випадкове парне число, розмір якого на 1 біт менше розміру F;
4. Побудоване число n випробовується тестом на підставі теореми Поклінгтона із заданим параметром надійності.
Такий тест, наведений у посібнику, здійснює перевірку порівнянь (1) і (2) теореми Поклінгтона для всіх q i з розкладання числа F з кількох випадковим підставах a. Якщо для якогось підстави дані порівняння не виконуються, число відкидається (як, можливо, складене). Кількість основ, по яких проводиться перевірка, є параметр надійності.
Зауважимо, що число, побудоване за допомогою даного тесту, більш переважно для використання в якості модуля криптосистем, оскільки ніхто, навіть його творець, не знає повного розкладання числа n-1.
Для ілюстрації алгоритму в посібнику наведено приклад розрахунку алгоритму з наступними параметрами: випробувані число (n = RF +1) одно 4021, розкладання n-1 - 2 2 · 3.5.67, R = 67, F = 2 2 · 3 · 5 = 60. Студенту роз'яснюється, що в даному прикладі ймовірність того, що навмання вибране a буде задовольняти умовам теореми Поклінгтона для даного прикладу, є (1-1/67) ≈ 0,985.
Процедура генерації простих чисел заданої довжини ГОСТ Р 34.10-94. Даний процедура дозволяє будувати доказово прості числа більшого розміру на основі простих чисел меншого розміру. Заснована вона на теоремі Діемітко, яка свідчить що для n = qR +1 (де q - просте число, R - парне, R <4 (q +1)) якщо знайдеться a <n: 1) a n -1 ≡ 1 ( mod n), 2)
1.4. Розробка завдань для лабораторних і самостійних робіт
Для закріплення матеріалу лекційних занять нами були розроблені завдання для лабораторних і самостійних робіт. Усього розроблено три комплекти завдань, відповідні трьом темам: «Операції з великими числами», «Імовірнісні тести на простоту» і «доказово прості числа». Передбачається послідовне виконання цих завдань, в порядку, викладеному в методичному посібнику. На вивчення кожної з тем, відповідних розділів посібника, відводиться по 2 години лабораторних занять і по 2 години самостійної роботи. Програмна реалізація алгоритмів здійснюється студентами у комп'ютерному класі під керівництвом викладача, налагодження програми і оформлення результату - у години, відведені для самостійної роботи.Програмні модулі розроблені в рамках перерахованих тем, описані в них класи та функції, використовуються студентами надалі курсі предмета «Криптографічні методи захисту інформації» для виконання лабораторних робіт з реалізації та використання асиметричних алгоритмів шифрування, алгоритмів цифрового підпису, криптографічних протоколів, а також для виконання курсової роботи з предмета.
Завдання до першого розділу - «Операції з великими числами» не розділене на варіанти, так як результат даної лабораторної роботи має на увазі розробку класу для роботи з великими числами, який використовується при виконанні лабораторних робіт до другої і третьої головам. Виконання завдання до першого розділу, таким чином, є базовим елементом програм, які розробляються студентами в подальшому, протягом всього курсу предмета «КМЗІ».
Завдання до розділу «Операції з великими числами» включають в себе створення класу великих чисел, в якому задані наступні операції: додавання, обчислення залишку від ділення, множення двох чисел (методом Карацуби), зведення в квадрат, зведення в ступінь (дихотомічний алгоритм). Використовуючи дані операції можна отримати практично будь-яку арифметичну операцію.
Операція зведення в ступінь використовується при шифруванні даних в криптосистемах, заснованих на проблемі дискретного логарифмування, також дана операція використовується практично у всіх тестах на простоту.
Операції множення і зведення в квадрат використовуються при реалізації операції зведення в ступінь і.т.д. Виходячи з вищезазначених критеріїв, ми сформулювали завдання в порядку зростання складності, а саме першою операцією, яку потрібно реалізувати студенту, є операція додавання, як вже було описано вище, вона є базовою операцією, що використовується при реалізації інших операцій. Далі студенту належить реалізувати операцію множення. При реалізації даної операції використовується операція додавання. Наступним завданням є реалізація операції зведення в квадрат, в якій використовуються реалізовані ранні операції додавання і множення. Нарешті, студенту належить реалізувати операцію зведення в ступінь, для якої використовуються всі раніше реалізовані операції.
Існує велика кількість різних імовірнісних тестів на простоту. З більшості тестів було вибрано три «основних», які й стали предметом вивчення в рамках лабораторної роботи до глави «Імовірнісні тести на простоту». Дані тести були обрані нами виходячи з наступного: інші тести або набагато складніше, або не мають принципових відмінностей від обраних нами тестів. Ми розробили три варіанти лабораторної роботи, в кожному з варіантів студенту пропонується реалізувати один з тестів, залежно від варіанту, і закріпити свої знання, виконуючи завдання на використання асимптотичного закону розподілу простих чисел. Результат лабораторної роботи пропонується оформити у вигляді таблиці, що дозволило б викладачеві скоротити час, що витрачається на перевірку даної лабораторної роботи (це пов'язано з тим, що в даній лабораторній роботі використовуються алгоритми, комп'ютерний розрахунок яких на великих числах займає досить багато часу (на персональному комп'ютері )).
| № | 1 | 2 | ... | 10 |
| p | ||||
| n |
Також слід зазначити, що при заповненні таблиці число n має наступний сенс: кількість перебраних чисел до отримання простого, і якщо взяти середнє значення n по десяти експериментів, то результат повинен вийти досить близьким до обчисленого числа очікуваної кількості перебраних чисел до отримання простого числа. Якщо розбіжність дуже велика, то можна зробити висновок, що даний імовірнісний тест реалізований не вірно. Результат роботи реалізованого алгоритму студент може перевірити за допомогою тесту для самоперевірки (тести для самоперевірки будуть детально розглянуті в главі 1.5).
У завданні до глави «доказово прості числа» студенту пропонується реалізувати три тести заснованих на трьох різних принципах (Дані тести описані в розділі 1.3). Виходячи з цього, ми виділили три варіанти лабораторної роботи. У першому і другому варіанті лабораторної роботи пропонується використовувати тести Міллера і Поклінгтона для побудови простих чисел, а для третього варіанту пропонується генерувати прості числа за допомогою процедури ГОСТ 34.10-94. Результат лабораторної роботи студенту пропонується оформити у вигляді таблиці, що дозволяє викладачеві витрачати мінімум часу на перевірку даної роботи, а також, при відсутності часу на перевірку роботи на занятті, перевірити роботи в позаурочний час.
| № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| p | ||||||||||
| Результат перевірки імовірнісним тестом | ||||||||||
| k |
У даній таблицю в першому рядку вказується номер експерименту. У другому рядку - просте число, отримані в ході експерименту. У третьому рядку - результат перевірки цього числа p, реалізованого студентом до завдання у розділі «Імовірнісні тести на простоту». У четверну рядок необхідно внести кількість чисел, які були перевірені детерміністичних тестом і визначені як складові, але імовірнісним тест визначив їх, як прості.
Такий спосіб перевірки також дозволяє при необхідності студентам виконувати, а викладачеві перевіряти завдання, наведені в посібнику, дистанційно або повністю у час, відведений для самостійної роботи (наприклад, у випадку хвороби студента або при вивченні даних тем в рамках інших спеціальностей, де вивчення криптографії передбачено в якості спецкурсу або теми для самостійного вивчення). Слід зазначити, що комп'ютерний розрахунок роботи тестів, представлених у даному розділі, на великих числах займає досить багато часу (на персональному комп'ютері)). Студенту пропонується згенерувати десять простих чисел, алгоритм залежить від обраного варіанта, і потім перевірити дані числа одним з імовірнісних тестів (реалізованою в завданні до глави «Імовірнісні тести на простоту»). Кожне число, відкинуте при перевірці детерміністичних тестом, також перевіряти імовірнісними тестами. Дане завдання показує студенту, що деяка кількість простих чисел розпізнаються детерміністичних тестами як складові.
Отже, в результаті виконання комплексу завдань, запропонованих в методичному посібнику, студент повинен отримати такі знання, вміння та навички:
· Навички реалізації і використання класу великих чисел;
· Навички реалізації і практичного використання імовірнісних тесів на простоту;
· Знання про практичне застосування асимптотичного закону розподілу;
· Вміння розраховувати необхідну кількість ітерацій тесту для досягнення заданої ймовірності помилки (якщо студентові представитися можливість, можна застосувати до конкретної задачі, зіткнутися з реалізацією тестів на простоту, то він самостійно зможе розрахувати необхідну кількість ітерацій);
· Уявлення про відмінність імовірнісних і детерміністичних тестів на простоту (студент буде мати чітке уявлення про те, що при реалізації детерміністичних тестів він будує число, простота якого не викликає сумнівів);
· Знання про надійність тестів, про їх швидкодії;
· Знаннями про те, що не всі числа певні детерміністичних тестів, як складові насправді такими є.
Тести для самоперевірки для розділу «Операції з великими числами» являє собою дві таблиці (у першій таблиці довжина чисел не перевищує 64 біт, у другій довжина чисел не перевищує 128біт), в стовпці якої занесені числа a і b, назву операції і результат.
У таблиці нами були розроблені набори вхідних і вихідних даних для наступних арифметичних операцій: додавання, обчислення залишку від ділення, множення двох чисел, зведення в квадрат, зведення в ступінь. Студенту слід перевіряти реалізовані їм арифметичні операції в наступному порядку:
1. додавання, так як це базова операція, яка використовується при реалізації всіх інших;
2. множення, тому що при реалізації даної операції використовується лише складання, то для студента не складе труднощів знайти помилку в алгоритмі, знаючи, що операція додавання працює вірно;
3. обчислення залишку від ділення, так як при реалізації даної операції використовується бітовий зрушення, додавання і віднімання;
4. зведення в квадрат, тому що при реалізації даної операції використовуються операції додавання і множення;
5. зведення в ступінь слід перевіряти останнім, тому що при реалізації даної операції використовуються майже всі попередні перевіряються операції.
Приклад тестових даних приведено у наступній таблиці.
Числа a і b подаються в програму, реалізовану студентом, на вхід, а дані в колонках «a + b», «a * b», «a mod b», «a 2», «a b» це результати які повинна повернути програма при даних операціях (тобто на основі цих даних студент робить висновок про коректність, реалізованої ним операції). Слід зазначити, що в таблиці числа записані «0210» це слід розуміти як старшу і молодшу частину числа.
Також слід реалізовані операції перевіряти спочатку на даних з таблиці з малими значеннями (64 біта), при успішному результаті варто перевірити на даних із другої таблиці (128 біт).
Тести для самоперевірки для розділу «Імовірнісні тести на простоту» являють собою таблиці, в яких вказані вхідні дані і реакція тесту на ці вхідні дані (тобто число визначається як просте або як складене). Перед тим як використовувати таблиці за призначенням, слід встановити кількість ітерацій тесту рівним одному. Також слід зазначити, що перевіряється, кількість слід перевіряти тестом не менше десяти разів і результат перевірки звіряти з даними з таблиці. Це обумовлено тим, що ці тести завжди просте число приймає за просте, але кожен тест може прийняти складене число за просте (при використанні деяких випадкових підстав чисел). Тому якщо ми будемо перевіряти складені числа тестом, то іноді результат буде «просте» та частіше «складене». Варто відзначити, що для тесту Ферма існує клас чисел Кармайкла, які є складовими, але завжди приймаються за «прості». Такі числа також внесені в таблицю для самоперевірки.
Усього в посібнику налічується 30 наборів.
Тести для самоперевірки для розділу «доказово прості числа» являють собою таблиці, в яких вказані вхідні дані і реакція тесту на ці вхідні дані. Для тестів Міллера і Поклінгтона перевірка проводитися в два етапи перший етап полягає у перевірці даних тестів таблицею складених чисел, другий перевіркою таблицею орієнтованої на кожен з тестів. (Варто відзначити, що перед перевіркою слід встановити значення параметра надійності рівним одиниці).
Таблиця складених чисел:
Тест Міллера:
Тест Поклінгтона:
Усього в посібнику більше 30 тестових прикладів на кожен з тестів.
Для процедури генерації чисел заданої довжини ГОСТ 31.10-94 передбачена окрема таблиця, в якій вхідними даними є числа q і t а результатом є побудоване число p (Варто зазначити, що перед перевіркою слід встановити значення параметра ξ рівним 0).
Процедура генерації чисел заданої довжини ГОСТ 31.10-94:
Усього в посібнику налічується 20 наборів.
Глава 2. Апробація методичного посібника
У 2007-2008 навчальному році дане методичний посібник вперше було запропоновано студентам 4 курсу спеціальності «Комп'ютерна безпека» груп 347 і 347 Інституту математики та комп'ютерних наук Тюменського державного університету для виконання лабораторних робіт з дисципліни «Криптографічні методи захисту інформації». Даний експеримент проходив за наступною схемою: студенту пропонувалося виконати лабораторні роботи з методичного посібника, після того як він прослухав матеріал на лекційних заняттях. Лабораторні роботи, розроблені для дисципліни «Криптографічні методи захисту інформації», припускають реалізацію алгоритмів на якому-небудь мові програмування. Після аналізу програмних кодів студентських лабораторних робіт, нами була зібрані статистичні дані по помилках допущених студентами. На основі цих даних ми спробували висунути гіпотези про причини виникнення помилок.
Під час проведення даного експерименту, проаналізувавши перші, отримані нами програмні коди, ми з'ясували, що студенти не можуть у реалізації класу великих чисел, що послужило приводом додати матеріал з даної теми у посібник, оформлений у вигляді глави, під заголовком «Операції з великими числами».
Нами були доопрацьовані деякі ілюстрації до алгоритмів 1й глави («Операції з великими числами»), які дозволяють студенту сформувати більш точне уявлення про механізми що протікають «всередині» алгоритму.
Для поліпшення якості сприйняття студентом матеріалу, викладеного в методичному посібнику, нами були додані коментарі до алгоритмів і методів, зокрема, досить докладно був описаний алгоритм складання двох великих чисел, так як даний алгоритму використовується при реалізації інших алгоритмів, описаних у першому розділі, саме тому він є першим алгоритмом розділу. Були перероблені і переформульовані деякі завдання до лабораторних робіт, для того щоб забезпечити краще розуміння студентом суті завдання і полегшити перевірку їх викладачеві.
По завершенні апробації методичного посібника у Тюменському державному університеті методичний посібник сильно змінилося в плані подачі матеріалу, але основна концепція була збережена. В основному зміни торкнулися завдань лабораторних робіт, наповнення розділів теоретичним матеріалом. При аналізі результатів ми грунтувалися на припущенні, що студенти виконували лабораторні роботи самостійно, використовуючи для досягнення мети тільки матеріали лекційних занять і матеріали, викладені у методичному посібнику. Для отримання більш адекватних даних про ефективність методичного посібника було прийнято рішення провести ще одну апробацію в одному із ВУЗів міста Тюмені. Для апробації посібника була обрана ГОУ ВПО Тюменська державна академія економіки, управління та права спеціальність прикладна «інформатика в економіці». Наш вибір був обумовлений тим, що дана спеціальність у своєму навчальному плані має дисципліни, а саме «Інформаційна безпека», схожі з дисциплінами навчального плану ТюмГУ ІМіКН спеціальності «Комп'ютерна безпека», а саме «Криптографічні методи захисту інформації». Методичний посібник було запропоновано студентам 5го курсу спеціальності «Прикладна інформатика в економіці» Тюменської державної академії економіки, управління та права.
Дана апробація була проведена в рамках переддипломної практики в період з вересня по грудень 2008 року. Апробація проводилася за вже налагодженою схемою, яка раніше застосовувалася в Тюменському державному університеті. У результаті апробації були внесені наступні зміни в методичному посібнику:
Було прийнято рішення розробити тестові завдання для перевірки роботи алгоритмів, реалізованих студентами. Дані тестові завдання являють собою набори тестових даних, використовуючи які студент може оцінити правильність роботи реалізованого їм алгоритму. Як приклад таких тестових даних наведемо дані, запропоновані студенту в розділі «Імовірнісні тести на простоту» до тесту Ферма. Тестові дані оформлені у вигляді таблиці. У першій колонці цієї таблиці присутній опис чисел, які представлені в другій колонки. У третій колонці представлений результат тесту при перевірки чисел з другої колонки.
Результати здавалися у вигляді таблиць, наведених у завданнях до лабораторних робіт. Крім того, для перевірки та аналізу було зібрано вихідні коди програм, реалізованих студентами.
Крім того, студенти були опитані на предмет того, які моменти в реалізації алгоритмів генерації простих чисел викликали утруднення. Виявилося, що 7 з 11-ти осіб, які виконували генерацію простих чисел за допомогою тесту Соловея-штрассе, важко було у виконанні програмної реалізації обчислення символу Якобі, який використовується в даному тесті. Це тим більш несподівано, що більшість студентів достатньо впевнено обчислюють подібні символи самостійно (за допомогою ручки і паперу). Тому було вирішено включити в текст посібники алгоритм обчислення символу Якобі. 6 з 11-ти студентів, які реалізовували тест Міллера-Рабіна, заявили про необхідність прикладу в тексті посібника, що демонструє роботу алгоритму. Такий приклад був доданий у посібник.
Студенти, які виконували завдання по генерації простих чисел за допомогою тестів Міллера і Поклінгтона (1-й і 2-й варіанти), важко було у побудову числа p - кандидата в прості числа. Справа в тому, що число p повинно бути випадковим, непарних, і при цьому канонічне розкладання числа (p-1) має бути відомо. 18 з 22-х студентів, які виконували 1-й і 2-й варіанти, заявили про необхідність висвітлити в тексті посібника питання створення такого числа докладніше. Тому в текст посібники були включені інструкції по генерації таких чисел.
Крім того, аналіз текстів програм показав, що загальним місцем є неоптимальне виконання арифметичних операцій на великих числах, які використовуються в тестах. Зокрема, алгоритм піднесення до степеня у 19 з 33 студентів був реалізований через послідовне множення. Невелика кількість студентів (5 чол.) Зверталися до викладача за допомогою, оскільки при зведенні числа до степеня за модулем (a k mod n) отримували переповнення буферу. Виявилося, що всі ці студенти намагалися спочатку звести число до степеня, і лише потім обчислити залишок від ділення на n. Такого роду помилки, що виникають через непорозуміння процесів, що відбуваються в пам'яті комп'ютера при виконанні арифметичних операцій, зустрічалися досить часто, що послужило спонукальним мотивом до включення у посібник розділу «Операції з великими числами», що включає в себе теоретичний матеріал, завдання до лабораторних робіт .
У цілому, апробація допомоги у ТюмГУ пройшла успішно, студенти впоралися із запропонованими їм завданнями, в текст посібники були внесені необхідні зміни, дещо змінилася подача матеріалу.
Апробація проводилася за тією ж схемою що і в ТюмГУ. Студентам двох груп протягом двох занять викладачем було запропоновано виконати першу лабораторну роботу, тобто реалізувати клас для роботи з 128бітнимі числами. Спочатку викладач пояснив студентам загальнотеоретичний матеріал що стосується даної теми і реалізував спільно з ними операцію додавання, а інші операції було запропоновано реалізувати самостійно. У ході експерименту з'ясувалося, що студенти мають слабке уявлення про подання чисел у пам'яті комп'ютера, що в свою чергу, потребувало додаткових пояснень. Незважаючи на те, що операцію складання студенти робили під керівництвом викладача, досить поширеною помилкою стала помилка зв'язкова з бітом перенесення. У студентів даної спеціальності відсутня у програмі дисципліна «Теорія чисел», тому перед тим як приступити до завдань другого розділу викладачеві довелося прочитати лекцію (зокрема про практичне застосування асимптотичних закону розподілу, обчисленні символу Якобі і символу Лежандра і.т.д.). Незважаючи на те що студентів ознайомили з теоретичним матеріалом безпосередньо перед виконанням лабораторної роботи студенти важко було у застосуванні асимптотичного закону при генерації простих чисел. У результаті аналізу лабораторних робіт другого розділу зустрічалися різноманітні помилки, але дані помилки були настільки різні, що не уявлялося можливим обледеніть їх у загальні групи. Незважаючи на те, що на апробацію допомоги керівництвом вузу було виділено 10 годин, нам не вдалося апробувати третій розділ посібника, це пов'язано з тим, що викладачеві доводилося відхилятися від теми роботи і пояснювати супутній матеріал з інших дисциплін. У цілому апробація пройшла успішно, у посібник були внесені деякі корегування. Також було прийнято рішення включити у посібник тести для самоперевірки для кожної з глав, що дозволило б студенту перевіряти правильність виконаних ним робіт без участі викладача.
Матеріал, викладений у посібнику, є цілком достатнім для виконання робіт, оскільки всі необхідні алгоритми описані і наведено приклади. Матеріал викладений не в загальнотеоретичному виду, а у вигляді інструкцій і алгоритмів, що дозволяє студенту виконувати лабораторні роботи, не звертаючись до інших джерел літератури.
Даний посібник підходить як для контактного аудиторного навчання, так і для позааудиторної навчання, що надає йому деяку гнучкість, тобто воно може використовуватися не тільки на спеціальностях, на яких «Криптографічні методи захисту інформації» є обов'язковою дисципліною з виділеному аудиторним часом, але і для спеціальностей, де дана дисципліна вивчається в рамках спеціалізованого курсу. Також даний посібник може виступати в якості додаткової літератури при освоєнні даної теми студентами інших спеціальностей (таких як спеціальність «математика»). Оскільки воно дозволяє не тільки дистанційно навчатися, але і дозволяє викладачеві дистанційно перевіряти завдання, виконані студентом (це досягається шляхом використання таблиць результатів). Крім того, дані для самоперевірки дозволяють студенту перевірити коректність виконаних ним робіт без участі викладача.
У результаті прочитання студентом теоретичної частини, викладеної в посібнику, студент повинен отримати такі знання:
· Знання про основні принципи створення класу великих чисел і роботи з ним;
· Знання про способи отримання простих чисел;
· Знання про теоретико-числових принципах, на яких засновані тести на простоту;
· Знання про асимптотичному законі розподілу простих чисел;
· Знання про надійність тестів, про їх швидкодії;
· Знання про те, що не всі числа певні детерміністичних тестів як складові насправді такими є;
· Уявлення про відмінність імовірнісних і детерміністичних тестів на простоту (студент буде мати чітке уявлення про те, що при реалізації детерміністичних тестів він будує число, простота якого не викликає сумнівів).
В результаті виконання комплексу завдань, запропонованих в методичному посібнику, студент повинен отримати такі вміння та навички:
· Навички реалізації і використання класу великих чисел;
· Навички реалізації і практичного застосування імовірнісних тесів на простоту;
· Навички практичного застосування асимптотичного закону розподілу;
· Навички реалізації імовірнісних тестів на простоту;
· Вміння розраховувати необхідну кількість ітерацій тесту для досягнення заданої ймовірності помилки (якщо студентові представитися можливість, можна застосувати до конкретної задачі, зіткнутися з реалізацією тестів на простоту, то він самостійно зможе розрахувати необхідну кількість ітерацій);
· Навички реалізації алгоритмів для побудови доказово простих чисел.
Даний посібник дозволяє студенту вивчити теоретичну частину, виконати завдання для лабораторних робіт і перевірити свою роботу на тестових прикладах. Даний посібник початку орієнтоване на використання при аудиторної роботи і для самостійної роботи студентів денного відділення, однак воно може бути використано і при дистанційному навчанні, оскільки містить матеріал, необхідний на всіх етапах виконання самостійної роботи при вивченні теми «генерація великих простих чисел». А саме: короткий виклад теорії, завдання для виконання, докладне керівництво до виконання завдань і набори тестових даних для самостійної перевірки коректності реалізованих програм.
2. Алфьоров А.П., Зубов А.Ю., Кузьмін А.С., Черьомушкін А.В. Основи криптографії: Навчальний посібник. - М.: Геліос АРВ, 2002. - 480 с.
3. Введення в криптографію / Під загальною ред. В.В. Ященко. - М.: МЦНМО, 1998. - 272 с.
4. Виноградов І. М. Основи теорії чисел. - М.: Наука, 1972. - 402 с.
5. Молдовян Н.А., Молдовян А.А. Введення в криптосистеми з відкритим ключем. - СПб.: БХВ-Петербург, 2005. 288 с.: Іл.
6. Молдовян А.А., Молдовян Н.А., Рад Б.Я. Криптографія. - СПб.: Вид-во «Лань», 2001. - 224с.
7. Рябко Б.Я., Фіона О.М. Криптографічні методи захисту інформації: навчальний посібник для вузів. - М.: Гаряча лінія-Телеком, 2005. - 229 с.: Іл.
8. Черьомушкін А.В. Обчислення в алгебрі і теорії чисел. Курс лекцій. - М.: 2002.
9. Шнайер Б. Прикладна криптографія: Протоколи, алгоритми, вихідні тексти на мові Сі. - М.: Видавництво ТРІУМФ, 2003 - 816 с., Іл.
10. Goldwasser S., Bellare M. Lecture notes on cryptography. - Cambridge , Massachusetts
11. Grundbegriffe der Kryptographie / Vorlesungsscript von Eike Best - Oldenburg, 2005.
12. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 1996. - 661 p.
13. Анохін М.І., Варновскій Н.П., Сидельников В.М., Ященко В.В. Криптографія в банківській справі. http://geo.com.ru/db/msg.html?mid=1161287&uri=all.html
14. ГОСТ Р34.10-94. Інформаційна технологія. Криптографічний захист інформації. Процедури вироблення і перевірки електронного цифрового підпису на базі асиметричного криптографічного алгоритму.
15. Баричев С.Г., Гончаров В.В., Сєров Р.Є. Основи сучасної криптографії. Навчальний посібник для вузів - М.: Гаряча лінія - Телеком, 2002 - 175с.
16. Саломана А., Криптографія з відкритим ключем .- М.: Світ, 1995
Такий спосіб перевірки також дозволяє при необхідності студентам виконувати, а викладачеві перевіряти завдання, наведені в посібнику, дистанційно або повністю у час, відведений для самостійної роботи (наприклад, у випадку хвороби студента або при вивченні даних тем в рамках інших спеціальностей, де вивчення криптографії передбачено в якості спецкурсу або теми для самостійного вивчення). Слід зазначити, що комп'ютерний розрахунок роботи тестів, представлених у даному розділі, на великих числах займає досить багато часу (на персональному комп'ютері)). Студенту пропонується згенерувати десять простих чисел, алгоритм залежить від обраного варіанта, і потім перевірити дані числа одним з імовірнісних тестів (реалізованою в завданні до глави «Імовірнісні тести на простоту»). Кожне число, відкинуте при перевірці детерміністичних тестом, також перевіряти імовірнісними тестами. Дане завдання показує студенту, що деяка кількість простих чисел розпізнаються детерміністичних тестами як складові.
Отже, в результаті виконання комплексу завдань, запропонованих в методичному посібнику, студент повинен отримати такі знання, вміння та навички:
· Навички реалізації і використання класу великих чисел;
· Навички реалізації і практичного використання імовірнісних тесів на простоту;
· Знання про практичне застосування асимптотичного закону розподілу;
· Вміння розраховувати необхідну кількість ітерацій тесту для досягнення заданої ймовірності помилки (якщо студентові представитися можливість, можна застосувати до конкретної задачі, зіткнутися з реалізацією тестів на простоту, то він самостійно зможе розрахувати необхідну кількість ітерацій);
· Уявлення про відмінність імовірнісних і детерміністичних тестів на простоту (студент буде мати чітке уявлення про те, що при реалізації детерміністичних тестів він будує число, простота якого не викликає сумнівів);
· Знання про надійність тестів, про їх швидкодії;
· Знаннями про те, що не всі числа певні детерміністичних тестів, як складові насправді такими є.
1.5. Тести для самоперевірки
Для того щоб студент міг самостійно перевірити коректність виконаних ним робіт, нами були розроблені тести для самоперевірки. Тести є наборами вхідних і вихідних даних, тобто студент підставляє в реалізований їм тест набір вхідних даних і робить висновок про коректність тесту на основі порівняння отриманих ним вихідних даних і даних «еталону». У посібнику тести виділені в окрему главу, яка розташовується після завдань до голів.Тести для самоперевірки для розділу «Операції з великими числами» являє собою дві таблиці (у першій таблиці довжина чисел не перевищує 64 біт, у другій довжина чисел не перевищує 128біт), в стовпці якої занесені числа a і b, назву операції і результат.
У таблиці нами були розроблені набори вхідних і вихідних даних для наступних арифметичних операцій: додавання, обчислення залишку від ділення, множення двох чисел, зведення в квадрат, зведення в ступінь. Студенту слід перевіряти реалізовані їм арифметичні операції в наступному порядку:
1. додавання, так як це базова операція, яка використовується при реалізації всіх інших;
2. множення, тому що при реалізації даної операції використовується лише складання, то для студента не складе труднощів знайти помилку в алгоритмі, знаючи, що операція додавання працює вірно;
3. обчислення залишку від ділення, так як при реалізації даної операції використовується бітовий зрушення, додавання і віднімання;
4. зведення в квадрат, тому що при реалізації даної операції використовуються операції додавання і множення;
5. зведення в ступінь слід перевіряти останнім, тому що при реалізації даної операції використовуються майже всі попередні перевіряються операції.
Приклад тестових даних приведено у наступній таблиці.
| a | b | a + b | a * b | a mod b | a 2 | a b |
| 0 51 | 0 7 | 0 58 | 0 357 | 0 2 | 0 2601 | 0 897410677851 |
| 0 78 | 0 5 | 0 83 | 0 390 | 0 3 | 0 6084 | 0 2887174368 |
| 0 36 | 0 4 | 0 40 | 0 144 | 0 0 | 0 1296 | 0 1679616 |
| 0 21 | 0 10 | 0 31 | 0 210 | 0 1 | 0 441 | 0 16679880978201 |
| 0 5 | 0 12 | 0 18 | 0 60 | 0 5 | 0 25 | 0 244140625 |
Також слід реалізовані операції перевіряти спочатку на даних з таблиці з малими значеннями (64 біта), при успішному результаті варто перевірити на даних із другої таблиці (128 біт).
Тести для самоперевірки для розділу «Імовірнісні тести на простоту» являють собою таблиці, в яких вказані вхідні дані і реакція тесту на ці вхідні дані (тобто число визначається як просте або як складене). Перед тим як використовувати таблиці за призначенням, слід встановити кількість ітерацій тесту рівним одному. Також слід зазначити, що перевіряється, кількість слід перевіряти тестом не менше десяти разів і результат перевірки звіряти з даними з таблиці. Це обумовлено тим, що ці тести завжди просте число приймає за просте, але кожен тест може прийняти складене число за просте (при використанні деяких випадкових підстав чисел). Тому якщо ми будемо перевіряти складені числа тестом, то іноді результат буде «просте» та частіше «складене». Варто відзначити, що для тесту Ферма існує клас чисел Кармайкла, які є складовими, але завжди приймаються за «прості». Такі числа також внесені в таблицю для самоперевірки.
| Числа для перевірки | Результат тесту | |
| Прості числа | 0 8363 0 1657 0 9781 | Завжди «просте» |
| Числа Кармайкла | 0 1105 0 2465 | Для тіста Ферма-Завжди «просте», для тестів Міллера-Рабіна і Соловея-штрассе-частіше «складене», ніж «просте» |
| Складові, непарні, не Кармайкла | 0 625 0 791 0 3871 | Найчастіше «складене», ніж «просте» |
Тести для самоперевірки для розділу «доказово прості числа» являють собою таблиці, в яких вказані вхідні дані і реакція тесту на ці вхідні дані. Для тестів Міллера і Поклінгтона перевірка проводитися в два етапи перший етап полягає у перевірці даних тестів таблицею складених чисел, другий перевіркою таблицею орієнтованої на кожен з тестів. (Варто відзначити, що перед перевіркою слід встановити значення параметра надійності рівним одиниці).
Таблиця складених чисел:
| Числа для перевірки (p) | Розкладання p-1 | Розкладання F | R | Результат тесту |
| 0 335 0 437 0 657 0 779 | 2 * 167 2 2 * 109 2 4 * 41 2 * 389 | 167 109 41 389 | 2 4 16 2 | Завжди відкидаються |
| Просте число p | Розкладання (P-1) | Імовірність помилки (ймовірність того, що число буде прийнято за складене) |
| 13 | 2 2 * 3 | 0,66666 |
| 29 | 2 * 2 * 7 | 0,57142 |
| 61 | 2 * 2 * 3 * 5 | 0,73333 |
| 97 | 2 5 * 3 | 0,66666 |
| Просте число p | Розкладання F | R | Імовірність помилки (ймовірність того, що число буде прийнято за складене) |
| 13 | 2 * 2 | 3 | 0,5 |
| 29 | 7 | 4 | 0,14285 |
| 61 | 3 * 5 | 4 | 0,46666 |
| 97 | 3 * 2 2 | 8 | 0,66666 |
| 157 | 13 | 8 | 0,125 |
Для процедури генерації чисел заданої довжини ГОСТ 31.10-94 передбачена окрема таблиця, в якій вхідними даними є числа q і t а результатом є побудоване число p (Варто зазначити, що перед перевіркою слід встановити значення параметра ξ рівним 0).
Процедура генерації чисел заданої довжини ГОСТ 31.10-94:
| q | t | Побудоване число p |
| 3 | 4 | 13 |
| 5 | 6 | 41 |
| 7 | 5 | 29 |
| 5 | 5 | 31 |
| 11 | 7 | 67 |
| 11 | 8 | 199 |
| 13 | 7 | 79 |
Глава 2. Апробація методичного посібника
У 2007-2008 навчальному році дане методичний посібник вперше було запропоновано студентам 4 курсу спеціальності «Комп'ютерна безпека» груп 347 і 347 Інституту математики та комп'ютерних наук Тюменського державного університету для виконання лабораторних робіт з дисципліни «Криптографічні методи захисту інформації». Даний експеримент проходив за наступною схемою: студенту пропонувалося виконати лабораторні роботи з методичного посібника, після того як він прослухав матеріал на лекційних заняттях. Лабораторні роботи, розроблені для дисципліни «Криптографічні методи захисту інформації», припускають реалізацію алгоритмів на якому-небудь мові програмування. Після аналізу програмних кодів студентських лабораторних робіт, нами була зібрані статистичні дані по помилках допущених студентами. На основі цих даних ми спробували висунути гіпотези про причини виникнення помилок.
Під час проведення даного експерименту, проаналізувавши перші, отримані нами програмні коди, ми з'ясували, що студенти не можуть у реалізації класу великих чисел, що послужило приводом додати матеріал з даної теми у посібник, оформлений у вигляді глави, під заголовком «Операції з великими числами».
Нами були доопрацьовані деякі ілюстрації до алгоритмів 1й глави («Операції з великими числами»), які дозволяють студенту сформувати більш точне уявлення про механізми що протікають «всередині» алгоритму.
Для поліпшення якості сприйняття студентом матеріалу, викладеного в методичному посібнику, нами були додані коментарі до алгоритмів і методів, зокрема, досить докладно був описаний алгоритм складання двох великих чисел, так як даний алгоритму використовується при реалізації інших алгоритмів, описаних у першому розділі, саме тому він є першим алгоритмом розділу. Були перероблені і переформульовані деякі завдання до лабораторних робіт, для того щоб забезпечити краще розуміння студентом суті завдання і полегшити перевірку їх викладачеві.
По завершенні апробації методичного посібника у Тюменському державному університеті методичний посібник сильно змінилося в плані подачі матеріалу, але основна концепція була збережена. В основному зміни торкнулися завдань лабораторних робіт, наповнення розділів теоретичним матеріалом. При аналізі результатів ми грунтувалися на припущенні, що студенти виконували лабораторні роботи самостійно, використовуючи для досягнення мети тільки матеріали лекційних занять і матеріали, викладені у методичному посібнику. Для отримання більш адекватних даних про ефективність методичного посібника було прийнято рішення провести ще одну апробацію в одному із ВУЗів міста Тюмені. Для апробації посібника була обрана ГОУ ВПО Тюменська державна академія економіки, управління та права спеціальність прикладна «інформатика в економіці». Наш вибір був обумовлений тим, що дана спеціальність у своєму навчальному плані має дисципліни, а саме «Інформаційна безпека», схожі з дисциплінами навчального плану ТюмГУ ІМіКН спеціальності «Комп'ютерна безпека», а саме «Криптографічні методи захисту інформації». Методичний посібник було запропоновано студентам 5го курсу спеціальності «Прикладна інформатика в економіці» Тюменської державної академії економіки, управління та права.
Дана апробація була проведена в рамках переддипломної практики в період з вересня по грудень 2008 року. Апробація проводилася за вже налагодженою схемою, яка раніше застосовувалася в Тюменському державному університеті. У результаті апробації були внесені наступні зміни в методичному посібнику:
Було прийнято рішення розробити тестові завдання для перевірки роботи алгоритмів, реалізованих студентами. Дані тестові завдання являють собою набори тестових даних, використовуючи які студент може оцінити правильність роботи реалізованого їм алгоритму. Як приклад таких тестових даних наведемо дані, запропоновані студенту в розділі «Імовірнісні тести на простоту» до тесту Ферма. Тестові дані оформлені у вигляді таблиці. У першій колонці цієї таблиці присутній опис чисел, які представлені в другій колонки. У третій колонці представлений результат тесту при перевірки чисел з другої колонки.
2.1 Апробація в Тюменському державному університеті
Перша апробація методичного посібника проходила в квітні 2008 року в інституті Математики та комп'ютерних наук ТюмГУ на спеціальності «Комп'ютерна безпека» (групи 347, 348) в рамках курсу «Криптографічні методи захисту інформації». До моменту апробації посібник містило тільки два розділи: імовірнісні тести на простоту »і« доказово прості числа ». Кожен розділ містив теоретичний матеріал з даного розділу, а саме опис алгоритмів тестів на простоту і завдання для виконання до кожного розділу. Студентам двох груп (347 і 348 група) протягом двох лабораторних занять (4 навчальні години) давалися завдання з другого і третього розділів методичного посібника. При виконанні цих завдань студенти користувалися лекційним матеріалом і теоретичним матеріалом з методичного посібника. Завдання виконувалися ними в аудиторії під керівництвом викладача, а також під час, відведений для самостійної роботи.Результати здавалися у вигляді таблиць, наведених у завданнях до лабораторних робіт. Крім того, для перевірки та аналізу було зібрано вихідні коди програм, реалізованих студентами.
Крім того, студенти були опитані на предмет того, які моменти в реалізації алгоритмів генерації простих чисел викликали утруднення. Виявилося, що 7 з 11-ти осіб, які виконували генерацію простих чисел за допомогою тесту Соловея-штрассе, важко було у виконанні програмної реалізації обчислення символу Якобі, який використовується в даному тесті. Це тим більш несподівано, що більшість студентів достатньо впевнено обчислюють подібні символи самостійно (за допомогою ручки і паперу). Тому було вирішено включити в текст посібники алгоритм обчислення символу Якобі. 6 з 11-ти студентів, які реалізовували тест Міллера-Рабіна, заявили про необхідність прикладу в тексті посібника, що демонструє роботу алгоритму. Такий приклад був доданий у посібник.
Студенти, які виконували завдання по генерації простих чисел за допомогою тестів Міллера і Поклінгтона (1-й і 2-й варіанти), важко було у побудову числа p - кандидата в прості числа. Справа в тому, що число p повинно бути випадковим, непарних, і при цьому канонічне розкладання числа (p-1) має бути відомо. 18 з 22-х студентів, які виконували 1-й і 2-й варіанти, заявили про необхідність висвітлити в тексті посібника питання створення такого числа докладніше. Тому в текст посібники були включені інструкції по генерації таких чисел.
Крім того, аналіз текстів програм показав, що загальним місцем є неоптимальне виконання арифметичних операцій на великих числах, які використовуються в тестах. Зокрема, алгоритм піднесення до степеня у 19 з 33 студентів був реалізований через послідовне множення. Невелика кількість студентів (5 чол.) Зверталися до викладача за допомогою, оскільки при зведенні числа до степеня за модулем (a k mod n) отримували переповнення буферу. Виявилося, що всі ці студенти намагалися спочатку звести число до степеня, і лише потім обчислити залишок від ділення на n. Такого роду помилки, що виникають через непорозуміння процесів, що відбуваються в пам'яті комп'ютера при виконанні арифметичних операцій, зустрічалися досить часто, що послужило спонукальним мотивом до включення у посібник розділу «Операції з великими числами», що включає в себе теоретичний матеріал, завдання до лабораторних робіт .
У цілому, апробація допомоги у ТюмГУ пройшла успішно, студенти впоралися із запропонованими їм завданнями, в текст посібники були внесені необхідні зміни, дещо змінилася подача матеріалу.
2.2 Апробація в Тюменській державної академії економіки, управління та права
Апробація допомоги у ТГФЕУП проводилася в рамках переддипломної практики в період з вересня по грудень 2008 року. На апробацію допомоги керівництвом вузу було виділено 10 годин аудиторної навантаження. У апробації брали участь студенти п'ятого курсу спеціальності «Прикладна інформатика в економіці». Дисципліна «Криптографічні методи захисту інформації» не є профільною на даній спеціальності, а виступає в якості спеціального курсу. На момент апробації методичний посібник містило три розділи: «Операції з великими числами», «Імовірнісні тести на простоту», «доказово прості числа» також завдання для лабораторних і самостійних робіт.Апробація проводилася за тією ж схемою що і в ТюмГУ. Студентам двох груп протягом двох занять викладачем було запропоновано виконати першу лабораторну роботу, тобто реалізувати клас для роботи з 128бітнимі числами. Спочатку викладач пояснив студентам загальнотеоретичний матеріал що стосується даної теми і реалізував спільно з ними операцію додавання, а інші операції було запропоновано реалізувати самостійно. У ході експерименту з'ясувалося, що студенти мають слабке уявлення про подання чисел у пам'яті комп'ютера, що в свою чергу, потребувало додаткових пояснень. Незважаючи на те, що операцію складання студенти робили під керівництвом викладача, досить поширеною помилкою стала помилка зв'язкова з бітом перенесення. У студентів даної спеціальності відсутня у програмі дисципліна «Теорія чисел», тому перед тим як приступити до завдань другого розділу викладачеві довелося прочитати лекцію (зокрема про практичне застосування асимптотичних закону розподілу, обчисленні символу Якобі і символу Лежандра і.т.д.). Незважаючи на те що студентів ознайомили з теоретичним матеріалом безпосередньо перед виконанням лабораторної роботи студенти важко було у застосуванні асимптотичного закону при генерації простих чисел. У результаті аналізу лабораторних робіт другого розділу зустрічалися різноманітні помилки, але дані помилки були настільки різні, що не уявлялося можливим обледеніть їх у загальні групи. Незважаючи на те, що на апробацію допомоги керівництвом вузу було виділено 10 годин, нам не вдалося апробувати третій розділ посібника, це пов'язано з тим, що викладачеві доводилося відхилятися від теми роботи і пояснювати супутній матеріал з інших дисциплін. У цілому апробація пройшла успішно, у посібник були внесені деякі корегування. Також було прийнято рішення включити у посібник тести для самоперевірки для кожної з глав, що дозволило б студенту перевіряти правильність виконаних ним робіт без участі викладача.
Висновок
Результатом даної дипломної роботи є методичний посібник досить повно і докладно висвітлює тему генерації великих простих чисел. Поставлена мета - розробити методичний посібник на тему «Генерація простих чисел» для спеціальності «Комп'ютерна безпека» Тюменського державного університету, що включає в себе теоретичний матеріал, завдання до практичних робіт, вказівки до їх виконання та матеріали для перевірки якості виконаних завдань, досягнута в повному обсязі .Матеріал, викладений у посібнику, є цілком достатнім для виконання робіт, оскільки всі необхідні алгоритми описані і наведено приклади. Матеріал викладений не в загальнотеоретичному виду, а у вигляді інструкцій і алгоритмів, що дозволяє студенту виконувати лабораторні роботи, не звертаючись до інших джерел літератури.
Даний посібник підходить як для контактного аудиторного навчання, так і для позааудиторної навчання, що надає йому деяку гнучкість, тобто воно може використовуватися не тільки на спеціальностях, на яких «Криптографічні методи захисту інформації» є обов'язковою дисципліною з виділеному аудиторним часом, але і для спеціальностей, де дана дисципліна вивчається в рамках спеціалізованого курсу. Також даний посібник може виступати в якості додаткової літератури при освоєнні даної теми студентами інших спеціальностей (таких як спеціальність «математика»). Оскільки воно дозволяє не тільки дистанційно навчатися, але і дозволяє викладачеві дистанційно перевіряти завдання, виконані студентом (це досягається шляхом використання таблиць результатів). Крім того, дані для самоперевірки дозволяють студенту перевірити коректність виконаних ним робіт без участі викладача.
У результаті прочитання студентом теоретичної частини, викладеної в посібнику, студент повинен отримати такі знання:
· Знання про основні принципи створення класу великих чисел і роботи з ним;
· Знання про способи отримання простих чисел;
· Знання про теоретико-числових принципах, на яких засновані тести на простоту;
· Знання про асимптотичному законі розподілу простих чисел;
· Знання про надійність тестів, про їх швидкодії;
· Знання про те, що не всі числа певні детерміністичних тестів як складові насправді такими є;
· Уявлення про відмінність імовірнісних і детерміністичних тестів на простоту (студент буде мати чітке уявлення про те, що при реалізації детерміністичних тестів він будує число, простота якого не викликає сумнівів).
В результаті виконання комплексу завдань, запропонованих в методичному посібнику, студент повинен отримати такі вміння та навички:
· Навички реалізації і використання класу великих чисел;
· Навички реалізації і практичного застосування імовірнісних тесів на простоту;
· Навички практичного застосування асимптотичного закону розподілу;
· Навички реалізації імовірнісних тестів на простоту;
· Вміння розраховувати необхідну кількість ітерацій тесту для досягнення заданої ймовірності помилки (якщо студентові представитися можливість, можна застосувати до конкретної задачі, зіткнутися з реалізацією тестів на простоту, то він самостійно зможе розрахувати необхідну кількість ітерацій);
· Навички реалізації алгоритмів для побудови доказово простих чисел.
Даний посібник дозволяє студенту вивчити теоретичну частину, виконати завдання для лабораторних робіт і перевірити свою роботу на тестових прикладах. Даний посібник початку орієнтоване на використання при аудиторної роботи і для самостійної роботи студентів денного відділення, однак воно може бути використано і при дистанційному навчанні, оскільки містить матеріал, необхідний на всіх етапах виконання самостійної роботи при вивченні теми «генерація великих простих чисел». А саме: короткий виклад теорії, завдання для виконання, докладне керівництво до виконання завдань і набори тестових даних для самостійної перевірки коректності реалізованих програм.
Список літератури
1. Агібалов Г.П. Вибрані теореми початкового курсу криптографії: Навчальний посібник. - Томськ: Вид-во НТЛ, 2005. - 116 с.2. Алфьоров А.П., Зубов А.Ю., Кузьмін А.С., Черьомушкін А.В. Основи криптографії: Навчальний посібник. - М.: Геліос АРВ, 2002. - 480 с.
3. Введення в криптографію / Під загальною ред. В.В. Ященко. - М.: МЦНМО, 1998. - 272 с.
4. Виноградов І. М. Основи теорії чисел. - М.: Наука, 1972. - 402 с.
5. Молдовян Н.А., Молдовян А.А. Введення в криптосистеми з відкритим ключем. - СПб.: БХВ-Петербург, 2005. 288 с.: Іл.
6. Молдовян А.А., Молдовян Н.А., Рад Б.Я. Криптографія. - СПб.: Вид-во «Лань», 2001. - 224с.
7. Рябко Б.Я., Фіона О.М. Криптографічні методи захисту інформації: навчальний посібник для вузів. - М.: Гаряча лінія-Телеком, 2005. - 229 с.: Іл.
8. Черьомушкін А.В. Обчислення в алгебрі і теорії чисел. Курс лекцій. - М.: 2002.
9. Шнайер Б. Прикладна криптографія: Протоколи, алгоритми, вихідні тексти на мові Сі. - М.: Видавництво ТРІУМФ, 2003 - 816 с., Іл.
10. Goldwasser S., Bellare M. Lecture notes on cryptography. -
11. Grundbegriffe der Kryptographie / Vorlesungsscript von Eike Best - Oldenburg, 2005.
12. Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. - CRC Press, 1996. - 661 p.
13. Анохін М.І., Варновскій Н.П., Сидельников В.М., Ященко В.В. Криптографія в банківській справі. http://geo.com.ru/db/msg.html?mid=1161287&uri=all.html
14. ГОСТ Р34.10-94. Інформаційна технологія. Криптографічний захист інформації. Процедури вироблення і перевірки електронного цифрового підпису на базі асиметричного криптографічного алгоритму.
15. Баричев С.Г., Гончаров В.В., Сєров Р.Є. Основи сучасної криптографії. Навчальний посібник для вузів - М.: Гаряча лінія - Телеком, 2002 - 175с.
16. Саломана А., Криптографія з відкритим ключем .- М.: Світ, 1995