Криптосистема Накаша — Штерна

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

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

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

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

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

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

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

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

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

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

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

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

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

for ${\displaystyle j}$ = 0 to ${\displaystyle p_{i}}$ — 1:

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

${\displaystyle m_{i}=j}$

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

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

${\displaystyle p=21211=2*101*3*5*7+1}$

${\displaystyle q=928643=2*191*11*13*17+1}$

${\displaystyle n=21211*928643=19697446673}$

${\displaystyle g=131}$

${\displaystyle \sigma =3*5*7*11*13*17}$

${\displaystyle p_{1}=3,...,p_{6}=17}$

${\displaystyle \{i,j\}}$содержит ${\displaystyle 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

Шифрование ${\displaystyle m=202}$:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle m=202}$

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

${\displaystyle c}$ = 13370fe62d81fde356d1842fd7e5fc1ae5b9b449

bdd00866597e61af4fb0d939283b04d3bb73f91f

0d9d61eb0014690e567ab89aa8df4a9164cd4c63

6df80806c7cdceda5cfda97bf7c42cc702512a49

dd196c8746c0e2f36ca2aee21d4a36a₁₆

${\displaystyle g}$ = 0b9cf6a789959ed4f36b701a5065154f7f4f1517

6d731b4897875d26a9e244415e111479050894ba7

c532ada1903c63a84ef7edc29c208a8ddd3fb5f7

d43727b730f20d8e12c17cd5cf9ab4358147cb62

a9fb887bf15204e444ba6ade6132743₁₆

${\displaystyle n}$ = 1459b9617b8a9df6bd54341307f1256dafa241bd

65b96ed14078e80dc6116001b83c5f88c7bbcb0b

db237daac2e76df5b415d089baa0fd078516e60e

2cdda7c26b858777604c5fbd19f0711bc75ce00a

5c37e2790b0d9d0ff9625c5ab9c7511d₁₆

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