T.ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms//IEEE Transactions on Information Theory, 1985, vol.31, Э4, pp.469-472. Криптосистема с открытым ключом и метод цифровой подписи, основанные на дискретных логарифмах. I. Введение 1976, Диффи-Хеллман [3] - идея систем с открытым ключом. [6,7,9] - попытки практического воплощения. II. Система с открытым ключом Схема Диффи-Хеллмана: пусть А и В хотят сообща владеть (разделять) секретом Kab, причем А знает секрет Xa, а В - секрет Xb. Пусть p - большое простое число, а - примитивный элемент по модулю p, оба известны. А вычисляет Ya= mod p и посылает его В. В вычисляет Yb= mod p и посылает его А. Kab вычисляется как mod p=Ya mod p=Yb mod p. А и В могут рассчитать Kab, но для злоумышленника это тяжело. Ещг не доказано, что раскол системы эквивалентен вычислению дискретных алгоритмов (см. [3]). В любых криптосистемах, основанных на дискретных логарифмах, p должно выбираться так, чтобы p-1 имело по меньшей мере один большой простой множитель (если множители маленькие, то вычисление дискретных логарифмов легко [8]). Теперь предположим, что А желает послать В сообщение m, причгм 0<=m<=p-1. Сперва А выбирает число k, равномерно распределгнное между 0 и p-1 (k послужит как секретное Xa в схеме распределения ключей). Затем А вычисляет "ключ" K=Yb mod p, (1) где Yb= mod p взято из справочника или его послал В. Тогда шифртекст - это пара (С1,С2), где С1= mod p, С2=K*m modp. (2) Размер шифртекста равен удвоенному размеру сообщения. Умножение в (2) можно заменить любой обратимой операцией (например, сложением по модулю p). Дешифрование проводится в два этапа: сперва восстанавливают K, что несложно сделать для В, так как K=( ) =С1 mod p, а Xb известно только В. Затем C2 делят на K и восстанавливают сообщение m. Справочник состоит из одного атрибута для каждого пользователя (Yi для пользователя i; и p известны всем пользователям). Возможен вариант, когда и p выбираются самими пользователями, но тогда справочник утраивается в размере. Не рекомендуется использовать одно и то же k для шифрования более одного блока сообщения, иначе знание одного блока m1 позволит злоумышленнику раскрыть другие блоки. Пусть С1,1= mod p С2,1=m1*K mod p С1,1= mod p С1,1=m2*K mod p. Тогда m1/m2=С2,1/С2,2 mod p, и m2 вычислим при известном m1. Раскол системы эквивалентен расколу метода распределения Диффи-Хеллмана. Во-первых, если m можно вычислить из С1, С2 и Y, то K можно рассчитать из Y, С1 и С2 (которое похоже на случайное число, поскольку k и m неизвестны). Во-вторых, (даже при известном m) вычисление k или X из С1, С2 и Y эквивалентно вычислению дискретных логарифмов, так как X и k появляются в качестве экспоненты Y и C1. - 2 - III. Метод цифровой подписи Предлагается новый метод цифровой подписи. Справочник содержит одни и те же открытые ключи как для шифрования сообщений, так и для проверки подписи. Пусть m - подписываемый документ, где 0<=m<=p-1. В справочнике имеется Y= mod p для каждого пользователя. Для подписания документа m пользователь А должен так использовать секретный ключ Xa, чтобы все пользователи могли проверить аутентичность документа при помощи открытого ключа Ya (совместно с и p), и никто не мог бы подделать цифровую подпись без знания Xa. Цифровая подпись документа m - это пара (r,s), 0<=r,s