Şifreli metin ayırt edilemezliği - Ciphertext indistinguishability

Şifreli metin ayırt edilemezliği birçok kişinin mülküdür şifreleme şemaları. Sezgisel olarak, eğer bir şifreleme sistemi mülkiyetine sahiptir ayırt edilemezlik, o zaman bir düşman çiftleri ayırt edemez şifreli metinler şifreledikleri mesaja göre. Altında ayırt edilemezlik özelliği düz metin saldırısı seçildi çoğu için temel bir gereklilik olarak kabul edilir kanıtlanabilir şekilde güvenli açık anahtarlı şifreleme sistemleri ancak bazı planlar aynı zamanda altında ayırt edilemezlik sağlar seçilen şifreli metin saldırısı ve uyarlanabilir seçilmiş şifreli metin saldırısı. Seçilen düz metin saldırısı altındaki ayırt edilemezlik, anlamsal güvenlik ve birçok kriptografik kanıt bu tanımları birbirinin yerine kullanır.

Bir şifreleme sistemi kabul edilir ayırt edilemezlik açısından güvenli rakip tarafından belirlenen iki öğeli mesaj alanından rastgele seçilen bir mesajın şifrelenmesi verildiğinde, hiçbir düşman mesaj seçimini rastgele tahmin etmekten önemli ölçüde daha iyi bir olasılıkla belirleyemezse (¹⁄₂). Herhangi bir düşman, seçilen şifreli metni aşağıdakilerden önemli ölçüde daha büyük bir olasılıkla ayırt etmeyi başarabilirse¹⁄₂, bu durumda bu düşman şifreli metni ayırt etmede bir "avantaja" sahip olarak kabul edilir ve şema değil ayırt edilemezlik açısından güvenli kabul edilir. Bu tanım, güvenli bir şemada düşmanın bir şifreli metni görmekten hiçbir bilgi öğrenmemesi gerektiği fikrini kapsar. Bu nedenle, rakip rastgele tahmin etmekten daha iyisini yapmamalıdır.

Biçimsel tanımlar

Ayrılmazlık açısından güvenliğin, saldırganın yetenekleri hakkında yapılan varsayımlara bağlı olarak birçok tanımı vardır. Normalde bir oyun, şifreleme sisteminin dikkate alındığı yer güvenli eğer hiçbir rakip oyunu rastgele tahmin etmesi gereken bir düşmandan önemli ölçüde daha büyük bir olasılıkla kazanamazsa. Kriptografide kullanılan en yaygın tanımlar şunlardır: altında ayırt edilemezlik düz metin saldırısı seçildi (IND-CPA olarak kısaltılmıştır), altında ayırt edilemezlik (uyarlanabilir olmayan) seçilen şifreli metin saldırısı (IND-CCA1) ve altında ayırt edilemezlik uyarlanabilir seçilmiş şifreli metin saldırısı (IND-CCA2). Son tanımlardan herhangi biri kapsamındaki güvenlik, önceki tanımlara göre güvenliği ifade eder: IND-CCA1 güvenli olan bir şema ayrıca IND-CCA2 güvenli ve IND-CCA2 güvenli olan bir şema hem IND-CCA1 hem de IND-CPA güvenlidir. Bu nedenle IND-CCA2, üç güvenlik tanımının en güçlüsüdür.

Seçilmiş düz metin saldırısı (IND-CPA) altında ayırt edilemezlik

Bir olasılık için asimetrik anahtar şifreleme algoritması, altında ayırt edilemezlik düz metin saldırısı seçildi (IND-CPA), bir rakip ve bir rakip arasındaki aşağıdaki oyunla tanımlanır. Temel alan şemalar için hesaplama güvenliği düşman, bir olasılıksal polinom zamanı Turing makinesi yani oyunu tamamlaması ve bir tahmin bir polinom zaman adımı sayısı içinde. Bu tanımda E (PK, M) bir mesajın şifrelenmesini temsil eder M anahtarın altında PK:

Meydan okuyan, bir anahtar çifti oluşturur PK, SK bazı güvenlik parametrelerine göre k (ör. bit cinsinden anahtar boyutu) ve yayınlar PK düşmana. Meydan okuyan SK.
Düşman, polinomik olarak sınırlı sayıda şifreleme veya başka işlemler gerçekleştirebilir.
Sonunda, rakip iki ayrı seçilmiş düz metin gönderir. ${ displaystyle scriptstyle M_ {0}, M_ {1}}$ meydan okuyan kişiye.
Meydan okuyan biraz seçer b ${ displaystyle scriptstyle in}$ {0, 1} tek tip olarak rastgele ve meydan okuma şifreli metin C = E (PK, ${ displaystyle scriptstyle M_ {b}}$ ) düşmana geri dönüyor.
Düşman, herhangi bir sayıda ek hesaplama veya şifreleme yapmakta özgürdür. Son olarak, değeri için bir tahmin çıkarır b.

