Математичні аспекти безпеки криптографічних систем

Территория рекламы

Вступ

Аналіз та синтез надійних безпечних криптографічних систем, управління їх безпекою потребує чіткого уявлення усіх складових безпеки засобів КЗІ, уміння формувати та аналізувати моделі порушника та моделі безпеки криптосистем.

Серед актуальних проблем прикладної криптології слід особо виділити питання теоретичної та практичної стійкості, які є базисними для вибору криптосистем, які плануються до застосування. Саме вказані проблеми розглядаються у наступних розділах та є вирішальними для вивчення подальших питань побудови та аналізу криптографічних систем.

1 Практичні вимоги до симетричних шифрів

В сучасних умовах безпека криптографічного захисту інформації забезпечується шляхом:

застосування нормативно-правових методів регулювання діяльності в цій сфері;

впровадження системи відповідних організаційних заходів, зокрема, в частині охорони засобів криптографічних захисту інформації та ключів;

використання безпечних (стійких до атак) математичних методів перетворення інформації криптоалгоритмів та криптопротоколів, механізмів генерації та тестування ключової інформації;

реалізації обраних математичних методів у вигляді надійних програмних та апаратних засобів (забезпечення так званих інженерно-криптографічних властивостей);

а також завдяки захисту криптографічних засобів від несанкціонованого доступу до критичної та блокування/ нейтралізації каналів її витоку за рахунок фізичних полів, акустичних перетворень тощо.

В цьому розділі ми вивчимо питання вибору математичних методів, які повинні забезпечити безпеку криптографічного захисту інформації.

Історія криптографії знає багато досліджень у цьому напряму. Зокрема, шість базових принципів побудови шифрів (фактично симетричних криптографічних систем) сформулював голландський математик Огюст Керкхоффс в своїй книзі «Воєнна криптографія» (Auguste Kerckhoffs, «La Cryptographie Militaire», 1883). На його переконання:

Шифр повинен бути, якщо не математично, то практично (фізично) нерозкриваємим;

Збереження в таємниці принципів побудови шифру не вимагається. Отримання шифрувальної системи супротивником не повинно створювати проблеми з безпекою;

Збереження та передача ключу повинні здійснюватися без застосування паперових нотаток. Кореспонденти повинні мати можливість змінювати ключі на власний розсуд;

Шифр має бути придатним для передачі повідомлень за допомогою телеграфу;

Шифрувальна система повинна бути мобільною, робота з нею не вимагатиме залучення декількох осіб одночасно;

Використання шифрувальна система повинно бути простим та зручним, не може вимагати виконання великої кількості правил.

З перелічених вимог можливо зробити наступний висновок (правило Керкхоффса): стійкість шифру по не може залежати від знання або незнання зловмисником особливостей його побудови повинна визначатися секретністю ключа, інакше знання алгоритму шифрування не повинно впливати на надійність захисту.

Під час оцінки безпеки шифрувальних систем досліджується можливість атакуючої сторони отримати повну або часткову інформацію про вихідне повідомлення та/або ключ шифрування. В цих умовах, згідно з правилом Керкхоффса вважається, що у рівнянні шифрування у C=E(M,K) порушнику завжди відомі функція математичного перетворення E та шифроване повідомлення C. Стосовно відкритого тексту M він може мати певні здогадки, лише ключ шифрування K йому невідомий.

Згодом, в одній з своїх фундаментальних робіт «Теорія зв’язку в секретних системах» (1945/48 рік) американський математик Клод Шеннон обґрунтував ряд важливих критеріїв якості шифрувальних систем (принципів їх побудови), а також запропонував модель системи секретного зв’язку (рис. 1).

Рис. 1 Модель секретного зв'язку по Шеннону.

На аналізі вказаної моделі ми зупинимося пізніше. Зараз, розглянемо серед найбільш важливих критеріїв Шеннона наступні:

Обсяг секретності.

Деякі шифрувальні системи можуть залишати в шифрованому повідомленні відбиток статистичних властивостей відкритих повідомлень, що дозволяє в деяких випадках однозначно розв’язати задачу дешифрування, інколи, залежно від обсягу перехопленої криптограми, мати декілька найбільш імовірних варіантів відкритого повідомлення або ключу. Тобто, цей фактор полегшує задачу атакуючої сторони. В ідеальному випадку – в разі досконалого шифру по Шеннону після перехоплення криптограми зловмисник не отримує аніякої додаткової інформації стосовно вихідного повідомлення.

