Shafrira (Shafi) Và Giải Nobel về Khoa học Máy tính
Shafrira (Shafi) Và Giải Nobel về Khoa học Máy tính
Tôi đã phỏng vấn một số người vĩ đại trong lĩnh vực mật mã học, và nhiều người đề cập đến thời gian họ lắng nghe Shafi Goldwasser, và cách bà ấy đã truyền cảm hứng cho họ trong sự nghiệp. Năm 2012, bà đã giành được Giải Turing (Giải Nobel về Khoa học Máy tính) [here]:
Trong số nhiều điều bà ấy đã phát minh ra, có đồng phát minh ra mã hóa xác suất [here][1]:
và đồng phát minh ra bằng chứng không tiết lộ [2]:
Bà hiện là Giáo sư RSA về Kỹ thuật Điện và Khoa học Máy tính tại MIT [here]. Trong suốt sự nghiệp của mình, Shafi đã được trao nhiều giải thưởng, bao gồm, vào năm 2012, Giải Turing, và, vào năm 2019, bằng Tiến sĩ Khoa học Danh dự của Đại học Oxford. Shafi lấy bằng năm 1979 (Đại học Carnegie Mellon) và sau đó được trao bằng Tiến sĩ năm 1984 (từ Đại học California) [here]:
Bà cũng được xếp hạng là nhà nghiên cứu khoa học máy tính có ảnh hưởng thứ 12 trên thế giới từ năm 2010 đến năm 2020.
Mã hóa xác suất Blum-Goldwasser
Người hướng dẫn Tiến sĩ của Shafi là Manuel Blum hùng mạnh, và cùng nhau họ đã đồng sáng tạo ra mã hóa xác suất. Với mã hóa khóa công khai, Alice có thể có hai tin nhắn có thể có (một '0' hoặc một '1') mà cô ấy gửi cho Bob. Nếu Eve biết các tin nhắn có thể có (một '0' hoặc một '1'), cô ấy sẽ mã hóa từng tin nhắn bằng khóa công khai của Bob và sau đó đối chiếu kết quả với tin nhắn mật mã mà Alice gửi. Do đó, Eve có thể xác định những gì Alice đã gửi cho Bob. Để khắc phục điều này, phương pháp Blum-Goldwasser là một thuật toán khóa công khai sử dụng lược đồ mã hóa khóa công khai xác suất [here]:
Phương pháp mã hóa sử dụng kỹ thuật Blum-Blum-Shub (BBS) để tạo ra luồng khóa [here]. Ban đầu, chúng ta tạo hai số nguyên tố (p và q), và sau đó tính N:
N = p.q
Khóa công khai là N, và khóa riêng là p và q, và trong đó p và q:
p (mod 4) = 3
q (mod 4) = 3
Ví dụ: chúng ta có thể chọn p= 239, q= 179, vì cả hai sẽ cho chúng ta 3 khi chúng ta thực hiện phép toán (mod 4):
>>> p=239
>>> q=179
>>> p%4
3
>>> q%4
3
Phương pháp cơ bản, như được định nghĩa bởi Wikipedia, là:
Mã như sau [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)))
Một mẫu chạy là [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
Hệ mật mã Goldwasser–Micali (GM)
Với mã hóa khóa công khai, Alice có thể có hai tin nhắn có thể có (một '0' hoặc một '1') mà cô ấy gửi cho Bob. Nếu Eve biết các tin nhắn có thể có (một '0' hoặc một '1'), cô ấy sẽ mã hóa từng tin nhắn bằng khóa công khai của Bob và sau đó đối chiếu kết quả với tin nhắn mật mã mà Alice gửi. Do đó, Eve có thể xác định những gì Alice đã gửi cho Bob. Để khắc phục điều này, phương pháp Goldwasser–Micali (GM) triển khai một lược đồ mã hóa khóa công khai xác suất. Nó cũng hỗ trợ việc sử dụng mã hóa đồng hình và được phát triển bởi Shafi Goldwasser và Silvio Micali vào năm 1982.
Một minh chứng về phương pháp here.
Trong một phương pháp mã hóa xác suất, Alice chọn bản rõ (m) và một chuỗi ngẫu nhiên (r). Tiếp theo, cô ấy sử dụng khóa công khai của Bob để mã hóa cặp tin nhắn (m,r). Nếu giá trị là ngẫu nhiên, thì Eve sẽ không thể phạm vi các tin nhắn và các giá trị ngẫu nhiên được sử dụng.
Nếu Bob muốn tạo khóa công khai và khóa riêng của mình. Trước tiên, anh ta chọn hai số nguyên tố ngẫu nhiên cho khóa riêng của mình, và sau đó tính N:
N=p.q
Các giá trị của p và q sẽ là khóa riêng của anh ta và N sẽ tạo thành một phần của khóa công khai của anh ta. Đối với phần thứ hai của khóa công khai của mình, anh ta xác định:
a=pseudosquare(p,q)
Chúng ta chọn một giá trị của a, để sau đó không có giải pháp cho điều này:
u² ≡ a (mod N)
Điều này được định nghĩa là a không có thặng dư bậc hai (here).
Khóa công khai của Bob là (N,a) và khóa riêng là (p,q).
Tạo khóa
Phương pháp mã hóa khóa trở thành:
Bob chọn p và q.
Bob chọn a với (a/p) = (a/q) = -1. Đây là một phép tính ký hiệu Jacobi.
Bob công bố N và a.
Mã hóa
Để mã hóa cho Bob. Alice chọn m, và đó là một bit để mã hóa m∈0,1.
Alice sau đó sử dụng các giá trị (N,a) của Bob để tính toán:
c=r² (mod N) nếu m=0
c=a r² (mod N) nếu m=1
Alice chọn r một cách ngẫu nhiên, và do đó Eve sẽ không thể phát hiện ra tin nhắn, vì các giá trị ngẫu nhiên sẽ bao gồm tất cả các bình phương có thể có modulo N, khi m=0.
Alice gửi bit mật mã (c ) cho Bob.
Giải mã
Bob sau đó tính toán ký hiệu Jacobi (c/p) và nhận được:
m=0 nếu c/p=1
m=1 nếu c/p=−1
Một minh chứng về phương pháp here. Một phác thảo về mã từ here là:
# 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)
Một mẫu chạy với tin nhắn “hello” cho:
{'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: 805121215Kết luận
Hệ mật mã Goldwasser–Micali (GM) là một phương pháp khóa công khai đã tồn tại được một thời gian (1982), và là phương pháp đầu tiên phác thảo việc sử dụng các phương pháp xác suất để mã hóa. Theo tiêu chuẩn ngày nay, nó không hiệu quả, nhưng các phương pháp của nó hiện đang được sử dụng trong việc triển khai mã hóa đồng hình, chẳng hạn như với [paper]. Đối với Safi, bà vẫn đồng lãnh đạo Nhóm Mật mã và An ninh Thông tin (CIS) tại MIT, và nhóm này chứa một số người tuyệt vời nhất trong lịch sử mật mã:
Và đây là một bài nói gần đây:
Tài liệu tham khảo
[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).