Department of Mathematical Sciences / Institutionen för matematiska vetenskaper

Permanent URI for this communityhttps://gupea-staging.ub.gu.se/handle/2077/28886

Browse

Browsing Department of Mathematical Sciences / Institutionen för matematiska vetenskaper by Author "Alexander Schälin"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Faktoriseringsalgoritmer och Kryptografi
    (2019-07-01) David Elinder; Eric Lindström; Alexander Schälin; Mikael Strömstedt; Lukas Sundqvist; University of Gothenburg/Department of Mathematical Science; Göteborgs universitet/Institutionen för matematiska vetenskaper
    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.