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ı, ${\displaystyle m_{1}}$ ve ${\displaystyle m_{2}}$’nin şifrelemesini kullanarak ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle s}$ için ${\displaystyle p,q\in 1||\{0,1\}^{s-1}}$ ise bu koşul doğrudan sağlanır.^[1]
2. ${\displaystyle n=pq}$ ve ${\displaystyle \lambda =\operatorname {EKOK} (p-1,q-1)}$ olarak hesaplanır.
3. ${\displaystyle g\in \mathbb {Z} _{n^{2}}^{*}}$ olmak üzere rastgele bir ${\displaystyle g}$ tamsayısı seçilir.
4. ${\displaystyle L}$ fonkisyonu ${\displaystyle L(u)={\frac {u-1}{n}}}$ şeklinde tanımlanmak üzere; ${\displaystyle \mu =(L(g^{\lambda }\mod n^{2}))^{-1}\mod n}$’nın hesaplanabilirliği kontrol edilerek, ${\displaystyle n}$’nin ${\displaystyle 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 ${\displaystyle v\geq 0}$ olmak üzere ${\displaystyle a\geq vb}$ eşitsizliğini sağlayan en büyük tamsayı ${\displaystyle v}$’ye eşit olduğuna dikkat ediniz.

• ${\displaystyle (n,g)}$ - Açık Anahtar (Şifreleme Anahtarı).
• ${\displaystyle (\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, ${\displaystyle \varphi (n)=(p-1)(q-1)}$ olmak üzere, ${\displaystyle g=n+1,\lambda =\varphi (n),}$ ve ${\displaystyle \mu =\varphi (n)^{-1}\mod n}$, şeklinde daha basit olarak yapılabilir. .^[1]

Şifreleme

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

Şifre Çözme

1. Şifreli metin ${\displaystyle c\in \mathbb {Z} _{n^{2}}^{*}}$
2. Mesaj ${\displaystyle 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 ${\displaystyle 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ı

${\displaystyle D(E(m_{1},r_{1})\cdot E(m_{2},r_{2})\mod n^{2})=m_{1}+m_{2}\mod n.\,}$

${\displaystyle 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ı

${\displaystyle D(E(m_{1},r_{1})^{m_{2}}\mod n^{2})=m_{1}m_{2}\mod n,\,}$

${\displaystyle D(E(m_{2},r_{2})^{m_{1}}\mod n^{2})=m_{1}m_{2}\mod n.\,}$

Daha genel olarak belirtmek gerekirse:

${\displaystyle 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,

${\displaystyle (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

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

elde edilir. Buradan, eğer

${\displaystyle y=(1+n)^{x}\mod n^{2}}$

ise

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

yazılabilir. Yani;

${\displaystyle L}$ fonksiyonu ${\displaystyle L(u)={\frac {u-1}{n}}}$ (tamsayı bölme işleminin bölümü) şeklinde tanımlanmak üzere ve ${\displaystyle x\in \mathbb {Z} _{n}}$ iken

${\displaystyle 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. 

Notlar

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

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.