1991’de, Bedford, Massachusetts’teki siber güvenlik şirketi RSA Laboratories, iki asal sayıyı çarparak oluşturduğu, giderek artan 54 sayının bir listesini yayınladı. Daha sonra, bilgisayar bilimi topluluğuna bunları çarpanlara ayırmaları ve her durumda orijinal asal sayıları bulmaları için meydan okudu. Şirket, bazı çözümler için nakit ödüller bile teklif etti.
Bu zorluk, sayıları faktoringe ayırma konusunda son teknoloji yetenekleri değerlendirmek için tasarlandı. Bu önemlidir, çünkü faktoring – veya daha doğrusu zorluğu – çeşitli açık anahtar şifreleme sistemlerini güvence altına alır. Dolayısıyla, gelişmiş faktoring yetenekleri, bu şifreleme sistemlerini daha az güvenli hale getirir.
Meydan okuma 2007’de sona erdi ancak bugün bile bunlardan 31’i RSA numaraları faktörsüz kalır. En büyüğü RSA-2048’dir ve onu temsil etmek için gereken bit sayısı nedeniyle bu ad verilmiştir.
Faktoring sayılarındaki ilerlemenin durmuş olması gerektiğini düşünmek kolay olurdu. Ancak perde arkasında, faktoringde geleneksel makinelerden çok daha iyi olan, giderek daha yetenekli kuantum bilgisayarları şeklinde bir devrim yaşanıyor.
Şu an için bu makineler, en güçlü geleneksel bilgisayarlardan daha iyi performans gösterecek kadar güçlü değil. Ve bu ne zaman olacakları sorusunu gündeme getiriyor.
kuantum algoritması
Bugün, Çin’deki Matematik Mühendisliği ve İleri Hesaplama Devlet Anahtar Laboratuvarı’ndaki Bao Yan’ın ve sayıları çarpanlarına ayırabilen kuantum algoritmalarının gücünü önemli ölçüde artırmanın bir yolunu geliştiren meslektaşlarının çalışmaları sayesinde bir yanıt alıyoruz.
Bir kuantum bilgisayar tarafından şimdiye kadar çarpanlarına ayrılan en büyük sayının boyutunu artırmak için yaklaşımlarını kullanıyorlar. Ve çalışmalarının, kuantum bilgisayarların RSA-2048 gibi “kriptografik öneme sahip” kodları kırabilmelerinin yolunu açtığını söylüyorlar.
Açık anahtarlı şifreleme sistemlerinin güvenliği, çarpma işleminin tersi olan matematiksel faktoring işlemine bağlıdır. Çarpma ve çarpanlara ayırmanın ilginç özelliği, birbiriyle yakından ilişkili olmalarına rağmen gerçekleştirilmesinin çok farklı olmasıdır.
Daha büyük bir sayı elde etmek için iki asal sayıyı çarpmak kolaydır. Ancak daha büyük sayıdan başlayıp hangi asal sayıların çarpan olduğunu bulmak zordur. Aslında, zorluk sayının boyutuyla birlikte üstel olarak artar ve klasik bir bilgisayarın çarpanlarını bulmak için evrenin ömrüne ihtiyaç duyacağı kadar büyük bir sayı yapmak basittir.
Açık anahtar şifreleme sistemlerini bu kadar güvenli yapan da budur – mükemmel değillerdir, ancak geleneksel bir bilgisayarın onları kırması için evrenin ömrü boyunca ihtiyacı olacaktır.
Bu düşünce, 1994 yılında Amerikalı matematikçi Peter Shor’un sayıları geleneksel bir algoritmadan çok daha hızlı çarpanlara ayırabilen bir kuantum algoritması bulmasıyla değişti. Shor’un çalışması, bir anda, herhangi bir açık anahtarlı şifreleme sisteminin gelecekte bir kuantum bilgisayar tarafından kırılabileceği ihtimalini gündeme getirdi.
Shor’un algoritmasının vaadi, kuantum bilgisayarların geliştirilmesinde önemli bir itici güç olmuştur. Ancak, mevcut olanlardan önemli ölçüde daha güçlü kuantum bilgisayarları gerektirdiğinden, uygulamanın zor olduğu ortaya çıktı.
Shor’un algoritmasını kullanan bir kuantum bilgisayar tarafından çarpanlarına ayrılan en büyük sayı yalnızca 21’dir. Diğer yaklaşımlar daha başarılı olmuştur, ancak hiçbir yerde RSA sayılarını ele alacak kadar güçlü değildir. Bao ve arkadaşları, “Gerçek bir fiziksel sistemde genel bir yöntemle çarpanlarına ayrılan en büyük tamsayı 249919’dur” diyor.
Bu, 18 bit olarak tanımlanabilen bir sayıdır. Bununla birlikte, modern açık anahtar şifreleme sistemleri, 2048 bit veya daha fazla olarak tanımlanabilecek önemli ölçüde daha büyük sayılara bağlıdır. Bu kripto sistemlerinin bu tür saldırılara karşı güvenli görünmesinin nedeni budur, ancak önemli bir soru, kuantum bilgisayarların bunlarla da başa çıkabilmesinin ne kadar süreceğidir.
Kuantum-Klasik Hibrit
Bao ve ortaklarının yaptığı atılım, Shor’un algoritmasına alternatif bir yaklaşımı hızlandırmak oldu, adı Schnorr’un algoritması (sic). Bu, her birinin çözülmesi zaman alan birkaç adımdan oluşan klasik bir algoritmadır.
Bao ve co’nun yaklaşımı, en çok zaman alan adımı hızlandırmak için bir kuantum optimizasyon algoritması kullanmaktır. Bu kuantum-klasik hibrit yaklaşım, faktoring sürecini önemli ölçüde hızlandırma etkisine sahiptir, ancak Shor’un algoritması için gerekli olandan daha az güçlü bir kuantum bilgisayarla.
Sonuçlar etkileyici. Bao ve ortakları, yaklaşımlarını yalnızca on kübitlik bir süper iletken kuantum bilgisayarı kullanarak 48 bitlik 261980999226229 sayısını çarpanlarına ayırmak için kullandılar. Bao ve arkadaşları, bunun “gerçek bir kuantum cihazında genel bir yöntemle çarpanlarına ayrılan en büyük tamsayı” olduğunu söylüyor.
Bütün bunlar, daha büyük sayıları bile çarpanlara ayırma olasılığının iyi olduğu anlamına gelir. Bao ve arkadaşları, yaklaşımlarının 372 kübitlik bir kuantum bilgisayar kullanarak RSA-2048’i etkileyebileceğini hesaplıyor.
“Böyle bir kuantum kaynakları ölçeğinin yakın gelecekte elde edilmesi büyük olasılıkla” diyorlar. Gerçekten de, IBM kısa süre önce açıkladı 433 kübitlik bir kuantum bilgisayar.
Ancak önemli bir uyarı var. Bir kuantum bilgisayarın kapasitesini belirleyen sadece kübitlerin sayısı değil, aynı zamanda hata oranıdır ve şu anda kuantum bilgisayarlar, daha büyük hesaplamaları karlı hale getirmek için çok fazla hataya eğilimlidir.
Bununla birlikte, Bao ve ortaklarının çalışması, RSA sayılarının yakın gelecekte on iğne gibi düşeceğini öne süren ilginç bir çalışmadır. 30 yıldan fazla zaman geçti, ancak RSA Faktoring Sorunu nihayet çözülmeye yakın olabilir.
Hala yaygın olarak kullanılan açık anahtarlı şifreleme sistemlerinin güvenliği açısından çıkarımlar açıktır. Shor’un duyurusundan bu yana, kriptografların mesaj göndermenin daha güvenli yollarını bulmak için bolca zamanı oldu. Başarılı olup olmadıkları kısa süre sonra ortaya çıkarılmalıdır.
Ref: Süper iletken bir kuantum işlemcide alt doğrusal kaynaklarla tamsayıları çarpanlara ayırma: arxiv.org/abs/2212.12372
Kaynak : https://www.discovermagazine.com/technology/a-30-year-old-cryptographic-challenge-is-about-to-be-solved