5. Криптографические атаки

Демонстрация возможных атак особенно важна при изучении криптографии, т.к. это помогает избежать типичных ошибок при использовании алгоритма. Это и будет основным критерием при выборе атак, т.к. в программе курса об атаках не говорится.

Возможные виды нападений на криптосистемы можно разделить на несколько групп [2]:

1. Нападения на криптографические алгоритмы.

2. Нападения, связанные с нарушением протокола.

3. Нападения, основанные на нарушении механизмов функционирования криптосистемы.

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

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

К нападениям, связанным с нарушением протокола относятся, например, повторения подписанных сообщений, задерживание сообщений. В данной работе основное внимание будет уделено атакам, которые возможны благодаря неправильному использованию алгоритма в том или ином протоколе.

Описание использованных атак

5.1. Атака на общий модуль против алгоритма rsa

Предположим, что генерация ключей для группы пользователей происходит следующим образом: всем пользователям дается одно значение n, но разные значенияeиd. ПользовательA хочет послать одно и то же сообщение,m, двум различным пользователям с открытыми ключами (n,e₁) и (n,e₂). Зашифрованными текстами будут:

c₁ =m^e1modn,

c₂=m^e2modn.

Противник узнал c₁иc₂, и хочет узнатьm. Чтобы он смог это сделать надо, чтобыe₁иe₂были взаимно простыми, а чаще всего так и оказывается. Поэтому будем считать, что НОД(e₁,e₂) = 1. Следовательно, существуют числаrиs, такие чтоr*e₁+s*e₂=1. Для вычисленияrиsможно воспользоваться расширенным алгоритмом Евклида.

Числа rиsимеют разные знаки. Предположим, чтоrотрицательно. Тогда противник может вычислить (c₁^-1)^-r*c₂^s=mmodn, т.е. получить открытый текст.

Описание атаки взято из [3].

5.2. Атака на выбранный шифртекст против алгоритма rsa

Пользователю A направлено сообщениеm, зашифрованное его открытым ключом,e. ПротивникE смог получить соответствующий зашифрованный текст,c.Е хочет узнать открытый текст, т.е. получитьm=c^dmodn, но он не знает секретного ключаd. ПоэтомуEдействует следующим образом:

1. Eвыбирает случайным образом числоr:r<n.

2. Имея открытый ключ A - e, Eвычисляет

x = r^e mod n

y = xc mod n

t = r^-1 mod n.

3. E добивается, чтобыA подписалyс помощью алгоритмаRSA, т.е. расшифровалy, а затем послал ему результатu=y^dmodn.A должен подписать само сообщение, а не его дайджест. Сообщениеyскорее всего будет выглядеть случайным, а на практике иногда приходится подписывать случайные сообщения.

4. E вычисляет

tu mod n = r^-1 y^d mod n = r^-1 x^d c^d mod n = c^d mod n = m,

т.е. получает открытый текст.

Описание атаки приведено в [3].