Числа Блюма.

Числа вида n=pq, p, q – различные простые числа, причем p ≡3(mod 4), q ≡3(mod 4), называются числами Блюма.

Пусть n – число Блюма, и a Q (n). Тогда сравнение x ²≡ a (mod n) имеет четыре решения, которые можно представить в виде системы: . Заметим, что . Аналогично получим . То есть один корень из пары b, —b является, а другой не является квадратом по модулю p, один корень из пары c, —c является, а другой не является квадратом по модулю q.

Таким образом, если n – число Блюма, то один из четырех корней сравнения x ²≡ a (mod n) является квадратом и один – псевдоквадратом по модулю n. Корень, являющийся квадратом по модулю n, называется главным корнем.

Итак, мы только что показали важное свойство квадратичных сравнений по модулю чисел Блюма: извлекая квадратный корень по модулю Блюма, получаем 4 решения, из одного из которых в свою очередь можно извлечь квадратный корень, и т. д. На этом важном свойстве построено несколько криптосистем.

BBS-генератор (генератор Blum-Blum-Shub):

Параметры генератора: n=pq, p, q – различные простые числа, причем p ≡3(mod 4), q ≡3(mod 4) (то есть n – число Блюма).

Начальное состояние (ключ генератора): s ₀ Q (n)

Генерируемая последовательность: BBS(s ₀)= z ₁, z ₂, …, z_m, где z_i=s_i mod 2, i =1,2,…, m, s_i+1=s_i² mod n, i ≥ 0.

Теорема (об условной стойкости BBS-генератора)

Если существует алгоритм, вычисляющий z ₀= s ₀ mod 2 по BBS(s ₀) за полиномиальное время с вероятностью не меньше ½+ε, ε>0, то для любого δ, ½<δ<1, существует вероятностный алгоритм, который различает квадраты и псевдоквадраты по модулю n за полиномиальное время с вероятностью не меньшей δ.

■

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

Дата добавления: 2015-09-07