SRVB Şifreleme Sistemine Başlarken

Tanıtım

Bilgi güvenliği, teorik bilgisayar bilimlerinden yazılım mühendisliğine kadar her şeyi içerebilen ve hatta insan hatası psikolojisini gözlemleyebilen büyüleyici bir bilgi alanıdır.

Kriptografi artık günlük hayatımızın birçok anonim teknolojik kahramanından biridir. Sosyal ağlar, web bankacılığı, askeri istihbarat ve hassas bilgilerle ilgilenen diğer bilgi sistemlerinin tümü büyük ölçüde kriptografiye dayanır. Kriptografi, bazılarının 12. insan hakkı olarak gördüğü mahremiyete sahip olmamızı sağlar.

Bu makale size açık anahtarlı şifreleme sistemlerinin arkasındaki ilkelere bir giriş yapacak ve sizi makalenin yazarı ve Prof. Daniel Santana Rocha tarafından geliştirilen bir şifreleme sistemi olan Santana Rocha-Villas Boas (SRVB) ile tanıştıracaktır. Yazma sırasında, algoritma yazarları, kodu kırmayı başaran herkese mali bir ödül içeren bir kampanya hazırlıyorlar. Makale algoritma işlevselliğini ayrıntılı olarak ele alacağından, ödül arayışına başlamak için en iyi yer burasıdır. Daha fazla bilgi SRVB sitesinde mevcuttur.

Kriptosistem Nedir?

Kriptografi, genellikle "anahtar" olarak adlandırılan belirli bir talimat sağlandığı sürece, bir mesajın yorumlanabilirliğini engellemeye ve yine de onu uygun bir şekilde yorumlamaya izin veren herhangi bir yöntemdir. Bu, en eski teknikleri bile kapsayan çok geniş bir tanım olsa da, bunun bilgi güvenliği ile ilgili her şeyi kapsamadığını belirtmekte fayda var.

Şifreleme yöntemleri ve bunları kırma yolları arasındaki teknolojik yarışın hiçbir zaman kesin bir kazananı olmaması bekleniyor. Her yeni neslin, şifrelenmiş mesajları sistematik olarak deşifre etme/kırma, yani güvenlik veya şifrelemeyi atlama teknikleri seti olan bilgi güvenliği ve kriptanaliz standartlarını yükseltmesi bekleniyor.

Bir kriptosistemin (belirli bir kriptografi tekniği) kullanıcıları tarafından güvenli kabul edilebilmesi için, Kerckhoffs ilkesi olarak bilinen uluslararası uzmanlar topluluğunun onayını alması ve dolayısıyla kamuoyu tarafından bilinmesi gerekir. Yine de bu durum, sistemi, şifrelemeleri sistematik olarak kırmanın yollarını bulmaya çalışacak olan dünyanın kriptanaliz topluluğunun incelemesine maruz bırakır.

Belirli bir şifreleme sürecini, yalnızca amaçlanan aracıların şifresini çözebileceği kadar gizli ve aynı zamanda dünyadaki kriptanaliz topluluğunun sağlamlığını onaylayabileceği kadar herkese açık hale nasıl getirebiliriz? Cevap, Kriptolojinin temel bir unsuru olan bir bileşendir: anahtar. Bir şifreleme sisteminin anahtarı, şifreleme veya şifre çözme algoritmaları veya her ikisi için bir parametredir. Algoritma ailesi yerine parametreleri gizli tutarak, her iki çelişkili gereksinime de ulaşılabilir. Parametre ailesinin yeterince büyük (muhtemelen sonsuz) olması ve bileşenlerinin her birinin yeterli özelliklere sahip olduğu kanıtlanabilmesi koşuluyla, saldırganların parametreleri yalnızca inceleme yoluyla belirlemesi mümkün olmayacaktır.

Son olarak, bir anahtarın etkili bir şekilde çalışması için, kolayca üretilebilir, ancak tahmin edilmesi neredeyse imkansız olmalıdır. Günümüz bilgisayarlarının hesaplama gücüyle, bir bilgisayarın insan tarafından oluşturulan bir anahtarı deşifre etmek için herhangi bir insanın hayal etmesi gerekenden daha az zamana ihtiyacı olacaktır, üstelik bu şekilde anahtar üretmenin zaten uygun maliyetli olmadığı gerçeğine ek olarak. Bu nedenle, anahtarlar bir algoritma tarafından oluşturulma eğilimindedir.

Bir anahtar üreten algoritma, tipik kullanımın bir sonucu olarak öngörülebilir/tekrarlanabilir çıktı oluşturmamalıdır. Algoritmalar, herhangi bir akıllı süreç olmaksızın prosedürleri yerine getirdiğinden, soru bunun nasıl yapılabileceği haline gelir. Cevap, anahtar üreten algoritmaları, büyük miktarda gerçekten rastgele bitleri anahtarlara dönüştüren haritalara dönüştürmektir. Gerçekten rastgele bitler, onları evrendeki belirsizlikten üreten işletim sisteminden elde edilebilir. Bazı kaynaklar, uygulamaya bağlı olarak fare hareketiniz, ağ paketi gecikmeleriniz ve hatta özel donanımınız olabilir.

Açık Anahtarlı Şifreleme Sistemleri

Bir kez daha şaşırmaya hazırlanın, çünkü şimdi az önce söylediklerimizle görünüşte çelişen bir kavramı tanıtacağız: açık anahtar.

Şimdiye kadar, gizli parametreler (anahtarlar) güvenli bir şekilde değiştirildikten sonra güvenli iletişimin oluşturulduğunu gördük, ancak parametrelerin genel bir kanal üzerinden değiş tokuş edilmesi sorunu devam ediyor. Şu anda, biraz daha elle tutulur bir sorunu çözen bir konsept sunacağız: güvenli bir kanalın oluşturulması.

Alice'in Bob ile çalıştığını ve iş etkileşimlerini şifreleme kullanarak güvende tutmak istediklerini varsayalım. Anahtarları üzerlerinde olan bir USB flash sürücü birbirlerine vererek buluşup şifreleme anahtarlarını değiştirebilirler. Ama ya Alice ve Bob farklı kıtalarda bulunuyorsa. Hiçbirinin olmadığı yerde güvenli bir kanal nasıl kurulur?

Anahtarları e-posta yoluyla göndermek bir seçenek olmayacaktır, çünkü rakipleri Eve değişimi durdurabilir ve daha sonra tüm şifrelenmiş verileri okumak için anahtarlarını kullanabilir. Bu hassas verileri iletebilecekleri başka bir dijital kanalları olsaydı, ilk etapta şifrelemeye ve dolayısıyla anahtarlara ihtiyaç duymazlardı. Anahtarın fiziksel posta yoluyla gönderilmesi de ele geçirilebilir, çünkü başlangıçta hassas bilgilerin değiş tokuşunu gerektirir. Başka verilerin içinde saklanarak bir steganografik anahtar göndermek akıllıca olacaktır, ancak gönderen, alıcının ve yalnızca alıcının böyle bir mesajın varlığından haberdar olduğundan ve nasıl çıkarılacağını bildiğinden emin olmadıkça işe yaramaz. Olduğu gibi, bir mesajın varlığının farkındalığı ile birlikte anahtarın verilerden nasıl çıkarılacağına dair açıklama, başlı başına bir anahtar türüdür ve bu da bizi ilk kareye geri getirir.

Çözüm, şifreleme parametresinin orijinal mesajı ^[1] makul bir şekilde yorumlamak için yeterli olmadığı bir şifreleme sistemi tasarlamak ve mesajın yorumlanmasına izin verecek parametreyi kendinize saklamaktır. Bu parametreye özel anahtar diyoruz. Özel anahtara dayalı olarak, bu yeni parametrelerin kendilerinin özel anahtarın ne olduğunu ortaya çıkarmasını sağlamadan bir şifreleme aracı için bir dizi parametre üretilebilir. Bu parametre seti herkese açık olarak paylaşılabilir, çünkü sadece bir kişinin şifresini çözebildiği sürece, bir şeyi kimin şifreleyebileceği o kadar önemli değildir. Şifreleme aracı için bu parametre seti herkese açık hale getirilebildiğinden, buna ortak anahtar denir.

Şifreleme ve şifre çözme anahtarlarının farklı olduğu ve birincisinin ikincisini çıkarmak için uygun bir şekilde kullanılamadığı kriptografiye asimetrik kriptografi denirken, simetrik kriptografi, bu anahtarlar aynı olduğunda veya birbirinden kolayca çıkarıldığında sahip olduğumuz şeydir.

Alice, Bob'a yalnızca şifresini çözebileceği şeyleri şifrelemek için kullanılabilecek ortak anahtarını gönderir (özel olarak tuttuğu özel anahtarıyla) ve tersine Bob, Alice'e yalnızca şeyleri şifrelemek için kullanılabilecek ortak anahtarını gönderir. tek başına şifresini çözebileceğini (özel olarak da sakladığı özel anahtarı aracılığıyla). Ancak, bir şifreleme algoritması için, tam ters algoritmayı çıkaramayan bir parametre nasıl yayınlanabilir?

Cevap, programlamaya en yakın olan matematik alanında, hesaplama karmaşıklığı teorisinde yatmaktadır. Matematik problemlerini yeterince derinlemesine inceleyen herkes, bir şekilde yapılması kolay, ancak tersini yapmak zor olan dönüşümleri duymuştur. Örneğin, matematikte, bir ders kitabı türevi bulmak tipik olarak basit bir alıştırma iken, tersini yapmak (örneğin, önemsiz olmayan herhangi bir integrali veya ders kitabı fiziksel ODE veya PDE'sini çözmek gibi), ilk önce fonksiyon ailelerini hipotezlemek için daha araştırmacı bir süreç gerektirir. çözüm(ler)i içermesi ve bu ailelerden çözümler bulmak için ters problemleri çözmesi garanti edilir (veya en azından makul).

RSA şifreleme sisteminde fiilen kullanılan bir örnek, büyük asal sayıları çarpmaya karşı, faktörleri bilmeden elde edilen ürünü çarpanlara ayırmadır. Çarpma yapmak önemsizdir, ancak çarpanlara ayırma, yüzlerce basamaklı asal çarpanları rastgele ^[2] tahmin etmenizi gerektirir. Operasyonun önemli bir özelliği, iyi ölçeklenmesi ihtiyacıdır. RSA'daki asal sayıların boyutuna birkaç basamak eklemek, şifreleme işlemine karmaşıklıkta küçük bir artış eklerken, kırılması için binlerce kat daha fazla işlem gerektiren bir anahtarın ortaya çıkmasına neden olacaktır. Çok kabaca konuşursak, asal sayıların çarpımı şifreleme için kullanılırken asal çarpan çifti şifre çözme için kullanılır.

Tüm bunları göz önünde bulundurarak, SRVB şifreleme sisteminin nasıl çalıştığına bir göz atalım.

Temel Algoritma - SRVB'ye Bakmak

Altküme Toplamı Problemi

Diğer herhangi bir açık anahtarlı şifreleme sistemi gibi, SRVB de üretilmesi kolay olan belirli bir sorunu çözmenin zorluğuna dayanır. SRVB'nin durumunda, aşağıdaki gibi tanımlanabilecek olan alt küme toplamı problemidir:

$w$ ve $v_1 tamsayıları verildiğinde, \cdot \cdot \cdot, v_N \in Z$ $b_1, \cdot \cdot \cdot, b_N \in {0,1}$ dizisini bulun, öyle ki $ \sum_ {i = 1}^{N} v_i b_i = w $.

Açıkçası, bu problem rastgele N tamsayı seçilerek, bunların bir alt kümesini rastgele seçerek ve bu alt kümeyi toplayarak üretilebilir - ki bu önemsizdir.

Bir kaba kuvvet araması $ O( N * 2^N ) $ karmaşıklığına sahip olur ve $b$s değerlerinin her bir kombinasyonunu hesaplar. 1972'de Horowitz ve Sahni tarafından $ O ( N * 2 ^ {N / 2} ) $ karmaşıklığı ile daha verimli bir yaklaşım verildi. $b$s ve $w$'ı $k$-boyutlu tamsayı vektörleriyle değiştirirsek, problem en azından o kadar zor olur. Bununla birlikte, bu daha zor problemin tutulacağı bölge, aşağıda göreceğimiz gibi, aynı problemin daha kolay bir versiyonunun yer aldığı halkalı bir izomorfizme de sahip olmalıdır. Bu nedenle, SRVB $ k = 2 $ olan Gauss tamsayıları içindeki alt küme toplamı probleminden yararlanır.

Bu sorunun açgözlü bir algoritma kullanılarak hesaplanmasının kolaylaştığı özel bir durum vardır. Bir dizi ölçekleme faktörü $ v_1, \cdot \cdot \cdot, v_N $ sıralarsak, burada dizideki her tam sayı, kendisinden önce gelen tüm tam sayıların toplamından daha büyüktür ($ \forall i , \sum_{j= 1}^{i-1} v_j < v_i $), doğrusal zamanda b dizisini bulmak için açgözlü bir yaklaşım kullanılabilir. Tanımlanan özelliklere sahip bir diziye süper artan dizi denir.

İşte bu durum için açgözlü çözümün basit bir açıklaması:

1. Şu anda gözlemlenen faktör olan $ i = N $ ile başlayın ve $w' = w $, $w$'ın kalanı

2. Geçerli ölçeklendirme faktörü, $w$'dan geriye kalanlara sığmayacak kadar büyükse, yani $v_i > w'$ ise, $b_i = 0$ olarak ayarlayın ve bir sonraki adıma geçin. Aksi takdirde, ölçekleme faktörünün sırayla olması gerektiğini biliyoruz (geri kalan faktörler $v_i$'dan daha küçük olduğundan) ve $b_i = 1$ olarak ayarladık.

3. $ w' \Sol w' - v_i * b_i$, $i \Sol i - 1$. $i > 0$ ise 2. adıma dönün.

4. Şimdi, $w' == 0$ olduğunu doğrulayın, aksi takdirde sorun bozulmuştur

Bu işe yarar, çünkü şu anda gözlemlenenden daha küçük olan tüm çarpanların, (alt)toplam $w' $'ın çoğunu mevcut çarpanın kapsayabileceği kadar toplu olarak kapsayamayacağını biliyoruz. Bu nedenle, kalan toplam mevcut faktörden daha büyükse, mevcut faktörün yardımı olmadan aşağıdaki tüm faktörlerin birlikte toplamda başarısız olacağını kesin olarak biliyoruz. Öte yandan, tüm çarpanlar pozitif olduğundan, eğer mevcut $ v_i $ çarpanı, kalan $ w' $ toplamından daha büyükse, herhangi bir başka çarpan eklemek, sonucun $ w' $'ı daha da fazla aşmasına neden olacaktır.

Makalenin geri kalanı için bir notasyon oluşturalım. $ v_1, \cdot \cdot \cdot, v_n $ ve $w$'ı süper artan dizinin çarpanları ve toplamı olarak seçiyoruz, $ u_1, \cdot \cdot \cdot, u_n $ ve $y$ ise halka açık olacak $ b_1, \cdot \cdot \cdot, b_n $ kurtarmak için sağlanan mevcut parametreler.

$ u_1, \cdot \cdot \cdot, u_n $ dizisi, süper artmayacak şekilde seçilmiş ve $y$ sayısının herkese açık olmasıyla, $ b_1, \cdot \cdot \cdot dizisini kurtarmak için herkese açık olarak yeterli bilgi sağlanmamıştır. , b_n $. Ancak, $ u_1, \cdot \cdot \cdot, u_n $ dizisinin yerini alabilecek bir aşırı artan $ v_1, \cdot \cdot \cdot, v_n $ dizisi varsa, sorunu çözmek için bu dizi kullanılabilir. açgözlü bir yaklaşım.

Aşağıda bunun nasıl çalıştığını göstereceğiz.

Önceki Bir Kriptosistemde Alt Küme Toplamlarının Kullanımı

1978'de Ralph Merkle ve Martin Helman, önceki bölümde açıklanan iki dizi arasındaki bağlantıyı kurmak için bu iki sırt çantası paradigmasını ve modül işleminin doğrusallığını kullanmanın bir yolunu tasarladılar - böylece bir Açık Anahtarlı Kriptosistem tasarladılar. Buradaki fikir, gizli işlenenlerle doğrusal bir işlem (modül) aracılığıyla kolay sırt çantasını (aşırı artan tamsayı vektöründen oluşan) sert olana (bu özellikten yoksun olan) dönüştürmekti. Dönüşüm, her $v_i$'ın bir $\theta$ ile çarpılmasından ve bu ürünün geri kalanının bir $\alpha$ ile alınmasından oluşur, burada $\alpha \gt \sum_{i=1}^N v_i$ ve $\gcd (\alpha, \theta) = 1$ (yakında gerekçelendirilecek iki kısıtlama). Sonuç, $u_1, \ldots, u_N$ dizisi artık aşırı artmıyor ve sert bir sırt çantası olarak kabul edilebilir.

Şifrelemek ve bize bir mesaj göndermek isteyen tarafa $u_1, \ldots, u_N$ dizisinin rastgele bir permütasyonu verilecektir. Permütasyon, üçüncü bir şahsın orijinal aşırı artan dizinin ne olduğunu tahmin etmesi için daha zor bir zaman geçirmesi için yapılır. Bir mesajın bit blokları $b_1, \ldots, b_N$ katsayıları olarak kullanılır. Şifreleme, anahtar dizisini bu katsayı dizisiyle çarparak ve çarpmaları $y$ olarak etiketleyeceğimiz bir sonuca toplayarak yapılır. Yalnızca özel anahtarın sahibi $y$'ı, bu aynı $b_1, \ldots, b_N$ blokları kolay tam sayılarla ($v_1, \ldots dizisi) çarpılmış olsaydı elde edilecek olan karşılık gelen $w$'a dönüştürebilir. , v_N$). Bu, $y$'ı $\theta^{-1}$ ile çarparak yapılır, $\theta$ modülünün $\alpha$ (varlığı $\gcd(\alpha, \ teta) = 1$). Başka bir deyişle, $(\theta * \theta^{-1}) \bmod \alpha = 1$. Bundan sonra, $w = (y * \theta^{-1}) \bmod a$'ı hesaplıyoruz. Bunun garantili olmasının nedeni , modülün doğrusallığıdır , yani, kalanların doğrusal kombinasyonu, doğrusal kombinasyonun kalanına eşittir.

$u$ tanımını, bölüm halkasını ve modül operatörünün doğrusallık özelliğini ardışık olarak uygularsak, yazışmaları görürüz:

$ \begin{align} y & = \sum_{i=1}^N b_iu_i \newline & = \sum_{i=1}^N b_i (v_i * \theta \bmod \alpha) \newline & = \sum_{ i=1}^N b_i * v_i * \theta \bmod \alpha \newline & = \left[ \sum_{i=1}^N b_i * v_i * \theta \right] \bmod \alpha \newline & = \ sol[ \sum_{i=1}^N b_i * v_i \sağ] * \theta \bmod \alpha \newline & = w * \theta \bmod \alpha \end{align} $

Ve böylece kolay toplam $w$, her iki tarafı $\theta^{-1}$ ile çarparak ve modülü $\alpha$ ile alarak elde edilebilir. Bunu yapmak için, özel anahtarın parçaları olarak gizli tutulacak olan $\alpha$ ve $\theta$ ($\theta^{-1}$'ın kolayca hesaplanmasına izin verir) bilinmesi gerekir.

Tek bir kısıtlama, $\alpha \gt \sum_{i=1}^N v_i$, gerekçesiz bırakıldı ve bunun açıklaması şöyle: İkinci ve üçüncü satırlar arasındaki eşitlik, bölümün kalıntı sınıfları arasındaki eşitlikten oluşur tamsayılar modulo $\alpha$ halkası. Diğer bir deyişle, sadece üyelerin eşitliği için yeterli bir koşul olmayan $\alpha$'a bölündüğünde kalan üyelerin eşitliğini belirtir . Sonuç olarak, birden fazla $b$ değeri vektörü tek bir $y$ ile eşlenebilir, bu da olası maksimum toplamın (yani tüm parsellerin toplamı $v_i$) $w_{max}$ ile sınırlandırılmasıyla önlenir. $b$ değerlerinin herhangi bir kombinasyonu için $\alpha$'dan küçük olabilir.

Tıpkı günlük hayatın herhangi bir örneği gibi, tüm hipotezlerin tam bilgisi genellikle imkansızdır ve asla kolay değildir. Sonuç olarak, bir şifreleme sisteminin kullanımının güvenli olup olmadığına karar verirken matematiksel sezgiye güvenmek zorundayız ve bu bize gerçek bir garanti vermez. Yaratılışından altı yıl sonra, MH kriptosistemi A. Shamir'in saldırısıyla kırıldı. MH'yi canlandırmak için birkaç girişim daha yapıldı ve bunların çoğu başarısız oldu.

Santana Rocha - Villas Boas (SRVB) Şifreleme Sistemi

2016'da, bu makalenin yazarıyla bir kriptosistemin farklı esinli ^[3] olasılıkları hakkında birkaç beyin fırtınası yaptıktan sonra, Daniel Santana Rocha, $\theta$ ve $\alpha$'ı Gauss Tamsayılarıyla değiştirme fikrine sahipti. Daha teknik nedenlerle, bu yaklaşım, yukarıda bahsedilen Shamir saldırısına karşı direnişe yol açmaktadır.

Ayrıca, sert bir sırt çantasının daha önce açıklanan doğrusal kombinasyonunun birçok adımından oluşan bir bit bloğu tasarladı. Bunların her birinde, dizinin sonuna, bire eşdeğer, öncekilerin toplamından daha yüksek yeni bir (Gauss) tamsayı eklenirken, şu anda en küçük olan düşürülür.

Şimdi bir Gauss tamsayısı olan $\alpha$ için farklı ve yine de zarif bir şekilde benzer bir kısıtlama geçerlidir. $w_{max} \leq \vert\alpha\vert^2$ gerekiyor. Nedeni formüle etmek çok zor, ama neyse ki zarif bir tanımdan kolayca anlaşılabilir:

Karmaşık sayılar düzleminde, kenarı gerçek ve sanal eksenlere paralel kateti a ve b dik üçgeninin hipotenüsü olan kare bir kafes hayal edin. Böyle bir kafes örneği aşağıda verilmiştir. Guass tamsayıları modulo $\alpha = a + bi$ böyle bir kafes içinde yer alan noktalarla temsil edilebilir. Böyle bir kafes içinde $\vert\alpha\vert^2$ farklı noktalar vardır. Yeterince büyük bir $\alpha$ seçersek, kolay sırt çantasının tüm doğrusal kombinasyonlarını sığdırabiliriz.

Bu, $f : Z/n \rightarrow Z[i]/(\alpha)$ izomorfizminin grafik temsilidir, burada $n = 13$ ve $\alpha = a + bi = 3 + 2i$ ($ n$ ve $\alpha$ gerçekten de $n = \vert \alpha \vert ^ 2 = a^2 + b^2 $'ı gerektiği gibi karşılar). Noktalar Gauss Tamsayılarını temsil eder, yani $a$ ve $b$ tamsayı olmak üzere $a + bi$ karmaşık sayılarını temsil eder. Her zaman olduğu gibi, yatay eksen gerçek kısmı, dikey eksen ise hayali kısmı temsil eder. Bu nedenle, bir noktayı sağa veya sola hareket ettirmek, mevcut değerine sırasıyla +1 veya -1 eklemekle eşdeğerdir. Benzer şekilde, bir noktayı yukarı veya aşağı hareket ettirmek, sırasıyla +i veya -i'nin eklenmesine karşılık gelir.

Kırmızı noktalar, $0 \bmod(\alpha)$'ın eşdeğerleridir. Bunların dışında 4 çift noktayı daha renklendirdik.

$f$ izomorfizmi, $(0,1,2,\cdot\cdot\cdot,10,11,12,0,1,2,\cdot) döngüsel dizisinin $i$th öğesinin dönüşümü ile tanımlanır. \cdot\cdot)$ aşağıdaki kurallara uyan şekildeki aynı zamanda döngüsel nokta dizisinin $i$th elemanına yerleştirin:

1. İlk satırın kırmızı noktasından başlar;
2. Yatay sağ okları takip eder; bunun haricinde
3. Okları takip ederek diziyi kafesin dışına yönlendirirken, siyah olmayan noktalardan birine ulaşacaktır. O noktaya gitmek yerine, aynı karenin içindeki aynı renkli noktaya (yani eşdeğer nokta modulo $\alpha$) atlar; ve sonunda
4. Bu siyah olmayan nokta kırmızı olduğunda (diğer tüm renkler geçtikten sonra gerçekleşir), dizi en üstteki kırmızı noktaya atlar ve böylece döngüyü yeniden başlatır;

En az $Y$ doğal tamsayıları eşlemek için, $\vert\alpha\vert^2$ alanına sahip bir kare alınmalıdır (burada $\vert\alpha\vert = \sqrt{a^2 + b^2} $, Pisagor teoremine göre, en az onun kadar yüksektir.

Her "atlamanın", satırları yukarıdan aşağıya sayarsa $r$ satır numarasını $r \leftarrow (r + b)(mod a + b)$ olarak ve eşdeğer olarak $r \leftarrow (r) olarak değiştirdiğine dikkat edin. + a)(mod a + b)$ aşağıdan yukarıya doğru sayılırsa. Bu nedenle, her satırın (ve noktanın) her döngüde tam olarak bir kez dolaşılması için gerekli ve yeterli koşul, atlamaların boyutunun satır sayısıyla veya başka bir deyişle $gcd(a,a +) ile asal olmasıdır. b) = gcd(b,a + b) = 1$. En büyük ortak bölen operatörünün özelliklerinden dolayı, bunların her ikisi de $gcd(a,b) = 1$'a eşittir.

YS Villas Boas, $a$ ve $b$'ın aynı olması gerektiğini fark etti. Aşırı artışı korumak için, dizinin sonuna eklenen her yeni $w$ tamsayısının, mevcut tüm tamsayıların toplamını geçmesi gerekir ($w > \sum_{i=1}^k v_i$). Bunu başarmak için, $b_i$ çarpma katsayılarının en az 1 olması gerektiğini ve bu nedenle her bitin 0 ve 1 katsayılarıyla eşleştirilemeyeceğini gözlemledi. Katsayılar 0 ve 1 olsaydı, sadece blok sadece birinden oluşan aşırı artışı tatmin eder. Bu nedenle, 0 ve 1 bitleri sırasıyla 1 ve 2 çarpma katsayılarına eşlenmiştir.

Son olarak ve daha az önemsiz: kod çözmenin her adımında, $b_1 v_1 = v_{n+1} - \sum_{i = 2}^{n} denkleminin çözümü olarak yeni bir $v_1$ tamsayısı bulunacak. b_i v_i$, burada tüm $v_i$ ve $b_i$ $1 < i \leq n$ olarak bilinir. $b_1$'ı da bilmediğimiz için elimizde bir denklem ve iki değişkenli bir sistem var ve bu da bize bir serbestlik derecesi bırakıyor. Bunu düzeltmek için, her zaman $b_1$'a atanacak bir pozitif değeri (basitlik adına, 1) tahkim etmemiz ve böylece belirsizliği ortadan kaldırmamız gerekir. Bu nedenle, ilk katsayı 1'e sabitlendiğinden, her adımda $n$ bitlerini kodlamak için tamsayı dizilerimiz $n + 1$ eleman uzunluğunda olmalıdır.

Çözülmesi gereken son bir teknik sorun, mesajın bayt cinsinden boyutunun blok boyutunun katı olmadığı durumdur. Başka bir deyişle, son veri bloğunun olası kalan baytlarıyla ne yapmalı, böylece veri blokları kurtarıldıktan sonra, orijinal içeriğin tüm baytları korunur, ancak onlardan daha fazla değil? Bunu mesajın son baytını bir kez tekrarlayarak çözdük. Bu kopya, daha sonra, her bileşenin yalnızca bir öncekinden farklı olması gereken rastgele bir sıra izler. Bu nedenle, veri blokları alındığında, bunların sonuncusu veya en kötü durumda, sondan önceki olan , baytların son tekrarında kesilir. ^[4]

Şimdi SRVB şifreleme sistemine bir örnek gösterelim.

Parametrelerle başlıyoruz:

$k = 4$;

$m = 4$;

bu, $l = 4 * 4 = 16$'lık bir blok uzunluğu ve çalıştırılan $k + 1 = 5$ doğal tamsayılardan oluşan bir süper artan diziyi verir - yani, lineer olarak birleştirilir, bu lineer kombinasyonun sonucu ile eklenir ve son $k + 1$ öğelerine indirgenir —$m = 4$ kez;

Basitlik adına, $v_i$'ın (aşırı artan) vektörü aşağıdaki olsun:

$(1,2,4,8,16)$

Gerçekten de, 2'nin ilk beş kuvvetinin dizisi, çünkü bu, beş elemanlı ve kesinlikle en küçük olası pozitif değerlere sahip aşırı artan dizidir (böylece, ortak anahtarda karşılık gelen 0'ı önemsiz bir şekilde verecek olan bir 0'dan kaçınılır). ).

Daha önce de söylediğimiz gibi $\alpha = a + bi$ için $a$ ve $b$ tam sayıları asal olmalı ve bahsettiğimiz yeni kısıtlamaya göre $a^2 + b^2 istememiz gerekiyor. = \vert\alpha\vert^2 \geq W$. Hızlı bir hesaplama $W = 1590$ verir. $\sqrt{1590} \simeq 39.8$ olduğundan, seçilecek çok uygun bir $\alpha$ $\alpha = 39 + 40i$ olacaktır, çünkü tamsayılardan oluşan bir halkaya sahip bir izomorfizmi yerleştirmek için yeterince büyüktür. en az 1590 bileşen, aynı zamanda $gcd(a,b)=1$'ı da karşılar. Ayrıca, $gcd(a,\theta)=1$ ^[5] olacak ve tercihen çok düşük olmayacak şekilde bir $\theta$ seçmemiz gerekiyor, böylece $(a_1 * \theta) \% \alpha \neq v_1 * \theta$, (ayrıca bilgi vermekten kaçınmak için). $\theta = 60$ işi yapar, şu sonucu verir:

$-19-1i,1+38i,3-3i,6-6i,12-12i$ ^[6]

O zaman ellerimizi kirletelim. Hello Toptal! . İlk önce onu ASCII'ye ve veri bloklarını kısaltma kuralımıza göre bir bayt dizisine eşliyoruz:

 01001000 01100101 01101100 01101100 01101111 00100000 01010100 01101111 01110000 01110100 01100001 01101100 00100001 00100001

Veri bloğumuz 16 bit = 2 bayt uzunluğunda olduğundan ve mesajımızın 13 karakteri olduğundan, her biri 2 baytlık 7 veri bloğu elde ederiz, burada sonuncusu '!' karakterinin bit temsilinin iki katını içerir. . İlk bloğu adım adım şifreleyelim. Her baytın bitleri önem sırasına göre alındığından dikkatli olun.

$m=01001000 01100101$

• İlk baytın ilk küçük parçası: $(0,0,0,1)\rightarrow(1,1,1,1,2)\cdot(-19-1i,1+38i,3-3i,6-6i,12 -12i)=15+4i$
• İlk baytın ikinci parçası: $(0,0,1,0)\rightarrow(1,1,1,2,1)\cdot(1+38i,3-3i,6-6i,12-12i,15+ 4)=49+9i$
• İkinci baytın ilk parçası: $(0,1,0,0)\rightarrow(1,1,2,1,2)\cdot(3-3i,6-6i,12-12i,15+4i,49+ 9i)=106-10i$
• İkinci baytın ikinci parçası: $(0,1,1,0)\rightarrow(1,1,2,2,1)\cdot(6-6i,12-12i,15+4i,49+9i,106- 10i)=252-2i$

Ve böylece, sadece haritaladık

“O” $\Rightarrow(12-12i,15+4i,49+9i,106-10i,252-2i)$

Şifreli mesajın geri kalanı aşağıdaki gibidir:

“ll” $\Rightarrow(12-12i,21-2i,61-3i,185-31i,367-59i)$

“o “ $\Rightarrow(12-12i,25+33i,65+32i,111+44i,244+124i)$

“Kime” $\Rightarrow(12-12i,9+10i,46+12i,149+5i,277+31i)$

“pt” $\Rightarrow(12-12i,3+16i,46+12i,73+23i,201+49i)$

“al” $\Rightarrow(12-12i,4+54i,44+53i,117+193i,231+389i)$

”!!” $\Rightarrow(12-12i,4+54i,32+65i,63+92i,121+247i)$

Şimdi, şifre çözme için $\theta^{-1}=60^{-1}=27+i$ var:

$($”O” $\Rightarrow)$ $(12-12i,15+4i,49+9i,106-10i,252-2i)*\theta^{-1}\%\alpha=(16,47 ,93,223,527)$

Şimdi, açgözlü algoritma geliyor:

İlk olarak, katkıda bulunan her faktörü bir ile çarparak çıkarırız, çünkü bunların sonuncusu için en az bir kez katkıda bulundukları bilinir ve şu sonucu verir:

• İkinci baytın ikinci parçası:

$T \sol ok (527-233-93-47-16) = 148$

$(T \geq 223) = (148 \geq 223) = false \Rightarrow b_1=0 ; T \sol ok (T - 0 * 223) = 148$

$(T \geq 93) = (148 \geq 93) = true \Rightarrow b_2 = 1; T \sol ok (T - 1 * 93) = 55$

$(T \geq 47) = 55 \geq 47) = true \Rightarrow b_3 = 1; T \sol ok (T - 1 * 47) = 8$

