Сьогодні про інші шифри, хоч і належать до криптосистемам з секретним ключем. Називаються іноді поточними, іноді потоковими.
Що таке потоковий шифр? Якщо блоковий шифр оперує великим об'ємом інформації і шифрує цілий блок, то потоковий шифр оперує битами. Дуже рідко він оперує байтами.
Потоковий шифр є розвитком шифру Вернона, який був придуманий в 1917 році, ще до появи криптографії як науки. Особливість цього шифру - про нього можна довести, що при дотриманні деяких умов він абсолютно стійкий.
Він працює так - у вас є потік відкритого тектсах і потік ключа, потоки складаються побитово по модулю два і отримуємо потік шифротекста.
Було доведено такою людиною як Клод Шеннон, який перший почав вивчати шифри і математизированной всю цю теорію. І він довів, що якщо в шифрі Вернона використовується ключ, рівний по довжині відкритого тексту і ключ вибирається _абсолютно_ випадково, і ключ використовується рівно один раз, то він є абсолютно стійким.
Але це тільки модель, як Машина Тьюринга.
Але в реальних системах не буває нічого абсолютно випадкового. Якщо вибирати ключ рівний довжині відкритого тексту ще можна, то ось вибрати абсолютно випадково важко.
І хотілося б мати детермінований алгоритм, який породжує ключову гаму.
Виникає питання, а що ж нам робити? Як би нам модифікувати шифр Вернона, що б отримати практичну криптосистему.
Будь-класичний потоковий шифр преддставляет з себе ключовий потік. Далі цей ключовий потік складається по модулю два з відкритим текстом і виходить шифрований текст.
Найголовніший елемент - якась функція, яка вираюативает нам ключову гаму. Вона сама залежить від якогось ключа, який подається на вхід.
Є ящик, кладете туди ключ, тиснете кнопку, він видає один біт. Ці біти ви використовуєте як гаму.
Потоковий шифр виробляє тільки гамму, ніяких хитрих операцій з відкритим текстом, як в блокових шифри немає.
У потокових шифрів є невеликий недолік - сам по собі ніяк не захищає від навмисних спотворень. Потокові шифри забезпечують тільки конфіденційність. У блокових же режимах є режими в які підтримують захист від спотворень.
Регістр зсуву зі зворотним зв'язком. Вироблення нового біта як функції від н попередніх. Дуже часто використовують звичайну лінійну функцію. істо теоретично можете використовувати нелінійну. Однак у більшості випадків використовують лінійну.
Регістри зсуву, у яких функція зворотного зв'язку є лінійною називаються регістрами зсуву з лінійної зворотним зв'язком.
Якщо говорити взагалі про регістрах зсуву. Будь-регістр зсуву з лінійним зворотним зв'язком може бути заданий не тільки як коеефіценти лінійної функції, а як поліном.
Старша ступінь полінома дорівнює довжині регістразсуву.
Раз регістр зсуву вираюативает нам ключову гаму, може так статися, що в силу кінцівки нашого регістра, послідовність буде періодичною.
А раптом послідовність повториться через мало тактів? Тоді наш ключ буде дуже поганий, ми отримаємо невипадково послідовність.
Нам би хотілося мати такий регістр зсуву, щоб період цієї послідовності був максимальний. І тут виникає питання - а як зробити так, щоб період був максимальний? Як вообзе визначити період регістразсуву?
Чтобф відповісти на питання про максимальне, звернемося до станів регістра. З якого моменту гамма починає повторюватися? Коли ви потрапите в сотояние, в яке вже потрапляли. Максимальний період вашої послідовності може бути якийсь? 2 ^ (lдліна регістра) - 1.
Подивимося на приклад s0 * s1 + s2. Характеристичний многочлен 1 + x 2 + x 3 000 -> 000
У разі нелінійного рістра період мало передбачуваний.
Зате в случе лінійного є припущення - для того, щоб він мав максимальний період, його характеристичний многочлен повинен бути не приводимо над гф2.
Насправді, непрівоімості многочленів недостатньо.
Треба, щоб многочлен був примітивний.
Доведіть, що 1 + x + x ^ 4 не матиме максимального періоду.
Чтоже таке прімтівний поліном?
Спочатку потрібно дати таке визначення - задати порядок многочлена. Порядок многочлена - таке мінімальнео число н, що многчлен x ^ n - 1 ділиться на F (x).
Ми не вдаємося в нетрі кінцеві полів, але там цей порядок - досить важлива характеристика.
Многочлен називається примітивним, якщо протягом п'яти років його порядок дорівнює 2 ^ n - 1.
Можна довести, що будь-який приводиться многочлен ділить многочлен.
a + b mod p a * b mod p
І нехай у нього не буде коренів в цьому полі.
Поліном називається примітивним, якщо через ось це альфа можна висловити все Сота елементи поля.
Якщо ви візьмете поліном, що не примітивний, то все не вишикується в ланцюжок.
Взяли регістр зсуву, забабахати нулики і одинички, взяли прімтівний многочлен, він поставив правила функціонування.
Можна довести, що послідовність утворюється на одному регістрі зсуву майже випадкова.
Якщо ви візьмете н = 256, то період буде 2 ^ 256. Тобто пі маленької довжині регістра можна отримати випадкову послідовність нереальною довжини. Але тут є підступ.
Поліном, фактично, є ключем.
Все було б добре, якби два еловек нам не нагадили, і не придумали адлгорітм, який би по невеликому шматку последовтельность восстаналівал регістр. Звали їх Берлекемпа і Мессі.
Він класика, використовується багато де.
Демонстрація роботи алгоритму берлекампа Мессі.
Нарешті ми прийшли до найцікавішого.
Ідея використовувати регістри зі зворотним зв'язком провалилася. Що робити? Як жити далі?
У чому проблема в нашому реєстрі? Він майже всюди лине. Треба ввести нелінійність.
Давайте фделаем фільтр. Будемо видавати не саму гаму, а якусь нелінійну функцію від гами. Інша ідея - використовувати інші види нелінійності
У нас є улюблений лінійний регістр зсуву, але кольорів не вибрасіивается з лівого вічка, а є якоюсь нелінійної функцією від стану. Тобто, з состоний в стан переходимо лінійно, але гаму вважаємо нелінійної функцією від стану. Є розвиток цієї ідеї.
Є нелінійна функція від ен змінних. І кожна з змінних продукується окремим регістром зсуву.
Можна довести, що перший варіант зводиться до другого.
Отже, коли був просто регістр, послідовність була майже випадковою. Пустили через фільтр. Хто сказав, що послідовність буде випадковою?
Яке може бути максимальна відстань?
max = ρ (f, A) Розглянемо перетворення Молош Адамара - розкладання по базису ортогональних функцій.
Максимум відстані 2 n - 2 (n / 2) якщо н парне. Функції, на яких досягається максимум, називаються бент-функціями.
Отже, ми з'ясували, що функція повинна бути бент-функцією, повинна бути врівноваженою, більш того, повинна бути абсолютно врівноваженою.
Давайте в функції замість змінних підставимо константу. Якщо нова функція буде неврівноважена, то ви можете провести атаку, підставивши на потрібні змінні нулі і намагаючись витягнути корелляции.
Наприклад, якщо у вигляді фільтрує функції така x * y \ xor x * z \ xor z. z = 1 =>! xy
f (x, y, z) = z з ймовірністю 3/4. І з тієї ж веротяностью дорівнює Іксу.
А це означає, що ви можете перебрати значення тільки ікси. І у вас є детектор вгадування - веротяность 3/4 збігів. Так само можете відновити реєстр z. Комбінуванням потім можна відновити ігрек.
Таки атаки називаються кореляційні. Складність там дуже сильно падає. Якщо потужність регістрів були Н1 Н2 Н3, то повним перебором буде 2 (n 1 + n 2 + n 3). то тут перебір буде 2 n 1 + 2 n 2 + 2 n 3
Погані шифри можна псомтреть зайшовши на https: \\ mail.ru
Якщо користуватися хромом, то воно показує замочок, і там в описі сказано, що з'єднання захищено rc4 128. Шифр rc4 є потоковим, егонедавно ломанулись і сейас він є небезпечним.