Cramer–Shoup kryptosystem

Cramer –Shoup-systemet är en asymmetrisk nyckelkrypteringsalgoritm och var det första effektiva schemat som visade sig vara säkert mot adaptiv vald chiffertextattack med standardkryptografiska antaganden. Dess säkerhet är baserad på beräkningsbarheten (allt antagen, men inte bevisad) av det beslutsmässiga Diffie–Hellman-antagandet. Den utvecklades av Ronald Cramer och Victor Shoup 1998 och är en förlängning av kryptosystemet ElGamal . I motsats till ElGamal, som är extremt formbar, lägger Cramer–Shoup till andra element för att säkerställa icke-formbarhet även mot en resursstark angripare. Denna icke-smidbarhet uppnås genom användning av en universell enkelriktad hashfunktion och ytterligare beräkningar, vilket resulterar i en chiffertext som är dubbelt så stor som i ElGamal.

Adaptiva valda chiffertextattacker

Definitionen av säkerhet som uppnåtts av Cramer–Shoup kallas formellt " omöjlig att skilja under adaptiv vald chiffertextattack " (IND-CCA2). Denna säkerhetsdefinition är för närvarande den starkaste definitionen som är känd för ett kryptosystem med offentlig nyckel: den förutsätter att angriparen har tillgång till ett dekrypteringsorakel som kommer att dekryptera all chiffertext med hjälp av systemets hemliga dekrypteringsnyckel. Den "adaptiva" komponenten i säkerhetsdefinitionen innebär att angriparen har tillgång till detta dekrypteringsorakel både före och efter att han observerar en specifik målchiffertext för att attackera (även om han är förbjuden att använda oraklet för att helt enkelt dekryptera denna målchiffertext). Den svagare uppfattningen om säkerhet mot icke-adaptivt valda chiffertextattacker (IND-CCA1) tillåter bara angriparen att komma åt dekrypteringsoraklet innan han observerar målchiffertexten.

Även om det var välkänt att många allmänt använda kryptosystem var osäkra mot en sådan angripare, ansåg systemdesigners under många år att attacken var opraktisk och till stor del av teoretiskt intresse. Detta började förändras under slutet av 1990-talet, särskilt när Daniel Bleichenbacher demonstrerade en praktiskt adaptiv vald chiffertextattack mot SSL- servrar med en form av RSA- kryptering.

Cramer–Shoup var inte det första krypteringsschemat som gav säkerhet mot adaptiv vald chiffertextattack. Naor-Yung, Rackoff-Simon och Dolev-Dwork-Naor föreslog bevisligen säkra omvandlingar från standardscheman (IND-CPA) till IND-CCA1- och IND-CCA2-scheman. Dessa tekniker är säkra under en standarduppsättning av kryptografiska antaganden (utan slumpmässiga orakel), men de förlitar sig på komplexa för nollkunskapssäkring och är ineffektiva när det gäller beräkningskostnad och chiffertextstorlek. En mängd andra tillvägagångssätt, inklusive Bellare / Rogaways OAEP och Fujisaki–Okamoto, uppnår effektiva konstruktioner med hjälp av en matematisk abstraktion som kallas ett slumpmässigt orakel . Tyvärr krävs det att någon praktisk funktion (t.ex. en kryptografisk hashfunktion ) ersätts för att implementera dessa scheman i praktiken i stället för det slumpmässiga oraklet. En växande mängd bevis tyder på osäkerheten i detta tillvägagångssätt, även om inga praktiska attacker har påvisats mot utplacerade system.

Kryptosystemet

Cramer–Shoup består av tre algoritmer: nyckelgeneratorn, krypteringsalgoritmen och dekrypteringsalgoritmen.

Nyckelgenerering

• Alice genererar en effektiv beskrivning av en cyklisk grupp $G$ av ordningen $q$ med två distinkta, slumpgeneratorer g $\displaystyle g_{1},g_{2}}$ .
• Alice väljer fem slumpmässiga värden $({x}_{1},{x}_{2},{y}_{1},{y }_{2},z)$ från $\{0,\ldots ,q-1\}$ .
• Alice beräknar $c={g}_{1}^{x_{1}}g_{ 2}^{x_{2}},d={g}_{1}^{y_{1}}g_{2}^{y_{2}},h={g}_{1}^{z }$ .
• Alice publicerar $(c,d,h)$ , tillsammans med beskrivningen av $G,q,g_{1},g_{2 }$ , som hennes publika nyckel . Alice behåller $(x_{1},x_{2},y_{1},y_{2},z)$ som sin hemliga nyckel . Gruppen kan delas mellan användare av systemet.

Kryptering

För att kryptera ett meddelande $m$ till Alice under hennes publika nyckel $(G,q,g_{1},g_{2} ,c,d,h)$ ,

• Bob konverterar $m$ till ett element av $G$ .
• Bob väljer en slumpmässig $k$ från ${\displaystyle \{0,\ldots ,q-1\}} och$ räknar sedan ut:
  • $u_{1}={g}_{1}^{k},u_{2}={g}_{2}^{k}$
  • $e=h^{k}m$
  • $\alpha =H(u_{1},u_{2},e)$ , där H () är en universell enkelriktad hashfunktion (eller en kollision -resistent kryptografisk hashfunktion , vilket är ett starkare krav).
  • $v=c^{k}d^{k\alpha }$
• Bob skickar chiffertexten $(u_{1},u_{2},e,v)$ till Alice.

Dekryptering

För att dekryptera en chiffertext $(u_{1},u_{2},e,v)$ med Alices hemliga nyckel $(x_{1},x_{2},y_{1},y_{2},z)$ ,

• Alice beräknar $\alpha =H(u_{1},u_{2},e)\,$ och verifierar att ${u}_{1}^{x_{1}}u_{2}^{x_{2}}({u}_{1}^{y_ {1}}u_{2}^{y_{2}})^{\alpha }=v\,$ . Om detta test misslyckas avbryts ytterligare dekryptering och utmatningen avvisas.
• Annars beräknar Alice klartexten som $m=e/({u}_{1}^{z})\,$ .

Dekrypteringssteget dekrypterar korrekt all korrekt formad chiffertext, eftersom

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

Om utrymmet för möjliga meddelanden är större än storleken på $G$ , kan Cramer–Shoup användas i ett hybridkryptosystem för att förbättra effektiviteten på långa meddelanden.

• Ronald Cramer och Victor Shoup . "Ett praktiskt kryptosystem med offentlig nyckel som bevisligen är säkert mot adaptiv vald chiffertextattack." i förfarandet av Crypto 1998, LNCS 1462, sid. 13ff ( ps , pdf )
• Leksaksimplementeringar av Cramer–Shoup i Emacs Lisp och Java
• 1998 vintage nyhetsbevakning av Cramer och Shoups publicering i Wired News och i Bruce Schneiers Crypto -Gram
• Ronald Cramer och Victor Shoup : "Universella hashbevis och ett paradigm för vald chiffertext säker kryptering av offentlig nyckel." i processer av Eurocrypt 2002, LNCS 2332, s. 45–64. Full version (pdf)