Программно-технические меры, то есть меры, направленные на контроль компьютерных сущностей - оборудования, программ и/или данных, образуют последний и самый важный рубеж информационной безопасности. Напомним, что ущерб наносят в основном действия ле­гальных пользователей, по отношению к которым процедурные регулято­ры малоэффективны. Главные враги - некомпетентность и неаккурат­ность при выполнении служебных обязанностей, и только программно-технические меры способны им противостоять.

Компьютеры помогли автоматизировать многие области человечес­кой деятельности. Вполне естественным представляется желание возло­жить на них и обеспечение собственной безопасности. Даже физическую защиту все чаще поручают не охранникам, а интегрированным компью­терным системам, что позволяет одновременно отслеживать перемещения сотрудников и по организации, и по информационному пространству.

Следует, однако, учитывать, что быстрое развитие информационных технологий не только предоставляет обороняющимся новые возможнос­ти, но и объективно затрудняет обеспечение надежной защиты, если опираться исключительно на меры программно-технического уровня. При­чин тому несколько:

повышение быстродействия микросхем, развитие архитектур с высокой степенью параллелизма позволяет методом грубой си­лы преодолевать барьеры (прежде всего, криптографические), ранее казавшиеся неприступными;

развитие сетей и сетевых технологий, увеличение числа связей между информационными системами, рост пропускной спо­собности каналов расширяют круг злоумышленников, имею­щих техническую возможность организовывать атаки;

появление новых информационных сервисов ведет и к образо­ванию новых уязвимых мест как «внутри» сервисов, так и на их стыках;

конкуренция среди производителей программного обеспече­ния заставляет сокращать сроки разработки, что приводит к снижению качества тестирования и выпуску продуктов с де­фектами защиты;

навязываемая потребителям парадигма постоянного наращива­ния мощности аппаратного и программного обеспечения не позволяет долго оставаться в рамках надежных, апробирован­ных конфигураций и, кроме того, вступает в конфликт с бюд­жетными ограничениями, из-за чего снижается доля ассигно­ваний на безопасность.

Перечисленные соображения лишний раз подчеркивают важность комплексного подхода к информационной безопасности, а также необхо­димость гибкой позиции при выборе и сопровождении программно-тех­нических регуляторов.

Центральным для программно-технического уровня является поня­тие сервиса безопасности.

Следуя объектно-ориентированному подходу, при рассмотрении ин­формационной системы с единичным уровнем детализации мы увидим совокупность предоставляемых ею информационных сервисов. Назовем их основными. Чтобы они могли функционировать и обладали требуемы­ми свойствами, необходимо несколько уровней дополнительных (вспо­могательных) сервисов - от СУБД и мониторов транзакций до ядра опе­рационной системы и оборудования.

К вспомогательным относятся сервисы безопасности (мы уже сталки­вались с ними при рассмотрении стандартов и спецификаций в области ИБ); среди них нас в первую очередь будут интересовать универсальные, высокоуровневые, допускающие использование различными основными и вспомогательными сервисами. Далее мы рассмотрим следующие сервисы:

идентификация и аутентификация;

управление доступом;

протоколирование и аудит;

шифрование;

контроль целостности;

экранирование;

анализ защищенности;

обеспечение отказоустойчивости;

обеспечение безопасного восстановления;

туннелирование;

Для обеспечения защиты от сетевых атак наиболее широко используемым и эффективным является установка :

1. Комплексных систем защиты класса ЗАСТАВА , обеспечивающих защиту корпоративных информационных систем на сетевом уровне с помощью технологий виртуальных частных сетей (Virtual Private Networks - VPN) и распределенного межсетевого экранирования (МЭ, FW).

2. Широкополосный аппаратный IP-шифратор класса "Заслон" - это отечественный магистральный широкополосный аппаратный IP-шифратор, предназначенный для криптографической защиты информации в современных телекоммуникационных системах.

3. Средств комплексной защиты информации - СЗИ ОТ НСД Secret Net 7 .

