Bästa svaret
I kryptanalysfältet är det stor skillnad mellan ” crack ”och” break ”.
Du sprickar ett lösenord i den enklaste meningen genom att försöka låsa upp systemet med alla möjliga iterationer av det lösenordet, en metod som kallas brute-force cracking. Om du känner till reglerna som styr skapandet och användningen av lösenordet, vet du också i förväg vilken tid / ansträngningskostnad som ligger i den chiffran. Varje enskild algoritm där ute har en känd förväntad beräkning som krävs för att knäcka den.
En algoritm, som MD5 eller SHA-1 (verkliga exempel) sägs vara bruten när du hittar någon form av kollision som minskar det förväntade universumet (alla möjliga lösningar på formeln som används för att skapa nyckeln / lösenordet).
För att förenkla, låt mig gå igenom ett verkligt exempel på WPS (Wi-Fi Protected Setup ). WPS skapades för att underlätta för användare att säkra sina Wi-Fi-nätverk. Den bestod av en åttasiffrig PIN-kod som skulle utbytas mellan den begärande användaren och routern genom att trycka på en knapp.
Skaparna av systemet visste i förväg det förväntade universumet: 8 siffror ger dig 100.000.000 möjliga kombinationer (10 ^ 8). Implementeringen av protokollet delade emellertid upp det numret i två fyrsiffriga kombinationer som validerades separat.
Detta innebar att du bara faktiskt skulle behöva testa 10 000 (10 ^ 4) + 10 000 (10 ^ 4) kombinationer, i värsta fall, för att knäcka PIN-koden. Ditt universum med 100 miljoner kombinationer sjönk nu plötsligt till bara 20 000 kombinationer. Algoritmen är trasig . Du kan sedan försöka knäcka det – som du skulle kunna ha gjort om det inte hade gått sönder – men eftersom det har gått sönder är dina chanser att lyckas mycket bättre, bara kräver högst 20 000 försök istället för 100 miljoner.
Slutsatsen att dra av detta:
Att bryta och spricka är olika saker. En trasig chiffer betyder inte att den är osäker, bara att det är lättare att knäcka nu. Beroende på värdet av vad som skyddas av det, stavas inte döden för ett visst system, utan bara en förståelse för att det är mindre säkert än vad man ursprungligen förväntade sig vara.
RSA-2048 kommer att brytas om någon hittar ett sätt att skapa kollisioner som i sig minskar det förväntade antalet kombinationer för att knäcka krypteringen.RSA 2048 kan knäckas som det är, som alla andra krypteringar, med brute-force.
Svar
RSA, i och för sig själv, har bara ett fåtal attacker mot den offentliga modulen (som vanligtvis är en halvprime eller två stora slumpmässigt valda prim s multipliceras tillsammans). Den mest effektiva klassiska algoritmen för att lösa faktoriseringsproblemet, som möjliggör härledning av den privata nyckeln med grundläggande aritmetik, är GNFS (General Number Field Sieve). Denna algoritm körs under exponentiell tid och är inte möjlig att använda på korrekt implementerade RSA-2048 bitsystem.
Det finns också Shors algoritm, men det kan inte monteras på RSA-2048 av en typisk angripare. Quantum-datortillverkare driver ett oligopol, särskilt ledt av D-Wave. Det är inte bara otroligt dyrt att få en, men det kräver också specialutrustning för att köra och underhålla dem. Inget chip har skapats med tillräcklig uthållighet och kraft för att bryta mer än några få bitar.
Som nämnts tidigare är ett kryptosystem inget utan en korrekt implementering. De flesta implementeringar av RSA använder också en algoritm för fingeravtryck för allmän nyckel, vanligtvis en hash. Förutom det är det möjligt att hitta faktorisering av primtal med en exploatering som är otroligt sällsynt och också statistiskt försumbar när det gäller framgångsgrad. Som Euclid påpekade finns det oändliga primtal, men det finns inte bara oändliga primtal, det finns många i ett visst tangentutrymme. Om två moduler råkar dela samma prime, är det enkelt att hitta deras faktorisering. Med hjälp av största gemensamma divisoralgoritm , som körs linjärt (den kan enkelt köras på den enhet du tittar på denna inom millisekunder), kan den gemensamma faktorn hittas och delas sedan ut från modulerna för att ge de två andra saknade primtal. Detta leder till åtkomst till båda nycklarna. Varje korrekt implementering av RSA skulle aldrig återanvända primtal för separata nycklar, utan istället välja dem helt slumpmässigt. Eftersom det finns många möjliga moduler inom 2048-bitars nyckelutrymme, som kan skrivas som antalet primtal längd 2048 välj 2 (eller högre än 2 om du arbetar med icke-standardmoduler) är chansen att två tangenter till och med delar två primtal är försumbar . Det är med andra ord helt enkelt slöseri med att ta alla nycklar från en nyckelserver och köra GCD-algoritmen på dem alla.