Shafrira (Shafi) 与计算机科学的诺贝尔奖
由AI翻译Shafrira (Shafi) 与计算机科学的诺贝尔奖
我采访过一些密码学界的伟人，许多人都提到他们听Shafi Goldwasser演讲的经历，以及她如何激励了他们的职业生涯。2012年，她获得了图灵奖（计算机科学的诺贝尔奖）[here]：
在她发明的众多事物中，包括概率加密的共同发明[here][1]：
以及零知识证明的共同发明者 [2]：
她目前是麻省理工学院 (MIT) 的 RSA 电气工程和计算机科学教授 [here]。在她的职业生涯中，Shafi 获得了许多奖项，包括 2012 年的图灵奖，以及 2019 年牛津大学授予的荣誉科学博士学位。Shafi 于 1979 年获得学位（卡内基梅隆大学），然后在 1984 年获得博士学位（来自加州大学）[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
维基百科定义的基本方法是：
代码如下 [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/p) = (a/q) = -1 的 a。这是一个 Jacobi 符号计算。
Bob 发布 N 和 a。
加密
为了给 Bob 加密。Alice 选择 m，它是一个要加密的位 m∈0,1。
然后 Alice 使用 Bob 的 (N,a) 值来计算：
如果 m=0，则 c=r² (mod N)
如果 m=1，则 c=a r² (mod N)
Alice 随机选择 r，因此 Eve 将无法发现该消息，因为当 m=0 时，随机值将由所有可能的平方模 N 组成。
Alice 将密码位 (c ) 发送给 Bob。
解密
然后 Bob 计算 Jacobi 符号 (c/p) 并得到：
如果 c/p=1，则 m=0
如果 c/p=−1，则 m=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).