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

Генерация ключей

1. Выбираются два больших простых числа ${\displaystyle p}$ и ${\displaystyle q}$ , такие, что ${\displaystyle \gcd(pq,(p-1)(q-1))=1}$ .
2. Вычисляется ${\displaystyle n=pq}$ и ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$ .
3. Выбирается случайное целое число ${\displaystyle g}$ , такое что ${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$
4. Вычисляется ${\displaystyle \mu =(L(g^{\lambda }\mod n^{2}))^{-1}{\bmod {n}}}$ , где ${\displaystyle L(u)=div({\frac {u-1}{n}})}$ .

• Открытым ключом является пара ${\displaystyle (n,g)}$ .
• Закрытым ключом является пара ${\displaystyle (\lambda ,\mu ).}$

Шифрование

1. Предположим, что необходимо зашифровать открытый текст ${\displaystyle m}$ , ${\displaystyle m\in \mathbb {Z} _{n}}$
2. Выбираем случайное число ${\displaystyle r}$ , ${\displaystyle r\in \mathbb {Z} _{n}^{*}}$
3. Вычисляем шифротекст ${\displaystyle c=g^{m}\cdot r^{n}{\bmod {n}}^{2}}$

Расшифрование

1. Принимаем шифротекст ${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. Вычисляем исходное сообщение ${\displaystyle m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}}$

Электронная подпись

Для работы в режиме электронной подписи требуется наличие хеш-функции ${\displaystyle h:\mathbb {N} \mapsto \{0,1\}^{k}\subset \mathbb {Z} _{n^{2}}^{*}}$ .

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

Для того, чтобы подписать сообщение ${\displaystyle m}$ , необходимо вычислить

${\displaystyle s_{1}={\frac {L(h(m)^{\lambda }{\bmod {n}}^{2})}{L(g^{\lambda }{\bmod {n}}^{2})}}{\bmod {n}}}$

${\displaystyle s_{2}=(h(m)g^{-s_{1}})^{{\frac {1}{n}}{\bmod {\lambda }}}{\bmod {n}}}$

Электронной подписью будет пара ${\displaystyle (s_{1},s_{2})}$ .

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

Подпись считается верной, если выполнено следующее условие:

${\displaystyle h(m)=g^{s_{1}}s_{2}^{n}{\bmod {n}}^{2}}$ .

Генерация ключей

1. Случайно и независимо друг от друга выбираются два больших простых числа ${\displaystyle p}$ и ${\displaystyle q}$ .
2. Вычисляется ${\displaystyle n=pq}$ и ${\displaystyle \lambda =\operatorname {lcm} (p-1,q-1)}$ .
3. Выбирается число ${\displaystyle g\in \mathbb {Z} _{n^{s+1}}^{*}}$ , такое, что ${\displaystyle g=(1+n)^{j}x{\bmod {n}}^{s+1}}$ , где ${\displaystyle j}$ известное взаимно простое число с ${\displaystyle n}$ и ${\displaystyle x\in H}$ .
4. Используя китайскую теорему об остатках, выбирается ${\displaystyle d}$ такое, что ${\displaystyle d{\bmod {n}}\in \mathbb {Z} _{n}^{*}}$ и ${\displaystyle d=0{\bmod {\lambda }}}$ . Например, ${\displaystyle d}$ может быть равен ${\displaystyle \lambda }$ из оригинальной криптосистемы Пэйе.

• Открытым ключом является пара ${\displaystyle (n,g)}$ .
• Закрытым ключом является ${\displaystyle d}$ .

Шифрование

1. Допустим мы хотим зашифровать сообщение ${\displaystyle m}$ , где ${\displaystyle m\in \mathbb {Z} _{n^{s}}}$ .
2. Выбираем случайное число ${\displaystyle r}$ такое, что ${\displaystyle r\in \mathbb {Z} _{n^{s+1}}^{*}}$ .
3. Вычисляем шифротекст ${\displaystyle c=g^{m}\cdot r^{n^{s}}{\bmod {n}}^{s+1}}$ .

Расшифрование

1. Пусть у нас есть шифротекст ${\displaystyle c\in \mathbb {Z} _{n^{s+1}}^{*}}$ и мы хотим его расшифровать.
2. Вычисляем ${\displaystyle c^{d}\;mod\;n^{s+1}}$ . Если ${\displaystyle c}$ действительно является шифротекстом, то выполнены равенства: ${\displaystyle c^{d}=(g^{m}r^{n^{s}})^{d}=((1+n)^{jm}x^{m}r^{n^{s}})^{d}=(1+n)^{jmd\;bmod\;n^{s}}(x^{m}r^{n^{s}})^{d\;bmod\;\lambda }=(1+n)^{jmd\;bmod\;n^{s}}}$ .
3. Применяем рекурсивную версию механизма расшифрования криптосистемы Пэйе для получения ${\displaystyle jmd}$ . Так как произведение ${\displaystyle jd}$ известно, мы можем вычислить ${\displaystyle m=(jmd)\cdot (jd)^{-1}\;bmod\;n^{s}}$ .

Электронное голосование

Используя криптосистему Пэйе можно организовать выборы между несколькими кандидатами, используя следующую схему: ^{[7] [8]}

1. Пусть ${\displaystyle N}$  — число избирателей и ${\displaystyle k\in \mathbb {N} }$ такое, что ${\displaystyle N<2^{k}}$ .
2. Если избиратель хочет проголосовать за кандидата номер ${\displaystyle i}$ , то он шифрует число ${\displaystyle 2^{k(i-1)}}$ и передает полученный шифротекст координатору выборов.
3. При подведении итогов выборов координатор дешифрует произведение всех шифротекстов, полученных от избирателей. Несложно заметить, что первые ${\displaystyle k}$ бит результата будут давать число голосов, отданных за первого кандидата, вторые ${\displaystyle k}$ бит будут давать число голосов, отданных за второго кандидата, и так далее.

Электронная лотерея

При помощи криптосистемы Пэйе можно организовать проведение электронной лотереи следующим образом:^[7][8]

1. Пусть ${\displaystyle N}$ игроков хотят поучаствовать в лотерее, каждый имеет свой лотерейный билет с уникальным номером ${\displaystyle n\in \{0,\dots ,N-1\}}$ .
2. Каждый игрок выбирает случайное число, шифрует и передает организатору лотереи.
3. Для того чтобы вычислить «счастливый» билет, организатор дешифрует произведение всех полученных шифротекстов, получая при этом сумму ${\displaystyle s}$ случайных чисел, сгенерированных игроками. Организатор лотереи объявляет победителем билет с номером ${\displaystyle s{\bmod {n}}}$ .

Несложно заметить, что у всех участников вероятности выигрыша будут равны даже если ${\displaystyle n-1}$ игроков попытаются сфальсифицировать итог лотереи, отправив организатору заранее подготовленные числа.

Электронная валюта

Еще одной отличительной особенностью криптосистемы Пэйе является так называемое самоослепление^[en]. Под этим термином понимают способность изменения шифротекста без изменения открытого текста. Это может быть использовано при разработке систем электронной валюты, например таких как ecash^[en]. Допустим вы хотите оплатить товар онлайн, но не хотите сообщать продавцу номер своей кредитной карты, и, следовательно, свою личность. Как и в случае с электронным голосованием, мы можем проверить правильность электронной монеты(или электронного голоса), не раскрывая при этом личность человека, с которым сейчас она связана.