Методи сучасної криптографії

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Методи сучасної криптографії:Іспит

Зміст

1 Лекція 1
2 Лекція від 21.09.2009
- 2.1 Симетричні шифри
3 Лекція n-1

Лекція 1

Вимоги до безпеки інформації:

конфіденційність
цілісність
аутентифікація
контроль доступу
мітка часу
підпис
неспростовність (неможливість відмови від дії)

Криптографія

Вивчення математичних технік, пов'язаних із такими аспектами безпеки інформації:

конфінденційність
цілісність
аутентифікація об'єктів та походження даних
невідмовність від дій
не має бути прив'язки до носія інформації.

Характеристики алгоритмів:

1. Рівень безпеки

2. Функціональність

3. Методи використання

4. Продуктивність

5. Легкість реалізації

DES використовується для шифрування даних, генератор випадкових числел, хеш-функція.

‎

Функції

$X \xrightarrow{f} Y$

$X \to Y$

$y \in Y, x \in X: f(x)=y$ , x - прообраз

$Im(f) = \{ y \in Y | \exists x \in X: f(x)=y \}$

$f (x) = x 2 m o d 1050 + 1$

Визнач. f - ін'єкція, якщо x₁ ≠ x₂ ->

f(x₁) ≠ f(x₂)

Визнач. f - сюр'єкція, якщо Im(f)=Y

Визнач. f - бієкція, якщо вона є сюр'єкцією і ін'єкцією

f - бієкція, $X \xrightarrow{f} Y$

$f(x) = y \in Y$

$g(y): y \to x$

$g (f (x)) = x$

$f - 1$

Визнач. Перестановка - $f: S \to S$

3 не є дільником p-1

$x= \{ 1, \dots , p-1 \}$ p - просте число

$f (x) = x 3 m o d p$ - перестановка

Визнач. Важкооборотна функція

$f: X \to Y, f(x)$ обчислити "легко", існує поліноміальний

алгоритм, але для "суттєво усіх" $y \in Im(f)$ жоден ефективний

алгоритм не в змозі знайти $x': f (x') = y$

$n \forall g P \{ f(g(y))=x \} < \frac{1}{n}$

Визнач. Важкооборотна функція з скеретом

f(x) обчислити "легко"

$f - 1 (x)$ , якщо відома додаткова інформація (секрет), то

$\forall y \in Im(f)$ існує легкий алгоритм обчислення

$f - 1 (y)$

$f (x) = a x m o d p$

2 ¹¹: 2 -> 2² -> 2⁴ -> 2⁸, (11=8+2+1), 2¹¹=2⁸*2²*2¹

$l o g 2 (x)$ операцій (2 -> 2² -> 2⁴ -> 2⁸)

1) $a^{-1} (x) = x^{1} : a^{x^{1}} \equiv a^{x} \pmod{p}$ - дискретне логарифмування

2) Розклад числа на прості множники $n=p \cdot q$ : p = 48611, q = 53993, n = 2624653723

$f (x) = x 3 m o d n$

$\begin{cases} x \equiv a \pmod p \\ x = b \pmod q \end{cases}$

$\exists ! x, x \in [ 0; q-1 ]$

$y^3 \equiv a mod p$

$y^3 \equiv a mod q$

A - скінченний алфавіт

{0; 1}, {0; 1, ..., 255}, {0, ..., 28}

M -простір повідомлень складається з рядків символів з алфавіту A

Елемент $m \in M$ -відкритий текст

C - простір криптотекстів, $c \in C$ - криптотекст

K - простір ключів

$\forall e \in K$ бієкція із M в C

E_e - функція шифрування

$\forall d \in K, D_d : C \to M$ - дешифруюча функція

$\{ E_e, e \in K \} \to \{D_d, d \in K \}$

$e \in K \exists ! d \in K: D_d = E^{-1}_e$

$\forall m D_d(E_e(m))=m$

(e,d) - ключова пара

$\{ M, C, K, \{ E_e, e \in K \}, \{D_d \in K \} \}$ -криптосистема, весь набір є відомим

секретною э лише пара ключів (e,d)

Захищений канал - не можна читати, модифікувати, видаляти інформацію, що йде по ньому.

Незахищений канал - є можливість усіх або деяких з цих дій.

1. Безумовна безпека

Довжина k ≥ довжини відкритого тексту

m₁, m₂, ..., m_n $\in \{ 0, 1, ..., p-1 \}$

k₁, k₂, ..., k_n

c₁, c₂, ..., c_n

c_i = m_i + k_i mod p

2. Теоретико-складносна безпека (ідеалізація)

O(n²⁰)

3. Безпека, яку можна довести

Процедура: Шифрований Текст -> Відкритий Текст є еквівалентна якійсь складній задачі

4. Обчислювана безпека

Атаки на криптосистеми

1. Атака за ШТ

2. Атака за відомим ВТ (DES - 2⁵³)

3. Атака за вибраним ВТ (DES - 2⁴⁸)

4. Атака адаптивним вибором ВТ

5. Атака з вибраним ШТ

Лекція від 21.09.2009

Симетричні шифри

1.Шифри заміни

Деяке повідомлення m₁m₂...m_n

f(m_i)=c_i, f:A->A

2.Шифр перестановки

m₁m₂...m_km_k+1...m_n

(m₁m₂...m_km_k+1) ... m_n

2.Аффіний шифр

0...m-1 - літери нашого алфавіту

f(m_i)=(a m_i + b) mod m

Розкодування:

(e_i - b)a^-1 mod m, a та m взаємнопрості

Відкритий текст (ВТ) -> Шифрований текст (ШТ)

2ⁿ -> 2ⁿ, n-біт

1. Взаємно однозначне відображення

2. Компроміс між швидкістю та ефективністю

3. Розсіювання (За Шенноном)

4. Перемішування (За Шенноном)

Розсіювання - зміна хоча б одного біта повідомлення на вході має призводити до зміни принаймні половини бітів вихідного повідомлення.

Перемішування - кожен біт шифрованого тексту має залежати від кожного біту Відкритого тексту та ключа.

S - деяке лінійне перетворення якщо $S(a \oplus b)=S_a \oplus S_b$ , в іншому разі воно не лінійне

Приклади лінійних перетворень

1. mod 2

2. перестановка бітів

3. циклічний зсув

4. множення двійкових векторів на невироджену матрицю

Нелінійні перетворення

1. довільна заміна за таблицею

2. додавання двійкових векторів за модулем 2ⁿ

3. множення за mod 2ⁿ+1

4. оперований зсув x << y

5. обчислення оберненого елемента в скынченному полі

5. високочастотний ступінь нелінійності

6. кореляційний імунітет

P(m & 0010₂)= a ≠ 1/2

P(E_k(m) & 00100₂)= 1/2

7. відсутність особливостей шифрування

E_k(m)=m, повернули те ж повідомлення
f_k(m)=k, повернули ключ

8. ітеративність

Алгоритм Rijndaell AES-2002 FIP-197

Властивості

1. блочний шифр

2. 3 блоки довжинами 128, 192, 256

3. 3 ключі 128, 192, 256

a₀₀ a₁₀ a₀₁ a₁₁ a₀₂ a₁₂ a₀₃ a₁₃

N_b=4, 6, 8 - кількість стовпчиків у блоці даних N_k=4, 6, 8 - кількість стовпчиків у блоці ключів

1. Byte sub

2. Shift now

3. Fix column

4. add round key

5. XOR (key)

[023, 024, 025].jpg

Лекція n-1

Хеш-функція h:

умови-Властивості:

1) Компресія, тобто h відображає вхід x довільної довжини у вихід Y фіксованої довжини

2) Ефестивність обчислення:

