4. Lekcija

4.lekcija kursā

“Datu aizsardzība un kriptogrāfija”

Lineāras kongruences.

Iepriekšējā lekcijā pārliecinājāmies, ka var atrast tādu x, a * x 1 (mod p); Tagad ķersimies klāt pie mazliet grūtāka uzdevuma: 17 * x 32 (mod 53)

Lai tādu atrisinātu, rīkosimies sekojoši: 17 * y * x 32 * y (mod 53)

Atrod y, ka 32 * y 1 (mod 53)
Atrod x, ka 17 * y * x 1 (mod 53)

32 * y 1 (mod 53), Pēc P. Fermā mazas teorēmas
y = 32⁵¹

Bet ko varētu darīt, ja 17 * x 32 * (mod 53 * 37) ?
Mūs varētu interesēt Eilera funkcijas rēķināšana:

S(53 * 37) = ?

|| Izsvītro visus tos skaitļus, kas nav savstarpēji pirmskaitļi ar 37. Palikušo vienību
|| summa arī ir Eilera funkcijas rezultāts.

1 2 3 4 5 … 36 37 38 … 52 53 54 … 1961

Ko svītrosim? Apskatīsim arī vispārīgo uzdevumu :

S(p * q) = ?

Izsvītrosim visus 37 daudzkārtņus;
Izsvītrosim visus 53 daudzkārtņus;

1961 ir 37 un 53 kopīgais daudzkārtnis.
S(p * q) = p * q – q – p + 1 = (p-1) * (q-1) // p * q – kopējais vienību (skaiļu) skaits

T. _ Ja p ir pirmskaitlis, a >= 1 (Naturāls skaitlis), tad S(p^a) = (p^a-1) * (p-1)

T. _ Ja p un q ir dažādi pirmskaitļi, a, b – patvaļīgi naturāli skaitļi, tad
S(p^a* p^b) = S(p^a) * S(q^b)

T. Ja m = p1^a1 * p2^a2 * … * ps^as ir kanonisks izvirzījums pirmskaitļu
reizinājumā, tad S(m) = p1^a1-1 * p2^a2-1 * … * ps^as-1 * (p1-1) * (p2-1) *…* (ps-1)

Kriptogrāfijas sistēma – RSA;
Autori: Rivest, Shamir, Adleman

Pašlaik šī ir pati populārākā kriptogrāfijas sistēma pasaulē.
Kā piemēru varētu minēt: Viesnīcas pasūtīšanu izmantojot Internet.


Ideja:

Ņem divus dažādus pirmskaitļus p, q

Apzīmē: n = p * q un S(n) = (p-1)*(q-1)

Izvēlas: lielu gadījumskaitli d > 1, tādu, ka (d, S(n)) = 1 un izrēķina tādu e
(1<e<S(n)), ka e * d 1 (mod S(n))

Ja šifrējamais teksts ir W, tad nošifrētais teksts ir :
c = W^e (mod n)

Lai legālais saņēmējs to atšifrētu, pietiek izrēķināt :
W = c^d (mod n)

Kas šeit ir/nav slepens ?
Teksts italic stilā(zils) - nav slepens.
Teksts bold stilā(sarkans) - ir slepens !!!

Piemērs:
p = 37 n = 37 * 101 = 3737
q = 101 S(n) = 36 * 100 = 3600

izvēlas d = 7
7 * e = 1 (mod 3600)
||Tā kā 3600 nav pirmskaitlis, tad e = 7^S(3600)-1 = ?

3600 = 2⁴ * 3² * 5²

Pēc T.
S(3600) = 2³ * 3 * 5 * 1 * 2 * 4 = 24 * 5 * 8 = 960
7⁹⁵⁹ = ?