MulFullIdent — полный мультилинейный алгоритм шифрования на основе идентификационных данных. Протокол построен на основе метода Фуджисаки-Окамото, предложенного в 1999 году. Алгоритм является улучшением протокола MulBasicIdent.
Параметры протокола
Введены следующие обозначения для параметров и групп, использующихся в алгоритме:
- n {displaystyle n} — число участвующих в генерации общего ключа сторон;
- I D i {displaystyle ID_{i}} — уникальное двоичное число (идентификатор) пользователя с номером i {displaystyle i} ;
- G 1 {displaystyle G_{1}} — аддитивная циклическая группа;
- G 2 {displaystyle G_{2}} — мультипликативная циклическая группа.
Группы G 1 {displaystyle G_{1}} и G 2 {displaystyle G_{2}} используются для дальнейшего построения мультилинейного отображения.
Описание алгоритма
Протокол представлен этапами инициализации, получения закрытого ключа, шифрования и расшифрования. Пусть k ∈ Z {displaystyle kin mathbb {Z} } — принимаемый алгоритмом на этапе инициализации параметр стойкости.
Инициализация
На основе k {displaystyle k} Центром генерации закрытых ключей (PKG) вырабатывается простой порядок q {displaystyle q} групп G 1 {displaystyle G_{1}} и G 2 {displaystyle G_{2}} , 2 n {displaystyle 2n} -мультилинейное отображение μ : G 1 × G 1 × … × G 1 ⏟ 2 n → G 2 {displaystyle mu colon underbrace {G_{1} imes G_{1} imes ldots imes G_{1}} _{2n} o G_{2}} и произвольный образующий элемент группы P ∈ G 1 {displaystyle Pin G_{1}} . Центром PKG случайным образом выбираются элементы s 1 , … , s n ∈ Z q ∗ {displaystyle s_{1},ldots ,s_{n}in mathbb {Z} _{q}^{*}} и вычисляется набор открытых ключей P p u b 1 = s 1 P , … , P p u b n = s n P ∈ G 1 {displaystyle P_{pub_{1}}=s_{1}P,ldots ,P_{pub_{n}}=s_{n}Pin G_{1}} . Центром PKG выбираются криптографические хеш-функции H 1 : { 0 , 1 } ∗ → G 1 ∗ {displaystyle H_{1}colon {0,1}^{*} o G_{1}^{*}} и H 2 : G 2 → { 0 , 1 } l {displaystyle H_{2}colon G_{2} o {0,1}^{l}} для некоторого l ∈ Z {displaystyle lin mathbb {Z} } , H 3 : { 0 , 1 } l × { 0 , 1 } l → Z q ∗ {displaystyle H_{3}:{0,1}^{l} imes {0,1}^{l} o mathbb {Z} _{q}^{*}} и H 4 : { 0 , 1 } l → { 0 , 1 } l {displaystyle H_{4}:{0,1}^{l} o {0,1}^{l}} . В данном алгоритме пространства сообщений и шифротекстов представляют собой множества ϑ = { 0 , 1 } l {displaystyle vartheta ={0,1}^{l}} и C = G 1 ∗ × { 0 , 1 } l × { 0 , 1 } l {displaystyle C=G_{1}^{*} imes {0,1}^{l} imes {0,1}^{l}} соответственно, элементы s 1 , … , s n ∈ Z q ∗ {displaystyle s_{1},ldots ,s_{n}in mathbb {Z} _{q}^{*}} являются мастер-ключами абонентов, а системными параметрами является набор ⟨ G 1 , G 2 , μ , l , P , P p u b 1 , … , P p u b n , H 1 , H 2 , H 3 , H 4 ⟩ {displaystyle langle G_{1},G_{2},mu ,l,P,P_{pub_{1}},ldots ,P_{pub_{n}},H_{1},H_{2},H_{3},H_{4}
angle } .
Получение закрытого ключа
Для идентификаторов абонентов I D 1 , … , I D n ∈ { 0 , 1 } ∗ {displaystyle ID_{1},ldots ,ID_{n}in {0,1}^{*}} Центр PKG вычисляет Q I D 1 = H 1 ( I D 1 ) ∈ G 1 ∗ , … , Q I D n = H 1 ( I D n ) ∈ G 1 ∗ {displaystyle Q_{ID_{1}}=H_{1}(ID_{1})in G_{1}^{*},ldots ,Q_{ID_{n}}=H_{1}(ID_{n})in G_{1}^{*}} . Центр PKG вычисляет и передает абонентам по защищенному каналу закрытые ключи d I D 1 = s 1 Q I D 1 , … , d I D n = s n Q I D n {displaystyle d_{ID_{1}}=s_{1}Q_{ID_{1}},ldots ,d_{ID_{n}}=s_{n}Q_{ID_{n}}} , d I D i ∈ G 1 {displaystyle d_{ID_{i}}in G_{1}} , где s 1 , … , s n {displaystyle s_{1},ldots ,s_{n}} — мастер-ключи. Шифрование
Для шифрования сообщения M {displaystyle M} с помощью идентификаторов I D 1 , … , I D n ∈ { 0 , 1 } ∗ : {displaystyle ID_{1},ldots ,ID_{n}in {0,1}^{*}:} абонент выполняет следующие операции:
Вычисляет Q I D 1 = H 1 ( I D 1 ) ∈ G 1 ∗ , … , Q I D n = H 1 ( I D n ) ∈ G 1 ∗ {displaystyle Q_{ID_{1}}=H_{1}(ID_{1})in G_{1}^{*},ldots ,Q_{ID_{n}}=H_{1}(ID_{n})in G_{1}^{*}} . Выбирает случайный вектор σ ∈ { 0 , 1 } l , l ∈ Z {displaystyle sigma in {0,1}^{l},lin mathbb {Z} } . Вычисляет r = H 3 ( σ , M ) , r ∈ Z q ∗ {displaystyle r=H_{3}(sigma ,M),rin mathbb {Z} _{q}^{*}} . Вычисляет шифротекст C = ⟨ r P , σ ⊕ H 2 ( g r ) , M ⊕ H 4 ( σ ) ⟩ {displaystyle C=langle rP,sigma oplus H_{2}(g^{r}),Moplus H_{4}(sigma )
angle } , где g = μ ( Q I D 1 , … , Q I D n , P p u b 1 , … , P p u b n ) ∈ G 2 ∗ {displaystyle g=mu (Q_{ID_{1}},ldots ,Q_{ID_{n}},P_{pub_{1}},ldots ,P_{pub_{n}})in G_{2}^{*}} . Расшифрование
Для расшифрования шифротекста C = ⟨ U , V , W ⟩ {displaystyle C=langle U,V,W
angle } абонентом с идентификатором I D i {displaystyle ID_{i}} с помощью закрытого ключа d I D i ∈ G 1 ∗ {displaystyle d_{ID_{i}}in G_{1}^{*}} выполняются следующие процедуры.
Если U ∉ G 1 ∗ {displaystyle U
otin G_{1}^{*}} , то шифротекст не принимается. В противном случае, с помощью закрытого ключа d I D i ∈ G 1 ∗ {displaystyle d_{ID_{i}}in G_{1}^{*}} вычисляется V ⊕ H 2 ( μ ( Q I D 1 , … , Q I D i − 1 , d I D i , Q I D i + 1 , … , Q I D n , P p u b 1 , … , P p u b i − 1 , U , P p u b i + 1 , … , P p u b n ) ) = σ . {displaystyle Voplus H_{2}(mu (Q_{ID_{1}},ldots ,Q_{ID_{i-1}},d_{ID_{i}},Q_{ID_{i+1}},ldots ,Q_{ID_{n}},P_{pub_{1}},ldots ,P_{pub_{i-1}},U,P_{pub_{i+1}},ldots ,P_{pub_{n}}))=sigma .}
Абонентом вычисляется W ⊕ H 4 ( σ ) = M {displaystyle Woplus H_{4}(sigma )=M} . Абонентом вычисляется r = H 3 ( σ , M ) , r ∈ Z q ∗ {displaystyle r=H_{3}(sigma ,M),rin mathbb {Z} _{q}^{*}} и проверяется U = r P {displaystyle U=rP} . Если равенство не выполняется, то шифротекст не принимается, противном случае полагается, что M {displaystyle M} — открытый текст.
Корректность алгоритма потдверждается аналогично MulBasicIdent.