лекция 3. Лекция 3 Специальность 170101 Бсіт Лектор Сушко С. А

• Название: Лекция 3 Специальность 170101 Бсіт Лектор Сушко С. А
• Дата: 30.03.2022
• Размер: 459.51 Kb.
• Имя файла: лекция 3.docx
• Тип: Лекция; #429797
• страница: 1 из 4

ПРАКТИЧЕСКАЯ КРИПТОЛОГИЯ ЛЕКЦИЯ 3

Специальность: 6.170101 – Бсіт Лектор: Сушко С.А.

§1. КРИПТОГРАФИЧЕСКАЯ СТОЙКОСТЬ ШИФРОВ

Стойкость шифра – это способность шифра противостоять атакам на него. Стойким считается алгоритм, который для успешной атаки требует от противника недостижимых вычислительных ресурсов, недостижимого объёма перехваченных открытых и зашифрованных сообщений или же такого времени раскрытия, что по его истечению защищенная информация будет уже не актуальна, и т. д.
В криптографии различают три типа стойкости:

• 
  вычислительная стойкость – когда имеется потенциальная возможность вскрыть шифр, но при выбранных в шифры параметрах и ключах на современном этапе розвития криптоанализа у противника не хватит вычислительных ресурсов и времени для вскрытия. Если алгоритм вскрытия шифра на современных мощных компьютерах должен выполнить
  

 2⁸⁰ операций, то шифр называют вычислительно стойким. Никакой реальный шифр нельзя обоснованно считать вычислительно защищенным, поскольку мы не знаем, как доказать оптимальность найденного метода взлома. Не являются вычислительно стойкими: шифры сдвига, замены, Виженера. К вычислительно стойким шифрам относятся DES, AES, RSA, шифр Эль-Гамаля (изучим позже).

• 
  информацийно-теоретическая стойкость (или абсолютную стойкость), когда криптоаналитик не может раскрыть криптосистему ни теоретически, ни практически, даже имея бесконечно большие вычислительные ресурсы. Доказательства стойкости в такой модели выводятся из теории информации;
  
• 
  доказуемая стойкость, при которой доказательство стойкости криптосистеми сводят к решению определенной трудно решаемой математической проблемы, положенной в основу алгоритму. Например, криптосистема RSA стойка, если модуль алгоритму n нельзя факторизовать.
  

Переходим к изучению информационно-теоретической стойкости шифров.

§2. ВЕРОЯТНОСТНАЯ МОДЕЛЬ ШИФРА ПО ШЕННОНУ

Для алгебраическоймоделишифранадо задать:

1. 
   X– пространство открытых текстов;
   

2. 
   Y– пространство шифротекстов;
   
3. 
   K– пространство ключей;
   
4. 
   функцию зашифрования y E(x, k), переводящую открытый
   

текст xна ключе шифрования kв шифротекст y;

5. 
   функцию расшифрования
   

x  D( y, k) .

Тройка множеств

X, K,Yс введенными функциями называется

шифромпоШеннону, если каждый шифротекст есть результат

шифрования одного из открытых текстов (т.е. функция

y E_k(x, k)

сюрьективна), а разным открытым текстам отвечают разные

шифротексты (т.е. функция y E(x, k) инъективна).

Пусть X {x₁, x₂ ,..., x_n}. Априорнаявероятностьоткрытого

текста– это вероятность p(x)  0

выбора открытого текста для

шифрования, вычисленная противником до перехвата шифротекста.

Вероятности

p₁, p₂ ,..., p_n

текстов задают распределение вероятностей

P( X) на множестве Xоткрытых текстов. Апостериорная

вероятностьоткрытоготекставычисляется противником после перехвата шифротексты. Аналогично выводится априорная

вероятность p(k) выбора ключа kи распределение вероятностей

P(K) на множестве Kключей.

Принимается:

• 
  выбор ключа не зависит от выбора открытого текста;
  
• 
  ключи выбираются независимо друг от друга, т.е.
  

p(k) 

¹ , де

K– количество всех ключей.

Вероятностноймодельюшифраназывается его алгебраическая модель, дополненная известными независимыми

распределениями вероятностей P( X) и P(K) .

Эти априорные распределения с помощью функции

y E_k(x, k)

порождают безусловноераспределение

P(Y)  { p_{кр.( y)}}

вероятностейшифротекстов, где вероятность появления шифротекста yравна

p( y)  _

E_k( x) y

^p.(x)  p.(k)

(1)

По известным распределениям вероятностей открытых текстов и ключей и перехваченном шифротексте криптоаналитик может найти:

1. 
   p( y/ x)
   

– условную вероятность возникновения шифротекста

y, если для зашифрования выбрано сообщение x. Она равна сумме

вероятностей всех тех ключей, которые переводят текст xв шифротекст

y:

p( y/ x) 

_ p

kK yE_k( x)

_(k) ; (2)

2. 
   p( y/ k) – условную вероятность шифротекста yв случае
   

выбора ключа k, которая равна сумме вероятностей всех тех открытых текстов, которые на ключе kперейдут в шифротекст y:

p( y/ k)

 _ p

xX yE_k( x)

_(x) . (3)

3. 
   p(x/ y) – условную апостериорную вероятность текста x, если
   

перехвачен шифротекст y, которая, очевидно, белее всего интересует криптоаналитика, вскрывающего шифр. Она находится из определения условной вероятности:

p(x/ y) 

p(x)  p( y/ x)

. (4)

p( y)

4. 
   p(k/ y) – условную апостериорную вероятность ключа kпри
   

условии, что перехвачен шифротекст y:

p(k/ y) 

p(k)  p( y/ k)

. (5)

p( y)

Пример. Заданы распределения вероятностей открытых текстов и ключей:

Распределение вероятностей открытых текстов
текст	x1	x2	x3	x4
вероятность	p(x1)  0, 24	p(x2 )  0,16	p(x3)  0, 28	p(x4 )  0,32

Распределение вероятностей ключей
ключ	k1	k2	k3
вероятность	p(k1)  0,3	p(k2 )  0,3	p(k3)  0, 4

Пространство шифротекстов – множество Функция зашифрования задана матрицей

Y{y₁; y₂ ; y₃; y₄}.

	x1	x2	x3	x4
k1	y2	y4	y3	y1
k2 k3	y2 y4	y1 y2	y4 y1	y3 y3.

Найти:

а) распределение вероятностей шифротекстов;

б) условные вероятности шифротекста yпри условии, что

выбрано сообщение x;

в) условные апостериорные вероятности текста x, если был перехвачен шифротекст y.

Р е ш е н и е. а). вероятность того, что криптограмма

y₁ получена

при шифровании открытого текста

x₄ на ключе

k₁ или текста

x₂ на

ключе

k₂ или текста

x₃ на ключе

k₃, вычисляем по формуле (1):

p( y₁) 

p(x₄ ) p(k₁) 

p(x₂ ) pk₂) 

p(x₃) p(k₃)  0, 256.

Аналогично найдем

p( y₂ ) 

p( y₃ ) 

p( y₄ ) 

p(x₁) p(k₁) 

p(x₃) p(k₁) 

p(x₂ ) p(k₁) 

p(x₁) p(k₂) 

p(x₄ ) p(k₂ ) 

p(x₃) p(k₂) 

p(x₂) p(k₃)  0, 208;