Подякувати Студентському архіву довільною сумою
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, 10).
По кількості помилкових розрядів помилки бувають одно, двох і більше кратними.
Експериментальні дослідження показали, що помилки символів при передачі по каналу зв’язку групуються у пачки різної тривалості. Пачка – це участок послідовності символів, які починаються і закінчується помилковими символами. В середині пачки можуть бути і окремі правильні символи.
Для визначення місця помилкових символів у кодовій комбінації використовується вектор помилки е (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) – перехіід із дозволених у заборонені.
Таким чином не всі спотворення можуть бути виявлені. Частка помилкових комбінацій, що можуть бути виявлені визначається як
EMBED Equation.3 ;
Для використання коду як коректуючого, множина заборонених кодових комбінацій розбивається на N підмножин Mі , що не перетинаються. Кожна їз цих підмножин відповідає одній із дозволених комбінацій Аі . Якщо прийнята заборонена комбінація належить підмножині Mі , то вважається, що передана комбінація Аі. Помилка буде виправлена лише тоді, коли заборонена комбінація утворилася із Аі . Таким чином, помилка виправляється в (N0-N) випадках (тільки для заборонених комбінацій). Частка виправлених помилкових комбінацій із загальної кількості виявлених помилкових рівна
EMBED Equation.3 ;
Спосіб розбиття на підмножини залежить від того які помилки повинні виправлятися даним кодом.
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 розрядів коду, який виявляє та коректує одну помилку приведена в таблиці:
На основ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
12 11 10 9 8 7 6 5 4 3 2 1
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.
Криптостійка хеш-кодування функція перш за все повинна володіти стійкістю до колізій двох типів:
- стійкість до HYPERLINK "mhtml:file://D:\\3SEMESTR\\Методи%20і%20засоби%20ІТ\\Курсак\\Хеширование%20—%20Википедия.mht!/wiki/%D0%9A%D0%BE%D0%BB%D0%BB%D0%B8%D0%B7%D0%B8%D1%8F_%D1%85%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8" \o "Коллизия хеш-функции" колізії першого роду: для заданого повідомлення повинно бути практично неможливо підібрати інше повідомлення, що має таке ж хеш-кодування. Ця властивість також називається безповоротністю хеш-функції.
- стійкість до колізії другого роду: повинно бути практично неможливо підібрати пару повідомлень, що мають однакове хеш-кодування.
Наприклад, при записі текстових полів в базі даних може розраховуватися їх хеш-кодування код і дані можуть поміщатися в розділ, відповідний цьому хеш-коду|. Тоді при пошуку даних треба буде спочатку обчислити|обчисляти| хеш-кодування-код тексту і відразу стане відомо, в якому розділі їх треба шукати, тобто|цебто|, шукати треба буде не по всій базі, а тільки|лише| поодинці її розділу (це сильно прискорює пошук).
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 –...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора