RSA-kryptering

RSA är ett kryptosystem med offentlig nyckel som introducerades 1977 av Ron Rivest, Adi Shamir och Leonard Adleman vid MIT. Patentet gick ut 2000, varefter det spreds till i princip alla kryptografiska bibliotek. RSA möjliggör två kompletterande operationer: kryptera med en offentlig nyckel så att endast den privata nyckeln kan dekryptera, och signering med en privat nyckel så att alla med den offentliga nyckeln kan verifiera.

Matematiken, kortfattat

RSA:s säkerhet vilar på svårigheten att faktorisera stora siffror. Nyckelgenerering:

1. Välj två stora slumpmässiga primtal p och q (vanligtvis 2048 bitar vardera).
2. Compute n = p × q. Detta är modulen, public.
3. Beräkna Eulers totient: φ(n) = (p-1)(q-1).
4. Välj en liten udda e coprime till φ(n). Vanligtvis 65537 (=2^16+1).
5. Compute d = e^(-1) mod φ(n). Detta är den privata nyckeln.

Den publika nyckeln är paret (n, e); den privata nyckeln är d.

För att kryptera ett meddelande m: chiffertext c = m^e mod n. För att dekryptera: m = c^d mod n. Vem som helst med den publika nyckeln kan kryptera; endast någon med den privata nyckeln kan dekryptera. För att signera, det omvända: s = m^d mod n, verifiera med m = s^e mod n.

Varför detta fungerar

Tricket: att beräkna dXPLZ, som kräver φ-faktor(kräver φ-faktor(kräver kunskap) n till p × q. Att faktorisera en 2048-bitars semiprime kräver mer beräkning än mänskligheten har. Att verifiera n = p × q när du redan vet p och q är trivialt. Asymmetrin — enkel multiplikation, hård factoring — är hela grunden för RSA.

Nyckelstorlekar

• RSA-1024 — bruten i princip av motståndare med goda resurser; NIST har förbjudit det för nya distributioner sedan 2014.
• RSA-2048 — nuvarande baslinje. Anses säkert på medellång sikt mot klassiska motståndare.
• RSA-3072 — rekommenderas för nya distributioner enligt NIST:s 2030 övergångstidslinje.
• RSA-4096 där nyckeln har 0-signering —0, där nyckeln har 0-år. horisont. Långsammare men konservativt säker.

RSA i praktiken

RSA krypterar nästan aldrig stora meddelanden direkt. Det är långsamt – att kryptera en kilobyte kräver tusentals modulära exponentieringar. Istället används RSA i hybrid-kryptering: generera en slumpmässig AES-nyckel, kryptera data med AES, kryptera endast AES-nyckeln med RSA. Dekrypteringssidan RSA-dekrypterar nyckeln, sedan AES-dekrypterar data. Varje TLS RSA-handslag fungerar på detta sätt; varje PGP-krypterad e-post fungerar på det här sättet.

Padding spelar roll

Plain ("lärobok") RSA — krypterar m direkt utan utfyllnad — är katastrofalt osäkert. Många attacker utnyttjar formbarhet, frånvaron av slumpmässighet och kantfall som små m. Real RSA använder utfyllnadsscheman:

• PKCS#1 v1.5 utfyllnad — original utfyllnad; sårbara för Bleichenbachers attack om implementeringar läcker om utfyllnad är giltig. Fortfarande allmänt spridd.
• OAEP (Optimal Asymmetric Encryption Padding) — modern utfyllnad; resistent mot attacker med vald chiffertext. Använd detta för ny RSA-kryptering.
• PSS (Probabilistic Signature Scheme) — modern signaturutfyllnad; överlägsen PKCS#1 v1.5 för signering.

Utfyllningsschemat är en del av det distribuerade protokollet, inte valfritt. Misstag i utfyllnadsimplementeringen är den enskilt vanligaste källan till RSA-sårbarheter i verkliga system.

RSA:s långsamma pensionering

RSA ersätts av två anledningar:

• SAKey-storleken är stor. än motsvarande elliptiska kurvtangenter med 10×. TLS-handskaknings- och lagringskostnaderna ökar i skala.
• Kvantmotstånd. En tillräckligt stor kvantdator skulle faktorisera RSA via Shors algoritm i polynomtid. ECC är också sårbart men kvantresistenta alternativ är enklare att distribuera.

TLS 1.3 föråldrat RSA-nyckelutbyte till förmån för ECDHE. Modern signering av certifikatmyndigheter flyttar till ECDSA. RSA kvarstår för kompatibilitet med installerad bas (PGP, JWT, smartkort, kodsignering) och kommer att finnas kvar i flera år.

Postkvantfrågan

Även om kvantdatorer som kan bryta RSA är decennier bort, skördas krypterad data med långsiktigt värde idag under antagandet att den kan dekrypteras senare. Statliga kablar, medicinska journaler, immateriella rättigheter - "skörda nu, dekryptera senare" är den nuvarande hotmodellen. NIST:s post-kvantstandarder (CRYSTALS-Kyber för nyckelinkapsling, CRYSTALS-Dilithium för signaturer) distribueras tillsammans med RSA i hybridkonfigurationer. Pure-RSA-distributioner för långsiktiga konfidentiella data anses alltmer otillräckliga.