978-5-4439-0026-1 Введение в криптографию Под общ. ред. В.В.Ященко


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.

ٲ..
,

޼ƽ
2012
ô003.26
32.973
-
18.2
24
:..(,1,

-
ղ),..(2,3,ղ),..
-
(4),..(5),..,
..
-
,..(6),..,..
,
..,..(7),..(
-
ձ).
24


/
.....

4
-

.,..:ƽ,2012.

348.
ISBN978
-
5
-
4439
-
0026
-
1




.



-


,
.

.
,
-

-
.
32.973
-
18.2
ISBN978
-
5
-
4439
-
0026
-
1

,2012

ƽ,2012

....................................5
1.

9
1...................................9
2...........................10
3..........................17
4.............................20
5.................................26
2.

27
1...................................27
2.P
=
NP....................30
3..........................32
4.......................3
4
5...............
..37
...................................42
3.

44
1...................................44
2..
..47
3...............
..63
4.



.......70
5.......................75
6.



.............78
7..

-
..............................84
8.............................86
...................................87
4.

89
1...................................89
2.RSA........................91
3.
-
..............94
4..............
..100
4

5...................1
02
6...............
.106
7.........
..113
8......................1
16
9.................................122
...................................122
5.

124
1...................................124
2..
......126
3.......................1
29
4..............
..131
...................................134
6.

136
1...............................136
2...............................138
3.?.........................146
4........................159
5.............................169
...................................170
7.

171
1...................................172
2...............................175
3............................189
4...
...198
5....
....206
6............................221
...................................259
հ.
غ.




261
ձ.

-

298
ղ.

304
...........
...341
............
..345


:
.

.3Ҽƽ,





.
ݰ.
,,
,
.

,,

.


.


-



-
ؼ¸.,

-
,ѳ:..




.



.



-


.

.


-
.




-


.

2012

.

.




(,

-
..),,
.


-
,,

.
1999

2000.
:

-
6070000(

6

),


-
051319.

-
...2000.








-


.




.


,

.




,,


-
,

-
.
-

-


.
༳,


.

.


2000

.

7

,

-
.
C
1999

.

.






,


.

-


-
,,.

.




.




-
,,,..


.



,

-
:
,
.,




-
.

.
?
?

-
??

.

-
.
(





;,
,
)


.
.
.

-
(1

..
-
,..,

25

,.:͸,1994;1,2,
4,5





,,2,
.:ƽ,1998;7





(
8





),4,1998).
-

.


-
.(

)

-
.1



,


:,,,
,
.

-
,.2,3,4,5

-
,

.6

.7

,,

-
,.
:

-
,,

;


.

-
޺
.





-
1945.,1948.,

1963.




(1963.).,
غ.




.
-
.




-
(

).,


,
,,,
.






м..,
޽..,в..,޲..,.:ĸ
,1997.

1998

.

.

1

1.


?
(



¿

,..
ٿ-

).,,,

,

.
¿,,

.
1.,

.
2.,
-
.
3.,
,

.
.
1.



.
2.



.

.
,
:
,

-
.


,:

.
10
.1.




:
-

(),
,,

-

,.


-





,.

Ҹ

1
;




,48(225)11997.,.62.
(,

.,

-
,,,

-




.)
3.(

)

-

.

.

(

)


-
,..
(
-

)(

,
-

),.


,,..
-


,.


,

,

,

,

.
2.

?
¿,

.
,

-
,.
,


,

,
1
http://www.geocities.com/SiliconValley/Vista/6001/
2.
11

,

.,
-
:

;

;

;

;

..
,
:


-


,
;



,
,,
.




.
-

:
,..
,

¿,(..1).
AB

.1
AB

;
.


(

),

.

,

.
,

(,.)

.

,(
-
,
,,..)
,
-
.,




,
12
.1.


.

,.,,

-







.
,

-


-
.

,,


.

(

)




.



-
.
,
-

-



-
..
,
-
.


-
,

.

.
,

,

-
.
,
.,

,

.,

:

-

,(




).
:
-
,

-
.
,


-
.

,:
1),
;
2),.
2.
13

-
:,
,
-
.


-
,
.

-
.
,,.
,
.

-

,
.

XX



޺..


-
.

.

1
1967.
(
ݴ
...,
,2000)...
2

-
.


-
.
.


-
л(



).,





,



.
.(1462

1516),
ҳ.1566ڴ.

(

к

).
VI
IV.
..
,




1700,ۿ.
(.)


,,
.





:



.



.ݴ.
.





V..

,
.

1
KahnDavid
.Codebreakers.ThestoryofSecretWriting.NewYork:Macmi
llan,1967.
2

.

.(

-
XVIII

XX.)..,1994.
14
.1.
(),

.(
),

-
().
.
,


-
.
,


.
,



,
-

.
.

:

-
,,..









.,
,

-
.,,
,.
,
,

.
,

-


.





.,

().

,,,
,
.


,
-
.,


-


,


.
,
-
.
,


-
,

,

-
.
,
,



.


,

.


(.1,.199).

-
2.
15



(..2).
,
,,.
AB

ÿ͵
ι
.2
,,

.

-
,

-
.

:,,,

..
,


-
.

.
-

.
(,,.)

,(,)


.

,.


,


.


-


.


.

.
,

-



.,

.(

-
.)





,.
-


.


-
,

-
16
.1.
.

-
,


.


-
,
.
,,,



-
.

,,,

-
,..

:

,
;


-
;

(!)
.



..
ױ(I.):

,
,
-
,,

,.



.



:

,

,
,
-
,...

PGP.(



,481.12.1997,
.45

46):

,,
,


,...


,

-
...




-
.








,
.

