Säkerheten för den offentliga nyckeln (asymmetrisk) kryptografi är baserad på beräkningssvårigheten för specifika matematiska problem. Olika kryptosystem för offentlig nyckel förlitar sig på olika problem, men kärnidén är alltid densamma:det är lätt att utföra en operation, men beräkningsmässigt omöjligt att vända den utan att ha speciell kunskap (den privata nyckeln).
Här är några exempel på de matematiska problemen som används:
* heltalsfaktorisering: RSA förlitar sig på svårigheten att ta ett stort antal (modulen *n *) som är produkten av två stora primtal. Att hitta dessa främsta faktorer är beräkningsmässigt mycket dyrt för tillräckligt stort antal.
* Diskret logaritmproblem (DLP): Elliptic Curve Cryptography (ECC) och Diffie-Hellman Key Exchange förlitar sig på svårigheten att hitta den diskreta logaritmen i en ändlig grupp, till exempel en elliptisk kurvgrupp. Med tanke på en punkt P på kurvan och en punkt Q =KP (där K är en skalmultiplikator) är det att hitta K är beräkningsmässigt svårt för lämpliga storlekar.
* Undergruppsmedlemskapsproblem: Detta problem ligger till grund för vissa kryptosystem och innebär att avgöra om ett givet element tillhör en specifik undergrupp inom en större grupp.
Säkerheten är inte absolut; Det är baserat på det aktuella tillståndet för beräkningskraft och algoritmisk kunskap. Förbättringar i algoritmer eller ökningar av beräkningskraft (som kvantdatorer) kan potentiellt bryta dessa kryptosystem. Systemets styrka är därför direkt relaterad till valet av nyckelstorlek och det underliggande matematiska problemets svårighet och behöver periodiska justeringar när tekniken går framåt.
