 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Использование маркантов или производных ключей
Данный метод используется для увеличения срока действия ключевой информации. Заключается в использовании для шифрования не непосредственно ключей, хранимых у абонентов, а некоторых производных ключей из них получаемых. Для простоты будем считать, ключи двоичными векторами длины N.
1. Использование маркантов.
Заключается в использовании вместо ключа K двоичного вектора S, полученного побитным суммированием K и случайного двоичного вектора M, называемого маркантом, при этом маркант передается в открытом виде отправителем получателю. Данный метод очень распространен при использовании шифров гаммирования, для обеспечения стойкости к перекрытиям. Действительно использование одного и того же ключа, но разных маркантов не снижает стойкости шифра. Однако этот метод обладает одним недостатком - восстановление одного сеансового ключа, обеспечивает чтение всех ранее переданных с использованием текущего базового ключа сообщений (т.н. называемое чтение назад).
2. Использование производных ключей.
Заключается в использовании вместо ключа K для шифрования сообщения с номером L двоичного вектора, полученного по правилу - KL=FL(K), где F, отображающая VN(2) в VN(2), псевдооднонаправленная функция (см.лекцию «Новое направление в криптографии»), т.е. функция не допускающая вычисление аргумента по значению за приемлемое время, а FL - L -тая степень функции F. Таким образом, для шифрования первого сообщения используется ключ K1=F(K), а для шифрования сообщения L (L>1) ключ KL=F(KL-1). В силу псевдооднонаправленности функции F чтение назад невозможно.
Остается добавить, что срок службы основного ключа при применении данного метода определяется отдельно с учетом результатов анализа, используемого шифра и конкретных условий эксплуатации сети связи. Опыт показывает, что в среднем срок службы ключа может увеличен в 10 раз, а в случае шифров гаммирования, требующих смены ключа на каждое сообщение применение такого подхода увеличивает время эксплуатации ключа в сотни и даже тысячи раз.
Применение различных подходов к улучшению эксплуатационных характеристик ключевых систем с симметричными ключами позволило продолжить их использование в условиях бурного развития телекоммуникаций и как следствие - роста числа потребителей услуг секретной связи. Однако, в тот момент когда защита информации стала востребована крупными независимыми от государства корпорациями (впервые всерьез эта проблема была поднята в конце 60-ых годов в США) стало ясно, что симметричные ключевые системы непригодны для коммерческой эксплуатации.
Основных причин было две:
1. Ни одна даже самая крупная компания не может позволить себе, по экономическим соображениям, содержать специальную службу, занимающуюся только развозом ключей по ее филиалам.
2. При участии в обмене шифрованными сообщениями двух и более независимых организаций возникает вопрос о том, кто собственно, генерирует ключи, т.е. фактически встает вопрос о взаимном доверии различных фирм друг к другу.
Предложение доверить генерацию и распределение ключей единой государственной службе, понятно энтузиазма не вызвал. Система, которая устраивала государственные организации начал давать сбои при переносе ее в коммерческие области.
27. Причины непригодности использования симметричных криптосистам для коммерческой эксплуатации
Основным недостатком симметричного шифрования является то, что секретный ключ должен быть известен и отправителю, и получателю. С од-ной стороны, это ставит новую проблему рассылки ключей.
сложность управления ключами в большой сети. Означает квадратичное возрастание числа пар ключей, которые надо генерировать, передавать, хранить и уничтожать в сети. Для сети в 10 абонентов требуется 45 ключей, для 100 уже 4950, для 1000 — 499500 и т. д.
сложность обмена ключами. Для применения необходимо решить проблему надёжной передачи ключей каждому абоненту, так как нужен секретный канал для передачи каждого ключа обеим сторонам.
28. Новое направление в криптографии, постулаты У. Диффи и М. Хеллмана
В середине 70-х гг. ХХ столетия произошел настоящий прорыв в современной криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь
отправной точкой принято считать работу, опубликованную Уитфилдом Диффи и Мартином Хеллманом в 1976 г. под названием "Новые направления в современной криптографии". В ней впервые сформулированы принципы обмена шифрованной информацией без обмена секретным ключом.
Независимо к идее асимметричных криптосистем подошел Ральф Меркли. Несколькими годами позже Рон Ривест, Ади Шамир и Леонард Адлеман открыли систему RSA, первую практическую асимметричную криптосистему, стойкость которой была основана на проблеме факторизации больших простых чисел. Асимметричная криптография открыла сразу несколько новых прикладных направлений, в частности системы электроннойцифровой подписи (ЭЦП) и электронных денег.
В 1980–90-е гг. появились совершенно новые направления криптографии: вероятностное шифрование, квантовая криптография и другие. Осознание их практической ценности еще впереди. Актуальной остается и задача совершенствования симметричных криптосистем. В этот же период были разработаны нефейстелевские шифры (SAFER, RC 6 и др.), а в 2000 г.после открытого международного конкурса был принят новый национальный стандарт шифрования США – AES.
Постулаты У. Диффи и М. Хеллмана:
1. Ключ KA для шифрования сообщений входящих к абоненту А должен изготовить сам абонент А. Он же изготавливает ключ KA-1 - для расшифрования данных сообщений.
2. Ключ KA рассылается всем желающим, отправлять сообщения абоненту A, ключ KA-1 держится в секрете.
3. Ключ KA-1 не восстанавливается по ключу KA.
Алгоритм Диффи-Хелмана (1976) использует функцию дискретного возведения в степень и используется для открытого распределения ключей по открытому каналу связи.
Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана.
Цель алгоритма состоит в том, чтобы два участника могли безопасно обменяться ключом, который в дальнейшем может использоваться в каком-либо алгоритме симметричного шифрования. Сам алгоритм Диффи-Хеллмана может применяться только для обмена ключами.
Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа Q как числа, чьи степени создают все целые от 1 до Q – 1. Это означает, что если А является примитивным корнем простого числа Q, тогда числа
A mod Q, A2 mod ……AQ-1 mod Q
являются различными и состоят из целых от 1 до Q – 1 с некоторыми перестановками. В этом случае для любого целого B < Q и примитивного корня A простого числа Q можно найти единственную экспоненту Х, такую, что
Y =AX mod Q,где 0≤ X ≤ (Q-1).
Экспонента X называется дискретным логарифмом, или индексом Y, по основанию A mod Q. Это обозначается как
indA,Q(Y)
Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.
| Общеизвестные элементы | |
| Q | Простое число |
| A | A < Q и A является примитивным корнем Q |
| Создание пары ключей пользователем I | |||
| Выбор случайного числа X i (закрытый ключ) | Xi<Q | ||
| Вычисление числа Y i (открытый ключ) | Yi=AXimod Q | ||
| Создание открытого ключа пользователем J | |||
| Выбор случайного числа X j (закрытый ключ) | X j< Q | ||
| Вычисление случайного числа Y j (открытый ключ) | Yj=A Ximod Q | ||
| Создание общего секретного ключа пользователем I |
| K= (Yi)Ximod Q |
| Создание общего секретного ключа пользователем J |
| K=(Yj)Xjmod Q |
Предполагается, что существуют два известных всем числа: простое число Q и целое A, которое является примитивным корнем Q. Теперь предположим, что пользователи I и J хотят обменяться ключом для алгоритма симметричного шифрования. Пользователь I выбирает случайное число Xi< Q и вычисляет Y i=AXi mod Q. Аналогично пользователь J независимо выбирает случайное целое число Xj<Q и вычисляет Y i=AXj mod Q. Каждая сторона держит значение Х в секрете и делает значение Y доступным для другой стороны. Теперь пользователь I вычисляет ключ как K=(Yi)Xi mod Q, и пользователь J вычисляет ключ как K= (Yj)Xj mod Q. В результате по правилам модульной арифметики оба получат одно и то же значение:
K= (Yj)Xi mod Q= (AXj mod Q)Xi mod Q = (A Xj)Xi mod Q = A XjXi mod Q =
(A Xi)Xj mod Q= (A Xi mod Q)Xj mod Q = (Yi)Xj mod Q.
Таким образом, две стороны обменялись секретным ключом. Так как Xi и Xj являются закрытыми, противник может получить только следующие значения: Q, A, Yi и Yj. Для вычисления ключа атакующий должен взломать дискретный логарифм, т. е. вычислить
Xj = ind a,q(Yj)
29. Описание системы с открытыми ключами
Метод достижения одновременно аутентичности и целостности при распределении открытых ключей заключается в использовании сертификатов. Система, основанная на сертификатах, предполагает, что имеется центральный орган (ЦО), как и в случае распределения секретных ключей. Далее предполагается, что каждый пользователь может осуществлять безопасное взаимодействие с ЦО. Для этого требуется, чтобы у каждого пользователя был открытый ключ ЦО – 
Тогда каждый пользователь А может зарегистрировать в ЦО свой открытый ключ ЕА. Поскольку Е Д является открытым, это можно сделать по почте, по открытому каналу электросвязи и т.п.
Обычно при регистрации в ЦО А будет следовать определенной ау-тентификационной процедуре. Альтернативным вариантом может быть обработка регистрации системой, имеющей древовидную структуру: ЦО выдает сертификаты местным представителям, которые в дальнейшем действуют в качестве посредников в процессе регистрации пользователя на более низких уровнях иерархии.
В любом случае, в ответ А получает сертификат, подписанный ЦО и содержащий ЕА, т.е. ЦО формирует сообщение М, содержащее ЕА, идентификационную информацию для А (IА), период действия сертификата и т.п. Затем ЦО вычисляет CERTА = D ЦО(М), который и становится сертификатом A. CERTA делается общедоступным документом, который содержит ЕА и одновременно аутентифицирует его, поскольку сертификат подписан ЦО. Сертификаты могут распространяться ЦО, пользователями или использоваться в иерархической системе. Включение срока действия является обобщением временного штампа, что обеспечивает защиту от использования скомпрометированных ключей.
Однако, проблема устаревших данных не может быть решена только с помощью временных штампов, поскольку сертификат может стать недействительным до истечения срока его действия вследствие компрометации или по административным причинам. Поэтому, если сертификаты хранятся у пользователей (а не выдаются каждый раз ЦО при их использовании), ЦО должен время от времени публиковать списки аннулированных сертификатов.
Некоторые свойства рассмотренных схем могут быть объединены в подход, известный под названием "телефонный справочник", с использованием электронного эквивалента, такого как гибкий диск, содержащий сертификаты. Это облегчит использование, поскольку пользователь сможет быстро связаться с другим, очень быстро получая доступ к сертификату последнего.
30. Система электронной подписи
Электро́ннаяпо́дпись (ЭП) — реквизит электронного документа, позволяющий установить отсутствие искажения информации в электронном документе с момента формирования ЭП и проверить принадлежность подписи владельцу сертификата ключа ЭП. Значение реквизита получается в результате криптографического преобразования информации с использованием закрытого ключа ЭП.
Электронная подпись предназначена для идентификации лица, подписавшего электронный документ[1]. Кроме этого, использование электронной подписи позволяет осуществить:
§ Контроль целостности передаваемого документа: при любом случайном или преднамеренном изменении документа подпись станет недействительной, потому что вычислена она на основании исходного состояния документа и соответствует лишь ему.
§ Защиту от изменений (подделки) документа: гарантия выявления подделки при контроле целостности делает подделывание нецелесообразным в большинстве случаев.
§ Невозможность отказа от авторства. Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец не может отказаться от своей подписи под документом.
§ Доказательное подтверждение авторства документа: Так как создать корректную подпись можно, лишь зная закрытый ключ, а он должен быть известен только владельцу, то владелец пары ключей может доказать своё авторство подписи под документом. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д.
Все эти свойства ЭП позволяют использовать её для следующих целей[2]:
§ Декларирование товаров и услуг (таможенные декларации)
§ Регистрация сделок по объектам недвижимости
§ Использование в банковских системах
§ Электронная торговля и госзаказы
§ Контроль исполнения государственного бюджета
§ В системах обращения к органам власти
§ Для обязательной отчетности перед государственными учреждениями
§ Организация юридически значимого электронного документооборота
§ В расчетных и трейдинговых системах
31. Открытое шифрование и электронная подпись
1. Абонент А изготавливает пару алгоритмов преобразования открытого текста - алгоритм шифрования E и алгоритм расшифрования D со свойством - для любого открытого текста M выполняется соотношение D(E(M)) = M.
2. Алгоритм E рассылается всем желающим, отправлять сообщения абоненту A, алгоритм D держится в секрете.
Алгоритм D не восстанавливается по алгоритму E.
Данная система называется системой открытого шифрования.
Для формирования системы ЭЦП можно использовать криптографическую систему Ривеста-Шамира-Адлемана.
Пользователь А вырабатывает цифровую подпись предназначенного для пользователя В сообщения М с помощью следующего преобразования:
SIG(m)=Eeb,nb(Eda,na(M))
При этом он использует: свое секретное преобразование; открытое преобразование Eeb,nb пользователя В. Eda,na
Затем он передает пользователю В пару{M,SIG(M)}.
Пользователь В может верифицировать это подписанное сообщение сначала при помощи своего секретного преобразованияс целью получения Edb,nb
Eda,na(M)=Edb,nb(SIG(M))=Edb,nb(Eeb,nb(Eda,na(M)))
и затем открытого Eea,na пользователя А для получения сообщения М:
M= Eea,na(Eda,na(M))
Затем пользователь В производит сравнение полученного сообщения М с тем, которое он получил в результате проверки цифровой подписи, и принимает решение о подлинности/подложности полученного сообщения.
В рассмотренном примере проверить подлинность ЭЦП может только пользователь В. Если же требуется обеспечение возможности верификации ЭЦП произвольным пользователем (например, при циркулярной рассылке документа), то алгоритм выработки ЭЦП упрощается, и подпись вырабатывается по формуле SIG(M)= Eda,na(M), а пользователи осуществляют верификацию с использованием открытого преобразования отправителя (пользователя А): M= Eea,na(SIG(M))= Eea,na(Eda,na(M))
Недостатком подобного подхода является то, что производительность асимметричной криптосистемы может оказаться недостаточной для удовлетворения предъявляемым требованиям.
Возможным решением является применение специальной эффективно вычисляемой функции, называемой хэш-функцией или функцией хэширования. Входом этой функции является сообщение, а выходом – слово фиксированной длины, много меньшей, чем длина исходного сообщения. ЭЦП вырабатывается по той же схеме, но при этом используется не само сообщение, а значение хэш-функции от него.
32. Oсновные результаты статьи Диффи и Хеллмана
Алгоритм Диффи-Хелмана (1976) использует функцию дискретного возведения в степень и используется для открытого распределения ключей по открытому каналу связи.
Первая публикация данного алгоритма открытого ключа появилась в статье Диффи и Хеллмана, в которой вводились основные понятия криптографии с открытым ключом и в общих чертах упоминался алгоритм обмена ключа Диффи-Хеллмана.
Цель алгоритма состоит в том, чтобы два участника могли безопасно обменяться ключом, который в дальнейшем может использоваться в каком-либо алгоритме симметричного шифрования. Сам алгоритм Диффи-Хеллмана может применяться только для обмена ключами.
Алгоритм основан на трудности вычислений дискретных логарифмов.
Безопасность обмена ключа в алгоритме Диффи-Хеллмана вытекает из того факта, что, хотя относительно легко вычислить экспоненты по модулю простого числа, очень трудно вычислить дискретные логарифмы. Для больших простых чисел задача считается неразрешимой.
Следует заметить, что данный алгоритм уязвим для атак типа «man-in-the-middle». Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников Yi и Y j, создать свою пару открытого и закрытого ключа 
и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.
33. Однонаправленные функции, построение однонаправленных функций с секретами.
В основе идей, изложенных в статье Уитфилда Диффи и Мартина Хеллмана лежало понятие однонаправленной функции.
Пусть X, Y - произвольные равномощные множества, F - биективная функция, отображающая X в Y. Обозначим через Q(F) - сложность вычисления значения F(x) для произвольного xÎX, через Q(F-1) - сложность вычисления по произвольному yÎY значения x, такого, что F(x)=y (сложность вычисления понимается в стандартном смысле теории сложности).
В данных терминах будем говорить, что функция F является однонаправленной, если Q(F-1) много больше Q(F). Как видно, данное определение не является достаточно строгим. Под термином «много больше» можно подразумевать весьма разные понятия, например то, что вычисление F имеет полиномиальную сложность, а F-1- экспоненциальную.
Для того, чтобы под понятием однонаправленная функция понимался вполне конкретный класс объектов считают, что под термином «много больше», понимается следующее:
1. Сложность вычисления F такова, что алгоритм ее вычисления реализуем на современной технике и выдает ответ за приемлемое время
2. Сложность вычисления F-1 такова, что алгоритм ее вычисления либо не реализуем на современной технике, либо не дает ответ за приемлемое время.
Что считать приемлемым временем следует из практических соображений - вычисление F не должно замедлять скорости обработки информации, а сложность вычисления F-1 должна быть столь велика, чтобы не допускать обращения функции F злоумышленником.
На момент опубликования статьи авторы не имели конкретной системы ЭЦП и по этой причине их система ОРК повисла в воздухе, так как в ней не решался вопрос аутентификации отправителя сообщения. Такое решение появилось значительно позднее - в 1984 году. Пока же авторы предложили еще одну абстрактную схему с использованием так называемых однонаправленных функций с секретом (trapdoor one-way function). Строгое определения однонаправленной функции с секретом дать весьма затруднительно.
Попробуем сформулировать его следующим образом.
Однонаправленной функцией с секретом S называется биективная функция F отображающая произвольное множество X в множество Y, зависящая от параметров T1,...,TL и обладающая следующим свойствами:
1. Существует некоторая функция S, зависящая от параметров T1,...,TL
2. По виду функции F значение функции S для конкретных параметров T1,...,TL не восстанавливается
3. Сложность вычисления значения F-1(y) " yÎY при знании значения S(T1,...,TL) не превосходит сложности вычисления прямого преобразования F
4. Сложность вычисления преобразования F-1 без знания значения S(T1,...,TL) много больше сложности вычисления прямого преобразования F.
Иными словами, без знания дополнительной информации о функции F она является однонаправленной, при наличии некоторой дополнительной информации (которую нельзя получить по функции F) обратное преобразование эффективно вычисляемо.
Для иллюстрации данного понятия можно привести следующий пример. Известно, что не существует общего метода решения уравнений четвертой степени над полем действительных чисел.
34. Система RSA. Использование алгоритма Евклида для расчета секретного ключа d.
Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Адлеманом (L. Adleman). Эта асимметричная криптосистема в настоящее время является широко распространенной во всем мире. В основе алгоритма RSA лежат идеи алгоритма Диффи-Хеллмана.
Первым этапом любого асимметричного алгоритма шифрования является создание пары ключей: открытого и закрытого (с последующим свободным распространением открытого ключа).
Для алгоритма RSA этап создания ключей состоит из следующих операций:
· Выбираются два простых числа p и q;
· Вычисляется их произведение n = p*q;
· Выбирается произвольное число e (e<n), такое, что НОД (e, (p-1)(q-1))=1
, т. е. должно быть взаимно простым с числом (p-1)(q-1);
· методом Евклида решается в целых числах уравнение
e*d+ (p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах;
· два числа (e, n) – публикуются как открытый ключ;
· число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e, n).
Собственно шифрование с помощью этих чисел производится следующим образом:
· отправитель разбивает свое сообщение на блоки, равные k= [log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа. Подобный блок может быть интерпретирован как число из диапазона (0; 2i-1);;
· для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e) mod n
35. Алгоритма цифровой подписи Эль Гамаля, преимущества по сравнению с методом RSA, недостатки.
Система Эль-Гамаля – это криптосистема с открытым ключом, основанная на проблеме логарифма, Система включает как алгоритм шифрования, так и алгоритм цифровой подписи. В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма.
По сравнению с методом RSA данный метод имеет целый ряд преимуществ:
1. При заданном уровне стойкости алгоритма цифровой подписи целые числа, с которыми приходится проводить вычисления, имеют запись на 25% короче, что соответственно уменьшает сложность вычислений почти в 2 раза и позволяет заметно сократить объем используемой памяти;
2. При выборе параметров достаточно проверить всего два достаточно легко проверяемых условия;
Алгоритм не запатентован, и не требует специальной лицензии на его реализацию. Кроме того данный алгоритм подписи, не допускает его использования в качестве алгоритма шифрования (в отличии от RSA в котором шифрование и подпись суть одно и то же), а следовательно не подпадает ни под какие экспортные ограничения из США.
Множество параметров системы включает простое число p и целое число g, степени которого по модулю р порождают большое число элементов Zp. У пользователя А есть секретный ключ а и открытый ключ у, где у = ga(mod p). Предположим, что пользователь В желает послать сообщение т пользователю А. Сначала В выбирает случайное число k, меньшее р, и вычисляет y1=gk(mod p), y2=m*(yk(mod p)),
где * обозначает побитовое "исключающее ИЛИ". В посылает А пару (у1, у2).
После получения шифрованного текста пользователь А вычисляет m=(y1a mod p)*y2.
Известен вариант этой схемы, когда операция ⊕ заменяется на умножение по модулю р. Это удобнее в том смысле, что в первом случае текст (или значеникции) необходимо разбивать на блоки той же длины, что и число yk(mod p) Во втором случае этого не требуется и можно обрабатывать блоки текста заранее заданной фиксированной длины (меньшей, чем длина числа р). Уравнение расшифрования в этом случае будет таким: m=y2/y1k mod p.
Однако, при всех перечисленных выше преимуществах алгоритм Эль Гамаля имеет по сравнению с RSA и некоторые недостатки.
В частности, при том же уровне стойкости он оперирует с целыми числами на 25% короче, чем RSA, но длина подписи получается в 1,5 раза больше, что увеличивает время ее вычисления и ужесточает требования к надежности канала связ
36. Проблема дискретного логарифмирования, аутентификация
Система шифрования была представлена Мишелем Абдаллой, Михиром Беллэром и Филлипом Рогэвэем в рамках европейского проекта NESSIE (New European Schemes for Signatures, Integrity and Encryption). Она столь же эффективна, что и система Эль-Гамаля, но обладает дополнительными свойствами безопасности.
Данная криптосистема реализуема на основе любой циклической группы, для которой может быть сформулирована проблема Диффи-Хеллмана, например в { Zp* } или в группе точек на эллиптической кривой.Система строится из криптографических примитивов низкого уровня:групповой операции, симметричного шифра, функции хэширования и алгоритма вычисления кода аутентификации сообщения-имитовставки (MAC). Стойкость доказывается на основе предположения о сложности решения соответствующей проблемы Диффи-Хеллмана и предположения о стойкости входящих в схему симметричных примитивов.Опишем криптографические примитивы, входящие в схему.
Циклическая группа G = { g }. Далее будем использовать мультипликативную запись групповой операции. Алгоритмы, реализующие эту операцию, будут работать с представлениями элементов группы в виде битовых строк фиксированной длины gLen € N. Способ кодирования G →{0,1} gLen не фиксируется и может быть выбран из соображений эффективности.
Код аутентификации сообщения позволяет пользователям, обладающим общим секретным ключом, выработать битовую строку для аутентификации и проверки целостности данных Пусть Msg = {0,1}* – пространство сообщений, mKey = {0,1} mLen – пространство ключей для вычисления MAC для некоторого mLen € N, Tag = {0,1} tLen – включающее множество всех возможных значений MAC для некоторого tLen €N. В этих обозначениях код аутентификации сообщений представляет собой пару алгоритмов MAC =
{ MAC.gen, MAC.ver }. Алгоритм генерации MAC определяется как отображение MAC. gen (k, x): mKey × Msg → Tag и может быть вероятностным. Алгоритм верификации MAC является отображением со свойством MAC. ver (k, x, MAC. gen (k, x))=1.
В качестве MAC можно использовать, например, блочный шифр с достаточной длиной блока и ключа в режиме сцепления блоков шифрованноготекста.
Симметричный шифр позволяет пользователям, обладающим общим секретным ключом, обеспечить секретность. Пусть Msg, как и ранее, пространство сообщений, eKey = {0,1} eLen – пространство ключей для некоторого eLen € N, Ctext = {0,1}* – включающее множество всех возможных значений шифрованного текста и Coins = {0,1}∞ – множество строк бесконечной длины. В этих обозначениях шифр представляет собой пару алгоритмов SYM = { SYM.enc, SYM.dec }. Алгоритм зашифрования определяется как отображение
SYM. enc (k, x, r): eKey × Msg × Coins → Ctext, алгоритм расшифрования является отображением
SYM. dec (k, y): eKey × Ctext → Msg Uu{ BAD }, где значение BAD выдается, если шифртекст у не является результатом зашифрования никакого открытого текста.
Асимметричный шифр. Пусть Msg, Ctext, Coins определены как и ранее, PK G {0,1}*, SK G {0,1}* – множества открытых и секретных ключей.Асимметричный шифр определяется как тройка алгоритмов
ASYM = { ASYM.enc, ASYM.dec, ASYM.Key }. Алгоритм зашифрования является отображением
ASYM. enc (pk, x, r): PK × Msg × Coins → Ctext,а расшифрования: ASYM. enc (sk, y): SK × Ctext → Msg Uu{ BAD }.
Алгоритм выработки ключа в качестве аргумента берет строку r €Coins и выдает пару ключей
pk, sk € PK × SK. При этом должно выполняться следующее свойство:
@ (pk,sk): r’€ Coins: (pk,sk)= ASYM.key (r’), @ r €Coins
@x €Msg ASYM.dec(sk, ASYM.enc(pk, x, r))=.
Функция хэширования является отображением следующего вида: H:{0,1)2 gLen →{0,1) mLen + eLen.
Теперь можно описать криптографические примитивы, непосредственно составляющие рассматриваемую криптографическую систему. Графически процесс зашифрования представлен на рис. 3.2.
37. Система открытого шифрования «Рюкзак»
Задача о ранце в криптографии (англ. Knapsack problem) — это задача, на основе которой американские криптографы Ральф Меркл (англ.) и Мартин Хеллман разработали первый алгоритм шифрования с открытым ключом. Он носит название криптосистема Меркла-Хеллмана. Для шифрования сообщений использовалось решение задачи о рюкзаке, как известно являющейся NP-сложной. Потому, как считалось, она могла обеспечивать криптостойкость системы. На данный момент создано множество рюкзачных криптосистем. Однако практически все существующие на сегодняшний день взломаны или признаны потенциально небезопасными.
Задача о рюкзаке звучит так: задан набор 
из 
различных положительный целых чисел. Пусть есть число 
так же целое и положительное. Задачей является нахождение такого набора 
, чтобы в сумме они давали ровно . Ясно, что решение этой задачи существует не всегда.
Согласно определению систем с открытым ключом, для успешного шифрования/расшифровки нужно иметь два ключа. Законный получатель сообщения знает секретный ключ A, а отправитель владеет лишь открытым ключом B. Как же помешать злоумышленнику дешифровать сообщение в случае если ему стал известен открытый ключ? Ответ прост, открытый ключ должен получаться из секретного ключа при помощи какого-либо преобразования f, обладающего следующими двумя свойствами[16]:
· Легко вычислить 
, зная 
· Определение 
, зная 
, вероятно, трудновыполнимая задача.
В качестве трудновыполнимых задач обычно рассматриваются NP-полные задачи, поэтому задача о ранце подходит для построения систем на открытом ключе.
Сообщение шифруется как решение набора задач о ранце[2].
Def. Рюкзачным вектором назовём упорядоченный набор из n предметов[17].
Для шифрования открытого текста в двоичном представлении его разбивают на блоки длины (например, 
соответствует 5-ти предметам в рюкзаке). Считается, что единица указывает на наличие предмета в рюкзаке, а ноль на его отсутствие. Шифровать можно двумя способами:
1) Шифр сообщения получается возведением элементов рюкзачного вектора в степень соответствующих им бит шифруемого сообщения и дальнейшим перемножением результатов, то есть если 
, а сообщение 
, то шифром будет число 
. Такой способ называют мультипликативным [5].
2) Шифр сообщения получается путем умножения элементов рюкзачного вектора на соответствующий им бит шифруемого сообщения и дальнейшим сложением результатов, то есть если , а сообщение , то шифром будет число 
. Такой способ называют аддитивным [5]. Безопасность рюкзачных систем
Для небольших рюкзачных векторов, задачу о ранце легко решить даже вручную. Реальный рюкзак должен содержать большое число элементов. Вскрытие такого рюкзака при помощи грубой силы, т.е перебором, будет трудной (невозможной) задачей. Однако рюкзачные системы не являются безопасными для криптоанализа. Шамир и Циппел (англ. Zippel) обнаружили, что зная числа 
(«секретную лазейку») можно восстановили сверхвозрастающий вектор по нормальному открытому вектору [3]. Важно то, что числа 
(«секретная пара») не обязательно должны быть теми же, что использовались при создании системы легальным пользователем. Достаточно найти любую пару 
, такую что 
даст нам сверхрастущий вектор
38. Система открытого шифрования RSA, атаки на RSA.
В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA, названный так по начальным буквам фамилий ее изобретателей (Rivest, Shamir и Adleman) и представляющую собой криптосистему, стойкость которой основана на сложности решения задачи разложения числа на простые сомножители..
Под простым числом будем понимать такое число, которое делится только на единицу и на само себя. Взаимно простыми числами будем называть такие числа, которые не имеют ни одного общего делителя, кроме единицы.
Под результатом операции i mod j будем считать остаток от целочисленного деления i на j. Чтобы использовать алгоритм RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги:
• выберем два очень больших простых числа p и q;
• определим n как результат умножения p на q (n = p Ч q);
• выберем большое случайное число, которое назовем d (оно должно быть взаимно простым с m результатом умножения (р – 1) × (q – 1));
• определим такое число e, для которого является истинным следующее соотношение: (e Ч d) mod (m) = 1 или e = (1 mod (m))/ d.
Открытым ключом будут числа e и n, а секретным ключом – числа d и n.
Теперь, чтобы зашифровать данные по известному ключу { e, n }, необходимо сделать следующее:
• разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа М (i) = 0, 1, …, n – 1;
• зашифровать текст, рассматриваемый как последовательность чисел М (i) по формуле С (i) = (М (i) e) mod n.
Чтобы расшифровать данные, используя секретный ключ { d, n }, необходимо выполнить следующие вычисления: М (i) = (С (i) d) mod n. В результате получится множество чисел М (i), которые представляют собой исходный текст.
Криптостойкость алгоритма RSA основывается на проблеме факторизации больших простых чисел. Действительно, если злоумышленнику удастся разложить число n на простые множители p и q, то для него не составит труда вычислить j( n), а затем и определить секретный ключ пользователя. Однако нахождение секретного ключа RSA не эквивалентно проблеме факторизации. Это означает, что T(RSA)<=T(факторизации), где T(RSA) – трудоемкость определения секретного ключа RSA, а T(факторизации) – трудоемкость факторизации числа n. То есть, могут быть найдены эффективные алгоритмы определения секретного ключа алгоритма RSA, причем проблема факторизации при этом не будет разрешена.
Если сообщение невелико, то злоумышленник может попытаться подобрать открытый текст путем перебора всех возможных вариантов и шифрования их на открытом ключе абонента e до тех пор, пока не будет получен перехваченный шифртекст c.
Схема шифрования RSA несостоятельна при использовании абонентами общих модулей n. Допустим, что имеются 2 абонета A и В с открытыми ключами (e 1, n) и (e 2, n). Центр (например, общий сервер) желает послать обоим абонетам одно и то же сообщение m. Он получает me 1= c 1(mod n) и me 2= c 2(mod n) и посылает c 1 и c 2 абонентам А и В соответственно. Положим, что противник перехватывает эти сообщения. Затем, если (e 1, e 2)=1, то с помощью расширенного алгоритма Евклида можно найти такие k 1 и k 2, для которых e 1 k 1+ e 2 k 2=1. И, соответственно, me 1 k 1 me 2 k 2= m. Найдя такие k 1 и k 2 (это можно сделать, ведь открытые ключи противнику известны), противник вычислит собщение: (c 1) k 1(c 2) k 2 = m.
39. Система электронной подписи Эль Гамаля (EGSA - ElGamal Signature Algorithm)
Очень часто бывает желательно, чтобы электронная цифровая подпись была разной, даже если дважды подписывается одно и то же сообщение. Для этого в процесс выработки ЭЦП необходимо внести элемент "случайности". Конкретный способ был предложен Эль-Гамалем аналогично тому, как это делается в системе шифрования, носящей его имя.
Выбирается большое простое число р и целое число g, являющееся примитивным элементом в Zp. Эти числа публикуются. Затем выбирается секретное число х и вычисляется открытый ключ для проверки подписи y=gx(mod p)
Далее для подписи сообщения М вычисляется его хэш-функция т = h (M). Выбирается случайное целое k:1<k<(p-1), взаимно простое с р– 1, и вычисляется r=gk(mod p). После этого с помощью расширенного алгоритма Евклида решается относительно s уравнение m=xr+ks(mod(p-1)). Подпись образует пара чисел (r,s). После выработки подписи значение k уничтожается.
Получатель подписанного сообщения вычисляет хэш-функцию сообщения m=h(M) и проверяет выполнение равенства yrrs=gxrgks=gxr+ks=gm(mod p). Корректность этого уравнения очевидна.
40. Система открытого шифрования Эль Гамаля
Одновременно с описанием системы ЭЦП Эль Гамаль предложил к использованию систему открытого шифрования, так же основанную на задаче дискретного логарифмирования.
Пусть, как и выше задано простое число P, основание A, секретный ключ расшифрования x и открытый ключ шифрования y=AX.
Для шифрования сообщения M, проводится следующая процедура:
1. Выбирается случайное число k, (k,P-1)=1
2. Вычисляется G=AK mod P
3. Вычисляется H=yK M mod P
4. Пара (G, H) является шифрованным сообщением M
При расшифровании вычисляется:
H/GX mod P = yK M / AXK mod P = M mod P
Преимуществами системы ЭЦП и ОШ Эль Гамаля, является простота генерации открытых и секретных ключей, а так же то, что параметры P и A могут быть общими для всех участников сети связи.
Открытое шифрование по Эль Гамалю не получило широкого распространения, в то время, как алгоритм ЭЦП стал весьма известным и начал успешно конкурировать с алгоритмом RSA. Несколько позднее, усилиями криптографов была описана общая схема ЭЦП на основе дискретного логарифмирования.
41. Общая схема электронной подписи на основе дискретной экспоненты.
Механизм электронной цифровой подписи (ЭЦП) возник как побочный эффект криптографии с открытым ключом. Поэтому характерное для систем с открытым ключом разделение ключа на 2 части - секретную и несекретную - позволяет реализовать возможность проверки подлинности без возможности подписать другой документ.
цифровая подпись - это конечная цифровая последовательность, зависящая от самого сообщения или документа и от секретного ключа, известного только подписывающему субъекту, предназначенная для установления авторства.
Наиболее пpостым и pаспpостpаненным инстpументом электpонной подписи является алгоpитм RSA. Кpоме этого, существуют еще десятки дpугих схем цифpовой подписи.
Пpедположим, что
d, p, q – секpетные, а е, n = pq – откpытые.
Замечания.
1. Разложение по n дает: (n) = (p-1)(q-1); зная (n) и e, можно найти d.
2. Из e и d можно найти кpатность (n); кpатность (n) позволяет опpеделить делители n.
Пусть DATA – пеpедаваемое Александpом Боpису сообщение. Александp подписывает DATA для Боpиса пpи пеpедаче: Eeb,nb{Eda,na{DATA}}.
Пpи этом он использует:
· закpытый ключ Eda,na Александpа,
· откpытый ключ Eeb,nb Боpиса.
Боpис может читать это подписанное сообщение сначала пpи помощи закpытого ключа Eeb,nb Боpиса с целью получения Eda,na{DATA}= Edb,nb{ Eeb,nb{ Eda,na {DATA}}}
и затем откpытого ключа EeA,nA Александpа для получения
DATA=Eea,na{ Eda,na {DATA}}.
Таким обpазом, у Боpиса появляется сообщение DATA, посланное ему Александpом. Очевидно, что данная схема позволяет защититься от нескольких видов наpушений.Александp не может отказаться от своего сообщения, если он пpизнает, что секpетный ключ известен только ему. Наpушитель без знания секpетного ключа не может ни сфоpмиpовать, ни сделать осмысленное изменение сообщения, пеpедаваемого по линии связи. Данная схема позволяет пpи pешении многих конфликтных ситуаций обходиться без посpедников.
Иногда нет необходимости зашифpовывать пеpедаваемое сообщение, но нужно его скpепить электpонной подписью. В этом случае текст шифpуется закpытым ключом отпpавителя, и полученная цепочка символов пpикpепляется к документу. Получатель с помощью откpытого ключа отпpавителя pасшифpовывает подпись и свеpяет ее с текстом.
42. Использование произвольной циклической группы для организации систем ЭЦП и ОРК.
Алгоритмы Диффи-Хеллмана и алгоритма RSA дословно переносятся на произвольные конечные абелевы группы Gm порядка m. Это верно и для остальных несимметричных криптографических алгоритмов. Существует два варианта использования таких групп.
1. Если порядок группы m вычислить сложно (т.е. сложность такого вычисления по крайней мере субэкспоненциальна), то мы получаем RSA-подобные алгоритмы, в частности, собственно алгоритм RSA работает в группе Gm = 
, причем 
. Как сказано выше, вычисление значения функции Эйлера эквивалентно факторизации числа n.
2. Возьмем в Gm циклическую подгруппу 
, порожденную некоторым элементом 
.Если порядок этой циклической подгруппы легко вычисляется (этот порядок является делителем числа m), но решение уравнения 
, относительно x, 1 < x < n, имеет экспоненциальную сложность, то в этой циклической подгруппе можно строить криптографические системы экспоненциального типа. В этом случае будем считать, что группа Gm и есть циклическая группа порядка m.
Вопрос заключается в выборе группы Gm. В произвольной циклической группе Gm задачу дискретного логарифмирования можно решить за 
операций, например, с помощью метода Шэнкса. Это метод заключается в составлении двух список размером t = каждый. Первый список состоит из пар 
и отсортирован по второй компоненте. Второй список состоит из пар вида 
и тоже отсортирован по второй компоненте. Такая упорядоченность списков позволяет легко найти две пары с равными вторыми компонентами, т.е. 
и 
с 
. Тогда 
по модулю m. Поэтому группа должна допускать только алгоритмы решения задачи дискретного логарифмирования, порядок сложности которых не меньше , и не допускать алгоритмов субэкспоненциальной сложности. Аналогичные требования предъявляются к RSA-подобным криптографическим алгоритмам. Второе принципиально важное условие - групповая операция должна быть простой в реализации. Третье условие -построение групп должно быть не очень сложным и их должно быть достаточно много для того, чтобы построение самих групп и вычисление их параметров не превратилось в сложную задачу. Групп, пригодных для создания RSA-подобных систем, до сих пор не найдено.
43. Однонаправленные хеш-функции Понятие хеш-функции
Хэш-функция - функция, аргументом которой является сообщение, выходным значением - строка символов фиксированного размера (дайджест сообщения). Изменения в тексте сообщения приводят к изменению значения хеш-функции. Поэтому все изменения, в тексте сообщения приведут к изменению дайджеста.
Поиск по сайту: