RSA şifreleme (üç buluş baş harflerinden adlandırılır) olan bir algoritma bir asimetrik kriptografi , yaygın olarak kullanılan elektronik ticaret ile ilgili gizli veri alışverişi için daha genel olarak ve internet . Bu algoritma 1977'de Ronald Rivest , Adi Shamir ve Leonard Adleman tarafından tanımlanmıştır . RSA, 1983 yılında Amerika Birleşik Devletleri'nde Massachusetts Teknoloji Enstitüsü (MIT) tarafından patentlenmiştir . Patent 21 Eylül 2000 tarihinde sona ermiştir.
Şifreleme RSA'dır asimetrik : Bir oluşan tuşları (tamsayılar) bir çift kullanan ortak anahtar için şifreleme ve bir özel anahtar için şifresini gizli verileri. Her iki anahtar genellikle isimli şahsın, tarafından oluşturulur kongre tarafından Alice kendisine gönderilen gizli verileri istiyor. Alice, genel anahtarı erişilebilir kılar. Bu anahtar, muhabirleri ( Bob vb.) tarafından kendisine gönderilen verileri şifrelemek için kullanılır. Özel anahtar Alice için ayrılmıştır ve bu verilerin şifresini çözmesine izin verir. Özel anahtar ayrıca Alice tarafından gönderdiği verileri imzalamak için de kullanılabilir ; genel anahtar, muhabirlerinden herhangi birinin imzayı doğrulamasını sağlar.
Temel bir koşul, yalnızca genel anahtarı kullanarak şifreyi çözmenin, özellikle özel anahtarı genel anahtardan yeniden oluşturmanın "hesaplama açısından imkansız" olmasıdır, yani, mevcut hesaplama araçları ve işlem sırasında bilinen yöntemler. takas (ve sırrın saklanması gereken zaman) buna izin vermez.
RSA şifrelemesi genellikle simetrik bir şifreleme anahtarı iletmek için kullanılır , bu daha sonra alışverişin gizli bir şekilde devam etmesine izin verir: Bob, Alice'e daha sonra Alice ve Bob tarafından veri alışverişi için kullanılabilecek bir simetrik şifreleme anahtarı gönderir.
Ronald Rivest, Adi Shamir ve Leonard Adleman, şifrelemelerini 1978'de Dijital İmzaları ve Açık Anahtarlı Kriptosistemleri Elde Etme Yöntemi'nde yayınladılar . Gizli ihlal (veya arka kapı) ile tek yönlü fonksiyonlar elde etmek için tamsayılar ve Fermat'ın küçük teoremi üzerinde kongrüanslar kullanırlar .
Tüm hesaplamalar, iki asal sayının çarpımı olan bir n tamsayısına göre yapılır . Fermat'ın küçük teoremi şifreleme tasarımında önemli bir rol oynar.
Açık ve şifreli mesajlar, n tamsayısından daha küçük tam sayılardır . Şifreleme ve şifre çözme işlemleri, mesajı belirli bir modulo n gücüne yükseltmekten oluşur (bu, modüler üs alma işlemidir ).
RSA algoritmasının dayandığı matematiksel ilkelerin sadece açıklaması yeterli değildir. Pratik uygulaması, güvenlik için gerekli olan diğer konuların dikkate alınmasını gerektirir. Örneğin, çift (özel anahtar, genel anahtar), bilinse bile özel anahtarın yeniden oluşturulmasına izin vermeyen gerçekten rastgele bir süreç tarafından oluşturulmalıdır. Şifreli veriler çok kısa olmamalıdır, böylece şifre çözme gerçekten modüler bir hesaplama gerektirir ve uygun şekilde tamamlanır (örn. Optimal Asimetrik Şifreleme Doldurma ile ).
Anahtar oluşturma adımından Alice sorumludur. Anahtarlar yeniden kullanılabildiği için her şifrelemeye müdahale etmez. Şifrelemenin çözemediği ilk zorluk, Bob'un elindeki açık anahtarın Alice'in olduğundan oldukça emin olmasıdır. Anahtarların yenilenmesi, yalnızca özel anahtarın tehlikeye girmesi durumunda veya belirli bir süre sonra (yıllar olarak sayılabilir) bir önlem olarak gerçekleşir.
Şöyle e cp (asal olan , n göre) teoremi Bachet-Bezout orada iki tamsayı mevcut d ve k , öyle ki ed = 1 + k φ ( n ), yani yani ed ≡ 1 (mod φ ( n ) ): e gerçekten de ters çevrilebilir modulo φ ( n ).
Bir önceki paragrafta boyunca kullanabileceğimiz Carmichael göstergesi , bölen φ ( n ) .
( n , e ) - veya ( e , n ) - çifti , şifrelemenin genel anahtarıdır , özel anahtarı ise d sayısıdır , şifre çözme işleminin yalnızca özel anahtar d'yi ve tarafından bilinen n tamsayısını gerektirdiğini bilir . genel anahtar (özel anahtar bazen çift ( d , n ) veya üçlü ( p, q , d ) olarak da tanımlanır ).
Eğer M bir doğal sayı kesinlikle daha az olduğu , n bir mesajı temsil eden, daha sonra şifrelenmiş mesaj ile temsil edilecektir
doğal sayı C kesinlikle n'den daha az seçiliyor .
C'yi deşifre etmek için , e modulo'nun ( p - 1) ( q - 1) tersi olan d'yi kullanırız ve M düz mesajını şu şekilde buluruz :
Küçük asal sayılar içeren bir örnek (pratikte çok büyük asal sayılara ihtiyacınız vardır):
Alice'in genel anahtarı ( n , e ) = (33, 3) ve özel anahtarı ( n , d ) = (33, 7). Bob, Alice'e bir mesaj gönderir.
Alice'in özel anahtarını kullanarak imzalama mekanizması, anahtarların değiş tokuş edilmesiyle benzerdir.
Kanıt, Fermat'ın küçük teoremine dayanmaktadır , yani p ve q iki asal sayı olduğundan, M , p'nin katı değilse birinci eşitliğimiz var ve q'nun katı değilse ikincisi :
Aslında
Altın
bu, öyle bir k tamsayısının var olduğu anlamına gelir
bu nedenle, Fermat'ın küçük teoremine göre M , p'nin katı değilse
ve benzer şekilde, M q'nun katı değilse
İki eşitlik aslında herhangi bir M tamsayı için elde edilir , çünkü M , p'nin bir katıysa , M ve sıfır olmayan tüm güçleri 0 modulo p ile uyumludur . Aynı şekilde q için .
Bu nedenle tamsayı , farklı asal olan p ve q'nun bir katıdır , bu nedenle onların ürünü pq = n'dir (bunu asal faktörlere ayrışmanın benzersizliğinin bir sonucu olarak görebiliriz veya daha doğrudan Gauss lemmasının bir sonucu olarak görebiliriz) . , p ve q'nun kendi aralarında asal olduğunu bilmek, asal ve farklı olmak).
Bir mesajı şifrelemek için e ve n'yi bilmenin yeterli olduğunu görüyoruz . Öte yandan, deşifre etmek için d ve n'ye ihtiyacımız var .
e ve n kullanarak d'yi hesaplamak için , e modulo ( p - 1) ( q - 1) ' nin modüler tersini bulmalıyız, bunu p ve q tamsayılarını bilmeden yapamayız , yani n'nin asal sayıya ayrıştırılmasını faktörler.
Bu nedenle şifreleme, p ve q'yu bulabilmek için "çok büyük" sayıların asal sayılar olduğunu doğrulayabilmeyi gerektirir , ancak aynı zamanda bu çok büyük iki sayının çarpımının pratikte çarpanlara ayrılamayacağını da gerektirir. Aslında bir sayının asal olmadığını kontrol etmeyi mümkün kılan bilinen verimli algoritmalar çarpanlara ayırma sağlamaz.
Değeri φ ( n arasında) Euler indikatriks de n olan gruptan sırası tersine döndürülebilir eleman halka ℤ / nℤ . Bu tarafından derhal görmek mümkün kılan Euler teoremi (sonucu Lagrange teoreminin takdirde,) M ile asal n bu nedenle ters çevrilebilir (için geçerlidir hangi “en” doğal tamsayılar M kesinlikle daha az n )
veya RSA şifrelemesini doğrulamak için (bu tür M için ).
n , farklı asal sayıların bir ürünü olduğunda , eşitliğin tüm M için geçerli olduğu ortaya çıkar (kanıt, n'nin iki asal sayının bir ürünü olduğu özel durumda, esasen yukarıda RSA için yapılandır).
Anahtar çifti, büyük boyutlu iki asal sayı seçmeyi ister, böylece çarpımlarını çarpanlara ayırmak hesaplama açısından imkansızdır.
Büyük boyutlu bir asal sayı belirlemek için, isteğe bağlı olarak yeterli büyüklükte rastgele bir tek tamsayı sağlayan bir yöntem kullanıyoruz, bir asallık testi asal olup olmadığını belirlemeyi mümkün kılıyor ve bir asal sayı olur olmaz dururuz. elde edildi. Asal sayı teoremi bir asal sayı denemeden makul sayıda sonra bulunursa olmasını sağlar.
Ancak, yöntem çok hızlı bir asallık testi gerektirir. Pratikte, bir olasılık testi, Miller-Rabin asallık testi veya bir varyantı kullanılır. Böyle bir test, sayının asal olduğunu tam olarak garanti etmez, ancak yalnızca (çok) yüksek bir olasılıktır.
Gerekli özelliklerGüvenlik ihlallerini, ilk iki numara engellemek için ve aşağıdaki özellikleri karşılaması gerekir anahtar çiftini oluşturmak için seçilmiş:
Seçilen üs aşağıdaki özellikleri doğrulamalıdır:
Hesaplanması birinci hesaplama ile yapılamaz c , d , daha sonra geri kalan modülo N o kadar çok büyük tamsayı manipülasyonunu gerektirir, çünkü. Modüler üstelleştirmeyi hesaplamak için etkili yöntemler vardır .
Çin Kalan Teoremi'ni kullanarak daha hızlı şifre çözmeye izin vermek için özel anahtarın farklı bir formunu tutabiliriz .
Yalnızca n bilgisine dayalı olarak p ve q bulmayı içeren kaba kuvvet saldırıları ile kriptografik bilgi temelinde n bilgisine ve aynı zamanda p ve q'nun oluşturulma şekline dayalı saldırılar arasında ayrım yapmalıyız. kullanılan yazılım, bir veya daha fazla mesaj muhtemelen ele geçirildi vb.
RSA algoritmasının kaba kuvvet saldırılarına karşı güvenliği iki varsayıma dayanır:
İki varsayımdan birinin veya her ikisinin de yanlış olması mümkündür. Şimdiye kadar, RSA'yı bu kadar başarılı yapan şey , bilim camiasının geleneksel bilgisayarlarla kaba kuvvet saldırısı gerçekleştirebileceği bilinen bir algoritmanın olmamasıdır .
2 Aralık 2019dağıtılmış bir hesaplama yöntemi kullanılarak bu yolla çarpanlarına ayrılan en büyük sayı 795 bit uzunluğundaydı . RSA anahtarlarının uzunluğu genellikle 1024 ile 2048 bit arasındadır. Bazı uzmanlar yakın gelecekte 1024 bitlik anahtarların kırılabileceğine inanıyor (bu tartışmalı olmasına rağmen ), ancak çok azı yakın gelecekte 4096 bit anahtarları bu şekilde kırmanın bir yolunu görüyor. . Ancak, anahtar boyutu yeterince büyükse RSA'nın güvenli kaldığı varsayılabilir. Boyutu 256 bitten daha küçük bir anahtarın çarpanlara ayrılması, ücretsiz olarak kullanılabilen bir yazılım kullanılarak kişisel bir bilgisayarda birkaç dakika içinde bulunabilir. 512 bit'e kadar bir boyut için ve 1999'dan beri birlikte çalışmak için birkaç yüz bilgisayarın yapılması gerekiyor. Güvenlik için, şu anda RSA anahtarlarının boyutunun en az 2048 bit olması önerilir.
Bir kişinin n sayısını çarpanlara ayırmak için "hızlı" bir yolu olsaydı, bu ilkeye dayalı tüm şifreleme algoritmaları ve bu algoritmalar kullanılarak geçmişte şifrelenmiş tüm veriler sorgulanırdı.
1994 yılında, kuantum bilgisayarlar için üstel olmayan zamanda sayıları çarpanlarına ayırma algoritması yazıldı . Bu, Shor algoritmasıdır . Kuantum bilgisayarların uygulamaları teorik olarak RSA'yı kaba kuvvetle kırmayı mümkün kılıyor ve bu konuda araştırmaları harekete geçirdi; ancak şu anda bu bilgisayarlar, onları verimsiz yapan rastgele hatalar üretiyor.
Çok daha etkili olan diğer saldırı türleri (aşağıdaki Saldırılara bakın), p ve q asal sayılarının oluşturulma şeklini, e'nin nasıl seçildiğini, kodlanmış mesajların bulunup bulunmadığını veya başka herhangi bir bilgiyi hedefler. Kullanılmış. Bu konuyla ilgili araştırmaların bir kısmı yayınlandı, ancak kriptanaliz şirketleri ve NSA gibi istihbarat teşkilatları tarafından geliştirilen en yeni teknikler gizli kalıyor.
Son olarak, n sayısını çarpanlara ayırarak bir anahtarı kırmanın , şifrelenmiş bir mesajın hazır olmasını beklemeyi gerektirmediğine dikkat edilmelidir . Bu işlem, yalnızca erişime açık olan genel anahtar bilgisi temelinde başlatılabilir . Bu koşullar altında, eğer n çarpanlara ayrılırsa , özel anahtar hemen çıkarılır. Bu gözlemin sonuçları aynı zamanda bir kodun kullanılmadan önce bile kırılabilmesidir.
İki kişi, örneğin elektronik ticaret ile İnternette , gizli bir şekilde dijital bilgi alışverişi yapmak istediğinde, bu dijital verileri şifrelemek için bir mekanizma kullanmaları gerekir . RSA asimetrik bir şifreleme algoritması olduğundan , bu şifreleme mekanizmalarının kapsamını devralır. Alıntı yapacağız:
İkincisi aslında bir RSA mekanizmasına entegre edilmiştir. Aslında simetrik algoritmalardaki sorun, şifreleme anahtarının yalnızca bir sırrı paylaşmak isteyen kişilere açıklandığından emin olmanız gerektiğidir. RSA, bu simetrik anahtarın güvenli bir şekilde iletilmesine izin verir. Bunu yapmak için Alice önce simetrik bir anahtar seçecektir. Bob ile bir sır alışverişi yapmak isteyen Bob, bu simetrik anahtarı RSA kullanarak ona iletecektir. Bunun için simetrik anahtarı Bob'un açık anahtarı (RSA) ile şifreleyecek, böylece bu simetrik anahtarın şifresini sadece Bob'un çözebileceğinden emin olacaktır. Bob mesajı aldığında, şifresini çözer ve daha sonra Alice tarafından ayarlanan simetrik anahtarı kullanarak ona şifreli mesajlar göndermek için kullanabilir ve bu şifreyi sadece kendisi ve Alice çözebilir.
RSA şifrelemesini kırmak için birkaç saldırı önerildi.
Saldırı Wiener gizli üs halinde (1989) kullanışlı d altındadır . Bu durumda, devam eden kesir genişlemesini kullanarak gizli üssü bulabiliriz .
Keşfedilen ilk saldırılardan biri olan (1985'te) Håstad saldırısı , genel üs e'nin yeterince küçük olma olasılığına dayanır . En azından farklı alıcılara gönderilen aynı mesajı yakalayarak, orijinal mesajı Çince kalan teoremini kullanarak bulmak mümkündür .
Paul Kocher 1995'te RSA'ya yeni bir saldırı tanımladı: Saldırganın Eve'in Alice'in belgeleri hakkında yeterince bilgisi olduğunu ve birkaç şifreli belgenin şifre çözme sürelerini ölçebildiğini varsayarsak, şifre çözme anahtarını hızlı bir şekilde çıkarabilecekti. Aynı şey imza için de geçerli olacaktır.
2003'te Boneh ve Brumley , Çin kalan teoremine uygulanan bazı optimizasyonların filtreleyebileceği bilgilere dayanarak bir ağ bağlantısında ( SSL ) RSA çarpanlarına ayırmayı mümkün kılan daha pratik bir saldırı gösterdiler . Bu saldırıları engellemenin bir yolu, şifre çözme işleminin sabit bir süre almasını sağlamaktır. Ancak, bu yaklaşım performansı önemli ölçüde azaltabilir. Bu nedenle çoğu uygulama (uygulanan) RSA, "kriptografik körlük" ( körleme ) adı altında bilinen farklı bir teknik kullanır .
Körlük, hesaplamaya etkisi iptal edilebilecek rastgele bir gizli değer ekleyerek RSA'nın çarpımsal özelliklerinden yararlanır. Bu değer her şifreleme için farklı olduğundan, şifre çözme süresi artık şifrelenecek verilerle doğrudan ilişkili değildir, bu da zamanlama saldırısını yener: hesaplamak yerine , Alice önce gizli bir rastgele değer r seçer ve hesaplar . Bu hesaplamanın sonucu şudur ve bu nedenle r'nin etkisi , tersi ile çarpılarak iptal edilebilir.
Bu makalede açıklandığı gibi, RSA deterministik bir şifredir ve bu nedenle anlamsal olarak güvenli olamaz . Bir karşı önlem, hiçbir mesaj değeri şifrelendikten sonra güvenli olmayan bir sonuç vermeyecek şekilde olasılıksal bir doldurma şemasının kullanılmasıdır , örneğin C = M e ≤ N ise , basit bir saldırı doğrudan e-th kökünden yapılan hesaplamadır. Modülo N azaltılmıyacak olan C'nin.
1998'de Daniel Bleichenbacher, RSA mesajlarına karşı ilk pratik "uyarlanabilir seçilmiş şifre" saldırısını tanımladı. PKCS #1 v1 dolgu şemasındaki kusurlar nedeniyle , SSL oturum anahtarlarını kurtarabildi . Bu çalışmanın bir sonucu olarak, kriptograflar artık resmi olarak güvenli doldurma yöntemlerinin kullanılmasını önermektedir OAEP ve RSA Laboratories gibi , bu saldırılara dayanıklı yeni PKCS # 1 sürümlerini yayınladı .