Размещено на http://www.allbest.ru/

Дипломна робота

На тему

Реалізація алгоритму обміну секретної інформації із стисненням

Зміст

• Вступ
• Розділ І. Методи та алгоритми обміну секретною інформацією
• 1.1.Види секретної інформації та методи захисту.
• 1.2. Алгоритми захисту зберігання та обміну секретною інформацією
• 1.3. Тип і об'єм вхідних даних
• 1.4. Стиснення інформації. Архіватори
• 1.5. Опис конкретного методу шифрування
• Розділ ІІ. Програмна реалізація системи алгоритму шифрування зі стисненням
• 2.1.Основні завдання та вимоги до системи шифрування зі стисненням Export
• 2.1.1. Вимоги до системи
• 2.1.2. Модель розробки системи
• 2.2. Вибір методу реалізації програмного продукту Export
• 2.3. Призначення та опис програмного продукту Export
• 2.4. Організація тестування та налагодження програмного продукту Export
• 2.5. Рекомендації по впровадження і використанню програмного продукту Export
• Висновки
• Список використаних джерел
• Додатки
• Додаток 1

Вступ

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

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

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

Тема: Реалізація алгоритму обміну секретної інформації із стисненням.

Мета роботи: проаналізувати методику та алгоритми обміну секретною інформацією та реалізувати один із них.

Об'єкт роботи: алгоритми обміну секретною інформацією

Предмет роботи: алгоритми обміну секретною інформацією із стисненням.

Завдання роботи:

1. Розглянути види секретної інформації та методи захисту.

2. Розглянути алгоритми захисту, зберігання та обміну секретною інформацією.

3. Провести аналіз симетричних та асиметричних методів шифрування зі стисненням.

4. Провести аналіз аналогічних програмних розробок.

5. Реалізувати алгоритм обміну секретної інформації із стисненням.

Розділ І. Методи та алгоритми обміну секретною інформацією

В цьому розділі розглянуті основні властивості предмета обговорення - інформації, проблеми її захисту, зберігання,обміну та стиснення.

1.1 Види секретної інформації та методи захисту

Інформація -- абстрактне поняття, що має різні значення залежно від контексту. Походить від латинського слова «informatio», яке має декілька значень:

· роз'яснення; виклад фактів, подій; витлумачення;

· представлення, поняття;

· ознайомлення, просвіта.

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

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

Інформація - це товар, і, отже, є об'єктом товарних відносин. В Україні інформаційні відносини регулюються декількома законами, у тому числі і законом «Про інформацію» []. Зокрема, у цьому законі в статті 18 встановлена класифікація інформації з видів:

статистична інформація;

масова інформація;

інформація про діяльність державних органів влади й органів місцевого і регіонального самоврядування;

правова інформація;

інформація про особистість;

інформація довідково-енциклопедичного характеру;

соціологічна інформація.

Оскільки інформацію можна продати, купити, імпортувати, фальсифікувати, украсти і т.д., то з цього виникає, що вона повинна якимось чином оцінюватися. Далі, інформація, якою обмінюється людина через машину з іншою людиною чи машиною, може бути важливої і, отже, є предметом захисту. Однак захисту підлягає не всяка інформація, а тільки та, котра має ціну, тобто цінна інформація. Цінною ж стає та інформація, володіння якою дозволить її існуючому чи потенційному власнику одержати який-небудь виграш: моральний, матеріальний, політичний і т.д. Оскільки в людському суспільстві завжди існують люди, які бажають мати якійсь виграш над іншими, то вони бажають незаконним шляхом одержати коштовну інформацію і у її власника виникає необхідність її захищати. Цінність інформації є критерієм при прийнятті будь-якого рішення про її захист. Хоча було багато різних спроб формалізувати цей процес з використанням методів теорії інформації та аналізу рішень, процес оцінки інформації залишається дуже суб'єктивним.

Для оцінки потрібен розподіл інформації на категорії не тільки відповідно до її цінності, але за важливістю. За рівнем важливості можна розділити інформацію на категорії таким чином:

життєво важлива незамінна інформація, наявність якої необхідна для функціонування системи;

важлива інформація - інформація, що може бути замінена чи відновлена, але процес її відновлення важкий і зв'язаний з великими витратами;

корисна інформація - інформація, яку важко відновити, однак система може досить ефективно функціонувати і без неї;

несуттєва інформація - інформація, без якої система продовжує існувати.

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

Існують визначення груп осіб, пов'язаних з обробкою інформації: власник - організація чи особа, що володіють інформацією; джерело - організація чи особа, що поставляють інформацію; ЗЛ - організація чи особа, що прагнуть незаконно одержати інформацію. Відношення цих груп до значимості однієї і тієї ж інформації може бути різним: для однієї - важлива, для іншої - навпаки. секретна інформація алгоритм шифрування

Приведені категорії важливості цілком погоджуються з існуючим принципом розподілу інформації за рівнями таємності (або секретності). Рівень таємності - це адміністративні чи законодавчі заходи, що відповідають мірі відповідальності особи за витік конкретної інформації, регламентованої спеціальними документами, з урахуванням державних, воєнно-стратегічних, комерційних, службових чи особистих інтересів. Такою інформацією може бути державна, військова, комерційна, службова чи особиста таємниця. Рівень таємності визначається грифом, що привласнюється тій чи іншій інформації. В Україні в державних структурах установлені наступні рівні (грифи) таємності: несекретно, для службового користування, таємно, цілком таємно (Н, ДСК, Т, ЦТ). Аналогічна термінологія існує в більшості країн світу і виглядає наступним чином: unclassified, confidential, secret, top secret (U, C, S, TS). Така класифікація дозволяє визначити просту лінійну порядкову шкалу цінності інформації: Н<ДСК<Т<ЦТ (U<C<S<TS). За цією шкалою відразу видно, до якої категорії інформації необхідно пред'являти більш високі вимоги щодо її захисту.

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

На кінець, звернемо увагу на розбіжність між визначеною вище таємністю і безпекою інформації.

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

За способами реалізації всі заходи забезпечення безпеки АС підрозділяються на правові (законодавчі), морально-етичні, організаційні (адміністративні), фізичні і технічні ( програмні та апаратурні).

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

До морально-етичних заходів протидії відносяться норми поведінки, які традиційно склалися або складаються паралельно розповсюдженню ЕОМ в країні або суспільстві. Більшою частиною ці норми не є обов'язковими, як, наприклад, законодавчо затверджені нормативні, однак їх недотримання веде звичайно до падіння авторитету, престижу людини, групи осіб або організації.

Законодавчі та морально-етичні заходи протидії є універсальними в тому сенсі, що принципово можуть застосовуватися для всіх каналів проникнення і НСД до АС і інформації. В деяких випадках вони є єдиними, як, наприклад, при захисті відкритої інформації від незаконного тиражування або при захисті від зловживань службовим положення при роботі з інформацією.

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

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

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

В даний час особливо актуальною стала оцінка вже використовуваних криптоалгоритмів. Задача визначення ефективності засобів захисту найчастіше більш трудомістка, ніж їх розробка, вимагає наявності спеціальних знань і, як правило, більш високої кваліфікації, ніж задача розробки. Це обставини призводять до того, що на ринку з'являється безліч засобів криптографічного захисту інформації, про які ніхто не може сказати нічого визначеного. При цьому розробники тримають криптоалгоритм (як показує практика, часто нестійкий) в секреті. Однак завдання точного визначення даного криптоалгоритму не може бути гарантовано складної хоча б тому, що він відомий розробникам. Крім того, якщо порушник знайшов спосіб подолання захисту, то не в його інтересах про це заявляти. Тому суспільству має бути вигідно відкрите обговорення безпеки систем захисту інформації масового застосування, а приховування розробниками криптоалгоритму повинно бути неприпустимим.

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

1.2 Алгоритми захисту зберігання та обміну секретною інформацією

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

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

До деяких відомих, поширених алгоритмів з гарною репутацією належать: Twofish, Serpent, AES (або Рейндайль), Гост -89, Blowfish, CAST5, RC5, TDES (3DES), та IDEA.

3DES

Стандарт шифрування даних (The Data Encription Standard, DES) розроблений фірмою IВМ і затверджений в 1975 році. Він базується на тому, що початкова інформація розбивається на блоки довжиною 64 біти. Блок інформації підлягає первинній перестановці. Після цього за допомогою логічної функції додавання за модулем 2 та подальших перестановок формується кінцева криптограма. Алгоритм є досить складним, але на практиці доведена його надійність.

AES

Advanced Encryption Standard (AES), також відомий під назвою Rijndael -- симетричний алгоритм блочного шифрування, прийнятий в якості американского стандарту шифрування урядом США. AES має фіксовану довжину у 128 біт, а розмір ключа може приймати значення 128, 192 або 256 біт. Через фіксований розмір блоку AES оперує із масивом 4Ч4 байт, що називається станом (версії алгоритму із більшим розміром блоку мають додаткові колонки).

RC5

RC5 (Ron's Code 5 або Rivest's Cipher 5) - це алгоритм блочного шифрування, розроблений Роном Рівестом з компанії RSA Security Inc. зі змінною кількістю раундів, довжиною блоку і довжиною ключа. Це розширює сферу використання та спрощує перехід на більш сильний варіант алгоритму. Оскільки алгоритм RC5 має змінні параметри, то для специфікації алгоритму з конкретними параметрами прийнято позначення RC5-W/R/b, де

W - половина довжини блоку в бітах, можливі значення 16, 32 і 64. Для ефективної реалізації величину W рекомендують брати рівним машинному слову. Наприклад, для 32-бітних платформ оптимальним буде вибір W = 32, що відповідає розміру блоку 64 біта.

