Kuantum Kriptografi: Shor Algoritması ile Şifre Kırma

Kuantum kriptografi nedir ve Shor algoritması ile şifreler kuantum hızında nasıl kırılır? Peki kuantum bilgisayarlar standart enformasyon güvenliğini Shor algoritması ile nasıl ortadan kaldıracak? Geçen bölümde Shor algoritmasının çalışma mantığını gördük. Şimdi de kuantum kriptografi ve Shor algoritmasıyla şifre kırmayı göreceğiz. Merak etmeyin. Bunun için gereken matematiksel detayları önceki yazılarda verdim. Bu yazıda sadece kuantum bilgisayarların şifre kırma yöntemini çizimlerle göstererek anlatacağım. Hazırsanız başlayalım:

Kuantum kriptografi ve Shor algoritması

Geleneksel şifreleme yöntemlerinde yüzlerce basamaklı iki asal sayı alırız ve bunları birbiriyle çarparız. Şifreyi kırmak için de yeni devasa sayıyı asal çarpanlarına ayırmaya çalışırız. Bu da klasik bilgisayarların yüz yılda yapamayacağı kadar zor bir iştir. Shor algoritması ise 1, 2, 3… diye düz saymak yerine döngüsel sayım kullanır. Böylece sonsuza dek saysak bile sayı dizisinin hep tekrarlanan periyotları olacaktır. Bu da pi sayısının tam tersidir. Pi sayısının ondalık basamakları asla tekrarlanmaz.

Oysa şifrelemek için kullandığımız sayıların basamakları tekrarlanır. Bunun nedeni bu devasa sayıların asal çarpanlardan türetilmesidir. Shor algoritması da döngüsel sayımda ortaya çıkan periyodu kısayol olarak kullanır. Böylece en büyük sayıları bile kısa sürede asal çarpanlara ayırmaya imkan tanır. Şimdi gelelim kuantum bilgisayarlara… Kuantum kriptografi Shor algoritmasını şifre kırmakta nasıl kullanıyor?

Öncelikle kuantum bilgisayarlarla ilgili yanlış anlaşılan bir konu var. O da kuantum bilgisayarları paralel çalışan çok sayıda klasik bilgisayara benzetmektir. Oysa kuantum bilgisayarlar çok çekirdekli işlemcilerden farklıdır. Bunun nedeni de kuantum parayla yazı tura atmanın klasik parayla yazı tura atmaktan farklı olmasıdır. Klasik parada ya yazı ya tura gelir. Bunun olasılıkları da yüzde 50’dir. Kuantum parada ise diyelim üç seçenek var. Bunların gerçekleşme olasılığı ise yüzde 33 ile birbirine eşit değildir. Bunun yerine 1/3, 1/6 ve ½ gibi farklı olasılıklardır (Bkz. Bell eşitsizliği ve belirsizlik ilkesi).

Süperpozisyon

Bu yüzden Shor algoritması kuantum bilgisayarların şifreleri daha hızlı kırmasında tek başına işe yaramaz. Bunun için kuantum bilgisayarların asıl gücünü olan süperpozisyon özelliğini kullanmak gerekir. Peki süperpozisyonun Shor algoritmasını klasik bilgisayarlarda çalıştırmaktaki farkı nedir?

İlgili yazı: Kodlama İçin En Gerekli 16 Programlama Dili

 

Shor algoritması ve süperpozisyon

Klasik bilgisayarların N sayısını asal çarpanlara ayırmakta kullandığı yöntem nedir? Bu, sayıları kendinden küçük sayılara bölerek içlerinden hangisinin asal çarpan olduğuna tek tek bakmaktır. N büyük bir sayıysa bu çok uzun sürer. Öte yandan kuantum bilgisayarlar paralel çalışan klasik bilgisayarlar gibi olsa kübitlerden biri örneğin 6’yı 2’ye bölerken diğeri 3’e bölerdi. Böylece işlemi tek adımda tamamlardı. Kısacası sayıları asal çarpanlarına ayırmak için gereken bölme işlemini bir işlemcinin çekirdek sayısına bölerek kolaylaştırırdık.

