Протоколы Internet


Системы шифрования - часть 7


Следствие 4.

Пусть a соответствует требованиям теоремы 2, тогда ap-1 є p1.

Следствие 5. Для любого b № 0, bp-1 є p1.

Следствие 6. Если x є (p-1)y, тогда bx є pby

Лемма

Пусть b № 0, d наименьшее положительное число, такое что bd єp1.

Тогда для любого с>0 c bc єp1 d

делит c без остатка. В частности для следствия 5, d делит p-1 без остатка.

Согласно теореме 2, если p простое число, существует такое a, при котором равенство ax є pb имеет решение для любого b№ 0. Такое значение a называется примитивным корнем p, а x называется дискретным логарифмом b. Получение b при заданных a и x относительно просто, определение же x по a и b заметно сложнее. Многие современные системы шифрования основываются на факте, что никаких эффективных путей вычисления дискретных логарифмов не найдено. Никакого эффективного метода определения примитивных корней также неизвестно. Однако часто возможно найти примитивные корни в некоторых специальных случаях. Возьмем p=1223. p-1=2*13*47. Согласно лемме, если a не примитивный корень, тогда мы либо имеем a26, a94 или
a611 є 12231. a=2 и a=3 не годятся, но a=5 соответствует всем трем условиям, таким образом, это значение является примитивным корнем. Мы могли бы сказать, что a=4 не может быть признано примитивным корнем без проверки.

Легко показать, что если a примитивный корень, ax примитивный корень в том и только том случае, если (x,p-1)=1. В этом примере это означает, что число примитивных корней равно

1222*(1/2)*(12/13)*(46/47)=552

Таким образом, если мы выберем а произвольно, вероятность того, что это будет примитивный корень равна ~.45. Выбирая а наугад и тестируя, можно сравнительно быстро найти примитивный корень.

Наиболее современные системы шифрования используют асимметричные алгоритмы с открытым и секретным ключами, где нет проблемы безопасной транспортировки ключа. К числу таких систем относится алгоритм rsa (rivest-shamir-adleman - разработчики этой системы – Рональд Ривест, Ади Шамир и Леонард Адлеман, 1977 год), базирующийся на разложение больших чисел на множители.




Начало  Назад  Вперед