Deformowalność (kryptografia)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 wiadomości m, adwersarz może wygenerować inny szyfrogram, który będzie odpowiadał wiadomości f(m) dla pewnej funkcji f, bez znajomości m.

Deformowalność jest często niepożądaną własnością w kryptosystemach ogólnego przeznaczenia, ponieważ umożliwia adwersarzowi zmianę zawartości wiadomości. Przykładowo, załóżmy, że bank używa szyfru strumieniowego do ukrycia informacji finansowych. Użytkownik wysyła zaszyfrowaną wiadomość zawierającą informacje dotyczące przelewu: "TRANSFER $0000100.00 NA KONTO #199". Jeśli adwersarz może zmodyfikować szyfrogram oraz zna format wiadomości, mógłby on zmienić kwotę oraz adresata transakcji: "TRANSFER $0100000.00 NA KONTO #227."

Z drugiej strony, niektóre kryptosystemy są projektowane w taki sposób, aby były deformowalne. Innymi słowy, w niektórych przypadkach możliwość zmiany szyfrogramu wiadomości m na poprawny szyfrogram f(m) (dla pewnych ograniczonych klas funkcji f) bez znajomości m może być pożądaną funkcjonalnością. Takie schematy szyfrowania znane są pod pojęciem 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ą.

Przykłady deformowalnych systemów[edytuj | edytuj kod]

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

W algorytmie RSA, a tekst jawny m jest zaszyfrowany jako E(m) = m^e \bmod n, gdzie (e,n) jest kluczem publicznym. Mając taki szyfrogram, adwersarz może skonstruować szyfrogram wiadomości mt dla dowolnego t, ponieważ 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 m jest zaszyfrowany jako E(m) = (g^b, m A^b), gdzie (g,A) jest kluczem publicznym. Mając do dyspozycji szyfrogram (c_1, c_2), adwersarz może obliczyć (c_1, t \cdot c_2), co jest poprawnym szyfrogramem wiadomości tm, dla dowolnego t. Tymczasem kryptosystem Cramera-Shoupa (bazujący na ElGamalu) jest niedeformowalny.

W kryptosystemach ElGamal oraz RSA, można połączyć szyfrogramy wiadomości m_1 oraz m_2 tak, aby uzyskać poprawny szyfrogram wiadomości m_1 m_2.

Całkowita niedeformowalność[edytuj | edytuj kod]

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. Innymi słowy, adwersarz nie powinien mieć możliwości wygenerowania szyfrogramu, którego odpowiadający mu tekst jawny jest związany z oryginalną wiadomością relacją, która uwzględnia klucz publiczny.

Przypisy

  1. Danny Dolev, Cynthia Dwork, Moni Naor. Nonmalleable Cryptography. „SIAM Journal on Computing”. 30 (2), s. 391–437, 2000. doi:10.1137/S0097539795291562.