СВЯЗАННЫЕ С ОБОСНОВАНИЕМ КРИПТОГРАФИЧЕСКИХ СВОЙСТВ СИСТЕМЫ RSA

 

    7.1. В системе RSA простые числа p и q не следует выбирать близкими друг к другу. Нетрудно видеть, что

                                 (p+q)²/4 - n = (p-q)²/4.

    Таким образом, левая часть равенства образует полный квадрат.

    Проверяя далее целые числа x>(n)^1/2, находим такое, что x²-n есть полный квадрат:  x²-n = y². Отсюда получим разложение

                                 n= (x-y)(x+y).

    7.2. Выбор p и q важен также с точки зрения возможной атаки, основанной на последовательном шифровании. При этом процесс начинается с шифртекста c₀=m^e (mod n) и заключается в последовательном вычислении чисел c_i=(c_i-1)^e (mod n), i=1,2,... до нахождения открытого текста m.

    Нетрудно видеть, что данный метод может быть эффективным в случае “малости” мультипликативного порядка числа e по модулю j(n)=(p-1)(q-1). А так как порядок числа e является делителем j(n), то эффективность метода маловероятна, если (p-1) и (q-1) обладают большими простыми множителями.

 

    7.4. В некоторых случаях выбор “маленькой” экспоненты шифрования e может привести к слабости системы в целом.

    Пусть абоненты A,B,C имеют открытую экспоненту зашифрования e=3. При этом n₁, n₂, n₃  - соответствующие попарно взаимно простые модули используемых ими систем RSA.

    Пусть каждому из абонентов направлено одно и то же сообщение  w< min{n₁, n₂, n₃}. Тогда имеем систему уравнений   

                                 c_i =w³ (mod n_i), i =1,2,3.

    По известным c_i с учетом китайской теоремы об остатках можно вычислить число w_*ÎZ_n, n=n₁×n₂×n₃, удовлетворяющее соотношениям

c_i =w_* (mod n_i), i =1,2,3.

Следовательно,   w_* = w³ (mod n) , n=n₁n₂n₃.

    Так как w<n_i при любом i =1,2,3, то будем иметь равенство w³=w_*  в кольце Z целых чисел. Отсюда w = (w_*)^1/3 , и открытый текст восстановлен.

 

    7.5. Однако и выбор “большой” экспоненты e может оказаться неудачным. Нетрудно убедиться в том, что если e-1 является кратным обоих чисел p-1 и q-1, тогда для любого x

                                 x^eº x (mod n).

В частности, таким свойством обладает экспонента вида e= j(n)/2 +1.

    7.6. Теорема. Алгоритм нахождения экспоненты расшифрования d можно преобразовать в вероятностный алгоритм факторизации n=pq.

    Доказательство. В доказательстве мы будем использовать числа w со свойством 1£w<n и (w,n)=1. Ясно, что если в результате случайного выбора w<n мы получим (w,n)>1, то это приведет к разложению числа n=pq.

    Это будет и в случае нахождения в кольце Z_n нетривиального квадратного корня из 1, то есть в случае нахождения числа u такого, что      u¹±1 (mod n) и одновременно u²º1 (mod n).

    Действительно, в таком случае (u+1)(u-1)º0 (mod n),  Þ (u+1,n) - нетривиальный делитель для n.

    Итак, пусть экспонента d стала известной. Находим представление

                                 ed-1 = 2^s r, s³1, r - нечетно.

    Так как ed-1º0 (mod j(n)), то получаем соотношение

                                 2^s×r

                                 w   º 1 (mod n)

для произвольного w (напомним, что мы рассматриваем лишь такие w, что 1£w<n и (w,n)=1).

    Пусть s(1), где 0£s(1)£ s, является наименьшим числом, для которого выполнено сравнение

                                 2^s(1)× r

                                 w   º 1 (mod n).

 

    Если при этом s(1)>0 и

 

                                 2^s(1)-1×r

                                 w   ¹ -1 (mod n)                              (7.1)

 

то мы найдем нетривиальный квадратный корень из 1 по модулю n, что приводит к разложению числа n.

    Пусть теперь (7.1) не имеет места. Это равносильно тому, что

                                 w^r º 1 (mod n)

или

                                 2^t× r

                                 w   º -1 (mod n)                               (7.2)

для 0£t<s.

    Пусть p-1 = 2ⁱ×a, q-1 = 2^j×b, где a,b - нечетны, i,j³1. Положим для определенности i£j. Так как 2^s×r является кратным j(n), то r кратно ab. Отсюда если t³i,то 2^t×r кратно p-1 и будем иметь

                                 2^t×r

                                 w   º 1 (mod p).

    Далее имеем

                                  2^t×r

                                 w   ¹ -1 (mod p), Þ

                                 2^t×r

                                 w   ¹ -1 (mod n).

    Таким образом, условия (7.2) никогда не будут выполнены для t³i, Þ условия (7.2) можно записать в следующей эквивалентной форме:

                                 w^r = 1 (mod n)

или

                                 2^t×r

                                 w   º -1 (mod n)                          (7.3)

