Page 95 - 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ı

Sır paylaşımında kişilere dağıtılan parçaların uzunluğunun 2.3.2. Shamir Sır Paylaşımı 2.4. Habersiz Transfer Eğer x =x mod n ise Bora hiçbir bilgi edinemeyecek ve mesajı
1
en az anahtarın uzunluğu kadar olması ve bunların rasgele çözemeyecektir. Aksi takdirde (yüzde elli olasılıkla) d asallardan
olması gibi temel kurallar vardır. Shamir’in sır paylaşımı yöntemi, Blakley’in yönteminin özel Sanal alışveriş merkezinden bir ürünün fiyatını öğrenmek birine eşit olacaktır (d=p veya d=q). Yani yüzde elli olasılıkla
bir halidir. Fakat hem daha kullanışlı hem de daha verimlidir. istiyorsunuz fakat hangi ürün ile ilgilendiğinizin anlaşılmamasını Bora, asal sayıları bularak gizli anahtarı hesaplayabilecek ve
Sır paylaşımında kişilere dağıtılan parçaların uzunluğunun Shamir’in yönteminde polinomlar kullanılmaktadır istiyorsunuz. Ya da hangi bilgileri aldığınız anlaşılmayacak
en az anahtarın uzunluğu kadar olması ve bunların rasgele (p(x)=a +a x+a x + +a x ). Üç kişinin bir araya gelerek şekilde bir veritabanını sorgulamak istiyorsunuz. O zaman dolayısı ile mesajı çözebilecektir. Ayşe ise gönderdiği sayının
2 ...
n
1
olması gibi temel kurallar vardır. 0 1 2 n habersiz transfer protokollerini incelemenizi önerebiliriz. (x ) Bora’nın tuttuğu sayıya (x) eşit olup olmadığını
anahtarı oluşturması isteniliyorsa grup üyelerine ikinci bilemeyeceğinden (yüzde elli olasılıkla bildiğinden) Bora’nın
Bir başka örnek olarak yine 128 bitlik a anahtarının dört kişi dereceden rasgele bir polinom üzerinde rasgele noktalar verilir. Habersiz transfer protokolleri güvenli çok taraflı hesaplama mesajı çözüp çözmediğini de bilemeyecektir (yüzde elli olasılıkla
arasında paylaştırılmak istendiğini düşünelim. Bu kez herkese Hesaplanmak istenilen anahtarın polinomun y koordinatını protokollerinin temel yapılarından birisidir. Michael O. Rabin bilecektir).
rasgele 128 bitlik a , a , a , a anahtarları verilmiş olsun. kestiği nokta olduğunu düşünelim (yani p(0)). Herhangi üç tarafından 1981 yılında yayınlanan teknik rapor ile literatüre
1
4
3
2
Asıl anahtar ise bunların hepsinin “dışlamalı ya da” (modüler kişi bir araya gelerek polinomu ve dolayısı ile anahtarı bulabilir. girmiştir. Habersiz transfer çok güçlü bir yapıtaşıdır, tek başına Shimon Even, Oded Goldreich ve Abraham Lempel tarafından
2) işlemiyle hesaplanmasıyla (a=a O + a O + a O + a )bulunmaktadır. Kullanılan polinomun boyutu ile anahtarı oluşturmak için kullanılarak her türlü çoklu hesaplama problemleri çözülebilir. 1985 yılında duyurulan “2’de 1 habersiz transfer” protokolünde
2
3
1
4
Önceki örnekten daha iyi olmakla birlikte bu yöntem ile grubun gerekli kişi sayısı arasında bir bağ vardır, kişi sayısının bir Birçok güvenli çoklu hesaplama problemlerinde alt-protokol ise alıcı, göndericide bulunan iki mesajdan sadece birisi
tamamının bir araya gelmesi gerekmektedir. Örneğin, a , a , eksiğidir. olarak da kullanılır. öğrenebilmekte fakat gönderici alıcının hangi mesajı öğrendiğini
2
1
1
0
a ’ün bilinmesi ve a ’ün bilinmemesi durumu hiçbirinin anlayamamaktadır. Ayşe a ve a mesajına sahip olsun, Bora
3
4
bilinmemesi durumuyla aynıdır. da 0 veya 1 (b olarak adlandıralım) üretsin. Habersiz transfer
çalıştırdıktan sonra Bora a mesajını elde edecek fakat a 1-b
b
Asimetrik şifrelemeyle sır paylaşımını sağlayan başka bir mesajı hakkında hiçbir bilgi sahibi olamayacaktır. Yani, alıcı
sistem de Asimetrik (t,n) - Eşik Homomorfik Kripto Sistemlerdir. S Girdi S , S 1 {0,1} ı b {0,1} mesajlardan ikisini birden öğrenemeyecektir. Ayşe ise Bora’nın
0
Hem homomorfik, hem asimetrik hem de sır paylaşımını hangi mesajı açabildiğini öğrenemeyecektir. Bu protokolün
sağlayan en iyi örnekler için Eşik ElGamal ve Paillier kripto genelleştirilmiş hali “n'de 1 habersiz transfer protokolleri” de
sistemleri verilebilir. S 1 literatürde mevcuttur.
S = (x , y )
2
2
2
Bir sonraki bölümde basit ve anlaşılır iki sır paylaşımı yöntemi y 2 2.5. Taahhüt Şemaları
anlatılmaktadır.
S n Bölüm 2.6’da anlatılacak olan sıfır bilgi sızmalı kanıt
2.3.1. Blakley Sır Paylaşımı protokollerinin yapı taşlarındandır. Doğruluğu taahhüt edilmiş
Blakley’in sır paylaşımı yönteminin anlaşılması için basit bir x 1 x 2 x n verilerin geçici olarak saklanması için kullanılmaktadır. İki
örnek verebiliriz. Gruptan herhangi üçünün bir araya gelerek aşamalıdır;
anahtarı oluşturması istenildiğini düşünelim. Gruptaki üyelere (x , y ) 1. Taahhüt aşaması: Gönderen, örneğin Bora m mesajını bir
n
n
rasgele paralel olmayan düzlemler verilir. Bu düzlemlerin bir kasaya koyar, kasayı kilitler ve Ayşe’ye gönderir.
S ’yi öğreniyor,
özelliği daha vardır, hepsinin tek noktada kesişmesidir. İki Çıktı b’yi öğrenmiyor. S b ’yi öğrenmiyor. 2. Kanıt (açığa çıkarma) aşaması: Bora, kasadaki mesajın m
düzlemin kesişmesi ile doğru, üçünün kesişmesi ile bir nokta (x n-1 , y n-1 ) 1-b mesajı olduğuna dair kanıtını ortaya koyarak Ayşe’yi ikna eder.
(anahtar) elde edilir. Böylelikle herhangi üç kişinin bir araya
gelmesi ile kesişim noktası yani anahtar oluşturabilir. (0, s) Şekil 10. Habersiz transfer. Bit, tamsayı ve dizi olmak üzere üç tip taahhüt şeması vardır.
(x , y ) Taahhüt şemalarının iki özelliği sağlaması beklenmektedir.
1
1
L 1 (x , y ) 2.4.1. Rabin Habersiz Transferi [9,10] Bunlar;
3
3
Rabin’in protokolünde RSA algoritması kullanılmaktadır. Bu Gizleme: Taahhüt aşamasından sonra kötü niyetli bir alıcı
(x , y )
2
2
L 2 protokol ile Ayşe’nin gönderdiği mesajın şifresini Bora yüzde taahhüt edilen veri hakkında hiçbir şey öğrenememelidir. Yani,
Şekil 9. Shamir sır paylaşımı. elli olasılıkla çözebilmektedir. Ayşe ise Bora’nın, mesajın şifresini kasayı alan kişi anahtarı bilmediğinden asla açamamalıdır.
çözüp çözemediğini bilememektedir. Bir başka deyişle Ayşe, Bağlama: Kötü niyetli gönderici, kanıt aşamasında alıcıyı iki
S Bora’nın mesajı çözdüğünü ancak yüzde elli olasılıkla
Şimdiye kadar tarif edilen yöntemlerde grup üyelerinin dürüst bilmektedir. farklı veri konusunda ikna edememelidir. Yani, kasadaki m
olduklarını varsaydık. Grup üyelerinden biri veya birkaçının mesajını ondan farklı birm' mesajı şeklinde açamamalıdır.
dürüst olmayabileceğinin de dikkate alınması gerekebilir. 1. Ayşe, p ve q asal sayıları ile RSA modülü n=pq ve 2.5.1. Örnek bir Taahhüt Şeması
L 3 Elbette ki grupta eşik sayıda kişi anlaşarak anahtarı her zaman ilgili e açık anahtarı üretir.
a. İlk aşamada; Bora, rasgele k anahtarı üretir ve E (m)’yi
oluşturabilir. Bu durumu dikkate alarak geliştirilmiş sır paylaşımı 2. Ayşe, mesaj m’yi açık anahtarı kullanarak şifreler Ayşe’ye gönderir. k
e
protokolleri de vardır. Bu yöntemlerde, çok taraflı hesaplama m mod n.
ile birlikte sıfır bilgi protokolleri gibi ileri kripto protokolleri 3. Ayşe “şifreli mesajı”, n ve e’yi Bora’ya gönderir, b. İkinci aşamada; Bora k anahtarını Ayşe’ye gönderir. Ayşe
de kullanılmaktadır. şifreyi çözerek mesajı elde eder.
4. Bora, rasgele bir x:1<x<n sayısı bulur ve x mod
2
n’i hesaplar ve Ayşe’ye gönderir. Bu örneğin gizleme ve bağlama özelliklerini yerine getirip
getirmediğine bakalım. İlk aşamada mesaj rasgele bir anahtar
5. Ayşe, p ve q asal sayılarını bildiği için x = x mod
2
1
n’i hesaplayabilir. Karekök sonucu iki olasılık vardır, ile şifrelendiğinden Ayşe ikinci aşamadan önce hesaplamaya
x =x mod n veya x =-x mod n. Ayşe bunlardan birini dayalı zorluk nedeniyle mesaj hakkında bilgi
1
1
rasgele seçip (yüzde elli olasılıkla) Bora’ya gönderir. edinemeyeceğinden gizleme özelliği sağlanmaktadır. Fakat
ikinci aşamada Bora farklı bir anahtar gönderebileceğinden
6. Bora, d=OBEB(x-x ,n)’yi hesaplar.
Şekil 8. Blakley sır paylaşımı. 1
92 Sayı 05 Ocak-Nisan 2011 http://www.bilgem.tubitak.gov.tr/ 93
·