Интернет магазин китайских планшетных компьютеров

Компьютеры - Криптосистема Голдвассера-Микали

криптографическая система с открытым ключом, разработанная Шафи Голдвассером и Сильвио Микали в 1982 году. GM является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэфективной, так как шифртекст может быть в сотни раз длинее чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Голдвассер и Микали ввели широко используемое понятие семантической стойкости.

Основы

Понятие стойкости по отношению к атаке IND-CPA впервые было предложено Голдвассером и Микали. Они назвали это понятие семантической стойкостью. Оно заключается в том, что зашифрованный текст не допускает никакой утечки полезной информации об исходном тексте ни одному взломщику, обладающему полиномиально ограниченными вычислительными ресурсами. Голдвассер и Микали обнаружили, что во многих приложениях собщения могут содержать априорную информацию, полезную для организации атак. Например, зашифрованный текст может содержать только одну простую инструкцию.Голдвассер и Микали указали на то, что криптосистемы с открытым ключом, основаные на непосредственном применении однонаправленных функции с секретом, как правило, очень слабо скрывают такие сообщения.

Свойство.Все элементы открытого текста, которые можно эффективно вычислить по заданному зашифрованному тексту, можно эффективно вычислить и без него .

Голдвассер и Микали предложили схему вероятностного шифрования, обладающую этим свойством. Изобретенная ими схема называется криптосистемой GM. Она шифрует все сообщение бит за битом, причем вся сложность, связанная с поиском отдельного зашифрованного бита в тексте c, заключается в проверке, принадлежит число c множеству или множеству