Обсяг ключу.

Шеннон звернув увагу, що в деяких випадках необхідно запам’ятати ключ для того, щоб його передати іншому кореспонденту. В сучасних умовах надшвидкої обробки та передавання інформації великий обсяг ключів може утворювати труднощі з їх збереженням на носіях.

Складність операцій за шифрування і розшифрування.

В випадку, коли шифрування здійснюється вручну або за допомогою не надто швидкодіючим пристроєм, загальний час виконання складної процедури може бути неприпустимо довгим.

Розповсюдження кількості помилок.

Зважаючи на те, що звичайно канали зв'язку схильні до впливу завад, які можуть призводити до викривлень повідомлень, бажано щоб випадкова помилка в криптограмі без застосування корегуючи кодів призводила до мінімальної кількості помилок в повідомленні після розшифрування. В ідеалі одна помилка в криптограмі мала наслідком не більше однієї помилки в розшифрованому повідомленні.

Збільшення обсягу повідомлення.

З міркувань економного використання пропускної спроможності каналу зв’язку шифрування не повинно суттєво збільшувати довжину початкового повідомлення.

Підсумовуючі викладене, зазначимо, що важливішою властивістю будь-якої шифрувальної системи є її криптостійкість, що характеризує її здатність протистояти криптоаналітичним атакам та виключає в деяких припустимих межах можливість розкриття зашифрованих повідомлень без знання ключу або підробки повідомлень.

Существует несколько подходов к оценке криптостойкости, отметим только некоторые:

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

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

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

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

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

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

К современным криптографическим системам защиты информации предъявляются и другие требования:

зашифрованное сообщение должно поддаваться прочтению только при наличии ключа;

любой ключ из допустимого множества должен обеспечивать надежную защиту информации;

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

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

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

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

структурные элементы алгоритма шифрования должны быть неизменными.

2. Модель нарушителя и модель угроз криптосистеме

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

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

Для криптосистем различают четыре уровня возможностей атакующей стороны:

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

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

второй: нарушитель корпоративного типа дополнительно к возможностям предыдущего уровня располагает финансовой поддержкой мощной бизнес-структуры;

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

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

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

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

На практике криптосистемы используются в составе вычислительных сетей или систем специальной связи (рис. 2).

Рис. 2. Криптосистема и угрозы ее безопасности

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

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

-перехват шифрованных сообщений и проведение криптоанализа с целью восстановления их содержания или вскрытия ключей;

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

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

подслушивание, перехват и манипуляции (подделка) с данными в канале связи;

нарушение доступности и целостности информации в результате злоумышленного электромагнитного воздействия (электромагнитный терроризм), нарушений электропитания и других технических факторов.

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

3. Виды атак на симметричные и асимметричные шифрсистемы

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

Для уяснения проблемы рассмотрим атаки на симметричные криптосистемы (с использованием секретных ключей):

Атака на основе известных шифртекстов (ciphertext-only attack). Предполагается, что в этом случае злоумышленнику известен алгоритм шифрования и в его распоряжении имеется некоторое множество перехваченных сообщений (криптограмм) {Ci, i=1,2,…}, но не известен секретный ключ.

По исходным условиям данная атака является самой слабой из всех возможных. Многие современные криптосистемы успешно противостоят подобным атакам.

В случае атаки на основе известных открытых текстов (known-plaintext attack) дополнительно к условиям предыдущей атаки предполагается наличие у злоумышленника множества пар криптограмм и соответствующих им открытых текстов {(Ci,Mi): Ek(Mi)=Ci}.

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

При исследовании простой атаки с выбором открытых текстов (chosen-plaintext attack). Здесь злоумышленник имеет возможность выбрать необходимое количество открытых текстов {Ci, i=1,2,…} и получить соответствующие им шифртексты {Ci: Ek(Mi)=Ci}. Эту атаку часто называют "полуночной" или "обеденной" (midnight attack или coffee-break attack), что соответствует ситуации, когда оператор бесконтрольно оставил средство КЗИ в рабочем состоянии и им воспользовался злоумышленник. Хотя секретный ключ ему недоступен, злоумышленник может зашифровать подготовленные им открытые тексты, что дает ему дополнительную для криптоанализа системы информацию.

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

