WikiSort.ru - Не сортированное

Сходства

• Использование RSA чисел^{[1] [см. «Описание детерминированного варианта криптосистемы»]}

Различия

• Использование разных односторонних функций с потайным входом. Как подчеркивают авторы^[1], этот пункт имеет большой теоретический интерес, потому что, по их мнению, на данный момент существует только небольшое разнообразие односторонних функций с потайным входом, а это напрямую влияет на скорость создания новых криптосистем с открытым ключом.^[1]
• Стойкость этого алгоритма не связана напрямую со стойкостью алгоритма шифрования криптосистемы RSA. А именно, стойкость RSA связана со сложностью задачи факторизации целых чисел, а стойкость криптосистемы Накаша — Штерна — с сложностью задачи дискретного логарифмирования^{[4] [см. «Описание детерминированного варианта криптосистемы»]}
• Криптосистема RSA гомоморфна по умножению, а криптосистема Накаша — Штерна — по сложению^{[1][см. «Применение»]}

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

• Выбрать ${\displaystyle k}$ "маленьких простых чисел" ${\displaystyle p_{1},...,p_{k}}$ где ${\displaystyle k}$  — четное. Здесь фраза "маленькие простые числа" означает, что берутся или первые из простых чисел(1, 3, 5, ...) или генерируются каким-либо другим способом, кроме как использования алгоритмов генерации больших простых чисел.
• Пусть ${\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}}$
• Выбрать 2 "больших простых числа" ${\displaystyle a,\ b}$ , таких, что ${\displaystyle p=2au+1}$ , ${\displaystyle q=2b\upsilon +1}$  — простые. Здесь фраза "большие простые числа" использована в том смысле, в каком ее использует в алгоритмах генерации больших простых чисел.
• Пусть ${\displaystyle n=pq}$ . В литературе число ${\displaystyle n}$ — произведение "больших простых чисел" — называют RSA число.
• Выбрать случайным образом число ${\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\leq i\leq 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}$

и по китайской теореме об остатках получаем: ${\displaystyle m=202}$ ^[1]

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

• Выбрать ${\displaystyle k}$ "маленьких простых чисел" ${\displaystyle p_{1},...,p_{k}}$ где ${\displaystyle k}$  — четное. Здесь фраза "маленькие простые числа" означает, что берутся или первые из простых чисел(1, 3, 5, ...) или генерируются каким-либо другим способом, кроме как использования алгоритмов генерации больших простых чисел.
• Пусть ${\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}}$
• Выбрать 2 "больших простых числа" ${\displaystyle a,\ b}$ , таких, что ${\displaystyle p=2au+1}$ , ${\displaystyle q=2b\upsilon +1}$  — простые. Здесь фраза "большие простые числа" использована в том смысле, в каком ее использует в алгоритмах генерации больших простых чисел.
• Пусть ${\displaystyle n=pq}$  — RSA число.
• Выбрать случайным образом число ${\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\leq i\leq 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]