Alkulukujen arpominen nykyaikaisissa ohjelmistokirjastoissa

No Thumbnail Available

Files

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.

Date

2024-05-08

Department

Major/Subject

Tietotekniikka

Mcode

SCI3027

Degree programme

Teknistieteellinen kandidaattiohjelma

Language

fi

Pages

29

Series

Abstract

Tässä työssä tutkin nykyaikaisten avoimen lähdekoodin ohjelmistokirjastojen menetelmiä arpoa satunnaisia alkulukuja. Työssä tutkitaan alkulukujen arpomiseen käytettyjä algoritmeja ja niiden toimintaa. Työssä ei kuitenkaan keskitytä analysoimaan satunnaislukujen arvontaan käytettyjä menetelmiä eikä tutkittavia kirjastoja pinnallista yleiskuvaa tarkemmin. Pääasiallisina lähteinä käytetään kirjastojen lähdekoodien tiedostohakemistoja ja aiheeseen liittyvää kirjallisuutta. Tutkimuksessa perehdytään syvemmin OpenSSL-kryptografiakirjastoon ja SymPy-matematiikkakirjastoon. Työssä käsitellään myös pinnallisemmalla tasolla NSS-kryptografiakirjastoa ja Javan BigInteger-luokan toimintaa OpenJDK:n toteutuksessa. Algoritmeja selitetään pseudokoodin ja matematiikan avulla. Tutkimuksessa havaittiin, että alkulukujen arpomiseen käytettävät menetelmät ovat melko vakiintuneita. Pieniä alukulukuja arvottaessa käytetään usein jotain yksinkertaista algoritmia, jolla seulotaan alkulukukandidaatteja. Suurempia alkulukuja arvottaessa käytetään probabilistisia menetelmiä, kuten Millerin-Rabinin alkulukutestiä tai Lucasin alkulukutestiä. Tässä työssä perehdytään näiden algoritmien toimintaan tarkemmin. Kirjastojen menetelmistä voidaan huomata selkeitä eroja niiden käyttökohteen mukaan. Kryptografiakirjastot oletusarvoisesti keskittyvät erittäin suurien alkulukujen arvontaan, kun taas muissa kirjastoissa on enemmän huomioitu myös pienempiä alkulukuja. Molemmat kryptografiakirjastot myös käyttävät menetelmistä selvästi eniten tutkittua Millerin-Rabinin alkulukutestiä, kun taas muut kirjastot käyttävät vähemmän standardeja menetelmiä.

Description

Supervisor

Savioja, Lauri

Thesis advisor

Lievonen, Henrik

Keywords

alkuluvut, kryptografia, alkulukutestaus, ohjelmistokirjastot

Other note

Citation