Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз та реалізація алгоритму SHA-1
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Кафедра систем автоматизованого проектування
Інформація про роботу
Рік:
2008
Тип роботи:
Інші
Предмет:
Методи і засоби комп’ютерних інформаційних систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО НАУКИ І ОСВІТИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра систем автоматизованого проектування
ПОЯСНЮВАЛЬНА ЗАПИСКА
до курсової роботи
з дисципліни “ Методи і засоби комп’ютерних інформаційних систем”
на тему:
Аналіз та реалізація алгоритму SHA-1
Львів 2008
Анотація
Курсова робота з курсу “Методи і засоби комп’ютерних інформаційних систем”.
Розробка та реалiзацiя на мові програмування високого рівня Delphi програми реалізації алгоритму SHA-1/ Кобиринка О.Т., Львів: Національний університет “Львівська політехніка”, 2008.-32с.
Обсяг даної курсової роботи включно із кодом програм становить 32 сторінок. Курсова робота складається з 4-тьох розділів, у яких наведено основні необхідні теоретичні відомості про розробку і створення програми реалізації поставленого алгоритму.
Курсова робота ставить ціль – розробити програму реалізації алгоритму SHA-1.
Зміст.
1. Вступ…...................……………………………………………………......4
2. Аналіз предметної області………………………………………………..9
2.1. Завадостійке кодування……………..…………………………...9
2.2. Основні принципи завадостійкого кодування…………………11
2.3. Зв’язок коректуючої здатності коду і кодової віддалі……...…13
2.4. Код Хемігна….…………………………………………………..14
2.5. Криптографічні хеш-функції…………………………………...16
3. Опис алгоритму ………………………….………………………………23
3.1. Призначення алгоритму SHA-1………………………………...23
3.2. Логіка виконання алгоритму……………………………………25
3.3. Опис програмної реалізації….………………………………….28
3.4. Аналіз результатів роботи програми….………………………..30
4. Висновок…………………………………………………………………..31
Список використаної літератури……………………….………………….33
Додатки ...................................................................................................
Вступ
По формі представлення в каналі передачі розрізняють послідовні і паралельні коди. При послідовних кодах елементарні сигнали, що передають кодову комбінацію посилаються в канал передачі послідовно в часі. Вони можуть бути розділені часовим інтервалом або опитуватися в певні моменти часу (наприклад, як у послідовному інтерфейсі RS - 232 C).
Для паралельних кодів потрібні багатопровідні канали, тому при передачі інформації на значну відстань вони використовуються рідко через великі затрати (наприклад, паралельний інтерфейс Centronics). Паралельне представлення найчастіше використовується коли потрібна висока швидкість передачі даних (Centronics – 80 – 120 Кбайт/сек, сучасні двонаправлені системи – до 250 Кбайт/сек).
По можливості виявлення та виправлення помилок розрізняють прості (примітивні) і коректуючі коди.
В простих кодах помилка у будь-якому елементі кодової комбінації приводить до неправильного прийому декодованого повідомлення.
Коректуючі коди дозволяють виявляти і усувати помилки у кодових комбінаціях.
По основних законах кодоутворення коди поділяються на комбінаторні (нечислові) і арифметичні (числові).
Криптографічні хеш-функції використовуються зазвичай для генерації дайджест повідомлення при створенні цифрового підпису. Хеш-функції відображують повідомлення в те, що має фіксований розмір хеш-значення (hash value) таким чином, що вся безліч можливих повідомлень розподіляється рівномірно на безліч хеш-значень. При цьому криптографічна хеш-функція робить це таким чином, що практично неможливо підігнати документ до заданого хеш-значення.
Криптографічні хеш-функції зазвичай виробляють значення довжиною в 128 і більш біт. Це число значно більше, чим кількість повідомлень, які будь-коли існуватимуть в світі.
Багато криптографічних хеш-функцій доступно безкоштовно. Широко відомими є MD5 і SHA.
У даній роботі використовується алгоритм SHA-1.
Розглянемо основні поняття, що пов’язані з кодуванням та передаванням інформації. Подією називатимемо кожну кількісну чи якісну визначеність станів динамічної системи, яка фіксується спостереженнями .
Можна кожному стану системи поставити у відповідність певне значення чи послідовність значень деякої величини. За допомогою цієї величини можна здійснити передавання повідомлення (відомостей про подію, інформації про подію) від одного об’єкта до іншого.
Фізичний процес, що являє собою матеріальне втілення повідомлення, називається сигналом.
Система або середовище, де здійснюється передавання сигналу, називається каналом зв’язку.
Будь-які повідомлення, що підлягають передаванню по каналах зв’язку, переробці в кібернетичній системі, мають бути попередньо закодовані, тобто «перекладені» мовою сигналів.
Кодування можна визначити як процес подання інформації у вигляді деякої послідовності символів (кодових комбінацій). При цьому таку послідовність, у свою чергу, можна подати (перекодувати) у вигляді сукупностей фізичних сигналів тієї чи іншої природи — акустичних, оптичних, електричних тощо.
Наведемо приклад природного кодування. Нехай ви спостерігаєте деякий пейзаж. До вашого ока надходить інформація про це у вигляді світлових сигналів (фотонів). Ці сигнали сітківкою ока перекодуються в інші сигнали, що по нейронних ланцюгах надходять до головного мозку. Там ці сигнали перекодовуються в образи, які далі перекодовуються в певні відчуття.
Проте якщо потрібно цю інформацію зафіксувати на папері, її доводиться перекодовувати у вигляді букв та їх поєднань. А щоб цю інформацію повідомити комусь по телефону, її необхідно ще перекодувати у звукові коливання. Потім телефон ще раз закодує звукові коливання в електричні імпульси, які по телефонних лініях (каналах зв’язку) надійдуть на приймальний пристрій адресата, де відбудеться декодування електричних імпульсів у звукові коливання. Нарешті, ці коливання надійдуть адресатові (до його вуха), де він їх декодує в образи, або в текст.
Наведемо більш строге визначення кодування. Нехай дано довільну множину А, яку потрібно відобразити в іншу множину В. У цій множині В є скінченна кількість символів (знаків), що називається алфавітом. Наприклад, в абетці Морзе три символи (крапка, тире і прогалина), в англійській мові — 26 букв плюс прогалина і т. ін.
Кількість різних символів (букв), що входять до алфавіту, називається обсягом алфавіту. У цій множині В за певними правилами можна будувати послідовності символів, що називаються словами.
Кодуванням називається відображення довільної множини А у множину скінчених послідовностей (слів), утворених за допомогою деякого алфавіту множини В, а декодуванням — обернене відображення.
Кодом називається сукупність знаків (символів) алфавіту В і слів, складених із них за певними правилами і призначених для однозначного відображення множини А у множину В.
До будь-якої системи кодування висуваються такі основні вимоги:
1) взаємна однозначність перетворень відображуваної множини А у множину В, що її відображує в результаті кодування та оберненого перетворення (декодування) — необхідна умова відсутності помилок в інтерпретації вихідної інформації;
2) економічність кодування, забезпечується, насамперед, мінімізацією середньої довжини комбінацій, а отже, і довжини інформаційних текстів, завдяки чому заощаджується не лише час передавання тексту, а й носії інформації;
3) завадостійкість, тобто можливість виявлення та виправлення помилок у кодових комбінаціях під впливом тих чи інших перешкод та збоїв.
Зауважимо, що друга і третя вимоги взаємно суперечливі, оскільки підвищення завадостійкість досягається збільшенням довжини слів, через що знижується економічність систем кодування.
У техніці зв’язку й обробки інформації розроблено багато різних способів кодування, що забезпечують більш-менш вдалий компроміс у виконанні цих вимог у різних кібернетичних системах.
Схематичне зображення системи зв’язку наведено на 1. Ця схема відбиває найбільш істотні елементи будь-якої системи зв’язку: комп’ютерної мережі, системи супутникового чи мобільного зв’язку, розмовного каналу між двома співрозмовниками тощо.
Рис 1. Принципова схема системи зв’язку
Людське мислення у процесі переробки інформації являє собою своєрідний канал зв’язку із шумами, від пропускної здатності якого багато в чому залежить дієвість та ефективність управлінських рішень.
Тоді, коли людина встигає вчасно переробити необхідну для ухвалення рішення інформацію, тобто її канал зв’язку має достатню пропускну здатність і стійкість до шумів, можна очікувати прийняття найбільш ефективних рішень. Якщо терміни переробки та проходження інформації через канал зв’язку (свідомість людини) та час, необхідний для прийняття рішення, не збігаються, то рішення приймається або із запізненням, або в умовах неповної переробки інформації. І перше і друге негативно позначається на функціонуванні соціально-економічних систем.
2. Аналіз предметної області
2.1 Завадостійке кодування.
Завадостійкі коди – це один із найефективніших засобів забезпечення високої достовірності передачі інформації. Розвиток цього напрямку зумовлений використанням мікропроцесорної техніки у системах зв’язку.
Завадостійке кодування базується на теоремі Шеннона для передачі дискретної інформації по каналу із завадами: “Імовірністть помилкового декодування може бути як завгодно малою при виборі відповідного способу кодування”. Теорема вказує на принципову можливість, але не визначає спосіб кодування. Це обумовило інтерес до розробки завадостійких кодів.
Під завадостійкими розуміють коди, які дозволяють виявляти чи виявляти і виправляти помилки, які виникли через вплив завад.
Завадостійкість кодування забезпечується за рахунок внесення надлишковості в кодові комбінації, тобто крім інформаційних є і надлишкові (додаткові) розряди.
Всі завадостійкі коди поділяються на два класи:блочні та неперервні.
В блочних кодах кожному повідомленню (або елементу повідомлення) відповідає кодова комбінація (блок) із певної кількості сигналів. Блоки кодуються і декодуються окремо один від одного. Блочні коди можуть бути рівномірними (довжина кодових комбінацій n – постійна), або нерівномірними (n – міняється). Нерівномірні практично не використовуються через складність їх технічної реалізації.
В неперервних кодах внесення надлишковості в послідовність вхідних символів здійснюється без розбивки на окремі блоки. Для неперервних кодів процеси кодування та декодування мають теж неперервний характер. Цей напрям тільки розвивається.
Блочні і неперервні коди в залежності від методів внесення надлишковості поділяють на роздільні та нероздільні.
Рис 2.1.1 Види коректуючих кодів
В роздільних чітко визначена роль окремих символів. Одні символи є інформаційні, інші є перевірочними і забезпечують виявлення і виправлення помилок.
Роздільні блочні коди називають ще n, k – кодами, де n – довжина кодових комбінацій, k – кількість інформаційних символів в комбінаціях.
У нероздільних кодах немає чіткого поділу символів кодової комбінації на інформаційні та перевірочні. Таких кодів мало.
Роздільні блочні коди поділяються на систематичні і несистематичні. Несистематичні будуються таким чином, що перевірочні символи визначаються як сума підблоків, на які поділяється блок інформаційних символів.
Більшість відомих роздільних кодів є систематичними кодами. Для цих кодів перевірочні символи визначаються в результаті проведення лінійних операцій над певними інформаційними символами.
Декодування зводиться до перевірки на парність певних груп символів. В результаті цих перевірок отримується інформація про наявність помилок, а при потребі і про позицію помилкових символів.
2.2 Основні принципи завадостійкого кодування.
Будемо розглядати блочні рівномірні двійкові завадостійкі коди. Кількість розрядів n в кодовій комбінації називається довжиною коду. Символи коду – 0,1. Кількість одиниць в кодовій комбінації називається її вагою w.
Наприклад: 100101100 – n=9, w=4.
Кодова віддаль d визначається кількістю позицій чи символів, в яких кодові комбінації відрізняються одна від одної і рівна вазі суми (по модулю 2) цих кодових комбінацій
100101100
+ 110110101
_________
010011001 w=4, d=4.
За рахунок впливу завад в одному чи кількох рядках кодової комбінації можуть з’являтися помилки (0 ( 1, 1(0).
По кількості помилкових розрядів помилки бувають одно, двох і більше кратними.
Експериментальні дослідження показали, що помилки символів при передачі по каналу зв’язку групуються у пачки різної тривалості. Пачка – це участок послідовності символів, які починаються і закінчується помилковими символами. В середині пачки можуть бути і окремі правильні символи.
Для визначення місця помилкових символів у кодовій комбінації використовується вектор помилки е (n – розрядна комбінація, одиниці якої вказують місце помилкових символів). Наприклад, е = 01100 – третій і четвертий символи справа – помилкові.
Сума по модулю 2 спотвореної кодової комбінації і вектора помилки дає правильну комбінацію.
Звадостійкість кодування забезпечується надлишковістю (k<n). Тобто із загальної кількості No = 2n можливих кодових комбінацій для передачі інформації використовується тільки N = 2k комбінацій, тобто множина No ділиться на дві групи N=2k – множина дозволених і (No-N)=2n-2k множина заборонених комбінацій. Якщо прийнята комбінація заборонена, то це означає, що сигнал створений в каналі. Якщо дозволена – то або комбінація без спотворень, або був перехід з однієї дозволеної в іншу.
У загальному випадку кожна із N дозволених комбінацій може перетворитись у будь-яку із No можливих, тобто можливі N* No варіантів передачі, з них N варіантів безпомилкові, N*(N-1) - перехід із одних дозволених у інші дозволені, N*(No-N) – перехіід із дозволених у заборонені.
Таким чином не всі спотворення можуть бути виявлені. Частка помилкових комбінацій, що можуть бути виявлені визначається як
;
Для використання коду як коректуючого, множина заборонених кодових комбінацій розбивається на N підмножин Mі , що не перетинаються. Кожна їз цих підмножин відповідає одній із дозволених комбінацій Аі . Якщо прийнята заборонена комбінація належить підмножині Mі , то вважається, що передана комбінація Аі. Помилка буде виправлена лише тоді, коли заборонена комбінація утворилася із Аі . Таким чином, помилка виправляється в (N0-N) випадках (тільки для заборонених комбінацій). Частка виправлених помилкових комбінацій із загальної кількості виявлених помилкових рівна
;
Спосіб розбиття на підмножини залежить від того які помилки повинні виправлятися даним кодом.
2.3 Зв’язок коректуючої здатності коду і кодової віддалі.
Кодова віддаль характеризує ступінь відмінності між двома довільними кодовими комбінаціями. Найменша віддаль між дозволеними кодовими комбінаціями dmin - важлива характеристика коду, яка визначає його виявляючу і коректуючу здатність. Якщо необхідно побудувати код, який виявляє всі помилки кратністю t і нижче – це значить із множини N0 можливих вибрати N дозволених комбінацій так, щоб будь-яка з них в сумі по модулю 2 із будь-яким вектором помилок з вагою Wі не більшою t, не дала б в результаті іншої дозволеної комбінації. Для цього необхідно, щоб кодова віддаль dmin була не меншою t+1. Для виправлення виявленої помилки необхідно щоб кодова віддаль між двома дозволеними комбінаціями була не меншою ніж t+2. Це забезпечує утворення для кожної із дозволениих комбінацій множини заборонених, яка, при заданій кратності помилки, не перетинається із множинами заборонених для інших дозволених, що дає можливість однозначно виправити помилку. Очевидно, що виправлення помилок зведенням до дозволеної будь-якої комбінації із її множини заборонених базується на гіпотезі, що мала місце помилка з кратністю не більше t. Однак на практиці не виключена можливіть виникнення помилки з більшою кратністю і тоді помилкова кодова комбінація буде неправильно виправлена до найближчої дозволеної. Таким чином методи виправлення помилок мають імовірнісний характер.
2.4 Код Хемінга.
Код Хемiнга належить до найважливiших лiнiйних кодiв, якi широко використовуються на практицi i мають зручний для технiчноi реалiзацii алгоритм виявлення та виправлення однiєї помилки.
Код складаеться з k iнформацiйних двійкових розрядів та n-k контрольних. Загальна кількість розрядів у кодi n. Нумерація розрядів здійснюється справа наліво від 1 до n.
Число n повинно задoвiльняти нерiвнiсть 2n-k не менше n+1. Для визначення основних параметрiв коду Хемiнга задається кiлькiсть iнформацiйних розрядів k, по яких обчислюється n та n-k. Кiлькiсть iнформацiйних k та контрольних n-k розрядів коду, який виявляє та коректує одну помилку приведена в таблиці:
K
1…4
5…11
12…26
27…57
58…120
121…247
n-k
3
4
5
6
7
8
N
7
15
31
63
127
255
На основi основних параметрiв коректуючого коду визначають позицii інформаційних та контрольних розрядів. Позиції контрольних розрядів вибираються по значенню степенi 2і, де i=0,1,2,3... Тобто номери контрольних розрядів будуть рiвнi 1,2,4,16... Між контрольними розрядами справа наліво вписуються інформаційні. Потiм визначають значення контрольних розрядів по такому правилу: сума одиниць на перевiрочних позицiях для даного контрольного розряду повинна бути непарною. Якщо ця сума непарна, то контрольний розряд встановлюється рiвним нулю, якщо парна – одиницi (доповнення до непарності).
Перевiрочнi позицii вибирають таким чином. Cкладають таблицю для ряду натуральних чисел у двiйковому кодi. Кiлькiсть чисел - n. Потiм визначають перевiрочнi позицii по такому правилу: в першу перевiрку входять розряди, якi мiстять одиницю в першому розрядi справа (1,3,5,7 і т.д.), в другу - в другому (2,3,6,7…) і т.д.
8 7 6 5 4 3 2 1
1
0
0
1
1
0
1
0
12 11 10 9 8 7 6 5 4 3 2 1
1
0
0
1
0
1
0
1
0
0
0
0
1
0
0
0
1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
Рис. 2.4.1. Формування коду Хемінга.
Для виявлення і виправлення одиночної помилки в прийнятій кодовій комбінації проводять перевiрку на непарнiсть. Для першоi перевiрки сумують розряди для позицiй, що мiстять одиницю в молодшому розрядi (1,3,5,7...). Якщо кількість одиниць парна, то перший розряд справа для двійкового значення номера помилкової позиції (синдрома) встановлюється рівним одиниці. Потім сумуючи розряди для позицій, що містять одиницю у другому двійковому розряді, і перевіряючи суму на непарність визначають значення другого розряду синдрома. Процес повторюється для позицiй, що містять одиниці у розрядах 3,4,5 i т.д. В результатi формується номер помилкової позицiї коду. Для виправлення помилки символ у цiй позицiї необхiдно замiнити на протилежний. Якщо синдром рівний нулю, то прийнята комбінація не містить одиночних помилок. Наприклад, при помилці в шостому розряді визначене значення синдрому буде рівне 0110.
Криптостійка хеш-кодування функція перш за все повинна володіти стійкістю до колізій двох типів:
- стійкість до колізії першого роду: для заданого повідомлення повинно бути практично неможливо підібрати інше повідомлення, що має таке ж хеш-кодування. Ця властивість також називається безповоротністю хеш-функції.
- стійкість до колізії другого роду: повинно бути практично неможливо підібрати пару повідомлень, що мають однакове хеш-кодування.
Наприклад, при записі текстових полів в базі даних може розраховуватися їх хеш-кодування код і дані можуть поміщатися в розділ, відповідний цьому хеш-коду. Тоді при пошуку даних треба буде спочатку обчислити хеш-кодування-код тексту і відразу стане відомо, в якому розділі їх треба шукати, тобто, шукати треба буде не по всій базі, а тільки поодинці її розділу (це сильно прискорює пошук).
2.5 Криптографічні хеш-функції
Криптографічні хеш-функції використовуються зазвичай для генерації дайджест повідомлення при створенні цифрового підпису. Хеш-функції відображають повідомлення що має фіксований розмір хеш-значення (hash value) таким чином, що вся безліч можливих повідомлень розподіляються рівномірно по множині хеш-значення. При цьому криптографічна хеш-функція робить це таким чином, що практично неможливо підігнати документ по заданому хеш-значенню.
Криптографічні хеш-функції зазвичай проводять значення довжиною в 128 і більше. Це число значно більше, чим кількість повідомлень, які коли небудь існуватимуть в світі.
Широко відомі криптографічні функції MD5 і SHA.
Криптографічні генератори випадкових чисел проводять випадкові числа, які використовуються в криптографічних застосуваннях, наприклад - для генерації ключів.
Звичайні генератори випадкових чисел, наявні в багатьох мовах програмування і програмних середовищах, не підходять для потреб криптографії (вони створювалися з метою отримати статистично випадковий розподіл, криптоаналітики можуть передбачити поведінку таких випадкових генераторів).
У ідеалі випадкові числа повинні грунтуватися на справжньому фізичному джерелі випадкової інформації, яку неможливо передбачити. Приклади таких джерел включають шумлячі напівпровідникові прилади, молодші біти оцифрованого звуку інтервали між перериваннями пристроїв або натиснення клавіш. Отриманий від фізичного джерела шум потім "дистилюється" криптографічною хэш-функцией так, щоб кожен бит залежав від кожного біта. Достатньо часто для зберігання випадковій інформації використовується досить великий пул (декілька тисяч біт) і кожен біт залежить від кожного біта шумової информації і кожного іншого біта пулу криптографічний надійним (strong) способом.
Коли немає справжнього фізичного джерела шуму, доводиться користуватися псевдовипадковими числами. Така ситуація небажана, але часто виникає на комп’ютерах загального призначення. Завжди бажано отримати якийсь шум оточення - скажемо від величини затримок в пристроях, цифри статистики использованияресурсов, мережевої статистики, переривань від клавіатури або чогось іншого. Завданням є отримати дані, непередбачувані для зовнішнього спостерігача. Для дослідження цього випадковий пул повинен містити як мінімум 128 біт справжньої ентропії.
Криптографічні генератори псевдовипадкових чисел зазвичай використовують великий пул (seed-значение), що містить випадкову інформацію. Біти генерується шляхом вибірки з пулу з можливим прогоном через криптографічну хеш-функцію, щоб заховати вміст пулу від зовнішнього спостерігача. Коли потрібна нова порція біт, пул перемішується шляхом шифровки з випадковим ключем (його можна узяти з невикористаної поки частини пулу) так, щоб кожен біт пулу залежав від каждого наступного біта. Новий шум оточення повинен додаватися до пулу перед перемішуванням, щоб зробити прогноз нових значень пулу ще складніший.
Не дивлячись на те, що при акуратному проектуванні криптографічний надійний генератор випадкових чисел реалізувати не так вже і важко, це питання часто опускають з вигляду. Таким чином, слід підкреслити важливість криптографічного генератора випадкових чисел -якщо він зроблений погано, він може легко стати самим уразливим елементом системи.
Доступні декілька прикладів криптографічних генераторів випадкових чисел.
Хороші криптографічні системи створюються так, щоб зробити їх розшифрування як можна більш складною справою. Можна побудувати системи, які на практиці неможливо розкрити (хоча довести цей факт зазвичай не можна). При цьому не потрібно дуже великих зусиль для реалізації. Єдине, що потрібно - це акуратність і базові знання. Всі механізми, які можуть використовуватися для злому системи треба задокументувати і довести до кінцевих користувачів.
Теоретично, будь-який шифрувальний алгоритм з використанням ключа може бути розкритий методом перебору всіх значень ключа. Якщо ключ підбирається методом підбору, необхідна потужність комп'ютера росте експоненціально з збільшенням довжини ключа. Ключ завдовжки в 32 біта вимагає 2^32 (близько 10^9) кроки.
Таке завдання під силу будь-якому дилетантові і вирішується на домашньому комп'ютері.
Системи з 40-бітовим ключем (наприклад, експортний американскийвариант алгоритму RC4) вимагають 2^40 кроків - такі комп'ютерні потужності є в більшості університетів і навіть в невеликих компаніях. Системи з 56-бітними ключами (DES) вимагають для розшифрування помітних зусиль, проте можуть бути легко розкриті з допомогою спеціальної апаратури. Вартість такої аппарату різна, але доступна для зловмисників, великих компаній і урядів. Ключі завдовжки 64 біта зараз можливо, можуть бути розкриті велики фірмами і вже в найближчих декілька років будуть доступні для розшифрування злочинним організаціям, великим компаніями і невеликим державам. Ключ довжиною 80 біт може в майбутньому стати вразливими.
Ключі завдовжки 128 біт ймовірно залишаться недоступними для розшифрування методом підбору в майбутньому. Можна використовувати і довші ключі. У межі неважко добитися того, щоб енергія, потрібна для розшифрування перевершить масу сонця або всесвіту.
Проте, довжина ключа це ще не все. Багато шифрів можна розкрити і не перебираючи всіх можливих комбінацій. Взагалі кажучи, дуже важко придумати шифр, який не можна було б розкрити іншим ефективнішим способом. Розробка власних шифрів може стати приємним заняттям, але для реальних моментів використовувати саморобні шифри не рекомендується якщо ви не є експертом і не упевнені на 100 відсотків в тому, що робите.
Взагалі кажучи, слід триматися в стороні від неопублікованих або секретних алгоритмів. Часто розробник такого алгоритму не упевнений в його надійності, илиже надійність залежить від секретності самого алгоритму. Взагалі кажучи, жоден алгоритм, секретність якого залежить від секретності самого алгоритму не є надійним. Зокрема, маючи шифруючу програму, можна найняти программіста який дешифрує її і відновить алгоритм методом зворотної інженерії. Досвід показує, що більшість секретних алгоритмів, що стали згодом надбанням громадкості, стали не надійними.
Довжини ключів, використовуваних в криптографії з відкритим ключем зазвичай значно більше, ніж в симетричних алгоритмах. Тут проблема заключається в підборі ключа, а у відтворенні секретного ключа по відкритому. У разі RSA проблема еквівалентна розкладанню на множники великого цілого числа, яке являєтся твором пари невідомих простих чисел. У разі деяких інших криптосистем, проблема еквівалентна обчисленню дискретного логарифма по модулю великого цілого числа (таке завдання вважається приблизно аналогічним по трудності завданню розкладання на множники). Є криптосистеми, які використовують інші способи. Щоб дати уявлення про ступінь складності розшифрування RSA, скажімо, що модулі завдовжки 256 біт легко факторизуются звичайними програмістами. Ключі в 384 бита можуть бути розкриті дослідницькою групою університету або компанії. 512-бітові ключі знаходяться в межах досяжності великих держав. Ключ довжиною 768 біт ймовірно не будуть надійні тривалий час. Ключі завдовжки в 1024 біт можуть вважатися безпечними до тих пір, поки не буде прогресу в алгоритмі факторизації; ключі завдовжки в 2048 більшість вважає надійними на десятиліття.
Важливо підкреслити, що ступінь надійності криптографічної системи визначається її слабкою ланкою. Не можна упускати з вигляду жодного аспекта розробки системи - від вибору алгоритму до політики використання і розповсюдження ключів.
Криптоаналіз - це наука про дешифровку закодованих повідомлень не знаючи ключів. Є багатокриптоаналітичних підходів. Деякі з найбільш важливих для розробників приведені нижче.
Атака із знанням лише шифрованого тексту (ciphertext-only attack): Це
ситуація, коли той, що атакує не знає нічого про зміст повідомлення, і йому приходиться працювати лише з самим шифрованим текстом. На практиці, часто можна зробити правдоподібні припущення про структуру тексту, оскільки багато повідомлення мають стандартні заголовки. Навіть звичайні листи і документи починаються з легко передбачливої інформації. Також часто можна припустити що деякий блок інформації містить задане слово.
Атака із знанням вмісту шифровки (known-plaintext attack): Що атакує
знає або може вгадати вміст всього або частини зашифрованого тексту.
Завдання полягає в розшифровці решти повідомлення. Це можна зробити або шляхом обчислення ключа шифровки, або минувши це.
Атака із заданим текстом (chosen-plaintext attack): Той, що атакує має возможнот отримати шифрований документ для будь-якого потрібного йому тексту, але не знає ключа. Завданням є знаходження ключа. Деякі методи шифрування і, в частковості, RSA, вельми уразливі для атак цього типу. При використанні таких алгоритмів треба ретельно стежити, щоб той, що атакує не міг зашифрувати заданий ним текст. Атака з підставкою (Man-in-the-middle attack): Атака направлена на обмін шифрованими повідомленнями і, особливо, на протокол обміну ключами. Ідея полягає в тому, що коли дві сторони обмінюються ключами для секретної комунікації (наприклад, використовуючи шифр Діффі-хелмана, Diffie-Hellman) супротивник упроваджується між ними на лінії обміну повідомленнями. Далі супротивник видає кожній стороні свої ключі. В результаті, кожна із сторін матиме різні ключі, кожен з яких відомий супротивникові. Тепер супротивник буде розшифровувати кожне повідомлення своїм ключем і потім зашифровувати його допомогою іншого ключа перед відправкою адресатові. Сторони матимуть ілюзію секретного листування, тоді як насправді супротивник читає все повідомлення.
Одним із способів запобігти такому типу атак полягає в тому, що сторони при обміні ключами обчислюють криптографичну хеш-функцию значення протоколу обміну (або щонайменше значення ключів), підписують її алгоритмом цифрового підпису і посилають підпис іншій стороні. Одержувач перевірить підпис і те, що значення хеш-функціи спіпадає з обчисленим значенням. Такий метод використовується, зокрема, в системі Фотуріс(Photuris).
Атака за допомогою таймера (timing attack): Цей новий тип атак заснований на послідовному вимірюванні часів, що витрачаються на виконання операції зведення в стенень по модулю цілого числа. До неї схильні принаймні наступні шифри: RSA, Діффі-хеллман і метод еліптичних кривих. Є безліч інших криптографічних атак і криптоаналітичних підходів.
Проте приведені вище виявляються, мабуть, найбільш важливими для практичної розробки систем.
3. Опис алгоритму
3.1. Призначення алгоритму SHA-1.
Алгоритм SHA-1 (Secure Hash Algorithm) використовується в алгоритмах електронно-цифрових підписів (DSA - Digital Signature Algorithm). Для повідомлення (потоку даних) довжиною менше 2^64 біта, даний алгоритм обчислює 160-бітний хеш. Отриманий хеш використовується для генерації "підпису" до повідомлення, а також для її перевірки. Будь-які зміни у вихідному повідомленні приведуть до зміну хеша з дуже великою вірогідністю.
SHA-1 розроблявся з метою досягнути наступні властивості: не представляється можливим з використанням комп’ютера знайти вихідне повідомлення, знаючи хеш, або знайти два різні повідомлення що дає однаковий хеш.
У даному алгоритмі під "словом" розуміється кількість інформації в 32 біта "байт" - 8 біт. Ціле число в проміжку від 0 до 2^32 - 1 включно може бути представлено як слово, в якому старший байт записаний першим, молодший - останнім. Ціле z (0 <= z < 2^64) представляється у вигляді z = (2^32)x + y, де x і y - цілі в проміжку від 0 до 2^32 - 1. Таким чином z можна представити парою слів x і y. Блок з 512 біт може бути представлений послідовністю з 16 слів.
В алгоритмі використовуються наступні логічні операції:
x & y - побітове "І"
x | y - побітове "АБО"
x ^ y - побітове "виключне АБО"
~x - побітове заперечення
x <<< y - циклічний зсув x вліво на y біт
Вирівнювання повідомлення.
Довжина повідомлення приймається як кількість біт у вхідному потоці (можливе порожнє повідомлення довжиною 0 біт). Мета вирівнювання: зробити довжину повідомлення кратною 512, оскільки алгоритм SHA-1 обробляє вхідний потік блоками по 512 біт. Вирівнювання проходить таким чином: додається один біт '1' (a), потім слідують біти '0' (b), після чого записується довжина повідомлення до вирівнювання (c). В результаті отримуємо довжину потоку рівну n*512.
Приклад: допустимий вхідний потік біт має наступний вигляд:
01100001 01100010 01100011 01100100 01100101 (40 біт)
після кроку (a) повідомлення набирає вигляду:
01100001 01100010 01100011 01100100 01100101 1 (41 біт)
на кроці (b) додаються 407 '0', що в шістнадцятковому вигляді виглядає так:
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
на кроці (c) додаємо довжину до вирівнювання: 40 - 00000000 00000028 (hex); і отримуємо повідомлення, що вирівнюється:
61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000028
3.2. Логіка виконання алгоритму
Алгоритм складається з наступних кроків:
Крок 1: додавання бітів
Повідомлення додається так, щоб його довжина була кратна 448 по модулю 512 (довжина 448 mod 512). Додавання здійснюється завжди, навіть якщо повідомлення вже має потрібну довжину. Таким чином, число бітів, що додаються, знаходиться в діапазоні від 1 до 512. Додавання складається з одиниці, за якою слідує необхідна кількість нулів.
Крок 2: додавання довжини
До повідомлення додається блок з 64 бітів. Цей блок трактується як без знакове 64-бітне ціле і містить довжину вихідного повідомлення до додавання. Результатом перших двох кроків є повідомлення, довжина якого кратна 512 бітам. Розширене повідомлення може бути представлене як послідовність 512-бітних блоків Y0, Y1, . . ., YL-1, отже загальна довжина розширеного повідомлення є L * 512 біт. Таким чином, результат кратний шістнадцяти 32-бітним словам.
Крок 3: ініціалізація SHA-1 буфера
Використовується 160-бітний буфер для зберігання проміжних і остаточних результатів хеш-функції. Буфер може бути представлений як п'ять 32-бітних регістрів A, B, C, D і E. Ці регістри ініціалізувалися наступними числами:
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
E = C3D2E1F0
Крок 4: обробка повідомлення в 512-бітних (16-словних) блоках
Основою алгоритму є модуль, що складається з 80 циклічних обробок, позначений як HSHA. Все 80 циклічних обробок мають однакову структуру.
Рис. 3.2.1 Обробка 512-ти бітного блоку
Кожен цикл отримує на вході поточний 512-бітний оброблюваний блок Yq і 160-бітноє значення буфера ABCDE, і змінює вміст цього буфера.
У кожному циклі використовується додаткова константа Кt, яка набуває лише чотири різні значення:
0 t 19 Kt = 5A827999
(ціла частина числа [230 × 21/2])
20 t 39 Kt = 6ED9EBA1
(ціла частина числа [230 × 31/2])
40 t 59 Kt = 8F1BBCDC
(ціла частина числа [230 × 51/2])
60 t 79 Kt = CA62C1D6
(ціла частина числа [230 × 101/2])
Складання по модулю 232 виконується незалежно для кожного з п'яти слів в буфері з кожним з відповідних слів.
Крок 5: вихід
Після обробки всіх 512-бітних блоків виходом n-ої стадії є 160-бітне повідомлення.
3.3. Опис програмної реалізації
Основні етапи програмування алгоритму SHA-1:
Оголошуємо список основних змінних, які потрібні для реалізації алгоритму:
сonst – список констант
HC0=$67452301;
HC1=$EFCDAB89;
HC2=$98BADCFE;
HC3=$10325476;
HC4=$C3D2E1F0;
K1=$5A827999;
K2=$6ED9EBA1;
K3=$8F1BBCDC;
K4=$CA62C1D6;
Hout:string – результат кодування
size:integer;
size – вхідний розмір у бітах
Опис основних процедур:
procedure INIT; // ініціалізація - присвоєння змінним значення констант
begin
H0:=HC0;//$67452301;
H1:=HC1;//$EFCDAB89;
H2:=HC2;//$98BADCFE;
H3:=HC3;//$10325476;
H4:=HC4;//$C3D2E1F0;
Hout:='';
end;
function PADDING(s:string;FS:integer):string; // додавання одного біта (1000000=128) і додавання нулів до кратності 64 байтам
var size,i:integer;
procedure TForm1.FormCreate(Sender: TObject); // процедура створення форми
begin
WindowState:=wsMaximized;
Form1.Memo1.Clear;
Form1.SaveDialog1.Filter := 'Text Files (*.txt)|*.TXT|All Files (*.*)|*.*';
CheckBox1.Checked:=true;
CheckBox2.Checked:=true;
Application.Title:='SHA-1';
Caption:='SHA-1';
end;
procedure TForm1.Button1Click(Sender: TObject); // процедура відкриття діалогу
begin
if Form1.OpenDialog1.Execute then
begin
StopScan:=false;
Work(OpenDialog1.FileName);
end;
end;
procedure TForm1.FormResize(Sender: TObject); // процедура встановлення розміру текстового поля
begin
Memo1.Height:=Height-70;
end;
procedure TForm1.Button3Click(Sender: TObject); // процедура збереження діалогу
begin
If SaveDialog1.Execute then
begin
If FileExists(SaveDialog1.FileName) then
IF MessageDlg('File'+#13+SaveDialog1.FileName+#13+'already exists!'
+#13+#13+'Overwrite (Yes/No) ?',mtWarning, [mbYes, mbNo], 0) = mrNo then exit;
Memo1.Lines.SaveToFile(SaveDialog1.FileName);
end;
end;
procedure TForm1.Button4Click(Sender: TObject); // процедура очищення текстового поля
begin
Form1.Memo1.Clear;
end;
function rol(const x:integer;const y:byte):integer ; // зсув числа x на y біт вліво
begin
asm
mov eax,x
mov cl, y
rol eax,cl
mov x, eax
end;
result:=x;
end;
3.4 Аналіз результатів роботи програми
Вхідною стрічкою даної програми є текстові файли, зображення та інші види інформації. Відкриття файлу для створення однонаправленого хеш-коду здійснюється за допомогою діалогового режиму. Отримана хеш-функція або контрольна сума, тобто в даному випадку повідомлення, яке однозначно ідентифікує ти чи іншу інформацію.
Для хеш-функції передбачено відображення розміру та імені.
Скріншот програми представлено нижче:
Час отримання контрольної суми залежить від розміру файлу.
Алгортитм SHA-1 широко застосовується в Сполучених Штатах Америки для наступних додатків: S/MIME – дайджест повідомлення
IPSec – для алгоритму перевірки цілісності
SSH – для перевірки цілісності переданих даних
PGP – для створення електронного цифрового підпису
4. Висновок
Темою даної курсової роботи є реалізація алгоритму SHA-1. Цей алгоритм використовується в багатьох криптографічних додатках і протоколах. SHA-1 реалізує однонаправлену хеш-функцію, побудовану на ідеї функції стиснення. Входами функції стиснення є блок повідомлення довжиною 512 біт і вихід попереднього блоку повідомлення.
Хеш-функції використовуються в системах контролю версій, системах електронних підписів. SHA-1 представляє собою найбільш розповсюдженим серед всього сімейства SHA і застосовується в різних криптографічних алгоритмах.
Порівняємо обидва алгоритми відповідно до тих цілей, які були визначені для алгоритму MD4:
Безпека: найбільш очевидна і найбільш важлива відмінність полягає в тому, що дайджест SHA-1 на 32 біта довший, ніж дайджест MD5. Якщо передбачити, що обидва алгоритми не містять яких-небудь структурованих даних, які уразливі для крипто аналітичних атак, то SHA-1 є стійкішим алгоритмом. Використовуючи лобову атаку, важче створити довільне повідомлення, що має даний дайджест, якщо потрібно порядку 2160 операцій, як в разі алгоритму SHA-1, чим 2128 операцій, як в разі алгоритму MD5. Використовуючи лобову атаку, важче створити два повідомлення, що мають однаковий дайджест, якщо потрібний порядку 280 як в разі алгоритму SHA-1, чим порядку 264 операції як в разі алгоритму MD5.
Швидкість: оскільки обоє алгоритму виконують складання по модулю 232, вони розраховані на 32-бітную архітектуру. SHA-1 містить більше кроків (80 замість 64) і виконується на 160-бітном буфері в порівнянні з 128-бітним буфером MD5. Таким чином SHA-1 повинен виконуватися приблизно на 25% повільніше, ніж MD5 на тій же апаратурі.
Простота і компактність: обоє алгоритму прості і в описі, і в реалізації, не вимагають великих програм або підстановлювальних таблиць. Проте SHA-1 застосовує одно крокову структуру в порівнянні з чотирма структурами, використовуваними в MD5. Більш того, обробка слів в буфері однакова для всіх кроків SHA-1, тоді як в MD5 структура слів специфічна для кожного кроку.
Яких-небудь яскраво виражених переваг в цих підходах не існує.
Список використаної літератури:
Цымбал В.П. Теория информации и кодирование.: - К.: Вища школа, 1992.
Лагутин О.И. Модемы. Справочник пользователя –СПб.:”Лань”,1997.
У.Титце, К. Шенк. Полупроводниковая схемотехника.: - М.: Мир, 1982..
Лекцій з курсу „ МЗКІТ ”
Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы — М.: Триумф, 2002. — 816 с. — 3 000 экз. — ISBN 5-89392-055-4.
Нильс Фергюсон, Брюс Шнайер Практическая криптография = P...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора