Goldwasser–Micali (GM) kriptosistemi 1982 yılında Shafi Goldwasser ve Silvio Micali tarafından geliştirilmiş bir . GM standart kriptografik varsayımlar altında güvenliği kanıtlanmış ilk probabilistik yöntemidir. Bununla birlikte başlangıç düz metinden yüzlerce kez daha geniş olan şifreli metinler olduğundan verimli bir kriptosistem değildir. Kriptosistemin güvenlik özelliğini kanıtlamak için Shafi Goldwasser ve Silvio Micali anlamsal güvenliğin geniş alanda kullanılan bir tanımını önerdiler.
Temelleri
GM kriptosistemi kuadratik kalan probleminin p ve q büyük asal sayılar olmak üzere, N=p.q modunun zorluğunun varsayımına dayanan anlamsal güvenliktir. Bu varsayım verilen(x,N)'nin x'in, +1 için bir Jacobi sembolü olduğunda, N(x=y^2 mod N bazı y'ler için) modulüne göre kuadratik bir kalan olup olmadığını belirleme zorluğunu ifade eder. Kuadratik kalan problemi yeni kuadratik kalanlar herhangi bir kısım tarafından üretilebiliyorken verilen N nin çarpanlara ayırımını bu çarpanla ayrım bilgisi verilemese bile kolayca çözebilir. GM kriptosistemi birbirinden ayrı düz metin bitlerini ya rastgele kuadratik kalanlar ya da tüm kuadratik sembol +1 ile birlikte modül N'ye göre kalmayanları alıp şifreleyerek bu asimetrikliği sağlamış olur. Alıcılar N'nin çarpanlarını gizli anahtar olarak kullanır ve mesajı aldığı şifreli metnin değerlerinin kuadratik kalanını test ederek deşifrelerler.
Çünkü Goldwasser–Micali düz metnin her tek bitini şifrelemek için yaklaşık olarak |N| boyutunda bir değer üretir. GM şifreleme sağlam ölçüde şifreli metin genişlemesini sonucunu verir. Çarpanlara ayırmaya çalışma ataklarını önlemek için, |N| nin yüzlerce bit ya da daha fazla olması tavsiye edilmiştir. Bu yüzden yöntem temelde bir kavram kanıtı olarak hizmet eder ve Elgamal gibi daha etkili kanıtlanabilir güvenlik yöntemleri geliştirilmiştir. Çünkü şifreleme probabilistik algoritma kullanılarak şifrelenmiştir. Verilen bir düzmetin her bir zamanda şifrelediği birbirinden çok farklı şifrelimetinleri üretebilir. Bu hasımın bilinen şifrelimetinleri sözlükle karşılaştırarak haberleşmeler arasında müdahale edip eriştiği mesajlardan herhangi bir benzerlik bulup düz metne erişmeye çalışmasını önleme avantajı demektir.
Yöntemin Tanıtılması
Goldwasser–Micali 3 algoritma içerir: açık ve gizli anahtar üreten probabilistik anahtar üretimi algoritması, algoritması ve bir deterministik deşifreleme algoritması.
Bu yöntem verilen bir x değerinin kare mod N, ((p,q) N nin çarpanları) olup olmadığına karar vermenin zorluğuna güvenmektedir. Bu aşağıdaki prosedürü kullanarak başarılır:
1.xp = x mod p, xq = x mod q Hesapla 2.EĞER VE ise x mod N. ye göre bir kuadratik kalandır.
Anahtar üretimi
GM içindeki kullanılan mod alma işlemi RSA kriptosistem içerisindeki aynı yöntemle gerçekleştirilir. (ayrıntılar için RSA anahtar üretimine bakınız)
1.Alice 2 farklı büyük p ve q asal sayılarını rastgele ve her biri bir birinden bağımsız olacak şekilde üretir. 2.Alice N = p q. yu hesaplar 3.Alice olacak şekilde bir x bulur ve bundan dolayı Jacobi sembolü is +1 dir.
X değeri rastgele sayılar seçerek ve 2 Legendre sembolünü test ederek bulunabilir. Eğer (p,q) =3 mod 4 (N Blum Tam sayısı) ise o zaman N-1 değeri gereken özelliği karşılıyor anlamına gelir. Açık anahtar (x,N) den oluşur. Gizli anahtar (p,q) çarpanlarından oluşur.
Mesaj Şifreleme
Varsayalım ki Bob Alice e m mesajını göndermeyi istesin:
Bob ilk önce m i (m1, ..., mn) bitlerinden oluşan bir string olarak çözecektir.
1.Her mi, biti için, Bob modulo N den birimler halinde rastgele y değeri üretir veya
GCD(y,N) = 1. olacak şekilde rastgele değerler üretir. . değerlerini sonuç olarak üretir.
Bob (c1, ..., cn). Şifreli metinlerini gönderir.
Mesaj Deşifreleme
Alice (c1, ..., cn) i alır. Aşağıdaki prosedürü kullanarak m yi geri elde edebilir.
1.Asal çarpan (p,q) kullanan Her bir i için, Alice ci değerinin kuadratik kalan olup olmadığını belirler eğer öyle ise mi = 0, değilse mi = 1. dir.
Alice m = (m1, ..., mn). Mesajını çıktı olarak üretir.
Güvenlik özellikleri
Burada basitçe bu kriptosistemi Jacobi sembolü +1 ile rastgele modül N değerinin kuadratik kalan olup olmadığını belirleme problemine dönüştürerek kırmaya çalışma vardır. Eğer verilen bir A algoritması kriptosistemi kırarsa, ardından verilen bir 'x' değerinin kuadratik modül N kalanı olup olmadığını belirlemek için, biz A'yı (x,N) açık anahtarlarını kullanarak kırabildiğini anlamak için test ederiz. Eğer 'x' bir kalan değilse o zaman 'A' doğru olarak çalışacaktır. Ancak eğer 'x' bir kalansa o zaman her şifreli metin basitçe rastgele kuadratik kalan olabilir, bu yüzden 'A' zamanın yarısından daha doğru olamaz. Bundan başka bu problem verilen bir 'B' için her açık anahtarı tıpkı diğer açık anahtar gibi güvenli kılan rastgele kendini dönüştürme problemidir.
GM kriptosistemi homomorfik özelliklere sahiptir. Eğer c0, c1m0, m1, bitlerinin şifrelenmiş halleriyse o zaman c0c1 mod N, in şifrelenmiş halleri olacaktır. Bu sebebten dolayı GM kriptosistemi bazen daha karmaşık kriptografik ilkel yapılarla birlikte kullanılır.
Kaynakça
- S. Goldwasser, S. Micali (1982). "Probabilistic encryption and how to play mental poker keeping secret all partial information". Proc. 14th Symposium on Theory of Computing. ss. 365-377. doi:10.1145/800070.802212.
- S. Goldwasser, S. Micali (1984). "Probabilistic encryption". Journal of Computer and System Sciences. 28 (2). ss. 270-299. doi:10.1016/0022-0000(84)90070-9.
Dış bağlantılar
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Goldwasser Micali GM kriptosistemi 1982 yilinda Shafi Goldwasser ve Silvio Micali tarafindan gelistirilmis bir GM standart kriptografik varsayimlar altinda guvenligi kanitlanmis ilk probabilistik yontemidir Bununla birlikte baslangic duz metinden yuzlerce kez daha genis olan sifreli metinler oldugundan verimli bir kriptosistem degildir Kriptosistemin guvenlik ozelligini kanitlamak icin Shafi Goldwasser ve Silvio Micali anlamsal guvenligin genis alanda kullanilan bir tanimini onerdiler TemelleriGM kriptosistemi kuadratik kalan probleminin p ve q buyuk asal sayilar olmak uzere N p q modunun zorlugunun varsayimina dayanan anlamsal guvenliktir Bu varsayim verilen x N nin x in 1 icin bir Jacobi sembolu oldugunda N x y 2 mod N bazi y ler icin modulune gore kuadratik bir kalan olup olmadigini belirleme zorlugunu ifade eder Kuadratik kalan problemi yeni kuadratik kalanlar herhangi bir kisim tarafindan uretilebiliyorken verilen N nin carpanlara ayirimini bu carpanla ayrim bilgisi verilemese bile kolayca cozebilir GM kriptosistemi birbirinden ayri duz metin bitlerini ya rastgele kuadratik kalanlar ya da tum kuadratik sembol 1 ile birlikte modul N ye gore kalmayanlari alip sifreleyerek bu asimetrikligi saglamis olur Alicilar N nin carpanlarini gizli anahtar olarak kullanir ve mesaji aldigi sifreli metnin degerlerinin kuadratik kalanini test ederek desifrelerler Cunku Goldwasser Micali duz metnin her tek bitini sifrelemek icin yaklasik olarak N boyutunda bir deger uretir GM sifreleme saglam olcude sifreli metin genislemesini sonucunu verir Carpanlara ayirmaya calisma ataklarini onlemek icin N nin yuzlerce bit ya da daha fazla olmasi tavsiye edilmistir Bu yuzden yontem temelde bir kavram kaniti olarak hizmet eder ve Elgamal gibi daha etkili kanitlanabilir guvenlik yontemleri gelistirilmistir Cunku sifreleme probabilistik algoritma kullanilarak sifrelenmistir Verilen bir duzmetin her bir zamanda sifreledigi birbirinden cok farkli sifrelimetinleri uretebilir Bu hasimin bilinen sifrelimetinleri sozlukle karsilastirarak haberlesmeler arasinda mudahale edip eristigi mesajlardan herhangi bir benzerlik bulup duz metne erismeye calismasini onleme avantaji demektir Yontemin TanitilmasiGoldwasser Micali 3 algoritma icerir acik ve gizli anahtar ureten probabilistik anahtar uretimi algoritmasi algoritmasi ve bir deterministik desifreleme algoritmasi Bu yontem verilen bir x degerinin kare mod N p q N nin carpanlari olup olmadigina karar vermenin zorluguna guvenmektedir Bu asagidaki proseduru kullanarak basarilir 1 xp x mod p xq x mod q Hesapla 2 EGER xp p 1 2 1 modp displaystyle x p p 1 2 equiv 1 pmod p VE xq q 1 2 1 modq displaystyle x q q 1 2 equiv 1 pmod q ise x mod N ye gore bir kuadratik kalandir Anahtar uretimiGM icindeki kullanilan mod alma islemi RSA kriptosistem icerisindeki ayni yontemle gerceklestirilir ayrintilar icin RSA anahtar uretimine bakiniz 1 Alice 2 farkli buyuk p ve q asal sayilarini rastgele ve her biri bir birinden bagimsiz olacak sekilde uretir 2 Alice N p q yu hesaplar 3 Alice xp xq 1 displaystyle left frac x p right left frac x q right 1 olacak sekilde bir x bulur ve bundan dolayi Jacobi sembolu xN displaystyle left frac x N right is 1 dir X degeri rastgele sayilar secerek ve 2 Legendre sembolunu test ederek bulunabilir Eger p q 3 mod 4 N Blum Tam sayisi ise o zaman N 1 degeri gereken ozelligi karsiliyor anlamina gelir Acik anahtar x N den olusur Gizli anahtar p q carpanlarindan olusur Mesaj SifrelemeVarsayalim ki Bob Alice e m mesajini gondermeyi istesin Bob ilk once m i m1 mn bitlerinden olusan bir string olarak cozecektir 1 Her mi biti icin Bob modulo N den birimler halinde rastgele y degeri uretir veya GCD y N 1 olacak sekilde rastgele degerler uretir ci y2xmi modN displaystyle c i y 2 x m i pmod N degerlerini sonuc olarak uretir Bob c1 cn Sifreli metinlerini gonderir Mesaj DesifrelemeAlice c1 cn i alir Asagidaki proseduru kullanarak m yi geri elde edebilir 1 Asal carpan p q kullanan Her bir i icin Alice ci degerinin kuadratik kalan olup olmadigini belirler eger oyle ise mi 0 degilse mi 1 dir Alice m m1 mn Mesajini cikti olarak uretir Guvenlik ozellikleriBurada basitce bu kriptosistemi Jacobi sembolu 1 ile rastgele modul N degerinin kuadratik kalan olup olmadigini belirleme problemine donusturerek kirmaya calisma vardir Eger verilen bir A algoritmasi kriptosistemi kirarsa ardindan verilen bir x degerinin kuadratik modul N kalani olup olmadigini belirlemek icin biz A yi x N acik anahtarlarini kullanarak kirabildigini anlamak icin test ederiz Eger x bir kalan degilse o zaman A dogru olarak calisacaktir Ancak eger x bir kalansa o zaman her sifreli metin basitce rastgele kuadratik kalan olabilir bu yuzden A zamanin yarisindan daha dogru olamaz Bundan baska bu problem verilen bir B icin her acik anahtari tipki diger acik anahtar gibi guvenli kilan rastgele kendini donusturme problemidir GM kriptosistemi homomorfik ozelliklere sahiptir Eger c0 c1m0 m1 bitlerinin sifrelenmis halleriyse o zaman c0c1 mod N in sifrelenmis halleri olacaktir Bu sebebten dolayi GM kriptosistemi bazen daha karmasik kriptografik ilkel yapilarla birlikte kullanilir KaynakcaS Goldwasser S Micali 1982 Probabilistic encryption and how to play mental poker keeping secret all partial information Proc 14th Symposium on Theory of Computing ss 365 377 doi 10 1145 800070 802212 S Goldwasser S Micali 1984 Probabilistic encryption Journal of Computer and System Sciences 28 2 ss 270 299 doi 10 1016 0022 0000 84 90070 9 Dis baglantilar