1994 yılında bilgisayar bilimcisi Peter Shor keşfetti Kuantum bilgisayarlar icat edilmiş olsaydı, çevrimiçi olarak paylaşılan bilgileri korumak için kullanılan altyapının çoğunu yok edeceklerdi. Bu korkutucu olasılık, araştırmacıları kuantum bilgisayar korsanlarının eline düşmekten olabildiğince fazla bilgi kurtarmak için yeni, “kuantum sonrası” şifreleme şemaları üretmeye çabaladı.

Bu yılın başlarında, Ulusal Standartlar ve Teknoloji Enstitüsü ortaya Kuantum sonrası bir kriptografi standardı arayışında dört finalist. Üçü “kafes kriptografisi” kullanıyor - kafeslerden ilham alan bir şema, uzayda düzenli nokta düzenlemeleri.

Kafes kriptografisi ve diğer kuantum sonrası olasılıklar, önemli şekillerde mevcut standartlardan farklıdır. Ama hepsi matematiksel asimetriye güveniyor. Mevcut birçok kriptografi sisteminin güvenliği çarpma ve çarpanlara ayırmaya dayanır: Herhangi bir bilgisayar iki sayıyı hızla çarpabilir, ancak kriptografik olarak büyük bir sayıyı asal bileşenlerine ayırmak yüzyıllar alabilir. Bu asimetri, sırların kodlanmasını kolaylaştırır, ancak kodunun çözülmesini zorlaştırır.

Shor'un 1994 algoritmasında ortaya çıkardığı şey, bir faktoring tuhaflığının onu kuantum bilgisayarların saldırılarına karşı savunmasız hale getirmesiydi. “Kuantum bilgisayarın yapabileceği çok özel, özel bir şey” dedi. Katherine Stange, Colorado Üniversitesi, Boulder'da bir matematikçi. Böylece, Shor'dan sonra kriptografların yeni bir işi vardı: Yapması kolay, ancak geri alınması neredeyse imkansız olan yeni bir matematiksel işlem seti bulun.

Kafes kriptografisi şimdiye kadarki en başarılı girişimlerden biridir. İlk olarak 1990'larda geliştirilmiş olup, tersine mühendislik puan toplamlarının zorluğuna dayanır.

Kafes kriptografisini tanımlamanın bir yolu: Arkadaşınızın, düzlemin her yerinde düzenli, tekrar eden bir düzende sadece bir grup noktadan oluşan bir kafesi olduğunu hayal edin. Arkadaşınız bu noktalardan 10 tanesini adlandırmanızı istiyor. Ama zorlaşıyor ve tüm kafesi çizmeyecek. Bunun yerine, sadece iki noktayı listeler - ilki x-101 değeri ve a y- değeri 19, diğeri [235, 44] koordinatlarıyla.

Neyse ki, bir kafes üzerinde yeni noktalar bulmak kolaydır, çünkü bir kafes üzerinde herhangi iki noktayı toplayıp çıkardığınızda, aynı kafeste üçüncü bir nokta elde edersiniz. Yani tek yapmanız gereken arkadaşınızın size verdiği puanları toplamak ya da tamsayılarla çarpmak ve sonra onları toplamak ya da ikisinin bir kombinasyonu. Bunu sekiz farklı şekilde yapın ve arkadaşınızın sorusuna cevap verebileceksiniz.

Ama arkadaşın hala memnun değil. Size aynı iki başlangıç ​​noktasını verir ve ardından aynı kafes üzerinde [0, 0] yakınında bir nokta bulup bulamayacağınızı sorar. Bu soruyu doğru cevaplamak için, sizi [101, 19]'a yaklaştıran [235, 44] ve [0, 0] kombinasyonunu bulmalısınız. Bu problem ilkinden çok daha zordur ve muhtemelen cevabı almak için tahminde bulunup kontrol etmek zorunda kalacaksınız. Kafes kriptografisinin altında yatan şey bu asimetridir.

Bilgi paylaşmak için gerçekten kafes şifreleme kullanmak istiyorsanız, aşağıdakileri yaparsınız. Bir arkadaşınızın (daha iyi olan!) size güvenli bir mesaj göndermek istediğini hayal edin. Kare bir sayı ızgarasıyla başlarsınız. Diyelim ki iki satır ve iki sütun var ve şöyle görünüyor:

Şimdi sadece sizin bildiğiniz özel bir “anahtar” buluyorsunuz. Bu örnekte, özel anahtarınızın yalnızca iki gizli sayı olduğunu varsayalım: 3 ve -2. İlk sütundaki sayıları 3 ile, ikinci sütundaki sayıları -2 ile çarparsınız. İki girişli üçüncü bir sütun elde etmek için sonuçları her satırda toplayın.

