Система открытого шифрования Эль-Гамаля на основе возведения в степень в конечном поле

 

    Пусть Z_p – поле вычетов по модулю большого простого числа p.  Пусть участник A желает послать участнику B сообщение m, 0£m£p-1. Для этого A берет случайное число k из интервала от 0 до p-1. Это число k используется для образования ключа K следующим образом:

                                 K = (y_B)^k mod p,                               (2.1)

где y_B = a^x(B) (mod p) - открытый ключ абонента B (этот открытый ключ либо хранится в общем файле открытых ключей, либо высылается абонентом B по запросу), x(B) – секретный ключ абонента B.

    Шифртекст далее будет состоять из пары (c₁, c₂), где

                                  c₁ = a^k (mod p), c₂ = K×m (mod p).               (2.2)

    Таким образом, размер шифртекста вдвое превосходит размер открытого сообщения. Заметим также, что мультипликативная операция в (2.2) может быть заменена любой другой обратимой операцией, например, сложением:  K+m (mod p).

    На приемном конце операция расшифрования выполняется в два этапа. На первом этапе вычисляют ключ K, используя секретный ключ x(B):

                                 K = (a^k )^x(B) = (c₁)^x(B)    (mod p).                 

 

    На втором этапе восстанавливается сообщение “m” путем деления c₂ на K.

    Отметим, что параметры a и p могут быть одними и теми же для всех пользователей. Это приводит к экономии памяти для хранения открытых ключей абонентов (для каждого абонента “i” надо хранить всего один блок ключевой информации “y”).

    Если же параметры a и p будут свои для каждого пользователя, то это приведет к утроению объема файла, содержащего информацию об открытых ключах абонентов. Однако данный вариант организации связи с точки зрения безопасности связи представляется более надежным.

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

    Действительно, пусть

c_1,1 = a^k (mod p), c_2,1 = m₁ K (mod p),

                            c_1,2 = a^k mod p, c_2,2 = m₂ K (mod p).

 

    Тогда  

 

m₁  c_2,1

¾  = ¾  (mod p).  

m₂  c_2,2

 

    Следовательно, сообщение m₂ легко восстанавливается при известном m₁.

    Данная схема открытого шифрования с точки зрения криптографической безопасности эквивалентна схеме распределения ключей Диффи-Хеллмана. Действительно, если открытый текст “m” может быть вычислен по c₁, c₂  и y_B, тогда и K можно вычислить (т.е. раскрыть систему Диффи-Хеллмана).

    Попытка же вычислить k или x(B) по c₁, c₂, y_B  (даже при известном m) приводит к необходимости решать задачу дискретного логарифмирования.

 

Система Меркля – Хеллмана на основе задачи о ранце

 

    Пусть W = {w(1), ... , w(k)} - заданное множество целых чисел и S – их частичная сумма S = w(i₁) + ... + w(i_t), i₁< ... <i_t.

    Напомним, что задача о ранце состоит в отыскании w(i₁),...,w(i_t) при известных W и S.

    Хотя в общем случае эта задача является NP-полной, для некоторых множеств W эта задача решается весьма эффективно. Это имеет место, в частности, когда последовательность W = w(1),w(2), ...,w(k) является супервозрастающей, т.е. при всех i     

w(i+1) > w(1) + ... + w(i).

    Тогда восстановление w(i₁),...,w(i_t) при заданном S происходит следующим образом:     

    w(i_t) - это наибольшее число из W, не превосходящее S,

    w(i_t-1) - наибольшее число, не превосходящее S-w(i_t) и т.д.

    Одна из первых СОШ, основанная на проблеме укладки ранца, была предложена в 1978 году и заключается в следующем.

    Пусть W = {w₁, ... , w_k} - супервозрастающая последовательность,   n = w₁ + ... + w_k . Выбираем целое M случайным образом из промежутка между n и 2n, а также случайное целое число aÎ{0,1,..,M-1}, взаимно простое с M. Вычисляем b = a^-1 (mod M). Выбираем случайную перестановку p чисел {1,2,…,k}.

    Пусть

v_i =a×w_p(i) (mod M), 1£ i £ k.

    Набор V = {v₁, ... ,v_k} помещается в открытый справочник.

    Секретным ключом является набор (b, M, W, p).

    Открытый текст “m” представляется в двоичной форме вектором длины k:

m = (x₁, x₂, ... , x_k), x_i = 0,1.

    Тогда шифрованным текстом для сообщения “m” будет число

                                 y = v_i(1) + ... + v_i(t) ,                    

где i(1), ... , i(t) - номера единичных координат вектора m = (x₁, ... , x_k).

    Процесс расшифрования заключается в следующем. Имеем соотношения:

                                 y º a×w_p(i(1)) + ... + a×w_p(i(t)) (mod M),                 

                                 b×y º w_p(i(1)) + ... + w_p(i(t)) (mod M).                 

    Так как M > w_p(i(1)) + w_p(i(2)) + ... + w_p(i(t)) , то

                                 b×y (mod M) = w_p(i(1)) + w_p(i(2)) + ... + w_p(i(t)).

    Отсюда, учитывая свойство супервозрастания последовательности W = {w₁, w₂, ... , w_k}, легко восстанавливаются индексы p(i(1)), ... , p(i(t)), откуда находятся единичные координаты i(1), ... , i(t) открытого сообщения “m”.

    Главным достоинством данной СОШ (как и всех систем, основанных на проблеме ранца) является простота процессов зашифрования - расшифрования. Однако, как показано в [8], данная криптосистема может быть эффективно дешифрована.

 

---

Дата добавления: 2019-02-12; просмотров: 136; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!