Generiranje močnih praštevil

diplomsko delo

Andrej Gorjan (Avtor), Aleksandar Jurišić (Mentor)

Povzetek

Eden od temeljev kriptografije je teorija števil. Kot osnovni gradniki imajo v njej osrednji pomen praštevila in se posledično uporabljajo v mnogih šifrirnih algoritmih. To seveda pomeni, da morajo ti algoritmi imeti dostop do naključnih praštevil. Pri izbiri moramo biti pazljivi, saj nam kitajski izrek o ostankih pri določenih praštevilih omogoča učinkovit izračun tajnih ključev. Takšne napade lahko preprečimo z uporabo "močnih" praštevil. Ko jih vpeljemo, predstavimo dva algoritma za generiranje močnih praštevil in dokažemo njuno pravilnost ter izpeljemo njuno časovno zahtevnost. Algoritma potrebujeta naključna praštevila, zato nadaljujemo z analizo generatorja naključnih števil na osnovi LFSR. Kot gradnik ga lahko uporabimo v generatorju CCSR, na podoben način pa deluje tudi dober moderni generator Mersenne Twister. Zatem se na kratko posvetimo še testom praštevilskosti, kjer se osredotočimo na probabilistične teste. Na koncu sestavne dele združimo v algoritem, ki lahko generira naključna močna praštevila in predstavimo rezultate testiranja za kvaliteto naključnih števil ter hitrost delovanja generatorja.

Ključne besede

kriptografija;kitajski izrek o ostankih;praštevila;generator naključnih števil;testi praštevilskosti;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[A. Gorjan]
UDK:	004:511(043.2)
COBISS:	29035011
Št. ogledov:	1234
Št. prenosov:	123
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Generating strong primes
Sekundarni povzetek:	One of the foundations of cryptography is number theory. As building blocks, primes are central to the field and are used in many cryptographic algorithms. Of course, this means these algorithms require access to random prime numbers. When choosing them, we must be careful as certain primes allow for the Chinese remainder theorem to be used to efficiently compute our secret keys. These attacks can be prevented by using so called "strong" primes. We study them and present two algorithms for generating such numbers. We prove their correctness and determine their time complexity. Since these algorithms use random primes, we continue with an analysis of LFSR based random number generators. These can be used as building blocks in the CCSR generator and similar ideas are used by the Mersenne Twister generator. After this, we briefly discuss primality tests, focusing on probabilistic tests. These components are then combined into a efficient random strong prime number generator. Finally, the quality and speed of the generator are tested and the results are presented.
Sekundarne ključne besede:	cryptography;Chinese remainder theorem;prime numbers;random number generator;primality tests;computer and information science;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	74 str.
ID:	12029429