В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 11. Простые числа шая библиотека арифметических операций многократной точности должна иметь оптимизированную функцию для оценки таких операций. С выполне- нием этой задачи неплохо справляется особый тип умножения, называемый умножением Монтгомери (Montgomery). Существуют также способы вычис- ления a s с использованием меньшего количества умножений [10, глава 4]. Каждый из этих приемов может сэкономить от 10 до 30% времени, необ- ходимого для возведения в степень по модулю, поэтому в комбинации друг с другом они могут принести немалую пользу. Прямые реализации операций возведения в степень по модулю зачастую бывают чувствительны к тайминг-атакам. Более подробно тайминг-атаки и способы борьбы с ними рассматриваются в главе 16. Глава 12 Алгоритм Диффи–Хеллмана Обсуждая вопросы криптографии с открытым ключом, мы собираемся проследить исторический путь ее развития. Впервые понятие криптографии с открытым ключом было введено в 1976 году Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в опубликованной ими статье New Directions in Cryptography (Новые направления в криптографии) [21]. До сих пор речь шла только о шифровании и аутентификации с общими секретными ключами. Но где же взять эти общие секретные ключи? Если вы хотите общаться, скажем, с 10 друзьями, то можете встретиться и обме- няться секретными ключами друг с другом для дальнейшего использования в общении. Но, как и все секретные ключи, эти ключи должны подвергаться регулярному обновлению, поэтому вам придется вновь и вновь встречать- ся и обмениваться ключами. Для группы из 10 друзей нужно 45 секретных ключей. По мере увеличения этой группы количество необходимых ключей возрастает квадратически. Для ста человек, желающих общаться друг с дру- гом, вам понадобится уже 4950 ключей! Ситуация быстро выходит из-под контроля. Диффи и Хеллман поставили вопрос о том, нельзя ли проводить обмен ключами более эффективно. Предположим, у нас есть алгоритм шифрова- ния, в котором для шифрования и дешифрования применяются разные клю- чи. В этом случае мы можем спокойно опубликовать ключ шифрования, а ключ дешифрования сохранить в секрете. Теперь каждый человек может послать нам зашифрованное сообщение, но расшифровать его сможем только мы. Это бы решило проблему необходимости распространения такого боль- шого количества разных ключей. Диффи и Хеллман сформулировали этот вопрос, но смогли дать на него лишь частичный ответ. Полученное ими решение известно сегодня как прото- кол обмена ключами Диффи–Хеллмана (Diffie-Hellman key exchange protocol) , сокращенно DH [21]. 229 |