R - число раундів, можливі значення від 0 до 255. Збільшення числа раундів забезпечує збільшення рівня безпеки шифру. Так, при R = 0 інформація шифруватися не буде. Також алгоритм RC5 використовує таблицю розширених ключів розміру 2 (R + 1) слів, яка виходить з ключа заданого користувачем.

b - довжина ключа в байтах, можливі значення від 0 до 255.

ГОСТ-89

ГОСТ 28147-89 - це стандарт симетричного шифрування, введений в 1990 році. Повна назва - «ГОСТ 28147-89 Системи обробки інформації. Криптографічний захист. Алгоритм криптографічного перетворення». Блочний шифроалгоритм. При використанні методу шифрування з гамування, може виконувати функції поточного шифроалгоритма. ГОСТ-89 - це алгоритм з 256-бітним ключем і 32 циклами перетворення, що оперує 64-бітними блоками. Основа алгоритму шифру - Мережа Фейстеля. Базовим режимом шифрування за ГОСТ 28147-89 є режим простої заміни (визначені також більш складні режими гамування, гамування із зворотним зв'язком і режим імітовставки). Для зашифрування в цьому режимі відкритий текст спочатку розбивається на дві половини (молодші біти - A, старші біти - B). На i-му циклі використовується підключ Ki. Для генерації підключів вихідний 256-бітний ключ розбивається на вісім 32-бітних блоків: K1 ... K8. Ключі K9 ... K24 є циклічним повторенням ключів K1 ... K8 (нумеруються від молодших бітів до старших). Ключі K25 ... K32 є ключами K1 ... K8, що йдуть у зворотному порядку. Після виконання всіх 32 раундів алгоритму, блоки A33 і B33 склеюються (зверніть увагу, що старшим бітом стає A33, а молодшим - B33) - результат є результат роботи алгоритму. Розшифрування виконується так само, як і зашифрування, але інвертується порядок підключений Ki.

Асиметричні алгоритми шифрування -- алгоритми шифрування, які використовують різні ключі для шифрування та розшифрування даних.

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

Прикладами криптосистем з відкритим ключем є Elgamal (названа на честь автора, Тахіра Ельгамаля), RSA (названа на честь винахідників: Рона Рівеста, Аді Шаміра і Леонарда Адлмана), Diffie-Hellman і DSA, Digital Signature Algorithm (винайдений Девідом Кравіцом), Рабін.

RSA

Алгоритм RSA винайдений Р. Рівестом, А. Шаміром та Л. Алдманом в 1977 році. За першими літерами їх прізвищ і названо цей метод шифрування. Суть метода полягає в тому, що, знаючи відкритий текст М, модуль N та показник степіні е, можна визначити . Функція зведення у степінь є односторонньою функцією з точки зору обчислення коренів та логарифмів. У системі RSA використовується той факт, що знаходження добутку великих простих чисел не вимагає тривалих обчислень, в той час як розкладання добутку двох таких чисел є обчислювально важким завданням. Для того щоб утворити таємний та відкритий ключі, перший з користувачів за випадковим законом вибирає два великих простих числа Р та Q, перемноживши які, одержує двоскладовий модуль N. У вигляді відкритого ключа вибирається N та спеціально вибраний показник степіні е, а у вигляді таємного ключа - числа Р та Q. Будь-яка людина, яка знає N, може здійснити процедуру шифрування, яка полягає у зведенні в степінь за модулем N. Але лише той, кому відомі Р та Q, може текст розшифрувати. Використовуючи числа Р та Q, можна визначити значення функції Ейлера ц(Н), що показує кількість позитивних цілих чисел від 1 до Н, які є взаємно простими з N:

ц (N) = (P - 1) (Q - 1) .

Знаючи ц (N), користувач може визначити таке число d, що:

.

Якщо криптограму звести у степінь d, то в результаті можна одержати відкритий текст М:

Ель-Гамаля

Дана система є альтернативою RSA й при однаковому розмірі ключа забезпечує ту ж криптостійкість. Основу системи складають параметри p і g - числа, перше з яких - просте, а друге - ціле. Користувач А генерує секретний ключ а й обчислює відкритий ключ

y = gа mod p.

Якщо користувач Б хоче послати користувачеві А повідомлення m, то він вибирає випадкове число k, менше, ніж p і обчислює

y₁ = gk mod p та y₂ = m yk.

Потім користувач Б посилає (y1,y2) користувачеві А. Користувач А, отримавши зашифроване повідомлення, відновлює його:

m = (_y1a mod p) y₂.

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

1. Створення автоматизованих комплексів розподілу ключів в зашифрованому вигляді через відкриті канали передачі даних і автоматизований введення ключів у шіфротехніку. Цей напрямок передбачає наявність територіальних центрів створення та розсилання ключової інформації;

2. Використання асиметричних алгоритмів та криптографічних протоколів для безпечного і оперативного розподілу ключової інформації. Такий підхід набув широкого поширення завдяки появі глобальних мереж передачі даних (Internet, intranet і т.д.).

До відомих алгоритмів обміну ключами відносять такі алгоритми: Рабіна, Діффі-Хеллмана, Шенкса тощо.

Схема Рабіна

Генерація ключів для схеми шифрування Рабіна

1. Згенерувати два великих простих числа p та q приблизно однакової довжини;

2. Обчислити n = p * q;

3. Відкритим ключем А є n, закритим ключем А є p та q.

Схема шифрування Рабіна шифрує повідомлення M для A, яке потім A дешифрує.

Кодування інформації Дії B:

1. Отримати відкритий ключ n від А;

2. Представити повідомлення m як число у проміжку {0, ..., n-1};

3. Обчислити C = M² mod n;

4. Надіслати зашифроване повідомлення C до А.

Декодування інформації Дії A:

1. Обчислити квадратні корені із числа C. Нехай ними будуть m₁, m₂, m₃, m₄. (Якщо НСД(m, n) ??1, то рівняння x² ??C може мати один чи два корені);

2. Деякими допоміжними засобами встановити, який із коренів m₁, m₂, m₃, m₄ є вихідним повідомленням M.

Приклад

Генерація ключа. p = 277, q = 331, n = 277 * 331 = 91687;

Кодування. Перед кодуванням 10 бітового повідомлення M = 1001111001₂ припишемо в кінці його останні 6 бітів: M' = 1001111001111001₂ = 40569.

C = M'² mod n = 40569² mod 91687 = 62111

Декодування. Обчислюємо квадратні корені з числа 62111 за модулем 91687:

m₁ = 69654, m₂ = 22033, m₃ = 40569, m₄ = 51118,

які у двійковому представленні мають вигляд:

m₁ = 10001000000010110, m₂ = 1010110000100001,

m₃ = 1001111001111001, m₄ = 1100011110101110

Оскільки лише в одному із коренів останні 6 біт повторюються, то вихідним повідомленням було M = m₃.

Проблема дублювання інформації. Отримувач закодованого повідомлення С стоїть перед проблемою знаходження вихідного повідомлення M серед квадратних коренів m₁, m₂, m₃, m₄. Для цього можна перед кодуванням продублювати певну частину даних (наприклад останні 64 біти). Тоді з великою ймовірністю у одного із коренів m_i будуть продубльовані останні біти, який і вважається переданим повідомленням M. Якщо жодне із m_i не мають дублюючих даних, то повідомлення С вважається хибним і не розглядається далі.

Алгоритм Діффі-Хеллмана

Алгориитм Діффі-Хеллмана (англ. Diffie-Hellman, DH) -- алгоритм, що дозволяє двом сторонам отримати загальний секретний ключ, використовуючи незахищений від прослуховування, але захищений від підміни, канал зв'язку. Цей ключ може бути використаний для шифрування подальшого обміну за допомогою алгоритму симетричного шифрування.

Алгоритм був вперше опублікований Уітфілд Діффі (Whitfield Diffie) та Мартіном Хеллманом в 1976 році.

У 2002 році Хеллман запропонував називати даний алгоритм «Діффі-Хеллмана-Меркля», визнаючи внесок Меркля в винахід криптографії з відкритим ключем.

Припустимо, що обом абонентам відомі деякі два числа g і p (наприклад, вони можуть бути «зашиті» у програмне забезпечення), які не є секретними і можуть бути відомі також іншим зацікавленим особам. Для того, щоб створити невідомий більш нікому секретний ключ, обидва абонента генерують великі випадкові числа: перший абонент - число a, другий абонент - число b. Потім перший абонент обчислює значення A=g^a mod p і пересилає його другому, а другий обчислює B=g^b mod p і передає першому. Передбачається, що зловмисник може отримати обидва цих значення, але не модифікувати їх (тобто у нього немає можливості втрутитися в процес передачі). На другому етапі перший абонент на основі наявної в нього a і отриманого по мережі B обчислює значення B^a mod p=g^ab mod p, а другий абонент на основі наявної в нього b і отриманого по мережі A обчислює значення g^a mod p = g^b mod p. Неважко бачити, у обох абонентів вийшло одне і те ж число: K= g^ab mod p. Його вони і можуть використовувати як секретного ключа, оскільки тут зловмисник зустрінеться з практично нерозв'язною (за розумний час) проблемою обчислення g^ab mod p по перехоплених g^a mod p і g^b mod p, якщо числа p, a, b вибрані досить великими.

При роботі алгоритму, кожна сторона:

· генерує випадкове натуральне число a - закритий ключ

· спільно з віддаленою стороною встановлює відкриті параметри p і g (зазвичай значення p і g генеруються на одній стороні і передаються іншій), де

p є випадковим простим числом

g є первісним коренем за модулем p

· обчислює відкритий ключ A, використовуючи перетворення над закритим ключем

A = g^a mod p

· обмінюється відкритими ключами з віддаленою стороною

· обчислює загальний секретний ключ K, використовуючи відкритий ключ видаленої сторони B і свій закритий ключ a

K = B^a mod p

К виходить рівним з обох сторін, тому що:

B^a mod p = (g^b mod p)^a mod p = g^ab mod p = (g^a mod p)^b mod p = A^b mod p

У практичних реалізаціях, для a і b використовуються числа порядку 10100 і p порядку 10300. Число g не зобов'язане бути великим і зазвичай має значення в межах першого десятка.

Алгоритм Шенкса

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

Дискретна задача логарифму має принципове значення для області шифрування з відкритим ключем. Більшість з найбільш часто використовуваних систем шифрування засновані на припущенні, що дискретних логарифм дуже важко обчислити, чим важче, тим більше вона забезпечує безпеку передачі даних. Один зі способів збільшити складність обчислення дискретного логарифму, включити його в базу криптосистеми у велику групу.

Алгоритм оснований на компромісі простору-часу. Це досить проста модифікація звичайного множення, легкий метод знаходження дискретних логарифмів. З урахуванням циклічної групи G порядку n, генератор б і в елементів групи, завдання полягає в знаходженні цілого х такого, що

Алгоритм Шенкса заснований на перезапису х як

x = im + j і та

Таким чином, ми маємо:

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

Кращий спосіб прискорити алгоритм є використання ефективної схеми таблиці. Кращі в цьому випадку хеш-таблиці. Хешування виконується на другий компонент, а також виконувати перевірку на першому кроці основного циклу, г хешується і адреса пам'яті перевіряється. Так як хеш-таблиці можна вилучати і додавати елементи в 0(1) часу (constant time), це не сповільнить сам алгоритм. Час роботи алгоритму і простір складності O(), набагато краще, ніж O (N), час роботи розрахунку грубої сили. Він працює для будь кінцевої циклічної групи. Не потрібно знати порядок групи G заздалегідь. Алгоритм буде працювати, якщо n є лише верхня межа групи порядку. Зазвичай алгоритм використовується для груп, порядки яких є простим. Якщо для цієї групи порядок є компонований, то алгоритм Pohlig-Hellman є більш ефективним. лгоритм вимагає O (м) пам'яті. Це можна використовувати менше пам'яті, вибираючи менше м на першому кроці алгоритму. Це збільшує час роботи, які потім O (п / м). Альтернативи можна використовувати ро алгоритм Полларда для логарифмів, яка приблизно в той же час роботи алгоритму, як дитина-гігант крок за кроком, але лише мала пам'ять. Алгоритм був розроблений компанією Daniel Шанкс.

1.3 Тип і об'єм вхідних даних

Відомо, що шифрування й дешифрування даних відбувається за допомогою симетричних і асиметричних криптосистем, причому до появи останніх єдиними існуючими були симетричні криптосистеми.

З метою визначення найдоцільнішого криптографічного алгоритму при проектуванні захищеної системи, зробимо порівняльний аналіз алгоритмів шифрування з огляду на наступні критерії: вхідні данні, вихідні данні

Першим блоковим шифром, що широко використовується на практиці, став DES (Data Encryption Standart). Згодом з'явилося достатня кількість блокових алгоритмів - IDEA, радянський ДЕРЖСТАНДАРТ 28147-89 та інші. При блоковому шифруванні інформація розбивається на блоки й шифрується по 64 або 128 біт, або блоками змінної довжини.

AES

Даний алгоритм Advanced Encryption Standard (AES), також відомий як Rijndael - симетричний алгоритм блочного шифрування. Автори хотіли розробити алгоритм таким, яким він є, зрозумілим при розгляді його ефективної низькорівневої реалізації. Він був створений таким чином, щоб всі операції в процесі шифрування й розшифрування одного блоку могли бути виконані паралельно в 32 потоку. Ніяких початкових і кінцевих перестановок не потрібно. Шифрування складається з 32 раундів. Відкритий текст є першими проміжними даними. Кожен раунд складається з:

· Змішування з ключем. Проводиться побітове виключне АБО проміжних даних, з ключем довжиною 128 біт;

· Застосування таблиць підстановок. Вхідні дані довжиною 128 біт поділяються на 4 слова по 32 біта. Таблиця підстановок реалізована послідовністю логічних операцій, застосовується до цих 4 слів. У результаті виходить 4 вихідних слова. Таким чином, центральний процесор виконує підстановку по 32 копій таблиці одночасно;

В останньому раунді це лінійне перетворення замінено додатковим змішуванням з ключем. Першою причиною вибору такого лінійного перетворення є максимізація лавинного ефекту. Такі таблиці підстановок мають властивість, що зміна кожного вхідного біта призведе до зміни 2 вихідних бітів. Таким чином, кожен вхідний біт відкритого тексту вже через 3 раунду впливає на всі вихідні біти. Аналогічно кожен біт ключа впливає на результат шифрування. Друга причина полягає в простоті перетворення. Воно може бути реалізовано на будь-якому сучасному процесорі з мінімальними витратами.

3DES

полягає в тому, що повідомлення поділяється на групи символів довжиною n і до кожної групи використовується одна і та сама перестановка (наприклад 2 - 3 - 1 - 5 - 4). Послідовне використання двох транспозицій є складеною транспозицією.

Початковий текст т а є м н е п о в і д о м л е н н я

Після перестановки а є т н м п о е і в о м д е л н я н

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

RC5

RC5 - це алгоритм симетричного шифрування, розроблений Роном Райвестом у середині 90-х років [9]. Тобто, RC5 шифрує блоки відкритого тексту довжиною 32, 64 чи 128 бітів в блоки шифрованого тексту тієї самої довжини. Довжина ключа може змінюватись від 0 до 2040 бітів. Райвест пропонує використовувати RC5-32/12/16 як "стандартну" версію RC5.

В алгоритмі RC5 виконуються три елементарні операції (а також обернені до них):

* Додавання. Додавання слів виконується за модулем 2^w. Оберненою операцією є віднімання за модулем 2^w.

* Побітове виключне АБО.

* Циклічний зсув ліворуч. В алгоритмі використовується циклічний зсув слова x ліворуч на y бітів, оберненою операцією є циклічний зсув слова x праворуч на y бітів.

Двома найважливішими особливостями RC5 є простота алгоритму та використання керованих даними циклічних зсувів. Циклічні зсуви - єдина нелінійна складова цього алгоритму. Райвест стверджує [9], що у зв'язку з тим, що величина зсуву визначається даними, що обробляються алгоритмом, лінійний та диференційний криптоаналіз алгоритму буде серйозно утруднений.

ГОСТ-89

Алгоритми за ГОСТ 28147-89 характеризуються вкладеною циклічністю, де зовнішній цикл забезпечує послідовну обробку 8-байтних блоків вхідних даних і містить один із трьох базових циклів. В тілі будь-якого із базових циклів багаторазово використовується основний крок криптографічного перетворення, який у свою чергу містить цикл підстановки. Таким чином пріоритет у досягненні швидкодії повинен бути в послідовності - цикл підстановки - основний крок криптографічного перетворення - базовий цикл. Стандарт ГОСТ 28147-89 приписує виконання восьми ітерацій циклу підстановок, в кожній з яких реалізується повна чотирибітна підстановка. Для задавання таблиць восьми чотирибітних підстановок достатньо 64 байтів, які є довгостроковим ключем. Очевидною є можливість суміщення ітерацій циклу підстановок за рахунок збільшення розміру таблиць підстановок. Так, у випадку чотирьох таблиць восьмибітних підстановок необхідно виділити 1 Кбайт, а у випадку двох таблиць шістнадцятибітних підстановок - 128 Кбайт пам'яті. Такі розширені таблиці легко формуються із довгострокового ключа, а їх розмір не є занадто великим для систем управління доступом. З точки зору оптимізації, розглянутий алгоритм шифрування, за швидкодією поступається багатьом іншим алгоритмам. Також, як показують результати тестування, зростання об'ємів програм та даних є значними в порівнянні із традиційними методами реалізації алгоритмів.[4]

RSA

Даний алгоритм -- криптографічна система з відкритим ключем. RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису. Алгоритм використовується у великій кількості криптографічних застосунків. Система RSA використовується для захисту програмного забезпечення й у схемах цифрового підпису. Також вона використовується у відкритій системі шифрування PGP.

Через низьку швидкість шифрування (близько 30 кбіт/сек при 512 бітному ключі на процесорі 2 ГГц), повідомлення звичайно шифрують за допомогою більш продуктивних симетричних алгоритмів з випадковим ключем (сеансовий ключ), а за допомогою RSA шифрують лише цей ключ.

RSA працює значно повільніше симетричних алгоритмів.

1.4 Стиснення інформації. Архіватори

Якщо методи стиснення інформації застосовують до готових документів, то нерідко термін стиснення даних підміняють терміном архівація даних, а програмні засоби, що виконують ці операції, називають архіватор.

В залежності від того, в якому об'єкті розміщені дані, що піддаються стисненню, розрізнюють:

· ущільнення (архівацію) файлів;

· ущільнення (архівацію) папок;

· ущільнення дисків.

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

Ущільнення папок використовують як засіб архівації даних перед тривалим зберіганням, зокрема, при резервному копіюванні.

Ущільнення дисків служить цілям підвищення ефективності використання їх робочого простору і, як правило, застосовується до дисків, що мають недостатню місткість. [4], [9]

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

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

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

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

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

Чим частіше зустрічається той або інший символ, тією меншою кількістю бітів він кодується (відповідно, чим рідше зустрічається символ, тим довше його кодова бітова послідовність).Ієрархічна структура, що утворюється внаслідок кодування, прикладається до стиснутого документа як таблиця відповідності.

При збереженні, резервному копіюванні інформації тощо, якої б місткості не були ваші диски, завжди бажано стиснути файли так, щоб вони займали якомога менше місця. Найпростіше це робиться за допомогою програм, які звуться архіваторами. Зауважимо, що ці програми не тільки стискають інформацію в окремому файлі, але й можуть поміщувати в один архів групу (звичайно, споріднених за якоюсь ознакою) файлів.

Існує багато архіваторів. Серед них найбільш відомі: ARJ, DIET, ICE, LHA, LHARC, LZH, LZEXE, NARC, PAK, PKARC, PKLITE, PKXARC, PKPAK, PKZIP, PKUNZIP, RAR, ZOO. Далі ми розглянемо лише ті з них, які зарекомендували себе з найкращого боку і, отже, найчастіше використовуються на практиці. Зауважимо, що сучасні програмні продукти відомих фірм розповсюджуються в архівованому вигляді (за допомогою власних засобів) і розархівовуються при встановленні відповідної системи на вінчестер (програмами Setup або Install).

Останнім часом з'явилися програми, які, знаходячись у пам'яті комп'ютера резидентно, архівують та розархівують «на льоті» всі файли, з якими ви працюєте, що дозволяє суттєвим чином заощаджувати простір на жорсткому диску. Такі можливості надають, наприклад, утиліта dblspace операційної системи MS-DOS та програма DIET (T.Matsumoto, Японія).

Існує декілька методів стиснення інформації, що міститься у файлах. Мабуть, найпростішим із них є метод Хаффмана, який полягає у заміні стандартних 8-бітових ASCII-кодів бітовими рядками змінної довжини в залежності від частоти зустрічаємості символу. До речі, легко зрозуміти, що у текстах найбільш часто зустрічається символ «пропуск», ASCII-код якого має номер 32. Можна поширити цю ідею на пари, трійки і т.д. символів. При цьому можна одержати суттєвий виграш. Дійсно, візьміть, наприклад, дві пари символів «по» та «хщ». Ви можете назвати безліч слів із першим сполученням. Спробуйте відшукати слово, яке містить ото «хщ»! А при стандартному ASCII-кодуванні на кожне зі сполучень витрачається порівну бітів SYMBOL 151 \f "Arial Cyr" по 16. Серед інших методів, які широко застосовуються в архіваторах для стиснення інформації у файлах, назвемо лише метод Лемпела-Зіва.

Зауважимо, що комп'ютер не «розуміє» ніяких інших кодувань символів крім ASCII-кодування (чи споріднених кодувань). Тому перед використанням архівований файл повинен бути розархівованим!

Характерною особливістю більшості типів даних є їх надлишковість. Ступінь надлишковості даних залежить від типу даних. Наприклад, для відеоданих ступінь надлишковості в декілька разів більша ніж для графічних даних, а ступінь надлишковості графічних даних, у свою чергу, більша за ступінь надлишковості текстових даних. Іншим фактором, що впливає на ступінь надлишковості є прийнята система кодування. Прикладом систем кодування можуть бути звичайні мови спілкування, які є ні чим іншим, як системами кодування понять та ідей для висловлення думок. Так, встановлено, що кодування текстових даних за допомогою засобів української мови дає в середньому надлишковість на 20-25% більшу ніж кодування аналогічних даних засобами англійської мови.

Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Коли методи стиснення даних застосовуються до готових файлів, то часто замість терміну "стиснення даних" вживають термін "архівування даних", стиснений варіант даних називають архівом, а програмні засоби, що реалізують методи стиснення називаються архіваторами.

В залежності від того, в якому об'єкті розміщені дані, що підлягають стисненню розрізняють:

1. Стиснення (архівування) файлів: використовується для зменшення розмірів файлів при підготовці їх до передавання каналами зв'язку або до транспортування на зовнішніх носіях малої ємності;

2. Стиснення (архівування) папок: використовується як засіб зменшення обсягу папок перед довготерміновим зберіганням, наприклад, при резервному копіюванні;

3. Стиснення (ущільнення) дисків: використовується для підвищення ефективності використання дискового простору шляхом стиснення даних при записі їх на носії інформації (як правило, засобами операційної системи).

Існує багато практичних алгоритмів стиснення даних, але всі вони базуються на трьох теоретичних способах зменшення надлишковості даних. Перший спосіб полягає в зміні вмісту даних, другий - у зміні структури даних, а третій - в одночасній зміні як структури, так і вмісту даних.

Якщо при стисненні даних відбувається зміна їх вмісту, то метод стиснення є незворотнім, тобто при відновленні (розархівуванні) даних з архіву не відбувається повне відновлення інформації. Такі методи часто називаються методами стиснення з регульованими втратами інформації. Зрозуміло, що ці методи можна застосовувати тільки для таких типів даних, для яких втрата частини вмісту не приводить до суттєвого спотворення інформації. До таких типів даних відносяться відео- та аудіодані, а також графічні дані. Методи стиснення з регульованими втратами інформації забезпечують значно більший ступінь стиснення, але їх не можна застосовувати до текстових даних. Прикладами форматів стиснення з втратами інформації можуть бути: JPEG (Joint Photographic Experts Group) для графічних даних; MPG - для для відеоданих; MP3 - для аудіоданих.

Якщо при стисненні даних відбувається тільки зміна структури даних, то метод стиснення є зворотнім. У цьому випадкові з архіву можна відновити інформацію повністю. Зворотні методи стиснення можна застосовувати до будь-яких типів даних, але вони дають менший ступінь стиснення у порівнянні з незворотними методами стиснення. Приклади форматів стиснення без втрати інформації: GIF (Graphics Interchange Format), TIFF (Tagged Image File Format) - для графічних даних; AVI - для відеоданих; ZIP, ARJ, RAR, CAB, LH - для довільних типів даних. Існує багато різних практичних методів стиснення без втрати інформації, які, як правило, мають різну ефективність для різних типів даних та різних обсягів. Однак, в основі цих методів лежать три теоретичних алгоритми:

· алгоритм RLE (Run Length Encoding);

· алгоритми групи KWE(KeyWord Encoding);

· алгоритм Хафмана.

Алгоритм RLE

В основі алгоритму RLE лежить ідея виявлення послідовностей даних, що повторюються, та заміни цих послідовностей більш простою структурою, в якій вказується код даних та коефіцієнт повторення. Наприклад, нехай задана така послідовність даних, що підлягає стисненню: 1 1 1 1 2 2 3 4 4 4

В алгоритмі RLE пропонується замінити її наступною структурою: 1 4 2 2 3 1 4 3, де перше число кожної пари чисел -це код даних, а друге - коефіцієнт повторення. Якщо для зберігання кожного елементу даних вхідної послідовності відводиться 1 байт, то вся послідовність займатиме 10 байт пам'яті, тоді як вихідна послідовність (стиснений варіант) займатиме 8 байт пам'яті.

Чим менше значення коефіцієнта стиснення, тим ефективніший метод стиснення. Зрозуміло, що алгоритм RLE буде давати кращий ефект стиснення при більшій довжині послідовності даних, що повторюється. У випадкові розглянутого вище прикладу, якщо вхідна послідовність матиме такий вигляд: 1 1 1 1 1 1 3 4 4 4, то коефіцієнт стиснення буде рівний 60%. У зв'язку з цим найбільша ефективність алгоритму RLE досягається при стисненні графічних даних (особливо для однотонових фонових зображень).

Алгоритми групи KWE

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

Існує досить багато реалізацій цього алгоритму, серед яких найбільш поширеними є алгоритм Лемпеля-Зіва (алгоритм LZ) та його модифікація алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словником в даному алгоритмі є потенційно нескінченний список фраз. Алгоритм починає роботу з майже пустого словника, що містить тільки один закодований рядок, так званий NULL-рядок. Коли зчитується черговий символ вхідної послідовності даних, він додається до поточного рядка. Процес продовжується доти, поки поточний рядок відповідає якій-небудь фразі з словника. Але рано або пізно поточний рядок перестає відповідати якій-небудь фразі словника. У цей момент, коли поточний рядок являє собою останній збіг зі словником плюс щойно прочитаний символ повідомлення, кодер видає код, що складається з індексу збігу і наступного за ним символа, що порушив збіг рядків. Крім того, нова фраза, що складається з індексу збігу і наступного за ним снмвола, додається в словник. У наступний раз, коли ця фраза з'явиться в повідомленні, вона може бути використана для побудови більш довгої фрази, що підвищує міру стиснення інформації.

Алгоритм LZW побудований навколо таблиці фраз (словника), яка відображає рядки символів стиснуваного повідомлення в коди фіксованої довжини. Таблиця володіє так званою властивістю передування, тобто для кожної фрази словника, що складається з деякої фрази w і символа К фраза w також міститься в словнику. Якщо всі частинки словника повністю заповнені кодування перестає бути адаптивним (кодування відбувається виходячи з вже існуючих в словнику фраз).

Алгоритми стиснення цієї групи найефективніші для текстових даних великих обсягів і малоефективні для файлів малих розмірів (за рахунок необхідності зберігання словника).

Крім того, сучасні архіватори надають користувачеві повний спектр послуг для роботи з архівами, основними з яких є:

1. створення нового архіву;

2. додавання файлів в існуючий архів;

3. розпакування файлів з архіву;

4. створення архівів, що саморозпаковуються (self-extractor archive);

5. створення розподілених архівів фіксованих розмірів для носіїв малої ємності;

6. захист архівів паролями від несанкціонованого доступу;

7. перегляд вмісту файлів різних форматів без попереднього розархівування;

8. пошук файлів і даних всередині архіву;

9. перевірка на віруси в архіві до розпакування;

вибір та налаштування коефіцієнта стиснення

І нарешті, наведемо спробу класифікації методів стискання інформації:



Размещено на http://www.allbest.ru/

1.5 Опис конкретного методу шифрування

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

Основна ідея полягає в наступному: чим частіше зустрічається символ, тим меншою кількістю біт він кодується. Результат кодування зводиться в словник, що необхідний для декодування.