,.
3.
17



-
,
-
.

.


,
-
.



-
.

,,,

(
-

)


,


-
.
:

-


,,

,
...
,
,

-
.
3.


-
XXк
.
,
-


,.,,

1948
.



1
.

2




.,



-
,,
,

,

.
,.
,








.ݴ.
,










-
..

X
1
ShannonC
.
E
.Amathematicaltheoryofcommunication
//
BellSystemTechn.J.V.27,
3,1948.P.379

423;V.27,4,1948.P.623

656.
2
..
18
.1.

Y

(
),
.
g
:
X
!
Y


X

Y
.
-
:
1
2
...
n

g
(
1
)
g
(
2
)...
g
(
n
).
,,

-
.





.
-

-
.,,
n




f
1,2,...,
n
g
.
:
1
...
n

-

(1)
...
(
n
)
.
.
.

-

,
,
,
.
ݺ.


-
.
-
,

.
1
.


-
.


,

n
-


n
-
:
i
=
i

k
i
,
i
=
1,...,
n
.

1
...
n

,
k
1
,...,
k
n

,
1
...
n


-
.
,


:
1)()(,
,
,
-

-
);
2);
3).
1
..
3.
19




().
,,

.

,


.
.
۴.:

,,
-
,

,

-

.
.



.
,
-
,

,



.


,

.
,


-
.,,
.
,,

.

:

.

,
?,,,

,,
10
.
,
-



-


.


-


.
:

,
-
;,

,

;
20
.1.


,..

-
;

,;



-
.


:(

-
,)

(
,
).,

:,

,.
4.
1983



..ػ..
-
(



):



,,,,


-


.
.1976

.

ؼ..



1
,
,

.






(.2).


F
:
X
!
Y
,
:
)
F
(
);
)


-

F
(..
F
(
)
=

,
-
..32).
,

-
,,
-

.

.
1

.,
ݼ
.

..
//
¸..67,3,1979.
4.
21


.


.
-

F
:
K

X
!
Y
,:
),

-
(
k
1
,
k
2
),
k
1


K
.
k
2

;
),
k
1

2
X

F
(
k
1
,
);
)

F
(
k
1
,

)
k
1
(
k
2
);
),

-

k
2

F
(
k
1
,

).

,
.

-
,

.)
,
,,

-


.

-
,RSA(

.4).
:
1)

,..

;
2)

-

;
3),

(

.).
,,

,;

-
,,.
,,.1).
A
,
,

-

F
K

K
.
(,)
F
K

.
K

.
B

-

A

2
X
,
=
F
K
(
)


A
.
A

-

K

F
K
,

.
22
.1.

K
)
-



F
K
(
)
.

-

,
F
K

.
-

,:
.

-


:
.(.


-


.)
,

-


-
.

,

-
.
A

-

.,
K
,
,
F
K
(
)
=
,



B

.
B


,
A

.
,,

(
,
),

,


F
K
(
)
=
,
F
K
:
X
!
Y

,
.
F
K

:
1)
,..
F
K
(
)
=
,



K
;,
-
;
2),
,..
F
K
;
3)

;
4)(
,
),,
-
.
,
-



.:

A

B

-
,:
4.
23
1)
A

B
,
()
A

B
,..;
2),

-
,
A

B
,
-

A

B
.

F
(
)
=
x
mod
p
,

p

,

,




GF
(
p
).,
-

x
mod
p
,..,
-
.(
.
-
4.)
,,,


,.

A

B




A

B
..
:
A
=
x
A
mod
p
,
B
=
x
B
mod
p
.
(
p

.)
.
A
,
B


A
,:
x
A
B
mod
p
=
(
x
B
)
x
A
mod
p
.

B
:
x
B
A
mod
p
=
(
x
A
)
x
B
mod
p
.

A

B
,
x
A
x
B
.

A

B
.
,
p
,
,
x
A
,
x
B
,

A

B

x
A
x
B
.
-
,,
,


.
,
-
,

.

-



(.3).
24
.1.


,,,

-
.

-

.,
.

:
,

-

..


,.
,

-
.(

-

-
.)
1..

.,

:,
-
.

-

.
2..

.,
,
,

,.

-

.


-


).
A

B

f
:
X
!
Y
,
:
1)
X

,

-
;
2)
x
1
x
2
2
X
,
f
(
x
1
)
=
f
(
x
2
),
;
3)
f
(
x
)




-

x
.


-

x
2
X
,


x
.
A

,,
B

,.
:
1)
A

x
(



),
x
,.e.
=
f
(
x
),

B
2)
B

,
x

-

A
4.
25
3)
A

B

B
,,

x
4)
B
,
A
,
f
(
x
)

.
3.
A

B
(:
A


,
B

).
A

B
,
A
,
.

-

.
4.,

-
.,,

-
.
,
-
.

,
-



.


1985

1986.





.
-

,
(

.2).
(
P
,
V
,
S
)
-
:
P
()
V
(
-
).
P

V
,
S
.

V
,
P
,
-

S
(
V
).
P

,
V
,
S
,
.



P

V
:
1)



S
,
P


V
;
2)



S
,
P

-

V
,
S
.





-
.
,(
P
,
V
,
S
),

V
.
V
,





P

-

-

S
?
P
,,,
(
P
,
V
,
S
).
26
.1.
(
P
,
V
,
S
),,

-
,1)
2),
:
3)


(
P
,
V
,
S
)

V

S
,
-
,,
S
.
5.


-
..

e
-
mail,:


-
?

.,
,

-




,



(,
-
.).
-



e
-
mail...




...

.
.



.
5.207
1.1.
,



,
,

n

n
(
n

)..
.