для 0£t<i.

    Пусть g - образующий элемент поля Z_p и w=g^u (mod p). Ясно, что число решений сравнения (относительно wÎZ_p) w^r = 1 (mod p) совпадает с числом решений сравнения (относительно uÎF_p) u×r º 0 (mod p-1) и равняется (r, p-1) = a.

    Аналогичным образом b есть число решений сравнения w^r=1 (mod q), Þ ab есть число решений сравнения w^r=1 (mod n).

    Рассуждая аналогичным образом и учитывая, что t+1£i, получим, что число решений сравнений

              2^t+1×r                      2^t×r

              w   º 1 (mod p) и w º 1 (mod p)

равно соответственно (2^t+1×r, p-1) = 2^t+1×a и (2^t×r, p-1) = 2^t×a.

    Отсюда число решений сравнения

                                 2^t r

                                 w   º -1 (mod p)

равно 2^t+1 a - 2^t a = 2^t a.

    Аналогичным образом число решений сравнения

                                 2^t r

                                 w   º -1 (mod q)

равно 2^t b, Þ число решений сравнения

                                 2^t r

                                 w   º -1 (mod n)

равно 2^2t×a×b.

    Теперь мы можем дать верхнюю оценку количества чисел w, удовлетворяющих условию (7.3):

 ab + ab× 2^2t = ab×(1+ 4^t) = ab×(1 + (4ⁱ-1)/3) =

= ab×(2/3 + 2/3×2^2i-1) £ ab×(2/3×2^i+j-1 + 2/3) =

= ab×(2^i+j-1 + 1/3×(2 - 2^i+j-1)) £ ab×2^i+j-1 = j(n)/2.

    Так как j(n) есть общее число всех опробуемых w, то после проверки k чисел вероятность разложения n будет не менее 1-2^-k , то есть будет стремиться к 1 при k®¥.

 

    7.7. Если имеются два участника A, B с открытыми экспонентами e₁, e₂, общим модулем n=pq (p,q - для них неизвестны) и секретными экспонентами d₁, d₂, тогда любой из участников может найти секретную экспоненту другого без факторизации n.

    Покажем, как B может найти d₁.

Случай 1.  Пусть числа e₁ и a=e₂×d₂ -1 взаимно просты.

    С помощью расширенного алгоритма Евклида находим целые r,s, при которых в кольце целых чисел : re₁+sa=1.

Отсюда (с учетом того, что e₂×d₂ -1=0 (mod j(n))) вытекает равенство

re₁=1 (mod j(n)).

    Следовательно, r=d₁, и задача решена.

Случай 2 (общий случай). Пусть g₀ = e₂d₂ - 1, h₀ = (g₀, e₁).

    Далее строим последовательность пар {g_i, h_i}:

                                 g_i = g_i-1/h_i-1, h_i = (g_i, e₁).

Данный процесс останавливается при h_i=1. Так как для h_i³2 имеет место неравенство: g_i+1 £ g_i/2, то число шагов алгоритма не более log₂(e₂d₂ - 1).

    Для h_i=1 обозначим  t= h₀h₁h₂...h_i и a=g_i.

    Далее с помощью алгоритма Евклида вычисляем a,b такие, что

aa + be₁ = 1.

Если теперь показать, что aº0 (mod j(n)), то получим

                                  be₁ º 1 (mod j(n)),

и, следовательно, b=d₁.

    Для того, чтобы показать, что aº0 (mod j(n)), заметим, что из        условия (e₁,j(n))=1 следует, что t является произведением чисел, не имеющих общих множителей с j(n), Þ (t,j(n))=1.

    Отсюда a = k×j(n)/t, причем k/t - целое, Þ aº0 (mod j(n)).

 

 

ЛИТЕРАТУРА                      

 

 

1. Р. Лидл, Г. Нидеррайтер. Конечные поля, т. 1-2, М.- Мир, 1988.

 

2. Введение в криптографию (под редакцией В.В. Ященко). М. - МЦНМО- ЧеРо, 1998.

 

3. Саломаа А. Криптография с открытым ключом. – М.: Мир, 1996.

 

4. А.П.Алферов, А.Ю.Зубов, А.С.Кузьмин, А.В.Черемушкин. Основы криптографии (учебное пособие). – М.: Гелиос АРВ, 2001. – 408 с.

 

5. Menezes A.J., van Oorschot P.C., Vanstone S.A. Handbook of applied cryptography. – CRC Press, Boca Raton, New York, London, Tokyo, 1997.

 

6. T. El Gamal. A Public Key Cryptosystem and a Signature Scheme. Proceedings of Crypto-84. Lectyre Notes in Computer Science, 1984, p.10-19.

 

7. W.Diffie, M.Hellman. New directions in cryptography. IEEE Trans. Inform. Theory, v. IT-22, no. 6, 1976.

 

8. A.Shamir. A polinomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Trans. Inform. Theory, v. IT-30, no. 5, 699-704, 1984.

 

9. Blom R. Nonpublic key distribution // Advances in Cryptology. – Proceedings of EUROCRYPT’82. Plenum. New York. – 1983. pp. 231 – 236.

 

10. Matsumoto T., Takashima Y., Imai H. On seeking smart public-key-distribution systems // Trans. of the IECE of Japan. – 1986. – E69. – p. 99-106. 

 

---

Дата добавления: 2019-02-12; просмотров: 153; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!