Cramer – Shoup cryptosystem - Cramer–Shoup cryptosystem

System Cramer – Shoup jest asymetrycznym algorytmem szyfrowania klucza i był pierwszym skutecznym schematem, który okazał się zabezpieczony przed adaptacyjnym atakiem wybranego szyfrogramu przy użyciu standardowych założeń kryptograficznych. Jego bezpieczeństwo opiera się na obliczeniowej niewykonalności (powszechnie zakładanej, ale nie udowodnionej) decyzyjnego założenia Diffiego – Hellmana. Opracowany przez Ronalda Cramera i Victora Shoupa w 1998 roku jest rozszerzeniem kryptosystemu ElGamal. W przeciwieństwie do ElGamala, który jest niezwykle plastyczny, Cramer – Shoup dodaje inne elementy, aby zapewnić brak plastyczności nawet w obliczu zaradnego napastnika. Ta nieciągłość jest osiągana dzięki zastosowaniu uniwersalnej jednokierunkowej funkcji skrótu i ​​dodatkowych obliczeń, w wyniku czego tekst zaszyfrowany jest dwa razy większy niż w ElGamal.

Adaptacyjne wybrane ataki szyfrogramem

Definicja bezpieczeństwa osiągnięta przez Cramera-Shoupa jest formalnie określana jako „ nierozróżnialność w ramach ataku adaptacyjnego wybranego tekstu zaszyfrowanego ” (IND-CCA2). Ta definicja bezpieczeństwa jest obecnie najsilniejszą znaną definicją kryptosystemu klucza publicznego: zakłada, że ​​atakujący ma dostęp do wyroczni deszyfrującej, która odszyfruje dowolny zaszyfrowany tekst za pomocą tajnego klucza deszyfrującego schematu. „Adaptacyjny” składnik definicji bezpieczeństwa oznacza, że ​​atakujący ma dostęp do tej wyroczni deszyfrującej zarówno przed, jak i po zaobserwowaniu określonego szyfrogramu celu do ataku (chociaż nie wolno mu używać wyroczni do prostego odszyfrowania tego docelowego tekstu zaszyfrowanego). Słabsze pojęcie bezpieczeństwa przed nieadaptacyjnymi atakami wybranym szyfrogramem (IND-CCA1) umożliwia napastnikowi jedynie dostęp do wyroczni deszyfrującej przed obserwacją docelowego tekstu zaszyfrowanego.

Chociaż dobrze było wiadomo, że wiele szeroko używanych kryptosystemów było niezabezpieczonych przed takim napastnikiem, przez wiele lat projektanci systemów uważali ten atak za niepraktyczny i mający duże znaczenie teoretyczne. Zaczęło się to zmieniać pod koniec lat 90. XX wieku, zwłaszcza gdy Daniel Bleichenbacher zademonstrował praktyczny, adaptacyjny atak na wybrany zaszyfrowany tekst na serwery SSL przy użyciu formy szyfrowania RSA .

Cramer – Shoup nie był pierwszym schematem szyfrowania zapewniającym ochronę przed adaptacyjnym atakiem wybranym szyfrogramem. Naor – Yung, Rackoff – Simon i Dolev – Dwork – Naor zaproponowali, w sposób dający się udowodnić, bezpieczną konwersję schematów standardowych (IND-CPA) na schematy IND-CCA1 i IND-CCA2. Techniki te są bezpieczne w ramach standardowego zestawu założeń kryptograficznych (bez przypadkowych wyroczni), jednak opierają się na złożonych technikach dowodzenia wiedzy zerowej i są nieefektywne pod względem kosztów obliczeniowych i rozmiaru szyfrogramu. Wiele innych metod, łącznie Bellare / Rogaway „s OAEP i Fujisaki-Okamoto osiągnąć wydajne konstrukcje za pomocą abstrakcji matematycznej znanej jako losowej wyroczni . Niestety implementacja tych schematów w praktyce wymaga zastąpienia jakiejś praktycznej funkcji (np. Kryptograficznej funkcji skrótu ) w miejsce losowej wyroczni. Coraz więcej dowodów sugeruje niepewność tego podejścia, chociaż nie wykazano żadnych praktycznych ataków na wdrożone programy.

Kryptosystem

Cramer – Shoup składa się z trzech algorytmów: generatora kluczy, algorytmu szyfrowania i algorytmu deszyfrującego.

Generacja klucza

