МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» З В І Т до лабораторної роботи №3 з навчальної дисципліни: «Криптографія і стеганографія»  Львів – 2013 МЕТА РОБОТИ - Ознайомитися з основними алгоритмами побудови генераторів псевдовипадкових послідовностей та лінійними регістрами зсуву з зворотнім зв’язком. Короткі теоретичні відомості Потокові шифри Потоковий шифр - група симетричних шифрів, які шифрують кожен символ  відкритого тексту незалежно від інших символів. Синхронні потокові шифри В синхронному потоковому шифрі потік псевдовипадкових цифр породжується незалежно від відкритого тексту і шифротексту повідомлення, і тоді поєднується з відкритим текстом (для шифрування) або шифротекстом (для розшифрування). Випадкові числа. Генератори випадкових чисел Генератор послідовності псевдовипадковий, якщо він виглядає випадковим, тобто проходить усі статистичні тести випадковості. Для криптографічних застосувань статистичної випадковості недостатньо, хоча це і необхідна властивість. Послідовність називається криптографічно надійною псевдовипадковою послідовністю (КНПСП), якщо вона непередбачувана, тобто обчислювально нездійсненно передбачити наступний біт, маючи повне знання алгоритму (чи апаратури) і усіх попередніх бітів потоку. КНПСП теж схильні до криптоаналізу - як будь-який алгоритм шифрування. Генератор послідовності називається випадковим, якщо він не може бути достовірно відтворений, тобто двічі запускаючи генератор з абсолютно однаковими початковими даними (принаймні, на межі людських можливостей), ми отримаємо випадкові різні послідовності. Генератори псевдовипадкових послідовностей У більшості алгоритмів шифрування, особливо потокових шифрах, використовуються генератори ключової послідовності. Генератор ключової послідовності видає потік бітів, який виглядає випадковими, але насправді є детермінованим і може бути в точності відтворений на стороні одержувача. Чим більше генерований потік схожий на випадковий, тим більше часу буде потрібно криптоаналітику для злому шифру. Регістр Фібоначчі. Загальний вид рекурентного співвідношення, що визначає генератор Фібоначчі, задається рівнянням

,
де
- параметри генератора; елемент
представляє собою двійковий k-вектор і дія виконується покомпонентно.
Рис.4. Регістр зсуву з лінійним зворотнім зв’язком Фібоначчі Приклад: рядок (32, 7, 5, 3, 2, 1, 0) означає, що якщо взяти 32-бітовий регістр зсуву і генерувати нові біти XOR-складанням тридцять другого, сьомого, п'ятого, третього, другого і першого бітів, то результуюча послідовність матиме максимальний період - вона пройде через 232 - 1 значень до того, як почне повторюватися. РЗЛЗЗ в програмній реалізації працюють досить повільно, і швидкість можна збільшити застосуванням для програмування мови Асемблер замість Сі. Ще одне можливе рішення - запускати 16 РЗЛЗЗ (або 32, залежно від розміру слова в комп'ютері) у паралельному режимі. Така схема використовує масив слів, так що кожна бітова комірка регістру представлена окремим РЗЛЗЗ. При умові, що всі вони мають один і той же поліном зворотного зв'язку, така схема працює досить швидко. У загальному випадку найкращий спосіб оновлювати стани регістрів зсуву - це множити поточний стан на відповідні двійкові матриці. Регістр Галуа На відміну від регістра Фібоначчі, де зворотний зв'язок є функцією від всіх комірок в регістрі, а результат поміщається в саму ліву комірку, зворотний зв'язок в регістрі Галуа потенційно застосований до кожної комірки регістра, хоча є функцією тільки від самої правої комірки. У РЗЛЗЗ Галуа можна модифікувати схему зворотного зв'язку перетворивши регістр в так звану "конфігурацію Галуа". Не можна сказати, що генератор, що вийшов в результаті, стає кращим з криптографічної точки зору, але він теж може мати максимальний період і простий в програмній реалізації. У цій схемі замість використання біт з точок знімання для генерації нового найлівішого біта, кожен біт з точки зні...