Faktoriseringsalgoritmer och Kryptografi

Abstract

I detta arbete behandlas olika kryptosystem, de underliggande matematiska problem som håller kryptosystemen säkra och de algoritmer som löser dessa problem. De kryptosystem som behandlas är ElGamal och RSA. De underliggande problemen som behöver lösas för att knäcka kryptosystemen är diskreta logaritmproblemet för ElGamal och faktorisering av stora tal för RSA. De lösningsalgoritmer vi diskuterar för att lösa det diskreta logaritmproblemet är en direkt metod och Shanks babystep-giantstep algoritm. För att faktorisera stora tal använder vi en direkt metod, Pollards rho-algoritm, Fermats algoritm, Dixons algoritm, Kedjebråksmetoden och Kvadratiskt såll. Vi analyserar även algoritmer för primtalstest vilka är viktiga för RSA kryptering. De algoritmer för primtalstest som behandlas är en direkt metod, Solovay- Strassens test och Miller-Rabins test. Det resultat vi fick var att dessa kryptosystem kan anses säkra eftersom de på kort tid kan kryptera tal av storleken 101000 och lösningsalgoritmerna med våra implementationer inte kan faktorisera tal av storlek 10100 inom rimlig tid. Vi beskriver också en kvantalgoritm, vid namn Shors algoritm, som skulle kunna vara ett framtida hot mot dessa system. Detta ses dock inte som ett problem idag då det än så länge inte finns några tillräckligt kraftfulla kvantdatorer som kan implementera algoritmen på en tillräckligt omfattande skala.