Oysa çok çekirdekli klasik bilgisayarlar bunu zaten yapıyor ama yeterli olmuyor. 512 veya 4096 basamaklı bir sayıyı asal çarpanlarına ayırmak yine çok uzun sürüyor. Diğer yandan 50 kübitlik bir kuantum bilgisayar 50 kübitin birbiriyle dolanık ve süperpozisyon halinde olmasıyla çalışır. Örneğin 4096 basamaklı bir sayıyı tek tek sayılara bölerek elde edeceğiniz bütün sayıları (bütün temel işlem sonuçlarını) süperpozisyon halinde içerir.

Dolayısıyla süperpozisyon bu bölenlerin hangi ikisinin asal çarpanlar olacağına dair olasılıkları verir.  Çok çekirdekli bir işlemciyle süperpozisyon arasındaki fark işte budur. Çok çekirdekli bir işlemci her bölme işleminin sonucunu ayrı bir çekirdekte işler ve içerir. Kuantum bilgisayarı ölçtüğünüzde ise durum farklıdır. Ona sorduğunuz “bu asal sayının çarpanları nedir?” sorusunun yanıtını aldığınız durumlarda, bilgisayar size her seferinde bir asal çarpan verir.

Shor algoritmasının sınırları

Sonuç olarak süperpozisyon bütün sonuçları tıpkı bir tombala torbasındaki fişler gibi içermez. Bunun yerine hangi sayıların asal çarpan olacağının olasılık dağılımını verir.  Öyle ki Shor algoritmasını kuantum bilgisayarda çalıştırsanız da bir şey değişmez. Asal çarpanlara dair bütün olasılıkları tek tek denemek ve içlerinden hangisi doğru diye tek tek sonuçlara bakmak zorunda kalırsınız. Bu da şifre kırma işini hızlandırmaz. Öyleyse şifreleri kuantum bilgisayarla nasıl kıracağız?

İlgili yazı: Gerçek Adem: ilk insan ne zaman yaşadı?

 

Shor algoritması ve dalga fonksiyonu

Yukarıdaki çok basit bir hata yaptık. Kuantum bilgisayarları klasik bilgisayarlar gibi çalıştırdık. O zaman da şifreleri daha hızlı kıramadılar. Bu kez sadece kuantum bilgisayarlarda daha hızlı çalışan bir algoritma kullanacağız. Shor algoritmasını Fourier dönüşümüyle kuantum algoritmaya dönüştüreceğiz. O zaman süperpozisyon en büyük sayıları bile hızlıca asal çarpanlarına ayıracak. Bu bağlamda süperpozisyon, bir sayıyı asal çarpanlarına ayırmak gibi bir kuantum sisteminin bütün sonuçlarını yalnızca olasılık dağılımı olarak içeren bir durumdur.

Demek ki asal çarpanları bulma olasılığı ile diğer sonsuz sayıdaki yanlış sonucu elde etme olasılıklarını birbirine bağlayan fiziksel bir altyapı var. O altyapı da bütün olası sonuçları içeren Schrödinger olasılık dalga fonksiyonu denklemidir. Süperpozisyon bu denklemin fiziksel görünümüdür. Olasılık dalga fonksiyonunun fiziksel olup olmadığı kuantum fiziğinde büyük tartışma konusudur. Oysa nesnel gerçeklik yazısında bulanık, yani hangi olasılığın gerçekleşeceği belli olmayan süperpozisyon halinin fiziksel olduğunu gördük. Bu da bize şifre kırmak için güzel bir fırsat veriyor:

