Paillier Şifrelemesi

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}$ 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.
4. ${\displaystyle L}$ fonksiyonu ${\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.

${\displaystyle {\frac {a}{b}}}$ gösteriminin ${\displaystyle a}$ ile ${\displaystyle b}$’nin çarpmaya gore modüler tersinin çarpımına değil, ${\displaystyle 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 tam sayı ${\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]

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. 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.
3. Şifreli metin ${\displaystyle c=g^{m}\cdot r^{n}\mod n^{2}}$ şeklinde hesaplanır.

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 6 Nisan 2012 tarihinde Wayback Machine sitesinde arşivlendi. de belirtildiği gibi şifre çözme işlemi, temel olarak, mod ${\displaystyle n^{2}}$’de yapılan bir üs alma işleminden ibarettir.

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.

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,

${\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}}}$ (tam sayı 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.

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

Bu sayfa, en Paillier Şifrelemesi maddesinden çevrilirken çeşitli sebeplerden dolayı çeviri yarım kalmıştır. Yardım etmek istiyorsanız, çalışmaya katılan kişilerle iletişime geçip, sayfanın durumunu onlara sorabilirsiniz. Sayfanın geçmişine baktığınızda, sayfa üzerinde çalışma yapanları görebilirsiniz.

Bu sayfa, Türkçe Paillier cryptosystem maddesinden çevrilmektedir. Siz de yardım etmek istiyorsanız ya da çeviri yarıda kalmışsa, çalışmaya katılan kişilerle veya çeviri grubu ile iletişime geçip, sayfanın durumunu onlara sorabilirsiniz. Sayfanın geçmişine baktığınızda, sayfa üzerinde çalışma yapanları görebilirsiniz.