русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Алгоритм ЦП RSA


Дата добавления: 2013-12-23; просмотров: 546; Нарушение авторских прав


Алгоритмы ЕЦП

Российский стандарт хеш-функций

Алгоритм безопасного хеширования SHA

 

Для использования совместно с алгоритмами ЦП DSA

 

Для рассмотрения самостоятельно

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

 

 

 

ГОСТ Р.34.11-94 определяет алгоритм и процедуру вычисления h(.) для любых последовательных двоичных символов, применимых в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя может быть и использован с другим блочным алгоритмом шифрования – 64-битовым блоком и 256-битным ключом. Данная h(.) формирует 256-битное h-значение.

Функция сжатия:

Hi = f(Mi, Hi-1)

Hi, Mi – 256-битные величины

Определяется следующим образом:

- Генерируется 4 ключа шифрования kj (j=1..4) путем линейного смешивания Mi, Hi-1, const

- Каждый ключ kj используется для ­­шифрования 64-юитных подслов слова Hi-1 в режиме простой замены

64 → hj → Hi-1

Результирующая последовательность длиной 256 бит запоминается со временной переменной S

Sj = Ekj (hj) S4, S3, S2, S1 → S

- Значение Hi является сложной, хотя и линейной функцией смешивания S, Mi, Hi

 

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

Hn – значение последнего блока сообщения

Z – значение контрольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения

L – длина сообщения

 

Эти 3 переменные и дополнительный последовательный блок М’ объединяются в h-значение следующим образом:

+
H = f(Z M’, f(L, f(M’, Hn)))

Данная h(.) определена российским стандартом для использования с российским стандартом ЭЦП.



 

 

Лекция 11

 

 

 

Для постановки цифровой подписи (ЦП) для каждого абонента генерируется пара ключей: секретный и открытый.

Секретный хранится абонентом в тайне и используется для формирования ЭЦП.

Открытый известен всем пользователям и предназначен для проверки ЭЦП получателя.

Открытый ключ не позволяет выделить секретный.

Для генерации пары ключей в алгоритме ЭЦП, как и в асинхронных системах шифрования, используются схемы, основанные на применении однонаправленных функций. Схемы делятся на 2 группы. В основе лежат: задача факторизации (разделение на множители) больших чисел – задача дискретного логарифмирования.

 

 

Сначала необходимо выделить пару ключей. Для этого отправитель (автор) вычисляет 2 больших простых числа P, Q. Затем находит их произведение и значение функции φ(N) = (P-1)(Q-1) , где N = P*Q

Вычисляет число E: E <= φ(N), НОД (Е, φ(N)) = 1

Вычисляет число D: D < N, E * D ≡ 1 mod φ(N)

Пара чисел E, N → открытый

D → закрытый

 

М
БС
SEmodN= h(M)
БС
ГК
mD
SE
да
нет
E, N
S=mD mod N
SE mod N = m’
D, N
M
m=h(M)
Отправитель
Канал
Получатель
m=h(M)

 


M – сообщение

БС – блок сжатия

ГК – генератор ключей

 

Если соблюдается условие SZ mod N = h(M), то получатель признает пару M и S подлинной.

Доказано, что только обладатель секретного кода D может сформировать ЦП. S по документу M, а определить секретной ключ D по открытому E не легче, чем разложить модуль N на множители, кроме того, можно математически доказать, что результат проверки ЦП S будет степени n+p в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому ключу E. Поэтому Е – идентификатор подписывания.

Недостатки:

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

- Для обеспечения криптостойкости RSA ну уровне национальной системы США, необходимо использовать при вычислениях N, D, E целые числа не менее, чем 2256, что требует затрат >20-30% вычислительных затрат других алгоритмов.

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

 

Более надежный и удобный алгоритм – Эль Гамаля (EGSA)

 

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

Сразу генерируют пару ключей. Для этого берут большие простые числа p и g.

p~21024

g < p ~ 2512

 

Отправитель выбирает случайное число Х, (1 <= X <= p-1) и вычисляет Y = GX mod P – открытый ключ для проверки ЦП и отправителя получателем.

Х – секретное

Для подписи сообщения М отправитель хеширует ее с помощью h-функции

m= h(M) 1 < m < p-1

и генерирует случайное целое число k:

1 < k < p-1,

k, p-1 – взаимопростые

Отправитель вычисляет целое число а:

а = G* mod p

Применяя расширенный алгоритм Евклида вычисляет с помощью секретного ключа Х целое число b из уравнения:

m = X*a + k*b (mod (p-1))

Пара чисел a и b образуют ЦП S, выставляемую под документом М.

M, a, b – передаются получателю

X, k – секретные данные

 

После приема подписанного сообщения M, a, b, получатель проверяет, соответствует ли подпись сообщения М. Для этого по принятому М вычисляет:

m = h(M)

A = Yaab (mod p)

и признает М подлинным, если А = Gm mod p

то есть Yaab mod p = Gm mod p

 

Математически равенство выполняется, когда подпись получена с помощью того секретного ключа Х, из которого получен Y. Тем самым удостоверится, что отправителем сообщения М является обладатель секретного ключа Х не раскрывая сам ключ.

Выполнение ЭП по EGSA требует нового значения k. Если k раскрыто, то раскроется X.

Схема ЦП EGSA имеет преимущество перед RSA.

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

2. При выборе модуля p достаточно просто проверить, что оно простое, а (p-1) есть простой сомножитель, то есть 2 просто проверяемых условия.

3. Формирование подписи по EGSA не позволяет вычислить подписи под новыми М без знания ключа.

 



<== предыдущая лекция | следующая лекция ==>
Однонаправленная ХЕШ-функция | Защита от несанкционированного доступа


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.086 сек.