Рассмотрим данные продукты более подробно.

Продукты ЗАСТАВА работают на различных аппаратных платформах, под управлением многих популярных операционных систем. Они используются как в крупных, территориально распределенных системах, где одновременно работают тысячи агентов ЗАСТАВА, так и в системах малого и среднего бизнеса, где необходима защита всего для нескольких компьютеров. Программный комплекс "VPN/FW "ЗАСТАВА", версия 5.3, обеспечивает защиту корпоративных информационно-вычислительных ресурсов на сетевом уровне с помощью технологий виртуальных частных сетей (Virtual Private Networks - VPN) и распределенного межсетевого экранирования (МЭ).

ЗАСТАВА 5.3 обеспечивает:

· защиту отдельных компьютеров, в том числе мобильных, от атак из сетей общего пользования и Интернет;

· защиту корпоративной информационной системы или ее частей от внешних атак;

Сертифицированная ФСБ РФ версия продукта предоставляет заказчикам готовое решение, позволяющее органично интегрировать продукт в любые информационные системы без необходимости получения дополнительных заключений о правильности встраивания и обеспечивающее полную легитимность его использования для защиты конфиденциальной информации, включая персональные данные. Срок действия сертификатов с 30 марта 2011 г. по 30 марта 2014 г.

Шифратор Заслон - это полностью аппаратное решение. Все криптографические функции и сетевое взаимодействие реализованы в нём схемотехническими, а не программными методами. Выбор аппаратной реализации, в отличие от распространенных устройств (криптомаршрутизаторов), базирующихся на ПЭВМ общего назначения, обусловлен необходимостью преодоления ограничений архитектуры таких ЭВМ. Это, в первую очередь, ограничения общей шины, к которой подключаются сетевые интерфейсные карты. Несмотря на высокую скорость работы современных шин PCI и PCI-X, особенности работы сетевых шифраторов (коррелированные во времени прием и передача пакета со сдвигом на время зашифрования/расшифрования) не позволяют использовать всю их пропускную способность.

В общем, если требуется объединить локальные вычислительные сети незащищенными каналами связи, не опасаясь нарушения конфиденциальности данных при передаче и не тратя значительных усилий на обеспечение совместимости приложений при работе по шифрованным каналам. Заслон выполнен в виде "прозрачного" с точки зрения сети устройства. По этой причине в большинстве случаев достаточно только сконфигурировать шифратор и включить его "в разрыв" соединения защищаемой локальной сети с внешним каналом связи.

СЗИ ОТ НСД Secret Net 7 предназначена для предотвращения несанкционированного доступа к рабочим станциям и серверам, работающим в гетерогенных локальных вычислительных сетях . Система дополняет своими защитными механизмами стандартные защитные средства операционных систем и тем самым повышает защищенность всей автоматизированной информационной системы предприятия в целом, обеспечивая решение следующих задач:

v управление правами доступа и контроль доступа субъектов к защищаемым информационным, программным и аппаратным ресурсам;

v управление доступом к конфиденциальной информации, основанное на категориях конфиденциальности;

v шифрование файлов, хранящихся на дисках;

v контроль целостности данных;

v контроль аппаратной конфигурации;

v дискреционное управление доступом к устройствам компьютера;

v регистрация и учет событий, связанных с информационной безопасностью;

v мониторинг состояния автоматизированной информационной системы;

v ролевое разделение полномочий пользователей;

v аудит действий пользователей (в том числе администраторов и аудиторов);

v временная блокировка работы компьютеров;

v затирание остаточной информации на локальных дисках компьютера.

Система Secret Net 7 состоит из трех функциональных частей:

· защитные механизмы, которые устанавливаются на все защищаемые компьютеры автоматизированной системы (АС) и представляют собой набор дополнительных защитных средств, расширяющих средства безопасности ОС Windows.

· средства управления защитными механизмами, которые обеспечивают централизованное и локальное управление системой.

