Всі теми даного розділу:
Однонаправлені хеш-функції
18.1 Основи Односпрямована функція ЩМ) застосовується до повідомлення довільної довжини М і повертає значення фіксованої довжини h. h = ЩМ), де
Довжини односпрямованих хеш-функцій
64-бітові хеш-функції занадто малі, щоб протистояти розтину методом дня народження. Більш практичні односпрямовані хеш-функції, що видають 128-бітові хеш-значення. При цьому, щоб знайти два
Огляд односпрямованих хеш-функцій
Нелегко побудувати функцію, вхід якої має довільний розмір, а тим більше сделаьть її однон а-спрямованої. У реальному світі односпрямовані хеш-функції будуються на ідеї функції стиснення.
криптоаналіз Snefru
Використовуючи диференційний криптоаналіз, Біхам і Шамір показали небезпечність двопрохідні Snefru (з 128-бітовим хеш-значенням) [172]. Їх спосіб розтину за кілька хвилин виявляє пару спо
опис MD5
Після деякої первісної обробки MD5 обробляє вхідний текст 512-бітовими блоками, раз-битими на 16 32-бітових подблоков. Виходом алгоритму є набір з чотирьох 32-бітових блоків, до
Безпека MD5
Рон Ривест навів такі поліпшення MD5 в порівнянні з MD4 [1322]: 1. Додався четвертий етап. 2. Тепер в кожній дії використовується унікальна прибавляемая константа.
опис SHA
По-перше, повідомлення доповнюється, щоб його довжина була кратною 512 бітам. Використовується той же доповнення-ня, що і в MD5: спочатку додається 1, а потім нулі так, щоб довжина отриманого повідомлення б
Безпека SHA
SHA дуже схожа на MD4, але видає 160-бітове хеш-значення. Головною зміною є введення розширює перетворення і додавання виходу попереднього кроку в наступний з метою отримання більш
Модифікація схеми Davies-Meyer
Лай (Lai) і Массей (Massey) модифікували метод Davies-Meyer, щоб можна було використовувати шифр IDEA [930, 925]. IDEA використовує 64-бітовий блок і 128-бітовий ключ. Ось запропонована ними схема:
Preneel-Bosselaers-Govaerts-Vandewalle
Ця хеш-функція, вперше запропонована в [1266], видає хеш-значення, в два рази більше довжини блоку алгоритму шифрування: при 64-бітовому алгоритмі виходить 128-бітове хеш-значення. при
Quisquater-Girault
Ця схема, вперше запропонована в [1279], генерує хеш-значення, в два рази більше довжини блоку. Її швидкість хешування дорівнює 1. Вона використовує два хеш-значення, G, і Я "і хешірует разом два бл
Тандемна (Tandem) і одночасна (Abreast) схеми Davies-Meyer
Інший спосіб обійти обмеження, властиві блоковим шифрів з 64-бітовим ключем, використовує алг о-ритм, подібний IDEA (див. Розділ 13.9), з 64-бітовим блоком і 128-бітовим ключем. Наступні дві схеми
MDC-2 u MDC-4
MDC-2 і MDC-4 розроблені в IBM [1081, 1079]. В даний час вивчається питання використання MDC-2, іноді званої Meyer-Schilling, як стандарт ANSI і ISO [61, 765], цей варіант був
Хеш-функція AR
Хеш-функція AR була розроблена Algorithmic Research, Ltd. і потім поширена ISO тільки для ін-формації [767]. Її базова структура є варіантом використовуваного блочного шифру (DES в упом
Хеш-функція ГОСТ
Ця хеш-функція з'явилася вУкаіни і визначена в стандарті ГОСТ Р 34.11.94 [657]. У ній використовується блоковий алгоритм ГОСТ (див. Розділ 14.1), хоча теоретично може використовуватися будь-який блоковий а
СВС-МАС
Найпростіший спосіб створити незалежну від ключа односпрямований хеш-функцію - шифрування повідомлення блоковим алгоритмом в режимах СВС або CFB. Хеш-значенням є останній шифрований блок, за-шифр
Алгоритм перевірки справжності повідомлення (Message Authenticator Algorithm, MAA)
Цей алгоритм є стандартом ISO [760]. Він видає 32-бітове хеш-значення і був спроектований для мейнфреймів з швидкими інструкціями множення [428]. v = v <« 1 e
методи Джунемана
Цей MAC також називають квадратичним конгруентним кодом виявлення маніпуляції (quadratic con-graential manipulation detection code, QCMDC) [792, 789]. Спочатку розділимо повідомлення на від-бітові бл
RIPE-MAC
RIPE-MAC був винайдений Бартом Пренелом [тисяча двісті шістьдесят дві] і використаний в проекті RIPE [1305] (див. Розділ 18.8). Він заснований на ISO 9797 [763] і використовує DES як функції блочного шифрування. існує
IBC-хеш
IBC-хеш - це ще один MAC, який використовується в проекті RIPE [1305] (див. Розділ 18.8). Він цікавий тому, що його безпечність доведена, ймовірність успішного розкриття може бути оцінена кількісно
Односпрямована хеш-функція MAC
Як MAC може бути використана і односпрямована хеш-функція [одна тисяча п'ятсот тридцять сім]. Нехай Аліса і Боб ис-товують загальний ключ К, і Аліса хоче відправити Бобу MAC повідомлення М. Аліса об'єднуються
Безпека алгоритмів з відкритими ключами
Так як у криптоаналитика є доступ до відкритого ключа, він завжди може вибрати для шифрування будь-яке повідомлення. Це означає, що криптоаналитик при заданому C = EKЦP) мож
Створення відкритого ключа із закритого
Розглянемо роботу алгоритму, не заглиблюючись в теорію чисел. щоб отримати нормальну послідовність рюкзака, візьмемо сверхвозрастающую послідовність рюкзака, наприклад,,
шифрування
Для шифрування повідомлення спочатку розбивається на блоки, рівні за довжиною числу елементів последов а-ності рюкзака. Потім, вважаючи, що одиниця вказує на присутність члена послідовності, а
дешифрування
Законний одержувач даного повідомлення знає закритий ключ: оригінальну сверхвозрастающую поїв е-довність, а також значення я і від, використані для перетворення її в нормальну послідовник
практичні реалізації
Для послідовності з шести елементів неважко вирішити задачу рюкзака, навіть якщо послідовність ь-ність не є сверхвозрастающей. Реальні рюкзаки повинні містити не менше 250 елементів. дл
Безпека методу рюкзака
Зламали криптосистему, засновану на проблемі рюкзака, не мільйон машин, а пара криптографов. Сну-чала був розкритий єдиний біт відкритого тексту [725]. Потім Шамір показав, що в певних
швидкість RSA
Апаратно RSA приблизно в 1000 разів повільніше DES. Швидкість роботи найшвидшої НВІС-реалізації RSA з 512-бітовим модулем - 64 кілобита в секунду [258]. Існують також мікросхеми, які вико-
Розтин з обраним шіфротекста проти RSA
Деякі розтину працюють проти реалізацій RSA. Вони розкривають не саме базовий алгоритм, а над-строєний над ним протокол. Важливо розуміти, що саме по собі використання RSA не забезпечує безпечного
Розтин загального модуля RSA
При реалізації RSA можна спробувати роздати всім користувачам однаковий модуль я, але кожному свої значення показників ступеня е і d. На жаль, це не працює. Найбільш очевидна проб
Розтин малого показника шифрування RSA
Шифрування і перевірка підпису RSA виконується швидше, якщо для е використовується невелике значення, але це також може бути небезпечним [704]. Якщо е (е + 1) / 2 лінійно
отримані уроки
Джудіт Мур (Judith Moore) на підставі перерахованих розтинів наводить такі обмеження RSA [1114, 1115]: - Знання однієї пари показників шифрування / дешифрування для даного модуля
Розтин шифрування і підпису з використанням RSA
Має сенс підписувати повідомлення перед шифруванням (див. Розділ 2.7), але на практиці ніхто не виконують-няет цього. Для RSA можна розкрити протоколи, шифрувальні повідомлення до його підписання [48].
стандарти
RSA de facto є стандартом майже по всьому світу. ISO майже, but not quite, created an RSA digital-signature standard; RSA служить інформаційним доповненням ISO 9796 [762.]. французьке
патенти
Алгоритм RSA запатентований в Сполучених Штатах [1330], але ні водної іншій країні. РКР отримала ли-ценз разом з іншими патентами в області криптографії з відкритими ключами (розділ 25.5). термін д
патенти
Алгоритм Pohlig-Hellman запатентований в США [722] і в Канаді. РКР отримала ліцензію разом з іншими патентами в області криптографії з відкритими ключами (див. Розділ 25.5). 19.5 Rabin
шифрування EIGamal
Модифікація EIGamal дозволяє шифрувати повідомлення. Для шифрування повідомлення М спочатку вибирає-ся випадкове число до, взаємно просте ср - 1. Потім обчислюються
патенти
EIGamal незапатентованою. Але, перш ніж рухатися вперед і реалізовувати алгоритм, потрібно знати, що РКР вважає, що цей алгоритм потрапляє під дію патенту Діффі-Хеллмана [718]. Однак термін дей
Інші алгоритми, засновані на лінійних кодах, що виправляють помилки
Алгоритм Нідеррейтера (Niederreiter) [1 167] дуже близький до алгоритму Макеліс і вважає, що відкритий ключ - це випадкова матриця перевірки парності коду, що виправляє помилки. Закритим ключем слу
Бітовим показником ступеня (на SPARC II)
512 бітів 768 бітів 1024 біта Підпис 0.20 з 0.43 з 0.57 з Перевірка 0.35 з 0.80 з 1.27 з Практичні реалізації DSA часто можна прискорити за допомогою попередніх вичисл
Генерація простих чисел DSA
Ленстра і Хабер вказали, що зламати деякі модулі набагато легше, ніж інші [950]. Якщо хто-небудь змусить користувачів мережі використовувати один з таких слабких модулів, то їх підписи буде ле
розтину до
Для кожного підпису потрібно нове значення до, яке повинно вибиратися випадковим чином. Якщо Єва уз-нает до, яке Аліса використовувала для підпису повідомлення, може бути скористатися
Небезпеки загального модуля
Хоча DSS не визначає застосування користувачами загального модуля, різні реалізації можуть восполь ь-тися такою можливістю. Наприклад, Податкове управління розглядає використання DSS для е
дискретних логарифмів
Рівняння підписи рівняння перевірки (1) r'k = s + mx mod q (2) r'k = m + sx mod q (3) sk = r '+ mx mod q / -gy-mod p
ONG-SCHNORR-SHAMIR
Ця схема підпису використовує многочлени по модулю п [1219, 1220]. Вибирається велике ціле число (знати розкладання п на множники не обов'язково). Потім вибирається випадкове число
Безпека ESIGN
Коли цей алгоритм був вперше запропонований, до було вибрано рівним 2 [1215]. Така схема швидко була зламана Ерні Брікеллом (Ernie Brickell) і Джоном ДеЛаурентісом [261], які распространи
патенти
ESICN запатентований в Сполучених Штатах [1208], Канаді, Англії, Франції, Німеччини та Італії. Той, хто хоче отримати ліцензію на алгоритм, повинен звернутися в Відділ інтелектуальної власності