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ı, ve ’nin şifrelemesini kullanarak ’nin şifrelenmiş hâli hesaplanabilir.

Algoritma

değiştir

Sistemin çalışma şekli aşağıda anlatılmıştır:

Anahtar Üretimi

değiştir
  1. ”p” ve “q”, rastgele seçilen, birbirinden bağımsız ve   özelliğini sağlayan iki büyük asal sayı olsun. İki asal sayı da eşit uzunlukta seçilirse, yani güvenlik parametresi   için   ise bu koşul doğrudan sağlanır.[1]
  2.   ve   olarak hesaplanır.
  3.   olmak üzere rastgele bir   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.   fonksiyonu   şeklinde tanımlanmak üzere;  ’nın hesaplanabilirliği kontrol edilerek,  ’nin  ’nin mertebesini böldüğünden emin olunur.
  gösteriminin   ile  ’nin çarpmaya gore modüler tersinin çarpımına değil,  ’nın b’ye bölümüne; yani   olmak üzere   eşitsizliğini sağlayan en büyük tam sayı  ’ye eşit olduğuna dikkat ediniz.
  •   - Açık Anahtar (Şifreleme Anahtarı).
  •   - Gizli Anahtar (Şifre Çözme Anahtarı)

Eğer eşit uzunlukta p,q kullanılırsa, yukarıda anlatılan anahtar üretim işlemi,   olmak üzere,   ve  , şeklinde daha basit olarak yapılabilir. .[1]

Şifreleme

değiştir
  1.  ,   koşulunu sağlayan, şifrelenecek mesaj olsun.
  2.   koşulunu sağlayan rastgele bir   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   şeklinde hesaplanır.

Şifre Çözme

değiştir
  1. Şifreli metin  
  2. Mesaj   eşitliği kullanılarak hesaplanır.

Özgün makalede[2] belirtildiği gibi şifre çözme işlemi, temel olarak, mod  ’de yapılan bir üs alma işleminden ibarettir.

Homomorfik Özellikler

değiştir

Paillier şifrelemesinin homomorfik özelliği oldukça önemlidir. Şifreleme fonksiyonu toplama işlemine göre homomorfik olduğu için, aşağıdaki eşitlikler geçerlidir:

  • Şifrelenmemiş metinlerin homomorfik olarak toplanması
 
 
  • Şifrelenmemiş metinlerin homomorfik olarak çarpılması
 
 
Daha genel olarak belirtmek gerekirse:
 

Özellikle belirtmek gerekirse, Paillier şifrelenmiş hali verilen iki mesajın çarpımının şifrelenmiş hali, gizli anahtar olmadan hesaplanamaz.

Temel Bilgiler

değiştir

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,

 

Yukarıdaki eşitlikten

 

elde edilir. Buradan, eğer

 

ise

 

yazılabilir. Yani;

  fonksiyonu   (tam sayı bölme işleminin bölümü) şeklinde tanımlanmak üzere ve   iken
 ,

yazılabilir.

Anlamsal Güvenlik

değiştir

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

değiştir
  1. ^ a b Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007
  2. ^ Pascal Paillier. "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes" (PDF). 6 Nisan 2012 tarihinde kaynağından (PDF) arşivlendi. 
  3. ^ "Paillier Cryptosystem". 18 Şubat 2012. 18 Şubat 2012 tarihinde kaynağından arşivlendi. Erişim tarihi: 14 Ekim 2020. 
  4. ^ "Paillier Cryptosystem". 16 Şubat 2012. 16 Şubat 2012 tarihinde kaynağından arşivlendi. Erişim tarihi: 14 Ekim 2020. 
  5. ^ "Theory and Practice of Cryptography". 23 Aralık 2011. 23 Aralık 2011 tarihinde kaynağından arşivlendi. Erişim tarihi: 14 Ekim 2020. 

Kaynakça

değiştir
  • 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). 20 Ekim 2006 tarihinde kaynağından (PDF) arşivlendi. Erişim tarihi: 22 Mayıs 2012. 

Dış bağlantılar

değiştir
  • "Homomorfik Şifreleme Projesi". 29 Haziran 2012 tarihinde kaynağından arşivlendi. 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.