$(T \geq 16) = 8 \geq 16) = false \Rightarrow b_4 = 0; T \sol ok (T - 0 * 16) = 8$

Sonuç: 0110;

Kalan: 8 (dizinin başına yeni en düşük öğe olarak eklendi);

Mevcut dizinin finalinden 527 bırakın;

• İkinci baytın ilk nibble:

$T \sol ok (233-93-47-16-8) = 59$

$(T \geq 93) = (59 \geq 93) = false \Rightarrow b_1 = 0; T \leftarrow(T - 0 * 93) = 59$

$(T \geq 47) = (59 \geq 47) = true \Rightarrow b_2 = 1; T \sol ok (T - 1 * 47) = 12$

$(T \geq 16) = (12 \geq 16) = false \Rightarrow b_3 = 0; T \sol ok (T - 0 8 16) = 12$

$(T \geq 8) = (12 \geq 8) = true \Rightarrow b_4 = 1; T \sol ok (T - 0 * 12) = 4$

Sonuç: 0101;

Kalan: 4 (dizinin başına yeni en düşük öğe olarak eklendi);

Mevcut dizinin finalinden 233 bırakın;

• İlk baytın ikinci nibble:

$T \sol (93 - 47 - 16 - 8 - 4) = 18$

$(T \geq 47) = (18 \geq 47) = false \Rightarrow b_1 = 0; T \sol ok (T - 0 * 47) = 18$

