Практикум по алгебре, теории чисел, элементам криптографии
Покупка
Основная коллекция
Издательство:
Инфра-Инженерия
Год издания: 2025
Кол-во страниц: 136
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-9729-2476-9
Артикул: 867185.01.99
Рассмотрены следующие темы: «Основные положения алгебры, теории чисел, элементов криптографии», «Теория делимости и непрерывные дроби», «Теория сравнений», «Элементы общей алгебры и теории многочленов», «Комплексные числа и элементы теории многочленов», «Элементы криптографии», «Эллиптические кривые», «Криптографические алгоритмы на основе эллиптических кривых». Каждая тема сопровождается примерами решения задач и заданиями для самостоятельной работы студента. Для студентов высших учебных заведений, обучающихся по укрупненным группам направлений подготовки и специальностей 10.00.00, 02.00.00, 09.00.00.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 02.03.01: Математика и компьютерные науки
- 02.03.02: Фундаментальная информатика и информационные технологии
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 10.03.01: Информационная безопасность
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
В. П. Добрица, Е. А. Кулешова, Ю. А. Халин ПРАКТИКУМ ПО АЛГЕБРЕ, ТЕОРИИ ЧИСЕЛ, ЭЛЕМЕНТАМ КРИПТОГРАФИИ Учебное пособие Москва Вологда «Инфра-Инженерия» 2025
УДК 511+512 ББК 22.13 Д55 Рецензенты: кандидат технических наук, доцент кафедры информационных технологий Белгородского государственного технологического университета им. В. Г. Шухова Косоногова Марина Александровна; доктор технических наук, профессор, главный научный сотрудник НИИЦ (г. Курск) ФГУП «18 ЦНИИ» МО РФ Сизов Александр Семенович Добрица, В. П. Д55 Практикум по алгебре, теории чисел, элементам криптографии : учебное пособие / В. П. Добрица, Е. А. Кулешова, Ю. А. Халин. – Москва ; Вологда : Инфра-Инженерия, 2025. – 136 с. : ил., табл. ISBN 978-5-9729-2476-9 Рассмотрены следующие темы: «Основные положения алгебры, теории чисел, элементов криптографии», «Теория делимости и непрерывные дроби», «Теория сравнений», «Элементы общей алгебры и теории многочленов», «Комплексные числа и элементы теории многочленов», «Элементы криптографии», «Эллиптические кривые», «Криптографические алгоритмы на основе эллиптических кривых». Каждая тема сопровождается примерами решения задач и заданиями для самостоятельной работы студента. Для студентов высших учебных заведений, обучающихся по укрупненным группам направлений подготовки и специальностей 10.00.00, 02.00.00, 09.00.00. УДК 511+512 ББК 22.13 ISBN 978-5-9729-2476-9 Добрица В. П., Кулешова Е. А., Халин Ю. А., 2025 Издательство «Инфра-Инженерия», 2025 Оформление. Издательство «Инфра-Инженерия», 2025
ОГЛАВЛЕНИЕ ПРЕДИСЛОВИЕ .......................................................................................................... 4 1. Основные положения алгебры, теории чисел, элементов криптографии ......... 6 1.1. Основные понятия теории чисел, используемые в криптографии ............... 6 1.2. Применение теории чисел в криптографии ..................................................... 8 2. Теория делимости и непрерывные дроби ........................................................... 13 2.1. Простые и составные числа, каноническое представление составного числа ......................................................................................................................... 13 2.2. Целая и дробная части числа. Функция Эйлера. Число и сумма делителей натурального числа ............................................................................... 16 2.3. Наибольший общий делитель и его линейное представление. Наименьшее общее кратное ................................................................................... 19 2.4. Цепные дроби ................................................................................................... 23 3. Теория сравнений .................................................................................................. 30 3.1. Числовые сравнения и их свойства ................................................................ 30 3.2. Различные системы вычетов по модулю ....................................................... 33 3.3. Сравнения первой степени и их решение ...................................................... 36 3.4. Системы сравнений. Первообразные корни и индексы ............................... 40 4. Элементы общей алгебры и теории многочленов ............................................. 50 4.1. Алгебраические структуры ............................................................................. 50 5. Комплексные числа и элементы теории многочленов ...................................... 66 5.1. Комплексные числа .......................................................................................... 66 5.2. Элементы теории многочленов ....................................................................... 79 6. Элементы криптографии. Эллиптические кривые. Криптографические алгоритмы на основе эллиптических кривых. .................... 92 6.1. Группы по сложению точек на эллиптических кривых над полем действительных чисел ............................................................................................. 92 6.1.1. Эллиптические кривые ............................................................................... 93 6.1.2. Геометрическое сложение .......................................................................... 94 6.1.3. Алгебраическое сложение .......................................................................... 96 6.1.4. Скалярное умножение ................................................................................ 98 6.1.5. Логарифм ...................................................................................................... 99 6.2. Группы по сложению точек на эллиптических кривых над конечными полями .................................................................................................................... 104 6.3. Криптографические алгоритмы на основе эллиптических кривых. ......... 123 6.3.1. Протокол Диффи – Хеллмана на эллиптических кривых. .................... 124 6.3.2. Реализация схемы цифровой подписи с помощью ECDSA. ................. 127 СПИСОК ЛИТЕРАТУРЫ ....................................................................................... 132
ПРЕДИСЛОВИЕ В современном мире нельзя переоценить роль средств коммуникаций и вычислительной техники, в том числе компьютерных и глобальных сетей. Развитие технологий приводит к возникновению все более сложных вольных или невольных атак на эти системы. Особенно это важно для компьютерной сферы, так как именно информационные системы подвергаются наибольшему количеству атак со стороны злоумышленников. Поэтому обеспечение безопасности этих систем и технологий становится архиактуальной задачей. Это естественно ставит задачу подготовки в достаточном количестве высококвалифицированных специалистов по информационной безопасности. Такие специалисты должны обладать глубокой фундаментальной подготовкой, без чего невозможно своевременно осваивать новые технологии, успешно разрабатывать системы, противостоящие возникающим новым атакам и рискам. Частью такой фундаментальной подготовки студентов по информационным технологиям и информационной безопасности и является курс «элементы алгебры и теории чисел». Данное пособие составлено в соответствии с Государственным образовательным стандартом высшего профессионального образования и содержит следующие разделы: 1. Основные положения алгебры, теории чисел, элементов криптографии. 2. Теория делимости и непрерывные дроби. 3. Теория сравнений. 4. Элементы общей алгебры и теории многочленов. 5. Комплексные числа и элементы теории многочленов. 6. Элементы криптографии. Эллиптические кривые. Криптографические алгоритмы на основе эллиптических кривых. В первом разделе рассмотрены основные инструменты теории чисел, такие как простые числа, делители, сравнения, функция Эйлера. Рассмотрены примеры применения теории чисел в криптографии. Во втором разделе рассмотрены следующие темы: теорема деления с остатком, свойства делимости чисел, простые и составные числа, НОД и НОК, целая и дробная часть числа, функция Эйлера, число и сумма делителей натурального числа, цепные дроби. В третьем разделе рассмотрены следующие темы: сравнение чисел, системы вычетов, свойства числовых сравнений, приложения числовых сравнений, сравнения с одним неизвестным, решения сравнений с неизвестным, системы сравнений с неизвестным и способы их решения, первообразные корни и индексы, нахождение первообразных корней и вычисление индексов. В четвертом разделе рассмотрены следующие темы: бинарные операции и их свойства. Полугруппы, моноиды, группы, подгруппы и их свойства. Полукольца, кольца, подкольца, идеалы кольца и их свойства. Поля, подполя, простые подполя и их свойства. Расширения полей. Гомоморфизм и изоморфизм алгебраических структур.
В пятом разделе рассмотрены следующие темы: определение комплексных чисел и основные операции над ними, алгебраическая и тригонометрическая запись комплексного числа, нахождение корней из комплексных чисел, кольцо многочленов над кольцом, кольцо многочленов над полем, алгебраически замкнутые поля, схема Горнера, решение уравнений 3 степени (формулы Кардано). В шестом разделе рассмотрены следующие темы: группы по сложению точек на эллиптических кривых над полем действительных чисел, группы по сложению точек на эллиптических кривых над конечными полями. Рассмотрены примеры использования групп точек на эллиптических кривых в криптографии. Материал каждого раздела изложен таким образом, что сначала вводятся основные понятия, перечисляются основные теоретические положения и формулы, затем рассматриваются решения типовых задач, что позволяет закрепить соответствующий материал и получить необходимые навыки. В каждом разделе даны варианты заданий для самостоятельной работы студентов. Практикум предназначен для студентов всех форм обучения (очной, заочной, очно-заочной).
1. ОСНОВНЫЕ ПОЛОЖЕНИЯ АЛГЕБРЫ, ТЕОРИИ ЧИСЕЛ, ЭЛЕМЕНТОВ КРИПТОГРАФИИ 1.1. Основные понятия теории чисел, используемые в криптографии Криптография – это наука о защите информации от несанкционированного доступа. Одним из самых распространенных методов защиты информации является шифрование, то есть преобразование исходного текста в непонятный для посторонних символьный ряд. Шифрование основывается на использовании различных математических алгоритмов, которые обеспечивают надежность защиты информации. Один из таких алгоритмов – это шифрование с открытым ключом, которое основано на использовании теории чисел [1]. Теория чисел – это раздел математики, который изучает свойства целых чисел и их взаимоотношения. Теория чисел применяется в различных областях математики, информатики и физики. Она предоставляет инструменты для решения сложных задач, связанных с простыми числами, алгебраическими структурами и аналитическими функциями [2]. Кроме того, теория чисел служит теоретической основой для разработки ряда криптографических алгоритмов и протоколов, которые обеспечивают защиту данных в современных информационных системах. [3]. Многие инструменты теории чисел, такие как простые числа, делители, сравнения, функция Эйлера, играют важную роль в асимметричной криптографии для генерации открытого и закрытого ключей для сокрытия информации. В данном разделе представлены основные понятия теории чисел, которые широко используются в асимметричной криптографии [4]. Простые числа Один из основных объектов изучения теории чисел – это простые числа. Простые числа – это целые числа, которые имеют только два делителя: единицу и само число [5]. Например: Простыми являются числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 … Делители Положительное целое число ࢞ делит целое число ࢟, если существует целое число ࢉ, такое что ࢞כ ࢉ ൌ ࢟ и записывается как ࢞ ȁ ࢟. Например: 3 | 15, так как 15 = כ , но 4 не делит 15, так как не существует целого числа ࢉ, такого, что 15 = כ ࢉ. Наибольший общий делитель Пусть ࢞ и ࢟ – два положительных целых числа, тогда целое число ࢊ называется наибольшим общим делителем ࢞ и ࢟, если ࢊ ȁ ࢞ и ࢊ ȁ ࢟, то есть ࢊ – общий делитель ࢞ и ࢟. И если любое целое число c таково, что ࢉ ȁ ࢞ и ࢉ ȁ ࢟, то ࢉ ȁ ࢊ, то есть любой другой общий делитель ࢞ и ࢟ будет делить ࢊ, это обозначается как ሺ࢞ǡ ࢟ሻ ൌ ࢊ.
Например: (25, 30) = 5. Два числа x и y называются взаимно простыми, если их наибольший общий делитель равен 1, то есть ሺ࢞ǡ ࢟ሻ ൌ . Например: 11 и 13 взаимно просты. Модульная арифметика Если два числа ࢇ и ࢈ дают одинаковые остатки при делении на положительное число ࡺ, то говорят, что они сравнимы по модулю ࡺ, и пишут ࢇ ؠ ࢈ ሺࢊ ࡺሻ. Эквивалентное определение: ࢇ и ࢈ сравнимы по модулю ࡺ, если разность ࢇ െ ࢈ делится на ࡺ. Например: a = 15, b = 3, тогда 15 mod 3 = 0 a = 15, b = 4, тогда 15 mod 4 = 3 Сравнение по модулю: Пусть ࢞ǡ ࢟ – два целых числа, а – любое положительное целое число, тогда говорят, что ࢞ сравнимо с y по модулю , если числа ࢞ и ࢟ имеют одинаковые остатки при делении на . Обозначается как ࢞ ؠ ࢟ ሺࢊ ሻ. Например: 29 Ł 8 (mod 7), 60 Ł 0 (mod 15). Свойства модулярности: ሺ࢞ሺࢊ ሻ࢟ ሺࢊ ሻሻࢊ ൌ ሺ࢞࢟ሻࢊ . ሺ࢞ሺࢊ ሻെ࢟ ሺࢊ ሻሻࢊ ൌ ሺ࢞െ࢟ሻࢊ . ሺ࢞ሺࢊ ሻכ ࢟ ሺࢊ ሻሻࢊ ൌ ሺ࢞כ ࢟ሻࢊ . Коммутативный закон: ሺ࢞࢟ሻࢊ ൌ ሺ࢟࢞ሻࢊ . ሺ࢞כ ࢟ሻࢊ ൌ ሺ࢟כ ࢞ሻࢊ . Закон тождества: ሺ࢞ሻ ࢊ ൌ ࢞ ࢊ . ሺכ ࢞ሻ ࢊ ൌ ࢞ ࢊ . Функция Эйлера «ሺܖሻ». Функция Эйлера «ሺܖሻ» определяется как ሺܖሻ = количество положительных целых чисел, меньших или равных n и являющихся взаимно простыми с , т. е. ሺܖሻ = количество положительных целых чисел «ࢇ», таких, что 1 ࢇ и НОД ሺࢇǡ ሻ ൌ . Например: (15) = 8, поскольку простые числа относительно 15 задаются как 1, 2, 4, 7, 8, 11, 13 и 14. И ሺܘܙሻ ൌ ሺܘሻሺܙሻ, где и являются взаимно простыми числами. Некоторые основные свойства конгруэнтности приведены ниже [6]: (1) ࢇؠ ࢈ሺࢊ ሻ тогда и только тогда, когда ࢈ؠ ࢇ ሺࢊ ሻ. (2) ࢇؠ ࢈ࢉ ሺࢊ ሻ тогда и только тогда, когда ࢇെࢉؠ ࢈ ሺࢊ ሻ. (3) ࢇؠ ࢈ሺࢊ ሻ и ࢇؠ ࢈ሺࢊ ሻ, тогда ࢇࢇؠ ࢈ ࢈ሺࢊ ሻ и ࢇെࢇؠ ࢈െ ࢈ሺࢊ ሻ. (4) ࢇؠ ࢈ ሺࢊ ሻ и ࢉ – любое целое число, тогда ࢉࢇؠ ࢉ࢈ሺࢊ ሻ. (5) ࢇ r ؠ ࢇሺࢊ ሻ, где – любое целое число.
1.2. Применение теории чисел в криптографии Криптография – это метод защиты информации и коммуникаций с помощью кодов, направленный на то, чтобы только те лица, которым адресованы данные, могли их изучать и обрабатывать. В более общем смысле, криптография – это создание и анализ соглашения, которое защищает стороны или общественность от чтения личных сообщений или информации [7]. В настоящее время методы и средства криптографии используются для обеспечения информационной безопасности как государства, так и частных лиц и организаций [8]. Криптография была создана в ответ на требования по обеспечению безопасной передачи информации по открытым каналам связи, к данной области относятся технологии шифрования и дешифрования информации, а также технологии взлома паролей [9]. При обеспечении защищенной передачи информации происходят следующие процессы: отправитель отправляет исходную информацию, известную как открытый текст, выполняет различные изменения или преобразования, известные как шифрование, и шифрует информацию – шифротекст, который отправляет получателю; получатель получает шифротекст, и шифротекст преобразуется обратно в открытый текст, что известно, как расшифровка. Раскодированный шифротекст является исходной формой сообщения. Во время передачи шифротекст может быть перехвачен злоумышленником, однако, не понимая алгоритма шифрования, злоумышленник не сможет понять исходную информацию на основе перехваченного шифротекста. Процесс извлечения злоумышленником открытого текста из зашифрованного называется взломом или дешифрованием [10]. Криптография относится к областям математики. Она делится на следующие классы: Первый – методы обеспечения защищенной передачи информации по каналам связи, то есть преобразование исходной информации к виду, затрудняющему ее взлом злоумышленниками (шифрование). Второй – перехват зашифрованного текста и его расшифровка для получения полезной исходной информации (криптографический анализ). Первый аспект известен как криптография или кодирование. Второй аспект известен как криптоанализ. Эти два компонента составляют криптографию в целом. Кодирование и криптоанализ иногда называют науками-близнецами или взаимными науками. Целью первой категории является разработка криптографических подходов, которые повышают безопасность шифрования. Целью второй категории является разработка подходов, направленных на раскрытие содержания шифротекста. Оба взаимно противоречат друг другу, дополняют друг друга и развиваются совместно [11]. Термин «криптосистема» относится к алгоритму шифрования и набору оборудования, используемого для выполнения шифрования. Основная концепция криптографической системы заключается в шифровании информации или данных с целью обеспечения конфиденциальности информации для того, чтобы злоумышленник не смог понять ее значение в случае перехвата [12]. Криптография в целом подразделяется на три основных типа: 1. Криптография с симметричным ключом. Криптография с симметричным ключом также называется симметричным шифрованием или симметрич
ной криптосистемой. Это система шифрования, в которой отправитель и получатель сообщения используют один общий ключ для шифрования и расшифровывания сообщений [13]. Субъекты, взаимодействующие посредством симметричного шифрования, должны обменяться ключом, чтобы его можно было использовать в процессе расшифровки. 2. Хэш-функции. В этом алгоритме не используется ключ. Хэш-функция – это достижимое отображение из набора всех двоичных последовательностей в набор двоичных последовательностей некоторой фиксированной длины [14]. Хэш-функция – это арифметическая функция, которая преобразует математическое входное значение в другое сжатое математическое значение. Входные данные для хэш-функции имеют случайную длину, но выходные данные всегда имеют постоянную длину. 3. Асимметричное шифрование. Это метод шифрования данных, предполагающий использование двух ключей – открытого и закрытого. Открытый (публичный) ключ применяется для шифрования информации и может передаваться по незащищенным каналам [15]. Протокол Диффи-Хеллмана был одной из первых изобретенных криптосистем с асимметричными ключами. Асимметричная криптография с ключом также называется криптографией с открытым ключом. Асимметричная криптография с ключом включает пару ключей, известных как открытый ключ и закрытый ключ, которые связаны с субъектом, которому необходимо подтвердить свою личность в электронном виде, подписать или зашифровать данные. Каждый открытый ключ публикуется, а соответствующий закрытый ключ хранится в секрете. Данные, зашифрованные с помощью открытого ключа, могут быть расшифрованы только с помощью соответствующего закрытого ключа [16]. Необходимость конфиденциальности существовала всегда [17]. Асимметричная криптография обеспечивает конфиденциальность и лучшую безопасность, поскольку использует два разных ключа – открытый ключ, который используется только для шифрования сообщений, что делает его безопасным для всех, и закрытый ключ для расшифровки сообщений, который никогда не передается другим. Криптография с использованием шифра Цезаря Метод шифра Цезаря является одним из самых основных и простейших методов шифрования. Это тип шифра замены, который также называется шифром сдвига или аддитивным шифром. В этом методе каждая буква алфавита заменяется буквой, стоящей на три (или любое другое фиксированное число), позиции ниже в алфавите. Например: при сдвиге A на 3, A будет заменена на D, B станет E и так далее. Таким образом, для шифрования заданного текста нам требуется целочисленное значение, известное как сдвиг, которое показывает номер позиции, на которую каждая буква текста была перемещена вниз. Шифрование можно представить с помощью модульного вычисления, сначала преобразовав буквы в числа в соответствии со схемой (табл. 1.1), A = 0, B = 1, C = 3, Z = 25. Алгоритм. Для открытого текста мы используем букву P, а для зашифрованного текста – C.
ܥ ൌ ܧሺܲǡ ݇ሻ ݉݀ ʹ ൌ ሺܲ݇ሻ ݉݀ ʹ (E = шифрование, k = 3 = ключ в шифре Цезаря в английском алфавите). ܲ ൌ ܦሺܥǡ ݇ሻ ݉݀ ʹ ൌ ሺܥ െ ݇ሻ ݉݀ ʹ (D = расшифровка, k = 3 = ключ в шифре Цезаря). Таблица 1.1 Схема преобразования букв в числа A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Пример: зашифровать слово «conference» с помощью шифра Цезаря. Решение (табл. 1.2): Таблица 1.2 Схема зашифровывания для текста «conference» P c o n f e r e n c e C F R Q I H U U Q F H Так как шифрование ܥ ൌ ሺܲ͵ሻ ݉݀ ʹ, то для «conference» c (2): ܥ ൌ ሺܲ͵ሻ݉݀ ʹ ൌ ሺʹ ͵ሻ݉݀ ʹ ൌ ͷ ݉݀ ʹ ൌ ͷ; C = 5; C = F. Для o(14): ܥ ൌ ሺܲ͵ሻ݉݀ ʹ ൌ ሺͳͶ ͵ሻ ʹ ൌ ͳ ʹ ൌ ͳ; C = 17; C = R. Открытый текст (P): conference. Зашифрованный текст (C): FRQIHUHQFH. Расшифровка (табл. 1.3): Таблица 1.3 Схема расшифровывания для текста «FRQIHUHQFH» C F R Q I H U U Q F H P c o n f e r e n c e Так как расшифровывание ܲ ൌ ሺܥെ͵ሻ ݉݀ ʹ, то для F(5): ܲ ൌ ሺܥെ͵ሻ݉݀ ʹ ൌ ሺͷ െ͵ሻ ʹ ൌ ʹ; P = 2; P = c.