Прислал Stalker

Этот раздел содержит в себе описания различного рода атак на одну из наиболее популярных ныне схем открытого шифрования и цифровой подписи - RSA. Рассматриваемые методы предполагают наличие определенных математических слабостей схемы, не учитываемых при бесшабашной реализации. Также приводятся меры противодействия этим атакам. Их необходимо принимать во внимание при реализации схемы RSA или протоколов, основанных на ней.

1. Безключевое чтение RSA.

2. Атака на подпись RSA в схеме с нотариусом.

3. Атака на подпись RSA по выбранному ш.т.

Прежде всего вспомним саму схему о.ш и ЭЦП RSA.

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

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

Процедура зашифрования: C=E_(e,n)(M)=M^e(mod n), где С-получаемый ш.т. , M - о.т., удовлетворяющий следующему условию: M^ф(n)=1(mod n).

Процедура расшифрования: M=D_(d,n)(C)=C^d(mod n).

Генерация цифровой подписи: цифровая подпись Q=M^d(mod n).

Проверка цифровой подписи:   Q^e(mod n) ?= M.

1. Метод безключевого чтения RSA.

Начальные условия. Противнику известны открытый ключ (e,n) и шифротекст С.

Задача. Найти исходный текст M.

Противник подбирает число j, для которого выполняется следующее соотношение: С^ej(mod n)=C. Т.е. противник просто проводит j раз зашифрование на открытом ключе перехваченного шифротекста (это выглядит следующим образом: (С^e)^e)^e..)^e(mod n)=С^ej(mod n)). Найдя такое j, противник вычисляет C^ej-1(mod n) (т.е. j-1 раз повторяет операцию зашифрования) - это значение и есть открытый текст M !  Это следует из того, что С^ej(mod n)=(C^ej-1(mod n))^e=C. Т.е некоторое число C^ej-1(mod n) в степени e дает шифротекст С. А что же это, как не открытый текст M?

Пример (по Sinmons & Norris). p=983, q=563, e=49, M=123456.

C=M⁴⁹(mod n)=1603, C⁴⁹⁷(mod n)=85978, C⁴⁹⁸(mod n)=123456, C⁴⁹⁹(mod n)=1603.

2. Атака на подпись RSA в схеме с нотариусом.

Начальные условия. Имеется электронный нотариус, подписывающий проходящие через него документы. N - некоторый открытый текст, который нотариус не желает подписывать. Противнику известны открытый ключ (e,n) нотариуса.

Задача. Подписать этот текст N.

Противник вырабатывает некое случайное число x, которое взаимнопросто с N и вычисляет y=x^e(mod n). Затем получает значение M=yN и передает его на подпись нотариусу. Тот подписывает (ведь это уже не текст N!) M^d(mod n)=S. Т.е получаем, что S=M^d(mod n)=y^dN^d=(x^e)^dN^d =xN^d, а значит N^d=Sx ^-1(mod n).Т.е надо просто поделить полученное S на x.

Защита. При подписи добавлять некоторое случайное число в сообщение (например, время). Таким образом получится искажение числа M при подписи, т.е M_{(после добавления)} ... yN.

3. Атака на подпись RSA по выбранному шифротексту.

Начальные условия. Имеется шифротекст C. Противнику известны открытый ключ (e,n) отправителя сообщения.

Задача. Найти исходный текст M

Противник вырабатывает некое r: r<n, (r,n)=1 и вычисляет x=r^e(mod n). Затем о вычисляет t=r^-1(mod n) и y=xC(mod n) и посылает y на подпись отправителю.

Отправитель, ничего не подозревая, подписывает текст y: w=y^d(mod n) и отправляет w обратно.

Противник вычисляет tw(mod n)=r^-1y^d(mod n)= (поскольку r=x^d mod n)=x^-dx^dC^d(mod n)=C^d=M.

Противник не может сразу послать C на подпись, т.к. отправитель просматривает полученные в результате подписи сообщения и может заметить провокацию.

Атака носит несколько гипотетический характер, но тем не менее позволяет  сделать несколько важных выводов: а) подписывать и шифровать надо разными ключами, либо б) добавлять случайный вектор при подписи или использовать хэш-функцию.