stify"> j (а) j (b), (3.1.6)
ЯКЩО а і b - взаємно Прості, того
j (р r ) = р r-1 (р-1), де р - просте, r - натуральне. (3.1.7)
З (3.1.3-6) бачмо, что j (m) візначається просто, ЯКЩО ми маємо розкладення m на Прості множнікі. Далі, візначаємо d, таке, что:
е Вє 1 (mоd j (m)), 1? d
(так як е и j (m) взаємопрості, то таке d існує и єдине). Далі, за теоремою Ейлера, "х, взаємопростого з j (m), віконується хj (m) Вє 1 (mоd m), тому
аd Вє хdе Вє х (mоd m). (3. 1.9)
Отже, вімагаючі ще, щоб (а, m) = +1, отрімуємо єдиний розвязок конгруенції (3.1.2) у вігляді х = аd (mоd m).
Зауважімо, что Вимога (а, m) = 1 цієї статті не обовязкова у випадка, коли m є добутком різніх простих множніків. Тому творці RSА запропонувалі використовуват таке m, что:
= РQ, де р, q - й достатньо Великі Прості числа, тоді, згідно (3.1. 5,6):
j (m) = j (РQ) = j (р) j (q) = (р-1) (q-1),
а Умова (3.1.3) набуває вигляду:
НСД (е, р-1) = НСД (е, q-1) = 1. (3. 1.10)
Пара Р = (е, m) є відкрітім, тоб відомімі всім Користувач, ключем системи. Будь-хто може посілаті організатору ПОВІДОМЛЕННЯ, шіфровані функцією f, Вказаною в (3.1.1), Які організатор читає з помощью закритого ключа S = (d, m), Вибраного ЗА УМОВИ (3.1.8). p> Если припусти, что супротивник відомі Відкриті числа та принцип шифрування, то при m невелікої розмірності (Наприклад, 8 розрядів) й достатньо просто найти УСІ Прості дільнікі числа m, перебрав ВСІ числа від 1 до € m. А потім, Обчислено j (m), знайте ключ d з умови (3.1.8). Прото Із зростанням m кількість простих чисел, Які нужно перевіріті асимптотично дорівнює 2m (ln m) -1. Так, для m, записаного сотнею Десяткова знаків, $ не менше 4 * 1042 простих чисел, что могут буті его дільнікамі. Найшвідші з відоміх алгорітмів Розкладу числа на Прості множнікі не дають результату за Прийнятних годину - прінаймні, за умів Використання одного компютера. Тому ВСІ вдалі атаки на систему RSА були здійснені за помощью розподілу розрахунків. p> Для ілюстрації свого методу творці RSА зашіфрувалі Деяк ПОВІДОМЛЕННЯ функцією (3.1), взявши в якості m 129-значного числа. Отримай кріптограма булу опублікована разом з відкрітімі параметрами шифрування, первом, хто дешіфрує ее, булу обіцяна премія в 100 $. Було такоже додатково вказано, что m є добутком двох простих чисел розрядністю 64 та 65 знаків, протікання минуло 17 років, дере чем шифр Було розкрити. Чи не ВРАХОВУЮЧИ підготовку,...