Bir şifreleme sistemi Seçilen düz metin altında ayırt edilemez her olasılıklı polinom zamanlı rakibin sadece ihmal edilebilir bir değeri varsa saldırı "avantaj "Rastgele tahmin üzerinde. Bir rakibin yukarıdaki oyunu olasılıkla kazanırsa ihmal edilebilir bir" avantaja "sahip olduğu söylenir. ${ displaystyle scriptstyle sol ({ frac {1} {2}} sağ) , + , epsilon (k)}$ , nerede ${ displaystyle scriptstyle epsilon (k)}$ bir ihmal edilebilir işlev güvenlik parametresinde kyani her (sıfır olmayan) polinom işlevi için ${ displaystyle scriptstyle poli ()}$ var ${ displaystyle scriptstyle k_ {0}}$ öyle ki ${ displaystyle scriptstyle | epsilon (k) | ; <; sol | { frac {1} {poli (k)}} sağ |}$ hepsi için ${ displaystyle scriptstyle k ;> ; k_ {0}}$ .

Düşman bilmesine rağmen ${ displaystyle scriptstyle M_ {0}}$ , ${ displaystyle scriptstyle M_ {1}}$ ve PK, E'nin olasılıksal doğası, şifrelemenin ${ displaystyle scriptstyle M_ {b}}$ birçok geçerli şifreli metinlerden yalnızca biri olacak ve bu nedenle şifreleme ${ displaystyle scriptstyle M_ {0}}$ , ${ displaystyle scriptstyle M_ {1}}$ ve ortaya çıkan şifreli metinleri meydan okuma şifreli metni ile karşılaştırmak, düşmana ihmal edilemez herhangi bir avantaj sağlamaz.

Yukarıdaki tanım bir asimetrik anahtar şifreleme sistemine özgü olsa da, simetrik açık anahtar şifreleme işlevini bir şifreleme oracle, gizli şifreleme anahtarını tutan ve düşmanın isteği üzerine rastgele düz metinleri şifreleyen.

Simetrik IND-CPA Oyunu, Resmileştirilmiş

Seçilmiş bir şifresiz metin saldırısı gerçekleştirmenin çekişmeli süreci genellikle şu şekilde özetlenir: Kriptografik Oyun. Simetrik IND-CPA'yı test etmek için yukarıda açıklanan oyun tanımlanmıştır.^[1] İzin Vermek ${ displaystyle { mathcal {K}}}$ anahtar oluşturma işlevi olmak, ${ displaystyle { mathcal {E}}}$ bir şifreleme işlevi olmak ve ${ displaystyle { mathcal {D}}}$ bir şifre çözme işlevi olabilir. İzin Vermek ${ displaystyle { mathcal {S}} { mathcal {E}} = ({ mathcal {K}}, { mathcal {E}}, { mathcal {D}})}$ simetrik bir şifreleme şeması olabilir. Oyun ${ displaystyle Guess}$ olarak tanımlanır:

Düşman, istediği kadar çok kez kendi seçtiği iki düz metin mesajı seçer ve bunları LR mesajlardan birini şifreleyen bir şifreli metin döndüren oracle. Bir düşmanın avantajı, onun değerini tahmin etme olasılığı ile belirlenir. b, oyunun başında rastgele seçilen ve şifrelenmiş mesajı belirleyen bir değer LR oracle. Bu nedenle avantajı şu şekilde tanımlanır:^[1]

Seçilen şifreli metin saldırısı / uyarlanabilir seçilmiş şifreli metin saldırısı (IND-CCA1, IND-CCA2) altında ayırt edilemezlik

Uyarlanabilir olmayan ve uyarlanabilir Seçilmiş Şifreli Metin Saldırısı (IND-CCA1, IND-CCA2) altında ayırt edilemezlik, IND-CPA'ninkine benzer bir tanım kullanır. Bununla birlikte, açık anahtara (veya simetrik durumda şifreleme oracle'ına) ek olarak, düşmana bir şifre çözme oracle düşmanın isteği üzerine rastgele şifreli metinlerin şifresini çözen, düz metni döndüren. Uyarlanabilir olmayan tanımda, düşmanın bu kehaneti yalnızca sorgulama şifreli metnini alana kadar sorgulamasına izin verilir. Uyarlanabilir tanımda, düşman, şifre çözme için şifre metnini geçemeyebileceği uyarısıyla bir şifre çözme oracle'ını sorgulamaya devam edebilir (aksi takdirde, tanım önemsiz olur).