· средства оперативного управления, которые выполняют оперативный контроль (мониторинг, управление) рабочими станциями, а также централизованный сбор, хранение и архивирование системных журналов.

Secret Net 7 состоит из трёх компонентов:

1. СЗИ Secret Net 7 - Клиент. Устанавливается на все защищаемые компьютеры. В состав этого ПО входят следующие компоненты:

· Защитные механизмы - совокупность настраиваемых программных и аппаратных средств, обеспечивающих защиту информационных ресурсов компьютера от несанкционированного доступа, злонамеренного или непреднамеренного воздействия.

· Модуль применения групповых политик.

· Агент сервера безопасности.

· Средства локального управления - это штатные возможности операционной системы, дополненные средствами Secret Net 7 для управления работой компьютера и его пользователей, а также для настройки защитных механизмов.

2. СЗИ Secret 7 - Сервер безопасности. Включает в себя:

· Собственно сервер безопасности.

· Средства работы с базой данных (БД).

3. СЗИ Secret Net 7 - Средства управления. Включает в себя:

· Программу "Монитор". Эта программа устанавливается на рабочем месте администратора оперативного управления - сотрудника, уполномоченного контролировать и оперативно корректировать состояние защищаемых компьютеров в режиме реального времени.

В фирме требуется внедрение аналогичных технологий.





План:

Введение

• 1 Постановка задачи
• 2 Пример
• 3 Алгоритмы решения
  • 3.1 В произвольной мультипликативной группе
  • 3.2 В кольце вычетов по простому модулю
    • 3.2.1 Алгоритмы с экспоненциальной сложностью
    • 3.2.2 Субэкспоненциальные алгоритмы
  • 3.3 В произвольном конечном поле
  • 3.4 В группе точек на эллиптической кривой
• 4 Вычислительная сложность и приложения в криптографии



Введение

Дискретное логарифмирование (DLOG) – задача обращения функции g x в некоторой конечной мультипликативной группе G .

Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.

Для заданных g и a решение x уравнения g x = a называется дискретным логарифмом элемента a по основанию g . В случае, когда G является мультипликативной группой кольца вычетов по модулю m , решение называют также индексом числа a по основанию g . Индекс числа a по основанию g гарантированно существует, если g является первообразным корнем по модулю m .




1. Постановка задачи

Пусть в некоторой конечной мультипликативной абелевой группе G задано уравнение

Решение задачи дискретного логарифмирования состоит в нахождении некоторого целого неотрицательного числа x , удовлетворяющего уравнению (1). Если оно разрешимо, у него должно быть хотя бы одно натуральное решение, не превышающее порядок группы. Это сразу даёт грубую оценку сложности алгоритма поиска решений сверху - алгоритм полного перебора нашел бы решение за число шагов не выше порядка данной группы.

Чаще всего рассматривается случай, когда , то есть группа является циклической, порождённой элементом g . В этом случае уравнение всегда имеет решение. В случае же произвольной группы вопрос о разрешимости задачи дискретного логарифмирования, то есть вопрос о существовании решений уравнения (1), требует отдельного рассмотрения.




2. Пример

Проще всего рассмотреть задачу дискретного логарифмирования в кольце вычетов по модулю простого числа.

Пусть задано сравнение

Будем решать задачу методом перебора. Выпишем таблицу всех степеней числа 3. Каждый раз мы вычисляем остаток от деления на 17 (например, 3 3 ≡27 - остаток от деления на 17 равен 10).

Теперь легко увидеть, что решением рассматриваемого сравнения является x=4 , поскольку 3 4 ≡13.

На практике модуль обычно является достаточно большим числом, и метод перебора является слишком медленным, поэтому возникает потребность в более быстрых алгоритмах.




3. Алгоритмы решения

3.1. В произвольной мультипликативной группе