(
,
,,)
,
.
,
n
2
,
,

-
.

..


.


n
.
1.2.
:

,,

-
.
1
,
2


2
+
3
+
1.
-

(33
-
)
f
(
)
=
6
+
3
5
+
4
+
3
+
4
2
+
+
4
+
3,
=
1
,
=
2
(
),

.
1.3.
гҽ

.


-
1,2,3,...,,

.

,,

.


.
ҽ

1,3,710(

н).
1
3
.
,

,.
1.4.

a

b
,

d
=
6
-
208.7.

m
=
6930.,

d

m
.
1.5.
:



=

+


+

=

===

+

=

,

,

-
.

-
.
1.6.


.

f
a
,
b
,
c
g
.
-
.
P

Q
=
(
P
).
,,


.
P
1)
(
aP
)
=
P
;
2)
(
bP
)
=
(
P
)
a
(
P
);
3)
(
cP
)
(
P
)
-
.
,
(
P
)
=
P
.
,
bab
,
(
bab
)
=
(
ab
)
a
(
ab
)
=
bab
.,
.
2.1.
,



,
-
,

.,

-
,
.


,,

-
.
,



.,,,
,

.


,
d
,

h
.,,,
.
5.209
2.2.
.



,

.



-
,

10.

:
423461405313
2.3.
,
-


F
(
)
=
=
b
(
3
+
7
2
+
3
+
a
)10,
a
,
b


.
,
a
,
b

(..
).
2.4.
26,
-
,

,.

.


,
.,

-
26.
,

-
,.
2.5.
,



-
..





-

,
30
,
.
,



,
:



210.7.
2.6.

-
:






























1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
,
n
,
K


n
.




-
,

30,.
:

,,
,


,



.
3.1.
,
,
993,

99.
3.2.

A
=
f
a
1
,
a
2
,...
...,
a
n
g
,
n
,
,

.
,
,

A
.


:




























































,


.
,

.
,

?
3.3.

(
-
),
12.

,

,,

,
(),

.B



,,а,

5.211
.ղ:
-

---
-

-
,,

-


.
3.4.

C
1
,
C
2
,...,
C
n
,...,
C
n

n
n
.,
20.
3.5.
,
-
(
-
),
-

:
















01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16














-
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


3.4,


C
k
.


-
.:
2339867216458160670617315588
A
B
C
K
L
N
M
P
Q
.7
3.6.

ABC

,,
M

N


AB

BC
.
,
?
MQ

NL
?
MQ
.
-

Q

AC
,,
?
4.1.
,



,
6

10
.15,

-
6

10
.
212.7.
()
-
(,)

.
,
-
(

):















-



-
-



-



-



-



-











-

-


-
-


-


4.2.

122245321629282201820215102717211216

192275829123122216,192195172982962916:
82191929101929141929291910224211216
1014182117220228291621292862916.
(132),
.

,

,.








.ղ..
4.3.




.

.
09,
10
-
,
.

X

Y

-
,,
X
.
10
-

36

.0,1

-

-
.
4.4.

.

(ZA).

.

-


5.213
,
.
,,

.

OSZJXFXREYOQJSZRAYFJ
,,

-
()

.

.
24:
ABCDEFGHIJLMNOPQRSTUVXYZ
4.5.
,
Ũ
9,33.



,,

-
,,

-
,.,б


f
,,,
g
.
4.6.



:






























00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


-

A
1
,
A
2
,...,
-

A
100
.


-
.

30,

.

,
,
A
1
=
3
A
k
+
1
=
A
k
+
+
3(
k
2
+
k
+
1)
k
.
214.7.
4.7.
Ͳ,
-
.
a
(,
)

a
(
2

1)
=
r
1
+
x
a
.
(

-
.)

a

0.
5.1.
(
,
,
z
),
-
1020,
,

F
(
,
,
z
)
=
99.

F
(
,
,
z
)
=
3
2

2

7
z
.
5.2.
,20
.
-
,,

:


,


.
,
:





------
.
5.3.

ABC

AB
,
BC
,
AC

OP
,
OQ
,
OR
.,
OA
+
OB
+
OC


2(
OP
+
OQ
+
OR
).
5.4.


(

),

.

-
.
:
,










?.(
-
,).
5.215
5.5.
:
p
3
+
1
p
3
+
71

(7
+
p
2

1)
q
2
+
14
p
2

1
+
118
=
0.
5.6.
.
,





.





,
.
.
6.1.
,1997,

N
.
N
.
6.2.
1997

1997
-
11997,

11997.,
,
,

.
6.3.





.






,,


-
..
216.7.
6.4.

-
.
.
33,

10,

7.


:
Ũ

0906
.
,

.
.

-


.

,
.
1
-


,
2
-
3
-


0.
)

;
)
24809283911211
.
6.5.
19
-
.

-
0

,


.0

.
,



-


.
6.6.
,
a
1
,
a
2
,
a
3
,...2,
a
n

-

p
n
+
2
24
n

1.
6.7.

a
,



...


j
|
{z
}
1996

a
j
a



...




|
{z
}
1996
=
1996.
1997.
7.1.

10,
5.217


()?
7.2.
,.
,

.

-
.

.

,

.
:
4249188780319,4245133784397,5393511,428540012393,
4262271910365,4252370031465,4245133784735
4208212275831,4242592823026,

-
.
-
?
,.
7.3.

-
:

,,


r
,
.,

(
=
1,2,...,
r
),

f
(
)
=
ax

b
,
a

b

,
ax

b

ax
+
b

r
,
,
r
,.








.8
7.4.
ڻ
1759.

-
.,
(..8).
a4.
7.5.

a

0,
b

0,
c