Простая атака с выбором шифртекста (chosen-ciphertext attack). Злоумышленник имеет возможность выбрать необходимое количество криптограмм и получить соответствующие им открытые тексты. При этом все криптограммы должны быть выбраны заранее, т. е., до получения первого открытого текста.

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

Атака с выбором текста (chosen-text attack). Злоумышленник имеет возможность атаковать криптосистему с двух сторон, т. е., выбирать как криптограммы (и расшифровывать их), так и открытые тексты (и зашифровывать их). Атака с выбором текста может быть простой, адаптивной, а также простой "с одного конца" и адаптивной с другого.

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

Для асимметричных криптосистем (с открытым ключом) классификация атак аналогична.

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

Кроме того, существуют атаки, специфические для криптосистем с открытым ключом. Например, если число возможных открытых текстов невелико, то злоумышленник, зная открытый ключ, может заранее заготовить достаточное количество криптограмм и затем, сравнивая эти "заготовки" с перехваченными криптограммами, с высокой вероятностью получать соответствующие открытые тексты. Такая атака называется атакой с проверкой текста (verifiable-text attack).

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

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

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

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

Приведем классификацию типов атак на системы ЭЦП, предложенную Голдвассером, Микалли и Ривестом. Атаки перечислены таким образом, что каждая последующая сильнее предыдущей.

Атака на основе известного открытого ключа. Злоумышленник знает только открытый ключ ЭЦП. Это – самая слабая из всех возможных атак. Очевидно, что злоумышленник всегда может провести такую атаку.

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

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

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

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

Угрозами для схемы электронной подписи являются раскрытие схемы или подделка подписи. Голдвассер, Микалли и Ривест уточняют понятие угрозы, определяя следующие типы угроз (перечислены в порядке усиления).

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

Селективная подделка. Подделка подписи для сообщения, выбранного злоумышленником. При этом предполагается, что это сообщение выбирается априори (до начала атаки) и что, если злоумышленник проводит атаку с выбором сообщений, то сообщение, для которого требуется подделать подпись, не может входить в число выбираемых во время атаки.

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

Полное раскрытие предполагает нахождение секретного ключа.

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

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

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

Безусловно, не имеет смысла тратить время и средства на дешифрование, если совокупные доходы (могут измеряться в различных единицах, в зависимости от области применения криптосистемы) от успешного "взлома" существенно ниже стоимости затрат на криптоанализ.

4. Теоретическая стойкость, совершенно стойкий шифр. Доказательство совершенной стойкости шифра Вернама по конечному модулю

Теоретико-информационный подход к оценке стойкости шифров в 1949 году предложил американский инженер К.Шеннон. На основе вероятностной модели шифра он сформулировал понятие совершенно стойкого шифра и показал, что Вернама на основе случайной равновероятной гаммы удовлетворяет требованию совершенной стойкости.

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

Например, перехватив сообщение {АБВВГ…}, зашифрованное простой заменой, злоумышленник получит информацию о совпадении третьего и четвертого символов в открытом тексте, что делает весьма вероятным предположение об открытом тексте {СУММА…}. После чего он может попытаться отождествить последующий шифрованный текст с тем или иным числовым выражением стоимости сделки.

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

Шифр называется совершенно стойким по Шеннону, если открытый и шифрованный тексты статистически независимы, то есть для M,C в случае P(C)>0 имеет место равенство условной и безусловной вероятности:

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

Теорема. Шифр Вернама по модулю N:

ci=(mi+γi) mod N, i=1,2,…,n

(1)

является совершенно стойким шифром, если ключ шифрования Г ={1 …n } является результатом случайного равновероятного выбора из множества всех возможных n-грамм в алфавите ZN.

Доказательство: Пусть имеем открытый и шифрованный тексты M,C, причем вероятность P(M)>0. Так как ключ Г выбирается случайно и равновероятно, то P(Г)=N-n.

Для заданных текстов M и C ключ Г из уравнения (1) определяется однозначно, поэтому:

где CM означает поразрядное сложение по mod N двух n-мерных векторов.

Откуда, используя определение условной вероятности, получим:

По формуле Байеса для P(C)>0 из последнего равенства следует:

Что и требовалось доказать.

5. Понятие практической стойкости

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

В этом случае количественной мерой надежности шифра является вычислительная сложность решения задачи дешифрования. Пусть E – множество применимых к шифрсистеме E алгоритмов дешифрования. Обозначим T() – среднее количество элементарных операций некоторого вычислителя, необходимых для успешной реализации алгоритма E.

