Page 96 - bilgem-teknoloji-dergisi-5

Fatih BİRİNCİ, Mehmet Sabır KİRAZ Elektronik Seçim: İleri Düzey Kriptografinin Yapıtaşları ve Uygulamaları

(özellikle kısa mesajlarda) bağlama özelliği sağlanamayabilir. 2.6. Sıfır Bilgi Sızmalı Kanıt Protokolleri Ancak bu hata payı ihmal edilebilecek seviyelere kadar Protokol işleyişi: Bora, Ayşe’ye ayrık logaritma sonucunun
Bunun için mesajın değiştirilemeyeceğini bir şekilde garanti indirilebilmektedir. Bir uygulama alanına örnek olarak sıfır bilindiğini ispatlayacaktır (yani, b’yi bildiğini göstermeden
etmek gerekmektedir. Bir arkadaşınıza bir kapının anahtarının sizde olduğunu bilgi sızmalı kanıt protokolleri, dost düşman tanımlama ispat edecektir.). Aşağıdaki protokolün t kere çalıştırılması ile
kanıtlamak istiyorsunuz. Kapıyı o kişinin önünde açarak sistemlerinde de kullanılabilmektedir. Ayşe (1/2) hata oranı ile ikna olacaktır.
t
Bir Başka Örnek Taahhüt Şeması: , kriptografik özet anahtarının sizde olduğunu kanıtlayabilirsiniz. Peki, anahtarı
algoritmasıdır. o kişiye göstermeden sizde olduğuna inandırmak istiyorsanız Sıfır bilgi protokollerinin en etkileyici kullanım alanlarından Bora ’dan rasgele bir r seçer ve d=g mod n değerini Ayşe’ye
r
n
a. İlk aşamada; Bora, rasgele r:k bit değeri üretir, r ve ne yapabilirsiniz? bir tanesi, bu protokollerin kullanımıyla kişiye özellik/anonimlik gönderir.
(r,m)’yi Ayşe’ye gönderir. Siz ve o kişinin ortak tamamen güvendiği bir arkadaşınız sağlanırken dürüst davranıldığının da kanıtlanabilmesidir. Ayşe, rasgele bir e bit (0 veya 1) seçer ve Bora’ya gönderir.
Kullanıcı sıradan bir protokol adımlarını takip ederken yaptığı
b. İkinci aşamada; Bora m mesajını Ayşe’ye gönderir. olsun. Sadece o kişinin göreceği şekilde o anahtarla kapıyı açıp işlemlerin doğruluğunu sıfır bilgi yöntemi ile karşı tarafa Bora, y=r+eb mod n işlemini yapar ve y’yi Ayşe’ye gönderir.
kilitleyip onu ikna edersiniz. O da diğer arkadaşa evet o anahtar
Bu örneğin gizleme ve bağlama özelliklerini yerine getirip bu kapıyı açıyor der ve inanır. Peki, ortak güvenilir bir kişi kanıtlayabilir. Bu yolla protokollerin dürüst olmayan kişilere Ayşe, ¯ d=g h mod n’yi hesaplar, ¯ d=d ise kabul eder.
y -e
getirmediğine bakalım. Özet algoritmasının ön-görüntü yoksa bu problemi nasıl çözebiliriz? Biraz daha zor bir problem karşı güvenli hale getirilebilir. Örneğin seçmenden, Schnorr Protokolünün Güvenliği
dayanıklılığı (preimage resistance) özelliğinden dolayı mesaj olmakla birlikte çözümü vardır. referandumda kullandığı oyun evet/hayır/çekimser oylarından
özet değerinden elde edilemez. Özet algoritmasının çarpışmaya birisini içerdiğini, örneğin iki evet içermediğini kanıtlaması Eksiksizlik: Protokol başarı ile sonuçlanırsa r ve b’yi bilmeyen
dayanıklılığı (collision resistance) özelliğinden dolayı ikinci İki çıkışı olan bir mağara olduğunu düşünelim. Arkadaşınız istenilebilir. Kâğıt tabanlı seçimlerde seçmenlerin kullandıkları birisinin y’yi hesaplama mümkün olmadığından (ayrık logaritma
aşamada başka bir mesaj verilmesi mümkün değildir. k bu iki çıkış arasındaki gizli bağlantıyı bildiğini iddia etmektedir. oy zarfı bir oy içermektedir. Seçmen zarfın içine birden fazla problemi), Bora’nın r değerini biliyor olması gerekir.
parametresinin uzunluğuna bağlı olarak hem saklanma hem Gizli bağlantın yerini göstermeden sizi bildiğine ikna etmek oy pusulası koymuş olsa bile zarflar tek tek açıldığından bu Doğruluk: Eğer Bora b’yi bilmiyorsa yapabileceği en iyi şey
de bağlama özellikleri sağlanır. Fakat bu iki özellik de hesaplama istiyor. Arkadaşınız mağaranın içinde iken (hangi girişten durum anlaşılacaktır. Homomorfik tabanlı sistemlerde, ilk adımda y’yi hesaplayabileceği bir d seçmektir. Ayşe e’yi (0
zorluğuna dayalı olarak sağlanmaktadır. Daha iyisi yapılamaz girdiğini görmediniz) mağaranın önüne gelerek dilediğiniz kullanılan oy pusulaları açılmadan şifreli olarak toplandığından veya 1) rasgele seçtiğinden Bora’nın b’yi bilmeden doğru y
mı? bir çıkıştan çıkmasını istiyorsunuz. Arkadaşınız istenilen çıkışta oy pusulasının evet/hayır/çekimser dışında oy içermediğinden
belirdiği zaman gizli bağlantının yerini bildiğine ikna olacak emin olunması çok önemlidir. Aksi takdirde seçmenler hesaplama ihtimali (1/2)’dir. Protokol yeterince tekrarlanırsa
2.5.2. Pedersen Taahhüt Şeması mısınız? Arkadaşınızın mağaradan çıkmak için gizli bağlantıyı görünürde bir oy gerçekte ise birden fazla oy kullanabilir. Sıfır Bora’nın b’yi bilmeden Ayşe’yi ikna etme ihtimali ihmal edilebilir
Kurulum: Alıcı taraf (Ayşe) aşağıdaki işlemleri yapar. kullanmasına gerek kalmamış olabilir. Bunun olasılığı yüzde bilgi protokolleri bunu rahatlıkla garanti edebilir. düzeyde olacaktır.
ellidir. Yani yüzde elli olasılıkla arkadaşınız gizli geçidin yerini Sıfır Bilgi Sızması: Protokolün işleyişi ile gizli parametren b’nin
a. G:n (büyük asal bir sayı) elemanlı çarpma işlemine göre biliyor olabilir. Bu durumda ikna olmuş sayılmazsınız. Bu işlemi Sıfır bilgi protokolleri modern kriptografiye 1985 yılında bulunmasına katkıda bulunacak ek bilgi açığa çıkmamaktadır.
devirli grup,örn. n . on defa tekrarladığınızı ve her defasında arkadaşınızın istenilen Shafi Goldwasser, Silvio Micali ve Charles Rackoff tarafından
kazandırıldı [12, 13].
Sıfır bilgi sızmalı kanıt protokolleri etkileşimli ve etkileşimsiz
b. g:grubun üreteci yerden çıkmayı başardığını düşünelim. Gizli bağlantıyı bilmeden olabilmektedir. Schnorr protokolü etkileşimli bir sıfır bilgi
bunu yapma ihtimali çok düşüktür, binde bir civarındadır. Hala En basit ve yaygın olarak kullanılan kanıt protokollerinden
a
c. h=g , a:rasgele ikna olmadıysanız işleme devam edebilirsiniz [11]. birisi Schnorr protokolüdür. Schnorr protokolü, ayrık logaritma sızmalı kanıt protokolüdür. Etkileşimsiz protokollerde kanıtlayıcı
d. (G,n,g,h): açık anahtar sonucunun bilindiğinin karşı tarafa ispatlanması olarak gerekli tüm bilgileri hazırlayıp doğrulayıcıya göndermektedir.
A A özetlenebilir. Doğrulayıcı da gönderilen veriler üzerinden iddianın doğru
Taahhüt Aşaması: n ’dan x elemanı taahhüt etmek için Bora, Gözü kapalı “A’dan gel” olup olmadığını anlayabilmektedir. Etkileşimsiz protokollerde,
x r
n ’den rasgele bir r elemanı seçer, c=g h mod n’yi hesaplar A 2.6.1. Schnorr Protokolü Schnorr protokolünde olduğu doğrulayıcının o anda hazır
ve Ayşe’ye gönderir. olmasına ve iletişimde bulunmasına gerek yoktur.
Kanıt Aşaması: Bora, x ve r’yi Ayşe gönderir. Ayşe, ¯c=g h mod Bora Ayşe Homomorfik şifreleme bölümünün sonunda verdiğimiz
x r
n’yi hesaplar ve kendisine gönderilen c ile karşılaştırır. B B örnekte seçmenlerin dürüst davrandıklarını anlamak için sıfır
bilgi sızmalı kanıt protokollerinin kullanılabileceğini belirtmiştik.
Pedersen Taahhüt Şeması’nın gizleme ve bağlama özelliklerini
yerine getirip getirmediğine bakalım. Şekil 11. Sıfır bilgi sızmalı mağara yolu. Schnorr protokolü gibi sıfır bilgi sızmalı kanıt protokolleri,
homomorfik tabanlı sistemlerde tarafların dürüst davrandığını
Gizleme: Her bir c taahhüdü için n ’dan her bir x elemanı eşit anlamak için yaygın olarak kullanılmaktadır.
olasılıkla seçilmiş olabilir. Yani her bir x için c taahhüdünü Sıfır bilgi sızmalı kanıt protokollerinin aşağıdaki özellikleri
verecek bir r elemanı bulunabilir. Dolayısıyla bu şema, şartsız sağlaması beklenmektedir. 2.7. Karıştırıcı Sistemler
gizleme sağlar (Bknz. Kavramlar Sözlüğü). • Eksiksizlik: İddia doğru ise, dürüst davranan (kurallara uyan Karıştırıcı ağlar, kimin kime oy verdiği, kimin hangi siteleri

x
Bağlama: Bora’nın kanıt aşamasında, ’dan ¯¹x olacak şekilde ve protokol adımlarını izleyen) doğrulayıcı protokolün sonunda gezdiği (onion routing, webmixes, vb.) veya kimin kime e-posta
n
başka bir eleman gönderdiğini varsayalım. Bunun için Bora’nın ikna olacaktır. gönderdiği gibi kişi ile yaptığı iş arasında oluşabilecek
g h mod n=g ¯ x ¯ r n ’dan ¯x ve ¯r • Doğruluk: İddia doğru değil ise, (ihmal edilebilir düzeyde ilişkilerinin yok edilmesini hedeflemektedir. Karıştırıcı ağlarda
x r
h mod n olacak şekilde
elemanlarını bulması gerekmektedir. Bunun için Bora’nın hata payı ile) protokolün sonunda dürüst doğrulayıcı hiçbir kullanıcı mesaj ilişkisinin yok edilmesi için rasgele permutasyon,
-1
a=log h=(¯-x) (r-¯r) mod n ayrık logaritma işlemini şekilde ikna edilemeyecektir. Kurulum: Sitem parametreleri aşağıdaki gibi hesaplanır. asimetrik şifreleme ve tekrar şifreleme gibi değişik teknikler
x
g
hesaplaması gerekmektedir ki bu işlemin hesaplama zorluğuna a. G:n (büyük asal bir sayı) elemanlı çarpma işlemine göre kullanılabilmektedir [14].
dayalı olarak zor bir problem olduğu bilinmektedir (Bknz. • Sıfır Bilgi Sızması: Protokolün başarı ile tamamlanması devirli grup, örn. n . 2.7.1. Tekrar Şifreleme Tekniği Kullanımıyla Karıştırma
Kavramlar Sözlüğü). sonucu doğrulayıcı iddianın doğruluğu haricinde hiçbir ek
bilgi öğrenemeyecektir. b. g: grubun üreteci ElGamal gibi homomorfik şifreleyiciler kullanıldığı
b
İhmal edilebilir düzeyde hata içermelerinden dolayı sıfır bilgi c. h=g , b:rasgele durumlarda, bu algoritmaların homomorfik özelliği kullanılarak
sızmalı kanıt protokolleri matematikteki kanıt d. b:gizli anahtar kullanıcılar tarafından şifrelenen mesajlar sunucularda rasgelelik
katılarak tekrar şifrelenebilir. Rasgele permutasyonların da
mekanizmalarından ayrılmaktadır. Yani, bu protokoller e. (n,g,h):açık anahtar kullanımı ile ağ üzerinde mesajları takip eden kişinin mesaj
belirleyici olmamakla birlikte rasgelelik özelliği gösterirler. ile kullanıcı arasında ilişki kurmasının önüne geçilebilir.
94 Sayı 05 Ocak-Nisan 2011 http://www.bilgem.tubitak.gov.tr/ 95
·