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


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

Гольдвассер и Микали стали лауреатами Премии Тьюринга за 2012 год, создание криптосистемы с вероятностным шифрованием отмечено в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию.

Основы

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

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

Гольдвассер и Микали предложили схему вероятностного шифрования, обладающую этим свойством. Она шифрует всё сообщение бит за битом, причём вся сложность, связанная с поиском отдельного зашифрованного бита в тексте c, заключается в проверке, принадлежит число c множеству Q R N {displaystyle QR_{N}} или множеству J = { x ∈ Z N ∗ , ( x N ) } {displaystyle J={xin mathbb {Z} _{N}^{ast },left({frac {x}{N}} ight)}}

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

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

Чтобы установить параметры ключа, Алиса должна выполнить следующие операции :

  • Выбрать два случайных числа p {displaystyle p} и q {displaystyle q} , удовлетворяющих условию | p | = | q | {displaystyle |p|=|q|} бит
  • Вычислить значение N = p q {displaystyle N=pq}
  • Извлечь случайное целое число y {displaystyle y} , удовлетворяющее условию (символы Якоби) ( y p ) = ( y q ) = − 1 {displaystyle left({frac {y}{p}} ight)=left({frac {y}{q}} ight)=-1}
    (*Таким образом, y ∈ J ( N ) n Q R N {displaystyle yin J(N){mathcal {n}}QR_{N}} .*)
  • Описать пару ( N , y ) {displaystyle (N,y)} в качестве открытого ключа, а пару ( p , q ) {displaystyle (p,q)} сохранить в тайне как закрытый ключ.
  • Шифрование

    Чтобы послать Алисе строку m = b 1 b 2 … b l {displaystyle m=b_{1}b_{2}dots b_{l}} , Боб выполняет следующие операции:
    f o r ( i = 1 , 2 … , l ) {displaystyle for(i=1,2dots ,l)}

    {
    x ← U Z N ∗ ; {displaystyle xleftarrow _{U}mathbb {Z} _{N}^{ast };}
    i f ( b i == 0 ) c i ← x 2 ( m o d N ) ; {displaystyle if(b_{i}==0)c_{i}leftarrow x^{2}(modN);}
    e l s e   c i ← y x 2 ( m o d N ) ; {displaystyle else c_{i}leftarrow yx^{2}(modN);} }

    Боб посылает Алисе сообщение E N ( m ) ← ( c 1 , c 2 … , c l ) . {displaystyle E_{N}(m)leftarrow (c_{1},c_{2}dots ,c_{l}).}

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

    Получив кортеж ( c 1 , c 2 , … , c l ) {displaystyle (c_{1},c_{2},dots ,c_{l})} , Алиса выполняет следующие операции:
    f o r ( i = 1 , 2 … , l ) {displaystyle for(i=1,2dots ,l)}

    {
    i f ( c i ∈ Q R N ) b i ← 0 ; {displaystyle if(c_{i}in QR_{N})b_{i}leftarrow 0;}
    b i ← 1 ; {displaystyle b_{i}leftarrow 1;}
    }

    s e t   m ← ( b 1 , b 2 , … , b l ) . {displaystyle set mleftarrow (b_{1},b_{2},dots ,b_{l}).}

    Временная сложность алгоритма

    Для шифрования сообщения, состоящего из l {displaystyle l} бит, необходимо выполнить O ( l ( log 2 ⁡ N ) 2 ) {displaystyle O(l(log _{2}N)^{2})} побитовых операций. Это выражение представляет собой оценку временной сложности алгоритма. Степень расширения этого алгоритма равна log 2 ⁡ N {displaystyle log _{2}N} :одному биту исходного текста соответствуют log 2 ⁡ N {displaystyle log _{2}N} бит зашифрованного текста.
    Поскольку для вычисления символа Лежандра по модулю p {displaystyle p} и по модулю q {displaystyle q} при условии, что | p | = | q | = k {displaystyle |p|=|q|=k} необходимо выполнить O B ( k 2 ) {displaystyle O_{B}(k^{2})} побитовых операций, для расшифровки кортежа ( c 1 , c 2 , … c k ) {displaystyle (c_{1},c_{2},dots c_{k})} требуются O B ( ( log 2 ⁡ N ) 2 ) {displaystyle O_{B}((log _{2}N)^{2})} побитовых операций. Это выражение представляет собой оценку временной сложности расшифровки.

    Стойкость криптосистемы GM

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

    Нулевые биты в исходном тексте равномерно распределяются по множеству Q R N {displaystyle QR_{N}} , а единичные — по множеству J N ( 1 ) ∖ Q R N {displaystyle J_{N}(1)ackslash QR_{N}} .
    Оба распределения являются равномерными, поскольку для нулевого бита, содержащегося в исходном тексте, возведение в квадрат означает отображение группы Z N ∗ {displaystyle mathbb {Z} _{N}^{ast }} на множестве Q R N {displaystyle QR_{N}} , а для единичного бита умножение элемента множества Q R N {displaystyle QR_{N}} на число y {displaystyle y} является отображением из множества Q R N {displaystyle QR_{N}} на множество J N ( 1 ) ∖ Q R N {displaystyle J_{N}(1)ackslash QR_{N}} .

    Список литературы

    • Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6

  • Коуравнитель
  • Массы
  • RC4
  • Как выбрать плёнку для теплицы?
  • Эксплуатационные параметры лака ЭП-730

  •  

    • Яндекс.Метрика
    • Индекс цитирования