- хеш функція обчислюється швидше ніж m^e

Для криптографії:

підпис повідомлення: m-> h(m)->SIGN(h(m))

вимога

а) однобічність - "стійкість прообразу"

якщо відомо Y - якийсь хеш, то має бути обчислювально нереально знайти таке повідомлення X, хеш від якого дорівнює Y. x: h(x)=y

б) стійкість другого прообразу. Нехай відома пара: y=h(x). Має бути нереально знайти другий прообраз x'!=x: h(x)=h(x')

в) стійкість до колізії. - Має бути нереальним знайти такі повідомлення, хеш яких збігається: x,x': h(x)=h(x')

2^(m/2) ≥ 2^80 ≥ 160

Типи функцій:

а) х.ф-ції без ключа

- 1. потрібна для перевірки цілісності,

- 2. генератор псевдовипадкових бітів: h(1), h(2)... має кращі властивості від rand(2)...

- 3. генерація ключів: k->h(k)->h(h(k)), приклад - POS - термінал

- 4. зберігання паролів на сайтах (сіль, пассворд)

Перевірка цілісності - MDC (message detection codes)

б) з ключем (Mac - message authentification codes)

Стандартні хеш функції та їх параметри:

MD5 (128 біт) - вихідний блок - використовується на цілісність, а не шифрування

SHA-1 (secure hash algorithm ) - блоки по 512 біт (вхід), вихід - 160 біт

SHA-256

SHA-384

SHA-512

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

вимоги:

а) незмінність документу

б) ідентифікувати особу, що підписала документ

в) невідмовність

З допомогою системи RSA:

дві особи - Аліса та Боб.

Для ідентифікації використаємо закритий ключ

(E_A, D_A)
(E_Bob, D_Bob)

Аліса обчислює C=E_Bob(D_A(M)) E_Bob() - Шифрування відкритим ключем боба

Боб дешифрує повідомлення: 1. D_Bob(C) 2.M=E_A(D_Bob(C))

Потрібно мати три об'єкти:

- Ймовірніний алгоритм генерування ключів

A: K_A - open key, K_A` - таємний ключ

- SiGN: S=SiGN(M,K_A`)

- функція перевірки підпису CHECK: CHECK(K_A, M,S)=1 -> підпис вірний

умова: CHECK(K_A, M, SIGN(M,K_A`))=1

Загрози

а) екзистенційне фальшування - зловмисник може побудувати два повідомлення, підписи від яких збігаються: m',m : SIGN(m)=SIGN(m')

б) вибіркове фальшування - зловмисник може підробити підпис повідомлення за власним вибором.

в) універсальне фальшування

г) повний злам секретного ключа

Система цифрового підпису з допомогою системи Ель-Гамаля

Потрібно зробити дешифрування з допомогою секретного ключа

Генерування ключів:

p - просте, g: 1<g<p-1, в ідеалі - первісний корінь

a- випадкове, 1<a<p-1. h=g^a mod p

Відкритий ключ: (p,g,h) Закритий ключ: a

Підписування:

- вибрати випадкове число r \in Z_{p=-1}^*

- обчислити s_1=g^r mod p

- обчислити r'=r^-1 mod (p-1)

- обчислити s_2=(M-a*s-1) r' mod (p-1)

(s1,s2)-підпис

Перевірка підпису:

g^M ?= h^{s_1} s_1^{s_2} (mod p)

h^{s_1}s_1^{s_2}=g^{a*s_1}g^{r(M-a*s_1)r^-1}=a^{M+l(p-1)}=g^M mod p

Методи сучасної криптографії

Матеріал з USIC Wiki

Зміст

Лекція 1

Лекція від 21.09.2009

Симетричні шифри

Лекція n-1

Хеш-функція h:

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

Система цифрового підпису з допомогою системи Ель-Гамаля

Перегляди

Особисті інструменти

Навігація

Пошук

Інструменти