***** Google.Поиск по сайту:


Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.2. Секретность системы шифрования

14.2.1. Совершенная секретность

Рассмотрим систему шифрования с конечной областью сообщений {М}= М0, М1 ..., MN-1 и конечной областью шифрованных текстов {С} = С0, С1 ..., CU-1,. Для любого Мi априорная вероятность передачи сообщения Мi, равна Р(Мi). Апостериорная вероятность принятия сообщения Cj при переданном сообщении М, равна Pi/Cj). Говорят, что система шифрования имеет совершенную секретность, если для любого сообщения Mi и любого шифрованного текста Cj апостериорная вероятность равна априорной.

(14.2)

Таким образом, для системы с совершенной секретностью характерно следующее: если криптоаналитик перехватил сообщение Cj, то дальнейшей информации, которая бы облегчила ему дешифровку сообщения, он не получит. Необходимое и достаточное условие совершенной секретности: для любого Mi и Cj,

(14.3)

На рис. 14.4 изображен пример схемы совершенной секретности. В этом примере {М}=М0, М1, М2, М3; {С} = С0, С1,С2, С3; {К} =K0, K1 K2,K3 ;N=U=4, Р(Мi)=Р(Сj) =1/4.

Преобразование сообщения в шифрованный текст выполняется следующим образом.

(14.4)


Рис.14.4. Совершенная секретность.

Здесь ТKj определяет преобразование с помощью ключа Kj, а «х по модулю y»— это остаток от деления х на y. Таким образом, s= 0, 1, 2, 3. Криптоаналитик, перехвативший одно из шифрованных сообщений Cs =С1, С1,С2или С3, не сможет определить, какой из четырех ключей использовался и, следовательно, какое из сообщений М0, М1, М2или М3является верным. Если в системе шифрования число сообщений, число ключей и число шифрованных сообщений равны между собой, то система имеет совершенную секретность тогда и только тогда, когда выполняются следующие два условия.

1. Существует только один ключ, преобразующий каждое сообщение в каждый шифрованный текст.

2. Все ключи равновероятны.

Если эти условия не выполняются, то будет существовать некоторое сообщение Мi , при котором для данного Сj, не существует ключа, который мог бы дешифровать Сj в Мi. Отсюда следует, что для некоторых i и j Р(Мij)=0. В этом случае криптоаналитик может исключить из рассмотрения определенные нешифрованные сообщения, упростив, таким образом, задачу. Вообще, совершенная секретность является очень желательным свойством, поскольку это означает, что система шифрования безусловно защищена. Должно быть очевидно, что в системах, передающих большое количество сообщений, для достижения совершенной секретности требуется распределить большое количество ключей, а это, в свою очередь, может привести к значительным практическим затруднениям, что делает такие системы нереализуемыми. В системе с совершенной секретностью число возможных ключей так же велико, как и число возможных сообщений, поэтому, если мы разрешим передавать сообщения неограниченной длины, совершенная секретность потребует бесконечного количества ключей.

Пример 14.1. Взлом системы шифрования, если область ключей меньше области сообщений

Рассмотрим шифрованный текст, состоящий из 29 символов.

G R O В О К В О D R O R O В Y O C Y P I O C D O B I O K B

Данный текст был получен с помощью шифра Цезаря (см. раздел 14.1.4); каждая буква получена сдвигом на K символов, где 1К25. Покажите, как криптоаналитик может взломать этот код.

Решение

Поскольку количество возможных ключей (их 25) меньше количества возможных осмысленных сообщений из 29 символов (их огромное множество), совершенная секретность не может быть достигнута. В исходном полиалфавитном шифре, показанном на рис. 14.3, символ открытого текста заменяется буквой некоторой строки, причем номер строки постоянно возрастает. Следовательно, в процессе анализа шифрованного текста мы обращаем процесс: теперь буквы шифрованного текста заменяются буквами строк, причем номер строки постоянно уменьшается. Путем перебора всех ключей от 1 до 25 (рис. 14.5) можно легко рассмотреть все возможности. В результате, этот процесс приводит к единственному ключу (K=10), дающему осмысленное сообщение (пробелы были добавлены вручную): WHERE ARE THE HEROES OF YESTERYEAR.

Пример 14.2. Совершенная секретность

Для создания шифра, имеющего совершенную секретность, можно несколько модифицировать область ключей, описанную в примере 14.1. В этой новой системе шифрования каждый символ сообщения шифруется с использованием случайно выбранного ключевого значения. Теперь ключ K задается последовательностью k1, k2, ..., k29, где каждое ki— это случайно выбранное целое число из интервала (1,25), определяющее сдвиг, используемый для i-го символа. Таким образом, всего существует (25)29 различных ключевых последовательностей. Значит, шифрованный текст из 29 символов, приведенный в примере 14.1, может соответствовать любому осмысленному сообщению из 29 символов. Например, шифрованный текст мог соответствовать следующему открытому тексту (пробелы были добавлены вручную).