Тогда время τ на реализацию алгоритма E оценивается величиной:

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

В частности, в таблице 1 для некоторых криптоалгоритмов приведено ориентировочное время вскрытия ключа методом последовательного перебора всех его допустимых значений для постоянной вычислительной мощности (I) компьютера, а также в варианте (II) ее возрастания по закону Мура (удвоение каждый год).

Таблица 1

Среднее время вскрытия ключа методом полного перебора

Таким образом, для оценки практической стойкости шифрсистемы E целесообразно использовать характеристику:

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

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

В частности, такой подход был предложен Диффи и Хеллманом для оценки стоимости дешифрования алгоритма DES путем создания специального вычислителя, построенного на принципе распараллеливания процессов перебора всех вариантов ключей (см. раздел «Принципы построения и использования блочных алгоритмов шифрования»).

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

Важным фактором оценки стойкости является объем материала, необходимого для вскрытия шифрсистемы.

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

Нетрудно видеть, что, например, для шифра Вернама, количество таких пар равно числу открытых сообщений длины N (т.е. 2NH). Для каждой пары вычисляется свой ключ и только один из них является истинным. В таких условиях восстановление истинного ключа становится проблематичной задачей.

Если длина сообщения равна одному символу в коде АSCII, то количество пар возможных пар достигает 256. При возрастании длины сообщения, в силу избыточности реальных языков, количество ложных вариантов несколько сокращается.

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

Для криптосистем с конечным множеством ключей K расстояние единственности может быть получено из формулы:

где R величина избыточности языка, N – мощность алфавита открытого текста, |K| мощность множества ключей.

Упражнение. Рассчитать расстояние единственности для шифра простой замены на алфавите N=33, R=0,7. Указание: воспользоваться формулой Стирлинга для оценки числа 33!

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

До того момента, как длина шифрованного сообщения L (объем всех имеющихся в распоряжении криптоаналитика сообщений) не достигнет расстояния единственности, задача дешифрования заключается в поиске всех решений, имеющих наибольшую вероятность.

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

Средние трудозатраты W(L), измеряемые числом элементарных операций, необходимых для нахождения истинного ключа на основе шифрованного сообщения длиной N символов, называют рабочей характеристикой шифра (рис. 3).

W(L)

L

W(L)

L

Рис. 3. Рабочая характеристика шифра

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

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

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

Исходя из этих допущений необходимо:

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

проанализировать возможность применения наилучших из числа известных к моменту анализа алгоритмов решения поставленных задач;

провести всестороннее исследование тенденции развития обычных вычислительных средств и оценить стоимость создания специальных вычислителей (см раздел «Принципы построения и использования блочных алгоритмов шифрования»).

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

Заключна частина

Моделювання у сфері КЗІ дозволяє визначити пріоритети досліджень, провести апробацію певних методів та рішень, а також спрогнозувати умови застосування того чи іншого засобу КЗІ залежно від багатьох змінних параметрів.

← Предыдущая
Страница 1
Следующая →

Скачать

ПАК_Лекция_Т2(Л2).docx

ПАК_Лекция_Т2(Л2).docx
Размер: 135 Кб

Бесплатно Скачать

Пожаловаться на материал

Практичні вимоги до симетричних шифрів. Модель порушника та модель загроз криптосистемі. Види атак на симетричні та асиметричні криптосистеми. Теоретична стійкість, досконало стійкий шифр. Досконала стійкість шифру Вернама по кінцевому модулю. Поняття практичної стійкості

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Оценка качества вскрытия продуктивных пластов методом прямых керновых испытаний

Курсовая работа. по дисциплине «Техника и технология строительства скважин». Лигносульфонатные реагенты. Общие требования организации работ. Промыслово-геологические задачи бурения. Основы управления информативностью геофизических исследований в скважинах. Расчеты показателей качества вскрытия продуктивного пласта на буровом растворе. Технологические факторы управления продуктивностью скважины.

Маргрит Кеннеди Деньги без процентов и инфляции

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

Контрольная работа по дисциплине: Технология машиностроения

Сборочный чертеж изделия Маршрут сборки привода Маршрут обработки детали «зубчатая шестерня» Технологическая схема сборки привода

Жилищное право. Жилищный фонд

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

Обеспечение деятельности предприятия

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

Сохранить?

Пропустить...

Введите код

Ok