Реферат на тему:
Схема шифрування Рабіна з відкритим ключем
Генерація ключів для схеми шифрування Рабіна
1. Згенерувати два великих простих числа p та q приблизно однакової
довжини;
2. Обчислити n = p * q;
3. Відкритим ключем А є n, закритим ключем А є p та q.
Схема шифрування Рабіна B шифрує повідомлення M для A, яке потім A
дешифрує.
Кодування інформації Дії B:
1. Отримати відкритий ключ n від А;
2. Представити повідомлення m як число у проміжку {0, …, n-1};
3. Обчислити C = M2 mod n;
4. Надіслати зашифроване повідомлення C до А.
Декодування інформації Дії A:
1. Обчислити квадратні корені із числа C. Нехай ними будуть m1, m2, m3,
m4. (Якщо НСД(m, n) ??1, то рівняння x2 ??C може мати один чи два
корені);
2. Деякими допоміжними засобами встановити, який із коренів m1, m2, m3,
m4 є вихідним повідомленням M.
Приклад
Генерація ключа. p = 277, q = 331, n = 277 * 331 = 91687;
Кодування. Перед кодуванням 10 бітового повідомлення M = 10011110012
припишемо в кінці його останні 6 бітів: M’ = 10011110011110012 = 40569.
C = M’2 mod n = 405692 mod 91687 = 62111
Декодування. Обчислюємо квадратні корені з числа 62111 за модулем 91687:
m1 = 69654, m2 = 22033, m3 = 40569, m4 = 51118,
які у двійковому представленні мають вигляд:
m1 = 10001000000010110, m2 = 1010110000100001,
m3 = 1001111001111001, m4 = 1100011110101110
Оскільки лише в одному із коренів останні 6 біт повторюються, то
вихідним повідомленням було M = m3.
Проблема дублювання інформації. Отримувач закодованого повідомлення С
стоїть перед проблемою знаходження вихідного повідомлення M серед
квадратних коренів m1, m2, m3, m4. Для цього можна перед кодуванням
продублювати певну частину даних (наприклад останні 64 біти). Тоді з
великою ймовірністю у одного із коренів mi будуть продубльовані останні
біти, який і вважається переданим повідомленням M. Якщо жодне із mi не
мають дублюючих даних, то повідомлення С вважається хибним і не
розглядається далі.
Нашли опечатку? Выделите и нажмите CTRL+Enter
