Este algoritmo é baseado no algoritmo RSA de criptografia. Seu funcionamento pode ser expresso pela fórmula:

S = SigPrim (private key, Transform (Hash (M)))

Ou seja, aplicando uma primitiva de assinatura sobre a chave privada e uma transformação do valor hash da mensagem, é gerada a assinatura. Esta transformação em geral representa um sistema de “padding”(enchimento).
Na criptografia RSA essa formula pode ser traduzida como:

S = [(EM)^d] mod n
Onde (n, d) é a chave privada e EM é um inteiro que representa a mensagem criptografada.
O receptor então pode obter EM a partir da assinatura S, utilizando-se da chave pública:
EM = [(S)^e] mod n
Onde (n, e) é a chave pública.

Sistemas de Enchimento
Os sistemas de enchimento se fazem necessários neste tipo de criptografia para evitar que mensagens gerem valores não seguros para a aplicação do algoritmo. Isto é, existem valores para os quais a função modular se torna facilmente reversível, e portanto, não são seguros. Para evitar que isso ocorra, um enchimento – que pode ser fixo ou aleatório – é concatenado ao valor hash da mensagem.

Um Exemplo Funcional 
Um exemplo numérico do funcionamento deste algoritmo é apresentado abaixo:
Sejam dois números primos p e q:
p= 61 e q= 53
Computa-se n =p*q:
n= 61*53 = 3233
Computa-se fi(n) = (p-1)(q-1)
fi(n)= (61 -1)*(53 -1) = 3120
É escolhido um número inteiro positivo qualquer, que seja coprimo em relação ao valor encontrado para fi(n):
e = 17
Computa-se d tal que o produto (d*e) seja concruente a [1 mod fi(n))]:
d= 2753
Agora já temos a chave privada (n, d) para assinar digitalmente a mensagem:
S = [(EM)^d] mod n , onde EM é um inteiro que representa a mensagem após ser aplicada uma transformação sobre o valor hash da mensagem.
Seja 123 o valor obtido para EM:
S = (123)^2753 mod 3233 = 2746
O destinatário então – de posse da mensagem, da assinatura S, e da chave pública(n, e) – poderá verificar a autenticidade da assinatura computando:
EM = [(S)^e] mod n , onde (n, e) é a chave pública.
EM = (2746)^17 mod 3233 = 123
Se o número obtido pela decriptação da assinatura for igual ao obtido pela transformação da mensagem recebida, a autenticidade da assinatira estará garantida.

ElGamal

Este algoritmo permite confirmar a autenticidade de uma mensagem enviada, mesmo que tenha sido enviada em um canal não seguro, além de fazer uso do problema de logaritmo de algoritmo discreto.
A geração de suas chaves segue o padrão das chaves públicas, ou seja, cada entidade gera um par de chaves e acertam a forma como vão distribuir as chaves públicas.

Geração das Chaves
A entidade A procede do seguinte modo:
Gera de forma aleatória um número primo p de grande dimensão e g, que é uma raiz primitiva módulo p;
Seleciona aleatoriamente um inteiro a, onde 1 ≤ a ≤ p-2 e calcula r = g^a (mod p);
A chave pública da entidade será (p, g, r), e sua chave privada será a.

Encriptação
A entidade B obtém a chave pública de A (p, g, r);
Representa a mensagem como se m fosse um inteiro no intervalo {0, 1, ..., p-1};
Seleciona aleatoriamente um inteiro k, 1 ≤ k ≤ p – 2;
Calcula γ = g^k (mod p) e δ = m x r^k (mod p);
O texto cifrado será c = (γ, δ).

Desencriptação
Para haver a recuperação, A deve:
Usando a chave privada a, calcular γ^(p – 1 – a) (mod p);
Recupera a mensagem m calculando γ^(-a) x δ (mod p).
O problema da cifra ElGamal é que ele possui um valor de expansão de mensagem cifrada de 2, ou seja, o comprimento da mensagem cifrada é o dobro da mensagem clara.
O uso de aleatoriedade em seu código busca aumentar sua segurança ao evitar a eficiência dos ataques através da análise estatística.

Um Exemplo Funcional
Um exemplo numérico do funcionamento deste algoritmo é apresentado abaixo:
A entidade A seleciona o número primo p = 2357 e uma raiz primitiva módulo 2357, g = 2;
Para chave privada, a entidade A escolhe a = 1751 (1 ≤ a ≤ p – 2);
g^a mod p = 2^1751 mod 2357 = 1185
Portanto, a chave pública de A é (p = 2357, g = 2, r = g^a = 1185);
Para encriptar a mensagem m = 2035, B seleciona de forma aleatória um inteiro k = 1520 (1 ≤ k ≤ 2355) e calcula:
γ = 2^1520 mod 2357 = 1430 e δ = 2035 x 1185^1520 mod 2357 = 697
Portanto, a mensagem encriptada é c = (1430, 697)
Para realizar a desencriptação, a entidade A calcula:
γ^(p – 1 – a) = 1430^605 mod 2357 = 872
A mensagem original encriptada m é então obtida quando calculamos:
m = 872 x 697 mod 2357 = 2035