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

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 na poprawny szyfrogram (dla pewnych ograniczonych klas funkcji ) bez znajomości 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]

W szyfrach strumieniowych, szyfrogram jest wynikiem działania alternatywy wykluczającej na tekście jawnym oraz pseudolosowego strumienia bitów : , gdzie jest kluczem. Adwersarz może skonstruować szyfrogram dla dowolnego , ponieważ .

W algorytmie RSA, a tekst jawny jest zaszyfrowany jako , gdzie jest kluczem publicznym. Mając taki szyfrogram, adwersarz może skonstruować szyfrogram wiadomości dla dowolnego , ponieważ . Z tego powodu, RSA jest zazwyczaj używane ze schematami OAEP lub PKCS1.

W algorytmie ElGamal, tekst jawny jest zaszyfrowany jako , gdzie jest kluczem publicznym. Mając do dyspozycji szyfrogram , adwersarz może obliczyć , co jest poprawnym szyfrogramem wiadomości , dla dowolnego . Tymczasem kryptosystem Cramera-Shoupa (bazujący na ElGamalu) jest niedeformowalny.

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

Całkowita niedeformowalność[edytuj]

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.