Разрешимости и решению задачи дискретного логарифмирования в произвольной конечной абелевой группе посвящена статья J. Buchmann, M. J. Jacobson и E. Teske. В алгоритме используется таблица, состоящая из пар элементов и выполняется умножений. Данный алгоритм медленный и не пригоден для практического использования. Для конкретных групп существуют свои, более эффективные, алгоритмы.




3.2. В кольце вычетов по простому модулю

Рассмотрим уравнение

где p - простое, b не делится на p . Если a является образующим элементом группы , то уравнение (2) имеет решение при любых b . Такие числа a называются ещё первообразными корнями, и их количество равно φ(p − 1) , где φ - функция Эйлера. Решение уравнения (2) можно находить по формуле:

Однако, сложность вычисления по этой формуле хуже, чем сложность перебора.

Следующий алгоритм имеет сложность

Алгоритм

Конец алгоритма

Существует также множество других алгоритмов для решения задачи дискретного логарифмирования в поле вычетов. Их принято разделять на экспоненциальные и субэкспоненциальные. Полиномиального алгоритма для решения этой задачи пока не существует.




3.2.1. Алгоритмы с экспоненциальной сложностью




3.2.2. Субэкспоненциальные алгоритмы

Данные алгоритмы имеют сложность арифметических операций, где и - некоторые константы. Эффективность алгоритма во многом зависит от близости c к 1 и d - к 0.

Наилучшими параметрами в оценке сложности на данный момент является , .

Для чисел специального вида результат можно улучшить. В некоторых случаях можно построить алгоритм, для которого константы будут , . За счёт того, что константа c достаточно близка к 1, подобные алгоритмы могут обогнать алгоритм с .




3.3. В произвольном конечном поле

Задача рассматривается в поле GF(q) , где q = p n , p - простое.




3.4. В группе точек на эллиптической кривой

Рассматривается группа точек эллиптической кривой над конечным полем. В данной группе определена операция сложения двух точек. Тогда m P - это . Решением задачи дискретного логарифмирования на эллиптической кривой является нахождение такого натурального числа m , что

для заданных точек P и A .

До 1990 года не существовало алгоритмов дискретного логарифмирования, учитывающих особенностей строения группы точек эллиптической кривой. Впоследствии, Менезес (Alfred J. Menezes), Окамото (Tatsuaki Okamoto) и Венстон (Scott A. Vanstone) предложили алгоритм, использующий спаривание Вейля. Для эллиптической кривой, определённой над полем G F (q ) , данный алгоритм сводит задачу дискретного логарифмирования к аналогичной задаче в поле G F (q k ) . Однако, данное сведение полезно, только если степень k мала. Это условие выполняется, в основном, для суперсингулярных эллиптических кривых. В остальных случаях подобное сведение практически никогда не приводит к субэкспоненциальным алгоритмам.




4. Вычислительная сложность и приложения в криптографии

Задача дискретного логарифмирования является одной из основных задач, на которых базируется криптография с открытым ключом. Идея, лежащая в основе подобных систем, опирается на высокую вычислительную сложность обращения некоторых числовых функций. В данном случае, операция дискретного логарифмирования является обратной к показательной функции. Последняя вычисляется достаточно просто, в то время как даже самые современные алгоритмы вычисления дискретного логарифма имеют очень высокую сложность, которая сравнима со сложностью наиболее быстрых алгоритмов разложения чисел на множители.

Другая возможность эффективного решения задачи вычисления дискретного логарифма связана с квантовыми вычислениями. Теоретически доказано, что, используя их, дискретный логарифм может быть вычислен за полиномиальное время . В любом случае, если полиномиальный алгоритм вычисления дискретного логарифма будет реализован, это будет означать практическую непригодность криптосистем на его основе.

