RSA problem
I kryptografi sammanfattar RSA -problemet uppgiften att utföra en RSA -privatnyckeloperation med endast den publika nyckeln . RSA-algoritmen höjer ett meddelande till en exponent , modulo ett sammansatt tal N vars faktorer inte är kända. Således kan uppgiften enkelt beskrivas som att hitta de e : te rötterna till ett godtyckligt tal, modulo N. För stora RSA- nyckelstorlekar (över 1024 bitar) är ingen effektiv metod för att lösa detta problem känd; om en effektiv metod någonsin utvecklas, skulle den hota den nuvarande eller eventuella säkerheten för RSA-baserade kryptosystem – både för kryptering med offentliga nyckel och digitala signaturer .
Mer specifikt är RSA-problemet att effektivt beräkna P givet en publik RSA-nyckel ( N , e ) och en chiffertext C ≡ Pe ( mod N ) . Strukturen för den publika RSA-nyckeln kräver att N är ett stort halvprimtal (dvs en produkt av två stora primtal ), att 2 < e < N , att e är samprime till φ ( N ), och att 0 ≤ C < N . C väljs slumpmässigt inom detta intervall; för att specificera problemet med fullständig precision måste man också specificera hur N och e genereras, vilket kommer att bero på det exakta sättet att generera RSA slumpmässigt nyckelpar som används.
Den mest effektiva metoden som är känd för att lösa RSA-problemet är att först faktorisera modulen N, en uppgift som tros vara opraktisk om N är tillräckligt stor (se heltalsfaktorisering ) . RSA-nyckelinställningsrutinen förvandlar redan den offentliga exponenten e , med denna primfaktorisering, till den privata exponenten d , och så exakt samma algoritm tillåter alla som faktoriserar N att få den privata nyckeln . Varje C kan sedan dekrypteras med den privata nyckeln.
Precis som det inte finns några bevis för att heltalsfaktorisering är beräkningssvårt, finns det heller inga bevis för att RSA-problemet är lika svårt. Med ovanstående metod är RSA-problemet minst lika enkelt som att faktorisera, men det kan mycket väl vara lättare. Det finns faktiskt starka bevis som pekar på denna slutsats: att en metod för att bryta RSA-metoden inte nödvändigtvis kan omvandlas till en metod för att faktorisera stora semiprimtal. Detta är kanske lättast att se genom att faktoriseringsmetoden är överdriven: RSA-problemet ber oss att dekryptera en godtycklig chiffertext, medan factoringmetoden avslöjar den privata nyckeln: på så sätt dekrypterar alla godtyckliga chiffertexter, och den gör det också möjligt för en att utföra godtycklig RSA privata nyckelkrypteringar. På samma sätt är att hitta dekrypteringsexponenten d faktiskt beräkningsmässigt ekvivalent med factoring N , även om RSA-problemet inte kräver d .
Utöver RSA-problemet har RSA också en speciell matematisk struktur som potentiellt kan utnyttjas utan att lösa RSA-problemet direkt. För att uppnå RSA-problemets fulla styrka måste ett RSA-baserat kryptosystem också använda ett utfyllnadsschema som OAEP , för att skydda mot sådana strukturella problem i RSA.
Se även
- Starkt RSA-antagande
- RSA Factoring Challenge
- Rabin kryptosystem , vars motsvarighet till factoring är känd
Vidare läsning
- Att bryta RSA kan vara lika svårt som factoring , D. Brown, 2005. Detta icke refererade förtryck påstår att det är lika svårt att lösa RSA-problemet med ett rakt linjeprogram som factoring, förutsatt att e har en liten faktor.
- Breaking RSA Generically is Equivalent to Factoring , D. Aggarwal och U. Maurer, 2008. Detta Eurocrypt 2009-papper (länken är till en förtryckt version) bevisar att det är lika svårt att lösa RSA-problemet med en generisk ringalgoritm som factoring.
- When e-th Roots Become Easier Than Factoring , Antoine Joux , David Naccache och Emmanuel Thomé, 2007. Denna Asiacrypt 2007-tidning (länken är till en förtryckt version) bevisar att lösa RSA-problemet med hjälp av ett orakel till vissa andra specialfall av RSA-problem är lättare än factoring.
