Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- Часть II (Симметричная) Криптография с закрытым ключом 51 Глава 3
- 3.1 Расчетная стойкость
| Подсказка: Возьмите c1 = c2 .
(b) Скажем, система шифрования (Gen, Enc, Dec) является совершенно на- дежной для двух отдельных сообщений, если для всех распределений по M × M, где первое и второе сообщения обязательно являются разными (т.е ., рас- пределения по парам разных сообщений), все m1, m2 ∈ M, и все c1, c2 ∈ C при Pr[C1 = c1 ٨ C2 = c2] > 0: Pr[M1 = m1 ٨ M2 = m2 | C1 = c1 ٨ C2 = c2]= Pr[M1 = m1 ٨ M2 = m2]. Покажите систему шифрования, которая доказуемо соответствует данному определению. Подсказка: Предложенная вами система шифрования не обяза- тельно должна быть эффективной, хотя эффективное решение воз- можно . 51 Глава 3 Шифрование с закрытым ключом В предыдущей главе мы рассмотрели некоторые фундаментальные ограничения абсолютной криптографической стойкости. В данной главе мы начнем изучение со- временной криптографии с введения более слабого (но обоснованного) понятия вы- числительной стойкости. Затем мы покажем, как это определение можно использо- вать, чтобы обойти ранее показанные результаты невероятности и, в частности, как короткий ключ (скажем, длиной 128 бит) может быть использован для шифрования множества длинных сообщений (скажем, общим размеров в несколько гигабайт). Также мы изучим фундаментальное понятие «псевдослучайность», которое означает, что нечто может «выглядеть» случайным, но на самом деле таким не является. Это понятие лежит в основе современной криптографии, а также ис- пользуется и подразумевается в областях за ее пределами. 3.1 Расчетная стойкость В Главе 2 мы ввели понятие «абсолютная стойкость». И хотя абсолютная стойкость - цель многообещающая, она еще и необоснованно высокая. Абсо- лютная стойкость предусматривает абсолютное отсутствие утечки информа- ции о зашифрованном сообщении, даже если подслушивающая сторона обла- дает неограниченными вычислительными возможностями. Для практических же целей система шифрования будет считаться надежной, если она допускает ничтожно малую утечку информации в случае вмешательства подслушива- ющей стороны с ограниченными вычислительными возможностями. Напри- мер, система, допускающая утечку информации с максимальной вероятностью равной 2−60 при вмешательстве подслушивающей стороны, обладающей вы- числительной мощностью равной 200 годам вычислений на самом быстром из доступных суперкомпьютеров, вполне подходит для использования в реальных условиях. Стойкость, в соответствии с определением учитывающая предел вы- числительных возможностей перехватчика и допускающая малую вероятность провала, называется вычислительной и отличается от информационно-теоре- тических по своей природе понятий (например, абсолютная стойкость). Сейчас вычислительная стойкость является реальным направлением, в котором стой- кость определяется для всех криптографических целей. Подчеркиваем, что хотя мы и отказываемся от достижения абсолютной стой- кости, это не означает, что мы отходим от строгого математического подхода. 52 Определения и доказательства все еще играют важную роль. Единственное отличие - мы рассматриваем более слабые (но все еще эффективные) определения стойкости. Расчетная стойкость объединяет в себе два ослабления по сравнению с ин- формационно-теоретическими понятиями стойкости (в случае шифрования, оба эти ослабления необходимы для выхода за пределы ограничений абсолют- ной стойкости, описанных в предыдущей главе): 1. Стойкость обеспечивается только против эффективных противников, работающим в течение правдоподобного количества времени. Это означает, что если перехватчик обладает достаточным количеством времени (или доста- точными вычислительными возможностями), он может взломать систему. Если мы сумеем создать систему, для взламывания которой потребуются ресурсы, превышающие ресурсы реального злоумышленника, для всех практических це- лей мы можем считать систему невзламываемой. 2. Противники потенциально могут добиться успеха (т.е. стойкость по- тенциально может быть нарушена) с очень малой вероятностью. Если мы сможем свести такую вероятность к достаточному минимуму, нам не придется переживать из-за нее. Для построения значимой теории нам необходимо точно определить вышеу- казанные ослабления. Для этой цели существует два общих подхода: конкрет- ный подход и асимптотический подход - оба из которых описываются далее. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|