рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Практическое использование алгоритма RSA

Практическое использование алгоритма RSA - раздел Компьютеры, Методы и средства защиты компьютерной информации   Для Алгоритмов, Основанных На Открытых Ключах, Существует Ряд...

 

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

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

,

где k и n известны, зависит от сложности факторизации модуля n. Однако следует иметь в виду, что это утверждение является всего лишь предположением, поскольку строгих математических доказательств эквивалентности данных проблем пока не существует.

Поэтому первый вопрос, который необходимо обсудить, это выбор размера модуля n.

Определение. Размер параметра – количество битов в его двоичном представлении.

Учитывая последние достижения в области факторизации целых чисел, модуль n размером 512 бит обеспечивает лишь минимальную защиту от коллективной атаки. Так в 1996 году было рекомендовано выбирать модуль размером 768 бит, чтобы противостоять методам квадратичного просеивания и решета числового поля. Для долгосрочной защиты размер модуля должен быть 1024 или более бит.

Следующим важным моментом практического применения предлагаемого алгоритма является выбор параметров p и q.

Среди наиболее известных недостатков алгоритма RSA можно выделить некорректный выбор значений p и q. Основные требования к этим параметрам заключаются в следующем.

Во-первых, числа p и q должны быть простыми и не содержаться ни в одной из известных таблиц простых чисел. При факторизации можно всегда проверить всю таблицу или перебрать последовательность простых чисел специфического вида (например, числа Мерсенна или Ферма).

Во-вторых, p и q не должны быть близкими друг к другу. В противном случае можно воспользоваться методом факторизации Ферма. В целом рекомендуется, чтобы двоичное представление p и q различалось по длине на несколько битов.

В-третьих, при выборе p и q также должно быть рассмотрено и значение j. Оба числа p – 1 и q – 1 четны, из чего следует, что j делится на 4. Как известно, справедливо соотношение

,

где НОК – наименьшее общее кратное чисел, указанных в качестве аргументов. Поэтому, если НОД(p – 1, q – 1) окажется большим, то l = НОК(p‑1, q‑1) мало (ударение на букву о) по сравнению с j. Для нахождения экспоненты расшифрования d достаточно решить сравнение

вместо сравнения

.

В этом случае появляется возможность найти d простой проверкой, поэтому НОД(p – 1, q – 1) не должен быть большим. Вырожденным является случай, когда одно из p – 1 или q – 1 делит другое. В наилучшем случае НОД(p‑1,q‑1) = 2.

Необходимо также избегать ситуации, когда j раскладывается в произведение только малых простых сомножителей.

В-четвертых, чтобы исключить возможность применения (p – 1)- и (p + 1)-методов факторизации, рекомендуется выбирать в качестве p и q сильные простые числа. Эти два метода эффективны только если n имеет простой множитель p такой, что p – 1 или p + 1 раскладываются в произведение только малых простых сомножителей.

Определение. Простое число p называется сильным простым числом (strong prime), если выполнены следующие три условия:

1. p – 1 имеет большой простой множитель r;

2. p + 1 имеет большой простой множитель;

3. r – 1 имеет большой простой множитель.

Условие 1 этого определения предназначено для того, чтобы противостоять методу p – 1 Полларда. Условие 2 необходимо, чтобы противостоять методу p + 1 Вильямса. И, наконец, условие 3 необходимо, чтобы противостоять циклической атаке которая будет рассмотрена позднее.

Следует заметить, что в русскоязычной литературе нет общепринятой терминологии обозначающей английский термин strong prime. Например, используются следующие эквивалентные термины: строго простое число, сильно простое число, сильное простое число.

Если число p (аналогичные рассуждения справедливы и для q) выбрано случайно и подходящего по величине размера, то можно ожидать, что p – 1 и p + 1 имеют большие простые множители. В любом случае сильные простые числа защищают только от методов p – 1 и p + 1, но они не могут противостоять методу эллиптических кривых.

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

Наиболее сильное требование к p и q, сформулированное Райвестом (Rivest) в 1978 г., заключается в том, чтобы числа

, , ,

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

Следует заметить, что для алгоритма RSA характерно наличие так называемых нешифруемых сообщений, то есть таких m, для которых выполняется сравнение , где e – показатель зашифрования. Например, a = 0, a = 1 и a = n – 1 всегда являются нешифруемыми сообщениями. Точное количество нешифруемых сообщений равно

.

Учитывая, что e – 1, p – 1 и q – 1 всегда четны, то количество нешифруемых сообщений, по крайней мере, не меньше 9.

Одной из основных проблем, возникающих при использовании асимметричных алгоритмов, является низкая скорость проведения операций зашифрования/расшифрования по сравнению с симметричными алгоритмами. В частности алгоритм RSA, работает примерно в 1000 раз медленнее по сравнению с DES (Data Encryption Standard), который, в свою очередь, является далеко не самым быстрым из используемых в настоящее время симметричных алгоритмов. Один из способов решения проблемы – уменьшение размерности параметров системы, но это чревато уменьшением стойкости алгоритма.

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

Однако, выбор малых параметров e и d представляется небезопасным по ряду соображений.

Если значение e выбрано случайно, то процесс зашифрования с использованием бинарного алгоритма требует примерно N модульных возведений в квадрат и N/2 модульных умножений, где N – размер модуля n. Скорость зашифрования может быть увеличена за счет выбора малого показателя e и/или выбора такого значения e, чтобы его двоичное представление содержит малое количество единиц.

