Криптосистема Накаша — Штерна (Tjnhmkvnvmybg Ugtgog — Omyjug)

Криптосистема Накаша — Штерна (англ. Naccache — Stern cryptosystem) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи дискретного логарифмирования. В отличие от RSA, гомоморфен по сложению и вычитанию, а не по умножению➤.

Разработана Давидом Накашем^[англ.] и Жаком Штерном^[англ.] в 1998 году^[1] в двух версиях: детерминированный^[англ.] и вероятностный. Является усовершенствованием схемы Бенало^[2] — авторы смогли построить вероятностную гомоморфную криптосистему с семантической стойкостью и значительно уменьшить отношение между размером шифротекста и размером открытого текста➤.

Сравнение с RSA

Основное сходство с RSA — использование RSA чисел^[1]➤.

Среди различий:

использование разных односторонних функций с потайным входом^[1]: этот момент имеет большой теоретический интерес, потому что, по их мнению, на данный момент существует только небольшое разнообразие односторонних функций с потайным входом, а это напрямую влияет на скорость создания новых криптосистем с открытым ключом^[1];
стойкость алгоритма не связана напрямую со стойкостью алгоритма шифрования криптосистемы RSA: стойкость RSA связана со сложностью задачи факторизации целых чисел, а стойкость криптосистемы Накаша — Штерна — с сложностью задачи дискретного логарифмирования^[3]➤;
криптосистема RSA гомоморфна по умножению, а криптосистема Накаша — Штерна — по сложению^[1]➤.

Детерминированный вариант

Детерминированный вариант криптосистемы Накаша — Штерна может быть описан следующим образом: пусть $\sigma$ — B-гладкое (B мало — обычно это 10-битное число), нечетное, свободное от квадратов число и пусть $n=pq$ — RSA число (Обычно полагают, $n$ — это как минимум 768-битное число), такое что $\sigma$ делит $\phi (n)$ и оно взаимно просто с $\phi (n)/\sigma$ , где $\phi (n)$ — это функция Эйлера. Далее, пусть $g\in \mathbb {Z} /n\mathbb {Z}$ порядка $\phi (n)/4$ . Тогда тройка чисел $p,\ q,\ \sigma$ формирует закрытый ключ. Сообщение $m$ , меньшее чем $\sigma$ , шифруется как $g^{m}mod\ n$ . Расшифрование основано на использовании простых делителей числа $\sigma$ ^[1].

Генерация ключа

Выбрать $k$ «маленьких простых чисел» $p_{1},...,p_{k}$ где $k$ — четное. Здесь фраза «маленькие простые числа» означает, что берутся или первые из простых чисел(1, 3, 5, …) или генерируются каким-либо другим способом, кроме как использования алгоритмов генерации больших простых чисел.
Пусть $u=\prod _{i=1}^{k/2}p_{i}$ , $\upsilon =\prod _{i=k/2+1}^{k}p_{i}$ и $\sigma =uv=\prod _{i=1}^{k}p_{i}$
Выбрать 2 «больших простых числа» $a,\ b$ , таких, что $p=2au+1$ , $q=2b\upsilon +1$ — простые. Здесь фраза «большие простые числа» использована в том смысле, в каком её использует в алгоритмах генерации больших простых чисел.
Пусть $n=pq$ . В литературе число $n$ — произведение «больших простых чисел» — называют RSA число.
Выбрать случайным образом число $g\ mod\ n$ , такое что у $g$ порядок $\phi (n)/4$

Тогда открытый ключ формирует тройка чисел $\sigma ,\ n,\ g$ . А закрытый — $p,\ q$ ^[1]

С ростом числа $n$ генерация ключа становится очень затратной по времени операцией, потому что число a должно быть в подходящем диапазоне и, кроме того, удовлетворять тестам на простоту вместе с числом $p=2au+1$ . Для обхода этого затруднения, авторы предлагают сначала сгенерировать простые числа $a,\ b,\ u,\upsilon$ и затем, подбирая вспомогательные простые числа $p',q'$ , достичь равенства $p=2aup'+1$ и $q=2b\upsilon q'+1$ , где $p,\ q$ будут простыми^[1].

Шифрование

Шифрование состоит из единственной операции возведения в степень по модулю $n$ : сообщение $m$ , меньшее $\sigma$ , шифруется как $E(m)=g^{m}mod\ n$ . Причём здесь никак не используются $\sigma$ .^[1]

Расшифрование

Расшифрование основано на китайской теореме об остатках. Пусть $p_{i},\ 1\leqslant i\leqslant k$ — простые делители $\sigma$ . Алгоритм вычисляет $m_{i}=m\ mod\ p_{i}$ и затем дешифрует сообщение m с помощью китайской теоремы об остатках^[1].

