ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 310
Скачиваний: 7
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
120
Тогда число, обратное числу α равно
α
−1
≡ α
φ(????)−1
. (6.10)
Эффективное применение выражения (6.10) требует нахождения значения порядка ???? элемента α, т. е. когда выполняется условие
α
????
≡ 1mod ????.
Теорема 6.3. Порядок ???? числа α должен быть делителем функции Эйлера
φ(????).
Пример 6 .1 . Пусть α = 5, ???? = 31. Найти:
– обратное число α
−1
;
– порядок числа 5;
– число, обратное числу 5
−1
по mod 31.
Решение
1. Так как
???? – простое число, φ(????) = ???? − 1 = 30. Обратное число
α
−1
= ((α
φ(????)−1
)) = ((α
(????−1)−1
)) = ((α
30−1
)) = α
29 2. Находим порядок числа
5:
5 3
= 125 ≡ 1mod 31, ???? = 3.
Число 3 является делителем числа φ(31) = 30.
3. Обратное число
5
−1
= 5 29
= 5 27
∙ 5 2
= ((5 3
)
9
∙ 5 2
)) = 25.
Действительно,
5 ∙ 5
−1
= 5 ∙ 25 ≡ 1mod 31.
Пример 6 .2. Пусть α = 6, ???? = 31. Найти 6
−1
Решение. Функция Эйлера φ(????) = ???? − 1 = 30.
Число6
−1
= ((α
30−1
)) = 6 29
Хотя ближайшие числа 2, 3, 5 делят число 30, они не являются порядком ???? числа 6. Только число 6 является порядком ???? числа 6. Действительно,
6 6
= 46636 ≡ 1mod 31.
Находим число:
121 6
−1
= ((6 29
)) = ((6 24
∙ 6 5
)) = ((6 6
)
4
∙ 6 5
)) = 6 5
= 7776 ≡ 26 mod 31.
Действительно,
6 ∙ 26 ≡ 1mod 31.
6.7.3. Последовательность шагов криптоалгоритма RSA
Пр и м е р 6 .3 . Зашифровать слово РУХ с помощью алгоритма RSA.
Решение. Действия получателя А шифрованной информации.
1. Выбираем ???? = 3 и ???? = 7.
2. Вычисляем модуль ???? = ???????? = 3 ∙ 7 = 21.
3. Вычисляем значение функции Эйлера для ???? = 21:
φ(????) = φ(21) = (???? − 1)(???? − 1) = 2 ∙ 6 = 12.
4. Выбираем в качестве открытого ключа ???? произвольное число с учетом выполнения условий:
1 < ???? ≤ φ(????), НОД (????, φ(????)) = 1, НОД (????, 12) = 1.
Пусть ???? = 11.
5. Из выражения (6.8) вычисляем значение секретного ключа
????, используя алгоритм нахождения обратных чисел по теореме Эйлера:
???? ∙ ???? ≡ 1mod φ(????),
11 ∙ ???? ≡ 1mod 12.
???? = ????
−1
≡ 11
−1
mod 12.
Число 2 является порядком ???? = 2 числа α = 11, т. к. соблюдается условие:
α
????
≡ 1mod ????,
11 2
= 121 ≡ 1mod 12.
Из алгоритма нахождения обратных чисел по теореме Эйлера
α
−1
= ((α
φ(????)−1)
)) находим φ(12) = 4.
Число, обратное ????, равно
???? = ????
−1
= ((????
φ(12)−1)
)) = ((????
3)
)),
11
−1
= ((11 3
)) = ((11 2
∙ 11)) = 11.
122
Проверим правильность полученного значения ????:
???? ∙ ???? ≡ 1mod 12 = 11 ∙ 11 ≡ 1mod 12.
6. Получатель А шифрованной информации пересылает отправителю пару открытых чисел (???? = 21, ???? = 11).
Действия отправителя шифрованной информации
7. Представляем шифруемое сообщение РУХ в виде последовательности целых чисел в диапазоне ???? = 0, 1, … , ???? − 1.
Пусть буква Р записывается числом 1, буква У – числом 2, буква Х – чис- лом 3. Сообщению РУХ соответствует последовательность (блоки) чисел 123.
Текст сообщения в виде блоков записывается как ????
1
????
2
????
3
, где
????
1
= 1, ????
2
= 2, ????
2
= 3.
8. Шифруем текст, используя ключ ???? = 11 и ???? = 21 по формуле (6.4):
????
????
≡ ????
????
????
mod ???? ≡ ????
????
11
mod 21.
Шифротексту соответствуют следующие числа:
????
1
= 1 11
mod 21 ≡ 1,
????
2
≡ 2 11
mod 21 ≡ 2048 mod 21 ≡ 11,
????
3
≡ 3 11
mod 21 ≡ 12.
Криптограмма имеет вид
????
1
????
2
????
3
= ????
????
= 11112.
После разбиения на блоки она пересылается.
Действия получателя по дешифрации криптограммы
9. Дешифрация криптограммы
????
1
????
2
????
3
= 1, 11, 12 производится с исполь- зованием секретного ключа ???? = 11 по формуле
????
????
= ????
????
????
mod ???? = ????
????
11
mod21.
В результате получаем:
????
1
= 1 11
mod 21 ≡ ((1)),
????
2
= 11 11
mod 21 ≡ ((2)),
????
3
= 12 11
mod 21 ≡ ((3)).
Исходное сообщение: РУХ.
123
6.8. Задания для самостоятельного выполнения
1. Пусть
α = 2, ???? = 9. Найти порядок элемента α.
2. Пусть
α = 4, ???? = 17. Найти порядок элемента α.
3. Пусть
α = 7, ???? = 17. Найти 7
−1 4. Пусть
α = 10, ???? = 23. Найти 10
−1 5. Создать RSA-криптосистему, используя
???? = 2 ∙ 13. Вычислить публич- ный ключ (????, ????) и секретный ключ ????. Используйте эти ключи, для кодирования сообщения «МІНСК».
6. Создать RSA-криптосистему, используя
???? = 3 ∙ 17. Вычислить публич- ный ключ (????, ????) и секретный ключ (????, ????). Используйте эти ключи, для кодиро- вания сообщения «ІІТ».
124
1 ... 6 7 8 9 10 11 12 13 ... 17
ЧАСТЬ 2. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
7. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО КОДИ-
РОВАНИЯ
7.1. Основная теорема кодирования для канала с шумом (вторая тео-
рема Шеннона)
Теорема 7.1. Пусть C – пропускная способность дискретного канала без памяти, источник характеризуется энтропией ????. Если ???? < ????, тогда для любого
0 существует метод кодирования информации [n, k, d]-двоичным кодом, веро- ятность ошибки декодирования которого P
ош
Теорема Шеннона состоит из двух утверждений.
Прямое утверждение. При любой производительности источника сообще- ний, меньшей, чем пропускная способность канала, существует такой способ ко- дирования, который обеспечивает передачу информации со сколь угодно малой вероятностью ошибки.
Замечания:
1. Под производительностью источника сообщений понимают количество информации, вырабатываемой источником в единицу времени.
2. Пропускная способность канала – это предельная скорость передачи ин- формации, при которой еще возможна передача со сколь угодно малой вероят- ностью ошибки.
3. Пропускная способность
???? канала – это максимальная взаимная инфор- мация ????(????; ????)
max
, которая может быть достигнута в канале с матрицей ???? пере- ходных вероятностей (см. определение. 5.5).
Обратное утверждение. Не существует способа кодирования, позволяю- щего вести передачу информации со сколь угодно малой вероятностью ошибки, если производительность источника сообщений больше пропускной способно- сти канала.
Теорема с одной стороны – фундаментальна, а с другой стороны – некон- структивна.
Фундаментальность заключается в том, что теоремой устанавливается теоре- тический предел эффективности системы при достоверной передаче информации.
При этом:
помехи в канале не ограничивают точность (достоверность) передачи;
помехи ограничивают скорость передачи информации, при которой мо- жет быть достигнута сколь угодно высокая достоверность передачи;
при любой конечной скорости передачи информации, вплоть до про- пускной способности, сколь угодно малая вероятность ошибки достигается лишь при увеличении длительности кодовых последовательностей и использовании
125 большого ансамбля кодовых слов.
Неконструктивность теоремы заключается в том, что в ней не затрагива- ются пути построения кодов, методы обработки, обеспечивающие безошибоч- ную передачу информации, а лишь утверждается их существование.
7.2. Возможность исправления ошибок помехоустойчивым кодом
7.2.1. Параметры кодов
Определение 7.1. Код – это множество дискретных последовательностей, разрешенное для передачи сообщений.
Коды характеризуются следующими параметрами.
Размерность q кодового алфавита – число различных элементов алфа- вита, выбранное для построения кода.
В качестве кодового алфавита могут использоваться символы двоичного
{0,1} или бинарного алфавита {1, −1}. Например, слово ???? = (????
1
????
2
… ????
7
) =
= (−1 − 1 − 111 − 11) представлено символами бинарного алфавита источ- ника, q = 2.
Определение 7.2. Длина n кода (значность) – число символов кодового слова. Последовательности символов называются кодовыми словами или кодо- выми векторами.
Параметр n определяет следующие виды кодов:
– равномерные (блоковые), n = const;
– неравномерные, n = var;
– бесконечные, n =
Определение. 7.3. Размерность k кода – число информационных элемен- тов (позиций) кодового слова.
Определение 7.4. Мощность ???? = ????
????
кода – это число различных кодовых последовательностей (комбинаций), разрешенных для кодирования.
Различают ????
max
= ????
????
максимальное число кодовых слов при заданных q и n. Например, для q = 3, n = 6 имеем ????
max
= ????
????
= 729 слов. Код, у которого используются все комбинации, т. е. его мощность равна ????
max
, называется пол- ным (безызбыточным). Для него k = n.
Если код определяется числом M
max
> M, то код называется избыточным.
Пример 7 .1 . Код с параметрами q = 2, n = 5, M = 4 является избыточным.
Кодовые слова записаны в виде матрицы
???? = [
1 0 1 1 0
0 1 0 1 0
1 1 1 0 0
0 0 0 0 0
].
Определение 7.5. Число проверочных (избыточных) позиций кодового
126
слова r = (n – k).
Пусть n = 7, q = 2, k = 4. Тогда на длине слова из семи символов три избы- точных.
Определение 7.6. Скорость ???? =
????
????
передачи кода.
Для примера 7.1 ???? =
4 7
Определение 7.7. Кратность ???? ошибки. Параметр ????указывает, что все кон- фигурации с ????или менее ошибками в любом кодовом слове могут быть исправ- лены и (или) обнаружены.
Предположим, что по каналу передается или хранится в памяти двоичный вектор ???? = (????
0
, ????
1
, … , ????
????−1
), а принимается, или считывается из памяти, вектор
???? = (????
0
, ????
1
, … , ????
????−1
). Тогда вектор ???? − ???? = ???? = (????
0
, ????
1
, … , ????
????−1
) называется век- тором ошибок, где ????
????
∈ {0, 1}. Если ошибок не произошло, то все ????
????
= 0. Вектор ошибок указывает место и значение ошибок.
Определение 7.8. Расстояние Хэмминга ????
????
между двумя векторами (сте- пень удаленности любых кодовых последовательностей друг от друга). Если ???? =
(????
0
, ????
1
, … , ????
????−1
) и ???? = (????
0
, ????
1
, … , ????
????−1
) кодовые векторы, то расстояние Хэм- минга равно числу позиций, в которых они различаются.
Расстояние Хэмминга может обозначаться и как dist (????, ????). Например, dist ((a b b c b), (c b c a a) = 4, dist ((0 1 2 2), (2 2 1 2)) = 3.
Замечание. С позиции теории кодирования ????
????
показывает, сколько симво- лов в слове надо исказить, чтобы перевести одно кодовое слово в другое.
Определение 7.9. Наименьшее значение расстояния Хэмминга для всех пар кодовых последовательностей кода ???? называют кодовым расстоянием ???? (ми- нимальное расстояние кода):
???? = min {dist(????, ????)}, где ???? ∈ ????, ???? ∈ ????, ???? ≠ ????.
Кодовое расстояние ???? характеризует корректирующую способность кода:
???? = ????(????).
Определение 7.10. Код значностью n, размерностью k и расстоянием ???? называется [????, ????, ????]-кодом.
Пример 7 .2. Построить следующий [5, 2, 2]-код:
???? = [
1 0 1 1 0
0 1 0 1 0
1 1 1 0 0
0 0 0 0 0
].
127
Данный код можно использовать для кодирования 2-битовых двоичных чисел, используя следующее (произвольное) соответствие:
0 0
0 0 0 0 0,
1 0
1 0 1 1 0,
0 1
0 1 0 1 0,
1 1
1 1 1 0 0.
Найдем кодовое расстояние кода: dist((1 0 1 1 0), (0 1 0 1 0)) = 3, dist((1 0 1 1 0), (1 1 1 0 0)) = 2, dist((0 1 0 1 0), (1 1 1 0 0)) = 2.
Для этого кода ???? = min{dist(????, ????)} = 2.
Определение 7.11. Вес Хэмминга вектора ???? = (????
0
, ????
1
, … , ????
????−1
) равен числу ненулевых позиций этого вектора; обозначается wt(????).
Например, wt(1 2 3 0 4 3 0) = 5. Используя определение веса вектора Хэм- минга, получим очевидное выражение dist(????, ????) = wt(???? − ????). (7.1)
Пример 7 .3 . Найти ????
????
векторов
???? = (1 2 0 2)
T и ???? = (2 0 1 2)
T
Решение. dist(????, ????) = wt ([
1 2
0 2
] − [
2 0
1 2
]) = wt [
2 2
2 0
] = 3.
Из выражения (7.1) следует, что минимальное расстояние Хэмминга равно
???? = min{dist(????, ????)} = min{wt(???? − ????)}, где ???? ∈ ????, ???? ∈ ????, ???? ≠ ????.
Замечание. Для нахождения минимального расстояния линейного кода не обязательно сравнивать все возможные пары кодовых слов. Если ???? и ???? принад- лежат линейному коду ????, то ???? − ???? = ???? также является кодовым словом кода ????.
Такой код является аддитивной группой (определена операция сложения), сле- довательно,
???? = min{dist(????, ????)} = min wt(????), где ???? ∈ ????, ???? ≠ 0.
128
Теорема 7.2. Минимальное расстояние линейного кода равно минималь- ному весу ненулевых кодовых слов.
Так как ???? = ????(????), то возникает вопрос о величине d, такой, чтобы код обес- печивал контроль ошибок, т. е. обнаружение и исправление ошибок.
7.2.2. Блоковые коды
У блоковых кодов поток данных разделяется на блоки по ????информацион- ных символов, и далее они кодируются n-символьными кодовыми словами. На рис. 7.1 показана структура кодирования блоковым кодом.
Рис. 7.1. Блоковое кодирование
7.2.3. Ошибки, их разновидности
Ошибки бывают:
– случайные (независимые);
– зависимые.
Случайные ошибки возникают независимо друг от друга в передаваемом сообщении. При этом говорят о кратности ошибок t.
Зависимые ошибки делятся на:
– на пакетные;
– модульные.
Пакет ошибок описывается длиной пакета p. Он может находиться в про- извольном месте потока передаваемых (записываемых) символов. В этом случае говорят,что граница (фаза) пакета неизвестна.
Например, в ЗУ длиной 16 следует записать информацию
0001 0110 1111 1010.
Произошла пакетная ошибка длиной p = 4. В ЗУ запишется информация
0001 0101 0011 1010.
Кратность пакета ошибок обозначается через ????. Пакет ошибок