8. Схема Поллинга-Хеллмана

Данная схема не относится ни к симметричным алгоритмам, ни к схемам с открытым ключом, потому что ключи легко генерируются одни из другого и ключ шифрования и ключ расшифрования нужно хранить в секрете.

С=P^emodN - шифрование

P=C^dmodN -расшифрование

ed≡1mod (какого-либо сложного числа)

n – остается частью закрытого ключа, если мы знаем значение e и n, мы можем вычислить d. Не зная значений e или d нам необходимо вычислить формулу:

e=log_p^cmodN

9. Схема Рабина

Генерация ключа: Как любая асимметричная криптосистема, система Рабина использует и открытый и закрытый ключи. Открытый ключ необходим для шифрования документов и может быть опубликован для всеобщего обозрения. Закрытый ключ должен быть известен только получателям зашифрованных сообщений.

Процесс генерации ключей следующий:

Выбираются два больших простых числа p и q, которые удовлетворяют условию p≡n≡3 (mod 4) . Такой специальный вид простых чисел сильно ускоряет процедуру извлечения корней по модулю р и q.

Тогда n=p*q . n - открытый ключ. Числа p и q - закрытый ключ.

Для шифрования сообщения необходим открытый ключ n. Чтобы расшифровать зашифрованный текст нужны p и q.

Шифрование: Для шифрования используется только открытый ключ n. С помощью его исходный текст преобразовывается в зашифрованный. Для шифрования сообщение разбивается на блоки M<n. Для шифрования сообщения m нужно просто вычислить:

C=m²modn.

Таким образом, шифрование состоит из операции умножения по модулю N, что обеспечивает более высокую скорость шифрования, чем в RSA, даже если в последней выбирают небольшую шифрующую экспоненту.

Расшифрование: получатель знает p,q,n, и C. Вычисляются значения m₁, m₂, m₃ , m₄ .

m₁=C^(p+1)/4 mod p

m₂=(p-C^(p+1)/4 )mod p

m₃=C^(q+1)/4 mod p

m₄=(q-C^(p+1)/4 )mod p

Выбираем целые числа a и b, кот.удов. след. выражению:

a=q(q­^-1mod p)

b=p(p­^-1mod q)

Четырьмя возможными решениями явл. M₁, M₂, M₃, M₄.

M₁=(a_m1 + b_m3) mod n

M₂=(a_m1 + b_m4) mod n

M₃=(a_m2 + a_m3) mod n

M₄=(a_m2 + b_m4) mod n

Один из этих корней является истинным открытым текстом M . Если сообщение представляет собой случайный поток бит, то определить правильное Mii=1,4 практически невозможно. Для этого к сообщению рекомендуется добавлять известный заголовок.

10.Схема Вильямса

По схеме Вильямса необходимо вычислить p и q.

p≡3mod 8

q≡7mod 8

Также используется небольшое целое S, для кот.символ Якоби I(S,N)=-1

Значения S и N опубликовываются и вычисляется секретный ключ К по след.формуле.

К=1/2(1/4*(p-1)(q-1)+1)

Для шифрования сообщения М вычисляется С₁ такое что I(М,N)=(-1)^С1

Вычисляется М^’ =(S^C1*M) modn

Вычисляется C=( М^’)²modN

C₂=М^’mod 2

Зашифрованный текст представляет тройку сообщений (С, С₂,С₂).

Для расшифрования С получатель вычисляет значение М^’’ по формуле:

С^k≡± М^’’modN

Правильный знак определяет параметр С₂.

М=(S^C1+(-1)^C2) М^’’ mod N

В последствии Вильямс улучшил данную схему; вместо возведения в квадрат открытого текста сообщение возводить в третью степень, большие числа p и q должны быть ≡1 mod.