Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
шпоры тпи финал.doc
Скачиваний:
2
Добавлен:
01.05.2025
Размер:
4 Мб
Скачать
☆

4) Криптосистема с открытым ключом

Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir А.) и Л. Адлеман (Adleman L.). По их именам эта система получила название RSA.

Пусть абоненты А и В решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа (pA1, pA2 и pВ1, pВ2), находит их произведение (rа и rb), функцию Эйлера от этого произведения (φ(rа) и φ(rb)) и случайное число (а и b), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, А из уравнения аα ≡ 1 (mod φ(rа)) находит α (0 < а < φ(rа)), а B из уравнения bβ ≡ 1 (mod φ(rb)) находит β (0 < β < φ(rb)). Затем А и В печатают доступную всем книгу паролей вида:

А: rа, α

B: rb, b

Теперь кто-угодно может отправлять конфиденциальные сообщения А или В. Например, если пользователь книги паролей хочет отправить сообщение т для В (т должно быть меньшим rb, или делиться на куски, меньшие rb), то он использует ключ b из книги паролей для получения шифрованного сообщения m1 по формуле m1 ≡ mb(mod rb), которое и отправляется В. В для дешифровки m1 использует ключ β в формуле m1b ≡ mbβ ≡ m (mod rb), т. к. bβ ≡ 1 (mod φ(rb), следовательно, bβ ≡ kφ(rb)+1 для некоторого целого k и mkφ(rB)+1≡ (mφ(rB))km≡ m(mod rb), т. к. mφ(rB) ≡ 1 (mod rb) по теореме Эйлера-Ферма. Доказано [12], что задача нахождения секретного ключа β по данным из книги паролей имеет ту же сложность, что и задача разложения числа rb на простые множители.

Пример 9.13. Пусть для А pA1= 7 и pA2 = 23, тогда rа = pA1 pA2 = 161, φ(161) = 6 * 22 = 132, α = 7, α = 19 (из уравнения 7α ≡ 1 (mod 132)). Следовательно, запись в книге паролей для А будет иметь вид А: 161, 7. Если кто-то захочет отправить А секретное сообщение m = 3, то он должен сначала превратить его в шифровку m1 по формуле m1 ≡ З7 ≡ 94 (mod 161). Когда А получит m1 = 94 он дешифрует его по формуле m ≡ 9419 ≡ 3 (mod 161).

5) Вероятностные методы сжатия используют кодовые слова переменной длинны. В основе вероятностных методов сжатия (алгоритмов Шеннона-Фано и Хаффмена) лежит идея построения «дерева», на «ветвях» которого положение символа определяется частостью его появления. Каждому символу присваивается код, длина которого обратно пропорциональна частости появления этого символа. Существуют две разновидности вероятностных методов, различающихся способом определения вероятности появления каждого символа:

– статические методы, использующие фиксированную таблицу частости появления символов, рассчитываемую перед началом процесса сжатия,

– динамические или адаптивные методы, в которых частость появления символов все время меняется и по мере считывания нового блока данных происходит перерасчет начальных значений частостей.

Суть метода Хаффмена сводится к следующему. Символы, встречающиеся в файле, выписываются в столбец в порядке убывания вероятностей (частости) их появления. Два последних символа объединяются в один с суммарной вероятностью. Из полученной новой вероятности м вероятностей новых символов, не использованных в объединении, формируется новый столбец в порядке убывания вероятностей, а две последние вновь объединяются. Это продолжается до тех пор, пока не останется одна вероятность, равная сумме вероятностей всех символов, встречающихся в файле.

Процесс кодирования по методу Хаффмена поясняется табл. 8.2. Для составления кода, соответствующего данному символу, необходимо проследить путь перехода знака по строкам и столбцам таблицы кода.

Таблица 8.2

Процесс кодирования по методу Хаффмена

Символ

Частость

появления

1

Кодовое

слово

c

22

22

2 2

26

3 2

4 2

5 8

01

e

20

20

20

22

26

3

1

2

42

00

h

16

16

16

2

1

0

22

2

0

6

111

i

16

16

1

1

1

6

16

20

0

110

a

10

10

1 6

1

0

6

100

k

10

10

1 0

0

1011

m

4

6

0

10101

b

2

10100

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

Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.

Существует, правда, динамическая версия сжатия Хаффмена, которая может строить дерево Хаффмена "на лету" во время чтения и активного сжатия. Дерево постоянно обновляется, чтобы отражать изменения вероятностей входных данных. Однако и она на практике обладает серьезными ограничениями и недостатками и, кроме того, обеспечивает меньшую эффективность сжатия.

Еще один недостаток кодов Хаффмена - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код Хаффмена становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Наконец, код Хаффмена обеспечивает среднюю длину кода, совпадающую с энтропией, только в том случае, когда вероятности символов источника являются целыми отрицательными степенями двойки: 1/2 = 0,5; 1/4 = 0,25; 1/8 = 0,125; 1/16 = 0,0625 и т.д. На практике же такая ситуация встречается очень редко или может быть создана блокированием символов со всеми вытекающими отсюда последствиями.

Билеты №5, 22

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]