• Глава 6. ВЫБОР ДОЛГОВРЕМЕННОГО КЛЮЧА АЛГОРИТМА ГОСТ 28147-89
• 6.1. Область сильных ключей
• 6.1.1. Достаточность условия равновероятности псевдогаммы для выбора сильного блока подстановки
• 6.2. Контроль долговременного ключа алгоритма ГОСТ 28147-89
• 6.2.1. Угроза внедрения слабых параметров
• 6.2.2. Подход к выявлению слабых долговременных ключей
• 6.2.3. Свойства теста
• 6.2.4. Тестирование долговременного ключа
• Глава 7. ЭЛЕМЕНТЫ ТЕОРИИ СРАВНЕНИЙ
• 7.1.1. Расширенный алгоритм Эвклида
• 7.2. Модульная арифметика
• 7.2.1. Функция Эйлера и малая теорема Ферма
• 7.3. Сравнения первой степени от одного неизвестного
• 7.3.1. Китайская теорема об остатках
• 7.3.2. Степенные сравнения по простому модулю
• Глава 8. ВЫЧИСЛЕНИЕ КВАДРАТНОГО КОРНЯ В ПРОСТОМ ПОЛЕ
• 8.1.1. Символ Лежандра
• 8.1.2. Символ Якоби
• 8.2. Алгоритм нахождения квадратного корня в простом поле
• 9.1. Построение криптосистемы RSA. Идея цифровой подписи
• 9.2. Смешанные криптосистемы. Протокол Диффи-Хэллмана ключевого обмена
• 9.3. Цифровая подпись Эль-Гамаля
• 9.3.1. Криптосистема Эль-Гамаля
• 9.3.2. Механизм цифровой подписи Эль-Гамаля
• 9.3.3. Ослабление подписи Эль-Гамаля вследствие некорректной реализации схемы
• 9.3.4. Варианты цифровой подписи типа Эль-Гамаля
• 10.1 Обозначения и постановка задачи
• 10.2. Построение корней из единицы в поле
• 10.3. Алгоритм дискретного логарифмирования
• 10.3.1. Пример вычисления дискретного логарифма
• 10.4. Фальсификация подписи Эль-Гамаля в специальном случае выбора первообразного элемента и характеристики поля
• 10.4.1. Слабые параметры в подписи Эль-Гамаля
• Глава 11. МЕТОДЫ ФАКТОРИЗАЦИИ ПОЛЛАРДА
• 11.2.1. Оценка вероятности выбора критической пары
• 11.2.2. Оптимизация выбора критической пары
• Глава 12. НЕКОТОРЫЕ СЛУЧАИ ОСЛАБЛЕНИЯ КРИПТОСИСТЕМЫ RSA
• 12.1. Атаки на RSA, не использующие факторизацию модуля
• 12.2. Атаки на RSA, использующие факторизацию модуля
• 12.2.1. Алгоритм факторизации Диксона
• Глава 13. ТЕСТ ФЕРМА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
• 13.1. Решето Эратосфена и критерий Вильсона
• 13.2. Тест на основе малой теоремы Ферма
• 13.2.1. Основные свойства псевдопростых чисел
• 13.2.2. Свойства чисел Кармайкла
• 13.2.3. (n-1) - критерий Люка
• 13.2.3. Понятие о последовательностях Люка. (n+1) - критерий Люка
• Глава 14. ТЕСТЫ СОЛОВЕЯ-ШТРАССЕНА И РАБИНА-МИЛЛЕРА ПРОВЕРКИ ЧИСЕЛ НА ПРОСТОТУ
• 14.1. Тест Соловея-Штрассена
• 14.1.1. Эйлеровы псевдопростые числа
• 14.2. Тест Рабина-Миллера
• 14.2.1. Сильно псевдопростые числа
• Глава 15. ПОСТРОЕНИЕ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ
• 15.1. Детерминированный тест, основанный на обобщенном критерии Люка
• 15.1.1. Теорема Поклингтона
• 15.1.2. Обобщение критерия Люка
• 15.2. Детерминированный тест, основанный на теореме Димитко
• Глава 16. ВЫБОР ПАРАМЕТРОВ КРИПТОСИСТЕМЫ RSA
• 16.1. Общие требования к выбору параметров
• 16.2. Метод Гордона построения сильно простых чисел
• 16.3. Пример построения сильно простого числа
• Глава 17. ОБЩИЕ СВЕДЕНИЯ ОБ ИНОСТРАННЫХ КРИПТОСРЕДСТВАХ
• 17.1. Аппаратные криптосредства
• 17.2. Основные принципы построения систем управления ключами
• 17.2.1. Ключевые системы потоковых шифров
• 17.3. Блочные шифры в смешанных криптосистемах
• 17.3.2. Смешанная криптосистема на основе алгоритмов RSA и IDEA
• ЗАКЛЮЧЕНИЕ
• ЛИТЕРАТУРА

