W8_Kodowanie i Kryptografia_Algorytmy niesymetryczne_1g.pdf

(422 KB) Pobierz
Microsoft PowerPoint - W8_Kodowanie i Kryptografia_Algorytmy niesymetryczne_1g.ppt
Kryptografia
Algorytmy niesymetryczne
dr Robert Borowiec
Politechnika WrocĀawska
Instytut Telekomunikacji i Akustyki
pokj 909, C-5
tel. 71 3203083
e-mail: Robert.Borowiec@pwr.wroc.pl
Wykþad
1-godzina
Przypomnienie
Obliczanie odwrotnońci liczby
¤ Podane przez Eulera uoglnienie Fermata
dostarcza algorytmu do rozwiĢzania rwnania
, gdy NWD(a,n)=1.
RozwiĢzanie to ma postaę:
( ) 1
a
µ n
x
mod =
x
=
a
f
( )
n
-
mod
n
JeŇeli n jest liczba pierwszĢ, to:
x
=
a
( )
-
1
-
1
mod
n
=
a
n
-
2
mod
n
G
Kody korekcyjne i kryptografia
1
n
317372540.005.png
Algorytmy niesymetryczne
Tekst
jawny
Szyfrogram
Szyfrator
Tekst
jawny
Szyfrogram
Deszyfrator
Algorytmy niesymetryczne
¤ Algorytmy niesymetryczne charakteryzujĢ siħ tym,
Ňe klucz szyfrujĢcy rŇni siħ od klucza
deszyfrujĢcego
¤ Nie kaŇdy algorytm niesymetryczny nadaje siħ do
implementacji jako system klucza jawnego, gdyŇ
ujawnienie jednego z kluczy pociĢga za sobĢ
moŇliwoĻę znalezienia drugiego klucza
¤ Systemy niesymetryczne wykorzystywane sĢ
rwnieŇ do podpisw cyfrowych oraz procedury
wymiany klucza kryptograficznego
Kody korekcyjne i kryptografia
2
317372540.006.png 317372540.007.png 317372540.008.png 317372540.001.png
Bezpieczeĺstwo algorytmw niesymetrycznych
¤ Bezpieczeıstwo szyfrw niesymetrycznych opiera
siħ na trudnoĻci rozwiĢzania jednego z trzech
problemw trudnych obliczeniowo (NP-
zupeþnych):
Î faktoryzacji duŇych liczb
Î obliczaniu logarytmw dyskretnych w ciele
skoıczonym
Î pierwiastkowania liczb w ciele skoıczonym
Î problemie plecakowym
Algorytmy niesymetryczne
¤ Diffiego Hellmana
¤ RSA Rivesta-Shamira-Adlemana
¤ Poligha-Hellmana
¤ Rabina
¤ Algorytmy plecakowe
¤ i wiele innych
Kody korekcyjne i kryptografia
3
317372540.002.png
Szyfry potİgowe
(Hellmana, RSA)
Szyfry potħgowe dokonujĢ szyfrowania na bloku tekstu jawnego
M¬[0, n-1] poprzez wykonanie odpowiednio potħgowania
C=M e mod n
(1)
M=C d mod n
(2)
JeŇeli NWD(M, n)=1 oraz e i d speþniajĢ rwnanie
eßd mod f(n)=1
to rwnanie (2) jest odwrotnoĻciĢ rwnania (1), a wiħc:
C=M e mod n ¼ M= C d mod n
Szyfry potİgowe
(Hellmana, RSA)
Do obliczenia d przy wybranym e, ktre speþniajĢ rwnanie
e f
µ
d
mod =
( ) 1
stosowana jest zaleŇnoĻę
( )
( )
d
=
e
f
f
n
-
mod
f
n
,z ktrej w oglnym przypadku trudno wyznaczyę d z uwagi na
brak wartoĻci funkcji Eulera. JeŇeli natomiast n jest liczbĢ
pierwszĢ to rwnanie przybiera postaę
e
µ n
mod =
( ) 1
-
1
i moŇna je rozwiĢzaę bez znajomoĻci funkcji Eulera za pomocĢ
rozszerzonego algorytmu Euklidesa:
Kody korekcyjne i kryptografia
4
n
d
317372540.003.png
Poszukiwanie liczby odwrotnej
Rwnanie
( ) 1
a
µ n
x
mod =
jest rwnowaŇne rwnaniu:
a
µ
x
=
y
+
d
=
1
,
gdzie
d
-
reszta
z
dzielenia
n
n
ktre po wymnoŇeniu stronami moŇna przedstawię:
a
µ y
x
+
n
µ
=
1
Rozszerzony algorytm Euklidesa
Rozszerzony algorytm Euklidesa sþuŇy do obliczania
odwrotnoĻci multiplikatywnej w ciele skoıczonym .
1. Algorytm ten wyznacza liczby x i y takie , Ňe
a
µ
x
+
n
µ
y
=
d
,
gdzie
d
=
NWD
( )
,
n
2. JeŇeli z obliczeı d>1 to liczba a -1 mod n nie istnieje.
Gdy d=1, to x jest odwrotnoĻciĢ liczby a.
Kody korekcyjne i kryptografia
5
a
317372540.004.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin