Shafrira (Shafi) 與電腦科學諾貝爾獎
由AI翻譯Shafrira (Shafi) 與電腦科學諾貝爾獎
我採訪過一些密碼學界的偉人，許多人都提到他們聆聽 Shafi Goldwasser 演講的時光，以及她如何激勵了他們的職業生涯。2012 年，她贏得了圖靈獎（電腦科學諾貝爾獎） [here]：
在她發明的眾多事物中，包括共同發明了機率加密 [here][1]：
以及零知識證明的共同發明者 [2]：
她目前是麻省理工學院 (MIT) 的 RSA 電機工程和電腦科學教授 [here]。在她的職業生涯中，Shafi 獲得了許多獎項，包括 2012 年的圖靈獎，以及 2019 年牛津大學授予的榮譽科學博士學位。Shafi 於 1979 年獲得學位（Carnegie Mellon University），然後於 1984 年獲得博士學位（來自 University of California） [here]：
她還在 2010 年至 2020 年間被評為全球第 12 位最具影響力的電腦科學研究員。
Blum-Goldwasser 機率加密
Shafi 的博士生導師是強大的 Manuel Blum，他們共同創造了機率加密。使用公開金鑰加密，Alice 可以有兩個可能的消息（「0」或「1」）發送給 Bob。如果 Eve 知道可能的消息（「0」或「1」），她將使用 Bob 的公開金鑰對每個消息進行加密，然後將結果與 Alice 發送的密文消息進行匹配。因此，Eve 可以確定 Alice 發送給 Bob 的內容。為了克服這個問題，Blum-Goldwasser 方法是一種公開金鑰演算法，它使用機率公開金鑰加密方案 [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，因為當我們執行 (mod 4) 運算時，兩者都會給我們 3：
>>> 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) 密碼系統
使用公開金鑰加密，Alice 可以有兩個可能的消息（「0」或「1」）發送給 Bob。如果 Eve 知道可能的消息（「0」或「1」），她將使用 Bob 的公開金鑰對每個消息進行加密，然後將結果與 Alice 發送的密文消息進行匹配。因此，Eve 可以確定 Alice 發送給 Bob 的內容。為了克服這個問題，Goldwasser–Micali (GM) 方法實現了一種機率公開金鑰加密方案。它還支援同態加密的使用，由 Shafi Goldwasser 和 Silvio Micali 於 1982 年開發。
該方法的示範 here。
在一種機率加密方法中，Alice 選擇明文 (m) 和一個隨機字串 (r)。接下來，她使用 Bob 的公開金鑰來加密 (m,r) 消息對。如果該值是隨機的，那麼 Eve 將無法知道所使用的消息和隨機值的範圍。
如果 Bob 想要建立他的公開金鑰和私密金鑰。他首先為他的私密金鑰選擇兩個隨機質數，然後計算 N：
N=p.q
p 和 q 的值將是他的私密金鑰，而 N 將構成他的公開金鑰的一部分。對於他的公開金鑰的第二部分，他確定：
a=pseudosquare(p,q)
我們選擇一個 a 值，這樣就沒有這個的解：
u² ≡ a (mod N)
這被定義為沒有二次剩餘 (here)。
Bob 的公開金鑰是 (N,a)，私密金鑰是 (p,q)。
金鑰產生
金鑰加密方法變為：
Bob 選擇 p 和 q。
Bob 選擇一個 a，其中 (a/p) = (a/q) = -1。這是一個 Jacobi 符號計算。
Bob 發布 N 和 a。
加密
為了為 Bob 加密。Alice 選擇 m，這是一個要加密的位元 m∈0,1。
然後，Alice 使用 Bob 的 (N,a) 值來計算：
c=r² (mod N) 如果 m=0
c=a r² (mod N) 如果 m=1
Alice 隨機選擇 r，因此 Eve 將無法發現該消息，因為當 m=0 時，隨機值將由所有可能的平方模 N 組成。
Alice 將密文位元 (c ) 發送給 Bob。
解密
然後，Bob 計算 Jacobi 符號 (c/p) 並得到：
m=0 如果 c/p=1
m=1 如果 c/p=−1
# 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]。對於 Safi 來說，她仍然在 MIT 共同領導密碼學和資訊安全 (CIS)，其中包含密碼學歷史上一些最傑出的人：
這是一個最近的演講：
參考文獻
[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).