Asymmetrisk kryptografi (public key)

Asymmetrisk kryptografi bygger på trapdoor-problemer: operationer, der er billige i én retning og praktisk umulige at vende om uden en hemmelighed. RSA (Rivest, Shamir og Adleman, 1977) hviler på, at det er svært at faktorisere n = pq; Diffie-Hellman (1976) og varianten på elliptiske kurver (ECC, foreslået uafhængigt af Koblitz og Miller i 1985) hviler på det diskrete logaritmeproblem. Ideerne blev opdaget tidligere hos GCHQ af Ellis, Cocks og Williamson, men arbejdet var hemmeligstemplet indtil 1997. Fordi generiske algoritmer som number field sieve og Pollards rho giver genveje, kan nøglestørrelser ikke sammenlignes med symmetriske: NIST SP 800-57 vurderer RSA-2048 til ca. 112 bits sikkerhed og kræver RSA-3072 eller en 256-bit kurve som P-256 eller Curve25519 for 128 bit.

I praksis bruges asymmetriske primitiver til tre opgaver, aldrig til store datamængder: nøgleaftale (ECDHE i TLS 1.3, X25519 efter RFC 7748), nøgletransport eller -indkapsling (RSA-OAEP og key-encapsulation mechanisms) og digitale signaturer. Virkelige systemer er hybride: et asymmetrisk trin aftaler eller transporterer en tilfældig symmetrisk nøgle, og AES-GCM eller ChaCha20-Poly1305 krypterer selve indholdet. TLS 1.3 fjernede statisk RSA-nøgletransport helt, så hvert håndtryk bruger flygtig Diffie-Hellman og opnår forward secrecy.

Lærebogs-RSA er usikker: den er deterministisk og formbar, så padding er obligatorisk. Krypteringspaddingen i PKCS#1 v1.5 muliggjorde Bleichenbachers adaptive chosen-ciphertext-angreb fra 1998, som dukkede op igen i TLS-implementeringer som ROBOT i 2017; OAEP er det sikre valg, hvor RSA-kryptering stadig bruges. Implementeringer af elliptiske kurver skal kontrollere, at modtagne punkter ligger på kurven, for at undgå invalid curve-angreb, og alle implementeringer skal køre i konstant tid for at modstå timing- og cache-sidekanaler.

Shors algoritme vil kunne bryde RSA, Diffie-Hellman over endelige legemer og ECC i polynomiel tid på en tilstrækkeligt stor fejltolerant kvantecomputer, og "harvest now, decrypt later" gør det til et aktuelt problem for fortrolige data med lang levetid. NIST udgav de første post-kvante-standarder i august 2024: FIPS 203 (ML-KEM, en gitterbaseret key-encapsulation mechanism), FIPS 204 (ML-DSA) og FIPS 205 (SLH-DSA). Udrulningen er foreløbig hybrid, fx TLS-nøgleudvekslingsgruppen X25519MLKEM768, der kombinerer klassiske og post-kvante-hemmeligheder, og udkastet NIST IR 8547 (november 2024) foreslår, at kvantesårbare algoritmer på 112-bit-niveau udfases efter 2030, og at alle kvantesårbare algoritmer forbydes efter 2035. En sejlivet misforståelse er, at den offentlige nøgle i sig selv autentificerer ejeren; uden et certifikat, en pinnet nøgle eller verifikation ad anden vej kan en mand i midten blot udskifte den med sin egen, og det er netop det problem, PKI findes for at løse.