Xenomorf » 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, либо в Википедии написана чушь. Мониторинг интернета по указанной теме не дал результатов. Большая просьба: прояснить ситуацию.
Всем доброго времени. Разрабатываю алгоритм шифрования 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, либо в Википедии написана чушь. Мониторинг интернета по указанной теме не дал результатов. Большая просьба: прояснить ситуацию.