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

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

Şifreleme

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

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 makalede belirtildiği gibi şifre çözme işleim, 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 (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

• Paillier’in tarihsel öncüsü en:Okamoto–Uchiyama cryptosystem.
• 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.
• Paillier, Pascal (2002). "Composite-Residuosity Based Cryptography: An Overview". CryptoBytes 5 (1). http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_January_2002_final.pdf. 

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.