Shafrira (Shafi) ve Bilgisayar Biliminde Nobel Ödülü

Shafrira (Shafi) ve Bilgisayar Biliminde Nobel Ödülü

Kriptografideki bazı büyük isimlerle röportaj yaptım ve birçoğu Shafi Goldwasser'ı dinledikleri zamanı ve kariyerlerinde onlara nasıl ilham verdiğini belirtiyor. 2012'de Turing Ödülü'nü (Bilgisayar Biliminde Nobel Ödülü) kazandı [burada]:

İcat ettiği birçok şey arasında, olasılıksal şifrelemenin ortak icadı da vardı [burada][1]:

ve sıfır bilgi ispatlarının ortak mucidi [2]:

Şu anda MIT'de RSA Elektrik Mühendisliği ve Bilgisayar Bilimi Profesörüdür [burada]. Kariyeri boyunca Shafi, 2012'de Turing Ödülü ve 2019'da Oxford Üniversitesi tarafından Bilim Doktoru unvanı da dahil olmak üzere birçok ödül aldı. Shafi, 1979'da (Carnegie Mellon Üniversitesi) diplomasını aldı ve ardından 1984'te doktora derecesi aldı (California Üniversitesi'nden) [burada]:

Ayrıca 2010'dan 2020'ye kadar dünyadaki en etkili 12. bilgisayar bilimi araştırmacısı olarak yer aldı.

Blum-Goldwasser Olasılıksal Şifreleme

Shafi'nin doktora danışmanı, kudretli Manuel Blum'du ve birlikte olasılıksal şifrelemeyi yarattılar. Açık anahtarlı şifreleme ile Alice, Bob'a gönderdiği iki olası mesaja (bir '0' veya bir '1') sahip olabilir. Eğer Eve olası mesajları (bir '0' veya bir '1') biliyorsa, o zaman her birini Bob'un açık anahtarıyla şifreleyecek ve ardından sonuçları Alice'in gönderdiği şifreli mesajla eşleştirecektir. Böylece Eve, Alice'in Bob'a ne gönderdiğini belirleyebilir. Bunun üstesinden gelmek için Blum-Goldwasser yöntemi, olasılıksal bir açık anahtarlı şifreleme şeması kullanan bir açık anahtar algoritmasıdır [burada]:

Şifreleme yöntemi, anahtar akışını oluşturmak için Blum-Blum-Shub (BBS) tekniğini kullanır [burada]. Başlangıçta, iki asal sayı (p ve q) oluştururuz ve ardından N'yi hesaplarız:

N = p.q

Açık anahtar N'dir ve özel anahtar p ve q'dur ve burada p ve q:

p (mod 4) = 3

q (mod 4) = 3

Örneğin, p= 239, q= 179'u seçebiliriz, çünkü her ikisi de (mod 4) işlemi yaptığımızda bize 3 verecektir:

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

Wikipedia tarafından tanımlanan temel yöntem şudur:

Kod aşağıdaki gibidir [burada]:

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

Örnek bir çalıştırma [burada]:

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) kriptosistemi

Açık anahtarlı şifreleme ile Alice, Bob'a gönderdiği iki olası mesaja (bir '0' veya bir '1') sahip olabilir. Eğer Eve olası mesajları (bir '0' veya bir '1') biliyorsa, o zaman her birini Bob'un açık anahtarıyla şifreleyecek ve ardından sonuçları Alice'in gönderdiği şifreli mesajla eşleştirecektir. Böylece Eve, Alice'in Bob'a ne gönderdiğini belirleyebilir. Bunun üstesinden gelmek için Goldwasser–Micali (GM) yöntemi, olasılıksal bir açık anahtarlı şifreleme şeması uygular. Ayrıca homomorfik şifrelemenin kullanımını destekler ve 1982'de Shafi Goldwasser ve Silvio Micali tarafından geliştirilmiştir.

Yöntemin bir gösterimi burada.

Olasılıksal bir şifreleme yönteminde, Alice düz metni (m) ve rastgele bir dizeyi (r) seçer. Ardından, (m,r) mesaj çiftini şifrelemek için Bob'un açık anahtarını kullanır. Değer rastgele ise, Eve kullanılan mesaj ve rastgele değer aralığını belirleyemeyecektir.

Bob, açık ve özel anahtarlarını oluşturmak isterse. Öncelikle özel anahtarı için iki rastgele asal sayı seçer ve ardından N'yi hesaplar:

N=p.q

p ve q değerleri onun özel anahtarı olacak ve N, açık anahtarının bir parçasını oluşturacaktır. Açık anahtarının ikinci bölümü için şunu belirler:

a=pseudosquare(p,q)

a değerini seçiyoruz, böylece bunun için bir çözüm yok:

u² ≡ a (mod N)

Bu, hiçbir kuadratik kalıntıya sahip olmaması olarak tanımlanır (burada).

Bob'un açık anahtarı (N,a) ve özel anahtarı (p,q)'dur.

Anahtar üretimi

Anahtar şifreleme yöntemi şu hale gelir:

Bob p ve q'yu seçer.

Bob, (a/p) = (a/q) = -1 olan bir a seçer. Bu bir Jacobi sembolü hesaplamasıdır.

Bob, N ve a'yı yayınlar.

Şifreleme

Bob için şifrelemek için. Alice, şifrelemek için bir bit olan m'yi seçer m∈0,1.

Alice daha sonra Bob'un (N,a) değerlerini kullanarak şunu hesaplar:

c=r² (mod N) eğer m=0 ise

c=a r² (mod N) eğer m=1 ise

Alice, r'yi rastgele seçer ve böylece Eve mesajı tespit edemez, çünkü rastgele değerler, m=0 olduğunda N modülündeki tüm olası karelerden oluşacaktır.

Alice, şifreli biti (c ) Bob'a gönderir.

Şifre Çözme

Bob daha sonra Jacobi sembolünü (c/p) hesaplar ve şunu elde eder:

m=0 eğer c/p=1 ise

m=1 eğer c/p=−1 ise

Yöntemin bir gösterimi burada. Buradan kodun bir taslağı:

# 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” mesajıyla örnek bir çalıştırma şunları verir:

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

Sonuçlar

Goldwasser–Micali (GM) kriptosistemi, bir süredir (1982) var olan bir açık anahtar yöntemidir ve şifreleme için olasılıksal yöntemlerin kullanımını ilk özetleyen yöntemdir. Günümüz standartlarına göre verimli değildir, ancak yöntemleri artık [makale] gibi homomorfik şifrelemenin uygulanmasında kullanılmaktadır. Safi için, hala MIT'de Kriptografi ve Bilgi Güvenliği'ne (CIS) eş liderlik ediyor ve bu da kriptografi tarihindeki en şaşırtıcı insanlardan bazılarını içeriyor:

Ve işte yakın zamanda yapılan bir konuşma:

Referanslar

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