Shafrira (Shafi)とコンピュータサイエンスのノーベル賞

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はBobに送信する2つの可能なメッセージ（「0」または「1」）を持つことができます。Eveが可能なメッセージ（「0」または「1」）を知っている場合、Bobの公開鍵でそれぞれを暗号化し、Aliceが送信する暗号メッセージと照合します。したがって、EveはAliceがBobに送信したものを判断できます。これを克服するために、Blum-Goldwasser法は、確率的公開鍵暗号化スキームを使用する公開鍵アルゴリズムです [here]:

暗号化方式は、Blum-Blum-Shub（BBS）技術を使用してキーストリームを生成します [here]。最初に、2つの素数（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はBobに送信する2つの可能なメッセージ（「0」または「1」）を持つことができます。Eveが可能なメッセージ（「0」または「1」）を知っている場合、Bobの公開鍵でそれぞれを暗号化し、Aliceが送信する暗号メッセージと照合します。したがって、EveはAliceがBobに送信したものを判断できます。これを克服するために、Goldwasser–Micali (GM) 法は、確率的公開鍵暗号化スキームを実装します。また、準同型暗号の使用もサポートしており、1982年にShafi GoldwasserとSilvio Micaliによって開発されました。

メソッドのデモンストレーションはhere。

確率的暗号化方式では、Aliceは平文（m）とランダムな文字列（r）を選択します。次に、Bobの公開鍵を使用して、（m,r）のメッセージペアを暗号化します。値がランダムである場合、Eveは使用されるメッセージとランダム値の範囲を特定できません。

Bobが公開鍵と秘密鍵を作成したい場合。彼は最初に秘密鍵として2つのランダムな素数を選択し、次にNを計算します。

N=p.q

pとqの値は彼の秘密鍵になり、Nは彼の公開鍵の一部を形成します。公開鍵の2番目の部分として、彼は決定します。

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を選択します。これはヤコビ記号の計算です。

BobはNとaを公開します。

暗号化

Bobのために暗号化するには。Aliceはmを選択します。これは暗号化するビットm∈0,1です。

Aliceは次に、Bobの（N,a）の値を使用して計算します。

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

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

Aliceはrをランダムに選択するため、m=0の場合、ランダムな値はNを法とするすべての可能な正方形で構成されるため、Eveはメッセージを特定できません。

Aliceは暗号ビット（c）をBobに送信します。

復号化

Bobは次にヤコビ記号（c/p）を計算し、次を取得します。

m=0 if c/p=1

m=1 if 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]などの準同型暗号の実装で使用されています。Safiにとって、彼女は現在もMITのCryptography and Information Security (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).