Kryptografia

Zajęcia 3

q losujemy i sprawdzamy czy p to liczba pierwsza

p = 2q + 1

losujemy p-1 -> liczba pierwsza
znajdujemy pewne g : <g> = fi(p)
losujemy 1 < x < p-1
obliczamy y = q
KA = (p, q, y) -> klucz publiczny
ka = (p, x) -> klucz tajny

losujemy 1 < k < p
obliczamy c1 = q^k (mod p)
obliczamy c2 = m * y^k (mod p)

deszyfrowanie było na mini-projekcie 1

Zajecia2

Twierdzenie Fermata

Małe twierdzenie Fermata mówi, że jeśli p jest liczbą pierwszą i a nie dzieli się przez p, to:

a ^ (p-1) === 1 (mod p)

Przystawanie modulo link Przykład dla p = 13:

a^12 - 1 = k * 13
k - całkowite
(3^12 -1 / 13) = k
k = 40880
k jest całkowite więc spełnia twierdzenie Fermata.

Test pierwszości Fermata

Link, ogólniej link
a losujemy z zakresu od 1 do p - jeśli a nie będzie względnie pierwsze z p to znaczy że p nie jest liczbą pierwszą.

Reszta kwadratowa modulo

Link, przykład twierdzenie jest w materiałach na Teams.