Чтобы найти m_i при заданном шифротексте $c=g^{m}mod\ n$ , алгоритм вычисляет $c_{i}\ =\ c^{\phi (n)/p_{i}}\ mod\ n$ , что в точности равно $g^{m_{i}\phi (n)/p_{i}}\ mod\ n$ . Это следует из следующих вычислений — здесь $y_{i}=(m-m_{i})/p_{i}$ : ${\textstyle c_{i}\ =\ c^{\phi (n)/p_{i}}\ =\ g^{m\phi (n)/p_{i}}\ =\ g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\ =\ g^{m_{i}\phi (n)/p_{i}}g^{y_{i}\phi (n)}\ =\ g^{m_{i}\phi (n)/p_{i}}\ mod\ n}$ . Сравнивая этот результат со всеми возможными степенями $g^{j\phi (n)/p_{i}}$ , можно найти значение $m_{i}$ . Более формально функция расшифрования представлена псевдокодом^[1]:

for $i$ = 1 to $k$ :
$c_{i}\ =\ c^{\phi (n)/p_{i}}\ mod\ n$
for $j$ = 0 to $p_{i}$ — 1:

if $c_{i}==g^{j\phi (n)/p_{i}}\ mod\ n$ :

$m_{i}=j$

$x$ = ChineseReminder( $m_{i}$ , $p_{i}$ )

Пример

Генерация ключа для $k=6$ :

p=21211=2*101*3*5*7+1

q=928643=2*191*11*13*17+1

n=21211*928643=19697446673

g=131

\sigma =3*5*7*11*13*17

p_{1}=3,...,p_{6}=17

$\{i,j\}$ содержит $g^{j\phi (n)/p_{i}}\ mod\ n\ mod\ 10000$
	i=1	i=2	i=3	i=4	i=5	i=6
j = 0	1	1	1	1	1	1
j = 1	1966	6544	1967	6273	6043	372
j = 2	9560	3339	4968	7876	4792	7757
j = 3		9400	1765	8720	262	3397
j = 4			6488	8651	6291	702
j = 5			2782	4691	677	4586
j = 6				9489	1890	8135
j = 7				8537	6878	3902
j = 8				2312	2571	5930
j = 9				7701	7180	6399
j = 10					8291	9771
j = 11					678	9771
j = 12						609
j = 13						7337
j = 14						6892
j = 15						3370
j = 16						3489

Шифрование $m=202$ :

c=g^{m}mod\ n=131202\ mod\ 19697446673

.

Расшифрование:

c^{\phi (n)/p_{1}}\ mod\ nmod\ 10000=1996

c^{\phi (n)/p_{2}}\ mod\ n\ mod\ 10000=3339

c^{\phi (n)/p_{3}}\ mod\ n\ mod\ 10000=2782

c^{\phi (n)/p_{4}}\ mod\ n\ mod\ 10000=7994

c^{\phi (n)/p_{5}}\ mod\ n\ mod\ 10000=1890

c^{\phi (n)/\ p_{6}}\ mod\ n\ mod\ 10000=3370

Далее, используя таблицу:

m_{1}=m\ mod\ 3=table(1996)=1

m_{2}=m\ mod\ 5=table(3339)=2

m_{3}=m\ mod\ 7=table(2782)=1996

m_{4}=m\ mod\ 11=table(7994)=4

m_{5}=m\ mod\ 13=table(1890)=7

m_{6}=m\ mod\ 17=table(3370)=15

и по китайской теореме об остатках^[1]:

m=202

Вероятностный вариант

Вероятностный вариант криптосистемы — это усовершенствование предшествующих вероятностных криптосистем (например, криптосистемы Бенало).

Предшествующие криптосистемы имели очень существенный недостаток: чтобы зашифровать маленький набор данных $S$ (например, голоса 0, 1 в электронном голосовании), детерминированные криптосистемы, например, RSA, не подходят^[1], потому что для расшифровки будет достаточно сравнить шифротекст с зашифрованными элемента набора $S$ . Это свойство криптосистем — невозможность различить шифротексты различных элементов набора S, называется семантической стойкостью^[4]. Но при сочетании гомомофрности и семантической стойкости, предшествующие криптосистемы начинали генерировать около килобайта шифротекста, чтобы зашифровать открытый текст в несколько бит^[1]. В криптосистеме Накаша — Штерна, кроме того, что есть свойства гомоморфности, семантической стойкости, отношение между размером шифротекста и размером открытого текста в точности равно $n/\sigma$ . Авторы утверждают, что безопасно взять $\sigma /n<{\frac {1}{4}}$ ^[1].

