Generiranje močnih praštevil

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2020
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[A. Gorjan]
UDC:	004:511(043.2)
COBISS:	29035011
Views:	1234
Downloads:	123
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Generating strong primes
Secondary abstract:	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.
Secondary keywords:	cryptography;Chinese remainder theorem;prime numbers;random number generator;primality tests;computer and information science;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	74 str.
ID:	12029429