Paillier Şifrelemesi

Vikipedi, özgür ansiklopedi
Atla: kullan, ara

Paillier şifrelemesi , 1999’da Pascal Paillier tarafından geliştirilen olasılıksal açık anahtarlı şifreleme yöntemidir. n’inci kök sınıflarını hesaplamanın zorluğunu kullanan Paillier şifreleme sistemi, kararsal bileşik kök sınıfı varsayımı (en:decisional composite residuosity assumption) üzerine kurulmuştur. Sistem, toplama işlemine göre homomorfik (homomorphic) özellik gösterir; yani sadece açık anahtarı, m_1 ve m_2’nin şifrelemesini kullanarak m_1+m_2’nin şifrelenmiş hâli hesaplanabilir.

Algoritma[değiştir | kaynağı değiştir]

Sistemin çalışma şekli aşağıda anlatılmıştır:

Anahtar Üretimi[değiştir | kaynağı değiştir]

  1. ”p” ve “q”, rasgele seçilen, birbirinden bağımsız ve \operatorname{EBOB} (pq, (p-1)(q-1))=1 özelliğini sağlayan iki büyük asal sayı olsun. İki asal sayı da eşit uzunlukta seçilirse, yani güvenlik parametresi s için p, q \in 1 || \{0,1\}^{s-1} ise bu koşul doğrudan sağlanır.[1]
  2. n=pq ve \lambda=\operatorname{EKOK}(p-1,q-1) olarak hesaplanır.
  3. g\in \mathbb Z^{*}_{n^{2}} olmak üzere rasgele bir g tamsayısı seçilir.
  4. L fonkisyonu L(u) = \frac{u-1}{n} şeklinde tanımlanmak üzere; \mu = (L(g^{\lambda}\mod n^{2}))^{-1} \mod n’nın hesaplanabilirliği kontrol edilerek, n’nin g’nin mertebesini böldüğünden emin olunur.
\frac{a}{b} gösteriminin a ile b’nin çarpmaya gore modüler tersinin çarpımına değil, a’nın <math>b</math>’ye bölümüne; yani v \ge 0 olmak üzere a \ge vb eşitsizliğini sağlayan en büyük tamsayı v’ye eşit olduğuna dikkat ediniz.
  • (n, g) - Açık Anahtar (Şifreleme Anahtarı).
  • (\lambda, \mu). - Gizli Anahtar (Şifre Çözme Anahtarı)

Eğer eşit uzunlukta p,q kullanılırsa, yukarıda anlatılan anahtar üretim işlemi, \varphi(n) = (p-1)(q-1) olmak üzere, g = n+1, \lambda = \varphi(n), ve \mu = \varphi(n)^{-1} \mod n, where şeklinde daha basit olarak yapılabilir. .[1]

Şifreleme[değiştir | kaynağı değiştir]

  1. m, m\in \mathbb Z_{n} koşulunu sağlayan, şifrelenecek mesaj olsun.
  2. r\in \mathbb Z^{*}_{n} koşulunu sağlayan rasgele bir r seçilir.
  3. Şifreli metin  c=g^m \cdot r^n \mod n^2 şeklinde hesaplanır.

Şifre Çözme[değiştir | kaynağı değiştir]

  1. Şifreli metin c\in \mathbb Z^{*}_{n^{2}}
  2. Mesaj m = L(c^{\lambda} \mod n^{2}) \cdot \mu \mod n eşitliği kullanılarak hesaplanır.

Özgün makale de belirtildiği gibi şifre çözme işleim, temel olarak, mod n^2’de yapılan bir üs alma işleminden ibarettir.

Homomorfik Özellikler[değiştir | kaynağı değiştir]

Paillier şifrelemesinin en:homomorphic özelliği oldukça önemlidir. Şifreleme fonksiyonu toplama işlemine gore homomorfik olduğu için, aşağıdaki eşitlikler geçerlidir:

  • Şifrelenmemiş metinlerin homomorfik olarak toplanması
D(E(m_1, r_1)\cdot E(m_2, r_2)\mod n^2) = m_1 + m_2 \mod n. \,
D(E(m_1, r_1)\cdot g^{m_2} \mod n^2) = m_1 + m_2 \mod n. \,
  • Şifrelenmemiş metinlerin homomorfik olarak çarpılması
D(E(m_1, r_1)^{m_2}\mod n^2) = m_1 m_2 \mod n, \,
D(E(m_2, r_2)^{m_1}\mod n^2) = m_1 m_2 \mod n. \,
Daha genel olarak belirtmek gerekirse:
D(E(m_1, r_1)^k\mod n^2) = k m_1 \mod n. \,

Özellikle belirtmek gerekirse, Paillier şifrelenmiş hali verilen iki mesajın çarpımının şifrelenmiş hali, gizli anahtar olmadan hesaplanamaz.

Temel Bilgiler[değiştir | kaynağı değiştir]

Paillier şifrelemesi ile, bazı ayrık logaritmaların (en: discrete logarithms) kolay bir biçimde hesaplanabileceği gösterilebilir. Örneğin, binom açılımı kullanarak,

(1+x)^n=\sum_{k=0}^n {n \choose k}x^k = 1+nx+{n \choose 2}x^2 + higher\ powers\ of\ x

Yukarıdaki eşitlikten

(1+n)^x \equiv 1+nx\pmod{n^2}

elde edilir. Buradan, eğer

y = (1+n)^x \mod n^2

ise

x \equiv \frac{y-1}{n} \pmod{n}

yazılabilir. Yani;

L fonksiyonu L(u) = \frac{u-1}{n} (tamsayı bölme işleminin bölümü) şeklinde tanımlanmak üzere ve x \in \mathbb Z_{n} iken
L((1+n)^x \mod n^2) \equiv x \pmod{n},

yazılabilir.

Ayrıca bakınız[değiştir | kaynağı değiştir]

Kaynakça[değiştir | kaynağı değiştir]

  • Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". EUROCRYPT. Springer. pp. 223–238. doi:10.1007/3-540-48910-X_16
  • Paillier, Pascal; Pointcheval, David (1999). "Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries". ASIACRYPT. Springer. pp. 165–179. doi:10.1007/978-3-540-48000-6_14
  • Paillier, Pascal (1999). Cryptosystems Based on Composite Residuosity (Ph.D. thesis). École Nationale Supérieure des Télécommunications.
  • Paillier, Pascal (2002). "Composite-Residuosity Based Cryptography: An Overview". CryptoBytes 5 (1). http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_January_2002_final.pdf. 

Notlar[değiştir | kaynağı değiştir]

  1. ^ a b Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007

Dış bağlantılar[değiştir | kaynağı değiştir]

  • Homomorfik Şifreleme Projesi, Paillier şifrelemesinin homomorfik özellikleriyle beraber geliştirilmiş hâlidir.
  • Encounter : Paillier şifrelemesinin ve buna dayana kriptografik sayaçların geliştirilmiş hâlini içeren açık kaynak kütüphane.