Криптосистема Пэйе — вероятностная криптосистема с открытым ключом , изобретенная французским криптографом Паскалем Пэйе ( англ. Pascal Paillier ) в 1999 году. Аналогично криптосистемам RSA , Гольдвассер — Микали и Рабина , криптосистема Пэйе основана на сложности факторизации составного числа , являющегося произведением двух простых чисел .

Схема является аддитивной гомоморфной криптосистемой, то есть зная только открытый ключ и шифротексты, соответствующие открытым текстам ${\displaystyle m_{1}}$ и ${\displaystyle m_{2}}$ , мы можем вычислить шифротекст открытого текста ${\displaystyle m_{1}+m_{2}}$ .

История

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

Описание алгоритма

Алгоритм работает следующим образом:

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

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}}$ .

Гомоморфные свойства

Отличительной особенностью криптосистемы Пэйе является её гомоморфность . Так как функция шифрования является аддитивно гомоморфной, могут быть записаны следующие тождества :

• Гомоморфное сложение открытых текстов

Произведение двух шифротекстов будет расшифровано как сумма соответствующих их открытых текстов,

${\displaystyle D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.}$

Умножив шифротекст на ${\displaystyle g^{m_{2}}}$ мы получим сумму соответствующих открытых текстов,

${\displaystyle D(E(m_{1},r_{1})\cdot g^{m_{2}}{\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}.}$

• Гомоморфное умножение открытых текстов

Шифротекст, возведенный в степень, равную другому шифротексту, будет расшифрован как произведение двух открытых текстов,

${\displaystyle D(E(m_{1},r_{1})^{m_{2}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}},}$

${\displaystyle D(E(m_{2},r_{2})^{m_{1}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}}.}$

В общем случае, возведение шифротекста в степень ${\displaystyle k}$ , будет расшифровано как произведение исходного текста на ${\displaystyle k}$ ,

${\displaystyle D(E(m_{1},r_{1})^{k}{\bmod {n}}^{2})=km_{1}{\bmod {n}}.}$

Обобщение

В 2001 году и Мадс Юрик предложили обобщение криптосистемы Пэйе. Для этого предлагается вести вычисления по модулю ${\displaystyle n^{s+1}}$ , где ${\displaystyle n=p*q}$ , ${\displaystyle s}$ - натуральное число . Измененный алгоритм выглядит следующим образом:

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

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}}$ .

Применение

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

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

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}$ бит будут давать число голосов, отданных за второго кандидата, и так далее.

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

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

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

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

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

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

Примечания

Литература

• Paillier P. (англ.) // Advances in cryptology, EUROCRYPT'99. — 1999. — P. 223-238 . — ISBN 978-3-540-48910-8 . — doi : . 17 декабря 2014 года.

• Fouque P.-A., Poupard G., Stern J. (англ.) // Financial Cryptography, Proceedings of 4th International Conference. — 2001. — P. 90-104 . — ISBN 978-3-540-45472-4 . — doi : .

• Jurik M. J. (англ.) // Public Key Cryptography. — 2003. — P. 119-136 .

• Jurik M., Damgård I. (англ.) // Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptosystems. — 2001. — P. 119-136 .

• Варновский Н. П., Шокуров А. В. (рус.) // Труды ИСП РАН. — 2007. — С. 27-36 .

• Katz J., Lindell Y. Introduction to Modern Cryptography: Principles and Protocols. — Chapman & Hall/CRC, 2007. — С. 385-395. — ISBN 978-1584885511 .

Ссылки