Генерация ключа

Выбрать $k$ «маленьких простых чисел» $p_{1},...,p_{k}$ где $k$ — четное. Здесь фраза «маленькие простые числа» означает, что берутся или первые из простых чисел(1, 3, 5, …) или генерируются каким-либо другим способом, кроме как использования алгоритмов генерации больших простых чисел.
Пусть $u=\prod _{i=1}^{k/2}p_{i}$ , $\upsilon =\prod _{i=k/2+1}^{k}p_{i}$ и $\sigma =uv=\prod _{i=1}^{k}p_{i}$
Выбрать 2 «больших простых числа» $a,\ b$ , таких, что $p=2au+1$ , $q=2b\upsilon +1$ — простые. Здесь фраза «большие простые числа» использована в том смысле, в каком её использует в алгоритмах генерации больших простых чисел.
Пусть $n=pq$ — RSA число.
Выбрать случайным образом число $g\ mod\ n$ , такое что у $g$ порядок $\phi (n)/4$

Тогда открытый ключ формирует тройка чисел $\sigma ,\ n,\ g$ . А закрытый — $p,\ q$ ^[1]

Шифрование

Шифрование в вероятностном варианте очень похоже на шифрование в детерминированном варианте: пусть $x$ — случайным образом выбранное положительное число из кольца вычетов по модулю $n$ : $x\in \mathbb {Z} /n\mathbb {Z}$ . Тогда алгоритм записывается в виде $E(m)=x^{\sigma }g^{m}mod\ n$ ^[1]

Расшифрование

Расшифрование в вероятностном варианте остаётся без изменений в сравнении с детерминированным вариантом Эффект от умножение на $x^{\sigma }$ при шифровании учитывается, когда мы возводим шифротекст в степени $\phi (n)/p_{i}$ . Проделаем вычисления, чтобы убедиться в этом.

Пусть $p_{i},1\leqslant i\leqslant k$ — простые делители $\sigma$ . Алгоритм вычисляет $m_{i}=m\ mod\ p_{i}$ и затем дешифрует сообщение $m$ с помощью китайской теоремы об остатках.

Чтобы найти $m_{i}$ , при заданном шифротексте $c=x^{\sigma }g^{m}mod\ n$ , алгоритм вычисляет $c_{i}\ =\ c^{\phi (n)/p_{i}}\ mod\ n$ , что в точности равно $g^{m_{i}\phi (n)/p_{i}}\ mod\ n$ . Это следует из следующих вычислений:

{\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}

Сравнивая этот результат со всеми возможными степенями $g^{j\phi (n)/p_{i}}$ , можно найти значение $m_{i}$ ^[1]

Применение

В большинстве областей применения криптосистемы Накаша — Штерна используется свойство гомоморфности этой криптосистемы по сложению и вычитанию^[5]^[2]. Например, если у клиента в банке на счету $m$ и он хочет снять небольшую сумму $u$ , баланс $m$ хранится в зашифрованном виде $E(m)$ , и представитель банка, выполняя операцию снятия со счета клиента суммы $u$ , не имеет доступа к расшифрованию данных счета. С помощью криптосистема Накаша — Штерна предлагается простое решение этой проблемы через операцию $E(m)/E(u)\ mod\ n$ — это значение нового баланса на счету в зашифрованном виде: $m-u$ . Более формально: пусть $E(m_{1})=g^{m_{1}}mod\ n,\ E(m_{2})=g^{m_{2}}mod\ n$ — алгоритмы шифрования счетов $m_{1},\ m_{2}$ , тогда счет, равный сумме $m_{1}$ и $m_{2}$ вычисляется по следующей формуле: $E(m_{1})E(m_{2})=g^{m_{1}}g^{m_{2}}mod\ n=g^{m_{1}+m_{2}}mod\ n$ ^[1].

