Содержание к диссертации
Введение
1. Основные понятия криптологии 13
2. Теоретические основы метода 22
3. Алгоритм шифрования текстовой информации 29
3.1. Постановка задачи 29
3.2. Формирование алгоритма шифрования-дешифрования текста 29
4. Корреляционный анализ 37
4.1. Основные понятия корреляционного анализа 37
4.1.1. Характер связей, корреляция, регрессия 37
4.1.2. Параметрические методы оценки корреляционной связи показателей 39
4.1.3. Непараметрические методы оценки корреляционной связи показателей 42
4.1.4. Автокорреляция 45
4.2. Постановка задач корреляционного анализа 46
4.3. Установление соответствия закона распределения получаемой последовательности значений динамической переменной равномерному 48
4.4. Автокорреляционный анализ последовательности значений динамической переменной 50
4.5. Автокорреляционный анализ последовательности значений управляющего параметра (шифра) 5\
4.6. Выводы 53
5. Анализ криптостойкости 54
5.1. Постановка задачи 54
5.2. Описание решения задачи 54
5.3. Выводы 57
6. Описание разработанного программного продукта 58
7. Основные характеристики и сравнительный анализ метода 65
7.1. Основные характеристики метода в части шифрования текста 65
7.2. Сравнительный анализ метода 71
7.2.1. Криптографический алгоритм RSA, описание и общие вопросы 71
7.2.2. Криптографический алгоритм DES, описание и общие вопросы 75
7.2.3. Сравнение 77
7.3. Примеры шифрования текста 78
7.4. Основные достоинства метода 82
7.5 Выводы 83
7.5. Шифрование звуковой информации 84
7.5.1. Постановка задачи 84
7.5.2. Основные понятия о цифровом представлении звука 84
7.5.3. Формирование алгоритма шифрования-дешифрования звука 89
7.5.4. Корреляционный анализ 94
7.5.5. Анализ криптостойкости 100
7.5.6. Анализ применимости метода в области шифрования звука 102
7.5.7. Основные характеристики метода в части шифрования звука 104
7.5.8. Выводы 107
7.6.О генерации псевдослучайных чисел 108
Заключение 115
Список использованных источников
- Формирование алгоритма шифрования-дешифрования текста
- Параметрические методы оценки корреляционной связи показателей
- Описание решения задачи
- Криптографический алгоритм RSA, описание и общие вопросы
Введение к работе
Криптография - наука о шифрах - долгое время была засекречена, так как применялась, в основном, для защиты государственных и военных секретов. В настоящее время методы и средства криптографии используются для обеспечения информационной безопасности не только государства, но и частных лиц, и организаций. Дело здесь совсем не обязательно в секретах. Слишком много различных сведений «гуляет» по всему свету в цифровом виде. И над этими сведениями «висят» угрозы недружественного ознакомления, накопления, подмены, фальсификации и т.п. Наиболее надежные методы защиты от таких угроз дает именно криптография.
С каждым днем криптография и криптографические методы все шире входят в нашу жизнь и даже быт. Вот несколько примеров. Отправляя E-mail, мы в некоторых случаях отвечаем на вопрос меню: «Нужен ли режим зашифрования?» Владелец интеллектуальной банковской карточки, обращаясь через терминал к банку, вначале выполняет криптографический протокол аутентификации карточки. Пользователи сети Интернет наверняка знакомы с дискуссиями вокруг возможного принятия стандарта цифровой подписи для тех страниц, которые содержат критическую информацию (юридическую, коммерческую и др.). С недавних пор пользователи сетей стали указывать после своей фамилии наряду с уже привычным «Email ...» и менее привычное - «Отпечаток открытого ключа...».
Появляется множество методов криптографии (защиты информации) и криптоанализа (взлома защиты). Постоянно растут требования к методам, главным образом, касающиеся их криптостойкости и производительности.
В связи с этим вызывают интерес появляющиеся в последние годы приложения нелинейной, и, в частности, хаотической динамики к проблеме защиты информации. В работе предложен, исследован и программно реализован новый метод защиты передачи информации посредством кодирования элементов информации стабилизированными циклами семейства хаотических отображений.
Идея метода принадлежит профессору доктору физико-математических наук Александру Юрьевичу Лоскутову и кандидату физико-математических наук Сергею Дмитриевичу Рыбалко (оба: Московский государственный университет им. М.В. Ломоносова, физический факультет) [1,2,13,14,18,24-27,30,33]. Исследования, эксперименты, аналитические работы проводились при непосредственном участии авторов идеи.
Чтобы обоснованно подойти к практической реализации нового криптографического метода, необходимо провести эксперименты и получить ряд оценок, его характеризующих. Этим обусловлены последовательность, состав и содержание этапов работы. Кроме системы защиты информации, в работе показан, исследован и реализован метод генерации псевдослучайных чисел, базирующийся на некоторых свойствах хаотических систем.
Основной целью проводимых работ является комплексный анализ предлагаемого нового (что обуславливает большой объем исследовательских работ) криптографического метода на предмет применения для защиты информации от постороннего наблюдателя как при передаче по каналам связи, так и при сохранении на носителях информации, и практическая реализация шифрования этим методом. Практическая реализация целесообразна только при удовлетворительных результатах аналитических и исследовательских работ.
Защищаемые положения:
Построено теоретическое обоснование нового криптографического метода, основанного на стабилизации циклов нелинейных динамических систем. • Сформирован алгоритм шифрования-дешифрования текста;
• Экспериментально получены кодовые последовательности (шифры);
• Проведен корреляционный анализ метода;
• Проведен анализ криптостойкости (методом тотального опробования);
• Разработан программный продукт, реализующий обмен текстовыми сообщениями, зашифрованными представленным методом;
• Получены основные технические характеристики метода;
• Проведен сравнительный анализ метода с наиболее распространенными на сегодняшний день криптографическими методами.
Работу условно можно разбить на три этапа:
1. Исследование и реализация метода в части защиты текстовой информации;
2. Исследование и реализация метода в части защиты звуковой информации;
3. Исследование и реализация способа генерации псевдослучайных чисел, базирующегося на некоторых свойствах хаотических систем и использующегося при шифровании;
Работы выполнялись в следующем порядке:
1) Теоретическое обоснование метода.
При этом проводилось научное обоснование основньк положений метода и его оценка с этой позиции.
В части защиты текстовой информации:
2) Формирование алгоритма шифрования-дешифрования текста.
3) Экспериментальное получение кодовых последовательностей (шифров) для задачи защиты текстовой информации.
Имитация работы метода с целью получения числовых последовательностей, являющихся шифрами, для их дальнейшего исследования.
4) Корреляционный анализ.
Получение статистических характеристик шифров, необходимых для оценки предсказуемости их значений, что самым непосредственным образом влияет на надежность предлагаемого метода шифрования.
5) Анализ криптостойкости.
Получение оценки трудоемкости вскрытия шифра при различных параметрах ключа, содержании открытой информации, условиях передачи.
Примечание:
этапы 6-11 выполняются только в случае удовлетворительных результатов оценок, полученых на этапах 4, 5.
6) Проектирование программного продукта «Шифровалыцик-дешифровалыцик текста».
Выбор архитектуры будущей системы, средств разработки, выбор и обоснование методов разработки и тестирования продукта, проектирование интерфейсной части, подготовка документации по системе.
7) Разработка программного продукта «Шифровалыцик-дешифровалыцик текста».
Программирование, дополнение и корректировка документации.
8) Тестирование программного продукта «Шифровалыцик-дешифровалыцик текста».
9) Получение основных характеристик и сравнительный анализ метода в части защиты текстовой информации.
Получение и анализ основных характеристик метода. Сравнение предлагаемого метода с представленными на рынке криптографических средств и широко используемыми на сегодняшний день методами защиты текстовой информации.
В части защиты звуковой информации:
10) Формирование алгоритма шифрования-дешифрования звука.
11) Экспериментальное получение кодовых последовательностей (шифров) для задачи защиты звуковой информации.
Имитация работы метода с целью получения числовых последовательностей, являющихся шифрами, для их дальнейшего исследования.
12) Корреляционный анализ.
Получение статистических характеристик шифров, необходимых для оценки предсказуемости их значений, что самым непосредственным образом влияет на надежность предлагаемого метода шифрования.
13) Анализ криптостойкости.
Получение оценки трудоемкости вскрытия шифра при различных параметрах ключа, содержании открытой информации, условиях передачи.
Примечание:
этапы 14-17 выполняются только в случае удовлетворительных результатов оценок, полученых на этапах 12,13.
14) Проектирование программного продукта «Шифровалыцик- дешифровалыцик звука».
Выбор архитектуры будущей системы, выбор и обоснование методов разработки и тестирования продукта, средств разработки, проектирование интерфейсной части, подготовка документации по системе.
15) Разработка программного продукта «Шифровалыцик-дешифровалыцик звука».
Программирование, дополнение и корректировка документации.
16) Тестирование программного продукта «Шифровалыцик-дешифровалыцик звука».
17) Получение основных характеристик и сравнительный анализ метода в части защиты звуковой информации.
Получение и оценка основных характеристик метода в части шифрования звука. Сравнение предлагаемого метода с представленными на рынке криптографических средств и широко используемыми на сегодняшний день методами защиты звуковой информации.
Формирование алгоритма шифрования-дешифрования текста
Опишем способ применения предлагаемого метода для шифрования текстовой информации, вводимой с клавиатуры персонального компьютера [1,14,18].
Рассмотрим процессы шифрования и дешифрования на примере. Известно, что в операционных системах персональных компьютеров информация о печатных символах содержится в виде, т.н., кодов ASCII, которые представляют собой трехзначные числа, принадлежащие отрезку [0,255] (в десятичном представлении).
На первом этапе шифрования необходимо получить ASCII коды всех символов, входящих в кодируемый текст. Т.о., мы получаем некоторую последовательность ASCII-кодов. Представим эту последовательность в виде числового массива, каждый элемент которого есть одна из трех составляющих кода ASCII некоторого шифруемого символа. Например, символу «а» с ASCII-кодом 97 соответствует тройка чисел гм = 0, п2 = 9, n3 = 7 и в созданный массив мы вносим значения П, т.е. О, 9 и 7. Каждый член последовательности щ в терминах нелинейной динамики интерпретируем как период цикла, по которому изменяется динамическая переменная. Поэтому, для того, чтобы избежать присутствия вырожденных циклов (периода 0) и устойчивых точек (циклов периода 1) к каждому п следует прибавить двойку. Избавляться от циклов периода 1 следует потому, что эти циклы не изменяют значения динамической переменной x={xi,...,xm}. При этом значения управляющего параметра a ={ai,...,a„}, стабилизирующего такие циклы, повторяются, что нежелательно, т.к.: 1) Единицы в совокупности составляющих ASCII-кодов встречаются чаще других цифр; 2) Шифр представляет собой совокупность значений управляющего параметра.
Далее, необходимо получить последовательность чисел (желательно наличие у этой последовательности свойств, характеризующих ее как случайную), имеющую длину, равную сумме всех т\\ (увеличенных на два) плюс 1 (смысл этого прибавления единицы раскрыт ниже). Эту последовательность случайных чисел интерпретируем как последовательность значений динамической переменной х. Динамическая переменная - это величина, однозначно определяющая состояние динамической системы в каждый момент времени. При шифровании мы будем использовать дискретные динамические системы. Особенностью таких систем является то, что время для них квантовано: система изменяет свое состояние не непрерывно, а через определенные интервалы времени. Поэтому поведение дискретной динамической системы можно задать набором значений динамической переменной, каждое из которых описывает состояние системы на некотором шаге отсчета времени.
Необходимо сказать несколько слов о применяемом способе генерации числовой последовательности со случайными свойствами. Для образования такой последовательности не используются сторонние генераторы случайных чисел. Последовательности формируются на основе применения некоторых известных фактов хаотических динамики. Используемый метод генерации исследован, результаты исследований и описание метода помещены в разделе 7 .
Итак, мы сформировали последовательность значений динамической переменной х. Теперь наша задача состоит в том, чтобы «заставить» х изменяться циклически. Циклов должно быть столько, сколько членов содержится в последовательности rij (число символов кодируемого текста, умноженное на три), а периоды этих циклов должны равняться значениям п\.
Пусть при осуществлении указанных процессов используется квадратичная дискретная динамическая система, описываемая отображением: Т,: х - а х ( 10-х), (11) где х -динамическая переменная; а - управляющий параметр; f(a,x) = а х ( 10-х) - нелинейная функция. Предположим, что в некоторый момент времени / поведение динамической системы характеризовалось значением xi динамической переменной. Динамическая переменная х совершит цикл периода к если через к шагов примет свое исходное значение xj. Для совершения цикла периода к необходимо иметь к+1 значений динамической переменной (одно - начало отсчета).
Параметрические методы оценки корреляционной связи показателей
Статистика разработала множество методов изучения связей, выбор которых зависит от целей исследования и от поставленных задач. Связи между признаками и явлениями ввиду их большого разнообразия классифицируют по ряду оснований.
Признаки по их значению для изучения взаимосвязи делятся на два класса: о Результативные; о Факторные. Результативными называются признаки, изменяющиеся под действием других, связанных с ними признаков. Факторными называются признаки, обуславливающие изменение результативных признаков.
Существуют различные виды и формы связи признаков. По характеру зависимости признаков различают: о Функциональную (полную) связь; о Корреляционную (неполную) связь. Функциональная - это связь, при которой определенному значению факторного признака соответствует одно и только одно значение результативного признака.
Корреляционная - это связь, при которой определенному значению факторного признака соответствует лишь среднее значение результативного признака. Существуют также связи непосредственные и косвенные. Фактор X может непосредственно оказывать влияние на Y или косвенно, через другой фактор W. Связь между двумя признаками (результативным и факторным или двумя факторными) называется парной корреляцией.
Зависимость между результативным и одним факторным признаками при фиксированном значении других факторных признаков называется частной корреляцией.
Зависимость же результативного и двух или более факторных признаков, включенных в исследование, называется множественной корреляцией. Мы не будем подробно рассматривать математический аппарат множественной корреляции, т.к. имеем дело с однофакторной задачей.
Корреляционный анализ имеет своей задачей количественное определение тесноты связи между признаками (при парной связи) и между результативным и множеством факторных признаков (при многофакторной связи). Теснота связи количественно выражается величиной коэффициентов корреляции.
Регрессивный анализ заключается в определении аналитического выражения связи, в котором изменение результативного признака обуславливается влиянием одного или нескольких факторных признаков, а множество всех прочих факторов применяется за постоянные (или усредненные) величины. Корреляционно-регрессивный анализ включает в себя измерение тесноты и направления связи, а также установление аналитического выражения (формы) связи.
При прямолинейной форме связи показатель тесноты связи двух признаков определяется по формуле линейного коэффициента корреляции г: где х - значение факторного признака; у - значение результативного признака; n - число пар данных. г, вычисленные по данным сравнительно небольшой статистической совокупности, могут искажаться под действием случайных причин. Поэтому необходима проверка их сущности. Для оценки значимости г применяется, так называемый, t-критерий Стьюдента. При этом определяется фактическое значение критерия tr:
Исчисленное tr сравнивается с критерием tK, которое берется из таблицы значений t-Стьюдента с учетом заданного уровня значения а и числа степеней свободы к.
В рамках корреляционно-регрессивного анализа происходит и выбор адекватного эмпирическим данным уравнения регрессии. При этом недостаточно только качественного (логического) анализа. Хотя рабочие гипотезы о возможной форме связи формулировать можно.
Наглядное изображение анализируемых данных, то есть применение графического метода (путем построения корреляционного поля точек эмпирической линии регрессии), не дает обобщенную количественную оценку адекватности того или иного уравнения связи. Более продуктивно использование критерия минимальной остаточной дисперсии и показателя средней ошибки аппроксимации : п Yi (15) где yi - yxi - модуль линейных отклонений эмпирических и выравненых значений результативного признака.
Оценка параметров уравнений регрессии осуществляется методом наименьших квадратов. Сущность метода наименьших квадратов заключается в нахождении параметров модели (ао и ai), при которых минимизируется сумма квадратов отклонений эмпирических (фактических) значений результативного признака от теоретических. Для выражения прямолинейной формы зависимости между X и Y применяется формула:
Для определения параметров уравнения на основе требований метода наименьших квадратов составляется система нормальных уравнений: Для решения системы применяется способ определителей, позволяющий сводить к минимуму неточности округления в расчетах параметров уравнений регрессии:
Описание решения задачи
Правила криптоанализа были сформулированы еще в конце 19 века преподавателем немецкого языка в Париже голландцем Керкхофом в книге «La Cryptographie militare». Согласно одному из этих правил разработчик шифра должен оценивать криптографические свойства шифра в предположении, что не только шифртекст известен противнику (криптоаналитику противника), но известен и алгоритм шифрования, а секретным для него является лишь ключ [43-63].
Основными количественными мерами стойкости шифра служат так называемые трудоемкость метода криптографического анализа и его надежность. Трудоемкость дешифрования обычно измеряется усредненным по ключам шифра и открытым текстам количеством времени или условных вычислительных операций, необходимых для реализации алгоритма. Надежность метода - вероятность дешифрования. Раз метод несет в себе определенную случайность, например, неполное опробование ключей, то и положительный результат метода возможен с некоторой вероятностью. Наша задача состоит в том, чтобы оценить трудоемкость дешифрования и надежность применительно к исследуемому методу.
Опишем проведение анализа криптостойкости исследуемого метода одним из наиболее распространенных методов - методом тотального опробования, который заключается в последовательном случайном и равновероятном опробовании без повторений г ключей из К (пространство ключей). Процесс опробования заканчивается при опробовании к ключей; k=j - номер первого iono4a(l j N), при котором соответствующий расшифрованный текст будет признан критерием за содержательный текст, или k=N, если такое событие не произойдет при любом j N. Для оценки содержательности расшифровываемого текста вводятся следующие гипотезы: 1) НО - текст открытый (исходный, расшифрованный); 2) HI -текст случаен. При составлении вероятностной модели задачи эту оценку определяют следующие ошибки: 1) а=Р(Н 1 /НО) - вероятность отбраковки содержательного текста; 2) Р=Р(Н0/Н1) - вероятность принять несодержательный текст за содержательный. Приведем результаты расчета указанных выше основных характеристик криптостойкости алгоритма шифрования (трудоемкости и надежности).
Математическая модель вычисления трудоемкости метода криптографического анализа выглядит следующим образом (выкладки не приводятся): " (1 1) - трудоемкость криптографического метода - среднее число опробуемых ключей (математическое ожидание случайной величины к, характеризующей окончание процесса опробования); г - количество опробуемых ключей; К - множество ключей.
Результаты расчета в предположении безошибочной работы механизма принятия решений (а=0, (3=0) сведены в табл.5. В левой колонке указано количество байт, отводимое для хранения значения управляющего параметра. В последней колонке указана трудоемкость, переведенная в единицы времени на основании сведений о производительности современных мейнфреймов (приблизительно 1 инструкция за 1 мкс).
Очевидно, что надежность метода тотального опробования в предположении безошибочной работы механизма принятия решений (а=0, (3=0) равна 1.
Анализ криптостойкости методом тотальнонго опробования показал, что метод защиты информации, основанный на стабилизации циклов отображений нелинейных динамических систем обладает высокой криптоаналитической стойкостью при определенном выборе количества байт, отводимых для хранения значений управляющего параметра.
Стоит сказать, что проведенный анализ криптостойкости является лишь первым шагом к получению достоверной оценки устойчивости метода к взлому и не может рассматриваться как средство получения окончательных оценок. Предстоит получить еще множество оценок различными методами, построить ряд моделей, провести не одну экспертизу для достоверной оценки криптостойкости предлагаемого метода. Однако данные задачи выходят за рамки данной диссертационной работы.
Результаты проведенных исследований выявили целесообразность дальнейшей проработки предлагаемого метода защиты информации. Следующим шагом в этом направлении явилась практическая реализация метода.
На сегодняшний день разработано сетевое приложение, позволяющее пользователям обмениваться текстовыми сообщениями, защищенными представляемым методом. Работу программы иллюстрируют рисунки 10-16.
Опишем подробнее разработанный программный продукт. При вызове приложения "Codec 1.0" загружается стартовое окно приложения. Среди элементов управления, находящихся в этом окне можно выделить несколько групп, исходя из их функционального назначения: 1) Элементы управления соединением; 2) Элементы управления вводом, шифрованием и отсылкой сообщения; 3) Элементы управления получением и расшифровкой сообщения; 4) Элементы управления и контроля параметров шифрования. Элементы управления соединением предназначены для осуществления выбора адресата, инициализации и завершения сеанса связи.
Транспортная служба приложения реализована в соответствии со спецификациями TCP/IP [44]. На рисунке 10 показаны элементы интерфейса разработанного приложения, обеспечивающие взаимодействие пользователей. В поле "Server Name" необходимо указать IP-адрес машины, с которой устанавливается соединение, в поле "Server Port" - номер порта вызываемой машины, на котором будет работать наше приложение.
Криптографический алгоритм RSA, описание и общие вопросы
Если для хранения значения управляющего параметра выбрать 4 байта=32 бита (см. параметр байт/коэффициент в табл. 5), то среднее соотношение бит/символ составит 32 15,51=496,32, что в байтах приблизительно равно 62. В кодировке ASCII для каждого символа отводится 1 байт. Следовательно, с учетом сделанных допущений, при использовании предлагаемого метода шифрования, шифрованный текст по объему занимаемой памяти превосходит открытый, представленный в кодировке ASCII в среднем в 62 раза. 3) Степень соответствия шифра равномерному закону распределения.
Принято считать, что чем ближе закон распределения некоторого шифрованного текста к раномерному, тем лучше. С одной стороны, это действительно играет положительную роль с точки зрения защиты, т.к. целый ряд методов криптоанализа оценивают близость распределения шифра к распределению естественного языка открытого текста, что существенно ускоряет процесс вскрытия шифра. Например, если закон распределения шифра близок к закону распределения русского языка, делается предположение о том, что зашифрованный текст написан на русском языке. Далее оценивается повторяемость отдельных групп шифра и сравнивается со среднестатистической повторяемостью букв русского языка, делается предположение о том, что за данным участком шифра скрыт некоторый определенный символ. После этого вскрытие шифра составит труда. С этой точки зрения шифр имеющий характеристики случайной последовательности символов выглядит предпочтительнее.
С другой стороны, существуют данные, которые передаются или используются в зашифрованном виде (например: пароли, данные аутентификации и др.). И существуют методы поиска и извлечения таких данных, основанные на поиске и извлечении фрагмента информации с равномерным законом распределения. Допустим, некоторая программа-наблюдатель сканирует некоторый канал связи, или участок памяти компьютера путем построчного считывания данных и установления близости их распределения равномерному. Как только такие данные найдены, делается предположение о том, что это, например, пароль. Теперь злоумышленник может смело воспользоваться этим паролем для доступа к чему-либо, что этот пароль был призван защитить.
Ясно, что сегодня уже нельзя говорить о том, что шифры со свойствами случайных последовательностей наиболее надежны. Требуется более гибкий подход: нужно избежать сходства свойств шифра со свойствамим естественного языка, и в то же время, равномерности. Этого позволяет добиваться наш метод, что иллюстрируют рис. 18 и 19. «Неравномерность» распределения очевидна, а о сходстве распределения с естественным языком тоже говорить нельзя, т.к. здесь показаны гистограммы 1000-кратного шифрования символа «о» (латинского алфавита).
Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается (например, ее используют операционные системы Microsoft, Apple, Sun и Novell). В аппаратном исполнении алгоритм RSA применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании. Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями (по количеству проданных лицензий на рынке IT компания "RSA Data Security", владелец алгоритма, является мировым лидером).
Криптосистема RSA была разработана в 1977 году и названа в честь ее разработчиков Ronald Rivest, Adi Shamir и Leonard Adleman (по первым буквам фамилий).
RSA - криптографическая система с открытым ключом, обеспечивающая такие механизмы защиты как шифрование, цифровая подпись, аутентификация. Системами с открытым ключом, или асимметричными криптосистемами называют такие, где ключ состоит из двух частей - открытого и закрытого. При этом, если для шифрования использовалась одна часть ключа, расшифровка возможна только с использованием другой его части. Алгоритм RSA работает следующим образом: выбираются два достаточно больших простых числа р и q и вычисляется их произведение n = p q; п называется модулем. Затем выбирается число е, удовлетворяющее условию К е (р - l) (q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (р- l) (q-1). После этого вычисляется число d таким образом, что (e d - 1) делится на (р -l) (q-l). е - открытый (public) показатель d - частный (private) показатель. (п; е) - открытый (public) ключ (n; d). - частный (private) ключ.
Делители (факторы) р и q можно либо уничтожить, либо сохранить вместе с частным (private) ключом. Если бы существовали эффективные методы разложения на сомножители (факторинга), то, разложив п на сомножители (факторы) р и q, можно было бы получить частный (private) ключ d. Таким образом надежность криптосистемы RSA основана на трудноразрешимой - практически неразрешимой - задаче разложения п на сомножители (то есть на невозможности факторинга п) так как в настоящее время эффективного способа поиска сомножителей не существует.
При шифровании алгоритм RSA используется следующим образом. Предположим, Алиса хочет послать Бобу сообщение М. Алиса создает зашифрованный текст С, возводя сообщение М в степень е и умножая на модуль п: С = Ме (mod п), где е и п - открытый (public) ключ Боба. Затем Алиса посылает С (зашифрованный текст) Бобу. Чтобы расшифровать полученный текст, Боб возводит полученный зашифрованный текст С в степень d и умножает на модуль п: М = cd (mod п); зависимость между end гарантирует, что Боб вычислит М верно. Так как только Боб знает d, то только он имеет возможность расшифровать полученное сообщение.
Похожие диссертации на Защита информации посредством применения хаотических отображений
