Криптосистем основанные на эллиптических кривых. Содержание реферат
 Скачать 1.29 Mb.
|
|
1.6. Эллиптические кривые, рекомендованные NIST Национальный институт стандартов и технологий США (NIST) рекомендует 15 эллиптических кривых для использования их в алгоритмах шифрования. 1. Поля 𝐹𝑝 , где характеристикой поля p имеет длину 224, 256, 512 битов 2. Поля 𝐹2𝑚 , где степень m могут быть числа 233, 283, 409 или 571 Для каждого поля рекомендуется выбирать одну эллиптическую кривую. Эти конечные поля были получены путем тестирования и выбор этих полей для эллиптических кривых способствуют повышению уровня безопасности и вычислительной эффективности в реализации алгоритмов. Реализованные мной алгоритмы шифрования были протестированы на нескольких кривых представленных в стандартах NIST. 1.7. Выбор размер ключа На данный момент самым быстрым и эффективным алгоритмом, который решает проблему дискретного логарифмирования на эллиптических кривых, является алгоритм, придуманный Дэниэльем Шенксом под названием «алгоритм больших и малых шагов». Сложность данного алгоритма вычисляется по формуле 𝑂(√𝑛). Из этой формулы следует, что размер выбранного поля эллиптической кривой должен как минимум в 2 раза превосходить размер ключа. Так, например, для устойчивого алгоритма шифрования с ключом длиной 256 бит необходимо выбрать эллиптическую кривую с характеристикой поля 𝑝≈2512. Определенные выше операции над точками кривых могут быть распространены на случай произвольного поля. Необходимые формулы могут быть получены, если воспользоваться алгебраическими выражениями для геометрических понятий - "прямая", "вертикальная прямая", "касательная". 1.8. Введение в криптоанализ Криптоанализ — наука о методах нахождения исходного содержания зашифрованной (скрытой) информации, не имея возможности получения секретной информации (ключу), необходимой для этого. В большинстве случаев под этим подразумевается взлом шифра (кода). Впервые данное понятие было введено в 1920 году американским криптографом Уильямом Фридманом Под понятием «криптоанализ» понимается возможность найти уязвимые места в криптографическом алгоритме или протоколе. Не смотря на то что главной целью криптоанализа осталась неизменной с течением времени, способы криптоанализа во многом изменения. Если раньше в профессии криптоаналитика были, по большей части, лингвисты то в настоящее время основными криптоаналитиками считаются математики. Результаты криптоанализа конкретного шифра называют криптографической атакой на этот шифр. Успешную криптографическую атаку, дискредитирующую атакуемый шифр, называют взломом или вскрытием. Классический криптоанализ. Хотя понятие криптоанализ было введено сравнительно недавно, некоторые методы взлома были изобретены десятки веков назад. Первым известным письменным упоминанием о криптоанализе является «Манускрипт о дешифровке криптографических сообщений», написанный арабским учёным Ал-Кинди ещё в 9 веке. В этом научном труде содержится описание метода частотного анализа. Частотный анализ - основной инструмент для взлома большинства классических шифров перестановки или замены. Данный метод основывается на предположении о существовании нетривиального статистического распределения символов, а также их последовательностей одновременно и в открытом тексте, и в шифротексте. Причём данное распределение будет сохраняться с точностью до замены символов как в процессе шифрования, так и в процессе дешифрования. Стоит отметить, что при условии достаточно большой длины шифрованного сообщения моноалфавитные шифры легко поддаются частотному анализу: если частота появления буквы в языке и частота появления некоторого присутствующего в шифротексте символа приблизительно равны, то в этом случае с большой долей вероятности можно предположить, что данный символ и будет этой самой буквой. Самым простым примером частотного анализа может служить банальный подсчёт количества каждого из встречающихся символов, затем следуют процедуры деления полученного числа символов на количество всех символов в тексте и умножение результата на сто, чтобы представить окончательный ответ в процентах. Далее полученные процентные значения сравниваются с таблицей вероятностного распределения букв для предполагаемого языка оригинала. Современный криптоанализ. По мере развития новых методов шифрования математика становилась всё более и более значимой. Так, например, при частотном анализе криптоаналитик должен обладать знаниями и в лингвистике, и в статистике. В то время как теоретические работы по криптоанализу Энигмы выполнялись преимущественно математиками, например, Аланом Матисоном Тьюрингом. Тем не менее благодаря всё той же математике криптография достигла такого развития, что количество необходимых для взлома элементарных математических операций стало достигать астрономических значений. Современная криптография стала гораздо более устойчивой к криптоанализу, чем некогда используемые, устаревшие методики, для взлома которых было достаточно ручки и листа бумаги. Может показаться, что чистый теоретический криптоанализ не способен более эффективно взламывать современные шифры. Криптографическая атака – это результат криптоанализа выбранного шифра. Если криптографическая атака была успешна, то такую атаку называют взломом или вскрытием. Под стойкостью криптографического алгоритма обычно понимают количество операций, которые необходимо выполнить, чтобы получить секретный ключ, используя открытый ключ. От числа и характера «элементарных» операций напрямую, зависит время, необходимое для их выполнения. Атака на основе шифротекста. Допустим, криптоаналитик обладает некоторым числом шифротекстов, полученных в результате использования одного и того же алгоритма шифрования. В этом случае криптоаналитик может совершить только атаку на основе шифротекста. Целью криптографической атаки в этом случае является нахождение как можно большего числа открытых текстов, соответствующих имеющимся шифротекстам, или, что ещё лучше, нахождение используемого при шифровании ключа. Входные данные для подобного типа атак криптоаналитик может получить в результате простого перехвата зашифрованных сообщений. Если передача осуществляется по открытому каналу, то реализация задачи по сбору данных сравнительно легка и тривиальна. Атаки на основе шифротекста являются самыми слабыми и неудобными. Атака на основе адаптивно подобранного шифротекста. Атака такого типа является более удобным частным случаем атаки на основе подобранного открытого текста. Удобство атаки на основе адаптивно подобранного шифротекста состоит в том, что помимо возможности выбирать шифруемый текст, криптоаналитик может принять решение о шифровании того или иного открытого текста на основе уже полученных результатов операций шифрования. Другими словами, при осуществлении атаки на основе подобранного открытого текста криптоаналитик выбирает всего один большой блок открытого текста для последующего шифрования, а потом на основе этих данных начинает взламывать систему. В случае организации адаптивной атаки криптоаналитик может получать результаты шифрования любых блоков открытого текста, чтобы собрать интересующие его данные, которые будут учтены при выборе следующих отправляемых на шифрование блоков открытого текста и так далее. Наличие обратной связи даёт атаке на основе адаптивно подобранного шифротекста преимущество перед всеми вышеперечисленными типами атак. Атака на основе подобранного ключа. Вопреки своему названию атака на основе подобранного ключа не подразумевает под собой того, что криптоаналитик занимается простым перебором ключей в надежде найти нужный. Атака такого типа строится на том, что криптоаналитик может наблюдать за работой алгоритма шифрования, в котором используются несколько ключей. Криптоаналитик изначально ничего не знает о точном значении ключей, зато ему известно некоторое математическое отношение, связывающее между собой ключи. Примером тому может служить ситуация, когда криптоаналитик выяснил, что последние 80 битов у всех ключей одинаковы, хотя сами значения битов могут быть неизвестными. Атака на основе подобранного открытого текста. Для осуществления такого типа атаки криптоаналитику необходимо иметь не только какое-то количество открытых текстов и полученных на их основе шифротекстов. Помимо прочего в данном случае криптоаналитик должен обладать возможностью подобрать несколько открытых текстов и получить результат их шифрования. Задачи криптоаналитика повторяют задачи для атаки на основе открытого текста, то есть получить ключ шифрования, либо создать дешифрующий алгоритм для данного ключа. Получить входные данные для такого вида атаки можно, например, следующим образом: При осуществлении атаки подобного типа криптоаналитик имеет возможность подбирать блоки открытого текста, что при определённых условиях может позволить получить больше информации о ключе шифрования. Атака на основе открытых текстов и соответствующих шифротекстов. Пусть в распоряжении криптоаналитика есть не только шифротексты, но и соответствующие им открытые тексты. Тогда существуют два варианта постановки задачи: Получение открытых текстов играет решающую роль в осуществлении этой атаки. Открытые тексты извлекают из самых различных источников. Так, например, можно догадаться о содержимом файла по его расширению. 1.9. Виды атак 1.9.1. Атака по времени Атака по времени — это атака, используемая злоумышленником в сторонних каналах связи, построена на анализе времени, которое необходимо на исполнение криптографического алгоритма. Каждая вычислительная операция требует определенное время на исполнение на персональном компьютере. Это время может быть различным в зависимости от представленных данных. Если злоумышленник располагает точными измерениями времени для выбранных операций, то он может попытаться восстановить входные данные. Криптографические алгоритмы обычно тратят разное количество времени на обработку входных данных. Это может быть обусловлено не правильной оптимизацией выбранного алгоритма, чтением данных из буфера обмена в оперативной памяти, командами процессора, которые используют разное время для вычисления различных операций. Характеристики производительности на прямую связаны как от размера ключа шифрования, так и от входных данных. 1.9.2. Предотвращение временной атаки Самый очевидный способ предотвратить временных атак – смоделировать алгоритм шифрования таким образом, что все производимые вычисления будут исполняться за равное время. Однако создать такой идеальный код достаточно сложно, так как некоторые вычислительные процессы, такие как: чтение из КЭШ, отклик системы, выполнение потоков могут способствовать появлению временных отклонений. Другой способ заключается в том, чтобы сделать измерения времени настолько неточными, чтобы атака стала неэффективной. Например, в программном коде можно прописать временные задержки, которые будут иметь случайную длину. Такой подход является наиболее эффективным при борьбе с таким видом атак. 1.9.3. Атака «Человек посередине» Этот метод основан на том, что злоумышленник подключается к каналу передачи данных, тем самым нарушая криптографический протокол. [19] Он может активно вмешиваться в алгоритм передачи и выдавать себя за одного из получателей. [20] Так он может удалять, изменять и выдавать ложную информацию за действительность. Допустим, что пользователь A пытается передать пользователю B некую зашифрованную информацию. Злоумышленник C знает о структуре и свойствах выбранного метода шифрования и передачи данных. Для совершения атаки на канал связи злоумышленник С представляется пользователю А как пользователь В и наоборот. Пользователь А, не зная об этом, пытается послать информацию В, а на самом деле посылает её С. Объект С, получив информацию, и совершив с ней некоторые операции пересылает данные получателю В. Пользователь В, в свою очередь, считает, что информация была получена им от пользователя А. 1.9.3. Полный перебор Полный перебор — метод решения задачи путем перебора всех возможных вариантов. Сложностью данного метода является количество всевозможных решений данной задачи. Если количество решений слишком большое, то этот метод может не дать результатов в определённого времени. Оценка криптостойкости шифров как раз и основывается на сложности метода полного перебора решений. В итоге шифр будет криптостойким к атакам если не будет выявлен алгоритм нахождения ключа за время меньшее чем время, потраченное на полный перебор. Криптографические атаки, которые основаны на алгоритме полного перебора, являются самыми универсальными, но очень долгими. 1.9.4. Предотвращение атаки «полного перебора» Самым лучшим способом избежать атак полного перебора является правильный выбор параметров эллиптической кривой. Если использовать в качестве параметров эллиптической кривой числа, длины которых превышают 512 бит, а в качестве характеристики поля выбрать большое простое число то это может способствовать улучшению криптостойкости алгоритма. Конечно мы потеряем немного во времени, так как все вычисления будут выполняться чуть дольше, но данные вычисления будут не столь критичны, как опасность взлома шифра. 1.9.5. Квантовый взлом Самой серьёзной угрозой для современной криптографии являются квантовые компьютеры и их большие возможности. Если модифицировать алгоритм Шора, чтобы он мог использоваться на квантовых компьютерах, то можно без особого труда решить проблему дискретного логарифмирования. Следовательно, криптосистема, которая основывается на эллиптических кривых будет под угрозой взлома. Но мне кажется, что бояться этого не следует. Так как квантовые компьютеры сейчас находятся лишь в стадии разработки. Скорее всего, в ближайшие десятилетия квантовые компьютеры, которые могут взломать уже существующие шифры, не появятся. Но даже если и появятся, то на данный момент уже активно развивается такой раздел науки как квантовая криптография. 2 ГЛАВА. ШИФРОВАНИЯ С ПОМОЩЬЮ ЭЛЛИПТИЧЕСКИХ КРИВЫХ 2.1. Сферы применения криптосистем с открытым ключом Криптографическая система с открытым ключом (разновидность асимметричного шифрования, асимметричного шифра) — система шифрования и/или электронной подписи (ЭП), при которой открытый ключ передаётся по открытому (то есть незащищённому, доступному для наблюдения) каналу и используется для проверки ЭП и для шифрования сообщения. Для генерации ЭП и для расшифровки сообщения используется закрытый ключ. Криптографические системы с открытым ключом в настоящее время широко применяются в различных сетевых протоколах, в частности, в протоколах TLS и его предшественнике SSL (лежащих в основе HTTPS), в SSH. Также используется в PGP, S/MIME. Идея криптографии с открытым ключом очень тесно связана с идеей односторонних функций, то есть таких функций f(x), что по известному x довольно просто найти значение f(x), тогда как определение x из f(x) невозможно за разумный срок. Но сама односторонняя функция бесполезна в применении: ею можно зашифровать сообщение, но расшифровать нельзя. Поэтому криптография с открытым ключом использует односторонние функции с лазейкой. Лазейка — это некий секрет, который помогает расшифровать. То есть существует такой y, что зная f(x) и y, можно вычислить x. Получатель информации формирует открытый ключ и «лазейку» (другими словами, открытую и закрытую часть ключа), затем передает открытый ключ отправителю, а «лазейку» оставляет у себя. Отправитель шифрует информацию на основе открытого ключа: такую зашифрованную информацию просто расшифровать, лишь имея одновременно и открытый ключ, и «лазейку». В терминах функции, получатель формирует f() с лазейкой y, затем передает информацию о параметрах функции f() отправителю (при этом, даже зная параметры функции f(), невозможно обнаружить «лазейку» за разумный срок). После этого отправитель формирует шифрованное сообщение f(x), а получатель извлекает x из f(x), зная y. Ниже показана схема передачи информации лицом А лицу В. Они могут быть как физическими лицами, так и организациями и так далее (рисунок 2.1). Рисунок 2.1  Начало асимметричным шифрам было положено в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Находясь под влиянием работы Ральфа Меркла о распространении открытого ключа, они предложили метод получения секретных ключей, используя открытый канал. Этот метод экспоненциального обмена ключей, который стал известен как обмен ключами Диффи — Хеллмана, был первым опубликованным практичным методом для установления разделения секретного ключа между заверенными пользователями канала. В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркле», признавая вклад Меркле в изобретение криптографии с открытым ключом. Эта же схема была разработана Малькольмом Вильямсоном (англ. Malcolm J. Williamson) в 1970-х, но держалась в секрете до 1997 года. Метод Меркле по распространению открытого ключа был изобретён в 1974 и опубликован в 1978 году, его также называют загадкой Меркле. В 1977 году учёными Рональдом Ривестом, Ади Шамиром и Леонардом Адлеманом из Массачусетского технологического института был разработан алгоритм шифрования, основанный на проблеме о разложении на множители. Система была названа по первым буквам их фамилий (RSA — Rivest, Shamir, Adleman). Эта же система была изобретена в 1973 году Клиффордом Коксом (англ. Clifford Cocks), работавшим в центре правительственной связи (GCHQ), но эта работа хранилась лишь во внутренних документах центра, поэтому о её существовании не было известно до 1977 года. RSA стал первым алгоритмом, пригодным и для шифрования, и для цифровой подписи. Вообще, в основу известных асимметричных криптосистем кладётся одна из сложных математических проблем, которая позволяет строить односторонние функции и функции-лазейки. Например, криптосистемы Меркля — Хеллмана и Хора — Ривеста опираются на так называемую задачу об укладке рюкзака. Казалось бы, что криптосистема с открытым ключом — идеальная система, не требующая безопасного канала для передачи ключа шифрования. Это подразумевало бы, что два легальных пользователя могли бы общаться по открытому каналу, не встречаясь, чтобы обменяться ключами. К сожалению, это не так. Рисунок иллюстрирует, как перехватчик, может захватить систему без взламывания системы шифрования (рисунок 2.2). Рисунок 2.2  Ещё одна форма атаки — вычисление закрытого ключа, зная открытый (рисунок ниже). Криптоаналитик знает алгоритм шифрования Ee, анализируя его, пытается найти Dd. Этот процесс упрощается, если криптоаналитик перехватил несколько криптотекстов с, посланных лицом A лицу B (рисунок 2.3). Рисунок 2.3  Большинство криптосистем с открытым ключом основаны на проблеме факторизации больших чисел. К примеру, RSA использует в качестве открытого ключа n произведение двух больших чисел. Сложность взлома такого алгоритма состоит в трудности разложения числа n на множители. Но эту задачу решить реально. И с каждым годом процесс разложения становится все быстрее. Ниже приведены данные разложения на множители с помощью алгоритма «Квадратичное решето». Также задачу разложения потенциально можно решить с помощью алгоритма Шора при использовании достаточно мощного квантового компьютера. Для многих методов несимметричного шифрования криптостойкость, полученная в результате криптоанализа, существенно отличается от величин, заявляемых разработчиками алгоритмов на основании теоретических оценок. Поэтому во многих странах вопрос применения алгоритмов шифрования данных находится в поле законодательного регулирования. Алгоритмы криптосистемы с открытым ключом можно использовать 1. Как самостоятельные средства для сохранности передаваемой информации, а также для защиты хранимой информации на носителях. 2. Как средства распределения ключей. Например, с помощью алгоритмов криптосистем с открытым ключом можно распределить ключи, малые по объёму. А передачу главной информации можно осуществить с помощью других алгоритмов. |