0
-
:
a
3
+
b
3
+
c
3
+
6
abc

1
4
(
a
+
b
+
c
)
3
.
7.6.

1.

218.7.
.

-
1
2
(
)?
7.7.
0,1,...,9
.,



(,).


k
-


k
-

Ũ
,

-
.

-
.

,
.
-
873146507381
.
.9
8.1.

-
.
-
,
,

-
.
-

-
,
.
.
8.2.
,
,
.
-

-

k
1


k
2
,
k
3
.


k
4

k
5
,

k
6
.
-

k
i
,
i
=
1,2,...,6,,
?

.
8.3.
,,
,6

5.219
.

-
8,,


,

.,
.41707

04041707
.
-
48.
,
100,,


2.
,3
,57

03
,
05

07
.
,
.
,

,

-
,

10.

:
150220454213266744305682533362327363924975709849
.
8.4.
13

131

1.
.10

-
,

.
.

-

,

-

1999,
-
,
.
.
8.5.

a
,
b

a
1

bx
=
b
1

ax
.
8.6.
2
30
+
1.
9.1.
,
-

,
.

220.7.


-
,

-
,.
),33

,
,
-
,.
),26

,

,
.
9.2.

Ũ
1949
1999
9.1

.
-


..


,

?
9.3.

-

Ũ
0102030405060708091011121314151617

18192021222324252627282930313233
(
)
.

77

.

:
317564404970017677550547850355
.
9.4.
4

4,
1,

216.,
,
-
,

(



).
,1,
-


2..

()

6.
221


.
9.5.
5

A
(

5;0)
D
(5;0).
-

B
,
C
,
:
1),
C


;
2),
C
;
3)
C
;
4),
ABE

ECD
,
.
9.6.

a

p

2


0,25
+
a
2

1
+
p

2
+
+
3,75.
6.
1.1.

n

n

-
.

1
2
3
4
5
1
5
6
7
8
6
2
4
8
9
9
7
3
3
7
9
9
8
4
2
6
8
7
6
5
1
5
4
3
2
1
,

-
.
6

6,

.
n
2
/
4(,

n

).
-

.
-


,

.

,


n
2
/
4(),
-
,.4
n
2
/
4
.,


.

-
,





n
4
n
2
/
4
.
ձ


,

-
,
,
-
.


.


.
1.


Ҿ
.

.,
Ұ
.

.,
޲
.

.
..:ƽ,2004.


-
.

:
;
;;

-

F
2
;

;;
;,
;
.,

-
,


-
.
2.
޾
.

.
-
.
.:ƽ,2003(1
-
.);2006(2
-
.).
.

-

-

-

.
:

-
;

;

-
;

;

-
;;

;

;

-
299
;

-
;
.
3.

..,,
-
..:ü,2002.
.

-
(1),

(2)(
3).,
4

-
,
.
,,
(
-
C)

(5)..

-
,1653.
4.

.

.

..
-
..:,2006.




,
-
,

.

:,
,
-
,,,

,,,


-

-
,
-
,
-
,,
-
,.

,

.


-
Mathematica.

-
CD
-
ROM.
-
,

Mathematica.
5.

...:
-
²,2001.


-
,
-
,
-

-
.

().
:
-
;

;;;
;
-
.
300
ձ
6.

.

..
:,,1998.
:

-
(,

-
,,),
(
,),

-
(),

.,

.,
,
.,

(.52)

.
7.
ٽ
.

..
-

//
.(

-
Ҽ17

182002.).:ƽ,2003.
.98

121.


-
:

-
,
,
,
,
-
.
.
8.
ٽ
.

.,
ҵ
.

.,


Ҿ
.

.
-

//

.(Ҽ28

292004.).:
ƽ,2005..32

64.
,

-
(



11
).,
,
,

.
9.
ٽ
.

.,
Ҳ
.

.,
ݽ
.

.

//

.(Ҽ28

292004.).:
ƽ,2005..65

90.
,
.
,

,,

(,

-
),.
301
10.

.

.i


.i:
-

-
i


i,1998(..).
,

-
ջ

-
...


.


.
11.
ٽ
.

..

http://thecrypto.ru/wiki/
index.php/_._._
;
,2010.
,,



-
вغ


ؼ
-
¸..

-
;

.

-
:
,
,
,
,,

-
,

,
-
,
-
,
,
.,

-
,

.
12.

.

.



.

http://logic.pdmi.ras.ru/infclub/
?q=courses/cryptography
;,
2010.
,P
D
-
MIComputerScienceClub(

)2008.

,

ѳ.

-
н..;,,





.
..,

302
ձ
.,
..
.
13.

.



.
:
http://yury.name/cryptography/
;
-
,
2010.
,
ѳ2005.

,

.

,,,
,
(oblivioustransfer,


),,

(multi
-
partysecurecomputation,
-


).,

,,
,
,

-
.
14.
GoldreichO
.Foundationsofcryptography.Vol.1(Basictools);Vol.2
(Basicapplications).Cambridge,UnitedKingdom:CambridgeU
niversity
Press,2001(v.1),2004(v.2).
.

-
:,
,
-
,,
,
,
.


-
(.52

-
).

-
1

.
-


.,
www
-
(
http://www.wisdom.weizmann.ac.
il/oded/
)
-
.
15.
LubyM
.Pseudorandomnessandcryptographicapplications.Prince
-
ton,NewJersey:PrincetonUniversityPress,1996.
,

-
Һ()

-
1990.:
,
-
,,

,,

-
303
,,


-
,,
(
),.

.

-
(
),

.




:
.,л

,


