Shafrira (Shafi) y el Premio Nobel de Ciencias de la Computación

Shafrira (Shafi) y el Premio Nobel de Ciencias de la Computación

He entrevistado a algunos de los grandes de la criptografía, y muchos mencionan el momento en que escucharon a Shafi Goldwasser, y cómo ella los inspiró en su carrera. En 2012, ganó el Premio Turing (el Premio Nobel de Ciencias de la Computación) [here]:

Entre las muchas cosas que inventó, se encuentra la coinvención del cifrado probabilístico [here][1]:

y la coinventora de las pruebas de conocimiento cero [2]:

Actualmente es profesora de ingeniería eléctrica e informática RSA en el MIT [here]. A lo largo de su carrera, Shafi ha recibido muchos premios, incluyendo, en 2012, el Premio Turing, y, en 2019, un Doctorado Honoris Causa en Ciencias por la Universidad de Oxford. Shafi obtuvo su título en 1979 (Carnegie Mellon University) y luego recibió un doctorado en 1984 (de la University of California) [here]:

También fue clasificada como la 12ª investigadora de ciencias de la computación más influyente del mundo entre 2010 y 2020.

Cifrado probabilístico de Blum-Goldwasser

El supervisor del doctorado de Shafi fue el poderoso Manuel Blum, y juntos co-crearon el cifrado probabilístico. Con el cifrado de clave pública, Alice podría tener dos posibles mensajes (un '0' o un '1') que envía a Bob. Si Eve conoce los posibles mensajes (un '0' o un '1'), entonces cifrará cada uno con la clave pública de Bob y luego compara los resultados con el mensaje cifrado que Alice envía. Por lo tanto, Eve puede determinar lo que Alice ha enviado a Bob. Para superar esto, el método Blum-Goldwasser es un algoritmo de clave pública que utiliza un esquema de cifrado probabilístico de clave pública [here]:

El método de cifrado utiliza la técnica Blum-Blum-Shub (BBS) para generar el flujo de claves [here]. Inicialmente, creamos dos números primos (p y q), y luego calculamos N:

N = p.q

La clave pública es N, y la clave privada es p y q, y donde p y q:

p (mod 4) = 3

q (mod 4) = 3

Por ejemplo, podemos seleccionar p= 239, q= 179, ya que ambos nos darán 3 cuando hagamos una operación (mod 4):

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

El método básico, tal como lo define Wikipedia, es:

El código es el siguiente [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)))

Una muestra de ejecución es [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)

Con el cifrado de clave pública, Alice podría tener dos posibles mensajes (un '0' o un '1') que envía a Bob. Si Eve conoce los posibles mensajes (un '0' o un '1'), entonces cifrará cada uno con la clave pública de Bob y luego compara los resultados con el mensaje cifrado que Alice envía. Por lo tanto, Eve puede determinar lo que Alice ha enviado a Bob. Para superar esto, el método Goldwasser–Micali (GM) implementa un esquema de cifrado probabilístico de clave pública. También soporta el uso de cifrado homomórfico y fue desarrollado por Shafi Goldwasser y Silvio Micali en 1982.

Una demostración del método here.

En un método de cifrado probabilístico, Alice selecciona el texto plano (m) y una cadena aleatoria (r). A continuación, utiliza la clave pública de Bob para cifrar el par de mensajes (m,r). Si el valor es aleatorio, entonces Eve no podrá el rango de mensajes y valores aleatorios utilizados.

Si Bob quiere crear sus claves pública y privada. Primero selecciona dos números primos aleatorios para su clave privada, y luego calcula N:

N=p.q

Los valores de p y q serán su clave privada y N formará parte de su clave pública. Para la segunda parte de su clave pública determina:

a=pseudosquare(p,q)

Elegimos un valor de a, de modo que entonces no haya solución para esto:

u² ≡ a (mod N)

Esto se define como que a no tiene residuos cuadráticos (here).

La clave pública de Bob es (N,a) y la clave privada es (p,q).

Generación de claves

El método de cifrado de claves se convierte en:

Bob selecciona p y q.

Bob selecciona a con (a/p) = (a/q) = -1. Este es un cálculo del símbolo de Jacobi.

Bob publica N y a.

Cifrado

Para cifrar para Bob. Alice selecciona m, que es un bit para cifrar m∈0,1.

Alice entonces usa los valores de Bob de (N,a) para calcular:

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

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

Alice elige r al azar, y por lo tanto Eve no podrá detectar el mensaje, ya que los valores aleatorios consistirán en todos los posibles cuadrados módulo N, cuando m=0.

Alice envía el bit cifrado (c ) a Bob.

Descifrado

Bob entonces calcula el símbolo de Jacobi (c/p) y obtiene:

m=0 si c/p=1

m=1 si c/p=−1

Una demostración del método here. Un esquema del código de here es:

# 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)

Una muestra de ejecución con el mensaje de “hello” da:

{'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

Conclusiones

El criptosistema Goldwasser–Micali (GM) es un método de clave pública que ha existido durante un tiempo (1982), y fue el primero en esbozar el uso de métodos probabilísticos para el cifrado. Para los estándares actuales, no es eficiente, pero sus métodos ahora se están utilizando en la implementación del cifrado homomórfico, como con [paper]. Para Safi, ella todavía co-dirige la Criptografía y Seguridad de la Información (CIS) en el MIT, y que contiene algunas de las personas más increíbles en la historia de la criptografía:

Y aquí hay una charla reciente:

Referencias

[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).