ENGLISH AND FRENCH ARE SPOKEN HERE

Данный текст получен с помощью ключа 2, 4, 8, 16, 6, 18, 20, ... . Стоит отметить, что большинство возможных наборов из 29 символов можно исключить, поскольку они не являются осмысленными сообщениями. Совершенная секретность данного кода – результат того, что перехват шифрованного текста не дает никакой дополнительной информации об открытом сообщении.

Ключ Текст

0

G

R

O

B

O

K

B

O

D

R

O

R

O

B

Y

O

C

Y

P

I

O

C

D

O

B

I

O

K

B

1

F

Q

N

A

N

J

A

N

C

Q

N

Q

N

A

X

N

B

X

O

H

N

B

C

N

A

H

N

J

A

2

E

P

M

Z

M

I

Z

M

B

P

M

P

M

Z

W

M

A

W

N

G

M

A

B

M

Z

G

M

I

Z

3

D

O

L

Y

L

H

Y

L

O

A

L

O

L

Y

V

L

Z

V

M

F

L

Z

A

L

Y

F

L

H

Y

4

C

N

K

X

K

G

X

K

Z

N

K

N

K

X

U

K

Y

U

L

E

K

Y

Z

K

X

E

K

G

X

5

B

M

J

M

J

F

W

J

Y

M

J

M

J

W

T

J

X

T

K

D

J

X

Y

J

W

D

J

F

W

6

A

L

I

V

I

E

V

I

X

L

I

L

I

V

S

I

W

S

J

C

I

W

X

I

V

C

I

E

V

7

Z

K

H

U

H

D

U

H

W

K

H

K

H

U

R

H

V

R

I

B

H

V

W

H

U

B

H

D

U

8

Y

J

G

T

G

C

T

G

V

J

G

J

G

T

Q

G

U

Q

H

A

G

U

V

G

T

A

G

C

T

9

X

I

F

S

F

B

S

F

U

I

F

I

F

S

P

F

T

P

G

Z

F

T

U

F

S

Z

F

B

S

10

W

H

E

R

E

A

R

E

T

H

E

H

E

R

O

E

S

O

F

Y

E

S

T

E

R

Y

E

A

R

11

V

G

D

Q

D

Z

Q

D

S

G

D

G

D

Q

N

D

R

N

E

X

D

R

S

D

Q

X

D

Z

Q

12

U

F

C

P

C

Y

P

C

R

F

C

F

C

P

M

C

Q

M

D

W

C

Q

R

C

P

W

C

Y

P

13

T

E

B

O

B

X

O

B

Q

E

B

E

B

O

L

B

P

L

C

V

B

P

Q

B

O

V

B

X

O

14

S

D

A

N

A

W

N

A

P

D

A

D

A

N

K

A

O

K

B

U

A

O

P

A

N

U

A

W

N

15

R

C

Z

M

Z

V

M

Z

O

C

Z

C

Z

M

J

Z

N

J

A

T

Z

N

O

Z

M

T

Z

V

M

16

Q

B

Y

L

Y

U

L

Y

N

B

Y

B

Y

L

I

Y

M

I

Z

S

Y

M

N

Y

L

S

Y

U

L

17

P

A

X

K

X

T

K

X

M

A

X

A

X

K

H

X

L

H

Y

R

X

L

M

X

K

R

X

T

K

18

O

Z

W

J

W

S

J

W

L

Z

W

Z

W

J

G

W

K

G

X

Q

W

K

L

W

J

Q

W

S

J

19

N

Y

U

H

U

Q

H

U

J

X

U

X

U

H

E

U

I

E

V

O

U

I

J

U

H

O

U

Q

H

20

M

X

U

H

U

Q

H

U

J

X

U

X

U

H

E

U

I

E

V

O

U

I

J

U

H

O

U

Q

H

21

L

W

T

G

T

P

G

T

I

W

T

W

T

G

D

T

H

D

U

N

T

H

I

T

G

N

T

P

G

22

K

V

S

F

S

O

F

S

H

V

S

V

S

F

C

S

G

C

T

M

S

G

H

S

F

M

S

O

F

23

J

U

R

E

R

N

E

R

G

U

R

U

R

E

B

R

F

B

S

L

R

F

G

R

E

L

R

N

E

24

I

T

Q

D

Q

M

D

Q

F

T

Q

T

Q

D

A

Q

E

A

R

K

Q

E

F

Q

D

K

Q

M

D

25

H

S

P

C

P

L

C

P

E

S

P

S

P

C

Z

P

D

Z

Q

J

P

D

E

P

C

J

P

L

C

Рис. 14.5. Пример взлома системы шифрования, если область ключей меньше области сообщений




***** Яндекс.Поиск по сайту:



© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.