В связи с этим, на практике, часто используют значение e = 3. В этом случае необходимо, чтобы p – 1 и q – 1 не делились на 3. В результате получается очень быстрое зашифрование, так как для этого требуется только одно модульное возведение в квадрат и одно модульное умножение. Однако такой выбор позволяет провести следующую атаку.

Пусть несколько абонентов используют одно и то же значение e, но каждый из них имеет собственный уникальный модуль. Если абонент A отправляет одно и то же сообщение m трем другим абонентам, чьи открытые модули есть , и , то соответствующие шифротексты равны , где i = 1, 2, 3. Если эти модули окажутся попарно взаимно простыми (а скорее всего так и будет), то злоумышленник, перехватив , и может восстановить открытый текст m (детальное описание данной процедуры выходит за рамки лекционного курса).

Таким образом, малый показатель зашифрования, например, e = 3, не может использоваться, если одно и то же сообщение (или, даже одно и то же сообщение с известными модификациями) отправляется нескольким абонентам.

Малый показатель e нельзя использовать для шифрования малых сообщений m, так как если , то m может быть вычислено из шифротекста просто нахождением целого значения корня степени e из c.

Другим часто используемым значением является . Это число имеет только две единицы в своем двоичном представлении и процесс зашифрования потребует 16 модульных возведений в квадрат и 1 модульное умножение. Показатель имеет преимущество по сравнению с e = 3, так как маловероятно, что одно и то же сообщение будет отправлено абонентам.

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

Во-первых, при очень малых значениях секретного параметра d, например , его можно определить простым перебором.

Во-вторых, если значение мало, что обычно и бывает, и если размер d не больше четверти размера n, то существует эффективный алгоритм вычисления d из открытых данных (n, e). Этот алгоритм не может быть расширен на случай, когда d имеет примерно такой же размер, как и n. Таким образом, чтобы защититься от этой атаки необходимо, чтобы d и n были примерно одного размера.

Следующим вопросом, который необходимо обсудить является использование общего модуля n несколькими абонентами. Как известно, в алгоритме RSA нельзя использовать общий модуль для нескольких пользователей, так как справедлива следующая теорема.

Теорема. Пусть два абонента A и B используют алгоритм RSA для защищенного обмена сообщениями. Пусть – открытый ключ абонента A; – секретный ключ абонента A; – открытый ключ абонента B; – секретный ключ абонента B. То есть A и B используют общий модуль n, но у каждого имеются свои уникальные показатели за- и расшифрования. Тогда каждый из них в состоянии детерминированно найти секретный показатель расшифрования другого абонента за квадратичное время (без факторизации n).

Необходимо указать на еще одно свойство алгоритма RSA, касающееся использования общего модуля несколькими пользователями. Пусть абоненты A и B используют общий модуль n, – показатель зашифрования абонента A, – показатель зашифрования абонента B. Если , то можно осуществить бесключевое чтение сообщения m, зашифрованного на этих ключах. Действительно, пусть

, .

Тогда, используя расширенный алгоритм Евклида, можно найти целые числа x и y такие, что , а затем вычислить

.

Одним из недостатков алгоритма RSA является наличие так называемой циклической атаки, которая заключается в следующем.

Пусть m – открытый текст, c – шифротекст, e – показатель зашифрования, n – модуль. Тогда

.

Злоумышленник может последовательно вычислять

, , ,

пока, при некотором целом положительном k, не выполнится соотношение

.

Такое k всегда существует, так как зашифрование является подстановкой на множестве . Тогда

.

 

 

– Конец работы –

Эта тема принадлежит разделу:

Методы и средства защиты компьютерной информации

Факультет электронной техники.. Кафедра Автоматизированные системы обработки информации и управления..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Практическое использование алгоритма RSA

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Актуальность защиты систем обработки информации
  В современном компьютерном сообществе атаки на информацию стали обыденной практикой. Злоумышленники используют как ошибки в написании и администрировании программ, так и методы соци

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

Наиболее распространенные методы взлома компьютерных систем
  1.3.1. Комплексный поиск возможных методов взлома   Часто злоумышленники проникают в систему не напрямую, «сражаясь» с системами шифрован

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

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

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

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

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

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

Мера стойкости шифра
  Шифром называется пара алгоритмов (E и D), реализующих каждое из указанных выше преобразований. Секретность второго из них делает данные недоступными

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

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

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

Базовая идея блочного шифра
  Отправной точкой в реализации рассматриваемого подхода является идея вырабатывать гамму для зашифрования сообщения … из самого сообщения! Однако сделать это непосредственно невозмож

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

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

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

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

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

Сравнения и их свойства
  Мы будем рассматривать целые числа в связи с остатками от деления их на целое положительное m, которое назовем модулем (слово “модуль” происходит от латинско

Вычисление степеней, возведение сравнений в степень
  Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому обсудим интересную задачу эффективного вычисления xn по заданным x и

Сравнения с одним неизвестным
  Числа, равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса о

Наибольший общий делитель
  Если u и v – целые числа, не оба рвные нулю, то их наибольшим общим делителем D(u, v) называется наибольшее целое число, на которое делятся без ос

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

Теоремы Эйлера и Ферма
  Теорема (Эйлера). При m > 1 и D(a,m) = 1 имеем aj(m) º 1 (mod m).

Однонаправленные функции
  Развитие криптографии в XX веке было стремительным, но неравномерным. Анализ истории ее развития как специфической области человеческой деятельности выделяет три основных периода.

Алгоритм RSA
  Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году так называемая система RSA. Ее название происходит от первых букв фамилий авто

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

Электронная подпись
  В чем состоит проблема аутентификации данных? В конце обычного письма или документа исполнитель или ответственное лицо обычно ставит свою подпись. Подобное действие обычно преследуе

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги