| Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум на Исходниках.RU > Алгоритмы > мат.модель шифра Шамира |
| Автор: FasterHarder 22.05.21, 10:57 |
| Всем хай! Сходу к делу. Есть пару небольших вопросов по алгоритму "шифр Шамира". Выбирают простое число p (пишут, что побольше желательно, лол, хотя в примерах дают до 50) Затем надо выбрать таких 2 числа (например, обозначим их a, b), чтобы они были обратными друг другу по модулю (p - 1). То есть математически имеем: a * b mod (p - 1) = 1 Вот тут кое-что непонятно. Например, по условию известно, что p = 17 - это простое число, тут все ок; a = 5. И надо рассчитать b. То есть a * b mod (p - 1) = (5 * b) mod 16 = 1 Из теории арифметики известно, что: делимое : делитель = частное (остаток) ---> за остаток отвечает как раз таки оператор mod Перепишем так: частное * делитель + остаток = делимое делимое = 5*b делитель - 16 частное - НЕИЗВЕСТНО (пусть x) остаток = 1 Итого: 16 * x + 1 = 5 * b В уравнении 2 неизвестных (b, x). Как бы это, того, не решить стандартным способом) Вроде как известно, что b, x = N (натуральные числа) Перебирать остается подстановкой значения х??? Т е однозначно нельзя получить b, зная на входе p и а? А может быть вариант, когда несколько пар значений {b, x} удовлетворяют уравнению? p.s. возможно, я здесь оч.жестко прогнал и все гораздо проще), но, построив мат. модель получилось такое А сам по себе алгоритм несложен, зная p, a, b, a2, b2 там уже по формулам легко можно высчитать x1, x2, x3, x4... спс за внимание |
| Автор: scrambrella 22.05.21, 19:46 |
| Цитата FasterHarder @ Всем хай! Сходу к делу. Есть пару небольших вопросов по алгоритму "шифр Шамира". По-человечески это называется шифр RSA. Ривест-Шамир-Адлеман. Число ваше ищется по расширенному алгоритму Евклида. |
| Автор: FasterHarder 22.05.21, 21:36 |
| не факт! по РСА есть описание - они чем-то похожи возможно, что РСА усовершенствовал шифр Шамира имхо, это НЕ одно и то же |
| Автор: amk 13.06.21, 08:51 |
| FasterHarder, тебе что, непонятно, как искать обратное по модулю? Если так, смотри расширенный алгоритм Эвклида - он находит не только общий делитель, но и линейную комбинацию заданных чисел, дающий этот общий делитель. Для взаимно простых чисел коэффициенты равны обратным. gcd(a,b) = c (c получается обычным алгоритмом Эыклида) d*a + e*b = c (c. d, e получается расширенным алгоритмом Эвклида) если c = 1, то d*a ≡ 1 (mod b) (d является обратным к a по модулю b) e*b ≡ 1 (mod a) (e является обратным к b по модулю a) если обратное при этом получается отрицательным, надо просто добавлять к нему модуль. |