p≡3(mod 4)
p≡1(mod 4)
p≡5(mod 8)
p≡1(mod 8)
p≡9(mod 16)
p≡1(mod 16)
И т. д.
а)Пусть
p≡3(mod 4), т.е.
p=4
k+3.
По критерию Эйлера,
. Подставляя сюда
p, получим
a2k+1≡1(mod
p)
a2k+2≡
a(mod
p)
Вернувшись сравнению, которое требуется решить, заметим, что
x2≡
a2k+2(mod
p), и тогда
x≡±ak+1(mod p) – искомое решение.
б)
p≡5(mod 8), т.е.
p=8
k+5.
Найдем какой-нибудь квадратичный невычет по модулю p. Согласно св-ву 7 для символа Лежандра, таким невычетом в случае
p=8
k+5 будет являться «2». Тогда, согласо критерию Эйлера, 2
4k+2≡—1(mod
p).
Так как a – квадратичный вычет по модулю p, то по критерию Эйлера,
.
Тогда возможны два варианта:
a2k+1≡1(mod
p) или
a2k+1≡—1(mod
p).
В первом случае дальнейшие рассуждения проводим как в пункте а, и получаем
x≡±
ak+1(mod
p).
Рассмотрим подробнее второй случай. Имеем:
a2k+1≡—1(mod
p)
Для того, чтобы избавиться от знака (—) в правой части, домножим левую часть этого сравнения на 2
4k+2, а левую – на –1.
2
4k+2a2k+1≡1(mod
p)
2
4k+2a2k+2≡
a(mod
p)
x≡±2
2k+1ak+1(mod
p)
Таким образом, имеются два кандидата на решение:
x≡±ak+1(mod p).x≡±22k+1ak+1(mod p)Вычислив и подставив каждое из них в исходное сравнение, выберем ту пару, которая удовлетворяет исходному сравнению.
в)
p≡9(mod 16), т.е.
p=16
k+9.
Найдем
N – какой-нибудь квадратичный невычет по модулю
p. Тогда по критерию Эйлера,
.
С другой стороны, поскольку
a – квадратичный вычет по модулю
p, то по критерию Эйлера,
.
Тогда возникают два случая:
a4k+2≡1(mod
p) или
a4k+2≡-1(mod
p).
Рассмотрим первый случай:
a4k+2≡1(mod
p). Поскольку показатель степени в левой части сравнения – четный, то вновь возникают два варианта:
a2k+1≡1(mod
p) или
a2k+1≡—1(mod
p), первый из которых приводит, как ранее, к кандидату в решение
x≡±
ak+1(mod
p), а второй вариант, рассуждая как в пункте б, приведем к кандидату в решения
x≡±
N4k+2ak+1(mod
p).
Рассмотрим второй случай:
a4k+2≡-1(mod
p). Для того, чтобы избавиться от знака (—) в правой части сравнения, домножим правую часть на
N8k+4, а левую – на –1. Получим
N8k+4a4k+2≡1(mod
p). Поскольку показатели степеней в левой части получившегося сравнения четны, то отсюда возникают два варианта:
N4k+2a2k+1≡1(mod
p) или
N4k+2a2k+1≡-1(mod
p).
Рассмотрим первый из вариантов:
N4k+2a2k+1≡1(mod
p)
N4k+2a2k+2≡
a(mod
p)
x≡±
N2k+1ak+1(mod
p).
Рассмотрим второй из вариантов:
N4k+2a2k+1≡-1(mod
p)
N12k+6a2k+1≡1(mod
p)
N12k+6a2k+2≡
a(mod
p)
x≡±
N6k+3ak+1(mod
p)
Итак, получили четыре пары – кандидата на решение:
x≡±ak+1(mod p)x≡±N2k+1ak+1(mod p)x≡±N4k+2ak+1(mod p)x≡±N6k+3ak+1(mod p)Вычислив и подставив в исходное сравнение, выберем ту пару, которая удовлетворяет исходному сравнению.
Рассмотренным способом можно построить решение для любого простого модуля
p. Если
p=2
hk+2
h—1+1, то при решении сравнения возникнет 2
h—2 пар – кандидатов в решение, каждая из которых будет иметь вид
x≡±
Nz(2k+1)ak+1(mod
p), где
.
Главная проблема здесь – отыскание квадратичного невычета
N, но поскольку, как было доказано ранее, квадратичных вычетов и невычетов по простому модулю – одинаковое количество, то невычет обязательно найдется.
Пример:Решить сравнение x
2≡8(mod 17).
17 – простое число. Выясним, имеет ли данное сравнение решение:
. Сравнение имеет 2 решения. Отыщем их.
17=2·8+1=4·4+1=8·2+1=16·1+1=32·0+17=2
5·0+17.
h=5,
k=0. Имеется 2
3=8 пар-кандидатов в решения.
Найдем какой-нибудь невычет по модулю 17:
.
Итак,
N=3 – кв. невычет по модулю 17.
Имеются следующие кандидаты в решения сравнения:
1)
x≡±8(mod 17) 5)
x≡±
348(mod
p)
2)
x≡±3·8(mod 17) 6)
x≡±
358(mod
p)
3)
x≡±3
28(mod 17) 7)
x≡±
368(mod
p)
4)
x≡±3
38(mod 17) 8)
x≡±
378(mod
p)
Будем проверять каждую пару решений, пока не найдем верное решение.
1)
x≡±8(mod 17). Тогда
x2≡64≡13(mod 17).
2)
x≡±3·8≡±24≡±7(mod 17). Тогда
x2≡49≡15(mod 17).
3)
x≡±3
28≡±72≡±4(mod 17). Тогда
x2≡16(mod 17).
4)
x≡±3
38≡±216≡±12(mod 17). Тогда
x2≡144≡8(mod 17).
Ответ:
x≡±12(mod 17), или
x≡±5(mod 17).
5.5. Квадратичные сравнения по составному модулю.
Рассмотрим сравнение вида
x2≡
a(mod
pα), где
p – простое нечетное число. Как было показано в п.4 §4, решение этого сравнения можно отыскать, решив сравнение
x2≡
a(mod
p). Причем сравнение
x2≡
a(mod
pα) будет иметь два решения, если
a является квадратичным вычетом по модулю
p.
Пример:Решить квадратичное сравнение
x2≡86(mod 125).
125 = 5
3, 5 – простое число. Проверим, является ли 86 квадратом по модулю 5.
. Исходное сравнение имеет 2 решения.
Найдем решение сравнения
x2≡86(mod 5).
x2≡1(mod 5).
Это сравнение можно было бы решить способом, указанным в предыдущем пункте, но мы воспользуемся тем, что квадратный корень из 1 по любому модулю есть ±1, а сравнение имеет ровно два решения. Таким образом, решение сравнения по модулю 5 есть
x≡±1(mod 5) или, иначе,
x=±(1+5
t1).
Подставим получившееся решение в сравнение по модулю 5
2=25:
x2≡86(mod 25)
x2≡11(mod 25)
(1+5
t1)
2≡11(mod 25)
1+10
t1+25
t12≡11(mod 25)
10
t1≡10(mod 25)
2
t1≡2(mod 5)
t1≡1(mod 5), или, что то же самое,
t1=1+5
t2.
Тогда решение сравнения по модулю 25 есть
x=±(1+5(1+5
t2))=±(6+25
t2). Подставим получившееся решение в сравнение по модулю 5
3=125:
x2≡86(mod 125)
(6+25
t2)
2≡86(mod 125)
36+12·25
t2+625
t22≡86(mod 125)
12·25
t2≡50(mod 125)
12
t2≡2(mod 5)
2
t2≡2(mod 5)
t2≡1(mod 5), или
t2=1+5
t3.
Тогда решение сравнения по модулю 125 есть
x=±(6+25(1+5
t3))=±(31+125
t3).
Ответ:
x≡±31(mod 125).
Рассмотрим теперь сравнение вида
x2≡
a(mod 2
α). Такое сравнение не всегда имеет два решения. Для такого модуля возможны случаи:
α=1. Тогда сравнение имеет решение только тогда, когда a≡1(mod 2), и решением будет x≡1(mod 2) (одно решение).
α=2. Сравнение имеет решения только тогда, когда a≡1(mod 4), и решением будет x≡±1(mod 4) (два решения).
α≥3. Сравнение имеет решения только тогда, когда a≡1(mod 8), и таких решений будет четыре. Сравнение x2≡a(mod 2α) при α≥3 решается так же, как сравнения вида x2≡a(mod pα), только в качестве начального решения выступают решения по модулю 8: x≡±1(mod 8) и x≡±3(mod 8). Их следует подставить в сравнение по модулю 16, затем по модулю 32 и т. д. вплоть до модуля 2α.
Пример:Решить сравнение
x2≡33(mod 64)
64=2
6. Проверим, имеет ли исходное сравнение решения. 33≡1(mod 8), значит сравнение имеет 4 решения.
По модулю 8 эти решения будут:
x≡±1(mod 8) и
x≡±3(mod 8), что можно представить как
x=±(1+4
t1). Подставим это выражение в сравнение по модулю 16
x2≡33(mod 16)
(1+4
t1)
2≡1(mod 16)
1+8
t1+16
t12≡1(mod 16)
8
t1≡0 (mod 16)
t1≡0 (mod 2)
Тогда решение примет вид
x=±(1+4
t1)=±(1+4(0+2
t2))=±(1+8
t2). Подставим получившееся решение в сравнение по модулю 32:
x2≡33(mod 32)
(1+8
t2)
2≡1(mod 32)
1+16
t2+64
t22≡1(mod 32)
16
t2≡0 (mod 32)
t2≡0 (mod 2)
Тогда решение примет вид
x=±(1+8
t2) =±(1+8(0+2t
3)) =±(1+16
t3). Подставим получившееся решение в сравнение по модулю 64:
x2≡33(mod 64)
(1+16
t3)
2≡33(mod 64)
1+32
t3+256
t32≡33(mod 64)
32
t3≡32 (mod 64)
t3≡1 (mod 2)
Тогда решение примет вид
x=±(1+16
t3) =±(1+16(1+2t
4)) =±(17+32
t4). Итак, по модулю 64 исходное сравнение имеет четыре решения:
x≡±17(mod 64)
и
x≡±49(mod 64).
Теперь рассмотрим сравнение общего вида:
x2≡
a(mod
m), (
a,
m)=1,
- каноническое разложение модуля
m. Согласно Теореме из п.4 §4, данному сравнению равносильна система
Если каждое сравнение этой системы разрешимо, то разрешима и вся система. Найдя решение каждого сравнения этой системы, мы получим систему сравнений первой степени, решив которую по китайской теореме об остатках, получим решение исходного сравнения. При этом количество различных решений исходного сравнения (если оно разрешимо) есть 2
k, если α=1, 2
k+1, если α=2, 2
k+2, если α≥3.
Пример:Решить сравнение
x2≡4(mod 21).
21 – составное число. Факторизуем его: 21=3·7. Проверим разрешимость исходного сравнения:
,
. Сравнение разрешимо и имеет 2
2=4 решения.
Составим систему:
. Решим каждое из уравнений этой системы. Получим
. Итак, имеем 4 системы:
1)
2)
3)
4)
Решая каждую из этих систем по китайской теореме об остатках, получим четыре решения:
x≡±2(mod 21),
x≡±5(mod 21).
5.6. Тест на простоту Миллера-Рабина.
Теперь, наконец, мы располагаем достаточной информацией для того, чтобы привести тест Миллера-Рабина. Этот тест, как и тесты Ферма и Соловея-Штрассена, строит вероятно простые числа, то есть число, опознанное этим тестом как простое, может с некоторой малой вероятностью оказаться составным, однако вероятность ошибки у теста Миллера-Рабина гораздо ниже, чем у первых двух тестов. Как правило, для опознания простого числа достаточно одной итерации теста, но все же рекомендуемое количество итераций – пять.
Тест Миллера-Рабина основан на двух важных фактах:
1) Согласно теореме Ферма, если
n – простое число, то для любого
a: 0<
a<
n выполняется
an—1≡1(mod
n);
2) Если
n – простое число, то сравнение
x2≡1(mod
n) имеет только тривиальные корни
x≡±1(mod
n), а если
n – составное, то такое сравнение имеет несколько корней помимо тривиальных.
Тест Миллера-Рабина: Вход:
n=2
sr+1 – нечетное число, проверяемое на простоту,
s≥0,
r – нечетное.
t - количество итераций, параметр надежности.
1. Повторить
t раз следующие шаги:
1.1. Случайным образом выбрать
a: 1<
a<
n—1.
1.2. Строим последовательность
b0,
b1,…,
bs, где
bj=
mod
n,
j=0,1,…,
s.
1.3. Если в построенной последовательности не встретилась «1», то идти на Выход с сообщением «
n - составное число».
1.4. Если перед первой единицей в последовательности стоит не «-1», то идти на Выход с сообщением «
n - составное число».
2. Идти на Выход с сообщением «
n – простое число с вероятностью ε
t».
Выход.
Обратим внимание на то, что в последовательности
b0,
b1,…,
bs каждый последующий член является квадратом предыдущего по модулю
n, а последний член есть ни что иное как
an—1 mod
n. Вероятность ошибки ε ≤ φ(
n)/4
n, то есть верхняя граница ошибки на одной итерации для теста Миллера-Рабина в 2 раза меньше аналогичной для теста Соловея-Штрассена и в 4 раза – для теста Ферма.
Пример 1.n=65=64+1=2
6+1.
r=1,
s=6.
t=5.
1. 1-я итерация:
1.1.
a=8.
1.2. Составляем последовательность: 8, 64=—1, 1, 1, 1, 1.
1.3. В последовательности встретилась «1».
1.4. Перед первой единицей стоит —1.
1. 2-я итерация:
1.1.
a=11.
1.2. Составляем последовательность: 11, 56, 16, 61, 16, 61.
1.3. В последовательности не встретилась «1».
Выход: «
n - составное число».
В том случае, когда тест Миллера-Рабина определяет составность числа
n на шаге 1.4, появляется возможность частично факторизовать
n.
Действительно, пусть в последовательности
b0,
b1,…,
bs, где
bj=
mod
n, нашлось такое
i, что
bi≠±1,
bi+1=1. Обозначим для краткости
bi=b. Тогда
bi+1=
b2≡1(mod
n). Тогда
n\(
b2—1)
n\(
b+1)(
b—1). Но в силу того, что
b ±1(mod
n),
n не делит (
b+1),
n не делит (
b—1). Следовательно,
1<НОД(
n,
b—1)<
n,
1<НОД(
n,
b+1)<
n.Значит, НОД(
n,
b—1) и НОД(
n,
b+1) являются нетривиальными делителями числа
n.
Пример 2n=161=160+1=2
5·5+1.
r=5,
s=5.
1. 1-я итерация:
1.1.
a=22. a
5 mod 161 = 22
5 mod 161=22.
1.2. Составляем последовательность: 22, 1, 1, 1, 1, 1.
1.3. В последовательности встретилась «1».
1.4. Перед первой единицей стоит 22.
Выход: «
n - составное число».
Факторизуем 161: b=22. b+1=23, b—1=21.
Вычислим НОД(161, 23): 161=23·7+0.
НОД(161,21): 161=21·7+14
21=14·1+7
14=7·2+0.
Итак, нашли два нетривиальных делителя 161, и получили 161=23·7.
Надо заметить, что на самом деле случай, когда в тесте Миллера-Рабина возникает возможность факторизации, происходит весьма редко. Гораздо чаще сообщение о составности мы получаем на шаге 1.3.
5.7. Связь задач извлечения квадратных корней и факторизации по модулю RSA. Криптосистема Рабина.
Пусть дано сравнение
x2≡
a(mod
pq),
p,
q – различные большие простые числа. Как следует из предыдущего пункта, решение данного сравнения можно найти, решив систему
, при этом необходимым условием существования решения является
. В том случае, если решения существуют, исходное сравнение имеет четыре различных решения:
x≡±
x1(mod
pq),
x≡±
x2(mod
pq)
Утверждение.Для модуля RSA (
n=pq,
p,
q – различные большие простые числа) задачи факторизации и извлечения квадратных корней вычислительно эквивалентны.
(Напомним, что две проблемы называются
вычислительно эквивалентными, если за полиномиальное время по решению одной из них находится решение другой и наоборот.)
Доказательство:1) Действительно, если умеем факторизовать модуль, то сможем извлечь квадратные корни по этому модулю (разложив исходное сравнение в систему и решив ее за полиномиальное время).
2) Если же разложения модуля RSA на простые сомножители неизвестно, но известны 4 различных решения сравнения
x2≡
a(mod
n), и эти решения суть ±x(mod
n), ±y(mod
n). Выберем пару чисел
x,
y. Заметим, что
x2≡
y2(mod
pq),
x ±y(mod
pq).
x2≡
y2(mod
pq)
x2—
y2 =(
x+y)(
x—y)≡0 (mod
pq), причем
x+y 0(mod
pq),
x—y 0(mod
pq). То есть
pq\(
x+y)(
x—y), но
pq не делит
x+y,
pq не делит
x—y. Пользуясь основным свойствам простых чисел а также в силу равноправия сомножителей
p и
q, заключаем, что
p\(
x+y),
q\(
x—y), и тогда
p=НОД(
x+y,
n)
q=НОД(
x—y,
n).
Вычисление наибольшего общего делителя осуществляется при помощи полиномиального алгоритма – алгоритма Евклида.
Доказуемо стойкая криптосистема Рабина.Криптосистема Рабина является асимметричной системой. Ее параметрами являются
n=pq,
p,
q – различные большие простые числа. В качестве открытого ключа (ключа шифрования) выступает
k1=
n, в качестве секретного ключа (ключа расшифрования) –
k2=(
p,
q).
Открытый текст
x≠0 возводится в квадрат по модулю
n, и получается криптограмма
y=x2 mod
n. Для расшифрования последней требуется вычислить квадратный корень из
y по модулю
n. При решении сравнения
y≡x2 (mod
n) возникнет четыре различных корня. Для того чтобы получатель мог выбирать нужный корень, в открытый текст
x до шифрования вносится избыточность – участок текста определенного вида.
Для дешифрования криптограммы, то есть для вычисления
x по
y в отсутствие закрытого ключа требуется извлечь квадратный корень по составному модулю, не зная его разложения на простые сомножители.
Криптосистема называется
доказуемо стойкой, если для нее доказана невозможность дешифрования без решения вычислительно трудной задачи. В силу доказанной вычислительной эквивалентности задач факторизации и извлечения квадратных корней, задача извлечения квадратных корней так же сложна, как задача факторизации, а последняя считается вычислительно сложной задачей. Поэтому криптосистема Рабина – доказуемо стойкая.
5.8. Квадраты и псевдоквадраты.
Пусть
n – модуль RSA, то есть
n=pq,
p,
q – различные большие простые числа.
Возьмем произвольное число
a: (
a,
n)=1. Возможны следующие случаи:
1)
. Тогда число
a является квадратичным вычетом, или квадратом, по модулю
n.
2)
,
, или
,
. Тогда
, и
a не является квадратом по модулю
n. То есть, не зная разложения модуля RSA на простые сомножители и получив отрицательное значение символа Якоби, можем с определенностью сказать, что
a – не квадрат по модулю
n.
3)
, тогда
a не является квадратом по модулю
n, но символ Якоби, как и для квадрата по модулю
n, равен единице:
. То есть, не зная разложения модуля
n на простые сомножители и получив положительное значение символа Якоби, не можем наверняка определить, является ли
a квадратом по модулю
n. Числа
a:
называются
псевдоквадратами по модулю
n=pq. Множество псевдоквадратов по модулю
n обозначается
.
Утверждение (о мощности множеств квадратов и псевдоквадратов по модулю RSA).n=pq,
p,
q – различные простые числа
|
Q(n)|=|
|=φ(
n)/4.
Доказательство:Согласно доказанной в п.1. теореме о числе кавдратичных вычетов, |
Q(
p)|=|
|=(
p—1)/2, |
Q(
q)|=|
|=(
q—1)/2. В силу взаимной простоты чисел
p и
q, среди чисел 0,1, 2, … ,
n—1 окажется ровно |
Q(
p)|·|
Q(
q)|=φ(
n)/4 квадратов и |
|·|
|=φ(
n)/4 псевдоквадратов.
Задача различения квадратов и псевдоквадратов не сложнее задачи факторизации, так как, зная разложение
n на простые сомножители, сможем вычислить
и
с помощью полиномиального алгоритма.
На момент написания этого пособия не имелось никакой информации о том, проще ли задача различения квадратов и псевдоквадратов, чем задача факторизации.
5.9. Числа Блюма.
Числа вида
n=pq,
p,
q – различные простые числа, причем
p≡3(mod 4),
q≡3(mod 4), называются
числами Блюма.
Пусть
n – число Блюма, и
a Q(
n). Тогда сравнение
x2≡
a(mod
n) имеет четыре решения, которые можно представить в виде системы:
. Заметим, что
. Аналогично получим
. То есть один корень из пары
b,
—b является, а другой не является квадратом по модулю
p, один корень из пары
c,
—c является, а другой не является квадратом по модулю
q.
Таким образом, если
n – число Блюма, то один из четырех корней сравнения
x2≡
a(mod
n) является квадратом и один – псевдоквадратом по модулю
n. Корень, являющийся квадратом по модулю
n, называется
главным корнем.
Итак, мы только что показали важное свойство квадратичных сравнений по модулю чисел Блюма: извлекая квадратный корень по модулю Блюма, получаем 4 решения, из одного из которых в свою очередь можно извлечь квадратный корень, и т. д. На этом важном свойстве построено несколько криптосистем.
BBS-генератор (генератор Blum-Blum-Shub):Параметры генератора:
n=pq,
p,
q – различные простые числа, причем
p≡3(mod 4),
q≡3(mod 4) (то есть n – число Блюма).
Начальное состояние (ключ генератора):
s0 Q(
n)
Генерируемая последовательность: BBS(
s0)=
z1,
z2, …,
zm, где
zi=si mod 2,
i=1,2,…,
m, s
i+1=s
i2 mod
n,
i ≥ 0.
Теорема (об условной стойкости BBS-генератора)Если существует алгоритм, вычисляющий
z0=
s0 mod 2 по BBS(
s0) за полиномиальное время с вероятностью не меньше Ѕ+ε, ε>0, то для любого δ, Ѕ<δ<1, существует вероятностный алгоритм, который различает квадраты и псевдоквадраты по модулю
n за полиномиальное время с вероятностью не меньшей δ.
■
Другими словами, если проблема распознавания квадратов и псевдоквадратов по модулю Блюма не решается за полиномиальное время, то BBS-генератор криптографически стоек. Проблему различения квадратов и псевдоквадратов по модулю Блюма действительно считают вычислительно сложной, поскольку в настоящее время она не решается эффективно без факторизации модуля, что служит основанием для признания BBS-генератора стойким.
Криптосистема Блюма-Гольдвассер (Blum-Goldwasser).Пусть
x1,
x2, … ,
xm – последовательность бит открытого текста. В качестве параметров криптосистемы выбираем
n=pq – число Блюма,
s0 – случайное число из
Zn, взаимно простое с
n.
В качестве открытого ключа для шифрования выступает
n, в качестве секретного ключа для расшифрования – пара (
p,
q).
Для того, чтобы зашифровать открытый текст, обладатель открытого ключа выбирает s
0. На основе BBS-генератора по ключу
s0 получает последовательность квадратов
s1,
s2, … ,
sm, по которой получает последовательность младших бит
z1,
z2, …,
zm. Путем гаммирования с этой последовательностью битов открытого текста получает шифрованный текст
yi=xi zi,
i=1,2,…,
m. Шифрограмма, которая пересылается обладателю секретного ключа, есть (
y1,
y2,…,
ym,
sm+1). После формирования шифрограммы последовательность
si,
i=0,1,…,
m уничтожается, и при следующем сеансе связи отправитель выбирает новое
s0.
Получатель шифрограммы восстанавливает по
sm+1 последовательность главных корней
sm, … ,
s1 и последовательность их младших бит
z1,
z2, …,
zm, а затем расшифровывает шифрограмму:
xi=yi zi ,
i=1,2,…,
m.
Криптосистема Гольдвассер-Микали. Параметры системы:
n=pq – число Блюма,
z – случайное число из
.
Открытый ключ для шифрования – пара (
n,
z), секретный ключ для расшифрования – пара (
p,
q).
Пусть
x1,
x2, … ,
xm – последовательность бит открытого текста. Бит шифрованного текста вычисляем по биту открытого текста как
, где
ai – случайное число из Z
n.
В итоге шифрования получается последовательность не бит, а чисел, причем
yi является псевдоквадратом по модулю n, если
xi =1, и квадратом, если
xi=0.
Адресату, обладающему секретным ключом, отправляется последовательность чисел шифртекста
y1,
y2, …,
ym , после чего параметр
z может быть уничтожен.
Адресат осуществляет расшифрование следующим образом:
,
i=1,2,…,
m.
Условная стойкость криптосистемы Гольдвассер-Микали основана на предположительной сложности алгоритма распознавания квадратов и псевдоквадратов по модулю Блюма без знания разложения модуля на простые сомножители.
Данная криптосистема имеет существенный недостаток – размер шифртекста значительно превышает размер открытого текста, ведь каждый бит последнего при шифровании преобразуется в число такой же размерности, как
n.
