Система Orphus

El Gamal

Создание пары из секретного и открытого ключей

  1. выбрать простое случайное число p (обычно длинной 1024 бита).
  2. выбирать генератор g\in \mathbb{Z}^*_p (в программных реализациях алгоритма генератор часто фиксирован малым числом, например g=2~\bmod~p).
  3. случайно выбрать x\in[1, p-1].
  4. вычислить y=g^x~\bmod~p,
  5. создать открытый ключ \mathrm{PK}=\{p,g,y\}
  6. создаеть секретный ключ \mathrm{SK}=\{x\}

Криптостойкость задается битовой длиной параметра p.

Шифрование

Процесс шифрования

Шифрующая сторона:

  1. извлечь открытый ключ \mathrm{PK}=\{p,g,y\} из директории стороны A.
  2. Сообщение представляется числом m\in[1,p-1].
  3. выбирать случайное число r\in[1,p-1] и вычислить
    a=g^r~\bmod~p,
    b=my^r~\bmod~p.
  4. получает шифрованное сообщение в виде
    c=\{a, b\}

Процесс расшифровывания

Принимающая сторона

  1. получает зашифрованное сообщение c=\{a,b\}
  2. сторона A вычисляет:
    m=\frac{b}{a^x}~\bmod~p.

Подпись

Процесс подписи

При работе в режиме подписи предполагается наличие фиксированной хеш-функции h(\cdot)\in[0,p-2].

  1. Вычисляет дайджест сообщения M:
    m=h(M)
  2. Выбирает случайное число r взаимно простое с p-1
  3. Вычислить:
    a=g^r~\bmod~p.
  4. Вычисляется число:
    b=\dfrac{m-xa}{r}~\bmod~(p-1).
  5. Получаем подпись сообщения M в виде пары \{a,b\}.

Проверка подписи

Зная открытый ключ \{p,g,y\}, подпись \{a,b\} сообщения M проверяется следующим образом:

  1. Вычислить дайджест
    m=h(M).
  2. Проверить, выполнение условия:
    y^aa^b=g^m~\bmod~p.

Система Orphus

Комментарии