-
(
)
.
16.
GoldwasserS
.,
BellareM
.Lecturenotesoncryptography.
www
-
ձ(
http://cseweb.
ucsd.edu/users/mihir/papers/gb.pdf
);
-
,2008.
:,,

-
,,
,
(,),
-

-
,,,

,.

,

.

ӳػ.,

,.



(
-
).
.
ղ


.
,


.
,

-
,
.


-

Ҹ
-
ؼ
.

,
,

,
.
,,

-
.,




,
-
.



,.

,

.
,
,
.

-
.
1.
Cryptography

-
,
,


,





,

,

.
-
,


305
,

-
.,

-
,:



.

.,
-





-

-
,


.
-
,..

,

,

.




,,
-
,.
-

-
.

-
,,

-
,
.
2.

:,
-

Cryptology,mathematicalcryptography,theoreticalcryptograp
hy

,
-


.


,:



.

.
-








.


,
,
.
3.


(

),
-



.

.
4.
Cryptanalysis


(

),
-


,


-
.
306
ղ
5.
Cryptographicprotocol


(

).


-
.,




-

,

,

.

,
:
,
,,

-
,,
.

,


.


-


.
6.
Cryptographicscheme



,
-
,..

-





-


.
7.
Cryptographictransform
,
-



.

-
.
,



(,

)
(

).
,(

-
,

).

.,




-
.:
.
8.
Cryptographicalgorithm
,

.

307

.






.
9.
Round



,

.


,

-
.

,



.



.


,

.
.



-

,
.

-
().





-
.

.


-
.,

,

.
10.

:
View
,

-
,

-
.




-


.
11.
Privatechannel
,


,..

.
-




(
-



).
308
ղ



-


.
12.
Authenticatedchannel
,


.


-

.
-




.
13.()
Party
,
.


.

,
,.,


,
:,
.
14.
Honestparty


,
-
,,,
-

(),

.

,
-
,,
.
15.
Authority,trustedauthority


,
-
.

,

,.
ޱ
,
:
,
,

-
(

).
16.ٱ
BigBrother

-

,
.

,.

309
17.
Alice
ر

,


-

(

).


ܵ(eavesdropper


-
),


-
(
,



).
18.
Bob
.

.
19.
Eve
.

.
20.
Adversary
,,
-

,

,
-

,

(,
).,,

-


.



-
.

-


.
21.
Passiveadversary

,
-


,
.



.
22.
Activeadversary
,
-

.,
-


-
.
310
ղ
23.
Dynamicadversary



-


,,

t
.,
,

,
t
.
24.
Attack


,

.,
,

-
,

.

.




,
.
25.
Threat


,

,
-

(,
-

),

.
26.

:
Con

dentiality,privacy,secrecy

-


,


.
27.
Integrity




,


,
-
.
28.
Messageintegrity
,

-
.

311
29.
Untraceability


-
,

,
-
..

-
,

,
-
.




.
30.
Unlinkability
,

.,
-

,

-
,,

.
31.
Anonymity
,

.,
-

-

-
,...,,

.

.

,

,
,

-
.
32.
Security


(


)

()

.
-
(,,

)

(

,

).
-
,

,,
,
.


,

-


,
-
,

.
312
ղ






.



-
,

.,


-
.

-

.


(

)
-
:
--


-
.

.





.





.
33.
Cryptanalytictechnique

-

-

.,

-






(

).

..

.
34.
-


:,
Information
-
theoreticsecurity,unconditionalsecurity,Shannonsecuri
ty


(
-

)

,
(

)
(
).
35.
-

Complexity
-
theoreticsecurity,complexity
-
basedsecurity


(
-

)

,
(

)
,

.,,

,


.

313
36.
Randomoraclemodel

-

,,

.

.

-
(,)

,,,

-
.

-

,
-
.
-







.
37.
Securityparameter




-



-

.,

,
-


..(

,

),


.

.


-


..

.
38.

:
Key


(
-

).
-


.






.
39.
Privatekey


(
-

),


.
-






(

).
314
ղ
40.
Publickey


(
-

),,

.



-
,,


.
41.
Negligiblefunction
[0,1],


n
!1
1
/
p
(
n
)
p
.
-




-


,
-

(,


)

.
42.
Negligibleprobability
.

.
43.

:
Cracking,breaking





(

),..,
-
.
44.
Totalbreaking,totalcracking



.
-


.
45.
,,
-
,.
:
-

,


,

,

.
46.
,
,

-

.:


,,.

315
47.
Cryptographicprimitive



-
,

(
-

)
-

.:

,


,

,
-
.
48.
Cryptographicassumption


(

)



-
,
-


.
:

,
-

..;
-
:

;
,,
.
49.
One
-
wayfunction
1.


,
-

.,
,

-
.,
,

.
2.


,

.
50.

:
Strongone
-
wayfunction,stronglyone
-
wayfunction



,
,



.
-
.

,

-


.
51.

:
Weakone
-
wayfunction,weaklyone
-
wayfunction



,
,

316
ղ

n
1

1
/
p
(
n
)

p
.
52.
One
-
waypermutation


.,
-
,
.
53.
Trapdoorfunctiongenerator
,,

(
)
-
.

-
.,,

-


.
54.
Trapdoorfunctionfamily
,


.
55.
Trapdoorfunction

,(
-
).
56.
Trapdoorpermutationfamily

,
.
57.
Trapdoorpermutation

,
().
58.
Pseudorandomgenerator
1.


,(
-
),

.
2.


,,
(,),

-


-
.

317
3.


()
-

-

.
59.

-

Cryptographicallystrongpseudorandombitgenerator


(

)


,
n

-

m
,
m

n
,

m
.,
,

.


-
,

,

-

(

).
60.
Next
-
bittest

,


.

;
,
,


