3. Разложение на множители: Если N - произведение двух простых чисел, то лиьо

(a) разложить N на множители,

(b) для заданных целых чисел M и C найти d, для которого Md = C (mod N),

(c) для заданных целых чисел e и C найти M, для которого Me = C (mod N),

(d) для заданного целого числа * определить, существует ли целое число y, для которого * = y2 (mod N).

Согласно Диффи [492, 494], проблема дискретных логарифмов б1ла предложена Дж. Гиллом (J. Gill), проблема разложения на множители - Кнутом , а проблема рюкзака - самим Диффи.

Эта узость математических основ криптографии с открытыми ключами немного беспокоит . Прорыв в решении либо проблемы дискретных логарифмов, либо проблемы разложения на множители сделает небезопасными целые классы алгоритмов с открытыми ключами. Диффи показал [492, 494], что подобный риск смягчается двумя факторами:

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

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

Как мы уже видели, не все алгоритмы с открытыми ключами, основанные на этих проблемах, безопасны . Сила любого алгоритма с открытым ключом зависит не только от вычислительной сложности проблемы, леж а-щей в основе алгоритма. Трудная проблема необязательно реализуется в сильном алгоритме . Ади Шамир объясняет это тремя причинами [1415]:

1. Теория сложности обычно связана с отдельными частными случаями проблемы. Криптоаналитик же часто получает большой набор статистически связанных проблем - различные шифротексты, заши ф-рованные одним и тем же ключом.

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

3. Произвольную сложную проблему необязательно можно преобразовать в криптосистему, к тому же проблема должна позволить встроить в нее лазейку, знание которой и только оно делает возможным простое решение проблемы.