Meydan okuyan, bir anahtar çifti oluşturur PK, SK bazı güvenlik parametrelerine göre k (ör. bit cinsinden anahtar boyutu) ve yayınlar PK düşmana. Meydan okuyan SK.
Düşman, herhangi bir sayıda şifreleme, şifre çözme oracle'ına rastgele şifreli metinlere dayalı çağrı veya diğer işlemleri gerçekleştirebilir.
Sonunda, rakip iki ayrı seçilmiş düz metin gönderir. ${ displaystyle scriptstyle M_ {0}, , M_ {1}}$ meydan okuyan kişiye.
Meydan okuyan biraz seçer b ∈ {0, 1} tek tip olarak rastgele ve "meydan okuma" şifreli metnini gönderir C = E (PK, ${ displaystyle scriptstyle M_ {b}}$ ) düşmana geri dönüyor.
Düşman, herhangi bir sayıda ek hesaplama veya şifreleme yapmakta özgürdür.
1. İçinde uyarlanabilir olmayan durumda (IND-CCA1), düşman değil şifre çözme oracle'ına başka çağrılar yapın.
2. İçinde uyarlanabilir durumda (IND-CCA2), rakip şifre çözme oracle'ına başka çağrılar yapabilir, ancak meydan okuma şifre metnini gönderemez C.
Son olarak, rakip, değer için bir tahmin üretir. b.

Bir şema IND-CCA1 / IND-CCA2 güvenlidir, eğer hiçbir rakibin yukarıdaki oyunu kazanmada ihmal edilemez bir avantajı yoktur.

Rastgele gürültüden ayırt edilemez

Bazen, şifreli metin dizesinin rakip tarafından rastgele bir dizeden ayırt edilemeyeceği şifreleme şemalarına ihtiyaç duyarız.^[2]

Düşman bir mesajın var olup olmadığını anlayamazsa mesajı yazan kişiye verir. makul bir şekilde reddetme.

Şifrelenmiş iletişim bağlantıları oluşturan bazı kişiler, trafik analizini daha zor hale getirmek için şifrelenmiş her veri biriminin içeriğini rastgele verilerden ayırt edilemez kılmayı tercih eder.^[3]

Şifrelenmiş verileri depolamak için sistemler oluşturan bazı kişiler, verileri rastgele verilerden ayırt edilemez hale getirmeyi tercih eder. veri gizleme daha kolay.Örneğin, bazı disk şifreleme gibi TrueCrypt bazı türlerden kalan masum rastgele verilerdeki verileri gizlemeye çalışın. veri silme Başka bir örnek olarak, bazı steganografi masum "rasgele" nin istatistiksel özellikleriyle eşleşmesini sağlayarak verileri gizlemeye çalışmak görüntü gürültüsü dijital fotoğraflarda.

Böyle desteklemek için reddedilebilir şifreleme sistemlerde, birkaç şifreleme algoritması şifreli metin mesajlarını rastgele bit dizilerinden ayırt edilemez hale getirmek için özel olarak tasarlanmıştır.^[4]^[5]^[6]

Çoğu uygulama, rastgele bitlerden ayırt edilemeyen şifrelenmiş mesajlar üretmek için bir şifreleme algoritmasına ihtiyaç duymaz. Ancak, bazı yazarlar bu tür şifreleme algoritmalarının kavramsal olarak daha basit, üzerinde çalışılması daha kolay ve pratikte daha çok yönlü olduğunu ve çoğu IND-CPA şifreleme Aslında algoritmalar, rastgele bitlerden ayırt edilemeyen şifreli mesajlar üretirler.^[7]

Eşitlikler ve çıkarımlar

Şifrelenmiş iletişimin gizliliğini korumak için ayırt edilemezlik önemli bir özelliktir. Bununla birlikte, ayırt edilemezlik özelliğinin bazı durumlarda diğer, görünüşte ilgisiz güvenlik özelliklerini ima ettiği bulunmuştur. Bazen bu çıkarımlar her iki yöne de gider ve iki tanımı eşdeğer kılar; örneğin, uyarlanabilir seçilmiş şifreli metin saldırısı (IND-CCA2) altında ayırt edilememe özelliğinin, şekillendirilemezlik aynı saldırı senaryosu altında (NM-CCA2). Biçimlendirilemezlik, gizlilikten ziyade mesaj bütünlüğü ile ilgilenen bir özellik olduğundan, bu eşdeğerlik hemen açık değildir. Diğer durumlarda, diğer yararlı tanımları ima etmek için ayırt edilemezliğin belirli başka tanımlarla birleştirilebileceği ve bunun tersi de gösterilmiştir. Aşağıdaki liste, hiçbir şekilde eksiksiz olmasa da bilinen birkaç çıkarımı özetlemektedir.

