Шафрира (Шафи) и Нобелевская премия по информатике

Шафрира (Шафи) и Нобелевская премия по информатике

Я брал интервью у некоторых выдающихся криптографов, и многие упоминали, как слушали Шафи Голдвассер и как она вдохновила их в карьере. В 2012 году она получила премию Тьюринга (Нобелевскую премию по информатике) [here]:

Среди многих вещей, которые она изобрела, было совместное изобретение вероятностного шифрования [here][1]:

и соавторство доказательств с нулевым разглашением [2]:

В настоящее время она является профессором электротехники и информатики RSA в MIT [here]. За свою карьеру Шафи была удостоена множества наград, в том числе премии Тьюринга в 2012 году и почетной докторской степени по науке Оксфордского университета в 2019 году. Шафи получила степень в 1979 году (Университет Карнеги-Меллона), а затем получила докторскую степень в 1984 году (в Калифорнийском университете) [here]:

Она также была признана 12-м самым влиятельным исследователем в области информатики в мире с 2010 по 2020 год.

Вероятностное шифрование Блюма-Голдвассер

Научным руководителем Шафи был могущественный Мануэль Блюм, и вместе они создали вероятностное шифрование. При шифровании с открытым ключом Алиса может иметь два возможных сообщения («0» или «1»), которые она отправляет Бобу. Если Ева знает возможные сообщения («0» или «1»), она зашифрует каждое из них с помощью открытого ключа Боба, а затем сопоставит результаты с зашифрованным сообщением, которое отправляет Алиса. Таким образом, Ева может определить, что Алиса отправила Бобу. Чтобы преодолеть это, метод Блюма-Голдвассер представляет собой алгоритм с открытым ключом, который использует вероятностную схему шифрования с открытым ключом [here]:

Метод шифрования использует технику Blum-Blum-Shub (BBS) для генерации ключевого потока [here]. Первоначально мы создаем два простых числа (p и q), а затем вычисляем N:

N = p.q

Открытым ключом является N, а закрытым ключом являются p и q, где p и q:

p (mod 4) = 3

q (mod 4) = 3

Например, мы можем выбрать p= 239, q= 179, так как оба дадут нам 3, когда мы выполним операцию (mod 4):

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

Основной метод, как определено в Wikipedia, таков:

Код выглядит следующим образом [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)))

Пример запуска [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

Криптосистема Goldwasser–Micali (GM)

При шифровании с открытым ключом Алиса может иметь два возможных сообщения («0» или «1»), которые она отправляет Бобу. Если Ева знает возможные сообщения («0» или «1»), она зашифрует каждое из них с помощью открытого ключа Боба, а затем сопоставит результаты с зашифрованным сообщением, которое отправляет Алиса. Таким образом, Ева может определить, что Алиса отправила Бобу. Чтобы преодолеть это, метод Goldwasser–Micali (GM) реализует вероятностную схему шифрования с открытым ключом. Он также поддерживает использование гомоморфного шифрования и был разработан Shafi Goldwasser и Silvio Micali в 1982 году.

Демонстрация метода here.

В методе вероятностного шифрования Алиса выбирает открытый текст (m) и случайную строку (r). Затем она использует открытый ключ Боба для шифрования пары сообщений (m,r). Если значение является случайным, то Ева не сможет определить диапазон используемых сообщений и случайных значений.

Если Боб хочет создать свои открытый и закрытый ключи. Сначала он выбирает два случайных простых числа для своего закрытого ключа, а затем вычисляет N:

N=p.q

Значения p и q будут его закрытым ключом, а N станет частью его открытого ключа. Для второй части своего открытого ключа он определяет:

a=pseudosquare(p,q)

Мы выбираем значение a, чтобы не было решения для этого:

u² ≡ a (mod N)

Это определяется как отсутствие квадратичных вычетов (here).

Открытым ключом Боба является (N,a), а закрытым ключом является (p,q).

Генерация ключей

Метод шифрования ключа становится:

Боб выбирает p и q.

Боб выбирает a с (a/p) = (a/q) = -1. Это вычисление символа Якоби.

Боб публикует N и a.

Шифрование

Чтобы зашифровать для Боба. Алиса выбирает m, который является битом для шифрования m∈0,1.

Затем Алиса использует значения Боба (N,a) для вычисления:

c=r² (mod N) если m=0

c=a r² (mod N) если m=1

Алиса выбирает r случайным образом, и, таким образом, Ева не сможет обнаружить сообщение, поскольку случайные значения будут состоять из всех возможных квадратов по модулю N, когда m=0.

Алиса отправляет зашифрованный бит (c ) Бобу.

Дешифрование

Затем Боб вычисляет символ Якоби (c/p) и получает:

m=0 если c/p=1

m=1 если c/p=−1

Демонстрация метода here. Схема кода от 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)

Пример запуска с сообщением «hello» дает:

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

Выводы

Криптосистема Goldwasser–Micali (GM) — это метод с открытым ключом, который существует уже довольно давно (1982 год) и первым очертил использование вероятностных методов для шифрования. По сегодняшним меркам он неэффективен, но его методы сейчас используются при реализации гомоморфного шифрования, например, с помощью [paper]. Что касается Шафи, она по-прежнему является соруководителем Cryptography and Information Security (CIS) в MIT, в котором работают одни из самых удивительных людей в истории криптографии:

И вот недавний разговор:

Ссылки

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