wyklad 06, AGH, WFiIS, Informatyka stosowana, Semestr I, matma dyskretna-misztal, wyklad
[ Pobierz całość w formacie PDF ]
AlgorytmRSA
c
2005, 2010 by M. J. Golin, G. Trippen”
na podstawie ”Slides
Wykład6
17 kwietnia 2012
(Wykład6)
AlgorytmRSA
17kwietnia2012 1/23
Outline
1
Wprowadzenie
2
Pot¦gowanie modularne
3
Małe twierdzenie Fermata
4
Algorytm RSA
5
Chi«skie twierdzenie o resztach
(Wykład6)
AlgorytmRSA
17kwietnia2012 2/23
Wprowadzenie
Funkcja ró»nowarto±ciowa
f:X
!
Y
jest funkcj¡ jednokierunkow¡,
je»eli znajomo±¢ warto±ci
f(x)
nie daje wystarczaj¡cej informacji by
wydajnie obliczy¢
x
.
Definicja funkcji jednokierunkowej jest dosy¢ ogólna. Je»eli
f
jest
ró»nowarto±ciowa to odwrotno±¢
g
funkcji
f
taka, »e
g
(
f
(
x
))=
x
zawsze istnieje.
Wiedza o istnieniu funkcji
g
, nie zawsze wystarcza do obliczenia
g(u)
.
Dla danego
u
,
g(u)
moze okaza¢ si¦ trudne do wyznaczenia.
Kryptografia z kluczem publicznym.
Publiczna funkcja koduj¡ca
P
B
musi by¢ ró»nowarto±ciowa.
Tajna funkcja dekoduj¡ca
S
B
, jest wydajnym sposobem obliczenia
odwrotno±ci
P
B
.
Wydajny sposób obliczania odwrotno±ci
S
B
jest tylko dost¦pny dla
wła±ciciela, który skonstruował
P
B
.
(Wykład6)
AlgorytmRSA
17kwietnia2012 3/23
Pot¦gowaniemodularne
Z lematu (2.3): je»eli
a
2
Z
n
, wtedy
a
j
modn
=
a
n
a
n
n
a
| {z }
j
czynników
.
a
j
modn
jest w
Z
n
iloczynem
j
czynników, z których ka»dy jest równy
a
.
Lemat(2.19)
Dlaka»dego
a2Z
n
idladowolnychnieujemnychliczbcałkowitych
i
,
j
1
(
a
i
modn
)
n
(
a
j
modn
)=
a
i+j
modn
2
(a
i
modn)
j
modn=a
ij
modn
Przykład
3
2
= 9
,
3
2
mod7=2
3
4
= 81
,
3
4
mod7=4
3
6
=729
,
3
6
mod7=1
3
8
=6561
,
3
8
mod7=2
(3
2
mod7)
7
(3
4
mod7)=3
6
mod7=1
(3
4
mod7)
2
mod7=3
8
mod7=16mod7=2
(Wykład6)
AlgorytmRSA
17kwietnia2012 4/23
Pot¦gowaniemodularne
Lemat(2.20)
Niech
p
b¦dzieliczb¡pierwsz¡.Dlaka»dejniezerowejliczby
a
2
Z
p
,
funkcja
f
a
(x)=x
p
a
jestfunkcj¡ró»nowarto±ciow¡.Wszczególno±ci,
liczby
1
p
a,2
p
a,...,(p1)
p
a
,s¡permutacj¡zbioru
f1,2,...,p1g
.
Dowód.
Zało»enie.
f
a
(x)
nie jest ró»nowarto±ciowa. Zatem dla
x6=y
f
a
(x)=f
a
(y)
.
Skoro
p
jest liczb¡ pierwsz¡, to Wniosek (2.17) mówi nam, »e istnieje
a
1
2Z
p
taka, »e
a
p
a
1
=1
.
Pomnó»my
f
a
(
x
)=
x
p
a
obustronnie przez
a
1
.
x=(x
p
a)
p
a
1
=f
a
(x)
p
a
1
=
f
a
(
y
)
p
a
1
=(
y
p
a
)
p
a
1
=
y
Sprzeczno±¢
f
a
(x)
jest ró»nowarto±ciowa.
(Wykład6)
AlgorytmRSA
17kwietnia2012 5/23
[ Pobierz całość w formacie PDF ]