$(T \geq 16) = (18 \geq 16) = true \Rightarrow b_2 = 1; T \sol ok (T - 1 * 16) = 2$

$(T \geq 8) = (2 \geq 8) = false \Rightarrow b_3 = 0; T \sol ok (T - 0 * 8) = 2$

$(T \geq 4) = (2 \geq 4) = false \Rightarrow b_4 = 0; T \sol ok (T - 0 * 4) = 2$

Sonuç: 0100;

Kalan: 2 (dizinin başına yeni en düşük öğe olarak eklendi);

Mevcut dizinin finalinden 93 bırakın;

• İlk baytın ilk nibble:

$T \sol ok (47-16-8-4-2) = 17$

$(T \geq 16) = (17 \geq 16) = true \Rightarrow b_1 = 1; T \sol ok (T - 1 * 16) = 1$

$(T \geq 8) = (1 \geq 8) = false \Rightarrow b_2 = 0; T \sol ok (T - 0 * 8) = 1$

$(T \geq 4) = (1 \geq 4) = false \Rightarrow b_3 = 0; T \sol ok (T - 0 * 4) = 1$

$(T \geq 2) = (1 \geq 4) = false \Rightarrow b_4 = 0; T \sol ok (T - 0 * 2) = 1$

Sonuç: 1000;