130 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

Запись показателя в виде дроби корректна, поскольку один из сомножителей числителя, а именно u , делится наp , т.е. дробь является обычным целым числом.

Очевидно, r p p , j = b ju = 1 , следовательно, элементыr p , j - корни степениp

из единицы. Аналогичным образом заполним все строки таблицы R .

Дальнейшая работа сводится к вычислениям, в результате которых появляются элементы, являющиеся корнями степени p из единицы в поле.

Для каждого такого элемента будет необходимо определить его позицию

j (номер колонки) в строке таблицыR с меткой
Поскольку в каждой строке элементы различны, то для данного числа
соответствующую ему позицию мы определим однозначно.
Для этого,	конечно, мы должны быстро просмотреть строку таблицы R ,
что возможно, поскольку число q − 1 - гладкое.
10.3. Алгоритм дискретного логарифмирования
Предположим, что x представлен в				p -ичной системе счисления. Тогда
его вычет по	модулю p a	имеет вид		x = x	X p +K+x		a− 1	p a − 1 modp a ,
0 ≤x i ≤p −1 .
Обозначим	y0 = y.		определения			x k,	k = 0, K , a− 1 ,
предложим следующую процедуру, которую обсудим позже.
Прежде всего, определяем x			как позицию		y u p	в строке с номером p

таблицы R .



Алгоритм дискретного логарифмирования 131

k > 0 коэффициентx k

определяем как позицию элемента

yk u

p k+ 1

yk = y0

b h(k) ,

h(k) = x+ x p+K+ x

p k− 1 .

k − 1

Повторив процедуру

делящего

q − 1 ,

получаем

значения

x modp a ,

помощью китайской

остатках

восстанавливаем x mod (q − 1 ) .

Обоснуем процедуру определения x k .

Вычислим y 0 u p . Очевидно,

y 0 u p-

корень степени

p из единицы, причем

y u p= y u

p = b xu p= b x0 u p+ (x− x0 ) u

x − x

X p +K+x

a− 1

p a − 1.

Кроме того, число x 0 u

p является целым, т.к.u делится на

В выражении (x − x 0 ) u p оба сомножителя делятся на

p . Разделив на

сомножитель,

получаем,

