WikiSort.ru - Не сортированное

Алгоритм создания открытого и закрытого ключей

1. Центр доверия T выбирает два различных случайных простых числа ${\displaystyle p}$ и ${\displaystyle q}$ , после чего вычисляет их произведение ${\displaystyle n=p\cdot q}$ .
2. T выбирает целое число ${\displaystyle e}$ (${\displaystyle 1<e<\varphi (n)}$ ), взаимно простое со значением функции ${\displaystyle \varphi (n)}$ . Функция ${\displaystyle \varphi (n)}$ является функцией Эйлера.
3. T вычисляет ${\displaystyle s=e^{-1}\mod \varphi (n)}$ и секрет ${\displaystyle x=J^{-s}\mod n}$ .
4. T вычисляет ${\displaystyle y=x^{e}\mod n}$ .
5. Тройка ${\displaystyle \left\{n,e,y\right\}}$ публикуется в качестве открытого ключа.
6. ${\displaystyle x}$ играет роль закрытого ключа, и передается стороне A.

Обмен сообщениями

1. А выбирает случайное целое ${\displaystyle r}$ , находящееся в диапазоне от ${\displaystyle 1}$ до ${\displaystyle n-1}$ . А вычисляет ${\displaystyle a=r^{e}\mod n}$ и отправляет его В.
2. В выбирает случайное целое ${\displaystyle c}$ , находящееся в диапазоне от ${\displaystyle 0}$ до ${\displaystyle e-1}$ . В посылает ${\displaystyle c}$ стороне А.
3. А вычисляет ${\displaystyle z=rx^{c}\mod n}$ и посылает его В.
4. B проверяет: если ${\displaystyle z^{e}=ay^{c}\mod n}$ , то подлинность доказана.

Действительно ${\displaystyle z^{e}=(rx^{c})^{e}=r^{e}x^{ec}=r^{e}(x^{e})^{c}=ay^{c}\mod n}$ .

Подпись сообщения

Пусть А хочет подписать сообщение ${\displaystyle M}$ .

1. А выбирает случайное целое ${\displaystyle r}$ , находящееся в диапазоне от ${\displaystyle 1}$ до ${\displaystyle n-1}$ . А вычисляет ${\displaystyle a=r^{e}\mod n}$ .
2. А вычисляет ${\displaystyle d=H(M,a)}$ , где ${\displaystyle M}$  — подписываемое сообщение, а ${\displaystyle H(x)}$  — однонаправленная хеш-функция. Значение ${\displaystyle d}$ , полученное с помощью хеш-функции, должно быть в диапазоне от ${\displaystyle 0}$ до ${\displaystyle e-1}$ . Если выход хеш-функции выходит за этот диапазон, он должен быть приведен по модулю ${\displaystyle e}$ .
3. А вычисляет ${\displaystyle z=rx^{d}\mod n}$ . Подпись состоит из сообщения ${\displaystyle M}$ , двух вычисленных значений ${\displaystyle d}$ and ${\displaystyle z}$ , и её атрибутов ${\displaystyle J}$ . А посылает подпись B.

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

Пусть В хочет проверить подпись.

1. B вычисляет ${\displaystyle a'=z^{e}J^{d}\mod n}$ . Затем он вычисляет ${\displaystyle d'=H(M,a')}$ . Если ${\displaystyle d=d'}$ , то А знает B, и её подпись действительна.

Подпись сообщения

Пусть А и B хотят подписать сообщение ${\displaystyle M}$ .

1. А выбирает случайное целое ${\displaystyle r_{A}}$ , находящееся в диапазоне от ${\displaystyle 1}$ до ${\displaystyle n-1}$ . Она вычисляет ${\displaystyle a_{A}=r_{A}^{e}\mod n}$ и посылает B.
2. B выбирает случайное целое ${\displaystyle r_{B}}$ , находящееся в диапазоне от ${\displaystyle 1}$ до ${\displaystyle n-1}$ . Она вычисляет ${\displaystyle a_{B}=r_{B}^{e}\mod n}$ и посылает А.
3. А и B, каждый вычисляет ${\displaystyle a=(a_{A}\cdot a_{B})\mod n}$ .
4. А и B, каждый вычисляет ${\displaystyle d=H(M,a)}$ , где ${\displaystyle M}$  — подписываемое сообщение, а ${\displaystyle H(x)}$  — однонаправленная хеш-функция. Значение ${\displaystyle d}$ , полученное с помощью хеш-функции, должно быть в диапазоне от ${\displaystyle 0}$ до ${\displaystyle e-1}$ . Если выход хеш-функции выходит за этот диапазон, он должен быть приведен по модулю ${\displaystyle e}$ .
5. А вычисляет ${\displaystyle z_{A}=r_{A}x_{A}^{d}\mod n}$ и посылает B.
6. B вычисляет ${\displaystyle z_{B}=r_{B}x_{B}^{d}\mod n}$ и посылает А.
7. А и B, каждый вычисляет ${\displaystyle z=z_{A}z_{B}\mod n}$ . Подпись состоит из сообщения ${\displaystyle M}$ , двух вычисленных значений ${\displaystyle d}$ and ${\displaystyle z}$ , и атрибутов обоих подписывающих: ${\displaystyle J_{A}}$ и ${\displaystyle J_{B}}$ .

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

Пусть К хочет проверить подпись.

1. K вычисляет ${\displaystyle J=J_{A}J_{B}\mod n}$ .
2. К вычисляет ${\displaystyle a'=z^{e}J^{d}\mod n}$ . Затем она вычисляет ${\displaystyle d'=H(M,a')}$ . Если ${\displaystyle d=d'}$ , то множественная подпись действительна.

Этот протокол может быть расширен на любое количество людей. Для этого подписывающие сообщение люди должны перемножить свои значения ${\displaystyle a_{i}}$ на этапе (3), и свои значения ${\displaystyle z_{i}}$ на этапе (7). Чтобы проверить множественную подпись, нужно на этапе (1) перемножить значения ${\displaystyle J_{i}}$ подписывающих. Либо все подписи правильны, либо существует по крайней мере одна неправильная подпись.