Shafrira (Shafi) e o Prêmio Nobel de Ciência da Computação

Shafrira (Shafi) e o Prêmio Nobel de Ciência da Computação

Entrevistei alguns dos grandes nomes da criptografia, e muitos mencionam a época em que ouviram Shafi Goldwasser, e como ela os inspirou em suas carreiras. Em 2012, ela ganhou o Turing Prize (o Prêmio Nobel de Ciência da Computação) [here]:

Entre as muitas coisas que ela inventou, está a co-invenção da encriptação probabilística [here][1]:

e a co-inventora das provas de conhecimento zero [2]:

Ela é atualmente a RSA Professor of Electrical Engineering and Computer Science no MIT [here]. Ao longo de sua carreira, Shafi foi premiada com muitos prêmios, incluindo, em 2012, o Turing Award e, em 2019, um Doutorado Honorário em Ciências pela Universidade de Oxford. Shafi obteve seu diploma em 1979 (Carnegie Mellon University) e foi então premiada com um PhD em 1984 (pela University of California) [here]:

Ela também foi colocada como a 12ª pesquisadora de ciência da computação mais influente do mundo de 2010 a 2020.

Encriptação Probabilística de Blum-Goldwasser

O orientador de PhD de Shafi foi o poderoso Manuel Blum, e juntos eles co-criaram a encriptação probabilística. Com a encriptação de chave pública, Alice poderia ter duas mensagens possíveis (um '0' ou um '1') que ela envia para Bob. Se Eve conhece as mensagens possíveis (um '0' ou um '1'), ela então cifra cada uma com a chave pública de Bob e então compara os resultados com a mensagem cifrada que Alice envia. Eve pode assim determinar o que Alice enviou para Bob. Para superar isso, o método Blum-Goldwasser é um algoritmo de chave pública que usa um esquema de encriptação de chave pública probabilística [here]:

O método de encriptação usa a técnica Blum-Blum-Shub (BBS) para gerar o fluxo de chaves [here]. Inicialmente, criamos dois números primos (p e q), e então calculamos N:

N = p.q

A chave pública é N, e a chave privada é p e q, e onde p e q:

p (mod 4) = 3

q (mod 4) = 3

Por exemplo, podemos selecionar p= 239, q= 179, pois ambos nos darão 3 quando fizermos uma operação (mod 4):

>>> p=239
>>> q=179
>>> p%4
3
>>> q%4
3

O método básico, conforme definido pela Wikipédia, é:

O código é o seguinte [here]:

iimport numpy as np
import binascii
import Crypto.Util.number
from Crypto import Random
import sys
import random

