Jasne jest, że bezpieczeństwo zapewniane przez schemat klucza publicznego zależy od „odwracalności” procesu od klucza publicznego do klucza prywatnego. Widzieliśmy, że RSA polega na trudności w rozłożeniu dużych liczb na czynniki pierwsze. Inny powszechnie stosowany schemat, opublikowany przez ElGamala, wykorzystuje problem logarytmu dyskretnego, trudności w znalezieniu x, biorąc pod uwagę ostatnią resztę po wielokrotnym dzieleniu ax, gdzie a jest znaną liczbą, przez liczbę pierwszą p. Algorytm ElGamal został wykorzystany do podpisów cyfrowych. Ma niewielką wadę, ponieważ generuje tekst zaszyfrowany, który jest dwa razy dłuższy niż oryginalna wiadomość.