Взаимосвязь компонентов RSA - раздел Полиграфия, Криптографические методы защиты информации Задача Rsa: Даны Числа C И E, Последнее Из Кот...
Задача RSA: Даны числа C и E, последнее из которых удовлетворяет соотношению:
НОД(E, (p – 1)(q – 1)) = 1.
Требуется найти такое число m, что
mE = C (mod N).
Лемма. Задача RSA не сложнее проблемы факторизации.
Доказательство. Применяя алгоритм факторизации, разложим число N на простые множители, вычислим значение функции Эйлера Ф = j(N) и найдем
D = 1/E (mod Ф).
Теперь, зная число D, легко восстановить m, поскольку
CD = mED = m1 (mod Ф) = m (mod N).
Отсюда следует, что при известных p и q легко находятся d и m.
Самые большие числа, которые к настоящему времени удается разложить на множители за разумное время, имеют 500 двоичных знаков. В связи с этим, для обеспечения стойкости систем среднего срока действия, рекомендуют брать модули шифрования порядка 1024 бит. Для систем большого срока действия следует выбирать модули, состоящие из 2048 бит.
Секретная экспонента и проблема факторизации:
Лемма. Если известна секретная экспонента d алгоритма RSA, соответствующая открытому ключу (N, E), то число N можно эффективно разложить на множители.
Доказательство. При некотором целом s имеет место равенство
Ed – s(p – 1)(q – 1) = 1.
Возьмем произвольное целое число X ¹ 0. Тогда
XEd – 1= 1(mod N).
Вычисляем квадратный корень Y1 по модулю N:
что можно сделать, поскольку Ed – 1 известно и четно. Приходим к тождеству
которое можно использовать для определения делителей числа N с помощью вычисления НОД(Y1 – 1, N). Однако это будет работать только если Y1 ¹ ±1 (mod N).
Предположим, что нам не повезло и Y1 = ±1 (mod N). Если Y1 = –1 (mod N), вернемся к началу и выберем другое число X. Если Y1 = 1 (mod N), то можно взять еще один квадратный корень
Опять получаем
откуда НОД(Y2 – 1, N) – делитель числа N. К сожалению, здесь тоже может оказаться, что Y2 = ±1 (mod N). Тогда придется повторить все снова.
Алгоритм необходимо повторять до тех пор, пока мы не разложим N на множители и не придем к числу (ED – 1)/2t, которое уже не будет делиться на 2. В последнем случае придется вернуться к началу алгоритма, выбрать новое случайное значение X и все повторить.
Отсюда следует, что при известном d легко найти p и q.
Алгоритм, приведенный в доказательстве, - типичный пример алгоритма Лас-Вегаса, вероятностного по своей природе, которая проявляется в процессе работы. Но если уж ответ отыщется, то он будет обязательно верным.
Пример. Входные данные задачи RSA:
N = 1441499, E = 17 и d = 507905.
Напомним, что мы предполагаем известной расшифровывающую экспоненту d, которая обычно хранится в секрете. Опираясь на предыдущий алгоритм, найдем числа N. Положим
T1 = (Ed – 1)/2 = 4317192,
X = 2.
Для вычисления Y1, сделаем преобразования :
Поскольку Y1 оказался равным 1, нам нужно взять
T2 = T1/2 = (Ed – 1)/4 = 2158596 и .
Теперь
Снова нужно повторять предыдущие шаги, что приведет нас к
T3 = (Ed – 1)/8 = 1079298
и
Отсюда
и мы можем найти простой делитель числа N, вычислив
НОД(Y3 – 1, N) = 1423.
Значение функции Эйлера j(N) и проблема факторизации:
Лемма. Значение Ф = j(N) позволяет эффективно разложить число N на множители.
Доказательство. Имеем
Ф = (p – 1)(q – 1) = N – (p + q) + 1.
Следовательно, положив S = N + 1 – Ф, мы получим
S = p + q.
Нам нужно определить числа p или q, опираясь на их сумму S и произведение N. Рассмотрим многочлен
f(X) = (X – p)(X – q) = X2 – SX + N.
Теперь можно найти как p, так и q, решая квадратное уравнение f(X) = 0 стандартным образом:
Отсюда следует, что при известном j(N) легко найти p и q.
Пример. Открытый модуль N = 18923 криптосистемы RSA. Известно Ф = j(N) = 18648. Вычисляем
S = p + q = N + 1 – Ф = 276.
Соответствующий многочлен имеет вид:
f(X) = X2 – SX + N = X2 – 276X + 18923,
а его корни – p = 149, q = 127.
Все темы данного раздела:
Темплан 2011г., п. 57
Подписано в печать 25.10.11 Формат 60х84 1/16 Бумага офсетная. Офсетная печать.
Усл. печ. л.12,61 Уч.-изд. л. 12,61 Тираж 60 экз. Заказ
И
Краткая история развития криптографических методов.
Исторически сложились и дошли до наших дней три подхода к защите информации.
1. Физическая защита носителя информации.Данный подход предполагает использование комплекса ра
Термины и определения
Криптография - область науки, техники и практической деятельности, связанная с разработкой, применением и анализом криптографических систем защиты информации (рис.3). Основн
Характер криптографической деятельности
Нарушения защиты (также называются атаками) делятся на две основные группы – пассивные и активные атаки. Классификация атак приведена на рис.9, а их схемы на – на рис. 10.
Алгебраические модели шифров.
Алгебраическая модель, предложенная К. Шенноном.
Пусть X, K, Y – конечные множества открытых текстов, ключей и шифртекстов соответственно, |X| > 1, |K
Шифр RSA.
Пусть n = pq (q и p - простые), X = Y = Zn – кольцо вычетов по модулю n.
K = {(n, p, q, a
Вероятностные модели шифров.
Введем теперь вероятностную модель шифра. Определим априорные распределения вероятностей P(X), P(K) на множествах X и K соответственно. Тем самым для любог
Частотные характеристики.
Наиболее важная характеристика – избыточность открытого текста (подробно рассматривается в разделе надежности шифров).
Более простые:
· повторяемость букв, пар бу
Критерии распознавания открытого текста.
Строятся на основе моделей открытого текста двумя методами:
· на основе различения статистических гипотез;
· на основе ограничений по запретным или ожидаемым сочетаниям букв (ЪЪ и
Криптографическая стойкость шифров
Попытки противника по добыванию зашифрованной информации называют криптоатаками. В симметричных криптосистемах обычно рассматривают следующие криптоатаки:
Атака на основе шифртекст
Энтропия и избыточность языка
Свойства текстов изучаются методами теории информации, разработанной К. Шенноном. Ключевое понятие – энтропия, определяемая функцией от вероятностного определения и характеризующая
Расстояние единственности.
При дешифровании криптограмм может возникнуть ситуация, в которой несколько найденных ключей дают осмысленный текст. Так, криптограмму WNAJW, полученную при помощи шифра Цезаря, порождают два откры
Теоретическая стойкость шифров
При анализе теоретической стойкости шифров отвлекаются от объема реальных затрат на дешифрование. Основным критерием является возможность получения на основе шифртекста вероятностной информации
Практическая стойкость шифров.
Раздел практической стойкости рассматривает атаки на шифры, не являющиеся совершенными.
Центровым понятием в практической стойкости по Шеннону является рабочая характеристика шифра
Имитостойкость шифров. Имитация и подмена сообщения
Помимо пассивных действий со стороны противника возможны активные действия, состоящие в попытках подмены или имитации сообщения.
Если передается шифрованное сообщение y Î Y
Способы обеспечения имитостойкости
Основной причиной отсутствия какой-либо имитостойкости шифра гаммирования является то, что множество возможных открытых текстов длины l совпадает с множеством всех слов длины l в алфа
Коды аутентификации
Другой метод нашел распространение при аутентификации электронной передачи фондов в Федеральной резервной системе США. Подобные передачи должны быть аутентифицированы с использованием процедуры, ко
Помехостойкость шифров
Помимо целенаправленных искажений передаваемой шифрованной информации возможны также искажения, происходящие за счет наличия помех в канале связи. Такие помехи могут привести к искажениям и даже по
Виды симметричных шифров. Особенности программной и аппаратной реализации.
Работа симметричных шифров включает в себя два преобразования:
C = Ek(m) и m = Dk(C),
где m – открытый текст
Базовые шифрующие преобразования
Алфавитом, на котором действует блочный шифр, является множество двоичных векторов-блоков открытого текста одинаковой длины (64, 128 и т.д.). Так как с увеличением мощности алфавита энтропия на оди
Сеть Файстеля
Сеть Файстеля служит структурной основой построения большинства современных блочных криптоалгоритмов и является по сути методом смешивания текущей части шифруемого блока с результатом некоторой фун
Основные параметры блочных криптоалгоритмов.
Основными параметрами, характеризующими современные блочные криптографические алгоритмы, являются размер блока шифртекста (определяющий энтропию алфавита сообщения), размер ключевого пространства (
Алгоритм DES
DES представляет собой 64-битовый блочный алгоритм с 56-битовым ключом. Как и ГОСТ он построен на классической сети Файстеля и выполняется в течение 16 рау
Блочный шифр TEA
Один из самых простых в реализации, но признанно стойких криптоалгоритмов – TEA (Tiny Encryption Algorithm).
Параметры алгоритма:
Размер блока – 64 бита.
Длина ключа – 12
Международный алгоритм IDEA
Данный алгоритм получает на входе 64-битовый блок открытого текста (в процессе шифрования он разбивается на четыре 16-битовых подблока) и 128-битовый ключ, из которого генерируется пятьдесят два 16
Зашифрование и расшифрование в IDEA
Процесс шифрования предполагает два раунда и выходное преобразование. Один раунд состоит из преобразования входных блоков и субшифрования (см рис. 17). Основой субшифрования является основной строи
Алгоритм AES (Rijndael)
Алгоритм – победитель конкурса AES, объявленный в 2000 году, был разработан двумя бельгийскими криптографами Дименом (Daemen) и Рийменом (Rijmen). Эта криптосистема не является обобщением шифра Фей
Развертывание ключа.
Основной ключ алгоритма состоит из 128 битов, а нам нужно произвести 10 подключей K1, ..., K10, каждый из которых включает в себя четыре 32-битовых слова. Здесь
Синхронизация поточных шифрсистем
Многоалфавитные поточные шифры не распространяют ошибок при искажении отдельных знаков шифртекста, но оказываются неустойчивыми к пропускам/вставке знаков шифртекста, поскольку это приводит к непра
Структура поточных шифрсистем
Поточная система шифрования состоит из двух основных блоков:
· Управляющий блок (генератор ключевой последовательности - гаммы).
· Шифрующий блок (реализует преобразование, наклад
Регистры сдвига с обратной связью
Регистр сдвига с обратной связью состоит из двух частей: регистра сдвига и функции обратной связи.
Рис 19. Регистр сдвига с обратной связь
Алгоритм Берленкемпа-Месси
Пусть P – некоторое поле, e – единица поля P. Обозначим через начальный отрезок произвольной последовательности u элементов поля P. Будем говорить, что многочлен
Усложнение линейных рекуррентных последовательностей
Несмотря на достаточно большой период и хорошие статистические качества, линейные рекуррентные последовательности имеют простое строение (ярко выраженная аналитическая связь между предыдущими и пос
Современные поточные криптоалгоритмы
Краткие сведения о некоторых наиболее известных поточных криптоалгоритмах, считающихся относительно стойкими, сведены в табл.7.
Таблица 7. Стойкие поточные криптоалгоритмы
Режимы использования шифров
Для решения разнообразных криптографических задач блочные шифры используют в нескольких режимах работы. Рассмотрим этот вопрос на примере шифра DES.
Алгоритм DES может использоваться в сле
Группы, кольца.
Определение. Группа – множество G с операцией, которая: замкнута, обладает нейтральным элементом, ассоциативна. Группу с коммутативной операцией называют коммутат
Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма
Одна из центральных задач арифметики остатков - решение сравнения:
a · x º b (mod n)
- Если НОД (a, n) = 1, то существует ровно одно
Конечные поля
Целые числа по простому модулю – не единственный пример конечных полей. Более общий тип полей используется при рассмотрении таких криптосистем как AES, поточных шифров на основе РСЛОС и криптосисте
Алгоритм разложения чисел на простые множители.
Алгоритм А (Разложение на простые множители путем деления). По данному положительному целому числу N этот алгоритм находит простые множители p1 ≤
Алгоритм Евклида
Разделить целое число a на число b с остатком – это значит найти такие числа q и r c 0 £ r < |b|, при которых выполняется равенство
a
Расширенный алгоритм Евклида
Позволяет найти не только НОД(a, b), но и мультипликативный обратный к b по модулю a. Преобразуем формулы для алгоритма Евклида, выразив все остатки ri
Алгоритмы нахождения НОД и мультипликативного обратного по модулю
Алгоритм Евклида
Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольш
Символы Лежандра и Якоби. Извлечение корней
Пусть p – простое число, большее 2. Рассмотрим отображение
,
сопоставляющее каждому элементу поля его квадрат. На множестве ненулевых элементов поля Fp эт
Криптосистема RSA
Система построена на следующих функциях:
Односторонняя функция - умножение двух больших простых чисел:
N = p · q.
Обратная задач
Слабые моменты реализации RSA
Разделенный модуль: Поскольку арифметика остатков – дорогое удовольствие с точки зрения компьютера, весьма заманчиво разработать систему шифрования, в которой пользователи разделяю
Криптосистема Эль-Гамаля
Односторонняя функция - возведение в степень с фиксированным модулем P и основанием G.
H = Gx (mod P)
Обратная задача –
Криптосистема Рабина
Система базируется на трудности задачи факторизации больших целых чисел, а точнее на трудности извлечения квадратного корня по модулю составного числа N = p · q.
Эти з
Рюкзачные криптосистемы
Задача об укладке рюкзака. Задано множество {vi} из k натуральных чисел и целое число S.
Требуется найти такое k-разрядное число
Криптосистема Меркля-Хеллмана
Предположим, что элементы открытого текста имеют в качестве своих числовых эквивалентов k-разрядные двоичные числа n.
Каждый пользователь выбирает быстрорастущий набор {v
Шифрсистема Мак-Элиса
Идея, лежащая в основе данной системы, состоит в выборе корректирующего кода, исправляющего определенное число ошибок, для которого существует эффективный алгоритм декодирования. С помощью секретно
Криптографические хэш-функции
Хэш-функции — это функции, предназначенные для "сжатия" произвольного сообщения или набора данных, записанного, как правило, в двоичном алфавите, в некоторую битов
Блочно-итерационные и шаговые функции
Пусть X - множество сообщений (последовательности символов некоторого алфавита, как правило, двоичного). Пусть Y — множество двоичных векторов фиксированной длины.
Хэ
Ключевые функции хэширования
В криптографических приложениях к ключевым функциям хэширования предъявляются следующие основные требования:
— невозможность фабрикации;
— невозможность модификации.
Бесключевые функции хэширования
Обычно требуется, чтобы бесключевые хэш-функции обладали следующими свойствами:
1) однонаправленность, (по Y = h(X) трудно определить X)
2) у
Схемы использования ключевых и бесключевых функций
Схемы использования ключевых хэш-функций (кодов аутентичности сообщений) приведены на рис. 34.
М
M
Задачи и особенности электронно-цифровой подписи
Цифровая подпись для сообщения является числом, зависящим от самого сообщения и от некоторого секретного, известного только подписывающему субъекту, ключа. При этом предполагается,
Алгоритм цифровой подписи Эль-Гамаля
Схема цифровой подписи Эль-Гамаля основана на сложности вычисления дискретных логарифмов в конечном поле.
Так же как и для шифрования Эль-Гамаля выбираются параметры системы:
P
Алгоритм цифровой подписи Шнорра
Принадлежит семейству цифровых подписей на дискретных логарифмах и интересна с точки зрения практического применения в смарт-картах для реализации процедуры аутентификации. Алгоритм также может быт
Алгоритм цифровой подписи Ниберга-Руппеля
Данный алгоритм также базируется на сложности дискретного логарифмирования и является примером схемы с восстановлением сообщения.
Все схемы подписи с восстановлением сообщения используют н
Алгоритм цифровой подписи DSA
Рассмотрим данный алгоритм более подробно, так как на его основе построен стандарт цифровой подписи DSS. DSA – алгоритм подписи с дополнением, в котором собственно подпись состоит из двух 160-битов
Симметричные (одноразовые) цифровые подписи
Рассмотренные системы цифровой подписи имеют один потенциальный недостаток. Он состоит в возможности построения новых эффективных алгоритмов для решения этих математических задач. Поэтому в реальны
Двусторонние протоколы.
Различают протоколы, в которых стороны заранее располагают какой-либо известной им обоим секретной информацией, и протоколы, не требующие этого условия.
Пусть стороны А и В з
Трехсторонние протоколы.
Рассмотрим протоколы распределения ключей между парами участников с использованием третьей стороны Т, называемой центром. В этом качестве обычно выступает некоторый выделенный узел сети, или
Сертификаты открытых ключей
Как правило, при использовании открытых ключей хранят не сами ключи, а их сертификаты. Сертификат представляет собой набор данных
CA=(A,kA,t,SkT
Открытое распределение ключей
Открытое распределение ключей позволяет двум абонентам выработать общий секретный ключ путем динамического взаимодействия на основе обмена открытыми сообщениями без какой-либо общей секретной инфор
Схемы предварительного распределения ключей в сети связи
Если число абонентов сети засекреченной связи невелико, то и число распределяемых ключей также невелико. Для больших же сетей распределение ключей становится очень серьезной проблемой. Она заключае
Способы установления ключей для конференц-связи
Еще один тип распределения ключей между группами пользователей дают протоколы распределения ключей для проведения конференц-связи. Несмотря на внешнюю схожесть с протоколами разделения секрета, они
Методы применения шифрования данных в локальных вычислительных сетях
В настоящее время применяется два основных метода шифрования при передаче информации – абонентское шифрование и канальное шифрование.
Рис.37. Схемы абонентского и канальног
Обеспечение секретности данных при долгосрочном хранении.
В последнее время для характеристики способа шифрования хранимой на диске информации все чаще применяют два термина: «прозрачное шифрование» и «непрозрачное шифрование». На деле же речь идет о двух
Задачи обеспечения секретности и целостности данных и ключей при краткосрочном хранении
При разработке программного обеспечения по защите данных с использованием криптографических алгоритмов необходимо уделять особое внимание решению следующих задач:
1.
Обеспечение секретности ключей при долгосрочном хранении
Основные способы хранения ключевой информации:
1. Хранение на логическом диске ПК. Наиболее неудачное решение. При работе одного пользователя с несколькими компьютерами ко
Атаки на симметричные криптоалгоритмы
Существует множество типов атак на симметричные алгоритмы шифрования и хэш-функции, каждый из которых обладает своей степенью сложности:
1. Атака с использованием только шифрованно
Анализ поточных криптосистем.
При проведении криптоанализа поточных алгоритмов решаются следующее задачи:
1. Распознавание ЛРП:
Если s0,s1,… - линейная рекуррентная последов
Дифференциальный криптоанализ.
Первые открытые упоминания в литературе с 1990 года в работах Мерфи, Бихема и Шамира. Методика анализа строится индивидуально для каждого алгоритма и основана на знании пар сообщений m и
Линейный криптоанализ.
Более новым направлением в криптоанализе является линейный криптоанализ. Метод линейного криптоанализа заключается в построении линейной аппроксимации преобразования, выполняемого в ходе шифрования
Атаки на хэш-функции и коды аутентичности
Атака «дней рождения».
Этот тип атаки основан на том факте, что одинаковые значения, называемые также коллизиями (collisions), появляются намного быстрее, чем можно
Двусторонняя атака.
Является разновидностью атак, в основе которых лежит парадокс задачи о днях рождения, носит также название атаки "встреча на середине" (meet-in-the-middle attacks). (В совокупности
Атаки на криптосистемы, основанные на сложности задачи факторизации.
Очевидное направление криптоанализа систем шифрования и цифровой подписи, основанных на сложности решения задачи факторизации – разработка переспективных методов факторизации целых чисел.
Возможные атаки на систему RSA.
1. Факторизация модуля n = p · q.
2. Решение сравнения для конкретного y - нахождение корня степени e из y по модулю p. (задача не менее сл
Эллиптические кривые
Проективная плоскость P2(K) над полем K определяется как множество троек (X, Y, Z) не равных одновременно нулю элементов X, Y, Z &
Групповой закон.
Рассмотрим для char K ¹ 2, 3 замену переменных
переводящую кривую заданную длинной формой Вейерштрасса в изоморфную ей кривую, определяемую короткой формой Вейе
Эллиптические кривые над конечными полями
Количество Fq-рациональных точек над эллиптической кривой конечно. Обозначим его #E(Fq). Ожидаемое число точек кривой бл
Проективные координаты
Одна из проблем, возникающих при использовании формул группового закона как при большой, так и при четной характеристике поля, связана с необходимостью деления. Деление в конечном поле считается до
Сжатие точек
Во многих криптографических протоколах возникает необходимость хранить в памяти или передавать по сети отдельные точки эллиптической кривой. В аффинных координатах это можно сделать при помощи двух
Эллиптические группы
Эллиптическая группа по модулю p определяется следующим образом. Выбираются два неотрицательных числа a и b, которые меньше p и удовлетворяют условию
4a
Кривые над полем характеристики 2
Пусть основное поле K = Fq с q = 2n при . В этом случае j-инвариант кривой вычисляется по формуле Условие j(E
Алгоритм цифровой подписи EC-DSA
Алгоритм DSA можно обобщить на произвольную конечную абелеву группу A , в которой сложно решается задача дискретного логарифмирования, порождающий элемент G имеет простой порядок Q
Квантовая криптография
Идея квантовой криптографии основывается главным образом на физике фотонов. Как показано на рисунке 40, фотон во время своего движения производит колебания. Все четыре фотона летят в одном направле
СПИСОК ИСПОЛЬЗОВАННОЙ И РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
1. Алферов, А. П. Основы криптографии. учебное пособие/ А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. – М.: Гелиос-АРВ, 2001. – 480 с.
2. Бабенко, Л. К. Совр
Новости и инфо для студентов