Лидовский. Учебное пособие написано на основе односеместрового 108 часового курса лекций и материалов для практических занятий, используемых автором в учебной работе со
 Скачать 0.89 Mb.
|
|
7 + x 5 + x + 1 построить полиномиальные коды для двоичных сообщений 0100, 10001101, Упражнение Принадлежат ли коду Голея кодовые слова 10000101011111010011111 и. Понятие о кодах Боуза-Чоудхури-Хоккенгема Остался открытым вопрос о методике построения кодов, минимальное расстояние между кодовыми словами которых равно заданному числу. В 1960 году независимо Боуз (Bose), Чоудхури (Chaudhuri) и Хоккенгем (Hocquengem) открыли способ построения полиномиальных кодов, удовлетворяющих таким требованиям. Эти коды получили названия кодов Боуза-Чоудхури-Хоккенгема или БЧХ-кодов (BCH codes). 67 БЧХ-коды могут быть не только двоичными, например, на практике достаточно широко используются недвоичные коды Рида-Соломона (Reed, Solomon), но далее будут рассматриваться только двоичные. Многочлен g(x) степени k называется примитивным, если x j + делится на g(x) без остатка для j = 2 k − 1 и не делится ни для какого меньшего значения Например, многочлен 1 + x 2 + примитивен он делит x 7 + 1, ноне делит x j + 1 при j < 7. Примитивен также многочлен 1 + x 3 + он делит x 15 + 1, ноне делит x j + 1 при j < Кодирующий многочлен g(x) для БЧХ-кода, длина кодовых слов которого n, строится так. Находится примитивный многочлен минимальной степени q такой, что n 2 q − 1 или q log 2 (n + 1). Пусть — корень этого многочлена, тогда рассмотрим кодирующий многочлен НОК(m 1 (x), . . . , m d−1 (x)), где m 1 (x), . . . , m d−1 (x) многочлены минимальной степени, имеющие корнями соответственно, α 2 , . . . , Построенный кодирующий многочлен производит код с минимальным расстоянием между кодовыми словами, не меньшими длиной кодовых слов n Пример. Нужно построить БЧХ-код с длиной кодовых слови минимальным расстоянием между кодовыми словами d = 5. Степень примитивного многочлена равна q = log 2 (n + 1) = 4 и сам он равен x 4 + x 3 + 1. Пусть α — его корень, тогда и α 4 — также его корни. Минимальным многочленом для будет x 4 + x 3 + x 2 + x + 1. Следовательно НОК(x 4 + x 3 + 1, x 4 + x 3 + x 2 + x + 1) = = (x 4 + x 3 + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 4 + x 2 + x + Степень полученного многочлена равна 8, следовательно, построенный БЧХ-код будет (7, кодом. Слово 1000100 или a(x) = x 4 + 1 будет закодировано кодовым словом a(x)g(x) = x 12 + x 6 + x 5 + x 2 + x + 1 или 111001100000100. Можно построить [1] двоичный БЧХ-код с кодовыми словами длины и нечетным минимальным расстоянием d, у которого число контрольных символов не больше q(d − Первый БЧХ-код, примененный на практике, был (92, 127)-кодом, исправляющим ошибки кратности до 5, но наиболее широкое распространение получил (231, код, обнаруживающий ошибки кратности до 6. БЧХ-коды умеренной длины не слишком далеки от совершенных или квазисовершенных кодов. Коды Хэмминга, например, являются БЧХ-кодами, а БЧХ-коды с минимальным весом кодового слова 5 — 68 квазисовершенны. Нос ростом длины кодовых слов качество БЧХ-кодов падает. Код Голея, например, — это не код БЧХ. Упражнение Найти кодирующий многочлен БЧХ-кода g(x) с длиной кодовых слови минимальным расстоянием между кодовыми словами 7. Использовать примитивный многочлен m 1 (x) = 1 + x + с корнем α. Проверить, будут ли и корнями соответственно многочленов m 3 (x) = 1 + x + x 2 + x 3 + и m 5 (x) = 1 + x + x 2 27. Циклические избыточные коды Циклический избыточный код (Cyclical Redundancy Check — имеет фиксированную длину и используется для обнаружения ошибок. Наибольшее распространения получили коды CRC-16 и CRC-32, имеющие длину 16 и 32 бита соответственно. Код CRC строится по исходному сообщению произвольной длины, те. этот код не является блочным в строгом смысле этого слова. Но при каждом конкретном применении этот код — блочный, (m, m + код для CRC-16 или (m, m + код для Вычисление значения кода CRC происходит посредством деления многочлена, соответствующего исходному сообщению (полином- сообщение, на фиксированный многочлен (полином-генератор). Остаток от такого деления и есть код CRC, соответствующий исходному сообщению. Для кода CRC-16 полином-генератор имеет степень, а для CRC-32 — 32. Полиномы-генераторы подбираются специальным образом и для кодов CRC-16/32 стандартизированы Международным консультативным комитетом по телеграфной и телефонной связи. Для CRC-16, например, стандартным является полином- генератор x 16 + x 12 + x 5 + Пример построения CRC-4 кода для сообщения 11010111, используя полином-генератор x 4 +x 3 +x 2 +1. Исходному сообщению соответствует полином x 7 + x 6 + x 4 + x 2 + x + 1, те. нумерация битов здесь начинается справа+ x 6 + x 4 + x 2 + x + 1 x 4 + x 3 + x 2 + 1 x 7 + x 6 + x 5 + x 3 x 3 + x x 5 + x 4 + x 3 + x 2 + x + 1 x 5 + x 4 + x 3 + x x 2 + Полиному x 2 + 1 соответствуют биты 0101 — это и есть CRC-4 код. Существуют быстрые алгоритмы для расчета кодов, использующие специальные таблицы, а не деление многочленов с остатком. CRC-коды способны обнаруживать одиночную ошибку в любой позиции и, кроме того, многочисленные комбинации кратных ошибок, расположенных близко друг от друга. При реальной передаче или хранении информации ошибки обычно группируются на некотором участке, а не распределяются равномерно по всей длине данных. Таким образом, хотя для идеального случая двоичного симметричного канала CRC-коды не имеют никаких теоретических преимуществ по сравнению, например, с простыми контрольными суммами, для реальных систем эти коды являются очень полезными. Коды CRC используются очень широко модемами, телекоммуникационными программами, программами архивации и проверки целостности данных и многими другими программными и аппаратными компонентами вычислительных систем. Упражнение Построить CRC-4 код для сообщений 10000000 и 101111001, используя полином-генератор x 4 + 1. 28. Основы теории защиты информации Криптография (тайнопись) — это раздел математики, в котором изучаются и разрабатываются системы изменения письма с целью сделать его непонятным для непосвященных лиц. Известно, что еще в веке до нашей эры тайнопись использовалась в Греции. В современном мире, где все больше и больше услуг предоставляется через использование информационных технологий, проблема защиты информации методами криптографии имеет первостепенное значение. Сегодня большая часть обмена информацией проходит по компьютерным сетями часто (в бизнесе, военными прочее) нужно обеспечивать конфиденциальность такого обмена. Теоретические основы классической криптографии впервые были изложены Клодом Шенноном в конце х годов. Простейшая система шифрования — это замена каждого знака письма на другой знак по выбранному правилу. Юлий Цезарь, например, заменял в своих секретных письмах первую букву алфавита на четвертую, вторую — на пятую, последнюю — на третью и т.п., те. на D, B на E, Z на C и т.п. Подобные шифры, называемые простой заменой или подстановкой, описаны в рассказах Пляшущие человечки” А. К. Дойла, Золотой жук Э. Пои других. Шифры простой замены легко поддаются расшифровке, признании исходного языка сообщения, т.к. каждый письменный язык характеризуется частотой встречаемости своих знаков. Например, в английском языке чаще всего встречается буква E, а в русском — О. Таким образом, в шифрованном подстановкой сообщении на русском языке самому частому знаку будет с большой вероятностью соответствовать буква О. Вероятность будет расти с ростом длины сообщения Усовершенствованные шифры-подстановки используют возможность заменять символ исходного сообщения на любой символ из заданного для него множества символов, что позволяет выровнять частоты встречаемости различных знаков шифра, но подобные шифры удлиняют сообщение и замедляют скорость обмена информацией. В шифрах-перестановках знаки сообщения специальным образом переставляются между собой, например, записывая сообщение в строки заданной длины и беря затем последовательность слов в столбцах в качестве шифра. Сообщение “ТЕОРИЯИНФОРМАЦИИ”, используя строки длины 4, будет в шифрованном таким методом виде выглядеть как “ТИФАЕЯОЦОИРИРНМИ”, потому что при шифровании использовался следующий прямоугольник: ТЕОР ИЯИН ФОРМ АЦИИ. Шифры-перестановки в общем случае практически не поддаются дешифровке. Для их дешифровки необходимо знать дополнительную информацию. Крупный недостаток подобных шифров в том, что если удастся каким-то образом расшифровать хотя бы одно сообщение, то в дальнейшем можно расшифровать и любое другое. Модификацией шифров-перестановок являются шифры-перестановки со словом- ключом, которое определяет порядок взятия слов-столбцов. Например, если для рассмотренного шифра взять ключ РЫБА, то шифрованное сообщение будет выглядеть как “РНМИОИРИТИФАЕЯОЦ”. Системы с ключевым словом или просто ключом, известные с века, широко применяются до сих пор. Их особенностью является два уровня секретности. Первый уровень — это собственно способ составления кода, который постоянно известен лицам, использующим данный шифр. Второй уровень — это ключ, который посылается отдельно от основного сообщения по особо защищенным каналами без которого расшифровка основного сообщения невозможна. Наиболее простой способ использования ключа хорошего шифра следующий под символами сообщения записывается раз за разом ключ, затем номера соответствующих знаков сообщения и ключа складываются. Если полученная сумма больше общего числа знаков, то от нее отнимается это общее число знаков. Полученные числа будут номерами символов кода. С ростом длины ключа трудоемкость дешифровки подобного шифра стремительно растет. Например, рассмотренное ранее сообщение с ключом КИБЕРНЕТИКА в шифрованном виде будет выглядеть как “ЮОРЦЪНОБЮЪСШЙШОЪ”. Процесс шифровки описывается схемой ТЕОРИЯ ИНФОРМАЦИИ КИБЕРНЕТИК АКИ БЕР12 10 2 6 18 15 6 20 10 12 1 12 10 2 6 18 32 16 18 24 28 15 16 2 32 28 19 26 11 26 16 Ю О Р Ц Ъ НО Б Ю Ъ С Ш Й Ш О Ъ. Если в качестве ключа использовать случайную последовательность, то получится нераскрываемый шифр. Проблема этого шифра это способ передачи ключа. В информационных сетях использование традиционных систем шифрования с ключом затрудненно необходимостью иметь специальный особо защищенный способ для передачи ключа. В 1976 году У. Диф- фи (Diffie W.) и М. Хеллман (Hellman M.) — инженеры-электрики из Станфордского университета, а также студент Калифорнийского университета Р. Меркль (Merkle R.), предложили новый принцип построения криптосистем, не требующий передачи ключа принимающему сообщение и сохранения втайне метода шифрования. В дальнейшем, в качестве примеров, рассмотрим три системы, основанные на идеях Диффи и Хеллмана: без передачи ключей, с открытым ключом и электронную подпись — все они в свою очередь основаны на математическом фундаменте теории чисел. Упражнение Зашифровать сообщение КИБЕРНЕТИКА ключом ДИСК. Криптосистема без передачи ключей Пусть абоненты A, B, C, . . . условились организовать между собой секретную переписку. Для этой цели они выбирают достаточно большое простое число p такое, что p − 1 хорошо разлагается на не очень большие простые множители. Затем каждый из абонентов независимо один от другого выбирает себе некоторое натуральное число, взаимно простое с p − 1. Пусть число абонента A — a, абонента B — b и т. д. Числа a, b, . . . составляют первые секретные ключи соответствующих абонентов. Вторые секретные ключи (α для A, β для B и т. д) находятся из уравнений для A из aα ≡ 1 (mod ϕ(p)), 0 < α < p − 1; для B — из bβ ≡ 1 (mod ϕ(p)), 0 < β < p − 1 и т. д. Пересылаемые сообщения, коды-числа, должны быть меньше p−1. В случае, когда сообщение больше или равно p−1, оно разбивается на части таким образом, чтобы каждая часть была числом, меньшим p − Предположим абонент A решил отправить сообщение m (m < p−1) B. Для этого он сначала зашифровывает свое сообщение ключом a, получая по формуле m 1 ≡ m a (mod p) шифрованное сообщение m 1 , которое отправляется B. B, получив m 1 , зашифровывает его своим ключом b, получая по формуле m 2 ≡ m b 1 (mod p) шифрованное сообщение которое отправляется обратно к A. A шифрует полученное сообщение ключом α по формуле m 3 ≡ m α 2 (mod p) и окончательно отправляет к B. B, используя ключ β, сможет теперь расшифровать исходное сообщение m. Действительно, m 4 ≡ m β 3 ≡ m aαbβ ≡ m (mod p), т. к ≡ 1 (mod ϕ(p)), следовательно, aαbβ = kϕ(p) + 1 для некоторого целого k и m kϕ(p)+1 ≡ (m ϕ(p) ) k m ≡ m (mod p), т. к. m ϕ(p) ≡ 1 (mod p) по теореме Эйлера-Ферма. Пример. Абоненты A и B вместе выбрали p = 23 (ϕ(23) = 22), выбрала. Затем из уравнения 5α ≡ 1 (mod ϕ(23)) A находит α = 9, а B из подобного уравнения находит β = 19. При передаче сообщения m = 17 от A к B сначала A отправляет к B m 1 ≡ 17 5 ≡ 21 (mod 23), из m 1 = 21 B вычисляет m 2 ≡ 21 7 ≡ 10 (mod и отправляет его обратно A, из m 2 = 10 A вычисляет для B m 3 ≡ 10 9 ≡ 20 (mod 23), наконец, B может прочитать посланное ему сообщение 19 ≡ 17 (mod Упражнение Между абонентами A и B установлен секретный канал связи без передачи ключей при заданных p = 167 и их первых ключах 15 и Описать процесс передачи сообщений 22 (от A к B) и 17 (от B к A). 30. Криптосистема с открытым ключом Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir A.) и Л. Адлеман (Adleman L.). По их именам эта система получила название Пусть абоненты A и B решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа (p A 1 , и p B 1 , p B 2 ), находит их произведение (и r B ), функцию Эйлера от этого произведения (ϕ(r A ) и и случайное число (a и b), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, A из уравнения aα ≡ 1 (mod ϕ(r A )) находит α (0 < α < ϕ(r A )), а B из уравнения bβ ≡ 1 (mod ϕ(r B )) находит β (0 < β < ϕ(r B )). Затем A и B печатают доступную всем книгу паролей вида r A , a B: r B , Теперь кто-угодно может отправлять конфиденциальные сообщения или B. Например, если пользователь книги паролей хочет отправить сообщение m для B (m должно быть меньшим r B , или делиться на куски, меньшие r B ), то он использует ключ b из книги паролей для получения шифрованного сообщения по формуле m 1 ≡ m b 73 (mod r B ), которое и отправляется B. B для дешифровки использует ключ β в формуле m β 1 ≡ m bβ ≡ m (mod r B ), т. к. bβ ≡ 1 (mod ϕ(r B )), следовательно, bβ = kϕ(r B ) + 1 для некоторого целого k и m kϕ(r B )+1 ≡ (m ϕ(r B ) ) k m ≡ m (mod r B ), т.к. m ϕ(r B ) ≡ 1 (mod r B ) по теореме Эйлера-Ферма. Доказано [12], что задача нахождения секретного ключа β поданным из книги паролей имеет туже сложность, что и задача разложения числа на простые множители. Пример. Пусть для A p A 1 = 7 и p A 2 = 23, тогда r A = p A 1 p A 2 = 161, ϕ(161) = 6 ∗ 22 = 132, a = 7, α = 19 (из уравнения 7α ≡ 1 (mod Следовательно, запись в книге паролей для A будет иметь вид A: 161, Если кто-то захочет отправить A секретное сообщение m = 3, то он должен сначала превратить его в шифровку по формуле m 1 ≡ 3 7 ≡ 94 (mod 161). Когда A получит m 1 = 94 он дешифрует его по формуле m ≡ 94 19 ≡ 3 (mod Упражнение Нужно послать секретные сообщения 25 и 2 для JB и 14 для используя следующие записи открытой книги паролей криптосистемы 77,7; CIA: Упражнение Пользователь системы RSA выбрали. Какие из чисел, 33, 125, 513 он может выбрать для открытого ключа Вычислить для них закрытый ключ. Упражнение Пользователь системы RSA, выбравший p 1 = 17, p 2 = 11 и a = получил шифрованное сообщение m 1 = 3. Дешифровать m 1 31. Электронная подпись Криптосистема с открытым ключом открыта для посылки сообщений для абонентов из книги паролей для любого желающего. В системе с электронной подписью сообщение необходимо подписывать, те. явно указывать на отправителя из книги паролей. Пусть W 1 , W 2 , . . . , W n — абоненты системы с электронной подписью. Все они независимо друг от друга выбирают и вычисляют ряд чисел точно также как ив системе с открытым ключом. Пусть i-ый абонент (1 = i n) выбирает два больших простых числа p и p затем вычисляет их произведение — r i = p i1 p и функцию Эйлера от него — ϕ(r i ), затем выбирает первый ключ a из условий 0 < a i < ϕ(r i ), НОД(a i , ϕ(r i )) = 1 и, наконец, вычисляет второй ключ α i из уравнения a i α i ≡ 1 (mod ϕ(r i )). Записи в книге паролей будут иметь вид W 1 : r 1 , a 1 W 2 : r 2 , a 2 · · · W n : r n , a Если абонент решает отправить секретное письмо m W 2 , то ему следует проделать следующую последовательность операций) Если m > min(r 1 , r 2 ), то m разбивается на части, каждая из которых меньше меньшего из чисел и r 2 ; 2) Если r 1 < r 2 , то сообщение m сначала шифруется ключом α 1 (m 1 ≡ m α 1 (mod r 1 )), а затем — ключом a 2 (m 2 ≡ m a 2 1 (mod r 2 )), если же r 1 > r 2 , то сообщение m сначала шифруется ключом a 2 (m 1 ≡ m a 2 (mod r 2 )), а затем — ключом α 1 (m 2 ≡ m α 1 1 (mod r 1 )); 3) Шифрованное сообщение отправляется для дешифровки сообщения должен знать, кто его отправил, поэтому к должна быть добавлена электронная подпись, указывающая на W 1 . Если r 1 < r 2 , то для расшифровки сначала применяется ключа затем — a 1 , если же r 1 > r 2 , то для расшифровки сначала применяется ключа затем — α |