Olasılık dalgası nihayet bir dalgadır. Eğer dalganın genliğiyle oynarsak ve dalganın doğru tepeleriyle çukurlarını üst üste bindirirsek ne olur? O zaman tepeler tepelerle ve çukurlar çukurlarla örtüşür. Böylece dalga yapıcı girişim yaparak kendini güçlendirir. Bu da kuantum bilgisayarın bir sayının asal çarpanlarını bulma olasılığını artırır. Böylece trilyonlarca deneme yerine birkaç bin veya birkaç düzine denemeyle doğru sonucu buluruz. Peki bunu nasıl yaparız?

İlgili yazı: Dünyadaki En Ölümcül 5 Toksin Nedir?

 

 

Shor algoritması ve sayılar teorisi

Bunun için sayılar teorisinden yararlanıyoruz. Belirli bir sayının asal çarpanlarını bulma problemini, bu asal sayıları içeren periyodik fonksiyonun periyodunu bulma problemine dönüştürüyoruz. Cümle sizi şaşırtmasın. Geçen yazıda nasıl yaptığımızı gördük. Bunun için kullandığımız 4 adımı resimde görebilirsiniz. Kuantum bilgisayarda yapmamız gereken ilk işlemse asal çarpanları bulmak yaptığımız a^r mod N işlemlerini almak ve bunların da periyodunu bulmaktır.

Resimde a^r mod N işleminin asal çarpanlardan birini gösterecek r periyodunu bulmanın (2. Adım) çok uzun sürdüğünü söylemiştim. Öyle ki farklı r değerleri için çok sayıda a^r mod N işlemi yapmak gerekiyor. Kuantum bilgisayarlar da doğru–yanlış bütün işlem sonuçlarını süperpozisyonda olasılık dağılımı olarak gösteriyor. Öyleyse asal çarpanları gösteren doğru a^r mod N işlemlerini bulmak için bütün bu a² mod N, a³ mod N, a⁴ mod N… aⁿ mod N periyodik sayı dizisinin genel periyodunu bulmak gerekiyor (n).

Unutmayın

Her bir olasılık doğru ya da yanlış herhangi bir periyodu içerir. Tüm periyodik sayıların genel periyodu ise sadece doğru sonuçları içerecektir. Marifet kuantum bilgisayar olasılık dalgasını doğru sonuçları verecek şekilde güçlendirmektir. Tabii bu sırada yanlış sonuçların olasılıkları da azalacaktır. Neden marifet dediğime gelince: Periyotların periyodunu alma işlemi de çok uzun sürer. Bu kez de sayılar yerine periyotları tek tek denemek gerekir. Doğru sonucu bulma olasılığını Fourier dönüşümü artırır. Bu dönüşüm de karmaşık analiz yöntemini kullanır ki adı üstünde çok karmaşıktır. Bu yüzden Fourier dönüşümünü tıpkı döngüsel sayımda yaptığımız gibi daireler çizerek basitçe göstereceğim:

İlgili yazı: Düz Dünya Teorisini Çürüten 12 Kanıt

 

Shor algoritması ve şifre kırma

Önce bir sürü daire çizelim. Sonra a² mod N, a³ mod N, a⁴ mod N… aⁿ mod N dizisinin genel periyodunu bulmak için bu dairelerin üzerine 2, 3, 4… n sayıda nokta çizelim. Yalnız noktalardan birini daireyi yatay olarak ikiye bölmekte kullanacağınız yatay çizginin çemberle kesiştiği noktalardan birine koyalım. Diğer noktaları da saatin ters yönde bu noktadan itibaren eşit aralıklarla yerleştirelim. Her nokta dizideki bir periyoda (r) karşılık geliyor. Nokta sayısı da dizinin bulmak istediğimiz tahmini genel periyod oluyor.

Bu arada noktalar 1’in karmaşık sayılı kökleridir. Neyse, şimdi şekildeki gibi ilk noktadan, sıfır noktasından başlıyoruz ve bunu gösteren bir yelkovan çiziyoruz (mavi çubuk). Sonra mavi yelkovanı her tekil periyot için 2, 3, 4… kez saatin ters yönünde çeviriyoruz. Her çevirmede yelkovanın gösterdiği yönü resimdeki gibi dairenin aşağısına çiziyoruz. 3 nokta için üçgen, 4 nokta için kare ve benzeri üretiyoruz. Peki bu oyun periyotların periyodunu ve dolayısıyla asal çarpanları bulmakta ne işe yarıyor?

