Paillier Şifrelemesi

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 == Sistemin çalışma şekli aşağıda anlatılmıştır: === Anahtar Üretimi === #”p” ve “q”, rastgele 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.Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007 #n=pq ve \lambda=\operatorname{EKOK}(p-1,q-1) olarak hesaplanır. #g\in \mathbb Z^{*}_{n^{2}} olmak üzere rastgele bir g tam sayısı seçilir. Yani g sayısı, 1 ile (n² - 1) arasında rastgele bir değer almalı ve EBOB(g, n²) = 1 özelliğini sağlamalıdır. # L fonksiyonu 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 b’ye bölümüne; yani v \ge 0 olmak üzere a \ge vb eşitsizliğini sağlayan en büyük tam sayı 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, şeklinde daha basit olarak yapılabilir. . === Şifreleme === # m, m\in \mathbb Z_{n} koşulunu sağlayan, şifrelenecek mesaj olsun. # r\in \mathbb Z^{*}_{n} koşulunu sağlayan rastgele bir r seçilir. Yani r sayısı, 1 ile (n - 1) arasında rastgele bir değer almalı ve EBOB(r, n²) = 1 özelliğini sağlamalıdır. #Şifreli metin c=g^m \cdot r^n \mod n^2 şeklinde hesaplanır. === Şifre Çözme === #Şifreli metin c\in \mathbb Z^{*}_{n^{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şlemi, temel olarak, mod n^2’de yapılan bir üs alma işleminden ibarettir. === Homomorfik Özellikler === 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 === Paillier şifrelemesi ile, bazı ayrık logaritmaların (Ayrık logaritma) 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} (tam sayı 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. === Anlamsal Güvenlik === Yukarıda belirtilen orijinal kriptosistem yukarıda gösterildiği gibi seçilmiş açık metin saldırılarına karşı anlamsal güvenlik sağlar (Seçilmiş açık metin saldırıs)). == Ayrıca bakınız == * Paillier’in tarihsel öncüsü Okamoto-Uchiyama Kriptosistemi. * Paillier’in genelleştirilmiş hâli :en:Damgård–Jurik cryptosystem. * Paillier’in etkileşimli simülatörü oylama uygulamasının örneğidir. * Paillier şifrelemesinin etkileşimli demosu . * Kriptografik yöntemler kullanılarak nasıl oylama yapılabileceğini gösteren googletechtalk videosu . == Kaynakça == * 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. * == Dış bağlantılar == *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. Kategori:Kriptografik algoritmalar