Квадраты и псевдоквадраты
Пусть n – модуль RSA, то есть n=pq, p, q – различные большие простые числа. Возьмем произвольное число a: (a,n)=1. Возможны следующие случаи: 1) . Тогда число a является квадратичным вычетом, или квадратом, по модулю n. 2) , , или , . Тогда , и a не является квадратом по модулю n. То есть, не зная разложения модуля RSA на простые сомножители и получив отрицательное значение символа Якоби, можем с определенностью сказать, что a – не квадрат по модулю n. 3) , тогда a не является квадратом по модулю n, но символ Якоби, как и для квадрата по модулю n, равен единице: . То есть, не зная разложения модуля n на простые сомножители и получив положительное значение символа Якоби, не можем наверняка определить, является ли a квадратом по модулю n. Числа a: называются псевдоквадратами по модулю n=pq. Множество псевдоквадратов по модулю n обозначается . Утверждение (о мощности множеств квадратов и псевдоквадратов по модулю RSA). n=pq, p, q – различные простые числа |Q(n)|=| |=φ(n)/4. Доказательство: Согласно доказанной в п.1. теореме о числе кавдратичных вычетов, |Q(p)|=| |=(p—1)/2, |Q(q)|=| |=(q—1)/2. В силу взаимной простоты чисел p и q, среди чисел 0,1, 2, … , n—1 окажется ровно |Q(p)|·|Q(q)|=φ(n)/4 квадратов и | |·| |=φ(n)/4 псевдоквадратов. □ Задача различения квадратов и псевдоквадратов не сложнее задачи факторизации, так как, зная разложение n на простые сомножители, сможем вычислить и с помощью полиномиального алгоритма. На момент написания этого пособия не имелось никакой информации о том, проще ли задача различения квадратов и псевдоквадратов, чем задача факторизации.
Числа Блюма. Числа вида n=pq, p, q – различные простые числа, причем p≡3(mod 4), q≡3(mod 4), называются числами Блюма. Пусть n – число Блюма, и a Q(n). Тогда сравнение x2≡a(mod n) имеет четыре решения, которые можно представить в виде системы: . Заметим, что . Аналогично получим . То есть один корень из пары b,—b является, а другой не является квадратом по модулю p, один корень из пары c, —c является, а другой не является квадратом по модулю q. Таким образом, если n – число Блюма, то один из четырех корней сравнения x2≡a(mod n) является квадратом и один – псевдоквадратом по модулю n. Корень, являющийся квадратом по модулю n, называется главным корнем. Итак, мы только что показали важное свойство квадратичных сравнений по модулю чисел Блюма: извлекая квадратный корень по модулю Блюма, получаем 4 решения, из одного из которых в свою очередь можно извлечь квадратный корень, и т. д. На этом важном свойстве построено несколько криптосистем. BBS-генератор (генератор Blum-Blum-Shub): Параметры генератора: n=pq, p, q – различные простые числа, причем p≡3(mod 4), q≡3(mod 4) (то есть n – число Блюма). Начальное состояние (ключ генератора): s0 Q(n) Генерируемая последовательность: BBS(s0)=z1, z2, …, zm, где zi=si mod 2, i=1,2,…,m, si+1=si2 mod n, i ≥ 0.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1304)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |