Научные проблемы Интернета (стр. 2 из 5)
 . | (1.13) |
Итак,
.Все сошлось. Возьмем, например,
. Тогда 
, 
: 
(ответ тот же).Таким образом, не имеет значения, какое z брать для получения d.
Метод RSA мы завершим следующим замечанием.
Метод RSA вообще говоря требует, чтобы m было большим простым числом. Для установления факта, что m – простое, можно использовать малую теорему Ферма:
 . | (1.14) |
В (1.14) a и p должны быть взаимно просты, а p – простое число.
Пример.
, 
: 
. 
, 
: 
.К сожалению, формула (1.14) справедлива также для некоторых составных чисел. Поэтому чтобы применить ее на практике, нудно выполнить проверку для некоторых различных a(идея алгоритма Рабина).
Электронная подпись. Принцип электронной подписи легко выводится из алгоритма RSA. Пусть нужно подписать текст T. Этот текст нудно «свернуть» в некое число y. Для свертки используют алгоритм хэширования. Теперь из уравнения (1.13) на основании секретного ключа получают подпись X. Число X и возвращается вместе с T и y в качестве подписи в документу Т. Не зная секретного ключа d (заменяющего фамилию), нельзя найти X. Проверяющий легко проверит (1.1), чтобы удостовериться, что X и y соответствуют друг другу. Заметим, что кто-либо может перехватить документ и подписать его своей подписью, если ему известно преобразование (1.13). Поэтому принятый «подделанный» документ должен быть «застрахован».
Для этого используется число e – открытый ключ подписавшего документ. Теперь очень легко проверить соотношение:
.Подобрать секретный ключ d к открытому ключу e практически невозможно.
Метод Диффи и Хеллмана является двухключевым. Каждый абонент в сети имеет два ключа: один секретный –
, второй открытый, вычисляемый по формуле 
,где p – большое простое число (взаимно простое с
); 
.Число
выбирается так, чтобы числа 
, 
, …, 
по модулю p давали некоторую перестановку чисел {1, 2, …, p-1}. Число называется первообразным корнем p. Все абоненты публикуют свои открытые ключи 
. Допустим, абоненты A и B хотят передать друг другу информацию. Тогда первый из них, например A, берет открытый ключ абонента B 
и вычисляет 
.Таким образом, оба абонента находят одно и то же число, которое они и используют в качестве ключа для обмена сообщениями. При этом секретные ключи абонентов остаются известными только им одним.
Алгоритм DES. Алгоритм DES (descriptionencryptionsystem) состоит в последовательности чередующихся операций подстановки и перемешивания. Алгоритм DES использует секретный ключ K. Пусть, например, блок данных есть
, а ключ 
.Подстановка есть сложение по модулю 2:
 | 10010011 |
| 11001011 | |
| 01011000 |
Таким образом, операция подстановки непредсказуемым образом искажает исходные данные. Для восстановления исходных данных достаточно выполнить подстановку вторично:
| | 01011000 |
| 11001011 | |
| 10010011 |
Операция перемешивания заключается в обмене местами двух блоков в соответствии с заранее составленными таблицами. Длина обмениваемых блоков одинакова, но варьирует от одного прохода к другому. Операция подстановки выполняется не над целым ключом, а над случайно выбираемой его частью. Эта случайно выбираемая часть сама определяется значением ключа. Одним из способов получения псевдослучайных чисел является следующий:
 . | (1.15) |
Здесь
– псевдослучайное число, порожденное на шаге i. первоначально полагают, например, 
. В качестве константы C примем  , | (1.16) |
где K – секретный ключ. Величина M как правило равна
; величина n равна числу разрядов генерируемого псевдослучайного числа. Например, пусть 
, 
, , 
, 
: 
, 
, 
, 
, 
и т.д.Порожденные псевдослучайные числа могут определять номера разрядов, выбираемых из ключа в формируемую часть для выполнения операции подстановки.
Для дешифрации принятой комбинации нужно знать ключ K и выполнять операции подстановки и перемешивания в обратном порядке
Сжатие по методу Д. Хаффмана
Метод сжатия Хаффмана является одним из лучших способов сжатия информации. Данный метод мы изложим на следующем примере. Пусть дана подлежащая сжатию последовательность из «0» и «1»:
| 010000101000101111001011. | (1.17) |
Разобьем эту последовательность на тройки разрядов и для каждой тройки подсчитаем, сколько раз она встречается в последовательности (рис. 1.13)
010’000’101’000’101’111’001’011
| 010 – 1000 – 2101 – 2111 – 1001 – 1011 – 1a) | 000 – 2101 – 2010 – 1111 – 1001 – 1011 – 1b) |
Рис. 1.13.
Упорядочим комбинации по частоте встречаемости (рис. 1.13b). Теперь «объединим» две последние комбинации на рис. 1.13b в одну и все комбинации снова переупорядочим по убыванию частоты встречаемости (рис. 1.14)
‘001-011’ – 2
000 – 2
101 – 2
010 – 1
111 – 1
Рис. 3.14.
Теперь снова объединим две последние комбинации в одну и проведем очередное упорядочение (рис. 1.15)
‘010-111’ – 2
‘001-011’ – 2
000 – 2
101 – 2
Рис. 1.15.
Дальнейший процесс объединения комбинаций выполним по аналогии (рис. 1.16, 1.17)
| ‘000-101’ – 2‘010-111’ – 2‘001-011’ – 2Рис. 3.16. | ‘010-111-001-011’ – 4 ‘000-101’ – 4Рис. 3.17. |
Теперь нарисуем дерево, схематически передающее реализованный нами способ объединения комбинаций (рис. 1.18)
