Основи криптографії
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
мовування всіх одиниць двійкового коду, або додати значення кодів всіх літер рядка, що обробляється (т.зв. контрольна сума) і т.д. Головне полягає в тому, що значення хеш-функції повинно залежати від усього вхідного рядка, щоби не можна було (в крайньому разі було б дуже важко) підібрати два різних вхідних рядки з однаковим значенням хеш-функції. Якщо таке трапляється, то кажуть що виникла колізія. Ми будемо користуватися найпростішою хеш-функцією, яка дуже недосконала і може викликати значні колізії. Однак, вона дуже проста і не потребує витрат машинного часу, а також складного програмування. Ця функція просто сумує всі значення символів за табл. 1 за модулем 33:
H(M)= (3)
До отриманого таким чином числа застосовують алгоритм прикладу 3, отримуючи, таким чином, зашифрований цифровий підпис. Отримувач, маючи повідомлення і цифровий підпис, розшифровує текст повідомлення, знаходить хеш-функцію від нього за формулою (3), розшифровує цифровий підпис, і порівнює отримані значення. Якщо вони однакові, повідомлення і цифровий підпис є істинними.
Проблема адміністрування криптографічними ключами вважається основним недоліком симетричних криптоалгоритмів. Цю проблему можна вирішити за допомогою асиметричної криптографії, тобто взагалі не використовувати симетричні криптоалгоритми. Однак такий підхід вважають нераціональним, оскільки асиметричні алгоритми працюють значно повільніше за симетричні і не можуть використовуватися у ряді важливих криптографічних застосувань. Іншим способом розповсюдження ключів є специфічні алгоритми, розроблені спеціально для таких застосувань. Одним з таких алгоритмів відкритого розповсюдження ключів є алгоритм Діффі-Хеллмана. Нехай учасники інформаційного обміну, сторони А і В, домовилися використати цей алгоритм для обміну ключами. Для цього необхідно виконати наступні обчислення. Спочатку А і В обирають велике просте число р, модуль системи. Для цього числа р обирають первісний корінь а. Числа р і а відкрито передають по каналах звязку, так щоб їх мали обидві сторони.
Далі виконується наступний протокол:
- А генерує ціле велике випадкове число х і відправляє В число:
;
2) В генерує велике ціле випадкове число у і відправляє А число:
;
3) А обчислює:
4) В обчислює:
.
І k, і k дорівнюють .
Отже сторони А і В отримали один і той самий криптографічний ключ, не пересилаючи його каналами звязку. Ніхто з осіб, що прослуховують цей канал, не зможе обчислити значення ключа. Адже їм відомі тільки p, a, X, Y, а для знаходження ключа необхідно розвязати задачу дискретного логарифмування. Тому А і В мають цілком таємний ключ, який більше ніхто не знає. Вибір а і р може помітно впливати на безпеку системи. Найголовніше, це те, що р повинно бути великим, таким, щоби задача дискретного логарифмування у скінченому полі була складною обчислювальною проблемою. Можна обирати довільне а, яке є первісним коренем за модулем р; немає причин, за якими не можна було б обрати а найменшим з можливих, навіть однорозрядним. Навіть необовязково, щоби а було первісним коренем, воно повинно лише утворювати досить велику підгрупу мультиплікативної групи за модулем р. Програмний генератор двійкових послідовностей BBS (назву утворено від перших літер його авторів Ленори та Мануеля Блум та Майка Шуба, Blum-Blum-Shub) вважають одним з найсильніших програмних генераторів псевдовипадкових послідовностей. Він вважається криптографічно стійким, і може використовуватися у серйозних криптографічних застосуваннях [2].
Нехай є два простих числа, p i q, причому p?q?3 mod 4. Добуток цих чисел n=pq називається цілим числом Блума. Оберемо ще одне випадкове число, х, взаємно просте з n та обчислимо x0?x mod n. Це число вважається стартовим числом генератора. Далі можна обчислити наступні біти послідовності за формулою: xi?xi-12 mod n та si?xi mod 2. Останнє визначає, що в якості виходу генератора обирається молодший біт числа xі . Найцікавішою властивістю генератора BBS є те, що для визначення значення і-го біту зовсім необовязково знати усі попередні і-1 бітів. Для безпосереднього обчислення значення і-го біту достатньо знати p та q. Безпека цієї схеми ґрунтується на складності розкладання n на множники. Число n можна опублікувати, так що кожен зможе генерувати біти за допомогою цього генератора. Однак поки криптоаналітик не розкладе n на множники, він не зможе передбачити вихід генератора. Більше того, генератор BBS непередбачуваний як в правому, так і в лівому напрямках. Це означає, що отримавши послідовність бітів, криптоаналітик не зможе передбачити ні наступний, ні попередній біти послідовності. Причиною цього є не якійсь заплутаний механізм генерації, а математика розкладання n на множники.
Приклад:
p=19;q=23
і01234567хi10115021335812327125188Si10101110
p=q?3 mod 4
n=437
x=233
Обовязковою умовою, що накладається на зародок х, повинно бути наступне:
а) x просте; б) х не ділиться на р і на q.
Цей генератор повільний, але є спосіб його прискорити. Як вказано у [2], в якості бітів псевдовипадкової послідовності можна використовувати не один молодший біт, а log2m молодших бітів, де m довжина числа xi. Порівняна повільність цього ген?/p>