Faktoriseringsalgoritmer och Kryptografi

Detta är en Kandidat-uppsats från Göteborgs universitet/Institutionen för matematiska vetenskaper

Sammanfattning: I detta arbete behandlas olika kryptosystem, de underliggande matematiska problem somhåller kryptosystemen säkra och de algoritmer som löser dessa problem. De kryptosystem sombehandlas är ElGamal och RSA. De underliggande problemen som behöver lösas för att knäckakryptosystemen är diskreta logaritmproblemet för ElGamal och faktorisering av stora tal förRSA. De lösningsalgoritmer vi diskuterar för att lösa det diskreta logaritmproblemet är endirekt metod och Shanks babystep-giantstep algoritm. För att faktorisera stora tal användervi en direkt metod, Pollards rho-algoritm, Fermats algoritm, Dixons algoritm, Kedjebråksmetodenoch Kvadratiskt såll. Vi analyserar även algoritmer för primtalstest vilka är viktiga förRSA 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 ansessäkra eftersom de på kort tid kan kryptera tal av storleken 101000 och lösningsalgoritmernamed våra implementationer inte kan faktorisera tal av storlek 10100 inom rimlig tid. Vi beskriverockså en kvantalgoritm, vid namn Shors algoritm, som skulle kunna vara ett framtidahot mot dessa system. Detta ses dock inte som ett problem idag då det än så länge inte finnsnågra tillräckligt kraftfulla kvantdatorer som kan implementera algoritmen på en tillräckligtomfattande skala.

  HÄR KAN DU HÄMTA UPPSATSEN I FULLTEXT. (följ länken till nästa sida)