Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| 2.1 Определения
Начнем с того, что напомним и расширим синтаксис, введенный в предыдущей главе. Система шифрования определяется тремя алгоритмами Gen, Enc, и Dec, а также заданием пространства (конечного) сообщения M при |M|>1.1 Алгоритм генерации ключа Gen - это вероятностный алгоритм, который выводит ключ k , вы- бираемый в соответствии с некоторой функцией распределения. Мы обозначаем (конечное) пространство ключей K, т.е. множество всех возможных ключей, ко- торые могут быть выведены функцией Gen. Алгоритм шифрования Enc на входе принимает ключ k ∈ K и сообщение m ∈ M и на выходе выдает шифртекст c. Теперь допустим, что алгоритм шифрования является вероятностным (итак, Enck (m) мо- жет выводить различный шифртекст при неоднократном запуске), и запишем c ← Enck (m) для обозначения, возможно, вероятностного процесса, с помощью которо- го сообщение m будет зашифровано ключом k для пол учения шифртекста c. (Если алгоритм Enc является детерминированным, мы можем подчеркнуть это, написав c := Enck (m). Далее , мы также можем иногда использовать запись x ← S для обозна- чения единого отбора x из множества S.) Допустим, C обозначает множество всех возможных шифртекстов, которые могут быть выведены функцией Enck (m), для всех возможных выборов k ∈ K и m ∈ M (и для всех случайных выборов алгоритма Enc, если он случаен). Алгоритм расшифрования Dec принимает на входе ключ k ∈ K и шифртекст c ∈ C, а на выходе выдает сообщение m ∈ M. Допустим совершен- ную корректность, т.е . для всех k ∈ K, m ∈ M и любого шифртекста c, выведенно- го функцией Enck (m), справедливо Deck (c) = m с вероятностью 1. Совершенная корректность подразумевает, что мы можем допустить, что алгоритм Dec является детерминированным, без потери общности, поскольку функция Deck (c) должна выводить один и тот же результат при каждом запуске. Таким образом, для обо- значения процесса расшифрования шифртекста c с использованием ключа k для 36 получения сообщения m мы запишем m := Deck (c). В определениях и теоремах, представленных ниже мы ссылаемся на распределе- ние вероятностей по K, M, и C. Распределение по K определяется запуском алгорит- ма Gen и получением вывода. (Так почти всегда и есть на самом деле, алгоритм Gen равномерно выбирает ключ из K, и мы фактически допускаем это без потери общ- ности; см. Упражнение 2.1.) Предположим, что K - случайная переменная, указыва- ющая значение ключа, выведенного алгоритмом Gen. Таким образом, для любого k ∈ K, Pr[K = k] обозначает вероятность того, что ключ, выведенный Gen, равняется k. Ана логичным образом допустим, что M - случайная переменная, обозначающая сообщение для шифрования, тогда Pr[M = m] означает вероятность того, что со- общение получит значение m ∈ M. Распределение вероятности сообщения не опре- делено самой системой шифрования, но вместо этого отражает правдоподобную вероятность того, что стороны с помощью системы отправят разные сообщения, кроме того, перехватчик не будет уверен в том, что будет отправлено. Например , пе- рехватчик может знать, что сообщение будет либо «attack today» (атакуй сегодня), либо «don’t attack» (не атакуй). Перехватчик может даже узнать (другими способа- ми), что вероятность сообщения, содержащего команду атаковать, составляет 0,7, а вероятность сообщения с командой не атаковать составляет 0,3. В таком случае мы имеем Pr[M = attack today] = 0,7 и Pr[M = don’t attack] = 0,3. K и M считаются независимыми, т.е. передаваемые сторонами сообщения не зависят от имеющегося у них ключа. Это имеет смысл еще и потому, что рас- пределение по K определяется самой системой шифрования (она определена алгоритмом Gen), тогда как распределение M зависит от условий использова- ния системы шифрования. Фиксация системы шифрования и распределения по M определяет распре- деление по пространству шифртекста C, полученного при выборе ключа k ∈ K (в соо тветствии с алгоритмом Gen) и сообщения m ∈ M (в соответствии с за- данным распределением), а затем вычисление шифртекста c ← Enck (m). Допу- стим, C - случайная переменная, определяющая полученный шифртекст. Таким образом, при c ∈ C для определения вероятности того, что шифртекст равняется заданному значению c, запишем Pr[C = c]. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|