def xgcd(a, b):
    """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

# Method from https://stackoverflow.com/questions/7396849/convert-binary-to-ascii-and-vice-versa
def to_bits(text, encoding='utf-8', errors='surrogatepass'):
    bits = bin(int(binascii.hexlify(text.encode(encoding, errors)), 16))[2:]
    return bits.zfill(8 * ((len(bits) + 7) // 8))
def from_bits(bits, encoding='utf-8', errors='surrogatepass'):
    n = int(bits, 2)
    return int2bytes(n).decode(encoding, errors)
def int2bytes(i):
    hex_string = '%x' % i
    n = len(hex_string)
    return binascii.unhexlify(hex_string.zfill(n + (n & 1)))
# Derived from https://github.com/coenvalk/blum-goldwasser-probabilistic-encryption/blob/master/blumgoldwasser.py
def BGW_enc(p, q, x, m):
    n = p * q

    # assert p%4 == 3 and q%4 == 4
    k = int(np.log2(n))
    h = int(np.log2(k))
    t = len(m) // h
    xi = x
    c = ''
    for i in range(t):
        mi = m[i*h:(i + 1)*h]
        xi = (xi ** 2) % n
        xi_bin = bin(xi)
        pi = xi_bin[-h:]
        mi_int = int(mi, 2)
        pi_int = int(pi, 2)
        ci = pi_int ^ mi_int
        ci_bin = format(ci, '0' + str(h) + 'b')
        c += ci_bin
    xt = (xi ** 2) % n
    return c, xt
        
    
def BGW_dec(p, q, a, b, xt, c):
    assert a*p + b*q == 1
    n=p*q
    k = int(np.log2(n))
    h = int(np.log2(k))
    t = len(c) // h
    d1 = pow((p + 1) // 4,(t + 1) , (p - 1))
    d2 = pow((q + 1) // 4,(t + 1) , (q - 1))
  #  d2 = (((q + 1) // 4)**(t + 1)) % (q - 1)
    u = pow(xt,d1,p)
    v = pow(xt,d2, q)
    x0 = (v*a*p + u*b*q) % n
    xi = x0
    m = ''
    for i in range(t):
        ci = c[i*h:(i + 1)*h]
        xi = (xi**2) % n
        xi_bin = bin(xi)
        pi = xi_bin[-h:]
        ci_int = int(ci, 2)
        pi_int = int(pi, 2)
        mi = pi_int ^ ci_int
        mi_bin = format(mi, '0' + str(h) + 'b')
        m += mi_bin
    return m
p = 499
q = 547
bits=10
msg='Hello'
if (len(sys.argv)>1):
        bits=int(sys.argv[1])
if (len(sys.argv)>2):
        msg=(sys.argv[2])
while True:
 p=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
 if (p%4==3): break

while True:
 q=Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
 if (q%4==3): break
m=to_bits(msg)
    
a=1
b=1
_,a,b=xgcd(p,q)

r= random.getrandbits(bits)
x0 = (a*p*r + b*q+r) % (p*q)
       
c, xt = BGW_enc(p, q, x0, m)
print(("Message: %s" % msg))
print(("   %s" % m))
print(("\nNo of bits in prime is %d" % bits))
print(("p= %d" % p))
print(("q= %d" % q))
print(("a= %d" % a))
print(("b= %d" % b))
print(("r= %d" % r))
print(("x0= %d" % x0))
print(("ap+bq: %d" % (a*p+b*q)))
print("\nCiphertext:", c)
d = BGW_dec(p, q, a, b, xt, c)
    
print(("Decrypted: %s" % from_bits(d)))

Uma execução de amostra é [here]:

Message: Hello
   0100100001100101011011000110110001101111

No of bits in prime is 16
p= 44119
q= 50647
a= 24633
b= -21458
r= 14161
x0= 2119402684
ap+bq: 1

Ciphertext: 0001011100111001001110010010011100101011
Decrypted: Hello

Criptosistema Goldwasser–Micali (GM)

Com a encriptação de chave pública, Alice poderia ter duas mensagens possíveis (um '0' ou um '1') que ela envia para Bob. Se Eve conhece as mensagens possíveis (um '0' ou um '1'), ela então cifra cada uma com a chave pública de Bob e então compara os resultados com a mensagem cifrada que Alice envia. Eve pode assim determinar o que Alice enviou para Bob. Para superar isso, o método Goldwasser–Micali (GM) implementa um esquema de encriptação de chave pública probabilística. Ele também suporta o uso de encriptação homomórfica e foi desenvolvido por Shafi Goldwasser e Silvio Micali em 1982.

Uma demonstração do método here.

Em um método de encriptação probabilística, Alice seleciona o texto simples (m) e uma string aleatória (r). Em seguida, ela usa a chave pública de Bob para encriptar o par de mensagens (m,r). Se o valor for aleatório, então Eve não será capaz de variar as mensagens e os valores aleatórios usados.

Se Bob quiser criar suas chaves pública e privada. Ele primeiro seleciona dois números primos aleatórios para sua chave privada e, em seguida, calcula N:

N=p.q

Os valores de p e q serão sua chave privada e N fará parte de sua chave pública. Para a segunda parte de sua chave pública, ele determina:

a=pseudosquare(p,q)

Escolhemos um valor de a, para que não haja solução para isso:

u² ≡ a (mod N)

Isso é definido como não tendo resíduos quadráticos (here).

A chave pública de Bob é (N,a) e a chave privada é (p,q).

Geração de chaves

O método de encriptação de chave se torna:

Bob seleciona p e q.

Bob seleciona a com (a/p) = (a/q) = -1. Este é um cálculo de símbolo de Jacobi.

Bob publica N e a.

Encriptação

Para encriptar para Bob. Alice seleciona m, e que é um bit para encriptar m∈0,1.

Alice então usa os valores de Bob de (N,a) para computar:

c=r² (mod N) se m=0

c=a r² (mod N) se m=1

Alice escolhe r aleatoriamente e, portanto, Eve não será capaz de detectar a mensagem, pois os valores aleatórios consistirão em todos os quadrados possíveis módulo N, quando m=0.

Alice envia o bit cifrado (c ) para Bob.

Decriptação

Bob então computa o símbolo de Jacobi (c/p) e obtém:

m=0 se c/p=1

m=1 se c/p=−1

Uma demonstração do método here. Um esboço do código de here é:

# https://asecuritysite.com/encryption/goldwasser
# Based on https://gist.github.com/brunoro/5893701/
from unicodedata import normalize 
from string import ascii_letters
from random import randint
import sys
from functools import reduce

# Miller-Rabin probabilistic primality test (HAC 4.24)
# returns True if n is a prime number
# n is the number to be tested
# t is the security parameter

def miller_rabin(n, t):
    assert(n % 2 == 1)
    assert(n > 4)
    assert(t >= 1)
    # select n - 1 = 2**s * r
    r, s = n - 1, 0
    while r % 2 == 0:
        s += 1
        r >>= 1 #r = (n - 1) / 2 ** s
    for i in range(t):
        a = randint(2, n - 2) # this requires n > 4
        y = pow(a, r, n) # python has built-in modular exponentiation
        if y != 1 and y != n - 1:
            j = 1
            while j <= s - 1 and y != n - 1:
                y = pow(y, 2, n)
                if y == 1:
                    return False
                j += 1
            if y != n - 1:
                return False
    return True
def is_prime(n):
    if n in [2, 3]:
        return True
    if n % 2 == 0:
        return False
    return miller_rabin(n, 10)
def nearest_prime(n):
    if is_prime(n):
        return n
    if n % 2 == 0:
        n += 1
    i = 0
    while True:
        i += 1
        n += 2
        if is_prime(n):
            return n 
def big_prime(size):
    n = randint(1, 9)
    for s in range(size):
        n += randint(0, 9) * s**10
    return nearest_prime(n)
def is_even(x):
    return x % 2 == 0
# calculates jacobi symbol (a n)
def jacobi(a, n):
    if a == 0:
        return 0
    if a == 1:
        return 1
    e = 0
    a1 = a
    while is_even(a1):
        e += 1
        a1 =a1// 2
    assert 2**e * a1 == a
    s = 0
    if is_even(e):
        s = 1
    elif n % 8 in {1, 7}:
        s = 1
    elif n % 8 in {3, 5}:
        s = -1
    if n % 4 == 3 and a1 % 4 == 3:
        s *= -1
    n1 = n % a1
    
    if a1 == 1:
        return s
    else:
        return s * jacobi(n1, a1)
def quadratic_non_residue(p):
    a = 0
    while jacobi(a, p) != -1:
        a = randint(1, p)
    return a
def xeuclid(a, b):
    """ return gcd(a,b), x and y in 'gcd(a,b) = ax + by'.
    """
    x = [1, 0]
    y = [0, 1]
    sign = 1
 
    while b:
        q, r = divmod(a, b)
        a, b = b, r
        x[1], x[0] = q*x[1] + x[0], x[1]
        y[1], y[0] = q*y[1] + y[0], y[1]
        sign = -sign
 
    x = sign * x[0]
    y = -sign * y[0]
    return a, x, y
 
 
def gauss_crt(a, m):
    """ return x in ' x = a mod m'.
    """
    modulus = reduce(lambda a,b: a*b, m)
 
    multipliers = []
    for m_i in m:
        M = modulus // m_i
        gcd, inverse, y = xeuclid(M, m_i)
        multipliers.append(inverse * M % modulus)
 
    result = 0
    for multi, a_i in zip(multipliers, a):
        result = (result + multi * a_i) % modulus
    return result
def pseudosquare(p, q):
    a = quadratic_non_residue(p)
    b = quadratic_non_residue(q)
    return gauss_crt([a, b], [p, q])
def generate_key(prime_size = 6):
    p = big_prime(prime_size)
    q = big_prime(prime_size)
    while p == q:
        p2 = big_prime(prime_size)
    y = pseudosquare(p, q)
    n=p*q
    
    keys = {'pub': (n, y), 'priv': (p, q)}
    return keys
def int_to_bool_list(n):
    return [b == "1" for b in "{0:b}".format(n)]
def bool_list_to_int(n):
    s = ''.join(['1' if b else '0' for b in n])
    return int(s, 2)
def encrypt(m, pub_key):
    bin_m = int_to_bool_list(m)
    n, y = pub_key
    def encrypt_bit(bit):
        x = randint(0, n)
        if bit:
            return (y * pow(x, 2, n)) % n
        return pow(x, 2, n)
    return list(map(encrypt_bit, bin_m))
def decrypt(c, priv_key):
    p, q = priv_key
    def decrypt_bit(bit):
        e = jacobi(bit, p)
        if e == 1:
            return False
        return True
    m = list(map(decrypt_bit, c))
    return bool_list_to_int(m)
def normalize_str(s):
    u = str(s)
    valid_chars = ascii_letters + ' '
    un = ''.join(x for x in normalize('NFKD', u) if x in valid_chars).upper()
    return un.encode('ascii', 'ignore')
def int_encode_char(c):
    ind = c
    val = 27 # default value is space
    # A-Z: A=01, B=02 ... Z=26
    if ord('A') <= ind <= ord('Z'):
        val = ind - ord('A') + 1
    return "%02d" % val
def int_encode_str(s):
    return int(''.join(int_encode_char(c) for c in normalize_str(s)))
message='hello'
key = generate_key()
print(key)
m = int_encode_str(message)
print("\nMessage:",message, "Encoded:",m) 
enc = encrypt(m, key['pub'])
print("\nEncrypted:",enc)
dec = decrypt(enc, key['priv'])
print("\nDecrypted:",dec)

Uma execução de amostra com a mensagem de “hello” dá:

{'pub': (810571289346697L, 417803374284193L), 'priv': (16117253, 50292149)}

Message: hello Encoded: 805121215

Encrypted: [102605923461178L, 143126886286230L, 745770432842022L, 168824391145739L, 261618935651655L, 460849071043598L, 798955941491864L, 487047472970991L, 397987844446930L, 743669716499309L, 669942878308283L, 178548007880797L, 645225183019810L, 779540939053212L, 384395411075108L, 782842239347547L, 691841667554224L, 181138769678461L, 779305447143669L, 451333672269645L, 32858488530236L, 678286539525029L, 51434079116117L, 281928894615544L, 156989394653382L, 31002122426343L, 334583216645061L, 216935340466474L, 38608665591955L, 332742987467921L]

Decrypted: 805121215

Conclusões

O criptosistema Goldwasser–Micali (GM) é um método de chave pública que existe há algum tempo (1982) e foi o primeiro a delinear o uso de métodos probabilísticos para encriptação. Pelos padrões de hoje, não é eficiente, mas seus métodos estão agora sendo usados na implementação de encriptação homomórfica, como com [paper]. Para Safi, ela ainda co-lidera o Cryptography and Information Security (CIS) no MIT, e que contém algumas das pessoas mais incríveis da história da criptografia:

E aqui está uma palestra recente:

Referências

[1] Goldwasser, S., & Micali, S. (1982, May). Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the fourteenth annual ACM symposium on Theory of computing (pp. 365–377).

[2] Goldwasser, S., Micali, S., & Rackoff, C. (2019). The knowledge complexity of interactive proof-systems. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali (pp. 203–225).