Журнал «Компьютерра» N 31 от 29 августа 2006 года

Секретный ключ Алисы в RSA - это два простых числа p и q. Чем больше эти числа, тем шифр надежнее. Именно поэтому многие организации готовы платить деньги за большие простые числа; давно существуют онлайн-проекты распределенных вычислений по поиску простых чисел. Алиса публикует произведение этих чисел N=pq. Ключевое предположение, на котором основана RSA, - то, что большое число трудно разложить на множители. То есть N можно распространять, а p и q все равно никто не узнает.

Кроме собственно N в открытый ключ входит также число e, которое должно быть меньше числа ? (N)=(p-1)(q-1) и взаимно просто с ним.[ ?(N) - это функция Эйлера, играющая очень важную роль в теории чисел; здесь, правда, используется ограниченный частный случай; в общем случае функция Эйлера от n равна количеству чисел, меньших n и взаимно простых с ним. ] Секретный же ключ - такое число d, что de ? 1 mod ? (N). Алиса может с легкостью вычислить d, но никто другой на это не способен - ведь если трудно разложить N на множители, то трудно и подсчитать функцию Эйлера. Боб теперь, желая зашифровать свое сообщение m, вычисляет y ? m e mod N и передает его Алисе (и всем желающим). Алиса может расшифровать его, вычислив y d ? m ed ? m mod N (последнее сравнение выполняется благодаря малой теореме Ферма - не путать с заметкой на полях «Арифметики»; доказательство малой теоремы достаточно просто и входит в любой базовый учебник теории чисел).

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

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

Математика криптосистемы Диффи-Хеллмана