Криптографічна математика

🎯 Що таке криптографічна математика?

Криптографічна математика — це галузь математики, яка займається розробкою та аналізом математичних методів для забезпечення безпеки інформації. Вона включає в себе теорію чисел, алгебру, теорію ймовірностей, статистику та інші математичні дисципліни для створення безпечних криптографічних алгоритмів та протоколів.

🔍 Основні концепції

Симетричне шифрування: використання одного ключа

Асиметричне шифрування: використання пари ключів

Хеш-функції: односторонні функції

Цифрові підписи: аутентифікація повідомлень

Теория складності: оцінка безпеки

Теорія інформації: ентропія та безпека

🔐 Симетричне шифрування

Симетричне шифрування використовує один ключ для шифрування та розшифрування повідомлень.

📊 Принцип роботи

Симетричне шифрування:

Алгоритм симетричного шифрування складається з:

Функції шифрування: E(K, P) = C

Функції розшифрування: D(K, C) = P

Ключ K: таємний ключ

🔧 Типи симетричних алгоритмів

Блокові шифри: шифрування блоків фіксованого розміру

Потокові шифри: шифрування бітів по одному

Гібридні схеми: комбінація блокових та потокових шифрів

🎯 AES (Advanced Encryption Standard)

Алгоритм AES:

Розміри ключів: 128, 192, 256 біт

Розмір блоку: 128 біт

Кількість раундів: 10, 12, 14 відповідно

Структура: підстановка-перестановка

🔑 Асиметричне шифрування

Асиметричне шифрування використовує пару ключів: публічний для шифрування та приватний для розшифрування.

📊 Принцип роботи

Асиметричне шифрування:

Публічний ключ: K_pub (відкритий)

Приватний ключ: K_priv (таємний)

Шифрування: E(K_pub, P) = C

Розшифрування: D(K_priv, C) = P

🎯 RSA

Алгоритм RSA:

Генерація ключів: Оберіть два великі прості числа p, q Обчисліть n = p·q та φ(n) = (p-1)(q-1) Оберіть e таке, що НСД(e, φ(n)) = 1 Знайдіть d таке, що e·d ≡ 1 (mod φ(n)) Публічний ключ: (n, e), Приватний ключ: (n, d)

Оберіть два великі прості числа p, q

Обчисліть n = p·q та φ(n) = (p-1)(q-1)

Оберіть e таке, що НСД(e, φ(n)) = 1

Знайдіть d таке, що e·d ≡ 1 (mod φ(n))

Публічний ключ: (n, e), Приватний ключ: (n, d)

Шифрування: c ≡ m^e (mod n)

Розшифрування: m ≡ c^d (mod n)

🔧 Еліптичні криві (ECC)

ECC шифрування:

Крива: y² = x³ + ax + b (mod p)

Базова точка: G на кривій

Приватний ключ: ціле число d

Публічний ключ: точка Q = d·G

🔍 Хеш-функції

Хеш-функції перетворюють довільні дані у фіксованої довжини рядок бітів.

📊 Властивості хеш-функцій

Криптографічні хеш-функції:

Детерміністичність: однаковий вхід → однаковий вихід

Швидкість: швидке обчислення

Стійкість до колізій: важко знайти два входи з однаковим хешем

Односторонність: важко знайти вхід по хешу

Аваланчний ефект: малі зміни входу → великі зміни виходу

🎯 SHA (Secure Hash Algorithm)

Сімейство SHA:

SHA-1: 160 біт (застарілий)

SHA-256: 256 біт (поточний стандарт)

SHA-384: 384 біт

SHA-512: 512 біт

SHA-3: новий стандарт (Keccak)

🔧 Структура SHA-256

Алгоритм SHA-256:

Доповнення повідомлення до кратності 512 біт

Ініціалізація восьми 32-бітних змінних

Обробка блоків по 512 біт

Фінальний хеш як конкатенація змінних

✍️ Цифрові підписи

Цифрові підписи забезпечують аутентифікацію, цілісність та невідмовність повідомлень.

📊 Принцип роботи

Цифровий підпис:

Генерація підпису: Sign(K_priv, M) = S

Перевірка підпису: Verify(K_pub, M, S) = true/false

Аутентифікація: підтвердження авторства

Цілісність: перевірка незмінності

Невідмовність: неможливість відмовитися від підпису

🎯 DSA (Digital Signature Algorithm)

Алгоритм DSA:

Параметри: p, q (прості), g (генератор)

Приватний ключ: x ∈ [1, q-1]

Публічний ключ: y = g^x (mod p)

Підпис: (r, s) де r = (g^k mod p) mod q

Перевірка: r = (g^(s^(-1)·H(m)) · y^(s^(-1)·r) mod p) mod q

🔧 ECDSA

ECDSA (Elliptic Curve DSA):

Крива: еліптична крива над скінченним полем

Базова точка: G порядку n