Также протокол может применяться для повышения безопасности облачных вычислений. Например, если в облаке $S$ содержится множество пользователей (клиентов) $p_{1},...,p_{i},...,p_{l}$ , у пользователя $p_{i}$ имеются конфиденциальные данные $x_{i}$ , хранящиеся в облаке, то пользователь $p_{i}$ может обратиться к облаку с запросом на вычисление значения некоторой функции $F$ , зависящей от конфиденциальных данных. Запрос должен состоять из описания функции $F$ , идентификатора пользователя и его открытого ключа $pk_{i}$ . Облако должно проверить полномочия пользователя $p_{i}$ на вычисление $F(x_{i})$ . Такая проверка может быть реализована с помощью стандартной процедуры электронной цифровой подписи. Если пользователь подтвердил свои права на вычисление функции $F$ , то облако должно вычислить значение $E(pk_{i},\ F(x_{i}))$ и отправить его пользователю. В качестве $E$ можно взять функцию шифрования любой гомоморфной криптосистемы с открытым ключом, какой, к примеру, является криптосистема Накаше — Штерна. Пользователь, который размещает конфиденциальные данные и даёт запрос на вычисление функции $F$ , не доверяет облаку, и должен принимать соответствующие меры и предъявлять требования по обеспечению их безопасности. Очевидно, что было бы гораздо безопаснее передавать данные в таком виде, чтобы во время операций, которые производятся над ними, никоим образом не распространялась информация об этих данных. Поэтому, во-первых, данные необходимо шифровать, причём они должны поступать на сервер уже в шифрованном виде. Это означает, что шифрование должно осуществляться ещё пользователем. Во-вторых, необходимо обрабатывать эти данные без расшифровки, так как для передачи и хранения секретного ключа необходимо соблюдение определённых процедур, особенно сложных, если информация обрабатывается в недоверенной среде. Криптосистемы с гомоморфным шифрованием как раз помогают решить эти проблемы^[6]^[2].

Ещё одним применением является обфускация для защиты программных продуктов. Впервые о применении обфускации в криптографии было упомянуто в работе Диффи и Хеллмана^[7]. В ней, для построения асимметричной криптосистемы, предложено использовать сложность задачи, заключающейся в анализе программ на низкоуровневом языке программирования (ассемблере, байт-коде). Основной целью обфускации является затруднение понимания функционирования программы. Поскольку все традиционные компьютерные архитектуры используют двоичные строки, применяя полностью гомоморфное шифрование над битами, можно вычислить любую функцию. Следовательно, можно гомоморфно зашифровать целиком всю программу так, что она сохранит свою функциональность^[8].

Криптосистема может быть применена в системах электронного голосования. Например, если есть $n$ кандидатов и комиссия, которая обладает этой криптосистемой, распространяет среди участников бюллетень-вектор $(p_{1},...,\ p_{n})$ , где $p_{i}$ — фамилия $i$ -го кандидата, и у каждого участника есть открытый ключ $pk$ , и каждый избиратель возвращает в комиссию вектор $(\nu _{1},...,\nu _{n})$ , где $\nu _{i}\in \{0,1\}$ — вектор предпочтений, то победителем выбором считается тот кандидат, который набрал в сумме больше всех голосов — это число — сумма голосов — подсчитывается над шифрованными векторами избирателей. Это становится возможным благодаря гомоморфности. Польза от такого подхода в том, что нет необходимости расшифровывать данные избирателей для подсчёта голосов — повышается безопасность выборов для избирателей^[9].

Область водяных знаков^[10]. Гомоморфность криптосистемы позволяет наносить водяной знак на зашифрованные данные^[11].

Как и другие гомоморфные системы, криптосистема также может применяться, когда появляется необходимость подтвердить владение какой-либо информации, которая поддаётся такой проверке без раскрытия самой информации (доказательство с нулевым разглашением)^[12]^[13].

Атаки

Широко известных атак на эту криптосистему не задокументировано. Сами авторы поощряют работу над взломом криптосистемы. В оригинальной статье предлагаются^[1] 768 долларов тому, кто расшифрует шифротекст $c$ и опубликует метод криптоанализа:

$c$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449
bdd00866597e61af4fb0d939283b04d3bb73f91f
0d9d61eb0014690e567ab89aa8df4a9164cd4c63
6df80806c7cdceda5cfda97bf7c42cc702512a49
dd196c8746c0e2f36ca2aee21d4a36a₁₆

$g$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517
6d731b4897875d26a9e244415e111479050894ba7
c532ada1903c63a84ef7edc29c208a8ddd3fb5f7
d43727b730f20d8e12c17cd5cf9ab4358147cb62
a9fb887bf15204e444ba6ade6132743₁₆

$n$ = 1459b9617b8a9df6bd54341307f1256dafa241bd
65b96ed14078e80dc6116001b83c5f88c7bbcb0b
db237daac2e76df5b415d089baa0fd078516e60e
2cdda7c26b858777604c5fbd19f0711bc75ce00a
5c37e2790b0d9d0ff9625c5ab9c7511d₁₆

Здесь $k=30$ ( $p_{i}$ — формируются из первых $i$ простых чисел, кроме 2)^[1].

