Många designer hävdade att deras kryptografischema har 80-bitars säkerhet. Så hur man beräknar tiden för attttcking detta 80-bitars säkerhet kryptografi schema, till exempel 80-bitars säkerhet RSA med hjälp av en slags CPU? li> 80-bitars RSA kan brytas i en blinkning, med t.ex. GMP-ECM . För information om RSA-faktoriseringsposter, se detta . För information om 80-bitars säkerhet, se detta . För val av nyckelstorlek, se detta .
Svar
Frågan kokar till stor del till:
Vad betyder $ n $ -bit säkerhet i praktiken för ett givet värde av $ n $ ?
TL; DR: lika säker som en bra symmetrisk chiffer med en $ n $ -bit-nyckel.
Det finns inte en enda mer exakt definition, även om vi begränsar oss till angripare som använder klassisk datorer (snarare än kvantdatorer), som detta svar gör.
En allmänt accepterad betydelse är att antalet ”steg” för att bryta systemet antas vara $ 2 ^ n $ , eller mer exakt att sannolikheten att bryta systemet med $ s $ ”steg” inte är känd för att vara mer än $ s \, 2 ^ {- n} $ med vilken metod som helst för valfri $ s $ . Men ”steg” och ”bryt” definieras inte exakt.
I teorin om symmetrisk kryptering tas ”steg” vanligtvis som en exekvering av krypteringen med en ny nyckel. På detta sätt har en ideal chiffer med en nyckel på $ n $ bitar $ n $ -bit säkerhet, under brute force nyckelsökning. När vi går för att träna är attackerare inte tvungna att använda brute force-sökning, och definitionen av ett ”steg” måste bli ett antal delsteg som kan jämföras i antal och beräkningskostnad med de delsteg som krävs för en exekvering av kryptering med en ny nyckel för klartext storleken på nyckeln . Med denna definition har en praktisk chiffer med en nyckel på $ n $ bitar högst $ n $ – bit säkerhet och syftar till det idealet.
När vi går till hash kan definitionen av ett steg bli ett antal delsteg som kan jämföras i antal och beräkningskostnad med de nödvändiga delstegen för att hasha ett nytt meddelande storleken på hash-utdata .
Ett av många problem med ovanstående är att det inte finns någon överenskommelse om vi ska räkna eller inte kostnaden för minne och minnesåtkomst i beräkningskostnaden. Det säkra ur en användares perspektiv är att inte räkna det, men det kan vara av yttersta vikt för en angripare.
Definitionen av ”steg” blir ännu grumligare när det gäller asymmetrisk kryptografi som RSA.I teorin kan ”steg” vara en beräkning i den algebraiska strukturen som används för kryptosystemet; som, för RSA, en utvärdering av modulär multiplikation $ (a, b) \ mapsto a \, b \ bmod N $ för godtyckligt heltal $ a $ och $ b $ i $ [0, N) $ , där $ N $ är den offentliga modulen. Men det finns problem att flytta detta till praktiken, särskilt för RSA: den mest kända attacken är att faktorera den offentliga modulen $ N $ med GNFS -algoritm, vilken beräkningskostnad domineras av operationer som har liten likhet med modulär multiplikation, och av praktiska kostnader som domineras av minne och åtkomst till minne. Vilket sätter användningen tillbaka till den vaga definitionen i TL; DR.
hur man beräknar tiden för att attackera detta 80-bitars säkerhetskrypteringsschema, t.ex. 80-bitars säkerhets-RSA med en slags CPU?
”80-bitars säkerhets-RSA” ska inte förstås som RSA med en 80-bitars allmänhet modul $ N $ , som slutligen är osäker. Om vi hade storleken $ N $ , kunde vi uppskatta svårigheten utifrån den och tidigare erfarenheter (se detta och dess länkar). Men vi gör det inte, och det finns ingen enighet om storleken på $ N $ för RSA med 80-bitars säkerhet: 1024-bitar citeras ofta, men beroende på hypotesen , och vem du frågar, det är grovt för mycket eller för lite. Således är det bästa att ignorera att vi pratar om RSA, och komma tillbaka till: så mycket tid som behövs för att bryta en bra symmetrisk chiffer med en 80-bitars nyckel.
Vilket tar oss till: $$ \ text {Time} = \ frac {2 ^ n \ times k \ times p} {\ text {Frequency } \ times \ text {Number-of-CPUs}} $$ där $ n $ är säkerhetsnivån i bitar, $ k $ är en uppskattning av antalet CPU-cykler för att utvärdera en bra kryptering med hjälp av en ultraoptimerad algoritm och $ p $ är den återstående sannolikheten för en motståndares framgång. Beroende på perspektiv kan vi ta $ k = 1 $ (vilket sparar att undersöka uppgifterna), $ k = 32 $ (eftersom det fortfarande är mindre än i de bästa attackerna mot bra chiffror med en dator för allmänt ändamål), eller mycket mer. Beroende på perspektiv kan vi ta $ p = 1 $ (mest försiktiga ur en legitim användares perspektiv), $ p = 1/2 $ (ger den förväntade tiden vid en blockkodning) eller en mindre $ p $ om vi vill ha en säkerhetsmarginal¹.
Till exempel med $ n = 80 $ , $ k = 1 $ , $ p = 1/1000 \ approx2 ^ {- 10} $ , $ \ text {Frequency} = 4 \ text {GHz} \ approx2 ^ {32} \ text {s} ^ {- 1} $ , $ \ text {Number-of-CPUs} = 1000 \ approx2 ^ {10} $ , vi får $ \ text {Time} \ approx2 ^ {80-10-32-10} \ text {s} = 2 ^ {28} \ text {s} $ , det är ungefär åtta år. Med andra ord, våra 1000 processorer har bara en mycket liten sannolikhet för framgång mot 80-bitars symmetrisk krypto, tills de blir tekniskt föråldrade.
Å andra sidan är 1000 processorer en liten bråkdel av globala processorer och bitcoinbrytning visar slutgiltigt att 80-bitars krypto inte längre räcker mot motståndare med förmågan att designa ASIC, bygga dem i stora mängder och upprätthålla energikostnaderna för deras drift; se detta .
¹ Termen $ p $ i formeln är den mest försiktiga ur en legitim användares perspektiv, men det gör att $ \ text {Time} $ underskattas i många attackscenarier. Till exempel i kollisionssökning, den rätta termen skulle vara mer som $ \ sqrt p $ .