что (x − x

p = ku,

B x 0 u

Сравнив с обозначением r

p , получаем, чтоy u p

j = x.

Это позволяет определить

Как позицию

y u p в строке таблицы

R с

меткой p .

Уничтожим теперь x

в показателе степени b x ,

разделив

b x 0.

Обозначим результат через y 1 :y 1 = y 0 b x 0 p 0 и вычислимy 1 u p 2 = b u (x − x 0 ) p 2 .

члены, кроме ux 1 p p 2 , кратныu и на значениеb u (x − x 0 ) p 2 не влияют.



132 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

Поскольку u делится на

также целое,

откуда y u

p2 = b x1 u p= r

j = x . Таким образом,

x равен позиции

y u p2

в строке с меткой p таблицыR .

Для определения

уничтожим

в показателе степени b x − x 0 , разделив

b x1 p1 .

b x0 p0 + x1 p1

B d ,

d = x2 p2 +K+ xa − 1 pa − 1 .

Вычисляем y u p 3

B x2 u p= r

j = x , что позволяет определитьx

по таблице R и т.д., пока не определимx a − 1 .

10.3.1. Пример вычисления дискретного логарифма

В поле F 37 , приb = 2 , найти дискретный логарифм элемента 28.

Решение. Задача сводится к решению в поле F

уравнения 28 = 2 x .

q = 37

является

степенью

простого

числа, поэтому

операции в поле совпадают с операциями в поле вычетов по модулю 37, в частности, деление есть умножение на обратный элемент.

		u = q − 1= 36= 22 32 ,						следовательно,	имеем два
делителя: 2 и 3.
	Составим таблицу						со строки с меткой p = 2 .				Вычислим
	B j (q − 1 )2	для j = 0,1						2 (q − 1 ) 2 ≡ −1 (37 ) .
2, j
	Элементами строки с меткой 3						являются числа:			B j (q − 1 )3 ,	j = 0,1,2,
									3, j

т.е. r 3,0 = 1 ,r 3,1 = 2 36 3 ≡ 26 (37 ) ,r 3,2 = 2 2 36 3 ≡ 2 24 ≡ 10 (37 ) . ТаблицаR имеет следующий вид.



Алгоритм дискретного логарифмирования 133

Таблица 4. Корни из единицы степеней 2 и 3

Найдем вычет	x = x	X p +K+x	a− 1	pa − 1	mod p a ,	при p = 2 ,a = 2 .
Число шагов равно	a = 2 . Итак, необходимо определить					x 0 , x 1 . Найдемx 0 .

Вычислим y 0 u p = 28 18 ≡ 1 (37 ) . Позиция единицы в строке 2 таблицыR равна

0, следовательно, x 0 = 0 .

Вычислим y ,

уничтожив член с

в показателе числа b x :

y = y

b x0 p0 .

Поскольку x

то y = y .

Возводим y

в степень u

p 2,

p 2= 4 :

y u 4= 28 36 4= − 1 (37 ) .

Позиция числа (-1) в строке 2 таблицыR равна 1, следовательно,

x 1= 1 .

Итак x = x 0 + x 1 p = 2 mod 4.

Найдем вычет

x mod p a , при

p = 3 ,a = 2 . Число шагов равноa = 2 .

y 0 u p = 28 12 ≡ 26 (37 ) . Позиция

26 в строке 3 таблицы

следовательно,

x = 1 , поэтому

y = y

b x 0 p 0 = 14.

Возводим

в степень

p 2,

p 2= 9 :

y u9

1436 9 = 10(37) ,

следовательно x 1 = 2 . Итак,

x = 7 mod9.



Z p r Z

134 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

	систему сравнений x = 2 mod4 ,x = 7 mod9 :9 − 1 (4 ) = 1 ,
4− 1 (9) = 7,	x ≡ 2 9(9− 1 mod 4) + 7 4(4− 1 mod 9) = 214, т.е.

x ≡ 34 mod36.

10.3.2. Логарифмирование в группе единиц кольца вычетов по модулю pr .

Существование частных методов дискретного логарифмирования в конечном поле приводит к необходимости построения больших простых чисел со специальными свойствами. В качестве подхода, позволяющего снизить величины генерируемых простых чисел, можно, в принципе, рассмотреть использование в протоколе Диффи-Хэллмана операцию приведения по модулю

существует первообразный элемент γ , степени которого представляют все вычеты, взаимно простые с модулем. Эти вычеты образуют вмультипликативную группуU (p r ) изϕ (p r ) элементов (т.н. группу единиц).

Можно показать , что если γ p - первообразный корень в поле

GF (p ) , то одно из чиселγ = γ p + kp , гдеk { 0,1 } , удовлетворяет условию

(γ p + kp ) p − 1 ≠ 1 (mod p 2 ) и является первообразным корнем по любому модулюp α ,α > 1 . Заметим, что пары чиселa ,p , для которых выполняется соотношениеa p − 1 = 1mod p 2 , встречаются редко. Поэтому будем считать, что

γ = γp .

Таким образом, любой из ϕ (p r ) = p r − 1 (p − 1 ) вычетовb U (p r ) можно

представить в виде b = γ x mod p r .



Алгоритм дискретного логарифмирования в группе единиц… 135

Соответственно, задача дискретного логарифмирования в группе единиц кольца Z p r Z состоит в определении вычетаx поmod ϕ (p r ) , исходя изb и

γ .

К сожалению, использование модуля p r не дает преимуществ, поскольку

при наличии эффективного алгоритма логарифмирования в простом поле

GF (p ) логарифмирование в группе единиц кольца вычетов по модулюp r ,r > 1 , практически всегда можно осуществить, воспользовавшись свойствами так называемого обобщенного отношения ФермаL m (a ) .

Областью определения отображения L m (a ) является группаU (m )

вычетов по модулю m , взаимно простых с модулем. По теореме Эйлера,

существует λ :a ϕ (m ) − 1 = λ m . ЗначениеL m (a ) определяется как вычет числаλ по модулюm :L m (a ) = a ϕ (m m ) − 1 (mod m ) .

Легко убедиться, что отношение Ферма обладает следующими замечательными свойствами.

Lm (ab) = Lm (a) + Lm (b)(mod m) ,

Lm (a+ mc) = Lm (a) + ϕ (m) ca- 1 (mod m) ,

где a, b U(m) , c ZmZ.

				r > 1 . Заметим,	что в этом случае,
	(a+ mc) = L(a) + (pr − pr − 1 ) ca- 1 (mod m) = L(a) (mod pr − 1 ) .
образом, если a ≡ b (mod m ) , то			L (a) ≡ L(b) (mod pr − 1 ) .
		L (γ ) = 0(modp r − 1 ) ,		определения	L (γ ) следует, что

γ ϕ (m ) = 1(modp 2 r − − 2 ≤ r − 1 , т.е.

r ≤ 1 , что противоречит

Если L

(γ )= 0 (mod m ), то

(γ ) = 0(modp r − 1 ) и r ≤ 1 .

Аналогично, при L

(γ ) = pt (modp r − 1 ) ,

получаем

γ ϕ (m ) = 1(modp r + 1 ) ,

что невозможно, т.к. ϕ (p r + 1 ) > ϕ (m ) .

Таким образом, элемент L m (γ )

p и, следовательно,

обратим по модулю p r − 1 .

Рассмотрим задачу логарифмирования

в группе единиц кольца

Z mZ ,

эффективный алгоритм

логарифмирования в кольце

известен.

Из соотношения b = γ x mod p r

b = γ x mod p,

известно значение x по модулю

p − 1 . Если мы найдемx (mod p r − 1 ) , то

значение

по модулю ϕ (m ) = p r − 1 (p − 1 )

можно вычислить по китайской

теореме об остатках.

Очевидно,

что значение x (mod p r − 1 )

легко определить

из сравнения

L (b) = xL(γ ) (mod pr − 1 ) .

необходимо

вычислять

значения

h = Lm (a) (mod pr − 1 ) .

Группа исследователей из EPFL и Университета Лейпцига смогла посчитать логарифм по основанию простого числа размером 768 бит . Для этого им понадобилось 200 ядер и время с февраля 2015 года. Использовали они вариант цифрового решета. Таким образом логарифмирование сравнялось с факторизацией где рекорд для обычных чисел тоже 768 бит

Кстати, после завтрашнего апдейта можно будет прикручивать бесплатный TLS к dyndns хостам! Это суперкруто, все хомяки теперь будут с сертификатами.

Защищаемся от Side channel атак

Не секрет, что нынче информацию о ключах шифрования можно удаленно снимать чуть ли не через вентилятор. Поэтому, все большую популярность обретают constant-time алгоритмы, которые не зависят от входных данных. Немцы выпустили минимальные требования для реализаций, выполнение которых усложнит задачу получения секретных данных через побочные каналы данных. , советую ознакомиться.

На этом у меня всё, до новых встреч!