Примечания

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ ¹⁹ ²⁰ ²¹ Jacques, Stern. A New Public Key Cryptosystem Based on Higher Residues (англ.) // ACM. — 1998. — P. 59–66. Архивировано 6 декабря 2006 года.
↑ ¹ ² ³ А. И. Трубей. Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) (рус.) // Информатика. — 2015. — Январь. Архивировано 26 ноября 2018 года.
↑ Thomas W. Cusick. A comparison of RSA and the Naccache-Stern public-key cryptosystem (англ.) // Security Protocols. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. — P. 111–116. — ISBN 9783540624943, 9783540680475. — doi:10.1007/3-540-62494-5_10. Архивировано 2 декабря 2018 года.
↑ S. Goldwasser, S. Micali. Probabilistic Encryption (англ.) // JCSS. — 1984. — Апрель. — P. 270—299.
↑ A Brief Overview of Homomorphic Cryptosystem and Their Applications // International Journal of Computer Applications. — 2015.
↑ R. L. Rivest, L. Adleman, M. L. Dertouzos. On data banks and privacy homomorphisms // Foundations of secure computation.
↑ W. Diffie, M. Hellman. New directions in cryptography // IEEE Trans. Inf. Theory.
↑ J. Alwen [et al.] On the relationship between functional encryption, obfuscation, and fully homomorphic encryption // Cryptography and Coding – 14th IMA Intern. Conf., IMACC-2013..
↑ J.D. Cohen Benaloh. Verifiable Secret-Ballot Elections (англ.) // Yale University : Ph-D thesis. — 1988.
↑ B. Pfitzmann, M. Schunter. Assymetric fingerprinting (англ.) // Spinger-Verlag. — 1996. — P. 84—95.
↑ Constructing Secure Content-Dependent Watermarking Scheme using Homomorphic Encryption.
↑ O. Goldreich, S. Micali, A. Wigderson. Proofs that Yield Nothing But Their Validity and a Methodology of Cryptographic Protocol Design (англ.). — 1986. — P. 174—187.
↑ G. Brassard, D. Chaum, C. Crépeau. Minimum Disclousure Proofs of Knowledge // JCSS. — 1988. Архивировано 27 сентября 2011 года.

[:1-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ ¹⁰ ¹¹ ¹² ¹³ ¹⁴ ¹⁵ ¹⁶ ¹⁷ ¹⁸ ¹⁹ ²⁰ ²¹ Jacques, Stern. A New Public Key Cryptosystem Based on Higher Residues (англ.) // ACM. — 1998. — P. 59–66. Архивировано 6 декабря 2006 года.

[:0-2] ¹ ² ³ А. И. Трубей. Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) (рус.) // Информатика. — 2015. — Январь. Архивировано 26 ноября 2018 года.

[3] Thomas W. Cusick. A comparison of RSA and the Naccache-Stern public-key cryptosystem (англ.) // Security Protocols. — Berlin, Heidelberg: Springer Berlin Heidelberg, 1997. — P. 111–116. — ISBN 9783540624943, 9783540680475. — doi:10.1007/3-540-62494-5_10. Архивировано 2 декабря 2018 года.

[4] S. Goldwasser, S. Micali. Probabilistic Encryption (англ.) // JCSS. — 1984. — Апрель. — P. 270—299.

[5] A Brief Overview of Homomorphic Cryptosystem and Their Applications // International Journal of Computer Applications. — 2015.

[6] R. L. Rivest, L. Adleman, M. L. Dertouzos. On data banks and privacy homomorphisms // Foundations of secure computation.

[7] W. Diffie, M. Hellman. New directions in cryptography // IEEE Trans. Inf. Theory.

[8] J. Alwen [et al.] On the relationship between functional encryption, obfuscation, and fully homomorphic encryption // Cryptography and Coding – 14th IMA Intern. Conf., IMACC-2013..

[9] J.D. Cohen Benaloh. Verifiable Secret-Ballot Elections (англ.) // Yale University : Ph-D thesis. — 1988.

[10] B. Pfitzmann, M. Schunter. Assymetric fingerprinting (англ.) // Spinger-Verlag. — 1996. — P. 84—95.

[11] Constructing Secure Content-Dependent Watermarking Scheme using Homomorphic Encryption.

[12] O. Goldreich, S. Micali, A. Wigderson. Proofs that Yield Nothing But Their Validity and a Methodology of Cryptographic Protocol Design (англ.). — 1986. — P. 174—187.

[13] G. Brassard, D. Chaum, C. Crépeau. Minimum Disclousure Proofs of Knowledge // JCSS. — 1988. Архивировано 27 сентября 2011 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]