Deformowalność (kryptografia)

Deformowalność – własność pewnych algorytmów kryptograficznych^[1]. Algorytm jest deformowalny, jeśli adwersarz ma możliwość zmiany szyfrogramu bez znajomości tekstu jawnego. Innymi słowy: mając szyfrogram komunikatu ${\displaystyle m}$ adwersarz może wygenerować inny szyfrogram, który będzie odpowiadał komunikatowi ${\displaystyle f(m)}$ dla pewnej funkcji ${\displaystyle f,}$ bez znajomości ${\displaystyle m.}$

W kryptosystemach ogólnego przeznaczenia deformowalność jest często cechą niepożądaną, ponieważ umożliwia adwersarzowi zmianę zawartości komunikatu. Załóżmy dla przykładu, że bank używa szyfru strumieniowego do ukrycia informacji finansowych. Użytkownik wysyła zaszyfrowany komunikat z informacją „PRZELEJ 0000100,00 ZŁ NA KONTO NR 199”. Jeśli adwersarz może zmodyfikować szyfrogram oraz zna format komunikatu, mógłby on zmienić kwotę oraz adresata transakcji na, dajmy na to, „PRZELEJ 0100000,00 ZŁ NA KONTO NR 227”.

Z drugiej strony istnieją kryptosystemy celowo projektowane jako deformowalne. Innymi słowy, w niektórych przypadkach, możliwość zmiany szyfrogramu komunikatu ${\displaystyle m}$ na poprawny szyfrogram ${\displaystyle f(m)}$ (dla pewnych ograniczonych klas funkcji ${\displaystyle f}$) bez znajomości ${\displaystyle m}$ może być pożądana. Takie schematy szyfrowania znane są pod nazwą szyfrowania homomorficznego.

Kryptosystem może być semantycznie bezpieczny wobec ataków z wybranym tekstem jawnym, lecz nadal deformowalny. Podatność na adaptywny atak z wybranym szyfrogramem jest natomiast jednoznaczna z niedeformowalnością.

W szyfrach strumieniowych szyfrogram jest wynikiem działania alternatywy wykluczającej na tekście jawnym ${\displaystyle m}$ oraz pseudolosowego strumienia bitów ${\displaystyle S{:}}$ ${\displaystyle E(m)=m\oplus S(k),}$ gdzie ${\displaystyle k}$ jest kluczem. Adwersarz może skonstruować szyfrogram ${\displaystyle m\oplus t}$ dla dowolnego ${\displaystyle t,}$ ponieważ ${\displaystyle E(m)\oplus t=m\oplus t\oplus S(k)=E(m\oplus t).}$

W algorytmie RSA tekst jawny ${\displaystyle m}$ jest zaszyfrowany za pomocą przekształcenia ${\displaystyle E(m)=m^{e}{\bmod {n}},}$ gdzie ${\displaystyle (e,n)}$ jest kluczem publicznym. Mając taki szyfrogram adwersarz może skonstruować szyfrogram komunikatu ${\displaystyle mt}$ dla dowolnego ${\displaystyle t,}$ ponieważ ${\displaystyle E(m)\cdot t^{e}{\bmod {n}}=(mt)^{e}{\bmod {n}}=E(mt).}$ Z tego powodu RSA jest zazwyczaj używane ze schematami OAEP lub PKCS1.

W algorytmie ElGamal tekst jawny ${\displaystyle m}$ jest zaszyfrowany funkcją ${\displaystyle E(m)=(g^{b},mA^{b}),}$ gdzie ${\displaystyle (g,A)}$ jest kluczem publicznym. Mając do dyspozycji szyfrogram ${\displaystyle (c_{1},c_{2}),}$ adwersarz może obliczyć ${\displaystyle (c_{1},t\cdot c_{2}),}$ co jest poprawnym szyfrogramem komunikatu ${\displaystyle tm,}$ dla dowolnego ${\displaystyle t.}$ Dla odmiany kryptosystem Cramera-Shoupa (oparty na ElGamalu) jest niedeformowalny.

W kryptosystemach ElGamal oraz RSA można tak połączyć szyfrogramy komunikatów ${\displaystyle m_{1}}$ oraz ${\displaystyle m_{2},}$ aby uzyskać poprawny szyfrogram komunikatu ${\displaystyle m_{1}m_{2}.}$

W 2005 roku Fishlin zdefiniował pojęcie całkowitej niedeformowalności jako zdolność systemu do pozostania niedeformowalnym nawet w przypadku, gdy adwersarz otrzymuje możliwość wybrania nowego klucza publicznego. Oznacza to, że adwersarz nie powinien mieć możliwości wygenerowania szyfrogramu, którego odpowiadający mu tekst jawny jest związany z oryginalnym komunikatem relacją uwzględniającą klucz publiczny.