-
()
-


.
61.
Pseudorandomfunctiongenerator



.
,

,,
.
62.
Pseudorandomfunctionfamily
,.,

-
,

-
.


,






,..
.

318
ղ
,

-


,
.
63.
Pseudorandomfunction

,
().
64.
Pseudorandompermutationfamily

,
.
65.
Pseudorandompermutationgenerator

,
-
.
66.
-


:
-

Cryptographichashfunction
,,



.
-

(

)
-
-
,
--

.
67.
Collision
(
,
)
-

h
,
=

h
(
)
=
h
(
).

(

)
-
:




.
68.
Speci

ccollision

-
h




,
=
,
h
(
)
=
h
(
).
69.
Existentialcollision

-
,
f
h
n
g
,
h
n

-

n
.

319

n

(
,
),
=

h
n
(
)
=
h
n
(
).
70.
-

Hash
-
code,imprint

-
.
71.
-

One
-
wayhashfunction
-
,


.
72.
-

Collision
-
intractablehashfunction
-
,


.

.
-




-
,

(collision

freehashfunction).
.
73.
Compressionfunction
,,
-
,
-
.
-
-
,
.
74.
Claw
-
freepermutationpair

,
f

g
,
-

,
,
f
(
)
=
g
(
).



.

-


.
75.
Interactiveproof
,


.
-


,



,


-
.

-
,.

-
320
ղ
:,

();
,
-


-
().

.,,
,

.
76.
Prover
.

.
77.
Veri

er
.

.
78.а


Arthur

Merlingame,public
-
coinproofsystem


,
,

,,

.
79.
Multi
-
proverinteractiveproof


,





.
-
,

.
80.
Proofofknowledge


,



-
.
-


-


.


.
81.
Noninteractiveproofofknowledge

,

:



,

321
,,

-
.
82.
Zero
-
knowledgeproof


,,
-
,

-
.

,,


-
,,

().

:,

,



..
-


-
:

;

;
-


.




-
:,

;,

-
(
),


;
-


.
83.
Computationalzero
-
knowledgeproof


,
,


-


.
84.
Statisticalzero
-
knowledgeproof


,




.
85.
Perfectzero
-
knowledgeproof



,,
-

,
,



,.
86.
Computationalzero
-
knowledgeargument
322
ղ


,






-


.
87.
Statisticalzero
-
knowledgeargument


,
,


-


.
88.
Perfectzero
-
knowledgeargument

-

,,
-
,

-
,



,.
89.

Multi
-
proverzero
-
knowledgeproof





.
-


(,

-
,
),





-

.
90.
Zero
-
knowledgeproofofknowledge


,


.
91.

Noninteractivezero
-
knowledgeproof


,


:



,,,

.

.
:




.
92.
Commonreferencestringmodel

323

-

,,
,()

.
93.
Noninteractivezero
-
knowledgewithpreprocessing

-

,
-
,

-
.,

,(
)

.
94.
Complexityknowledge
,

-
,


-


.


.
95.
Minimum
-
knowledgeproof

,
,

,
-


.


-

L






.,
-
L,
,
2
L

/
2
L
,.,,


,,


2
L
.

,
-
,
2
L

/
2
L

.
96.
Witnessindistinguishableproof

,
-


,
-
.







324
ղ

NP.
,
w
(
)

(NP
-
)
.


-



w
1
,
w
2
2
w
(
).
,

w
(
)
.
97.,
Witnesshidingproof

,
-


,

.
NP

-

G
,(
,
w
),
w

(NP
-
)
.

G
,

().
98.

Noninteractivewitnessindistinguishableproof

-

.
99.,
Noninteractivewitnesshidingproof

,
.
100.

Honest
-
veri

erzero
-
knowledge

.
,




,
..,.

-


,

,
.
101.
Securemessagetransmission(protocol)

,,


,
-
,

.
-




325
,
-

.
102.

:,,
Cryptographicsystem,cryptosystem,cipher


(
-

).
-

.


.
,

3.

.




-
.:

,

..

.
,




-






,
.

-
:,

..



,
,.
,




-
(
)




.
-
,

..
103.
Plaintext
,,

-



-


(

).
,,


.
104.
Ciphertext



-

.
326
ղ
105.
Cryptogram





.




,
-
.
106.

:
Blockcryptosystem,blockcipher

,


-
,





.

.







.
.,
.




,
:,..
107.

:
Streamcryptosystem,streamcipher

,





,,,

.

..

.
108.
Private
-
keycryptosystem


(

),,


,
-


.

.
-







-


,


-






.
.

-
,

:

-
.

,

-
.

327
109.
Public
-
keycryptosystem


(

),

(
-

),


(),

-

.

..
-

.
110.
Polynomialsecurity





.


-
.

-

.

,
-
,,
m
0

m
1
(
),


m
,

.

,1
/
2,..
-

n
,1
/
2
+
1
/
p
(
n
),
p


,
n


.
-


.
111.
Semanticsecurity





.


.
-

-
:



,,


.


.
112.
Encryption,enciphering




(

),
.(


,)

.

..
-




.
,

328
ղ

.






.
,
.
113.
Encryptionalgorithm

,
-

.
114.

:
Decryption,deciphering


,


.
-
.

(

,)

.

.
-




,
-
.
,

-
,,

.

.

-
,(
),decryption
cracking
(breaking)

-
.

.

-
,cracking(breaking)

,

,.,

.

,

:
?

-
,




-








.
-
,...!

,

-
?,

-
,,.
115.
Decryptionalgorithm

329

,
-

.
116.
Authentication
,

.
117.
Authenticationprotocol


,


.

(),



,
-

.
118.
Authenticationtheory


