Цілком таємні шифри
Чи існує Цілком таємно шифр. Яким чином він повинен бути побудований? І які умови необхідно забезпечити? Всі ці питання привели до поняття вчинені або теоретично стійких криптосистем.
теорія інформації
К.Шеннон є засновником Теорії інформації. У своїй роботі "Математична теорія зв'язку" К. Шеннон, використовуючи статистичний підхід до визначення кількості інформації (в якому оцінка інформації визначається з точки зору міри невизначеності, що знімається при отриманні інформації), показав, що кількість інформації зручно вимірювати за допомогою ентропії.
ЕнтропіяH (X) - міра невизначеності випадкової величини X. виражається наступною формулою
.
де позначає ймовірність того, що випадкова величина X прийме значення a. Це означає, що з імовірністю X може бути описана битами інформації.
модель Шеннона
Симетричні криптосистеми використовувалися понад дві тисячі років (згадайте шифр Цезаря), однак формальне математичне опис таких систем було дано Клодом Шенноном тільки в 1949 році. Підхід Шеннона перетворив криптографію з мистецтва в науку, так як з'явилася можливість доводити захищеність інформації за допомогою шифру. Однак реалізація послідовності незалежних і рівно можливих випадкових величин виявилася непростим завданням. Крім того, обсяг ключа в скоєному шифрі збігається з обсягом повідомлення, що ускладнює виконання умови секретності ключа.
За К. Шеннону, шифрування має використовувати такі принципи:
- Розсіювання (Diffusion) - поширення впливу одного знака відкритого тексту на більш, ніж один знак шифртекста, а також поширення впливу одного елемента ключа на більш, ніж один знак шифртекста.
- Перемішування, ускладнення, заплутування (Confusion) - властивість шифрувального перетворення ускладнювати взаємозв'язку між елементами даних, що ускладнює відновлення функціональних і статистичних зв'язків між відкритим текстом, ключем і шифртекст.
Ці два загальних принципу конструювання криптосистеми - дуже загальні і неформальні. Шеннон також описав більш специфічні принципи конструювання. Перший полягає в тому, щоб звести проблему забезпечення секретності системи до однієї з відомих обчислювально складних задач. Цей принцип часто використовується при створенні криптосистем з відкритим ключем, але не використовується для криптосистем з секретним ключем. Другий принцип Шеннона полягає в тому, щоб зробити систему стійкою до всіх відомих атак, і це досі кращий з відомих принципів побудови криптосистем з секретним ключем.
В описі криптосистеми, даному Шенноном, відправник А (часто званий Алісою) хоче відправити повідомлення m одержувачу В (якого називають Бобом). Повідомлення називається відкритим текстом і береться з кінцевого набору відкритих текстів М. Звичайно, Аліса може відправити більше одного повідомлення.
Через те, що канал зв'язку не захищений (противник, званий Євою, також має доступ до каналу), Аліса застосовує алгоритм шифрування до тексту m. Результат називають шифртекст, він є елементом набору шифртекст С. Аліса передає Бобу шифртекст C. який буде перехоплений Євою. Очевидно, що функція шифрування повинна бути биективное відображенням, інакше Боб не зможе відновити відкритий текст m по шифртексту з за допомогою функції розшифрування. За формулою (c) = m.
Так як тієї ж самої криптосистемою хочуть скористатися інші люди, а Аліса і Боб не хочуть використовувати один і той же відображення протягом довгого часу з міркувань безпеки, функцію шифрування вони беруть з великого набору Е функцій биективное відображення М в С. З цієї причини функції шифрування і розшифрування мають мітку k. Ця мітка k називається ключем і береться з так званого ключового простору K. Набором Е =<|k ЄK> і описується криптосистема.
Очевидно, що Аліса і Боб повинні використовувати один і той же ключ k. Щоб встановити загальний ключ, вони використовують захищений канал, лінію зв'язку, що не прослуховується. Одним із способів вибору загального ключа є попередня домовленість, інший полягає в тому, що один з учасників відправляє ключ іншого за допомогою деякого зв'язкового. Сьогодні для цієї мети часто використовується криптографія з відкритим ключем.
Зазвичай одна і та ж криптосистема Е може використовуватися протягом довгого часу великою кількістю людей, тому потрібно допустити, що ця криптосистема відома також криптоаналітику. Конфіденційність даних повинна забезпечуватися частою зміною ключа.
Часто буває так, що М = С. в цьому випадку хотілося б, щоб пари відкритий текст-шифртекст при зашифрованими на різних ключах були постійними. В такому випадку шифртекст не давав би ніякої інформації про відкрите тексті (див. Теорію інформації).
Противник, що прослуховує канал, по якому йде передача даних, може бути двох типів:
- Пасивний (прослуховує): криптоаналитик намагається вирахувати відкритий текст m (а ще краще - ключ k) по шифртексту.
- Активний (зламує): криптоаналитик намагається активно впливати на дані, що передаються. Наприклад, намагається змінити передається шифртекст.
Щоб не дозволити противнику зрозуміти, як легітимні учасники передачі даних виробили свій загальний ключ, потрібно виконувати наступні умови:
Умова 1. Всі ключі повинні бути рівноімовірними і завжди вибиратися з ключового простору випадковим чином.
Часто припускають, що всі деталі використовуваного відправником і отримувачем криптоалгоритма відомі противнику, крім конкретного значення секретного ключа.
Умова 2 (відоме, як умова Керкхоффса). Противник знає всі деталі алгоритмів шифрування і розшифрування, крім конкретного значення секретного ключа.
Теорема 1 (К. Шеннон). Для будь-яких ε> 0 і δ> 0 можна знайти таке n. що для будь-якого n> послідовності з V розпадаються на два непересічних класу В і так, що
нехай 0 <ε <1, - произвольное малое число. Пусть все последовательности длины n расположены в порядке убывания вероятностей их появления. Как отмечалось выше, множество открытых сообщений моделируется начальным участком таких последовательностей. Обозначим через β(ε) - число наиболее вероятных последовательностей таких, что сумма их вероятностей ≥ 1-ε, а сумма вероятностей любого набора из (β(ε) - 1) этих последовательностей <1-ε. Следующая теорема показывает, что при n → ∞ множество последовательностей, составляющих в нашей модели открытый текст, не зависит от ε.
Теорема 2 (К. Шеннон) .Для будь-якого ε> 0
Підходи до оцінки стійкості шифрів
У криптографії розроблені два базові підходи в оцінці стійкості шифрів. Основи першого підходу (досконала таємність) К. Шеннон виклав у своїй роботі в 1948 р
Інший підхід до визначення стійкості бере початок в тій же роботі Шеннона і називається практичної стійкістю або сложностний підхід до стійкості.
Зауваження 1. Можливо підвищувати складність алгоритмів дешифрування, підвищуючи складність перетворення Т (х. К) = у. Однак, якщо складність обчислення Т (х. K) і (у. K) при відомому k будуть великі, то практично такий шифр важко використовувати. Тому поряд з вимогою складності рішення рівняння Т (х. K) = у при невідомому k. привертають природна вимога простоти обчислення Т (х. k) і (у. k) при відомому k.
Зауваження 2. Вимога високої складності при всіх можливих алгоритмах дешифрування неконструктивно, тому що спирається на потенційну можливість перерахування всіх можливих алгоритмів дешифрування. Практично ця вимога замінюється на реалізоване умова високої трудомісткості при всіх відомих творцям шифру методах дешифрування.
бібліографічний покажчик
Бар-Гнар Р. Танаєва В.