LUC - Криптосистема с открытым ключом.

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Xenomorf
Сообщения: 1
Зарегистрирован: 20 ноя 2015, 09:03

20 ноя 2015, 09:05

Всем доброго времени. Разрабатываю алгоритм шифрования LUC. Описание взял из Википедии, так как в ней наиболее полное и относительно понятное объяснение. Не буду приводить прямые ссылки, так как не знаю правомерно ли это, лучше приведу кусок статьи.

Сначала выбираются два простых числа p и q.
Вычисляется их произведение N = p * q
Выбирается число e, взаимнопростое с числом (p-1)(q+1)(p+1)(q+1): gcd[(p-1) * (q-1) * (p+1) * (q+1),e ] = 1
Вычисляется D: D = P^2-4, где P — наше сообщение
Вычисляются следующие символы Лежандра L(D \ p) и L(D \ q)
Находится наименьшее общее кратное S(N) = lcm[(p - L(D \ p)),(q - L(D \ q)) ]
Вычисляется d d = e^-1 mod S(N)
открытый ключ: KU = (e,N)
закрытый ключ: KR = (d,N)



В качестве gsd здесь упомянута функция определения взаимной простоты двух чисел, а lnc - нахождение наименьшего общего кратного. Вопрос в последней строчке. Что значит "е в минус первой степени"? Согласно элементарной математике, любо число в минус первой - это единица деленная на любое число. Учитывая тот факт, что е получается числом натуральным(ниже приведу конкретный пример оттуда же), то его минус первая степень будет дробной, тогда как в качестве операндов Mod могут фигурировать только целые числа. А вот обещанный пример:

Выбираем два простых числа: p = 1949, q = 2089
Вычисляем N: N = p * q = 4071461
Вычисляем открытый ключ e из уравнения gcd[(p-1) * (p+1) * (q-1) * (q+1), e ] = 1 :gcd[1948 * 2088 * 1950 & 2090, e ] = 1 => e = 1103
Шифровать будем следующее сообщение P = 11111, далее вычисляем символ Лежандра L(D \ p) ; параметр D^2 = P^2 - 4 = 123454317 Используя критерий Эйлера находим: L(D \ p) = -1 L(D \ q)= -1
Теперь вычисляем функцию S(N): S(N) = lcm[(1949 + 1),(2089 + 1)] = 407550
Закрытый ключ: d = e^-1 mod 407550 = 24017



Как раз на последней строке и остановился. Три вывода: либо я не правильно понимаю смысл "е в минус первой", либо я не въезжаю как работает mod, и почему он дает 24017, когда должен давать "е в минус первой ~ 0,000906618313689936536718042", поскольку она очевидно меньше чем 407550, либо в Википедии написана чушь. Мониторинг интернета по указанной теме не дал результатов. Большая просьба: прояснить ситуацию.
Аватара пользователя
Сионист
Сообщения: 1077
Зарегистрирован: 31 мар 2014, 06:18

04 апр 2017, 06:35

В тексте (p-1)(q+1)(p+1)(q+1), а в формуле (p-1)(q-1)(p+1)(q+1), то есть в статье явно есть ошибка. Поищите другие описания, сопоставьте.
Писать можно на чём угодно, но зачем же так себя ограничивать? Пиши на c.
irma.oloko
Сообщения: 0
Зарегистрирован: 02 май 2018, 10:52

02 май 2018, 10:53

Все лучшие проститутки Москвы вы найдете
на нашем сайте, а еще вы сможете подобрать себе индивидуалку по вашим
сексуальным предпочтениям.
Ответить