Algoritmo de Blum-Golwasser

Sistema de chave pública probabilística.

O algoritmo de Blum–Goldwasser é um sistema de encriptação assimétrico que foi proposto, em 1984, por Manuel Blum e Shafi Goldwasser.

O esquema de encriptação probabilístico de chave pública de Blum-Golwasser combina a cifra probabilística de Golwasser-Micali com o gerador de bits pseudo-aleatório, Blum–Blum–Shub generator. Este esquema de encriptação baseia a sua segurança na dificuldade de fatorizar números de Blum, isto é, números primos que são congruentes com 3 módulo 4.

1. Geração da chave (chave pública, chave privada)

1- Seleciona-se dois primos, grandes e distintos, em que cada um é congruente com 3 módulo 4.

2- Calcula-se n = p*q.

3- Usando o algoritmo de Euclides extendido, calcula-se a e b tal que a*p + b*q = 1.

4- A chave pública é n e a chave privada é (p, q, a, b).

from sage.crypto.util import random_blum_prime
from sage.crypto.util import least_significant_bits

def BGkey():
    secp = 128
    p=random_blum_prime(2**(secp-1), 2**(secp))
    q=random_blum_prime(2**(secp-1), 2**(secp))
    while p==q:
        q=random_blum_prime(2**secp, 2**(secp+1))
    n=p*q
    d,a,b = xgcd(p,q)
    PubKey=n
    PrivKey=(p,q,a,b)
    return PubKey, PrivKey

2. Encriptação da mensagem

1- Obtém-se a chave pública para quem vai a mensagem.

2- Escolhe-se uma string que irá representar a mensagem que se quer enviar.

3- Separa-se a mensagem que se quer enviar a blocos, isto é, separa-se cada letra da mensagem e passa-se esta para o respetivo carácter ascii.

4- Seleciona-se um número aleatório (r) de $\mathbb{Z}_n^*$ e calcula-se x0 uma vez que este é congruente r^2 módulo n.

5- Para cada bloco da mensagem, calcula-se:

1- x = x^2 módulo n;

2- Calcular os bits menos significativos de x;

3- O criptograma é igual ao xor entre os bits menos significativos de x e o bloco da mensagem.

6- Calcular x = x^2 módulo n.

7- Enviar o criptograma que corresponde ao último passo do ciclo mais o x.

def BGencrypt(PubKey, msg):
    n = PubKey
    msgb = [ord(c) for c in msg]
    R = IntegerModRing(n)
    r = R.random_element()
    xi = r^2
    c=[]
    for m in msgb:
        xi = xi^2
        #cálculo dos bits menos significativos de xi
        c.append((ZZ(xi) % 256)^^m)
    xt = xi^2
    c.append(xt)
    return c

3. Desencriptação da mensagem

1- Calcular d1 = ((p+1)/4)^(t+1) mod(p-1).

2- Calcular d2 = ((q+1)/4)^(t+1) mod(q-1).

3- Calcular u = x^d1 mod(p).

4- Calcular v = x^d2 mod(q).

5- Calcular x0 = vap + ubq mod(n).

6- Para cada bloco do criptograma, calcula-se:

1- x = x^2 módulo n;

2- Calcular os bits menos significativos de x;

3- A mensagem é igual ao xor entre os bits menos significativos de x e o bloco do criptograma.

def BGdecrypt(Key, c, t):
    PubKey=Key[0]
    PrivKey=Key[1]
    p, q, a, b = PrivKey
    n = PubKey
    d1 = power_mod((p+1)/4, t+1, p-1)
    d2 = power_mod((q+1)/4, t+1, q-1)
    u = power_mod(ZZ(c[-1]), d1, p)
    v = power_mod(ZZ(c[-1]), d2, q)
    xi = mod((v*a*p)+(u*b*q),n)
    m = []
    for i in c[:-1]:
        xi = power_mod(xi, 2, n)
        m.append((ZZ(xi)%256)^^i)
    #retorna a mensagem numa string como originalmente
    return "".join([chr(j) for j in m])

4. Segurança

Se considerarmos que a fatorização de inteiros é um problema difícil então, podemos considerar que o esquema probabilístico de encriptação de Blum-Golwasser é seguro. No entanto, este esquema é vulnerável a ataques de criptograma escolhido uma vez que mesmo só sabendo a chave pública com estes ataques consegue-se descobrir a chave privada. Por esta razão, esta cifra não é usada.

5. Eficiência

A eficiência deste algoritmo ao nível da encriptação é menor do que a do RSA porque enquanto que este faz uma multiplicação modular para encriptar 8 bits de texto limpo, o RSA faz uma exponenciação modular. No entanto, ainda é bastante eficiente.

A eficiência deste algoritmo ao nível da desencriptação é melhor que a do RSA quando se trata de mensagens mais longas.

Chave = BGkey()
Publica = Chave[0]
Privada = Chave[1]

#cifração da mensagem
mensagem = 'Teoria de Numeros Computacional'
criptograma = BGencrypt(Publica, mensagem)

#decifração da mensagem
tamanho = len(criptograma)-1
BGdecrypt(Chave, criptograma, tamanho)

'Teoria de Numeros Computacional'

7. Observações

No algoritmo de Blum-Golwasser existe ainda um fator que é o h. Isto é, podemos representar cada bloco da mensagem de tamanho h de forma a introduzir alguma aleatoriedade e tornar a cifra mais segura. No entanto, nesta implementação foi escolhido um número certo de bits de forma a que o h fosse igual a 8 e então fosse de mais fácil implementação.