,
-
.,غ.(

-
).

,







,

.
119.
Authenticationcode
1.

.
2.,
-



-
.



.
-


MAC(

).

..
-
.

,
:



,.
120.
Impersonation
330
ղ



,
-

,
-
.
121.
Substitution
(

,

),


.
-

,,


-
.

.
122.
Messageauthenticationprotocol


.,



,

(2).
-
,


.
123.
-


:
Digitalsignatureprotocol


.

.



,




.

.




(

digitalsignature),
-


.




:

()

-
,,
;

,..

-




,
-
;






-
:,,

-
..

331



-
.(,
)

,



(),
.

,,,
.




(digital)
-
.

-
,

.

-
.
,
.
,
.
-




;
,(,)

,.
124.
Digitalsignaturescheme

,
-


-
.
.
-
.
125.
Signatureveri

cationalgorithm


.
-
,


-
.



,,


-
,.



.

-


-
.
126.

:
Signaturegenerationalgorithm


.,
-
,

-
,

,
-
332
ղ
.

.

-
(
).
127.
Arbitration



.
-


,
-

,

,

..,
.,

,

.
-
,

,(),

-
.
128.
Arbiter
.

.
129.
Arbitratedprotocol

,


.
.

-
.




.
130.
Forgery



.

,
-


,(,),


.
-
,

,

,




.
131.
Universalforgery



.

,
-


,,
-

333


.
.
132.
Selectiveforgery



.

,
-


,(
-
),,

,
.
133.
Existentialforgery



.

,
-


,


(,),


.
,.
,
.


,
,
-
.




.
134.
Messagerecoverysignature


,
-
,

.
135.
Blindsignaturescheme

,
-
,

,

,,

-
,.



.
136.
Fairblindsignaturescheme

,
-

,,
.


-




(
-
334
ղ



-


).
137.
Fail
-
stopsignaturescheme

,




-
.
.
-
,
-

,



.
138.
Undeniablesignaturescheme

,



-
,
.



,
-
,
,,
,.
,


.
139.
Groupsignaturescheme

,.

.

,

.
140.

:
Interactiveauthentication

,


.

,

.
-







.
-





335
.

-
,
-

,

.





.
141.
Mutualauthentication


,
,
.


.
142.
One
-
wayauthentication


,
,

.



,


.
143.۴


Di

e

Hellmankeyagreement
1.


-

,

-


,

.
-


д

.
2.

.1
,

.
144.
Multi
-
partysecurecomputation


,


..
n

-
,.


1
,...,
n
,
f

t
.
-

=
f
(
1
,...,
n
),

,
t



,

..

-
336
ղ
,,

.

:

,
..
145.
Byzantineagreement
,

ز

().
n
+
1


-

n
.
-
,:

.,
,
.,

()



.
:

-
,
.
146.
Contractsigningprotocol

,,
,,
,
-
,
.
-


:

-
,,

,.

-


.
,

(abuse).,

-

,
,

(,,

).
147.
Secretexchangeprotocol

.
.

-
,

-
()

.

337
148.
Electionscheme,votingscheme,votingprotocol

,
-
,

.
,
..,.



,

,
,

.

-
,

.

-
,

,,

,.
.
149.

:
Electroniccashsystem,e
-
cashsystem

,
,

.




-

,

,

.
-


.

-


.

-

.
,,

.

-

-

,

,



.
150.
On
-
linee
-
cashsystem

(
-

),
-


.
151.
O

-
linee
-
cashsystem
338
ղ

(
-

),,

-
.
,,



.
152.
E
-
cash
,



.
153.
E
-
coin
,
-

.
-
.

-
.
154.
Bitcommitmentprotocol


(),

,

,
:
1.(
),

.
2.

,

-
.
,
,,

-
(
).

..


.
155.
Blob
,

-


(

).
156.
Secretsharingscheme

339


,

.

s
,



s
1
,...,
s
n
.
s
i

i
-
.

s
,
,,

-
,
,
.
157.
Accessstructure


,
-

S

S
.
,



.
158.
Share,secretshare
,


.
159.
Thresholdsecretsharingscheme



,
-



t

t
,


.
160.
Perfectsecretsharingscheme

,


-


-
.,

,



.
161.
Idealsecretsharingscheme

,

.
162.
Secretsharingprotocol

,


,.

,
(
340
ղ
),.

-

.

,
.


,,

,

.
163.
Veri

ablesecretsharingprotocol

.

,
-
,.

-


-
,

.
-



-

-


(..
).




151
22

126

115


-
125


-
126

113
17
31
128
127

-
88


-
86


-
87
24
116

141

142
12

155
106
106
18
ٱ16

43


-
65

61

53

114
23

-
81

90

75


-
85


-
83

95

96

82


-
84

,97
76
158

19


-
136
11

а

78
342
ղ

-
161
120
140

38
119
67
26
4
105
102

6

-

-
59
8

38

47

5

-
48

7
1
2
3
102

109

108

2
94
33

-
92

93

36

-
79

89


98

91

,99
29
30

100

52

49
40

103


-
74
37
21
57
130
121
110
44

-
159
107
107

-
42

41

45

46
77
20
117

122

145

148



143

80

343


-
140


-
101


-
144

147

146

154


-
163

162

129


-

-
123

123

149
63
58

43
114
9

26
39
132
111

-
56

64

62

54
50
50
102

149
51
51

-
160
68
32

34


-
34


-
35

34
157

139


138

156

124

135


-
137

2
118
60
10

10

25

-
131
()13

55
73


-
70

-
66

66

71


-
72

27

28
15
344
ղ

-
150

14

102
112
104

69

133
153


-
134
152


