Вероятностное шифрование

Понятие вероятностного шифрования было изобретено Шафи Голдвассером (Shafi Goldwasser) и Сильвией Микали [624]. Хотя их теория позволяет создать самую безопасную из изобретенных криптосистем, ранняя реализации была неэффективной [625]. Но более поздние реализации все изменили.

Идеей вероятностного шифрования является устранение утечки информации в криптографии с открытыми ключами. Так как криптоаналитик всегда может расшифровать случайные сообщения открытым ключом, он может получить некоторую информацию. При условии, что у него есть шифротекст C= E_K(M), и он пытается получить открытый текст M, он может выбрать случайное сообщение M'и зашифровать его: C'= E_K(M'). Если C'= C, то он угадал правильный открытый текст. В противном случае он делает следующую попытку.

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

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

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

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

C₁ = E_K(M), C₂ = E_K(M), C₃ = E_K(M), . . . C_i = E_K(M)

M= D_K(C₁) = D_K(C₂) = D_K(C₃)= . . . = D_K(C_i)

При вероятностном шифровании криптоаналитику больше не удастся шифровать произвольные открытые тексты в поисках правильного шифротекста. Для иллюстрации пусть у криптоаналитика есть шифротекст C_i = E_K(M). Даже если он праильно угадает M, полученный при шифровании E_K(M) результат будет совершенно другим шифротекстом C: C_j. Сравнивая C_iи C_j, он не может по их совпадению определить правильность своей догадки.

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

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

Однако Мануэль Блюм (Manual Blum) и Голдвассер (Goldwasser) получили эффективную реализацию вероятностного шифрования с помощью генератора псевдослучайных битов Blum Blum Shub (BBS), описанного в разделе 17.9 [199].

Генератор BBS основан на теории квадратичных остатков. Существуют два простых числа, pи q, конгруэнтных 3 по модулю 4. Это закрытый ключ. Их произведение, pq= n, является открытым ключом. (Запомните свои p и q, безопасность схемы опирается на сложность разложения n на множители.)

Для шифрования сообщения Mсначала выбирается случайное x, взаимно простое с n. Затем вычисляется

x₀ = x² mod n

x₀ служит стартовой последовательностью для генератора псевдослучайных битов BBS, а выход генератора используется в качестве потокового шифра. Побитно выполняется XOR M с выходом генератора. Генератор выдает биты b_i (младший значащий бит x_i, где x_i = x_i-1² mod n), поэтому

M=M₁, M₂, M₃, . . . M_t

c = M₁ Å b₁, M₂ Å b₂, M₃ Å b₃, . . . M_t Å b_t

где t - это длина открытого текста

Добавьте последнее вычисленное значение, x_t, к концу сообщения, и дело сделано.

Расшифровать это сообщение можно только одним способом - получить x₀ и с этой стартовой последовательностью запустить генератор BBS, выполняя XOR выхода с шифротекстом. Так как генератор BBS безопасен влево, значение x_t бесполезно для криптоаналитика. Только тот, кому известны p и q, может расшифровать сообщение. Вот как на языке C выглядит алгоритм получения x₀ из x_t:

int xO (int p, int q, int n, int t, int xt) {

int a, b, u, v, w, z;

/* мы уже знаем, что НОД(p,q) == 1 */

(void)extended_euclidian(p, q, &a, &b);

u = modexp ((p+l)/4, t, p-l);

v = modexp ((q+l)/4, t, q-l);

w = modexp (xt%p, u, p);

z = modexp (xt%p, v, q);

return (b*q*w + a*p*z) % n;

}

При наличии x₀ дешифрирование несложно. Просто задайте стартовую последовательность генератора BBS и выполните XOR результата с шифротекстом.

Эту схему можно сделать еще быстрее, используя все известные безопасные биты x_i, а не только младший значащий бит. С таким улучшением вероятностное шифрование Blum-Goldwasser оказывается быстрее RSA и не допускает утечки информации об открытом тексте. Кроме того, можно доказать, что сложность вскрытия этой схемы равна сложности разложения n на множители.

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