Шифрование с закрытым ключом (симметричное)
Схема
x⟶S⟶R⟶x S и R знают ключ d. На второй строчке есть еще A (Ева), который пытается что-то узнать об x. Он ничего не должен узнать об x, а точнее он может узнать только то, что он мог бы узнать без входа.
Формальное определение
d=D(1n), D - генератор ключей, вероятностный полиномиальный алгоритм.
m=E(x,d) - алгоритм шифрования, вероятностный полиномиальный алгоритм.
y=D(m,d) - алгоритм дешифрования, вероятностный полиномиальный алгоритм.
Условине корректности: Pr{D(E(x,d),d)=x}≃1, где ≃ означает стремление быстрее любого полинома.
Условие надежности: E(x,d) и E(x′,d) вычислительно не отличимы.
Любая пара протоколов, для которых это верно будет называться схемой шифрования с закрытым ключом.
Гаммирование (one-time pad): E(x,d)=x⊕D, D(m,d)=m⊕d, |d|=|x|. Выполнение условий корректности и надежности проверяется лекго. Проблема в длине ключа. И в том, что схема одноразовая, ибо если зашифровать x и y, то станет известна побитовая сумма x и x′.
Гаммирование с генератором псевдо-случайных чисел: E(x,d)=x⊕G(d), D(m,d)=m⊕G(d). Здесь |x|=poly(|d|). Но схема по-прежнему одноразовая. Чтобы сделать многоразовую схему можно вязть генератор отображающий n бит в 20n.
Недостаток шифрования с закрытым ключом: нужен закрытый канал, для передачи ключа.