Kalan: 1 (dizinin başına yeni en düşük öğe olarak eklendi);

Mevcut dizinin finalinden 47 bırakın;

Sonuç olarak, mesajımızın ilk iki karakteri olan “He”yi içeren “01001000 01100101” veri bloğunu kurtardık. Sadece bu değil, ayrıca $(1,2,4,8,16)$ özel anahtar süper artan dizimizi de doğru bir şekilde aldık.

Diğer veri blokları haritaları da aynı şekilde gider.

Başlıca Açık Anahtar Kriptosistemleri ile Karşılaştırma

SRVB:

1. Tamamen ücretsiz ve herkese açık;

2. ECC'den ^[7] çok daha basit ve anlaşılması ve uygulanması daha kolay;

3. Anahtarlar boldur ve bu nedenle, örneğin, asal sayılara dayanan RSA'nın aksine, neredeyse maliyetsizdir, bu da pahalıdır.

En olası güvenlik açıklarını şimdiden özetleyebiliriz. SRVB, MH'den geldiği için, Shamir saldırısının veya onu kıran başka bir saldırının genelleştirilmesine karşı savunmasız olacağından şüphelenmek kolaydır. Yazarın durumun böyle olmayacağına inanmak için nedenleri olmasına rağmen, henüz bir doğrulama yapılmadı (ki bu kriptosistemlerle uğraşırken çok tipiktir).

Sıradaki ne?

Rocha, kullanılacak bölüm halkaları için muhtemelen kriptanalizin karmaşıklığında bir artışa yol açabilecek birkaç genelleme gözlemledi. Bu ihtimalleri de araştıracağız.

Lineer Cebirsel Obscuring

Olduğu gibi, SRVB'nin geliştirilmesi ve belgelenmesi sırasında, Villas Boas, bu makalenin çok uzun olmaması için, burada çok ayrıntılı olarak açıklanmayacak olan sırt çantası açık anahtarlı şifreleme kavramını geliştirmek için başka bir yaklaşım daha geliştirdi. ve yorucu, ama işte bir göz gezdirme. Bunu kavramayı başaramazsanız, endişelenmeyin, ayrıntılara daha ayrıntılı bir şekilde gireceğimiz bir sonraki makalemizin yayınlanması için bizi izlemeye devam edin: Diyelim ki, $y$ alt kümesine bakın: $N$ bölüm halka elemanları $u_i$ (önceki gibi süper artan dizinin $v_i$ pozitif tamsayılarına izomorfik olarak karşılık gelir), bu $u_i$ satır vektörünün bir sütun vektörü $B$ ile çarpımı olarak ( ikili için) sıfırlar ve birler ^[8] .

$y = \sum_{i=1}^n u_i b_i = (u_1,\cdot\cdot\cdot,u_n)^T\cdot(b_1,\cdot\cdot\cdot,b_n)$=UB,

nerede $b_i \in {0,1}$

Şimdi, bu $u_i$ vektörü yerine, sol tarafta $n$'a $N$ ($n < N$ ile) V matrisine sahip olduğunuzu, $v_i$'a (süper artan tamsayılar) sahip olduğunuzu hayal edin. dizisi) vektörü (genellik kaybı olmadan) ilk satırı olarak ve diğer tüm girişler gürültüyle dolu. Şimdi, V'yi aynı bit vektörü B ile çarpmanın size ilk girişi $w$ ve diğerlerinde gürültü olan bir sütun vektörü W verdiğine dikkat edin. Şimdi, bu V matrisini alın ve soldaki rastgele bir ^[9] n ile n matrisi R ile çarpın, n'ye N matrisi P'yi tanımlayın:

P = RV

Buradaki fikir, Bob'un P'yi yeni ortak anahtarı olarak kullanmasıdır. R'nin rastgeleliği nedeniyle, vektör

$Y = PB = RV B = RW$

V'nin diğer satırlarındaki gürültü tarafından gizlenen $w$ bilgisine sahiptir. Bob ayrıca önceden hesaplar ve aşağıdakileri karşılayan satır vektörü S'yi saklar:

$R^TS^T = e_1$

Alice, Y'yi Bob'a gönderdiğinde, sadece SY'yi bulur, çünkü:

$SY=S(PB)=S((RV)B)=SRVB= {e_1}^TR^{-1}((RV)B)=$

(şimdiye kadar sadece tanımlar)

${e_1}^T (VB)={e_1}^TW = w$

