Введение в современную криптографию


Равносильная формулировка



Pdf көрінісі
бет44/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   40   41   42   43   44   45   46   47   ...   249
Криптография Катц

Равносильная формулировка. Определение 3.8 требует, чтобы ни один ppt 
противник не мог определить, какое из двух сообщений зашифровано, с веро-
ятностью значительно больше 1/2. Равносильная формулировка: каждый ppt 
противник действует одинаково, когда видит зашифрованное сообщение m0 
или m1. Поскольку A выводит один бит, «действовать одинаково» означает, что 
он выводит 1 в каждом случае почти с одинаковой вероятностью. Чтобы это 
формализовать, определим 
(n, b) как 
указано выше за исключением того, что используется фиксированный бит b (а 
не выбранный случайным образом). Пусть out (
(n, b)) означает вы-
веденный во время эксперимента противником A бит br. Следующее главным 
образом указывает на то, что ни один A не может определить, участвует он в 
эксперименте 
(n, 0) или в эксперименте 
(n, 1).
ОПРЕДЕЛЕНИЕ 3.9 Система шифрования с закрытым ключом Π = (Gen, 
Enc, Dec) обладает неразличимым шифрованием при наличии подслушиваю-
щей стороны, если для всех ppt противников A существует такая пренебрежи-
мо малая функция negl, что
Pr[outA(
(n, 0)) = 1] − Pr[outA(
(n, 1)) = 1]. ≤ negl(n).
Доказательство равносильности данного определения определению 3.8 
оставлено в качестве упражнения.
 Шифрование и длина открытого текста 
Базовое понятие надежного шифрования не требует того, чтобы системы 
шифрования скрывали длин открытого текста и, фактически, все широко ис-
пользуемые системы шифрования обнаруживают длину открытого текста (или 
близкую к ней). Основная причина в том, что невозможно поддерживать со-
общения произвольной длины при сокрытии всей информации об открытом 
тексте (см. Упражнение 3.2). Во многих случаях это несущественно, поскольку 
открытый текст либо уже не секретен, либо не важен. Однако так происходит 
не всегда, иногда утечка информации о длине открытого текста представляет 
проблему. Например:


66
Простые численные и (или) текстовые данные: Скажем, используемая 
система шифрования точно воспроизводит длину открытого текста. Тогда за-
шифрованная информация о заработной плате раскроет, что некто получает 
5-значную или 6-значную заработную плату. Точно также шифрование ответов 
«да»/»нет» позволит точно догадаться об ответе.
• Автозаполнение: Веб-сайты часто имеют функцию «автозаполнения», или «вы-
падающего списка», по которому сервер предлагает список возможных слов или 
фраз, основываясь на частичной информации, которую пользователь уже ввел. Раз-
мер этого списка может раскрыть информацию о буквах, которые пользователь уже 
ввел. (Например, число автозаполнений для «th» гораздо больше, чем для «zo».)
• Поиск в базе данных: Рассмотрим случай, когда пользователь создает запрос 
обо всех записях базы данных, соответствующих некоторому критерию поиска. Ко-
личество выданных записей может раскрыть много информации о том, что искал 
пользователь. Это особенно может принести ущерб, если пользователь ищет ме-
дицинские данные и запрос раскрывает информацию о заболевании пользователя.
• Сжатые данные: Если открытый текст был сжат перед шифрованием, тогда 
информация об открытом тексте может быть раскрыта даже при шифровании 
данных только фиксированной длины. (Вследствие этого такая система шифро-
вания не будет соответствовать определению 3.8.) Например, короткий сжатый 
открытый текст будет указывать на то, что изначальный (несжатый) открытый 
текст обладает избыточностью. Если противник может управлять частью того, 
что было зашифровано, такая уязвимость может привести к тому, что противник 
узнает дополнительную информацию об открытом тексте. Доказано возможное 
использование атаки такого рода (ПРЕСТУПНАЯ атака) против зашифрован-
ного HTTP трафика для раскрытия куки (cookie) закрытой сессии.
При использовании шифрования необходимо определить, является ли утечка ин-
формации о длине открытого текста критичной, и если это так, необходимо принять 
меры для смягчения или предотвращения такой утечки, перед шифрованием необ-
ходимо дополнить сообщение битами заполнителя до указанной длины.


Достарыңызбен бөлісу:
1   ...   40   41   42   43   44   45   46   47   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет