Криптосистема RSA.

 

Эта асимметричная криптосистема в настоящее время является широко распространенной в мире и называется так по первым буквам в именах создателей R. Rivest, A. Shamir, L. Adleman.

1. Описание криптосистемы

1.1 Генерация ключей

Для работы каждый абонент должен выработать секретный и открытый ключи. 
Вырабатываются p,q - большие простые числа. 
Вычисляется произведение n=pq. 
Выбирается число e - такое, что 1<e<j(n) и НОД (e, j(n))=1, где j(n)=(p-1)(q-1) - функция Эйлера от n.
Из уравнения ed=1(mod j(n)) посредством расширенного алгоритма Евклида находится число d.  

Полученные числа e,n - открытый ключ пользователя, а d - секретный ключ. 

1.2 Шифрование

Абонент B зашифровывает и посылает A сообщение m, которое тот затем расшифровывает. 
Зашифрование. B должен сделать: 
Получить открытый ключ А : e,n
Представить сообщение в виде числа m из интервала [0,n-1]
Вычислить c=me mod n
Послать шифртекст с абоненту A 
Расшифрование. Для получения текста A должен сделать:
Используя секретный ключ d вычислить m=cd mod n.

Т-ма 1.2.1: если ed=1(mod j(n)), (e, j(n))=1, (m, n)=1, тогда (me)d mod n=m.

Док-во: поскольку ed=1(mod j(n)), значит ed=1+kj(n), где k - некое число. Из т-мы Эйлера следует, что 

m j(n) =1(mod n) при (m, n)=1. 

Значит (me)d(mod n)=(m1+kj(n))(mod n)=m(mj(n))k(mod n)=m.

Оценим вероятность того, что сообщение будет не взаимнопросто с n, т.е. что (m, n)?1. Число всех чисел - n, число чисел, взаимно простых с n - j(n). Значит вероятность попадания m в совокупность чисел, не взаимопростых с n  P{(m, n)?1}=(n-j(n))/n = (pq-(p-1)(q-1))/pq = (p+q-1)/pq < 1/p +1/q.

2. Стойкость RSA

Рассмотрим стойкость криптосистемы и возможные атаки.

Стойкость RSA основывается на проблеме факторизации больших простых чисел. Действительно, если злоумышленнику удастся разложить n на делители p и q, то для него не составит труда вычислить j(n), а затем в соответствии с п.4 "Генерации ключей" определить секретный ключ пользователя. Однако   нахождение секретного ключа RSA не эквивалентно проблеме факторизации. Это означает, что T(RSA)<=T(факторизации), где T(RSA) - трудоемкость определения секретного ключа RSA, а T(факторизации) - трудоемкость факторизации числа n. Т.е. могут быть найдены эффективные алгоритмы определения секретного ключа RSA, причем в то же время проблема факторизации не будет разрешена.

2.1 Малая экспонента e.

Рассмотрим ситуацию, когда у нас имеется малая экспонента e (e=3,5,7 и т.д.). Пусть e=3. Допустим, что некто А желает послать одно и то же сообщение трем другим  абонентам, имеющим открытые ключи (3,n1), (3,n2),(3,n3). А шифрует сообщение и получает ci=m3(mod ni) для i=1,2,3. Противник перехватывает все 3 сообщения и составляет систему:

x=c1 (mod n1);

x=c2 (mod n2);

x=c3 (mod n3).

Поскольку 0<=x<n1n2n3 и m3 <n1n2n3, то по китайской теореме об остатках злоумышленник может найти x=m3 и вычислив кубический корень из x найдет m.

Т.е. получаем, что нельзя использовать малые экспоненты при отправке большого числа одинаковых сообщений. Или же следует использовать добавки ("salting") в сообщение, в качестве которых могут выступать добалвенные в конец сообщения случайные вектора или же время отправки.

При использовании малых экспонет также возникает проблема с маленькими сообщениями, т.е с такими,  для которых m<n1/e, поскольку в этом случае m может быть получено из шифртекста c=me mod n путем вычисления корня e-ой степени из C. Однако использование добавок в сообщение помогает избежать этой проблемы.

2.2. Атака перебором возможных открытых текстов.

Если сообщение не велико, злоумышленник может попытаться подобрать открытый текст путем перебора всех возможных вариантов и шифрования их на открытом ключе абонента e до тех пор, пока не будет получен перехваченный шифртекст c. Такую атаку также возможно предотвратить при помощи добавок в сообщение.

2.3. Использование общих модулей.

Схема RSA несостоятельна при использовании общих модулей. Допустим есть 2 абонета A и В с открытыми ключами (e1,n) и (e2,n). Центр (общий сервер или циркуляр) желает послать обоим абонетам одинаковые сообщения. Он получает me1=c1(mod n) и me2=c2(mod n) и посылает c1 и c2 А и В соответственно. Противник перехватывает эти сообщения. Затем, если (e1,e2)=1, по расширенному алгоритму Евклида можно найти такие k1и k2, для которых e1k1+e2k2=1. И, соответственно, me1k1me2k2=m. Т.е. найдя такие k1и k2 (это он может сделать, ведь открытые ключи ему известны) противник вычислит (c1)k1(c2)k2 = m.   c

Если сообщение не велико, злоумышленник может попытаться подобрать открытый текст путем 

 

2.4. Циклическая атака (безключевое чтение RSA).

Атака безключевым чтением описана в разделе Криптоанализ:Атаки на RSA. Однако помимо описанной атаки есть так назывемая "обобщенная циклическая атака". Суть ее заключается в следующем: найти наименьшее целое  u, такое, чтобы f=НОД(ceu-c,n)>1. 

Если ceu=c (mod p) и ceu? с (mod q), то f=p.

Если ceu? c (mod p) и ceu=с (mod q), то f=q.

В обоих этих случаях злоумышленник получает либо p, либо q и факторизует n.

Если же ceu= c (mod p) и ceu=с (mod q), тогда f=n и ceu= c (mod n). Однако этот случай гораздо менее вероятен, чем первые два. Поэтому обобщенную циклическую атаку можно считать одним из методов факторизации n.

2.5. Мультипликативные свойства.

Система RSA обладает мультипликативными совствми. Пусть m1 и m2 - 2 различных открытых текста, а c1 и с2 - соответствующие им шифртексты. Заметим, что 

(m1m2)e=m1e m2e=c1c2 (mod n)

Другими словами, шифртекст открытого текста m=m1m2 есть c=c1c2 (mod n). Это свойство, называемое также гомоморфным свойством RSA, позволет осуществить атаку по выбранному шифртексту (см. Криптоанализ:Атаки на RSA). Его нужно учитывать при совмещении схем шифрования на основе RSA и цифровой подписи RSA.

3. Практические рекомендации

В настоящее время рекомендуется выбирать n размером как минимум 768 бит, а для долговременного хранения информации 1024 или даже 2048 бит.

3.1 Выбор простых чисел 

Поскольку простые числа должны выбираться таким образом, чтобы факторизовать их произведение было вычислительно невозможно, рекомендуется брать их очень большими и одинаковой длины. Так, для n длины 1024 бита p и q должны быть длиной 512 бит.

Разность  чисел p и q (p-q) также не должна быть маленькой, поскольку в этом случае p @ q и, следовательно,  p @ Цn. Таким образом, разложение n может быть найдено простым делением на все числа порядка Цn.

Числа p и q должны быть также "устойчивыми" простыми числами.

Определение 3.1.1. Число p является устойчивым (strong), если оно удовлетворяет 3 условиям:
p-1 имеет большой простой делитель, обозначим его как r (т.е. p=1(mod r));
p+1 имеет большой простой делитель, обозначим как s (т.е. p=s-1(mod s));
r-1 имеет большой простой делитель, обозначим его как t (т.е. r=1(mod t)).

Условие 1 не позволит успешно факторизовать n (p-1) методом Полларда, который позволяет быстро разложитьчисло n на множители, если его делитель p имеет небольшие (скажем, меньше миллиона) простые делители. . Условие 2 позволит избежать p+1 метода Ульямса, позволяющего разложить n при условии, что p+1 имеет неболшие делители. Условие 3 позволит избежать метода безключевого чтения RSA (циклической атаки).

Если p выбирается случайно и имеет довольно большой размер, то, как правило, p-1 и p+1 будут иметьбольшие простые делители. Однако выбор устойчивых простых чисел не защищает систему от атаки алгоритмом факторизации на основе эллиптических кривых. 

Получить устойчивые простые числа можно следующим способом. Генерируем большие простые числа s и t. Затем получаем такое число r, что r-1 делится на t (для этого рассматриваем нечетные числа вида kt+1, где k - последовательные натуральные числа, и проверяем их на простоту, пока не найдем простое). Затем вычисляя p=((sr-1-rs-1) mod rs)+xrs, где x - некоторое целое число и проверяя p на простоту, находим устойчивое простое число p.

3.2 Выбор экспоненты e и ускорение работы 

Если число e выбирается случайным образом, то одним из способов ускорения вичислений (т.е. уменьшение числа возведений в степень) является следующий алгоритм быстрого возведения (на примере):

a25=(a2a)2)2)2a.

Таким образом, вместо 25 умножений выполняется всего 6 (т.е. 4 возведения в квадрат и 2 умножения на a). Формально алгоритм выглядит следующим образом:

Вход: aОZn   и целое 0<=k<n, чье двоичное представление - k=еti=0ki2i .

Выход: ak mod n.

1. b=1. If k=0 then return b.

2. A=a

3. If k0=1 then b=a

4. For i=1 to t do

4.1 A=A2 mod n.

4.2 If ki=1 then b=A*b mod n.

5. Return b

На практике как правило используется e=3, в этом случае необходимо, чтобы чтобы ни p-1, ни q-1 не делились на 3. При таком открытом ключе операция зашифрования получется очень быстрой и требует одно возведение в квадрат и одно модульное умножение (или 2 модульных умножения - в зависимости от реализации). Другим часто используемым значением является e=216+1=65537. Это число имеет одну единицу в двоичной записи и требует при использовании описанного алгоритма 16 возведений в квадрат и одно модульное умножение. Такая экспонента имеет преимущество по сравнению с e=3, поскольку в этом случае атака, описанная ранее, не осуществиться, т.к. очень мала вероятность, что одно и тоже сообщение будет послано 216+1 абонентам.
