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

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

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

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

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

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

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

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

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

  1. Выбираются два больших простых числа и , такие, что .
  2. Вычисляется и .
  3. Выбирается случайное целое число , такое что
  4. Вычисляется , где .
  • Открытым ключом является пара .
  • Закрытым ключом является пара

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

  1. Предположим, что необходимо зашифровать открытый текст ,
  2. Выбираем случайное число ,
  3. Вычисляем шифротекст

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

  1. Принимаем шифротекст
  2. Вычисляем исходное сообщение

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

Для работы в режиме электронной подписи требуется наличие хэш-функции .

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

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

Электронной подписью будет пара .

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

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

.

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

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

  • Гомоморфное сложение открытых текстов
Произведение двух шифротекстов будет расшифровано как сумма соответствующих их открытых текстов,
Умножив шифротекст на мы получим сумму соответствующих открытых текстов,
  • Гомоморфное умножение открытых текстов
Шифротекст, возведенный в степень, равную другому шифротексту, будет расшифрован как произведение двух открытых текстов,
В общем случае, возведение шифротекста в степень , будет расшифровано как произведение исходного текста на ,

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

В 2001 году Иван Дамгард[en] и Мадс Юрик предложили обобщение[6] криптосистемы Пэйе. Для этого предлагается вести вычисления по модулю , где , - натуральное число. Измененный алгоритм выглядит следующим образом:

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

  1. Случайно и независимо друг от друга выбираются два больших простых числа и .
  2. Вычисляется и .
  3. Выбирается число , такое, что , где известное взаимно простое число с и .
  4. Используя китайскую теорему об остатках, выбирается такое, что и . Например, может быть равен из оригинальной криптосистемы Пэйе.
  • Открытым ключом является пара .
  • Закрытым ключом является .

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

  1. Допустим мы хотим зашифровать сообщение , где .
  2. Выбираем случайное число такое, что .
  3. Вычисляем шифротекст .

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

  1. Пусть у нас есть шифротекст и мы хотим его расшифровать.
  2. Вычисляем . Если действительно является шифротекстом, то выполнены равенства: .
  3. Применяем рекурсивную версию механизма расшифрования криптосистемы Пэйе для получения . Так как произведение известно, мы можем вычислить .

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

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

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

  1. Пусть  — число избирателей и такое, что .
  2. Если избиратель хочет проголосовать за кандидата номер , то он шифрует число и передает полученный шифротекст координатору выборов.
  3. При подведении итогов выборов координатор дешифрует произведение всех шифротекстов, полученных от избирателей. Несложно заметить, что первые бит результата будут давать число голосов, отданных за первого кандидата, вторые бит будут давать число голосов, отданных за второго кандидата, и так далее.

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

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

  1. Пусть игроков хотят поучаствовать в лотерее, каждый имеет свой лотерейный билет с уникальным номером .
  2. Каждый игрок выбирает случайное число, шифрует и передает организатору лотереи.
  3. Для того чтобы вычислить «счастливый» билет, организатор дешифрует произведение всех полученных шифротекстов, получая при этом сумму случайных чисел, сгенерированных игроками. Организатор лотереи объявляет победителем билет с номером .

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

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

Еще одной отличительной особенностью криптосистемы Пэйе является так называемое самоослепление[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.

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