Örneğin

2^r mod 7 dizisini yazalım. 2⁷ mod 7, 2⁸ mod 7, 2⁹ mod 7… gibi. Sonra bunların periyodlarını bulalım 2, 4, 1; 2, 4, 1 gibi… Sonra dairenin üzerine genel periyot tahminlerimiz için 2, 3, 4 nokta çiziyoruz. 2^r için de yelkovanı saatin ters yönünde 2, 3, 4… kez ters çeviriyoruz. Bu örnekte dairedeki nokta sayısı ne olursa olsun 1 sayısını dikkate alıyoruz. Yelkovanın biri bulana kadar her bir r periyodu için gösterdiği yönleri çiziyoruz. Öyleyse kuantum bilgisayarla şifre kırmakta son adıma geçebiliriz:

İlgili yazı: Kara Delik Termodinamiği Nedir ve Nasıl Çalışır?

 

Shor algoritması için sonsöz

Yine bu örnekte 3 noktalı dairede yelkovan 1 yönü için hep tam sağı gösteriyor. Oysa 3 yerine 4 noktalı dairelerde, 1 periyodunu her bulduğumuzda, yelkovanın dairede tam tur atıp başladığı yere geri döndüğünü görüyoruz. 4 nokta için bütün periyotlarda bu böyle ve bu da 2^r mod 7 dizisinin genel periyodunun 4 olduğunu gösteriyor. İşte kuantum bilgisayarlarda 2^r mod x için Shor algoritmasına Fourier dönüşümünü her uyguladığımızda dairedeki doğru nokta sayısını, genel periyodu buluyoruz (resme bakın).

Doğru nokta sayısını bulmak da olasılık dalga fonksiyonunda bir sayının asal çarpanlarını bulma olasılığını artırıyor. Bunun için genel periyodu bir kez bulmak yeterli olduğundan kuantum bilgisayarlar nihayet kısa sürede zor şifreleri kırmayı başarıyor. Doğru nokta sayısını bulmanın asal çarpanları bulmaktan çok daha kolay bir işlem olduğunu belirtelim.

İşte bu kadar! Kuantum bilgisayarların bugün internette kullanılan ama kuantuma dayanıklı olmayan şifreleri nasıl kıracağını gördük. Tabii bugünkü kuantum bilgisayarlar bunu yapacak kadar güçlü değil. O kadar çok sayıda dolanık kübit içermiyor. Oysa gelecekte Shor algoritmasına Fourier dönüşümünü uygulayarak büyük sayıları asal çarpanlarına hızla ayırmak mümkün olacak.

Siz de Gödel eksiklik teoremine şimdi bakabilir ve Newton’ın pi sayısını nasıl hesapladığını görebilirsiniz. Kara deliklerin merkezindeki tekilliği sorgulayarak kuantum fiziğinde karmaşık sayıların şart olup olmadığını merak edebilirsiniz. Sonsuzluk gerçek mi yoksa matematik kurgusu mu ve matematik evrensel dil mi sorularını da araştırabilirsiniz. Sanal parçacıkların gerçek mi, yoksa matematiksel mi olduğuna bakabilirsiniz. Hızınızı alamayıp sihirli kareler ve matematikte çözüm bekleyen 4 probleme de bakabilirsiniz. Bilimle ve sağlıcakla kalın. 😊

Kuantum bilgisayarlar şifreleri nasıl kırıyor?

¹Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
²Realization of a scalable Shor algorithm
³Revisiting Shor’s quantum algorithm for computing general discrete logarithms
⁴Factoring with Qutrits: Shor’s Algorithm on Ternary and Metaplectic Quantum Architectures