Приватний ключ: d ∈ [1, n-1]

Публічний ключ: Q = d·G

Підпис: (r, s) з використанням операцій на кривій

🔒 Теорія безпеки

Математичне обґрунтування безпеки криптографічних систем.

📊 Моделі безпеки

Основні моделі:

Perfect Secrecy: теоретична безпека (Шеннон)

Semantic Security: практична безпека

Chosen Plaintext Attack (CPA): атака з вибраним відкритим текстом

Chosen Ciphertext Attack (CCA): атака з вибраним шифротекстом

🎯 Теорема Шеннона

Теорема Шеннона про досконасту секретність:

Система шифрування має досконасту секретність тоді і тільки тоді, коли:

Кількість можливих ключів не менша за кількість можливих повідомлень

Кожен ключ використовується з однаковою ймовірністю

Кожен ключ використовується тільки один раз

🔧 Складність обчислень

Обчислювальна складність:

Поліноміальний час (P): ефективно розв'язувані задачі

Недетермінований поліноміальний час (NP): перевіряємі задачі

Експоненціальний час (EXP): важко розв'язувані задачі

Субекспоненціальний час: проміжний клас

🔢 Теорія інформації

Математичні основи інформації та її безпеки.

📊 Ентропія Шеннона

Ентропія:

H(X) = -∑ p(x) log₂ p(x)

де p(x) — ймовірність появи символу x.

🎯 Властивості ентропії

Основні властивості:

Негативність: H(X) ≥ 0

Максимальність: H(X) ≤ log₂ n для n символів

Додавання: H(X,Y) = H(X) + H(Y|X)

Взаємна інформація: I(X;Y) = H(X) - H(X|Y)

🔧 Теорема кодування Шеннона

Теорема Шеннона:

Мінімальна середня довжина коду не може бути меншою за ентропію джерела:

L ≥ H(X)

🔐 Квантова криптографія

Застосування квантової механіки для безпечного обміну інформацією.

📊 Принципи

Квантові принципи:

Принцип невизначеності Гейзенберга: неможливість одночасно виміряти спряжених змінних

Теорема про неможливість клонування: неможливість копіювання квантового стану

Квантова заплутаність: кореляції між частинками

🎯 BB84 протокол

Протокол BB84:

Аліса відправляє квантові біти в випадкових базисах

Боб вимірює отримані біти в випадкових базисах

Сторони обмінюються інформацією про базіси

Зберігають біти, виміряні в однакових базисах

Перевіряють безпеку каналу

Генерують спільний ключ

🔗 Застосування криптографічної математики

💻 Комп'ютерна безпека

SSL/TLS: безпечний транспортний протокол

VPN: віртуальні приватні мережі

Електронна пошта: PGP, S/MIME

Файлова система: шифрування диску

📱 Мобільні технології

Бездротові мережі: WPA3, 5G

Мобільні додатки: безпечне зберігання даних

Блокчейн: криптографічні хеші

Криптовалюти: Bitcoin, Ethereum

🏛️ Урядові та корпоративні системи

Державна безпека: секретна комунікація

Банківські системи: фінансові транзакції

Медицина: захист медичних даних

Освіта: безпечні екзамени

🎓 Історичний розвиток

🏛️ Класичний період

Цезар: шифр зсуву

Віженер: поліалфавітний шифр

Енігма: німецька машина шифрування

🔄 Сучасний період

Клод Шеннон (1916-2001): теорія інформації

Діффі-Хеллман (1976): обмін ключами

RSA (1977): асиметричне шифрування

DES (1977): стандарт шифрування

AES (2001): новий стандарт

🌟 Сучасна ера

Еліптичні криві (1985): ECC

Квантова криптографія (1984): BB84

Пост-квантова криптографія: стійкість до квантових атак

Гомоморфне шифрування: обчислення на зашифрованих даних

🔮 Сучасні напрямки

🌟 Пост-квантова криптографія

Розробка алгоритмів, стійких до атак квантових комп'ютерів.

🎯 Гомоморфне шифрування

Можливість виконувати обчислення на зашифрованих даних без розшифрування.

🔄 Функціональне шифрування

Шифрування, що дозволяє обчислювати певні функції на зашифрованих даних.

🌐 Блокчейн та криптовалюти

Застосування криптографії в децентралізованих системах.

📚 Практичні вправи

Вправа 1: RSA шифрування

Зашифруйте повідомлення m = 123 за допомогою RSA з параметрами n = 143, e = 7.

Вправа 2: Хеш-функції

Обчисліть SHA-256 хеш для повідомлення "Hello, World!".

Вправа 3: Еліптичні криві

Знайдіть суму точок (2, 3) + (3, 5) на кривій y² = x³ + 7 над полем 𝔽₁₇.

Вправа 4: Ентропія

Обчисліть ентропію джерела з символами A, B, C, D з ймовірностями 0.5, 0.25, 0.125, 0.125.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Spirograph і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.