Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?о такое событие будет сразу же обнаружено - шифрование и дешифрирование не будут работать. Существует ряд чисел, называемых числами Кармайкла, которые не могут обнаружить определенные вероятностные алгоритмы поиcка простых чисел. Они небезопасны, но чрезвычайно редки. Честно говоря, меня бы это не обеспокоило.
Вскрытие с выбранным шифротекстом против RSA
Некоторые вскрытия работают против реализаций RSA. Они вскрывают не сам базовый алгоритм, а надстроенный над ним протокол. Важно понимать, что само по себе использование RSA не обеспечивает безопасности. Дело в реализации.
iенарий 1: Е, подслушавшему линии связи А, удалось перехватить сообщение с, шифрованное с помощью RSA открытым ключом А. Е хочет прочитать сообщение. Ha языке математики, ему нужно т, для которого
т = cd
Для раскрытия т он сначала выбирает первое случайное число r, меньшее п. Она достает открытый ключ А e. Затем он вычисляет
x = re mod n = xc mod n = r-1 mod n
Если x = re mod n, то r = xdmod n.
Теперь E просит А подписать у его закрытым ключом, таким образом расшифровав у He забывайте, А никогда раньше не видел у. А посылает Е
и = yd mod n
Теперь Е вычисляет
tu mod n = r-1 yd mod = r -1xd cd mod n = cd mod n = m
И получает т.
iенарий 2: С - это компьютер-нотариус. Если А хочет заверить документ, он посылает его С. С подписывает его цифровой подписью RSA и отправляет обратно. (Однонаправленные хэш-функции не используются, С шифрует все сообщение своим закрытым ключом .)хочет, чтобы С подписал такое сообщение, которое в обычном случае он никогда не подпишет. Может быть это фальшивая временная метка, может быть автором этого сообщения является другое лицо. Какой бы ни была причина, С никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение т'.
Сначала F выбирает произвольное значение x и вычисляет у = xe mod n. e он может получить без труда - это открытый ключ С, который должен быть опубликован, чтобы можно было проверять подписи С. Теперь F вычисляет m = ym' mod n и посылает т С на подпись. С возвращает md mod n. Теперь F вычисляет (md mod n)x-1 mod n, которое равно nd mod n и является подписью m'.
Ha самом деле F может использовать множество способов решить подобную задачу. Слабым местом, которое используют такие вскрытия, является сохранение мультипликативной структуры входа при возведении в степень. To есть:
(xm)d mod n = x d md mod n
iенарий 3: Е хочет, чтобы А подписал m3. Он создает два сообщения, m1 и m2, такие что
m3=m1m2 mod m
Если Ева сможет заставить А подписать m1 и m2, она может вычислить подпись для m3:
M3d =(m1d mod n)(m2d mod n)
Мораль: Никогда не пользуйтесь алгоритмом RSA для подписи случайных документов, подсунутых вам посторонними. Всегда сначала воспользуйтесь однонаправленной хэш-фунцией.
Вскрытие общего модуля RSA
При реализации RSA можно попробовать раздать всем пользователям одинаковый модуль и, но каждому свои значения показателей степени e и d. K сожалению, это не работает. Наиболее очевидная проблема в том, что если одно и то же сообщение когда-нибудь шифровалось разными показателями степени (с одним и тем же модулем), и эти два показателя - взаимно простые числа (как обычно и бывает), то открытый текст может быть раскрыт, даже не зная ни одного ключа дешифрирования.
Пусть т - открытый текст сообщения. Два ключа шифрования - e1 и e2- Общий модуль - п. Шифротекстами сообщения являются:
С1= me1 mod n2 = me2 mod n
Криптоаналитик знает n,e1,e2,c1 и c2 Вот как он узнает m.
Так как e1 и e2 - взаимно простые числа, то с помощью расширенного алгоритма Эвклида r и s, для которых:
re1 + se2 = 1
iитая r отрицательным (или r, или s должно быть отрицательным, пусть отрицательным будет r), то снова можно воспользоваться расширенным алгоритмом для вычисления c1-1. Затем
(c1-1)-r *c2s = m mod n
Полученные уроки
На основании перечисленных вскрытий приводит следующие ограничения RSA:
Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику разложить модуль на множители.
Знание одной пары показателей шифрования/дешифрирования для данного модуля позволяет взломщику вычислить другие пары показателей, не раскладывая модуль на множители.
B протоколах сетей связи, применяющих RSA, не должен использоваться общий модуль. (Это является быть очевидным следствием предыдущих двух пунктов.)
Для предотвращения вскрытия малого показателя шифрования сообщения должны быть дополнены слyчайными значениями.
Показатель дешифрирования должен быть большим.
He забывайте, недостаточно использовать безопасный криптографический алгоритм, должны быть безопаcными вся криптосистема и криптографический протокол. Слабое место любого из трех этих компонентов сделaет небезопасной всю систему-впрочем, я об этом говорил в самом начале.
Вскрытие шифрования и подписи с использованием RSA
Имеет смысл подписывать сообщение перед шифрованием но на практике никто не выполняет этого. Для RSA можно вскрыть протоколы, шифрующие сообщение до его подписания.
А хочет послать сообщение B. Сначала он шифрует его открытым ключом B, а затем подписывает своим закрытым ключом. Eго зашифрованное и подписанное сообщение выглядит так:
(meb mod nb)da mod na
Вот как B может доказать, что А послал ему m', а не т. Так как B известно разложение на множители пв (это его собственный модул