A
Accessstructure157
Activeadversary22
Adversary20
Alice17
Anonymity31
Arbiter128
Arbitratedprotocol129
Arbitration127
Arthur

Merlingame78
Attack24
Authenticatedchannel12
Authentication116

code119

protocol117

theory118
Authority15
B
BigBrother16
Bitcommitmentprotocol154
Blindsignaturescheme135
Blob155
Blockcipher106

cryptosystem106
Bob18
Breaking43
Byzantineagreement145
C
Cipher102
Ciphertext104
Claw
-
freepermutationpair74
Collision67
Collision
-
intractablehashfunction72
Commonreferencestringmodel92
Complexityknowledge94
Complexity
-
basedsecurity35
Complexity
-
theoreticsecurity35
Compressionfunction73
Computationalzero
-
knowledgeargu
-
ment86

proof83
Con

dentiality26
Contractsigningprotocol146
Cracking43
Cryptanalysis4
Cryptanalytictechnique33
Cryptogram105
Cryptographicalgorithm8

assumption48

hashfunction66

primitive47

protocol5

scheme6

system102

transform7
Cryptographicallystrongpseudoran
-
dombitgenerator59
Cryptography1
Cryptology2
Cryptosystem102
D
Deciphering114
Decryption114

algorithm115
Di

e

Hellmankeyagreement143
Digitalsignatureprotocol123

scheme124
Dynamicadversary23
E
E
-
cash152
346
ղ

system149
E
-
coin153
Electionscheme148
Electroniccashsystem149
Enciphering112
Encryption112
Encryptionalgorithm113
Eve19
Existentialcollision69

forgery133
F
Fail
-
stopsignaturescheme137
Fairblindsignaturescheme136
Forgery130
G
Groupsignaturescheme139
H
Hash
-
code70
Honestparty14
Honest
-
veri

erzero
-
knowledge100
I
Idealsecretsharingscheme161
Impersonation120
Imprint70
Information
-
theoreticsecurity34
Integrity27
Interactiveauthentication140

proof75
K
Key38
M
Mathematicalcryptography2
Messageauthenticationprotocol122

integrity28

recoverysignature134
Minimum
-
knowledgeproof95
Multi
-
partysecurecomputation144
Multi
-
proverinteractiveproof79
Multi
-
proverzero
-
knowledgeproof89
Mutualauthentication141
N
Negligiblefunction41
Negligibleprobability42
Next
-
bittest60
Noninteractivezero
-
knowledgewith
preprocessing93

proofofknowledge81

witnesshidingproof99

indistinguishableproof98

zero
-
knowledgeproof91
O
O

-
linee
-
cashsystem151
On
-
linee
-
cashsystem150
One
-
wayauthentication142

function49

hashfunction71

permutation52
P
Party13
Passiveadversary21
Perfectsecretsharingscheme160

zero
-
knowledgeargument88

proof85
Plaintext103
Polynomialsecurity110
Privacy26
Privatechannel11

key39
Private
-
keycryptosystem108
Proofofknowledge80
Prover76
Pseudorandomfunction63

family62

generator61

generator58

permutationfamily64

permutationgenerator65
Publickey40
Public
-
coinproofsystem78
Public
-
keycryptosystem109

347
R
Randomoraclemodel36
Round9
S
Secrecy26
Secretexchangeprotocol147

share158

sharingprotocol162

scheme156
Securemessagetransmission(proto
-
col)101
Security32

parameter37
Selectiveforgery132
Semanticsecurity111
Shannonsecurity34
Share158
Signaturegenerationalgorithm126

veri

cationalgorithm125
Speci

ccollision68
Statisticalzero
-
knowledgeargu
-
ment87

proof84
Streamcipher107
Streamcryptosystem107
Strongone
-
wayfunction50
Stronglyone
-
wayfunction50
Substitution121
T
Theoreticalcryptography2
Threat25
Thresholdsecretsharingscheme159
Totalbreaking44

cracking44
Trapdoorfunction55

family54

generator53

permutation57

family56
Trustedauthority15
U
Unconditionalsecurity34
Undeniablesignaturescheme138
Universalforgery131
Unlinkability30
Untraceability29
V
Veri

ablesecretsharingprotocol163
Veri

er77
View10
Votingprotocol148

scheme148
W
Weakone
-
wayfunction51
Weaklyone
-
wayfunction51
Witnesshidingproof97

indistinguishableproof96
Z
Zero
-
knowledgeproof82

ofknowledge90
¾ĸ
ٲ..
04.09.2012.60

90
1
/
16
..
...22.2000.
޼

119002,,ٲ.,11..(499)24
1

74

83.
CtPҸ



194044,
-
,.,.9..
/
:(812)495

56

10
мƽ



,
ٲ.,.11..(499)241

72

85.E
-
mail:[email protected]
http:
//
biblio.mccme.ru


 
    !
      -    
  .       
   ,         -
     . !      -
       "-
!       "  .
 !        
  !  "!   ,
        
     ,  -
,   "...
#      $   %  ?
&       " ,  -
 ,      $   
        $ . '   
     !.  -
      !      
   .      
      !   .
"#


 
ISBN978-5-4439-0026-1
Ìàãàçèí¾Ìàòåìàòè÷åñêàÿêíèãà¿
ÊíèãèèçäàòåëüñòâàÌÖÍÌÎìîæíîïðèîáðåñòèâìàãàçèíå
¾Ìàòåìàòè÷åñêàÿêíèãà¿âÌîñêâåïîàäðåñó:Á.Âëàñüåâñêèéïåð.,
ä.

Приложенные файлы

  • pdf 8942227
    Размер файла: 3 MB Загрузок: 1

Добавить комментарий