Алгебра и теория чисел для криптографии: учебное пособие

Description

Основная цель пособия — подготовить математическую базу для чтения дисциплин, связанных с криптографическими методами защиты информации, в которых находят применение многие разделы алгебры и теории чисел. Особое внимание в пособии уделяется наиболее востребованным в криптографии вопросам делимости и сравнимости целых чисел, а также конечным алгебраическим объектам — конечным группам, кольцам и полям; многочленам и матрицам над конечными кольцами и полями и др. Кроме этого, пособие содержит дополнительные сведения из алгебры и теории чисел, необходимые для развития весьма актуальной в настоящее время криптографии на эллиптических кривых над конечными полями, а также содержит примеры применения алгебры и теории чисел в криптографии. Понятия и многие факты широко иллюстрируются примерами. В конце всех разделов приводятся контрольные вопросы и задания. Пособие предназначено обучающимся по направлениям бакалавриата и специалитета «Информационная безопасность». Оно может быть использовано обучающимися по направлению бакалавриата «Педагогическое образование» (профиль «Математическое образование»), так как охватывает содержание большинства разделов дисциплины «Алгебра и теория чисел». ПРЕДИСЛОВИЕ......Page 3 КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ МНОЖЕСТВ И МАТЕМАТИЧЕСКОЙ ЛОГИКИ......Page 7 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ......Page 13 1.1. Метод математической индукции......Page 14 1.2.1. Правило суммы......Page 20 1.2.2. Правило произведения......Page 21 1.2.3. Размещения с повторениями......Page 23 1.2.5. Число подмножеств конечного множества......Page 24 1.3. Правило исключений и включений......Page 25 1.4.1. Размещения без повторений......Page 28 1.4.2. Перестановки без повторений......Page 29 1.4.3. Сочетания без повторений......Page 30 1.4.4. Свойства сочетаний......Page 31 1.4.6. Свойства треугольника Паскаля......Page 32 1.5. Бином Ньютона......Page 33 1.5.1. Свойства биномиальных коэффициентов......Page 35 1.6.1 Перестановки с повторениями......Page 36 1.6.2. Сочетания с повторениями......Page 38 1.7.1. Понятие инверсии в перестановке......Page 39 1.7.2. Инверсии, их число и четность перестановок......Page 40 1.7.3. Подстановки и их четность......Page 41 2.1.1. Понятие бинарной алгебраической операции......Page 44 2.1.2. Основные свойства бинарных алгебраических операций......Page 47 2.2.1. Понятия полугруппы и моноида......Page 50 2.2.2. Свободные полугруппы......Page 52 2.2.3. Полугруппы преобразований......Page 53 2.3.1. Понятие группы и его простейшие свойства......Page 54 2.3.2. Симметрическая и знакопеременная группы подстановок n-й степени......Page 57 2.4.1. Понятие кольца и его простейшие свойства......Page 58 2.4.2. Простейшие свойства колец......Page 60 2.4.4. Простейшие свойства делимости в коммутативном кольце с единицей......Page 63 2.4.5. Основные понятия, связанные с делимостью в коммутативном кольце с единицей......Page 64 2.5.2. Простейшие свойства полей......Page 66 2.6.2. Свойства изоморфизма алгебраических структур......Page 68 2.6.3. Изоморфизм полугрупп, моноидов и групп......Page 69 2.6.4. Изоморфизм колец и полей......Page 71 2.7. Подструктуры......Page 72 2.7.1. Подполугруппы, подмоноиды и подгруппы......Page 73 2.7.2. Циклические подгруппы и группы......Page 74 2.7.3. Подкольца и подполя......Page 79 2.7.4. Поля частных областей целостности......Page 81 2.7.5. Характеристика кольца и поля......Page 82 3. ДЕЛИМОСТЬ ЦЕЛЫХ ЧИСЕЛ......Page 84 3.1.1. Алгоритм Евклида нахождения НОДа целых чисел......Page 85 3.1.2. Линейное представление наибольшего общего делителя целых чисел и свойства взаимно простых чисел......Page 88 3.1.3. Свойства взаимно простых чисел......Page 89 3.2. Наименьшее общее кратное целых чисел......Page 90 3.3. Простые числа......Page 91 3.3.1. Свойства простых чисел......Page 92 3.3.2. Разложение натуральных чисел в произведение простых чисел......Page 93 3.3.3. Число и сумма натуральных делителей числа......Page 95 3.4. Открытые проблемы теории делимости целых чисел......Page 96 4.1.1. Понятие сравнения по данному модулю......Page 102 4.1.2. Простейшие свойства сравнений......Page 103 4.2. Полная система вычетов по модулю......Page 105 4.3.1. Понятие функции Эйлера и ее основные свойства......Page 107 4.3.2. Приведенная система вычетов по данному модулю......Page 110 4.3.3. Теоремы Эйлера и Ферма......Page 111 4.4. Кольца и поля классов вычетов целых чисел......Page 112 4.5. Примеры использования теории сравнений в криптографии......Page 115 4.5.1. Аффинный и сдвиговый шифры......Page 118 4.5.2. Шифр Виженера......Page 122 4.5.3. Криптосистема RSA с открытым ключом......Page 126 4.5.4. Электронные цифровые подписи......Page 134 5.1. Построение поля комплексных чисел......Page 142 5.2. Действия над комплексными числами в алгебраической форме......Page 144 5.3.1. Тригонометрическая форма комплексного числа......Page 146 5.3.2. Умножение и деление комплексных чисел в тригонометрической форме......Page 150 5.3.4. Извлечение корня из комплексных чисел в тригонометрической форме......Page 152 5.3.5. Корни n-й степени из единицы......Page 153 5.3.6. Свойства корней n-й степени из единицы......Page 155 5.3.7. Показательная форма комплексного числа......Page 156 6.1. Построение кольца многочленов от одной переменной......Page 157 6.2.1. Деление многочленов с остатком......Page 160 6.2.2. Наибольший общий делитель многочленов......Page 166 6.2.3. Линейное представление наибольшего общего делителя многочленов......Page 169 6.2.4. Свойства взаимно простых многочленов......Page 170 6.2.5. Наименьшее общее кратное многочленов......Page 171 6.3.1. Понятия приводимого и неприводимого многочленов......Page 172 6.3.2. Свойства неприводимых многочленов над полем......Page 173 6.3.3. Разложение многочленов в произведение неприводимых многочленов......Page 174 6.4.1. Понятие производной многочлена......Page 177 6.4.3. Формула Тейлора......Page 178 6.4.4. Кратные неприводимые множители......Page 180 6.5. Рациональные дроби......Page 181 6.6. Многочлены над полем комплексных чисел......Page 184 6.7. Многочлены над полем действительных чисел......Page 186 6.8.1. Целые и рациональные корни многочленов с рациональными коэффициентами......Page 188 6.8.2. Признаки приводимости и неприводимости в кольце Q[x]......Page 191 6.9.1. Формулы для нахождения корней кубических уравнений......Page 194 6.9.2. Исследование кубических уравнений с действительными коэффициентами......Page 199 6.9.3. Уравнения четвертой степени......Page 201 7.1.1. Понятие алгебраического сравнения от одной переменной......Page 205 7.1.2. Понятие равносильности алгебраических сравнений и его свойства......Page 207 7.2.1. Сравнения первой степени......Page 209 7.2.2. Методы решения сравнений первой степени......Page 211 7.2.3. Системы сравнений первой степени......Page 212 7.3. Сравнения по простому модулю......Page 215 7.4. Показатели и первообразные корни......Page 217 7.4.1. Показатели и их свойства......Page 218 7.4.2. Первообразные корни по простому модулю......Page 221 7.4.3. Первообразные корни по составному модулю......Page 223 7.5.1. Понятие дискретного логарифма и его свойства......Page 227 7.5.2. Дискретные логарифмы по простому модулю......Page 230 7.5.3. Дискретные логарифмы по составному модулю......Page 232 7.6. Двучленные сравнения......Page 234 7.7.1. Символ Лежандра......Page 237 7.7.2. Символ Якоби......Page 241 7.8.1. Криптосистема с открытым ключом Эль-Гамаля......Page 247 7.8.2. Цифровая подпись Эль-Гамаля......Page 250 7.8.3. Протокол Диффи – Хеллмана открытого распределения ключей......Page 252 8. МАТРИЦЫ, ОПРЕДЕЛИТЕЛИ И СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ......Page 253 8.1. Операции над матрицами и их свойства......Page 254 8.2.1. Понятие определителя и его свойства......Page 260 8.2.2. Миноры и алгебраические дополнения......Page 270 8.3. Вычисление обратной матрицы с помощью определителей......Page 276 8.4. Решение квадратных систем линейных уравнений......Page 278 8.5. Ранг матрицы......Page 282 8.6. Исследование и решение систем линейных уравнений......Page 286 8.6.1. Исследование и решение систем линейных уравнений методом последовательного исключения переменных......Page 287 8.6.2. Критерий совместности систем линейных уравнений......Page 294 8.6.3. Свойства решений однородной системы......Page 296 8.6.4. Фундаментальный набор решений однородной системы......Page 297 8.7.1. Шифр Хилла......Page 303 9. ВЕКТОРНЫЕ ПРОСТРАНСТВА......Page 307 9.1. Определение и простейшие свойства векторного пространства......Page 308 9.2.1. Понятие подпространства......Page 311 9.2.2. Операции над подпространствами......Page 312 9.2.3. Линейная оболочка векторов пространства......Page 313 9.2.4. Понятие линейного многообразия......Page 314 9.2.5. Свойства линейных многообразий......Page 315 9.3.1. Понятия линейной зависимости и независимости векторов......Page 317 9.3.2. Простейшие свойства линейной зависимости и независимости векторов......Page 318 9.4.1. Понятия размерности и базиса векторного пространства......Page 322 9.4.2. Размерность линейной оболочки конечной системы векторов......Page 326 9.4.3. Размерность суммы и пересечения двух подпространств......Page 328 9.5.1. Понятие координаты вектора в базисе и его свойства......Page 330 9.5.2. Преобразование координат при изменении базиса......Page 332 9.6. Изоморфизм векторных пространств......Page 334 10.1. Понятия скалярного умножения и евклидова пространства......Page 337 10.2. Длина вектора и угол между векторами......Page 340 10.3. Процесс ортогонализации......Page 343 10.4. Ортогональное дополнение подпространства......Page 347 10.5. Изоморфизм евклидовых пространств......Page 349 11.1. Понятие линейного преобразования и его матрицы......Page 351 11.2. Связь между координатами вектора и его образа......Page 355 11.3. Связь между матрицами линейного преобразования в различных базисах......Page 356 11.4. Алгебра линейных преобразований......Page 358 11.5. Образ и ядро линейного преобразования......Page 363 11.6.1. Понятия собственного вектора и собственного значения линейного преобразования......Page 367 11.6.2. Свойства собственных векторов и собственных значений линейного преобразования......Page 368 11.6.3. Существование и нахождение собственных значений и собственных векторов линейных преобразований......Page 370 11.6.4. Практический способ нахождения собственных значений и собственных векторов линейных преобразований......Page 372 11.6.5. Возможность приведения матрицы линейного преобразования к диагональному виду......Page 375 11.6.6. Алгоритм нахождения базиса, в котором матрица преобразования имеет диагональный вид......Page 376 12. ГРУППЫ......Page 379 12.1. Смежные классы группы по подгруппе......Page 380 12.2.1. Нормальные делители групп......Page 383 12.2.2. Фактор-группы по нормальным делителям......Page 385 12.3. Гомоморфизмы групп......Page 387 12.4. Конечные абелевы группы......Page 391 12.4.1. Прямые суммы абелевых групп......Page 392 12.4.2. Разложение конечных абелевых групп в прямую сумму примарных групп......Page 394 12.4.3. Разложение конечных абелевых групп в прямую сумму циклических примарных групп......Page 398 13. КОЛЬЦА......Page 401 13.1. Идеалы колец......Page 402 13.2.1. Сравнение по идеалу и его свойства......Page 404 13.2.2. Фактор-кольца......Page 405 13.2.3. Кольца вычетов многочленов......Page 406 13.3. Гомоморфизмы колец......Page 409 14. ПОЛЯ......Page 412 14.1.1. Простые поля......Page 413 14.1.2. Символическое присоединение корня......Page 414 14.2.1. Описание конечных полей......Page 417 14.2.2. Алгоритм построения конечного поля порядка pn......Page 420 15. Группы точек на эллиптических кривых......Page 424 15.1. Группы точек на вещественных эллиптических кривых......Page 425 15.2. Группы точек на эллиптических кривых над любыми полями......Page 429 15.3. Группы точек на эллиптических кривых над конечными полями......Page 432 15.5.1 Аналог криптосистемы RSA на эллиптических кривых......Page 434 15.5.2. Протокол Диффи – Хеллмана открытого распределения ключей на эллиптических кривых......Page 437 ЛИТЕРАТУРА......Page 439 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ......Page 444