• Alicja generuje skuteczny opis cyklicznej grupy porządku za pomocą dwóch różnych, losowych generatorów . ${\ displaystyle G}$${\ displaystyle q}$ ${\ displaystyle g_ {1}, g_ {2}}$
• Alicja wybiera pięć losowych wartości z . ${\ displaystyle ({x} _ {1}, {x} _ {2}, {y} _ {1}, {y} _ {2}, z)}$${\ displaystyle \ {0, \ ldots, q-1 \}}$
• Alice oblicza . ${\ displaystyle c = {g} _ {1} ^ {x_ {1}} g_ {2} ^ {x_ {2}}, d = {g} _ {1} ^ {y_ {1}} g_ {2 } ^ {y_ {2}}, h = {g} _ {1} ^ {z}}$
• Alice publikuje wraz z opisem jako jej klucz publiczny . Alice zachowuje swój tajny klucz . Grupę można współdzielić między użytkownikami systemu. ${\ displaystyle (c, d, h)}$${\ Displaystyle G, q, g_ {1}, g_ {2}}$${\ displaystyle (x_ {1}, x_ {2}, y_ {1}, y_ {2}, z)}$

Szyfrowanie

Aby zaszyfrować wiadomość do Alicji pod jej kluczem publicznym , ${\ displaystyle m}$${\ Displaystyle (G, q, g_ {1}, g_ {2}, c, d, h)}$

• Bob przekształca się w element . ${\ displaystyle m}$${\ displaystyle G}$
• Bob wybiera losowo z , a następnie oblicza: ${\ displaystyle k}$${\ displaystyle \ {0, \ ldots, q-1 \}}$
  • ${\ Displaystyle u_ {1} = {g} _ {1} ^ {k}, u_ {2} = {g} _ {2} ^ {k}}$
  • ${\ displaystyle e = h ^ {k} m}$
  • ${\ Displaystyle \ alpha = H (u_ {1}, u_ {2}, e)}$ , gdzie H () to uniwersalna jednokierunkowa funkcja skrótu (lub odporna na kolizje kryptograficzna funkcja skrótu , która jest silniejszym wymaganiem).
  • ${\ Displaystyle v = c ^ {k} d ^ {k \ alfa}}$
• Bob wysyła szyfrogram do Alicji. ${\ Displaystyle (u_ {1}, u_ {2}, e, v)}$

Deszyfrowanie

Aby odszyfrować zaszyfrowany tekst tajnym kluczem Alicji , ${\ Displaystyle (u_ {1}, u_ {2}, e, v)}$${\ displaystyle (x_ {1}, x_ {2}, y_ {1}, y_ {2}, z)}$

• Alice oblicza i weryfikuje to . Jeśli ten test się nie powiedzie, dalsze odszyfrowywanie jest przerywane, a dane wyjściowe odrzucane. ${\ Displaystyle \ alpha = H (u_ {1}, u_ {2}, e) \,}$${\ displaystyle {u} _ {1} ^ {x_ {1}} u_ {2} ^ {x_ {2}} ({u} _ {1} ^ {y_ {1}} u_ {2} ^ {y_ {2}}) ^ {\ alpha} = v \,}$
• W przeciwnym razie Alice oblicza tekst jawny jako . ${\ Displaystyle m = e / ({u} _ {1} ^ {z}) \,}$

Etap deszyfrowania poprawnie odszyfrowuje każdy poprawnie sformułowany zaszyfrowany tekst, ponieważ

${\ Displaystyle {u} _ {1} ^ {z} = {g} _ {1} ^ {kz} = h ^ {k} \,}$ , i ${\ Displaystyle m = e / h ^ {k}. \,}$

Jeśli przestrzeń możliwych wiadomości jest większa niż ich rozmiar , wówczas Cramer – Shoup może być używany w hybrydowym systemie kryptograficznym w celu poprawy wydajności w przypadku długich wiadomości. ${\ displaystyle G}$

Bibliografia

• Ronald Cramer i Victor Shoup . „Praktyczny system kryptograficzny klucza publicznego, który jest w sposób udowodniony zabezpieczony przed adaptacyjnym atakiem z użyciem szyfrogramu”. w postępowaniu Crypto 1998, LNCS 1462, s. 13ff ( ps , pdf )
• Zabawkowe implementacje Cramer-Shoup w Emacs Lisp i Java
• 1998 rocznik wiadomości dotyczące Cramer Shoup za opublikowaniu w Wired News oraz w Bruce Schneier „s Crypto-Gram
• Ronald Cramer i Victor Shoup : „Uniwersalne dowody skrótu i ​​paradygmat dla bezpiecznego szyfrowania klucza publicznego wybranym tekstem zaszyfrowanym”. w postępowaniu Eurocrypt 2002, LNCS 2332, s. 45–64. Pełna wersja (pdf)