Криптосистема Пэйе

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Схема является аддитивной гомоморфной криптосистемой, то есть зная только открытый ключ и шифротексты, соответствующие открытым текстам m_1 и m_2, мы можем вычислить шифротекст открытого текста m_1+m_2.[2]

История[править | править вики-текст]

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

Описание алгоритма[править | править вики-текст]

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

Генерация ключей[править | править вики-текст]

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

Шифрование[править | править вики-текст]

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

Расшифрование[править | править вики-текст]

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

Электронная подпись[править | править вики-текст]

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

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

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

 s_1 = \frac{L(h(m)^\lambda \bmod n^2)} {L(g^\lambda \bmod n^2)} \bmod n

 s_2 = (h(m)g^{-s_1})^{\frac{1}{n} \bmod \lambda} \bmod n

Электронной подписью будет пара  (s_1,s_2) .

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

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

 h(m) = g^{s_1}s^n_2 \bmod n^2 .

Гомоморфные свойства[править | править вики-текст]

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

  • Гомоморфное сложение открытых текстов
Произведение двух шифротекстов будет расшифровано как сумма соответствующих их открытых текстов,
D(E(m_1, r_1)\cdot E(m_2, r_2)\bmod n^2) = m_1 + m_2 \bmod n. \,
Умножив шифротекст на g^{m_2} мы получим сумму соответствующих открытых текстов,
D(E(m_1, r_1)\cdot g^{m_2} \bmod n^2) = m_1 + m_2 \bmod n. \,
  • Гомоморфное умножение открытых текстов
Шифротекст, возведенный в степень, равную другому шифротексту, будет расшифрован как произведение двух открытых текстов,
D(E(m_1, r_1)^{m_2}\bmod n^2) = m_1 m_2 \bmod n, \,
D(E(m_2, r_2)^{m_1}\bmod n^2) = m_1 m_2 \bmod n. \,
В общем случае, возведение шифротекста в степень k, будет расшифровано как произведение исходного текста на k,
D(E(m_1, r_1)^k\bmod n^2) = k m_1 \bmod n. \,

Обобщение[править | править вики-текст]

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

Генерация ключей[править | править вики-текст]

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

Шифрование[править | править вики-текст]

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

Расшифрование[править | править вики-текст]

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

Применение[править | править вики-текст]

Электронное голосование[править | править вики-текст]

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

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

Электронная лотерея[править | править вики-текст]

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

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

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

Электронная валюта[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols, " Chapman & Hall/CRC, 2007
  2. 1 2 Варновский Н. П., Шокуров А. В. «Гомоморфное шифрование», 2007
  3. 1 2 Pascal Paillier, «Public-Key Cryptosystems Based on Composite Degree Residuosity Classes»,1999
  4. Pierre-Alain Fouque and David Pointcheval, «Threshold Cryptosystems Secure against Chosen-Ciphertext Attacks»,2001
  5. Lan Nguyen,Rei Safavi-Naini, Kaoru Kurosawa ,"A Provably Secure and Efficient Verifiable Shuffle based on a Variant of the Paillier Cryptosystem", 2006
  6. Jurik M., Damgård I. «A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System»,1999
  7. 1 2 P.-A.,Poupard G.,Stern J.,"Sharing Decryption in the Context of Voting or Lotteries",2001
  8. 1 2 Jurik M. J., «Extensions to the paillier cryptosystem with applications to cryptological protocols», 2003

Литература[править | править вики-текст]

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

Ссылки[править | править вики-текст]