Цифровий підпис
Цифровий підпис: принципи роботи
Контрольні суми, контроль CRC, хешування і цифровий підпис - базові
засоби аутентифікації при цифровій передачі даних. Уявіть собі ситуацію:
вам відправили по електронній пошті документ з конфіденційною інформацією з
фінансування на майбутній рік. Вам необхідна абсолютна впевненість у тому, що
отриманий файл скоєно ідентичний оригіналу і що містяться в ньому цифри не були
змінені "в дорозі". Пара скоригованих значень можуть коштувати вашій фірмі
круглої суми. Підозра, що документ "в дорозі" було підроблено з'являється якщо
деякі цифри не сходяться, а електронна передача велася через зовнішню
поштову систему. Як переконатися в тому, що отриманий вами документ - абсолютна
копія відправленого вам оригіналу?
Розглянута ситуація не настільки штучна, як може здатися з першого
погляд. У століття, коли цифрова комерція швидко стає реальністю, довіра
користувачів до подібного роду систем цілком залежить від безпеки таких
транзакцій. Якщо відправити електронною поштою або передати на гнучкому диску
файл з електронною таблицею, то яким чином одержувач дізнається про те, що
ніхто, через кого ця інформація пройшла, не вніс яких-небудь змін? Якщо
переслати по мережі Internet номер своєї кредитної картки, то як адресат
переконається в тому, що саме ви зробили це замовлення?
Вирішення цих питань доведеться шукати в спеціальному розділі математики, який
називають криптографією. Часто під цим терміном мається на увазі звичайне
кодування, однак область криптографії не обмежена лише теорією шифрування
даних. Вона також охоплює питання, пов'язані з підміною цифрових даних -
як перевірити достовірність цифрових даних і як за аналогією з рукописної
підписом на папері проставити візу на електронних документах, маючи на
розпорядженні лише послідовності нулів та одиниць. У цій статті
розглядаються ключові поняття аутентифікації цифрової інформації - від
найпростіших засобів верифікації цілісності цифрових даних до розгляду
проекту державного стандарту США - Digital Signature Standard, а також
основні правила оформлення цифрового підпису.
Контрольні суми
Найбільш простий спосіб перевірки цілісності даних, які передаються в цифровому
поданні, - це метод контрольних сум. Під контрольною сумою розуміється
деяке значення, розраховане шляхом додавання всіх чисел з вхідних даних.
Якщо сума всіх чисел перевищує максимально допустиме значення, заздалегідь
заданий для цієї величини, то величина контрольної суми дорівнює коефіцієнту
отриманої суми чисел - тобто це залишок від ділення підсумкової суми на
максимально можливе значення контрольної суми, збільшена на одиницю. Якщо
сказане записати у вигляді формули, то для розрахунку контрольної суми буде
використовуватися наступне вираз:
Checkssum = Total% (MaxVal + 1)
де Total - підсумкова сума, розрахована за вхідними даними, і MaxVal -
максимально допустиме значення контрольної суми, задане заздалегідь.
Припустимо, документ, вміст якого належить верифікувати, представляє
собою наступну послідовність величин, довжиною 10 байт:
36 211 163 4 109 192 58 247 47 92
Якщо контрольна сума 1 байт величина, то максимальне число, яке вона може
містити, так само 255 Для наведеного вище документа сума всіх його чисел одно
1159. Таким чином, 8-розрядів контрольної суми будуть містити залишок від
ділення числа 1159 на 256, тобто 135. Якщо контрольна сума, розрахована
відправником документа, дорівнювала, скажімо, 246, а після отримання вона має
значення 135, значить, інформація зазнала зміни. Метод контрольних сум -
це найбільш проста форма цифрової ідентифікації (digital fingerprint); тобто
величина, отримана в результаті підрахунку вмісту деяких інших даних,
змінюється при корекції даних, на основі яких він отриманий. Використання
алгоритму контрольних сум почалося ще на зорі обчислювальної техніки і до цих
пір він є базовим під час перевірки на помилки в деяких версіях широко
поширеного протоколу передачі даних XMODEM.
Недолік методу контрольних сум полягає в тому, що хоча розбіжність
значень цих сум служить вірним доказом, що даний документ
піддався зміні, рівність порівнюваних значень ще не дай гарантії, що
інформація залишилася незмінною. Можна довільним чином змінити порядок
слідування чисел в документі, а контрольна сума при цьому збереже колишнє
значення.
І що ще гірше - можна змінити окремі числа в документі і підігнати
інші таким чином, щоб забезпечити колишнє значення контрольної суми.
При використанні для контрольних сум 8-розрядної змінної ймовірність того,
що контрольні суми двох зовсім випадково обраних послідовностей
даних будуть однакові, дорівнює 1/256. При збільшенні довжини змінної під
контрольну суму до 16 або 32 розрядів, ймовірність збігів зменшується,
проте цей механізм все одно дуже чутливий до можливих помилок, щоб
забезпечити високу ступінь довіри до представлених даних.
Контроль CRC
Більш досконалий спосіб цифрової ідентифікації деякої послідовності
даних - це обчислення контрольного значення її циклічного надмірного коду
(cyclic redundancy check - CRC). Алгоритм контролю CRC вже протягом тривалого
часу широко використовується в системах мережевих адаптерів, контролерів жорсткого
диска та інших пристроїв для перевірки ідентичності вхідний і вихідний
інформації.
А також цей механізм застосовується в багатьох з нині існуючих
комунікаційних програм для виявлення помилок при пакетної передачі по
телефонних лініях зв'язку.
Механізм CRC заснований на поліноміальною розподілі, де кожен розряд
деякої порції даних відповідає одному коефіцієнту великого
поліноміальною вирази. Нагадаємо, що поліномом називається математичне
вираз, представлене наступним чином:
f (x) = 4x3 + x2 + 7
Для виконання розрахунків контролю CRC поліном, що представляє байт даних з
значенням 85 (8-розрядний двійковий еквівалент якого - 01010101) виглядає так:
0x7 + 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 0x1 + 1x0
або просто
x6 + x4 + x2 + 1
Ключовим принципом обчислень для механізму CRC є те, що операції
множення і ділення цих поліномів виконуються точно так само, як зі звичайними
числами. Якщо деякий "магічний" поліном (коефіцієнти якого отримані в
відповідно до використовуваним алгоритмом CRC) розділити на поліном, що представляє
якусь послідовність даних, то в результаті виходить поліном-приватне і
поліном-залишок. Друге з цих значень є основою для створення
контрольного параметра CRC. Так само, як і для контрольних сум, параметром CRC
не потрібно багато місця (зазвичай їх довжина становить 16 або 32 розряди); однак
в порівнянні з ними, надійність виявлення невеликих змін вхідний
інформації тепер значно вище. Якщо в деякому величезному блоці даних лише
один розряд став іншим, то й контрольний параметр CRC зі 100-відсотковою
ймовірністю також буде мати інше значення. Якщо ж зміняться два розряди,
то вірогідність виявлення помилки при довжині параметра CRC в 16-розрядів,
складає більше 99, 99%. На відміну від контрольних сум метод CRC зможе
розпізнати всякі фокуси з перестановкою двох байт або з додаванням 1 до одного
з них і вирахуванням 1 з іншого.
Механізм CRC надзвичайно корисний для перевірки файлів, що завантажуються з мережевих
інформаційних служб. Якщо хтось повідомляє мені, що передана йому через мережу ZD
Net утиліта раптом без видимої причини перестає працювати, то насамперед я
прошу його створити її архівний файл з допомогою програми PKZIP і набрати команду
PKZIP-V для перегляду створеного. ZIP файлу. Серед інших параметрів він побачить
також 32-розрядне значення параметра CRC, розраховане програмою PKZIP для
нестисненого файлу. Якщо обчислена значення параметра CRC для gjkextyyjq утиліти
не збігається
із значенням для вихідного варіанту файлу, значить, при завантаженні його сталася
невиявлені помилка передачі даних (таке іноді трапляється).
Можна організувати власний контроль CRC для ідентифікації файлів; для цього
потрібно переписати через службу PC Magazine Online файл CRC. COM. (Він
знаходиться в бібліотеці Tutor форуму Utilities/Tips служби ZD Net/CompuServe і в
фото V15N07. ZIP (на сервері за адресою http://www. Pcmag. Com). CRC. COM - це
утиліта DOS, якій в якості вхідного параметра вказується ім'я файлу. Виходячи
з в ньому інформації, вона розраховує 32-розрядне значення контролю
CRC. У програмі використаний відомий алгоритм розрахунку параметра CRC-32,
застосовуваний PKZIP та мережевих адаптери Token-Ring фірми IBM. Цей алгоритм
відрізняється високою швидкодією (вихідний текст повністю написаний на мові
асемблера;
проводиться буферизація під час читання/запису з диска; прекрасно реалізований
алгоритм розрахунку CRC-32 - все це дозволяє скоротити до мінімуму обсяг
вироблених обчислень) та розпізнає файли будь-якого розміру. Тепер при пересиланні
файлів через модем утиліта CRC. COM зможе надати вам неоціненну послугу - дати
впевненість, що інформація передана без спотворень.
Отримавши по мережі файл CRC. COM, першою справою перевірте сам цей файл, набравши в
рядку DOS команду:
CRC CRC. COM
Якщо отримане значення параметра CRC не дорівнює 86C23FA, значить файл слід
завантажити знову.
Алгоритми хешування
Проблема в тому, що навіть контроль за допомогою 32-розрядного значення CRC володіє
певними недоліками - він стійко виявляє випадкові зміни у
вхідної інформації (наприклад, що виникають у результаті збоїв при передачі
даних), однак недостатньо надійний у разі навмисних дій. Якщо для
ідентифікації деякого файлу ви використовуєте його 32-розрядний параметр CRC, то
для кого-то не так уже й складно за допомогою комп'ютера створити зовсім інший файл
з тим же значенням CRC.
Більш високу надійність, ніж при контролі CRC, можна досягти при використанні
односторонніх алгоритмів хешування; результатом їх роботи є особливі
"хешірованние" значення. Під терміном "односторонні" розуміється наступне: маючи
на вході А, можна без особливих зусиль отримати на виході В, але зробити протилежне -
тобто з В отримати А - неможливо, або, у всякому разі, практично
неможливо. Важлива відмінна риса будь-якого вдалого алгоритму
хешування полягає в тому, що генеруються з його допомогою значення настільки
унікальні і трудноповторіми, що навряд чи хтось навіть за допомогою серії
суперкомп'ютерів Cray і витративши колосальну кількість часу, зможе знайти
два набору вхідних даних, що мають однакові значення хешування. Як правило,
ці параметри займають не менше 128 розрядів. Чим більше їх довжина, тим важче
відтворити вхідний набір даних, тобто знайти послідовність,
забезпечує відповідний результат.
Серед односторонніх алгоритмів хешування найбільшою популярністю користуються
два з них: алгоритм MD5 (message digest), розроблений професором
Массачусетського технологічного інституту Роном Рівестом (Ron Rivest) (один з
авторів популярної криптосистеми з ключем загального користування RSA), і алгоритм
Secure Hash Algorithm (SHA), створений спільними зусиллями Національного
інституту із стандартизації і технологічних розробок (NIST) і Управління
національної безпеки США (NSA). Результат аналізу послідовності
вхідних даних за допомогою алгоритму MD5 - 128-розрядний цифровий ідентифікатор, а
при використанні алгоритму SHA - 160-розрядне значення. Враховуючи, що поки
нікому не вдалося підібрати ключ до жодного з названих алгоритмів, можна
вважати, що відновлення вихідних даних по деякому хешірованному
значенню, що є результатом роботи алгоритму SNA або по деякому
коефіцієнту алгоритму MD5 нереально. Таким чином, якщо вам відправили якийсь
файл і ідентифікатор, отриманий в результаті застосування до нього алгоритму MD5
або SHA, і якщо ви виконали з ним той же алгоритм хешування і ваш результат
збігся з початковим значенням, з певністю можна бути впевненим, що прийнятий вами
файл не піддався спотворень.
Алгоритм MD5
Термінологія
У даному випадку "word" є 32-х бітної величиною, "byte" - 8-ми бітна
величина. Послідовність біт повинна інтерпретуватися таким же способом що
і послідовність байт, де кожна послідовна група з восьми біт
інтерпретується як байт з старшим (найбільш значущим) бітом кожного байта
наступним у послідовності першим. Подібно до послідовності байт повинна
інтерпретуватися і послідовність 32-бітових слів.
Запис x_i означає "x sub i" (тобто х з індексом i). Якщо деякий вираз
використовується як індекс, то воно береться в фігурні дужки, наприклад x_ (i +1).
Символ "^" використовується для операцій зведення в ступінь, тобто x ^ i слід
розуміти як х в ступені i.
Символ "+" означає операцію додавання слів (тобто додавання по модулю 2 ^ 32).
Далі x
циклічного зсуву (обертання) попереднього значення х на s біт вліво. not (x) -
порозрядної операція заперечення, xvy - порозрядне АБО (OR) операндів x і y, x
xor y - порозрядне виключає АБО (XOR) операндів x та y, і xy - порозрядне
І (AND) операндів x та y.
Короткий опис алгоритму MD5
Спочатку допускаємо, що маємо на вході повідомлення з b-біт, і що ми бажаємо знайти
Message Digest цієї послідовності біт. Число b є довільним
невід'ємним цілим; b може бути рівним нулю, воно не обов'язково має бути
множником 8, і воно може бути довільно великим. Уявімо
послідовність біт повідомлення як:
m0 m1 m2. . . . . . m (b-1)
Наступні п'ять етапів виконуються для підрахунку Message Digest повідомлення.
Етап 1. Приєднання заповнюють (додаткових) бітів.
Повідомлення розширюється так, щоб його довжина (у бітах) співпадала з 448, по модулю
512. Доповнення завжди виконується, навіть якщо довжина повідомлення - вже співпадає з
448 за модулем 512. Доповнення виконується таким чином: одиночний "1" біт
додається до повідомлення, і далі "0" біти додаються так що довжина в бітах
заповнюваного повідомлення відповідає 448 за модулем 512. У загальному випадку, мінімум
один біт і максимум 512 біт додається.
Етап 2. Додавання довжини
64-бітове представлення вхідної послідовності b (довжина повідомлення перед
розширенням додатковими бітами) приєднується до результату попереднього
етапи. Малоймовірно, що довжина b буде більше, ніж 264 тому і використовується
64-х розрядна величина для зберігання довжини b. (Ці біти додаються як два 32-х
розрядних слова, молодше заноситься першим).
У цьому місці остаточне повідомлення (після виконання першого і другого етапів)
має довжину, кратну 512 бітам, тобто повідомлення має довжину, яка точно
кратна 16-ти словами. Послідовність М [0. . . . N-1] є словами
остаточного повідомлення, де N кратне 16.
Етап 3. Ініціалізація MD буфера.
Буфер на 4-е слова (A, B, C, D) використовується для підрахунку Message Digest. Кожне
з A, B, C, D є 32-х бітним регістром. Ці регістри ініціалізувалися
наступними шістнадцяткові значеннями, де першим слід наймолодший байт:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Програмісти з RSA Data Security, Inc. , Щоб не обтяжувати себе і інших
людей з приводу походження цих чисел, просто назвали їх магічними
константами.
Етап 4. Обробка повідомлення в блоках по 16 слів.
Спочатку визначаються чотири допоміжних функції кожна з яких має на
вході три 32-бітових слова і виробляє одне 32-бітне слово на виході.
F (X, Y, Z) = XY v not (X) Z
G (X, Y, Z) = XZ v Y not (Z)
H (X, Y, Z) = X xor Y xor Z
I (X, Y, Z) = Y xor (X v not (Z))
У кожній бітової позиції функція F діє як умовний опреатор: якщо X те Y
інакше Z. Функція F могла б визначатися з використанням операцію + замість v,
бо вираз XY and not (X) Z ніколи не матиме 1 в однакових бітових
позиціях.
Якщо біти X, Y і Z неза?? Сіми і несмещени (??), то кожен біт після виконання
F (X, Y, Z) буде незалежний і несмещен.
Опції G, H і I подібні функції F, вони діють в "побітового відповідно" для
знаходження вихідного значення від вхідних бітів X, Y і Z, тим же способом, що
якщо біти X, Y і Z незалежні і несмещени, то кожен біт після виконання
вищевказаних функцій буде незалежний і несмещен. Зверніть увагу, що функція
H (X, Y, Z) є порозрядної операцією виключає АБО (тобто функцією
контролю парності вхідних значень). Далі на цьому етапі відбувається чотири
циклу, в яких відбувається трансформація бітів повідомлення за допомогою
вищевказаних
функцій, функцій циклічного зсуву, і таблиці константних значень.
Етап 5. Висновок
В результаті виконання попередніх етапів Message Digest виробляє на виході
числа A, B, C, D, загальна довжина яких 128 біт.
Резюме
Алгоритм отримує на вході повідомлення довільної довжини і після обробки на
виході отримуємо 128-бітний "відбиток" або "Message Digest". Передбачається, що
обчислювальна трудомісткість знаходження двох повідомлень, що мають однакові
Message Digest дуже велика. MD5 алгоритм призначений для додатків,
формують цифрові сигнатури, в яких великий файл повинен бути "стиснутий"
безпечним способом перед зашифровки відкритим (або секретним) ключем до деякої
криптосистеми з відкритим ключем, такий як RSA.
MD5 алгоритм є розширенням алгоритму MD4.
MD5 алгоритм повністю розроблений для швидкої роботи на 32-х розрядних машинах.
До того ж алгоритм не вимагає яких-небудь великих таблиць;
забезпечується компактна кодування.
MD5 Message Digest алгоритм простий у використанні, і забезпечує одержання
128-ми бітного "відбитка" або Message Digest повідомлення довільної довжини.
Передбачається, що складність знаходження двох повідомлень, які зроблять
однакові Message Digest є близько 2 в 64 ступені операцій, і складність
побудови повідомлення по деякому відомому Message Digest є близько 2
в 128 ступені операцій.
Приклади вихідного коду для реалізації MD5.
Макроси
F, G, H, I
Дані макроси визначають чотири допоміжні функції, кожна з яких
має на вході три 32-бітових слова і виробляє одне 32-бітне слово на виході.
# define F (x, y, z) (((x) & (y)) ((~ x) & (z)))
# define G (x, y, z) (((x) & (z)) ((y) & (~ z)))
# define H (x, y, z) ((x) ^ (y) ^ (z))
# define I (x, y, z) ((y) ^ ((x) (~ z)))
У кожній бітової позиції функція F діє як умовний оператор: якщо X те Y
інакше Z. Якщо біти X, Y і Z незалежні і несмещени (??), то кожен біт після
виконання F (X, Y, Z) буде незалежний і несмещен.
Опції G, H і I подібні функції F, вони діють в "побітового відповідно" для
знаходження вихідного значення від вхідних бітів X, Y і Z, тим же способом, що
якщо
біти X, Y і Z незалежні і несмещени, то кожен біт після виконання
вищевказаних функцій буде незалежний і несмещен. Слід звернути увагу, що
функція H (X, Y, Z) є порозрядної операцією виключає АБО (тобто
функцією контролю парності вхідних значень).
FF, GG, HH, II
Дані макроси визначають чотири допоміжних функції, які на вході
отримують сім 32-х розрядних параметрів, а на виході отримуємо одну 32-х
розрядну величину.
Ці Функція використовуються у функції Transform () для бітових перетворень.
Опції працюють таким чином:
1. У вихідний параметр записується сума відповідної функції (для FF () це
F (), для GG () це G (), для HH () це H (), для II () це I ()) від 2-го, 3-го і 4-го
параметрів з 5-м і 7-м параметрами.
2. Проводиться циклічний зсув вліво вихідного параметра на кількість біт,
зазначене в 6-му вхідному параметрі.
3. Проводиться збільшення вихідного параметра на величину, зазначену в 2-му
вхідному параметрі.
# define FF (a, b, c, d, x, s, ac)/
((a) + = F ((b), (c), (d)) + (x) + (UINT4) (ac);/
(a) = ROTATE_LEFT ((a), (s));/
(a) + = (b);/
)
# define GG (a, b, c, d, x, s, ac)/
((a) + = G ((b), (c), (d)) + (x) + (UINT4) (ac);/
(a) = ROTATE_LEFT ((a), (s));/
(a) + = (b);/
)
# define HH (a, b, c, d, x, s, ac)/
((a) + = H ((b), (c), (d)) + (x) + (UINT4) (ac);/
(a) = ROTATE_LEFT ((a), (s));/
(a) + = (b);/
)
# define II (a, b, c, d, x, s, ac)/
((a) + = I ((b), (c), (d)) + (x) + (UINT4) (ac);/
(a) = ROTATE_LEFT ((a), (s));/
(a) + = (b);/
)
Відразу можна відзначити, що вхідні параметри вищевказаних функцій представляють
собою такі значення:
register UINT4 a = buf [0], b = buf [1], c = buf [2], d = buf [3]; Як видно
регістрові змінні a, b, c, d типу UINT4 ініціалізувалися значеннями
тимчасового буфера buf [4] що міститься в основній структурі Message Digest
MD5_CTX. П'ятий параметр x завжди ініціалізується символом з вхідного буфера
in [64] також знаходиться в структурі MD5_CTX.
Параметр s дорівнює одній із шістнадцяти констант, визначених у функції
Transform ().
А ось самий останній параметр ас дорівнює одному з 64-х "таємничих констант".
Розробники з RSA Data Security, Inc. пропонують вам розташувати ці константи
в "little-endian" порядку, розшифрувати за допомогою DES і ви отримаєте ТАЄМНІ
Послання. (от тільки DESовий ключик вони не вказали).
ROTATE_LEFT
Цей макрос зрушує x вліво на n біт.
# define ROTATE_LEFT (x, n) (((x) <(n)) ((x)>> (32 - (n))))
Якщо n> 32, то результат дорівнює нулю.
Опції
void MD5Init (MD5_CTX * mdContext)
Функція MD5Init (MD5_CTX * mdContext) виконує ініціалізацію деяких полів
структури Message Digest MD5_CTX Як параметр функція одержує покажчик
на структуру MD5_CTX.
(
/ * Обнулення полів, які будуть містити довжину повідомлення */
mdContext-> i [0] = mdContext-> i [1] = (UINT4) 0;
/ * Завантаження магічних констант ініціалізації. */
mdContext-> buf [0] = (UINT4) 0x67452301L;
mdContext-> buf [1] = (UINT4) 0xefcdab89L;
mdContext-> buf [2] = (UINT4) 0x98badcfeL;
mdContext-> buf [3] = (UINT4) 0x10325476L;
)
void MD5Update (register MD5_CTX * mdContext, unsigned char * inBuf, unsigned int
inLen)
Ця функція обробляє вміст структури MD5_CTX.
Як параметри функція одержує:
Покажчик mdContext на структуру MD5_CTX;
Cімвольний буфер inBuf [], який містить символи оригінальне повідомлення, чий
Message Digest ми підраховуємо; Довжину inLen переданого буфера.
Спочатку підраховується цілочисельних величина mdi:
mdi = (int) ((mdContext-> i [0]>> 3) & 0x3F);
Ця величина дорівнює довжині повідомлення в байтах за модулем 64. Довжина повідомлення в
бітах зберігається в структурі MD5_CTX в буфері i [0. . 1].
Довжина повідомлення в бітах заноситься в буфер i [0. . 1] наступним чином:
mdContext-> i [0] + = ((UINT4) inLen
mdContext-> i [1] + = ((UINT4) inLen>> 29);
Наступний ділянку коду виконує наступні дії:
while (inLen -)
(
/ * Додаємо новий символ у буфер, інкрементіруя mdi */
mdContext-> in [mdi + +] = * inBuf + +;
/ * Якщо необхідно виконуємо перетворення */
if (mdi == 0x40)
(
for (i = 0, ii = 0; i <16; i + +, ii + = 4)>
in [i] = (((UINT4) mdContext-> in [ii 3])
(((UINT4) mdContext-> in [ii 2])
(((UINT4) mdContext-> in [ii 1])
((UINT4) mdContext-> in [ii]);
Transform (mdContext-> buf, in);
mdi = 0;
)
)
Поки зменшується на 1 довжина переданого у функцію повідомлення не стане рівною
нулю виконуємо наступні дії:
Заносимо новий символ з вхідного буфера функції в 64-х байтним буфер структури
MD5_CTX, збільшуючи при цьому змінну mdi на 1. Якщо mdi дорівнює 64, то
перетворимо
однобайтние символи буфера in [] структури MD5_CTX в 4-х байтним величини типу
UINT4, заносимо в проміжний буфер на 16 величин типу UINT4, і далі передаємо
функції Transform (). Надаємо змінної mdi 0.
void MD5Final (MD5_CTX * mdContext)
Функція завершує обчислення Message Digest і заносить отримане значення в
структурі MD5_CTX в символьний буфер digest [0. . . 15].
Вхідним параметром функції є покажчик на структуру MD5_CTX.
Основні моменти:
Розширення повідомлення заповнюють додатковими символами з таблиці PADDING []
/ * Підрахунок довжини повідомлення в байтах за модулем 64 */
mdi = (int) ((mdContext-> i [0]>> 3) & 0x3F);
/ * Розширити до 56 за модулем 64 */
padLen = (mdi <56)? (56 - mdi): (120 - mdi);>
MD5Update (mdContext, PADDING, padLen);
Приєднання бітів довжини і виклик функції Transform ().
in [14] = mdContext-> i [0];
in [15] = mdContext-> i [1];
for (i = 0, ii = 0; i <14; i + +, ii + = 4)>
in [i] = (((UINT4) mdContext-> in [ii 3])
(((UINT4) mdContext-> in [ii 2])
(((UINT4) mdContext-> in [ii 1])
((UINT4) mdContext-> in [ii]);
Transform (mdContext-> buf, in);
Збереження буферу в digest (тобто отримання остаточного Message Digest):
for (i = 0, ii = 0; i <4; i + +, ii + = 4)>
(
mdContext-> digest [ii] = (unsigned char) (mdContext-> buf [i] & 0xFF);
mdContext-> digest [ii 1] = (unsigned char) ((mdContext-> buf [i]>> 8) & 0xFF);
mdContext-> digest [ii 2] = (unsigned char) ((mdContext-> buf [i]>> 16) & 0xFF);
mdContext-> digest [ii 3] = (unsigned char) ((mdContext-> buf [i]>> 24) & 0xFF);
)
void Transform (register UINT4 * buf, register UINT4 * in)
Ця функція є основним кроком в алгоритмі MD5.
Вхідними параметрами є покажчик на буфер buf [] із структури MD5_CTX і
покажчик на буфер in [], що зберігає значення типу UINT4. Функція виконує 4 циклу
по 16 кроків у кожному. У кожному циклі використовується одна з функцій FF, GG, HH,
II. Далі остаточний результат після 64-х перетворювальних ітерацій
додається до вмісту буфера buf [].
Структура MD5_CTX
Структура MD5_CTX є основною структурою для формування MessageDigest.
Структура містить наступні поля:
typedef struct
(
UINT4 i [2];/* кількість біт в повідомленні за mod 2 ^ 64 */
UINT4 buf [4];/* тимчасовий буфер */
unsigned char in [64];/* вхідний буфер */
unsigned char digest [16];/* містить дійсний Message Digest
після виклику MD5Final () */
) MD5_CTX;
 
Цифровий підпис і криптосистеми з ключем загального користування.
Якщо використовувати алгоритми хешування разом з криптосистемами з ключем загального
користування, то можна створити цифровий підпис, що гарантує достовірність
отриманого набору даних, аналогічно тому, як рукописна підпис, підтверджує
автентичність надрукованого документа. Криптосистема з ключем загального користування
- Це метод, що дозволяє здійснювати кодування та декодування інформації, з
допомогою двох вихідних ключів: ключа загального користування, вільно переданого
всім бажаючим, і особистого ключа, відомого тільки його власнику.
Сенс ключа і пароля приблизно однаковий. Припустимо, Том бажає, щоб Сем міг
відправити йому зашифрований документ, і обидва вони не хотіли б ризикувати,
передаючи пароль чи ключ по лініях зв'язку, тому що в цьому випадку він може бути
кимось перехоплений. Тоді Том може передати Сему свій ключ загального користування
(схема 1).
Використовуючи цей ключ, Сем шифрує документ і відправляє його Тому. Том дешифрує
документ за допомогою свого особистого ключа. Це єдиний ключ, з допомогою
якого можна відновити документ, зашифрований із застосуванням ключа загального
користування, що належить Тому. Той факт, що ключ загального користування Тома
може стати комусь відомий, не має особливого значення, тому що він абсолютно
даремний для розшифровки документа. А особистий ключ, відомий одному лише Тому,
з відкритих лініях зв'язку не передавався; теоретично тому зберігає його тільки в
власної пам'яті і навпаки, робота інших криптосистем з ключем загального
користування будується на зворотному принципі: Сем шифрує документ за допомогою свого
особистого ключа і передає свій ключ загального користування Тому, за допомогою якого
той міг би розшифрувати цей документ. Існуючі нині криптосистеми з ключем
загального користування, такі, наприклад, як система RSA (скорочення, складене
з перших літер прізвищ трьох творців цього алгоритму), широко використовуються.
Як же здійснюється цифровий підпис? Розглянемо ще один приклад. Припустимо,
Сем збирається відправити Тому контракт або номер своєї кредитної картки в
цифровому вигляді. Для підтвердження достовірності цих документів Тому потрібна
цифровий підпис Сема. Спочатку Сем відправляє свій документ. Потім використовує
алгоритм хешування для обчислення ідентифікатора цього документа, шифрує
хешірованное значення за допомогою свого особистого ключа і відправляє його Тому. Це
і є цифровий підпис Сема. Том за допомогою того ж алгоритму хешування
спочатку обчислює ідентифікатор прийнятого документа. Потім він розшифровує
значення, яке отримав від Сема, використовуючи наданий Семом ключ загального
користування. Якщо два значення хешування збіглися, Том не тільки дізнається, що
цей документподлінний, а й те, що підпис Сема дійсна. Зрозуміло, що
проведення комерційних транзакцій за таким сценарієм значно безпечніше,
ніж з використанням підпису від руки на папері, яку можна підробити. А якщо
відомості, що передаються Семом Тому, конфіденційні (наприклад, містять номер
кредитної картки), то і їх можна зашифрувати так, щоб прочитати їх зміг
тільки Том.
 
Message Digest і цифрові сигнатури
При створенні цифрової сигнатури деякого повідомлення PGP необхідно зашифрувати
його секретним ключем. Але PGP насправді не використовує секретний ключ для
шифрування повністю всього повідомлення, тому що цей процес був би довгим. Замість
цього PGP шифрує MessageDigest.
MessageDigest є компактною (128 біт) "перегонкою" Вашого повідомлення,
подібно до концепції контрольної суми. Ви також можете уявити MessageDigest
як "відбиток" повідомлення. MessageDigest представляє ваше повідомлення таким
чином, що якщо це повідомлення буде змінено будь-яким чином, то з
зміненого повідомлення буде підраховано відмінне від початкового
MessageDigest. Це дає можливість виявлення будь-яких змін, зроблених
зломщиком. MessageDigest обчислюється, використовуючи криптографічно стійку
односпрямований хеш-функцію повідомлення. Підбір повідомлення, яке зробить
ідентичне MessageDigest є з обчислювальної точки зору нездійсненно
для зломщика. У цьому відношенні МessageDigest набагато краще, ніж контрольна
сума (оскільки легше підібрати різні повідомлення, які будуть мати однакові
контрольні суми). Неможливо отримати початкове повідомлення по його MessageDigest.
Одного тільки MessageDigest не достатньо для аутентифікації повідомлення. Алгоритм
MD опубліковано, і не вимагає знання секретних ключів для обчислень. Якщо ми
просто будемо прикріплювати MessageDigest до повідомлення, то зломщик зможе змінити
повідомлення, обчислити його MessageDigest, прикріпити MessageDigest до зміненого
повідомленням і відправити далі. Для забезпечення реальної аутентифікації
відправник шифрує (підписує) MessageDigest своїм секретним ключем.
MessageDigest обчислюється з повідомлення відправником. Секретний ключ відправника
використовується для зашифровки MessageDigest і деякого тимчасового відбитка
(timestamp), формуючи цифрову сигнатуру, або сертифікат сигнатури. Відправник
посилає цифрову сигнатуру перед повідомленням. Одержувач отримує повідомлення і
цифрову сигнатуру, відновлює початкове MessageDigest з цифрової сигнатури
за допомогою розшифровки відкритим ключем відправника, заново обчислює
MessageDigest повідомлення і проводить порівняння з отриманими від відправника
MessageDigest. Якщо вони рівні, то над повідомленням не було зроблено ніяких
змін.
Потенційний зломщик має або зробити деяке повідомлення, яке
породжує ідентичне MessageDigest (що нездійсненно), або він повинен створити
нову цифрову сигнатуру від зміненого MessageDigest (що також нездійсненно
без знання секретного ключа відправника).
Цифрові сигнатури виробляють аутентифікацію повідомлення, а також перевірку
правильності повідомлення при його передачі між користувачами для виявлення
змін повідомлення від впливу будь-яких помилок або навмисних дій.
Використання MessageDigest для формування цифрових підписів має й інші
переваги крім істотної швидкості, ніж безпосереднє підписування
повного повідомлення секретним ключем. Message Digest дозволяє сигнатурах бути
Стандартний функцією невеликий фіксованої довжини, незалежно від розмірів
дійсного повідомлення. Також дозволяє контролювати цілісність повідомлення
автоматично, подібним способом використання контрольної суми, дозволяє
сигнатурі зберігатися окремо від повідомлення, можливо в деякому публічному
архіві, без викриття секретної інформації про дійсний повідомленні, оскільки
ніхто не зможе отримати повідомлення з його MessageDigest.
Схема. Система цифрового підпису.
1. Сем обробляє за спеціальним алгоритмом документ, який збирається
відправити Тому, в результаті отримує деякий параметр, розрахований на
підставі вмісту документа. Зазвичай це займає значно менше місця,
ніж вихідний документ - параметр 128 або 160 двійкових розрядів.
Потім Сем за допомогою свого особистого ключа шифрує отриманий параметр. Підсумкове
значення служить цифровим підписом Сема.
Сем відправляє Тому документ і свою цифровий підпис.
Том пропускає документ, отриманий від Тома, через той же алгоритм, яким
користувався Том.
Потім Том дешифрує цифровую підпис, отриману від Сема, користуючись
наданим Семом ключем загального користування.
Том порівнює значення параметра, отриманого при виконанні операції 4, з
розшифрованим значенням цифрового підпису. Якщо ці значення збігаються, значить,
підпис справжня і документ "в дорозі" не зазнав змін. В іншому
випадку, чи документ спотворено, або підпис підроблена, або і те й інше.
Найімовірніше саме за такою, або подібною схемою будуть вестися справи через
Internet або будь-яку іншу інформаційну службу. Цей алгоритм послужив основою
проекту державного стандарту США - Digital Signature Standard (DSS). У ньому
застосовуються: алгоритм Secure Hash Algorithm для розрахунку параметрів хешування і
криптосистема з ключем загального користування, відома під назвою Digital
Signature Algorithm (DSA) і призначена для отримання цифрового підпису за
параметрами хешування. Ряд пунктів проекту DSS зазнали критики, однак
багато хто з зауважень виходили від груп, фінансово зацікавлених у відхиленні
даного проекту.
Час покаже, чи який-небудь із методів створення цифрового підпису прийнятий в
як стандарт. Однак незалежно від результату, важливо інше:
дійсно існує можливість зовсім безпечно здійснювати цифрові
торгові операції.