Gösterim ${ displaystyle scriptstyle A ; Rightarrow ; B}$ A özelliğinin B özelliğini ifade ettiği anlamına gelir. ${ displaystyle scriptstyle A ; Leftrightarrow ; B}$ A ve B özelliklerinin olduğu anlamına gelir eşdeğer. ${ displaystyle scriptstyle A ; Rightarrow ; B}$ A mülkünün mutlaka B mülkü anlamına gelmediği anlamına gelir.

IND-CPA ${ displaystyle scriptstyle Leftrightarrow}$ anlamsal güvenlik EBM altında.
NM-CPA (şekillendirilemezlik seçilen düz metin saldırısı altında) ${ displaystyle scriptstyle Rightarrow}$ IND-CPA.
NM-CPA (şekillendirilemezlik seçilen düz metin saldırısı altında) ${ displaystyle scriptstyle not Rightarrow}$ IND-CCA2.
NM-CCA2 (şekillendirilemezlik uyarlanabilir seçilmiş şifreli metin saldırısı altında) ${ displaystyle scriptstyle Leftrightarrow}$ IND-CCA2.

Ayrıca bakınız

Referanslar

^ ^a ^b Bellare, Mihir; Rogaway, Phillip (11 Mayıs 2005). "Modern Kriptografiye Giriş, Bölüm 5: Simetrik Şifreleme" (PDF). s. 93. Alındı 6 Nisan 2020.
^ Chakraborty, Debrup; Rodríguez-Henríquez., Francisco (2008). Çetin Kaya Koç (ed.). Kriptografik Mühendislik. s. 340. ISBN 9780387718170.
^ iang (2006-05-20). "Tesadüfen ayırt edilemez". Alındı 2014-08-06.
^ Bernstein, Daniel J .; Hamburg, Mike; Krasnova, Anna; Lange, Tanja (2013-08-28). "Elligator: Eliptik eğri noktaları, tek tip rastgele dizilerden ayırt edilemez" (PDF). Alındı 2015-01-23.
^ Möller Bodo (2004). "Sözde Rastgele Şifreleme Metinlerine Sahip Açık Anahtarlı Şifreleme Düzeni". Bilgisayar Güvenliği - ESORICS 2004. Bilgisayar Bilimlerinde Ders Notları. 3193. s. 335–351. doi:10.1007/978-3-540-30108-0_21. ISBN 978-3-540-22987-2.
^ Moore, Cristopher; Mertens, Stephan (2011). Hesaplamanın Doğası. ISBN 9780191620805.
^ Rogaway, Phillip (2004-02-01). "Olmayan Tabanlı Simetrik Şifreleme" (PDF). s. 5–6. Alındı 2014-08-07.

Katz, Jonathan; Lindell, Yehuda (2007). Modern Kriptografiye Giriş: İlkeler ve Protokoller. Chapman & Hall / CRC Basın. ISBN 978-1584885511.

[:0-1] Bellare, Mihir; Rogaway, Phillip (11 Mayıs 2005). "Modern Kriptografiye Giriş, Bölüm 5: Simetrik Şifreleme" (PDF). s. 93. Alındı 6 Nisan 2020.

[2] Chakraborty, Debrup; Rodríguez-Henríquez., Francisco (2008). Çetin Kaya Koç (ed.). Kriptografik Mühendislik. s. 340. ISBN 9780387718170.

[3] (2006-05-20). "Tesadüfen ayırt edilemez". Alındı 2014-08-06.

[4] Bernstein, Daniel J .; Hamburg, Mike; Krasnova, Anna; Lange, Tanja (2013-08-28). "Elligator: Eliptik eğri noktaları, tek tip rastgele dizilerden ayırt edilemez" (PDF). Alındı 2015-01-23.

[5] Möller Bodo (2004). "Sözde Rastgele Şifreleme Metinlerine Sahip Açık Anahtarlı Şifreleme Düzeni". Bilgisayar Güvenliği - ESORICS 2004. Bilgisayar Bilimlerinde Ders Notları. 3193. s. 335–351. doi:10.1007/978-3-540-30108-0_21. ISBN 978-3-540-22987-2.

[6] Moore, Cristopher; Mertens, Stephan (2011). Hesaplamanın Doğası. ISBN 9780191620805.

[7] Rogaway, Phillip (2004-02-01). "Olmayan Tabanlı Simetrik Şifreleme" (PDF). s. 5–6. Alındı 2014-08-07.

[1]

[2]

[3]

[4]

[5]

[6]

[7]