Paillier şifreleme sistemi

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”, 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.
2. $n=pq$ ve $\lambda =\operatorname {EKOK} (p-1,q-1)$ olarak hesaplanır.
3. $g\in \mathbb {Z} _{n^{2}}^{*}$ olmak üzere rastgele 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 b’ye bölümüne; yani $v\geq 0$ olmak üzere $a\geq 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$, ş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 rastgele 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 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})=km_{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" (PDF). CryptoBytes. 5 (1). 

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.