(Şimdi, Rs'yi iptal etmek için ilişkilendirmeden yararlanmak)

and then proceeds as before to extract the vector of $b_i$ from $w$ by means of the greedy algorithm.

So, in one word, the Linear Algebraic Obscuring exploits the associativity of matricial multiplication (the fact that we could expand the terms and then operate their components in a new order provided we that preserved the sequence of all the operands in the sequence) to 'linearly' scramble and then filter (in the encryption and in the decryption respectively) noise to/from $w$. And in limit case $n = 1$, the system elegantly goes back to original to Rocha's approach.

The SRVB Campaign – a prize challenge

As explained before, in accordance to Kerckhoffs' principle, experience shows that antiquity of a publicly known unbroken cryptosystem is the main source of reliability of it, far more than any theoretical argumentation by the own authors, apart from anything else, because definitive proof of efficacy of the algorithms usually are not available.

And here it is our great chance to put these concepts to practice to earn a big money prize: Aware of this fact, we launched the aforementioned campaign, which is basically a crowdfunding for a prize automatically awarded to the first one that manages to break a message. The money is going to be converted to bitcoins in a given wallet whose private key will be SRVB encrypted and published so that anyone able to decipher it can simply take the money anonymously, no questions asked.

Teşekkür

This article in particular and the whole SRVB Crypto project in general have been greatly helped by Prof. Charles F. de Barros, assistant professor at the Federal University of Sao Joao Del Rei. Prof. Barros provided us a technical review of the SRVB cryptosystem itself. I judged it necessary to submit to before daring to publish, and that I would certainly take much longer to do by myself.

In addition, I also would like to extend my deep gratitude to professor Adnan Ademovic for his extraordinarily insightful, attentive, and patient work as the editor of this article.

Sözlük

1. Cryptology/Cryptography: The science/practice of making a message nearly impossible to interpret without a specific set of instructions (in this context, the so-called "key"), thus allowing agents who share these instructions to communicate securely even if tapped by third parties;
2. Steganography: The science/practice of hiding a message within another by means of adding apparently innocuous modifications to the latter;
3. Key generation: the mapping of (expectedly) random inputs into (as random) valid keys;
4. Encryption/Encoding: The easily computable mapping of an easily interpretable message into another that is either hard or impossible to construe, by means of an (as randomly specified) element the one correspondent to the key of a (by Kerckhoffs' principle, publicly known and validated) family of algorithms;
5. Decryption/Decoding: The easily computable mapping that consists of the inverse of the previous, also being definable by an (as randomly specified, and therefore, unknown and hard to be guessed by third parties) element _again, the one correspondent to the key_ of a (by the same principle, usually known) family of algorithms, that thus outputs the original message when input with the encrypted one;
6. Cryptosystem: A triad of the family of encoding algorithms, the family of corresponding decrypting algorithms, and a key generating algorithm;
7. Allies: The agents with whom the communication is intended, and who are expected to act according to the protocol's rules;
8. Enemies/Third Parties: The agents with whom the communication is not intended, but try, nevertheless, to eavesdrop the communication and bypass the security enhanced by the cryptosystem;
9. Secure Channel: Any protocol (procedure) for communication that is easy to use while also effectively preventing third parties to feasibly construe what is meant by its users;
10. Insecure Channel: any channel (ie, protocol or procedure) that, as the name suggests, is not a secure channel;
11. Breaking a Key: The process of discovering a key by means of public pieces of information (like an encrypted message or public key) other than the key itself to be discovered and that was not expected to feasibly allow the discovery of the key. Since the information that results from this process grants the decryption of the messages, this is a particular case of…
12. Breaking/Deciphering a message: Any way to deduce the original content of an encrypted message only by means of the encrypted message itself and other pieces of information that were not expected to suffice for the deduction of the original content;
13. Breaking a Cryptosystem: Discovery of a systematic way to feasibly break whatever message is encrypted by this method under whatever parameter;
14. Kerckhoffs' Principle/Desideratum/Axiom/Law: A cryptologic principle named after the dutch cryptographer Auguste Kerckhoffs, according to which, in order for a cryptosystem to be deemed secure, everything about it except by its (private) keys must be of public knowledge;
15. Key: Secret parametrization of a cryptosystem allowing it to be infeasible to be guessed (and consequently broken) by third parties while also being validated by the community of cryptanalysts (in accordance to Kerckhoffs' principle);
16. Symmetric Cryptosystem: Any cryptosystem on which any parameter for the encoding suffices for easily deducing the parameter for decoding, and, for this reason, must be kept private. One can rephrase it by saying that the encryption and decryption parameters are both equivalent to the key;
17. Asymmetric/Public Key Cryptosystem: Any cryptosystem for which there is a way to express the parameters for the encoding that does not suffice to feasibly deduce the correspondent parameter for decoding, allowing it to be sent to allies through an insecure channel, or even made public, and thus creating a secure channel where there was none;
18. Public Key: A component of an asymmetric cryptosystem that suffices for parameterizing the encryption but does not suffice for feasibly deducing the decryption parameter, ie, the…
19. Private Key: A component of an asymmetric cryptosystem that suffices for parameterizing the decryption and thus must be kept privately and usually also suffices for parameterizing the encryption;

^[1] Note that, here, the phrases decipher or decrypt do not apply, because before a given cryptosystem (with all its components, including its keys) is well defined, one cannot classify a given method of construing the original message from the encrypted one as the intended communication (decryption) or an attack (deciphering).

^[2] Though there are techniques to improve this guessing work, it still remains far more difficult discovering than multiplying them.

^[3] The first inspiration was to look at the tree of the tau conjecture, an infinite tree rooted in the number 1, whose other nodes consist of integers resulting in one binary operation of sum, subtraction, or multiplication between previous nodes, possibly one node operated with itself. The theory's goal relates to the depth, in this tree, in which each integer first appears. It is apparently hard to find large numbers in low branches (even if we relax the need for it), but is it immediate to check if a given sequence of operations indeed produces a given result.

^[4] This is surely not the most natural approach, but by adopting this, one ensures that this byte filling (called padding)…

1. Conceals the size of the padding (differently, for example of ciphertext stealing) and obscures the end of the message, thus rendering chosen-plaintext attacks more difficult;
2. Enhances a distribution of bits as close to uniform as possible;

If the last blocks of every message were known to be systematically biased in a far from uniform distribution, an attacker could exploit this fact to do a statistical cryptanalysis, for any given sample of messages would be statistically more representative than otherwise. In other words, the last blocks being statistically less diverse, they become they become the weakest links of the message.

^[5] Make no mistake: this greatest common divisor is Gaussian, while the previous is real.

^[6] …which is not perfect, because it easily gives away the fact that the last three components are proportional to 1, 2, and 4. But, again, for the sake of simplicity, we will ignore this detail.

^[7] …which is so complex that there are a few notorious cases of failure to implement and maintain protocols based on it.

^[8] Here, we will not adopt Rocha's approach of a multiple linear combinations block, which also allows us to randomly permute the bis to obscure them even more.

^[9] Though not totally random. Its transpose must span the subspace generated by the vector $ e_1 = (1,0,…,0) $.