Faktoriseringsalgoritmer och Kryptografi

Examensarbete för kandidatexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/257398
Download file(s):
File Description SizeFormat 
257398.pdfFulltext1.04 MBAdobe PDFView/Open
Type: Examensarbete för kandidatexamen
Bachelor Thesis
Title: Faktoriseringsalgoritmer och Kryptografi
Authors: Elinder, David
Lindström, Eric
Schälin, Alexander
Strömstedt, Mikael
Sundqvist, Lukas
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.
Keywords: Matematik;Mathematics
Issue Date: 2019
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
Chalmers University of Technology / Department of Mathematical Sciences
URI: https://hdl.handle.net/20.500.12380/257398
Collection:Examensarbeten för kandidatexamen // Bachelor Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.