Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию
Подождите немного. Документ загружается.
(K, A, S)
• K
• A
• S
K = Σ
m
m Σ
m
A = Γ
k
k Γ
α ∈ S E
α
K A E
α
(x)
x ∈ K E
−1
α
(c)
c ∈ A E
−1
α
E
α
D
α
• E
α
D
α
• α x
E
α
(x)
CAESAR K
A
26 S
{0, 1, 2, . . . , 25 } k ∈ S
k
k = 3
CRYPTOGRAPHYISFASCINATING,
FUBSWRJUDSKBLVIDVFLQDWLQJ.
k
2
3
K A
1
4
CAESAR
CAESAR
{0, 1, . . . , 25}
m
m
α = α
1
, α
2
, . . . , α
m
m i
α
i
α = 3, 1, 6
C R Y P T O G R A P H Y
3 1 6 3 1 6 3 1 6 3 1 6
F S E S U U J S G S I E.
5
K A m
6
f
f
f
−1
f
−1
f
f
f
f
f(x)
f f
−1
f
14
7
f
−1
8
Σ Γ f : Σ
∗
→ Γ
∗
• c, d ∈ IN
0
x ∈ Σ
∗
1
c
·|x| ≤ |f(x)| ≤ d · |x|.
|x| |f(x)|
• f
• A
k ∈ IN n
A,k
n ≥ n
A,k
w ∈ Σ
n
A(f(w)) = w n
−k
f
−1
9
14
10
11
A
w
12
f
−1
• f (x, y) = x · y
f
n
•
f(x) = a
x
mod n
a
x
≡ b mod n a
b n
RSA
p q
n = p ·q ϕ(n) = (p − 1) · (q − 1).
ϕ
n ϕ(n) a
1, 2, . . . , n − 1 (a, n) = 1
d > 1
(d, ϕ(n)) = 1.
d
e e
e · d mod ϕ(n) = 1.
n e p q ϕ(n) d
p q d
13
f
−1
14
NP
15
RSA
16
17
n
dlog
10
ne−1
w ∈ {0, 1, . . . , n − 1}
E
e,n
(w) = w
e
mod n.
c
D
d,n
(c) = c
d
mod n.
E
e,n
D
d,n
d (d, ϕ(n)) = 1
d ϕ(n)
d
ϕ(n) d
e
RSA
p q ϕ(n) d (e, n)
RSA
x
E
e,n
(x) (e, n)
RSA
w < n
D
d,n
(E
e,n
(w)) = w.
D
d,n
E
e,n
{0, 1, . . . , n −1}
w n
(w, n) = 1
ϕ(n) =
{a ∈ {1, 2, . . . , n} |
(a, n) = 1}
n
w
ϕ(n)
mod n = 1.
(Z/(n))
∗
ϕ(n)
w ∈
(Z/(n))
∗
k
w
k
mod n = 1.
b
ϕ(n) = k ·b,
w
ϕ(n)
mod n = w
k·b
mod n
= (w
k
mod n )
b
mod n
= (1)
b
mod n = 1.
x
1
, x
2
, . . . , x
ϕ(n)
∈ {1, 2, . . . , n − 1} x
i
(x
i
, n) = 1 a ∈ {1, 2, . . . , n − 1}
(ax
1
mod n, ax
2
mod n, . . . , ax
ϕ(n)
mod n)
x
1
, x
2
, . . . , x
ϕ(n)
RSA
p q n e d
RSA w < n
D
d,n
(E
e,n
(w)) = w
ed
mod n = w.
d e
e · d = j · ϕ(n) + 1
j ∈ IN w < n
w
j·ϕ(n)+1
mod n = w.
p q w
• p q w
p q w w < p · q
(p · q, w) = 1.
n = p · q w
w
ϕ(n)
mod n = 1
w
jϕ(n)
mod n = 1.
w
• p q w
p w w
q
w
q−1
mod q = 1,
w
(q−1)·( p−1)
mod q = 1, w
ϕ(n)
mod q = 1.
w
jϕ(n)
mod q = 1.
p w
n = p · q
w
jϕ(n)
mod n = 1.
w
• p q w
p q p · q > w
ut
K
B K B
18
ϕ(q) = q −1
q
19
B
K K
K B
F
K B
K B
K
B
K
B K
B
K
E
K
D
K
B E
K
K 2
K D
K
(w) w (w, D
K
(w)) B
B w = E
K
(D
K
(w))
E
K
K D
K
(w) B
K w E
K
B
K w B (w, D
K
(w))
E
K
(w, D
K
(w))
u D
K
(u)
w
w
K B
w
20
E
K
K
0
0
K B B
B K
B (w, D
K
(w))
K
K B
(w, D
K
(w)) K
E
K
(w, D
K
(w))
K
K (D
K
, E
K
)
B (D
B
, E
B
)
E
K
E
B
B K D
K
K D
B
B
K 3
B w E
K
(w)
K
K w = D
K
(E
K
(w)) K
c = E
B
(D
K
(w)) B
B
w = E
K
(D
B
(c)) = E
K
(D
B
(E
B
(D
K
(w)))).
3 B
K K
21 0
B
22
w = D
K
(E
K
(w)) = E
K
(D
K
(w)) w = D
B
(E
B
(w)) = E
B
(D
B
(w)).