владелец

Хотя алгоритм RSA получил широкое распространение, он ни в коей мере не яв­ляется единственным известным алгоритмом с открытым ключом. Первым алго­ритмом с открытым ключом стал «алгоритм ранца» (Merkle и Hellman, 1978). Его идея состоит в том, что имеется большое количество объектов различного веса. Владелец этих объектов кодирует сообщение, выбирая подмножество объектов и помещая их в ранец. Общий вес объектов в рюкзаке известен всем, как и список всех возможных объектов. Список объектов, находящихся в рюкзаке, хранится в секрете. При определенных дополнительных ограничениях, задача определения возможного списка объектов по известному общему весу считалась неразреши­мой для вычисления, то есть считалось, что решение можно найти только полным перебором различных сочетаний предметов списка. Поэтому она была положена в основу алгоритма с открытым ключом.

Изобретатель алгоритма Ральф Меркле (Ralph Merkle) был настолько уверен в надежности своего алгоритма, что предложил 100 долларов любому, кто суме­ет его взломать. Ади Шамир (Adi Shamir), «S» в группе RSA, мгновенно взло­мал его и получил награду. Это не смутило Меркле. Он усилил алгоритм и пред­ложил за его взлом уже 1000 долларов. Рон Ривест (Ron Rivest), «R» в RSA, тут же взломал улучшенную версию алгоритма и получил награду. Меркле не риск­нул предложить 10 000 долларов за следующую версию, поэтому «А», Леонар­ду Эйдлману (Leonard Adleman), не повезло. Несмотря на то, что алгоритм ран­ца был в очередной раз исправлен, он не считается надежным и редко использу­ется.

Другие схемы с открытым ключом основаны на сложности вычисления дис­кретных логарифмов. Алгоритмы, использующие этот принцип, были разработа­ны Эль-Гамалем (El Gamal, 1985) и Шнорром (Schnorr, 1991).

Существуют и некоторые другие методы, например, основанные на эллипти­ческих кривых (Menezes и Vanstone, 1993). Однако две основные категории со­ставляют алгоритмы, основанные на сложности нахождения делителей больших чисел и вычислений дискретных логарифмов. Эти задачи считаются особенно сложными, так как математики уже много лет пытаются их решить без особых успехов.