Yeni sütunu ızgaranızın sonuna yapıştırın. Bu yeni üç sütunlu kılavuz sizin ortak anahtarınızdır. Özgürce paylaşın!

(Gerçek dünya senaryosu biraz daha karmaşık olacaktır. Bilgisayar korsanlarının özel anahtarınızı çözmesini önlemek için, son sütununuza biraz rastgele gürültü eklemelisiniz. Ancak burada basitlik adına bu adımı görmezden geleceğiz. )

Şimdi arkadaşınız size bir mesaj göndermek için ortak anahtarı kullanacak. Kendine ait iki gizli sayı düşünür: 2 ve 0. İlk satırdaki sayıları 2 ile, ikinci satırdakileri 0 ile çarpar. Daha sonra, üçüncü bir satır elde etmek için her sütundaki sonuçları toplar.

Şimdi yeni satırı ızgaranın altına iliştiriyor ve size geri gönderiyor. (Yine, gerçek bir sistemde, sırasına biraz gürültü eklemesi gerekir.)

Şimdi mesajı okuyacaksın. Bunu yapmak için arkadaşınızın son satırının doğru olup olmadığını kontrol edin. Onun satırının ilk iki girişine kendi özel anahtarınızı uygulayın. Sonuç, son girişle eşleşmelidir.

Arkadaşınız, son sütunda yanlış numara içeren bir satır göndermeyi de seçebilir. Bu sayının senin hesaplarına uymayacağını biliyor.

Arkadaşınız son sayının doğru olduğu bir satır gönderirse, bunu 0 olarak yorumlarsınız. Sayının yanlış olduğu bir satır gönderirse, bunu 1 olarak yorumlarsınız. Dolayısıyla satır, tek bir sayıyı kodlar. bit: 0 veya 1.

Dışarıdan bir saldırganın sizin veya arkadaşınızın özel anahtarına erişimi olmayacağını unutmayın. Bunlar olmadan, saldırganın son sayının doğru olup olmadığı hakkında hiçbir fikri olmayacaktır.

Pratikte, bir bitten daha uzun mesajlar göndermek istersiniz. Yani 100 bitlik bir mesaj almak isteyen kişiler, sadece bir tane yerine 100 yeni sütun üretecektir. Ardından mesajı gönderen kişi, son 100 girişi her giriş için 0 veya 1 kodlayacak şekilde değiştirerek tek bir yeni satır oluşturacaktır.

Kafes kriptografisi gerçekten uygulanırsa, bu senaryoda ele alınmayan sayısız nüansa sahip olacaktır. Örneğin, mesajın meraklı gözlerden gerçekten korunmasını istiyorsanız, matrisin düşünülemez sayıda girişe sahip olması gerekir, bu da her şeyi kullanmaya değmeyecek kadar hantal hale getirir. Bunu aşmak için araştırmacılar, parametre sayısını azaltabilecek faydalı simetrilere sahip matrisler kullanırlar. Bunun ötesinde, sorunun kendisine, hataların dahil edilme şekline ve daha fazlasına uygulanabilecek bir dizi ince ayar var.

Elbette, tıpkı Shor'un faktoring için yaptığı gibi, kafes kriptografisinde birinin ölümcül bir kusur bulması her zaman mümkündür. Belirli bir şifreleme şemasının olası herhangi bir saldırı karşısında çalışacağına dair bir güvence yoktur. Kriptografi, kırılana kadar çalışır. Nitekim bu yaz başında umut verici bir kuantum sonrası şifreleme şeması kırıldı kuantum bilgisayar değil, sıradan bir dizüstü bilgisayar kullanarak. Stange'e göre, tüm proje rahatsız edici bir paradoks yaratıyor: "Kriptografi hakkında çok şaşırtıcı bulduğum şey, insan ırkı için bu altyapıyı, insan olarak yeteneklerimizin sınırlı olduğuna dair kesin inanç üzerine inşa etmiş olmamız," dedi. "Çok geri kalmış."

Düzeltme: 9 Kasım 2022
Bu makalenin orijinal versiyonu, kafes kriptografisinde çözülmesi zor problemin, kafes üzerinde orijine yakın belirli bir nokta bulmak olduğunu söyledi. Aslında, belirli bir noktayı bulmak nispeten basittir. Zor sorun, orijine yakın bir yerde bilinmeyen bir nokta bulmaktır. Makale bu gerçeği yansıtacak şekilde değiştirilmiştir.