Teorie čísel, algebraické struktury

Question 1

Teorie čísel

Answer 1

Teorie čísel je část matematiky zkoumající vlastnosti (zejména) celých čísel. Prvočíslo je 𝑝 ≥ 2, které nemá jiné dělitele než triviální. Každé celé číslo ≥ 2 je buď prvočíslo nebo se dá zapsat jako součin prvočísel. Pokud číslo není prvočíslo, nazýváme ho číslem složeným.
Tento obor má velmi širokou aplikaci v kryptografii, protože mnoho kryptografických algoritmů a protokolů je založeno na některých základních výsledcích a technikách teorie čísel. Teorie čísel využívá matematické struktury, které umožňují bezpečné šifrování, digitální podpisy, šifrovací klíče, a ověřování identity.

Question 2

Eulerova Funkce

Answer 2

Eulerova funkce, označovaná jako ϕ(n)je funkce, která pro dané přirozené číslo 𝑛 n určuje počet čísel menších než 𝑛 n, která jsou s ním nesoudělná (to znamená, že jejich největší společný dělitel greatest common divisor, GCD, je 1).
Pro konkrétní číslo 𝑛 n se tato funkce používá k určení počtu čísel, která mají s 𝑛 n společného dělitele pouze číslo 1.
Eulerova funkce se široce používá v kryptografii, především při práci s RSA algoritmem. V RSA se používá pro výpočet soukromého klíče.

Question 3

Grupa

Answer 3

V kryptografii jsou grupy základní matematickou strukturou, která se používá k vytváření bezpečných šifrovacích algoritmů. Matematická struktura “grupa” je soubor prvků, které splňují čtyři základní vlastnosti: uzavřenost, asociativnost, existenci neutrálního prvku a existence inverzního prvku.
Grupy jsou klíčové pro pochopení některých základních kryptografických algoritmů, jako je Diffie-Hellman nebo algoritmy založené na elliptických křivkách.

Question 4

Vlastnosti grupy - uzavřenost, asociativnost, existenci neutrálního prvku a existence inverzního prvku.

Answer 4

Uzavřenost - Když provedeme operaci mezi jakýmikoli dvěma prvky skupiny, výsledek bude stále v rámci téže skupiny.

Asociativita - Znamená, že pořadí, ve kterém provádíme operace, nemá vliv na výsledek, pokud se operace vykonávají na stejných prvcích.

Existence Neutrálního Prvku - Neutrální prvek e∈G je prvek, který při aplikaci operace na libovolný prvek a ∈ G nezmění jeho hodnotu. Tento prvek je v podstatě “neviditelný” pro operace, protože neovlivňuje výsledek, když se použije.

Existence Inverzního Prvku - Pro každý prvek a∈G existuje prvek
b∈G, který je inverzní k a v rámci operace. To znamená, že když operujeme a s jeho inverzním prvkem b, výsledek je neutrální prvek e.

Question 5

Cykličnost grupy a řád generátoru grupy

Answer 5

Grupa 𝐺 se nazývá cyklická, pokud existuje prvek 𝑔∈𝐺 (nazývaný generátor), takový, že každý prvek a∈G lze napsat jako mocnina 𝑔

Řád prvku 𝑎 je definován jako nejmenší kladné celé číslo 𝑡 takové že 𝑎 𝑡 = 1 pokud takové 𝑡 existuje.
Řád generátoru grupy se rovná řádu grupy.

Question 6

Volba parametrů grupy pro algoritmy založené na problému DL

Answer 6

Dostatečně velké prvočíslo - Alespoň 2048 bitů
Řád grupy - g^q =1 (mod 𝑝). kde q alespoň 160bitů
Volba generátoru
Generování Soukromého klíče x, x<q
Zveřejnění veřejného klíče y, y≡ 𝑔^𝑥 mod 𝑝.