close

Вход

Забыли?

вход по аккаунту

?

2001-0069-0-01

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Санкт-Петербургский
государственный университет аэрокосмического приборостроения
?. ?. ????
?????????? ??????????.
?????????????? ??????? ????????????
??????? ???????
Санкт-Петербург
2001
??? 512.54
E78
??? 22.1
???? ?. ?.
?78 ?????????? ??????????. ?????????????? ??????? ????????????: ????. ???????/???????. ???., 2001. 56 c.
? ??????? ??????? ?????? ???????? ???????? ????????? ????????????, ??????? ?? ????????????? ??????????????? ???????? ????? ??????????????? ??? ?????? ?????????? ??????????. ?????? ?????? ???????
??????????? ?? ??????? ??????????? ?????????????? ?????????? ? ???????? ?????????? ??????? ???????. ?????? ? ??????????? ??????? ?????????? ????????? ??????? ? ??????? ?????? ?????. ??? ?????????? ?
???? ???????? ????? ????????? ??????? ??????? ??????????? ??????????. ?????? ?????? ???? ?? ?????? ??? ????? ?????????? ?? ?????? ?????.
??????? ????????????? ?? ????????? ??????????? ?????????????, ?????????? ? ?????????????? ?????????? ??????????? ??????????? ??????????? ?????.
??????????:
??????? ??????????? ?????-??????????????
??????????????????? ????????????;
????. ????. ???? ?????? ?. ?. ????????
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
© ?????-?????????????
??????????????? ???????????
????????????????
???????????????, 2001
2
????????
???????????? ? ????? ? ????????? ?????????? ??? ?? ???? ??????
???. ?????? ?? ?????????? ??????? ??? ??????????? ??????????, ???????, ??????????. ? ?????? ? ???????? 70-? ????? ?????? ???????????
? ??????? ?????????????? ?????? (? ????? ? ??????????? ?????????
????????? ????????????? ??????). ??????? ?????????? ???????????
????????????????? ?????? ?? ?????????????? ??? ????? ????????????????????? ????????????, ? ?????? ??? ?????? ?????????????? ??????? ? ?????????? ?????, ??? ??????????? ??????? ? ?????????????? ???????????? ????? ? ?????? ???????.
????? ??? ???????? ???????????? ???????? ???????? ?????????
???????????? ? ??????????? ?????????. ??? ???????? ????????????
???????? ???????? ????? (??????????? ???????????? ?????????). ????? ????? ????????????? ???????? ????????? ??????? (???. 1).
????? ?????
???????????
?????????
????????????
?????????
??????????
?????????
??????????
?????????
????
(??????????
???????????
?????????)
???. 1. ????? ????? ?????????????
?????? ????????? ?????????? ???????????: pt ? ???????? ?????;
E(pt) = ct ? ????????????? ????? (???????????); D(ct) = pt ? ?????????????? ?????.
???????????? ? ????????????? ??????? ???????????? ? ?????? ?????????????.
????????????? ??????? ?? ????????? ???????????:
1. ???????????? ???????? ????????? PT, ??????? ???????? ???????????? ???????? ?????? pt.
3
2. ???????? ???????????? K. ??????? ????? k ? K ?????????????
???????? ???????????? Ek ? ????????????? Dk. ???? ? ????????? pt
????????? Ek, ? ? ?????????? Dk, ?? ????? ??????? ???????? ????? pt, ?.
?. Dk(Ek(pt)) = pt.
3. ???????????? ????????????? CT, ?. ?. ????? ???????????? ????????????? ct.
?????????? CT ???????? ?????????? ?????????? ? ????????? PT
??????? ?????????? Ek, ??? k ????????? ??? ???????????? K.
??? ???????? ????????? ????????? ?? ????????? ??????? ?????
?????? ????? ?????????????? ?????????? ??????????? ?? ???????? ???????? {0, 1}, ? ????? ??? ??? ????????? ???????????? ????????????.
???????? ???????????? ?????? ?? ?????? ???? ????? ?????????,
??? ??? ??????????? ?? ?????? ????? ??????????? ????????? ??? ?????. ????? ???????????? ?????? K ??????????. ??? ??????????, ???????? ?? ?????? ????????????? ???????? ??? ??????? ????? ????????????? ?????????? ? ??????????????:
1. ?? ???????? Ek ? ????????? ????????? pt ????? ????????? ct.
?? ???????? Dk ? ct ????? ????????? ???????? ????????? pt.
2. ?? ???? Dk, , ?????? ????????? pt ?? ???????????? ct.
3. ??????????? ?? ?????? ???????? ??????????, ?. ?. ?????? ????????? ???????????.
??? ?????????????? ?????? ?????????? ?? ????? ??????, ? ??????
?????????? ???????????????, ??? ??? ????????? ????????????? ????????????? ?? ?????? ???? ????? ???????, ? ?? ?????? ? ??????????????? ??????? ???????? ?? ??????????????????.
4
1. ???????? ???????????? ????????????
1.1. ??????? ????????????????? ???????
???????????? ? ?????????? ??????? ??????????????? (?????? ?
??????????? ?????????????) [2].
??????? ??????
????? ????????? ???????? ????????? ?????????, ?????????? ?? ?????????? ????? (???????? 26 ????, ??????? ????????????): WE GO TO
CITY. ??? ????? ?? A ?? Z ?????????? ??????? ?? 0 ?? 25 ? ? ????????? ???????????? ??????, ???????? ?? ??????? ?? ???:
A B C D E F G H I J K L MN O P Q R S T U V W X Y Z
D E F G H I J K L MN O P Q R S T U V W X Y Z A B C
? ???? ?????? ???????? ????? ????? ?????????? ??? ZHJRWRFLWB.
???????? ???????????? ??????? ?????? ??????? ?? 26 ????? ?? 0 ?? 25
? ?????????? ????? ???? ???? ???????? ??? ???????. Ek ? Dk ????? ??????????? ???? ?? ???????, ??? ??? Dk = E26?k. ????????? ?????
{Ek}???????? ????????????? ?????? ???????, ?????? Ek?1 = Dk
?????????? ????? ?????? ????? ??????? ???? ????????????. ????????? ????? ???????????? 26 ???? ????? 26!, ?? ???????????? ??????
?????? ????? ????? 26!, ?. ?. ?????????? ??????. ?????? ?????? ????????? ???????????? n ????????? ???????? ??????, ?. ?. ?? Ek ?????? ?
?????????? ????????? Dk
????????????? ?????
????????????? ???????? ?? ????????? ???????? ???????. ??? ?????
??????????? ???????? ?????????? ???????, ??? ? ? ?????????? ??????: A?0, B?1, ..., Z ?26. ??????? ??? ?????????? M ????? ??????
dЧd. ??? ???????? ??????????? ?? ?????? 26. ??? ????????? ??????????? ?? ????? ????? d. ??? ?????? ????????????? ??????????, ????? ??????? M ????? ?? ????????.
? 3...3 ?
?1 ? 15...17 ?
????????, M = ?
? M =?
?.
? 2...5 ?
? 20.....9 ?
5
???????? ????????? HELP ???????????? ????? ?????????
? H ? ?7?
P1 = ? ? = ? ? ;
? E ? ? 4?
? L ? ? 11 ?
P2 = ? ? = ? ? .
? P ? ? 15 ?
?7?
?0 ?
?? ????????? MP1 = C1 ? ? ; MP2 = C2 ? ? , ??? ????????????? ????8 ?
? 19 ?
????????? ????????? HIAT.
???????????? ????????? ????? ?????????? ???????? ??????? ??1
?? ?1 ? ?2.
????????????? ???????
??? ??????? ????????? ? ?????? ??????? ?????????? ???????????
????? ???????. ??? ?????????? ????????? ???????????? ???? ???????
? ?????????, ????????:
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
?????? ? ????????? ????????????? ?? ???? ?????? ? ? ??????? ??????????? ?????????. ????? ?????? ????????? ? ? ????????? ????????
??????????? ???????, ??????? ????????? ???????? ????? ??????????
?????. ??? ??? ??????? ????? ???????? ?????????:
I
I
D
M
L
F
H
L
H
E E
Y
O V
O R
Y P
O
A
P
S
E
E
E
V E
V E
U
K I
L
V E
R S
Y O U
Y O U
N D E R
N
M Y
A S T S
R
I N
P A C E
??? ???????? ?????????? ???????. ?? ???? ???????? ?????? ? ?????????, ??????? ???????? ????????? YOU KILL AT ONCE.
6
???????? ????????? ????????????? ????????????? ???????. ? ?????????, ?????? ? ????????? ????? ????? ? ???? ?????????? ???????, ?
??????? ? ??????? ????? ??????? ???, ????? ??? ????????????????
????????? ?? 90, 180 ? 270 ???????? ??????? ??????????? ??? ????????.
??????????????? ????????? ?????????? ??????? ???????????, ?
??????? ????? ?????????? ????????? ?? ?????????? ????? ??????.
?????????? ??????????????? ???????????. ?????????? ????????
??????????????? ??????????? ????? ??????? ?????????. ????????
????????? ???????? ?? ????? ?? ??? ????? ? ??????. ??? ??????????
?????? ????? ??????? ????? ?????????? ???????, ? ?????? ? ?????? ?????????? ?????????????? ?????? ? ??????. ???, ?????????
LETUSGOTOFRANCE ?????? ETLSGUTOORAFCEN. ??????? ?????
??????????. ????? ????? ????? ????? d, ????? ????? ????????? ???????? ?????? ????? d!
? ????????? ??????? ? ?????????????? ???????? ??????????? ?????????? ???????, ???????? ?? ???????? ????????? ??????. ????????,
???? ?????? ???? ????? ????? ????? ???:
A: B: C:
J?
K? L:
S
T
U
D:
E: F:
M? N? O?
V
W
X
G:
H: I:
P? Q? R?
Y
Z
????? ???????? ????????? WE TALK ABOUT IT MANY TIMES ????? ????????? ???:
:
:
.
:
:
.
.
.
:
.
:
:
.
:
???? ???????? ????????? ?????????? ?????? ? ???????? ?? ?????
???????????? ?????, ?? ??? ??? ??????????? ????? ???????????? ?????????????? ?????? ? ??????????? ????????? ???? ? ???????????? ??????????. ???? ?? ???????? ????????? ????????? ? ???????????? ????????? ? ??? ??????? ?????????????? ??????????, ?? ??????????? ??????????? ??????????? (26! ????????? ???????? ???????????).
?????????, ??? ????? ?? ????? ??????? ???????????? ???????? ??????? ???????. ?????????? ??????? ????? (????? ???????):
7
A B C D E
A
B
C
D
E
A
F
L
Q
V
B
G
M
R
W
C
H
N
S
X
D
I
O
T
Y
E
K
P
U
Z
?????? ????? ? ?????????????? ? ???????????? ????? ????, ??????????????? ?? ???????????. ???, ????????, ????????? HALLOW
????? ???????????? ??? BCAACACACDEB. ? ????? ?????????????
??????? ??????? ???? ?????????????? ??????? ?????. ????? J ?????????, ??? ???? ????? ???????? ???????. ??????? ??????????? ??? ???????? ????????? ??????.
???????? ?????????????
??? ??????? ???????????? ????? ?????? ??????? a ? b, ?????? 0 ? a,
b ? 25, (a, 26) = 1. ????? ? ?????????? ?? ?a+ b mod 26. ??? a = 3 ?
b = 5 ???????? ????????? ?????? ????:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
FILORUXADGJMPSVYBEHKNQTWZC
??????? ???????? ???????? a ? 26 ???????????? ???????? ????????????? ???????????.
??????????, ??????? ?????? ?????? ??????? ? ??????????? ???????? ???????. ????? a ????? ????????? ????????? ????????: 1, 3, 5, 7,
9, 11, 15, 17, 19, 21, 23, 25. ?????????? ?? ???????? a ????? b ?????????
26 ???????? (?? 0 ?? 25). ?????? a = 1; b= 0 ??????? ?????????. ?????
????? ????? ?????? ????? 311. ? ????? ?????????? ?????? ??????????????? ?? ??????????? ????? ??????? ??? ??????? ?????.
??????? ?????? ? ???????? ??????
??? ???????? ?????????????? ???????? ?????? ? ???????????? ????????? ?????? a ? ???????? ?????? (??????) ? ????????? ??????????? ????. ????? ??????? ?????? ?????? a = 8 ? ??????: HOW MANY
ELKS. ??? ? ????? ???????????? ?????? ??? ????? ?????????? ???????? ? ??? ??????, ??????? ?? 8 ?????, ??? ???????? ??????? ????????
?????. ?????????? ????? ?????? ?????? ? ?????????? ??????? ???????????? ????? ? ??????????? ?????????:
8
0
8
25
A B C D E F G H I J K L M N O P Q R S T U V WX Y Z
P Q R T U V X Z H0 WM A NYE L K S B C D F G I J
?????????? ?????? ?????? ???? ???????????????, ?????????? ??
???????? ?????? ????????? ????????? ???? ? ???????, ???????????? ?
????????????? ???????? (HOMOPHONES), ??????? ????? ????????
??????????????. ????? ????????? ????????? ????? ????????? ?????,
?????? ????? ????? ?????? ????? ??????????????? ??????????? ??
????????? ? ?????? ?????????.
1.2. ??????????????? ???????
??????? ????????? (PLAYFAIR)
??????? ??????? ? ????? ?????? ?????????. ????? ??????????? ????????, ????? ??????? ??????????? J, ??????????????? ? ???? ???????? 5Ч5, ????????
S
Y
D
W
Z
R
I
P
U
L
H
C
A
X
F
T
N
O
G
E
B
R
M
Q
V
??????? ???????????? ??? ???????????? ? ????????????? ?? ????????? ????????.
1. ???????? ????? ??????? ?? ????? ?? 2 ????? ? ??????. ?????
????? ?????? ????? ? ? ??? ?? ?????? ???? ??????, ?????????? 2
?????????? ?????. ???? ??? ?????????? ?? ?????????, ????? ?????????????? (???? ? ????? ???????? ??????????). ????????, AL LM EN; KI
SS ME; WH ER EA RE YO U. ?????? ????? ????????, ?????? ???????? ? ????? 2 ?????????? ?????, ?????? ????? ???????? ?????.
2. ???? ???? ???? ????? ?? ???????? ? ???? ?????? ??? ???????, ??
??? ???? ????????? ????? ???? ??????????????. ???? ?? ???? ???? ???????? ? ???? ?????? ??? ???????, ?? ??? ????????? ??????? ?? ??????? ?????? (? ??????) ??? ???? (? ???????). ???, AL ????????? FP;
LM?PV; EN?TO.
????????? ??????????? CR YP TO EN IG MA?HI DI NG TO UN
DO. EN IG MA ? ???????????? ??????, ?? ??????? ???? ????????
?????????????, ???????????? ??????? ?? ????? ???.
??? ??????????? ???????? ????? ? ???????? ???????? ????????? ???????? ????????????? ???????. ???????? ??????????? ????9
???? ?????????: ?????????????? ???????? 4Ч4; 3Ч9 ? ? ???? ???????? ??????.
??????? ????????? ? ???????? ??????
??? ???????? ????????? ???????: ?????????? ???????? ????? ???
??????? ???? ? ???????????? ? ?????? ??????? ????????, ? ????? ???????????? ?????????? ????? ? ?????????? ???????. ???, ??? ????????
?????: HOW MANY ELKS ???????? ??????? ??? ??????????:
H
N
S
G
T
O
Y
B
I
U
W
E
C
P
V
M
L
D
Q
X
A
K
F
R
Z
??????????????? ??????? ???????? (1523?1596).
??????? ???????? ???????? ????????? ???????:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
BCDEFGHIJKLMNOPQRSTUVWXYZA
CDEFGHIJKLMNOPQRSTUVWXYZAB
DEFGHIJKLMNOPQRSTUVWXYZABC
EFGHIJKLMNOPQRSTUVWXYZABCD
FGHIJKLMNOPQRSTUVWXYZABCDE
GHIJKLMNOPQRSTUVWXYZABCDEF
HIJKLMNOPQRSTUVWXYZABCDEFG
IJKLMNOPQRSTUVWXYZABCDEFGH
JKLMNOPQRSTUVWXYZABCDEFGHI
KLMNOPQRSTUVWXYZABCDEFGHIJ
LMNOPQRSTUVWXYZABCDEFGHIJK
MNOPQRSTUVWXYZABCDEFGHIJKL
NOPQRSTUVWXYZABCDEFGHIJKLM
OPQRSTUVWXYZABCDEFGHIJKLMN
PQRSTUVWXYZABCDEFGHIJKLMNO
QRSTUVWXYZABCDEFGHIJKLMNOP
RSTUVWXYZABCDEFGHIJKLMNOPQ
STUVWXYZABCDEFGHIJKLMNOPQR
TUVWXYZABCDEFGHIJKLMNOPQRS
UVWXYZABCDEFGHIJKLMNOPQRST
VWXYZABCDEFGHIJKLMNOPQRSTU
WXYZABCDEFGHIJKLMNOPQRSTUV
10
XYZABCDEFGHIJKLMNOPQRSTUVW
YZABCDEFGHIJKLMNOPQRSTUVWX
ZABCDEFGHIJKLMNOPQRSTUVWXY
??????? ???????? ??????? ??????? ??????, ? ??????? ???? ????????
?? ???? ? ????. ??????? ???????? ???????????? ??? ??? ????????????,
??? ? ??? ?????????????. ??? ???????????? ?????? ???????? ?????????
?? ????? ? ?????? ??????? ?????? ?? ????????. ???, ??? ????????? ????????? PURPLE ? ????????? ????? CRYPTO ??????? ??????????? P-?????? ? C-???????, ???????? R. ??????????? ????? ???: RLPEES. ??? ????????????? ???????, ? ????? ?????? ? C- ??????? ????? R? ???????? P.
?????????? ????? ?????? ???????? ?????????; ????? ?? ????????
????????? ???????? ??????? ????????, ???????? ???????? ????????
?????? ???????? ????????, ?????????? ? ???????? ???????.
???? ????????? ??????? ????????? ?????, ?? ????????? ???????????? ???????????. ???? ???????? ?????? ??????????, ?? ????????????
???????? ? ????????????? ?????????????? ??????. ? 1860 ?. ????????
???????????????? ?.?. ??????? ??? ????????? ????? ??? ???????? ????????????? ???????????? ? ??????????? ????????. ????? ??????? ???????? ?????? ? ??????? ??????????? ?????????? ???? ? ????????????.
????????????? AUTOKLAVE (????????????? ?????????? 16 ????
??. ???????, ?????????? ?????? ????????? ??? ??????? ????????? 3 ? 4-? ???????)
??????? ???????? ?????????? ???????????? ??????? ????????.
???????? ????????? ? ????????? ??????? ???? ???????? ? ??????
????????. ? ????????? ????????? ???? ????? 6:
?????????: A I D S I S T R A N S M I T T E D T H RO U GH
????:
A I D S I S TRA N SM I T T E DT
???? ????????????, ??? ? ??????? ???????? ??? ??????????? ?????? ??? ?????? ?????. ?????? ??????? ? ?????? ????? ????? ??????????? ??????????? ?????? ????????? ??? ???????? ??????. ??? ???
????????? ????? IMMUNE ???????? ????????? ?????? ??? ????????????:
?????????: A I D S I S T R A N SM I T T E D T H R O U GH
????:
I MMU N E A I D S I S T R A N S M I T T E D T
???????????: I U P M V W T Z D F A E B K T R V F P K H Y J A
? ?????? ???????? ??????????? ??????? AUTOKLAVE ? ????????
????? ???????????? ???????????, ?????????? ????? ????????? ?????.
11
? ?????? ?????? ?????????? ?????? ????? ?????????? ?????????
???????:
?????????: A I D S I S T R A N S M I T T E D T H R OU G H
????:
I M M U N E I U P M V WB L P Z N I J E I D O B
???????????: I U P MVW B L P Z N I J E I D Q BQ VWXW I
??? ????????????? ????????? ?????? ??????????????? ??????????
?????? ????? ????? ?????.
??? ????????? ??????????? ???????????? ????? ????????
????????? ?????????????? ????????? ?? ????????? ???????????????????? ????, ? ????? ??? ???????????? ???? ?? ????????????.
?? ???????????????? ????????????? ??? ?????????????? ? ???????????????. ?????? ????????????? ????? ????????????? ?? ???????????????????? ? ????????????????????. ? ?????? ????????? ?????????????? ?????, ?? ?????? ? ?????? ????. ??????? ????????????
????????? ????? ???? ? ????????? ???????:
???????
???????????????????? ????????????????????
?????????????? ??????
?????????
??????????????? ????????
????????? ? ????????
????? ??????? ????????? ? ???????? ???????? ??????? ?????????, ??? ?????? ?????? ???????????? ????????? ?????????, ????????, ???.
?????? ???? ???? ????????? ????????? ?????? ?????????, ?????? ?
??????, ?????? ? ???????, ????? ????????? ? ????? ?????? ? ?. ?.
??????? ???????? ?????? (CODE BOOK).
???????????? ?????????????? ? ???????????? ? ??????? ??????,
????????,
????????
ATTACK
..................
IN
..................
MORNING
..................
THE
12
???????
FISHING
.................
BETWEEN
..................
WORK HOUR
......................
THE
? ???? ?????? ????????? ATTACK IN THE MORNING (????? ?????) ????? ??????????? ??? FISHING BETWEEN THE WORK
HOURSE (??????? ? ??????? ????????). ????? ??????? ???????????
????????????? ??????????, ? ???? ??????????? ???????? ????????.
??????????? ??????? (ONE ? TIME PAD)
????????? ?????????????? ? ????????? ???????????? [10]. ?????????? ???????? ?????????????????? ????? ???????????? ?????. ? ????
????? ????????? ????? ???????? ??????????????????. ???? ??? ?????????? ? ????????????? ?????. ????????:
?????????S: 1 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1
????:
K:
1 0 0 0 1 0 1 1 0 1 1 1 1 0 0 1 0 0
????: S?K:
0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 1
??? ??????????? ????????? ?????????? ? S ? K ????????? ?? ?????? 2 ??? ??? K. ????? ?????? ????????? ???? ????????????.
????????? ??????????? ????? ????????????? ???????? ??, ??? ????
?????? ???? ?????????? ??????? ? ???????? ???????????? ?????????? ?????????.
1.3. ???????? ????????????????? ??????
????????????? ????????????? ????? ???? ??????? ????? ?????????????????? ? ?????????? ??? ????????????? ??????????????????
?????. ??????? ???????? ????? ????? ??????????? ??? ?????????
????? ???. ???????? ???? ?????????????? ??? ? ????????? ?????? ?????? ?????????? ? ?????? ??????????.
?????? ?????????? ??????? ?? ?????????? ??????, ??????? ?? ????
??? ? ??????? ??????????? ???????? ????????? ???? ????????????
?????. ?? ?????????? ????? ???????? ?? ?????? ?????????? ?????
??????????? ????????, ?????? ??????? ???? ?? ?????? ????? ????????.
???? ???????????? 10 ??????, ?? ???????? ????????? ??????????? ??
????? ?????? 10, ??????? ???????? ?????????? ? ???????????? ???????. ????????? ?????? ?? ???? ????? ??????????????? ?????????
???? ? ?? ???????, ?????????? ??? ???? ??????, ????????? ????????????? ????. ?????? ?????????? ????????? ??????????????? ???????????.
?? ?????? 50-? ????? ? ????? ??? ?????????????? ?????? ?-36
?????????? ???????????? ????????????????? ????? ?????? ????????.
????????? ????????? ????????????????? ??????, ????? ??? ???????? ENIGM?, ???????????? SIGABA, ???????? RED ? PURPLE ???13
??? ?????? ??????? ?????, ???????? ????????????????????. ???????? ?????? ? ??? ???????? ???? ? ???? ???????? ?????? ? ???????????? ??????????? ??????, ?????????? ???????.
1.4. ????????????????? ???????? DES
? 1977 ?. ??? ??????????? ???????? ?????????? ?????? (DES?Data
Encryption Standard) ????????????? ???? ??????????. DES?????????
??? ?????????? ?????????? ??? ??????????? ????????? ??? ???????????? ? ????????????? ??????. ?? ????????????? DES ?? ???? ???????? ??????????, ?????????? ?????? ???????? ??? ????????????? ?????????????????? ??????????. ???? ? ???????????? ??????????????, ???
?????????????? ????? ???????????? ?????????????, ??????, ??????????? ????????????? ???????????? ????????? ?????? ?????? ?? ??????????. DES ???????? ???????????. ?????????? ??? ??????????????? ?????? ? ???????????????? ????????????? ????? ??????? ?????????? ??????. ? ????? ???????, ???? ??? ??????????????? ??? ?????
???? ???, ??? ???????? ????????? ???????. ? ?????? ???????, ???????????? ????? ???? ????? ???????? ?????? ???????, ??? ????? ????????? ??????????????? ???????????? ?????????????? ??????????
????? ???????, ????????????? ? ???????? ??????.
?????????? ?????? ?????????? ????????????? DES.
???????????? ???????? ????, ?????????? 56 ?????. ???? ? ??? ??
???? ???????????? ??? ???????????? ? ????????????? ?????????, ??????? ????????? ? ???????????? ?? ?????? ????????? ??????. ? ??????? 8, 16, 24, ..., 64 ????? ??????????? ???????? ??????? ???, ?????
????? ?????? ? ?????? ???? ????????. ??? ????????? ????????? ???????? ????? ??? ???????? ? ????????. 56 ????? ?????, ??????????? ??
???????? 1, 2, 3, ..., 7, 9, 19, 11, ...17, 19, 20, 21, ...63, ???????????? ????????? ????????????:
57 49
41
33
25
17
9
1
58
50
42
34
26
18
10
2
59
51
43
35
27
???? C0
19
11
3
60
52
44
36
???????????????
63 55
47
39
31
23
15
7
62
54
46
38
30
22
14
6
61
53
45
37
29
???? D0
21 13
5
28
20
12
4
14
???????????? ???????????? ????? ??????? C0 ? D0 ?? 28 ??? ? ??????. ????? ???????????? ??????????? ????????? ??????????????. ??????? ????????? ????? Cn?1 , Dn?1 , ?????? ????? Cn , Dn ??? n = 1, 2, 3, 4, ...,
16 ????? ??? ????? ?????? ???????? ?? ?????? Cn?1 , Dn?1 ? ???????????? ?? ????????? ???????? ???????:
n
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
????? ?????
1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
???????
??? ????? ??????? ??? ???????? ????? ????????? ????? ?? ????
??? ??? ??????? ?????????? ? ???????? ??????? ?????. ?? ?????? CnDn
???????? ???????????? Kn , ????????? ?? 48 ??? (???? 9, 18, 22, 25, 35,
38, 43, 54 ? ???????????? ?? ??????). ????????? ???? ??????????????
????????? ???????:
14
17
11 24
1
5
3
28
15
6
21 10
23
19
12
4
26
8
16
7
27 20
13
2
41
52
31 37
47 55
30
40
51 45
33 48
44
49
39 56
34 53
46
42
50 36
29 32
??? ??????????? ?????????? ???????? ????????????????. ?? ????????? ????? ????????? 16 ??????????????????? Kn ?? 48 ??? ? ??????.
??? ?????????? ????????? ??? ?????????????? ????????? ??????? w, ??????????? ?? 64 ????. ??????? ???? ???????????? ?????????
????????????:
58
50
42 34
26
18
10
2
60
52
44 36
28
20
12
4
62
54
46 38
30
22
14
6
64
56
18 40
32
24
16
8
57
49
41 33
25
17
9
1
59
51
43 35
27
19
11
3
61
53
45 37
29
21
13
5
63
55
47 39
31
23
15
7
15
?????????? ???? w? ??????? ??????????? ?? ??? ????? w? = L0R0,
??? ?????? ???????? ?? 32 ????. ????? ???????????? ????????????
?????????. ???????? ????? Ln?1 ? Rn?1 , 1 ? n ? 16, ????????? Ln ? Rn
????????? ???????:
Ln = Rn?1,
Rn = Ln?1 ? f ( Rn?1, Kn),
??? ? ? ???????? ?? ?????? 2, ? ??????? f ????? ?????????? ?????.
????????????? ????????? ???????????? ?????????? ??????: ??????????? ????????? ????? ???? ???????????? ? ????:
Rn?1 = Ln.,
Ln?1 = Rn ? f (Ln, Kn).
????? ????????? Ln ? Rn, ????????? ?? L0, R0, ????? ???? ????????????? ?????????? ?????????.
??????? f ?????? ?? 32-??????? ?????? Rn?1 ??? Ln ? 48-????????
????? Kn 32-??????? ???? ????????? ???????. ???? ?? 32 ??? ??????????? ?? 48 ??? ? ???????????? ? ????????:
32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1
????? ???????, ????????? ???? ?? 32-???????? ????? ??????????? ?
48-??????? ?????. ????? ?????? ?????????? ??? 48-??????? ????? ??????? ???????????? ?? ?????? 2. ?????????????? 48-??????? ????
??????? ?? 8 ?????? ?? 6 ??? ?????? B = B1B2B3...B8. ????? ?????? ??
???? ?????? ?????? Bi ???????????????? ? 4-??????? ???? Bi? ? ??????? ??????????????? ??????? (??? ??????? ????? Bi ? ???? ???????)
? ???? ??????.
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
S 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
?????????????????????????
16
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
S 2 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
?????????????????????????
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
S 3 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
?????????????????????????
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
S 4 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
?????????????????????????
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
S 5 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
?????????????????????????
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
S 6 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
?????????????????????????
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
S 7 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
?????????????????????????
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
S 8 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
????????????????????????
?????????????? ?????????????? ????????? ???????. ????? ????
B3 ????? 111011. ?????? ? ?????? ?????? ???????????? ????? x, 0 ? x ? 3,
? ??????? ?? ??????? ?? ????? ? ????? y, 0 ? y ? 15. ??? ????????????17
???? ????? x = 3, ? y = 11. ? ????. S3 ?? ??????????? 3-? ?????? ? 11-??
??????? (?????? ?????????? ? ??????? ????????) ??????? ????? 3. ???
???????? ????????????? ? 4 ?????? ????? ??? 0011. ???????? f ?????????? ??????????? ????????????:
16
7
20
21
29
12
28
17
1
15
23
26
5
18
31
10
2
8
24
14
32
27
3
9
19
13
30
6
22
11
4
25
? ??????????? 32-???????? ????? B1?B2?B3?...B8?.
DES-????????? ???????? ????? ?????? ?? ?????????????????? ????????????. ? ?????? ???????, ???????????? ???????? ? ?????????????? ???????? ?????????? ?????????. ????? ???????????? ??????,
??????? ?????????? ????????? ??????????????? ????? ?????? (256).
????? ????, ??????? DES ???????? ????? ????????, ? ????? ?????? ???????????, ????????????: ?????????????? ????????? ????????? ?????????
??? ????? ???????? ? ???????????? ?????????? ????????????.
?????????? ?????? ????????????? DES (???? 28147?89) ?????????? ???? ? 256 ???.
18
2. ?????????????
? ???????? ?????????????? ??????
2.1. ????? ??????????? ? ???????
? ???????? ?????????????? ??????
?????????????, ????????? ?????, ????? ????? ????????? ??????????. ?? ????????? ???????????? ????? ????? ???????? ?????????????. ??????? ????? ?????? ????????? ? ?????????? ??????? ??? ???????????? ?? ??????????? ? ?????????? ?? ?????????????? ?????. ????
? ????? ??????? ??????? DES ????? ???????????? ? ?????????????
?????????. ????? ???? ?? ????? ????? ?????????, ??????? ?????????
??????, ? ?? ????? ?? ?????? ???????? ?????? ?????????? ?? ?????????????? ????? ???? ?????????? ???????, ??? ????????????? ?????? ??
?? ???? ???????. ????????, ???? ????? ???????? ???????, ????? ????????? ??? ?? ???????????? ??? ??????????????? ????? ? ??? ?? ?????? ????????? ???.
?????? ?????????? ???????, ? ??????? ????? ???????? ???????
?????????? ??? ????????????? ?????????? ??????????? ???????? ?
?????. ????? ??????? ???????? ????????? ? ???????? ?????????????? ??????. ??????? ???? ????? ?????? ???? ???????????? ????? ?
????????. ???? ?????????? ?????? ?? ????????, ?? ????????? ????????? ? ????????????.
???? ???????? ?? ????????????? ??? ?????????? ?????????????
???????. ????? ?? ????????? x ????? ??????????? ??????? f(x). ? ??
????????? f(x) ???????? x ??????????? ????? ??????. ????? ??????????
????????? f(x), ??????????????? ?? ?????? ????? ????? x ? ????????
???????????? ?????????. ?????? ??? ?????????, ???????? ??, ?????
???????????? ? ??? ?????????? ?????????? ?????????? ?? ??? ????
???????????? ???????? ????????? ? ???? ????????? ??????, ??????? ??????? ??? ?????? ???????????? ?????????? ?????????.
????? ?? ??????? ????????, ?????????????? ??? ????, ????????
????????? [2].
19
??? ????? ???? ? ???????? ??????? ???????????? ??? ??????????
??????? ? ???????? ??????? ? ?????????????? ???????????, ? ?????
???????, ? ????????? ?????????? ? ?????? ????? ??????????. ???? ?????
??????? ? ??? ???????, ? ???????? ????? ?? ??? ????? ???? ??????. ? ??
?? ????? ????? ????????? ?????? ?????? ? ????? ???????? ????.
???????? ??? ???? ??????, ???????? ?????????????? ????????
?????? ??????? ? ???????? ?????????????? ??????.
????? ?????????? ????????? ??????????? ? ?????????????? ??????????? ???????????. ??? ???????? ?????? ????? ?????????? ?????
????????? ????????? ?????, ? ??????? ??????? ??????? ???????? ??????????? ?????????? ?????. ????????? ?????????: ??????????
????????. ? ??????? ????????, ??? ??? ????? ???????.
????????? ????? ?????????
20
??????? ???????? ??????? ????????
?
????????
5830247
?
??????????
1422576
?
??????????
3523397
?
?????????
2355495
?
????????
1152843
?
??????
4326567
?
?????????
3768789
?
???????
1754328
?
????????
5377891
?
??????
2844390
?
????????
3155639
?
??????
4166720
?
?????????
1944267
?
?????
2255129
?
?????
4933221
?
????????
2288546
?
???????
2190032
?
??????
3811020
?????? ????? ????????? ????????? ?????????? ????? ????????
????????, ??????? ???????? ?????????? ? ???? ?????. ????????? ??????? ?? ????????? ????? ?????????? ????????? ???????, ?? ?????????? ?????? ????? ??????????????? ????????? ?????? ?????????. ?????? ????????????? ??? ???? ???????????? ??????????. ???????????????, ??????????? ??????? ????, ???????? ?????? ???????? ??????:
?? ?????? ???????? ?????? ??????? ????????, ???????? ???? ???????. ??? ?????? ??? ??????? ?????? ??????????? ??????????? ??????????? ????? ????????? ??????????? ??????????. ?????? ????????? ?????????? ????????? ????? ????????? ? ???? ??????????? ???????????,
????????????? ? ???????????? ? ????????????? ???????? ?????????.
? ???? ?????? ????? ?? ???????? ??????? ???????? ????? ?? ????????????. ???????, ???? ?????? ?????????? ?? ??? ????????????? ?????????????, ??? ??? ???? ???????, ??? ????? ????????? ???????? ??????????. ?????? ?? ???????????? ???? ????????? ????????????? ?????? ? ??????? ?????????.
? ????????? ????? ??????????? ????????? ????????????? ? ???????? ?????????????? ??????. ??? ??? ???????? ?? ?????????????
????????, ????? ?????? ?????????? ??????????? ?????, ? ???????? ?????? ? ????? ??????. ??????? ????? ???? ???? ?????????? ?????????????? ??????? ?????? ?????. ???????? ???????? ????????? ??????????????? ????? ?????? ?????, ??? ??????? ?????? ????????? ??? ??
??????????, ?? ??????? ??????? ?????????????? ?????????? ??????????.
FACTOR (n). ????? ?????????? ???????? ????? n ?? ?????????.
PRIMALITY (n). ?????? ?????? ? ???, ???????? ?? n ??????? ???????
FIND-PRIME (>n). ????? ??????? ?????, ??????? n.
SQUAREFREENESS (n). ??????, ????? ??? ??? ??????? ????????
????? ????? n?
QUAD-RESIDUE (a, n). ??????, ??????????? ??? ??? ?????????
x2 ? a mod n ??? ?????????? x?
SQUAREROOT (a, n). ?????, ???? ????????, ????? ????? x, ???
x2 ? a mod n.
DISCRETE-LOG (a, b, n). ?????, ???? ????????, ????? x, ??? ax ? b mod n.
????? ?????, ???????????? ??? ?????????? ???????????? ? ???????? ??????, ??????? ? ?????????:
21
1. ?????????? ????????????? ???????, ?????, ??? ?? x ????? ????????? f(x), ?? ?? f(x) ???????? x ????????? ????? ??????. ??????? f(x)
??????????? ???????.
2. ????????? ?????? ????????? ??????????? ?? f(x) ???????? x.
3. ???????? ???????????? ??????? f(x) ?????????????? (????????????), ???, ????? ??? ??????????????? ??? ????????? ??? ??????????????, ? ??? ?????????? ?????????? ??????????? ?????? ????????
???????????? ???????? ??????? ? ?????? ?????????, ??? ???????? ?????????? ??? ????.
????? ?????????????? ? ???? ?????? ???????? ??? ??????????
??????????? ?????????????, ? ???????????? ??????? ?? ? ?????????.
2.2. ????????? ???????
?????????? ?????? A = (a1 a2 a3 ...ai ... an), ??? ai ? ????????? ?????
????????????? ?????. ?????, ????? ????, ?????? ????????? ????????????? ????? k. ???????? ??????: ??????? ????? ai ????? ?????????
??????? A, ?????, ????? ?? ????? ? ???????? ????????? k. ? ???? ?????? ????? ????????, ??? k ?????????? ?????? ???????, ? ????????? ai
? ??????? ?????????, ??????? ?????????? ? ??????.
????? ?????? A = (43 129 215 473 903 302 561 1165 697 1523), ?
k = 3231. C ??????? ???????? ????? ?????: 3231 = 129 + 473+ 903+ 561+1165.
? ?????? ???????, ???? ????? ??????-??????? ???? (0 1 0 1 1 0 1 1 0 0)
? ???????? ??????-?????? A ?? ???? ??????-???????:
?0?
? ?
?1 ?
?0?
? ?
?1 ?
?1 ?
(43129 215 473 903 302 5611165 697 1523) ? ? ? = 3231,
?0?
?1 ?
? ?
?1 ?
? ?
?0?
? ?
?? 0 ??
22
?? ??????? ???????? k.
???? ?????? ????? ??????????? ???????? ???????????? ????????
????????????? ????? ? ??????? ???????????? ????????? ?? ???? ????,
?? ?????? ???? ????? ???????????? 10 ????????? ?????????. ?????
???????? ??????-?????? A ?? ???????-??????? ????? ??? ????, ??? ????
????? ???????? ??????????? ????????? k1 k2 k3 ... ?????????? ?????????????? ????? ??????, ? ??? ??? ??????????? ??????????? ????????? ??????????? ?????? ?????? ? ???????: ?? ???????? k ????????
???????? 10-????????? ??????-???????, ??? ????????? ?? ??????? ???????-?????? A ????? ???????? ?????? k. ??? ?????? ???? ?????????????: ?????? ?????????? ? ????? ??????? ?????????????. ? ????????,
????? ?? ?????? ? ??????? ??????? ???????? (210 ?????????). ??????
????????? ????????????? ????? ??????????? ??? ??? ???????????????, ??? ? ??? ?????????? ??????????, ???, ??????????, ????????????.
??? ???? ????? ????????? ?????????? ?????????? ??????????? ?????????, ????? ?????????? ??? ?????????. ? ?????? ?????? ?????????
????? ???? ???????? ????????? ???????. ?????????? ??????????i ?1
??? ??????? A = (a1 a2 a3 ...ai ... an), ? ??????? ai>
? al , ?. ?. ??????
l =1
??????? ??????? A ?????? ????? ???? ?????????? ?????????. ????????, A = (25 27 56 112 231 452 916 1803). ?????????? ?????????
??????? A, ????? ??????? ???? ???????? ????? k, ??????????? (????
????? ??????? ???????). ?????????????, ????? k = 1449. ?????????
1449<1803, ?? ????????? ??????? ??????? ?? ?????? ? ???????. ?????,
??? ??? 1449>916, ?? 916 ??????????? ?????? ? ???????, ??? ??? ?????
???? ?????????? ????????? ?????? 916. ????????? ??????????, ???????? ??? ??????? ?????????? ?????????: (1 0 1 0 0 1 1 0). ?????? ????
???????????? ???? ????????????? ??????, ?? ? ??? ???????????????
?????? ????????????? ????????? ?????? ????????????. ????? ?? ??????????? ????????????? ?????? A ? ?????? B ?? ?????????? ???????:
??????? ????????? ?????? m, ??????? ????? ???? ????????? A,
??????? ????????? t, ?????, ??? (t, m) = 1 ? ?????? ??????? ??????? B
????? ????????? ?? ???????: bi ? ai ?t mod m. ?????? B ??? ?? ?????
???????? ?????????????, ? ?? ????? ???? ??????????? ? ???????? ????????? ?????. ? ? ???????? ????????? ??? ?????????? ????????????
??????? ??? ???????? t ? m.
23
2.3. ?????? ????????????? ????????? ??????
??? ???????????? ? ???????? ?????????????? ??????
????? A ? ????????????? ?????????????????? ?????: (1 2 4 8 16).
i ?1
????? ??????, ??? ai>
? al , ?. ?. ????? ???? ?????????? ????????.
l =1
???????????? ????????? ????? ???????????? ????? ?????????
????????????? ???????? ????:
w1 = (1 0 1 1 0); w2 = ( 0 1 1 0 1); w3 = ( 1 0 0 0 1).
???????? ??????? ????????? ?????????????? ??????? A. ??? ?????
??????? ???????? ?????? m ???, ????? ?? ??? ?????? ????? ???? ai.
???????????? ????? ??????? t ???, ????? (t, m) = 1.
??? ???? ??????????, ????? ???? ?????? ???????? ait ???? ?? ?????? ?????? m (????? ? ?? ??? ?????? ???? ?? ????? ?????????? t). ???????? t = 40 ? m = 37.
???????? ??????? B ?????????? ????????? ???????: bi ? ait mod m.
??? ?????? B = (3 6 12 24 11). ?? ??? ?? ???????? ????????????? ????????, ??????? ???????????? ????? ?????????. ??????? ?????? B ??
???????, ???????????? ?? ???????? ???????? wi , ???????? ????????????? ?????:
?1 0 1 ?
?
?
?0 1 0?
B?W = (3 6 12 24 11) ? ?1 1 0 ? = (39 29 14) = X,
?
?
?1 0 0 ?
?0 1 1 ?
?
?
??? X ? ?????? ???????????? ?????????.
?????? ???? ??????????? ????? ?????????? ?? ?????? ????? ? ????? ???? ?????????? ????????????????. ????? ????, ?????????, ???
???? (?????? B) ????? ??????? ?????????? ???? (??? ?????????? ?????????, ??? ? ????? ???? ?????????? ????? ????????????? ????).
???????? t ? m ???????? ?????????? ??? ?????????? ?????????? ?????????. ?? ??????? ???????? u ?????, ??? t?u ? 1 mod m. ? ????? ??????
????? ????????? u = 25, ??? ??? 40?25 ? 1 mod 37.
24
????? ????????? ?????????? ????????? ????? ????? ??????? ?????????????? ??????? X:
39?25 ? 13 mod 37; 29?25 ? 22 mod 37; 14?25 ?17 mod 37. ??????
?????????? ????? ?????? X?= (13 22 17) ? ??? ???????? ????????? ???????? ?????? A , ???? ?????? B ? u:
3?25 ? 1 mod 37; 6?25 ? 2 mod 37; 12?25 ? 4 mod 37; 24?25 ? 8 mod 37;
11?25 ? 16 mod 37. ???????? ?????? A = (1 2 4 8 16) ???????? ?????????????, ??????? ?? ??????? A ? X? ????? ??????????? ?????????? ?????????:
?1 0 1 ?
?
?
?0 1 0?
?1 1 0 ?
?
?
?1 0 0 ?
?0 1 1 ?
?
?
2.4. ??????? ???????
?????? ? ???????, ??????? ? ?????? ????????? ???????? ?????? ?
???????? ?????????????? ??????, ????? ?????? ?????????, ? ??? ??????, ??? ?????????? ?????????? ??????? ????????????? ? ??????? ?? 1
?? n ????? ?????. ????????? ??????? ???????????? ????????? ???????:
d (A ) =
n
.
log 2 max A
???, ??? ?????????????? ??????? A = (1 2 4 8 16 32 64) d(A) = 7/6.
????????? ????????? ?????????? ??????? ????? ? ??????????????
????? ????? GF(ph), ??? p ? ???????; h ? ?????.
???????? ???? F(ph) ???????? ph ?????????. ???????? ???? F(p) ,
??????? ???????? ???????? ???? F(ph), ???????? p ???????? (0, 1, 2, 3, ...,
p?1) ? 2 ????????: ? mod p ? ? mod p.
??????? ? ?????????? ?????????????? ??????? h ??? ????? F(p),
???? ? ?????? ???? ? ????????????? ? F(p) ?????????: P(x) = 0, ??? P(x)
? ????????? ??????? h, ?? ?? ????????????? ???????? ????????? ?
??????????? ??????? ???????. ??? ?????? ?????????????? ????????25
?? P(x). ??? p h ????????? ???? F(p h ) ????? ???? ????????????
? ????
? cj?i ,
??? 0 ? cj ? p?1; 0 ? i ? h?1.
??? ??????????? ??????? ?s, ??? s ? h ?????????? ?? ??????? ?
???????????? ? ?????????? P(?) = 0.
?????, ????????, p = 3 , h = 2 ? ? ????????????? ????????? x2 ? x ? 1 =
= 0. ???????? ???? F(32) ????? ???????? ???:
0, 1, 2, ?, ? + 1, ?+ 2, 2?, 2? + 1, 2? + 2.
? ??????????? ????????? ???????? ???????????? ? ??????????????
????????? ?2 = ? + 1. ????????, (2? + 1)(?+ 2) = 2?2 + ?+ 4?+ 2 = 2(?+
+ 1) + 5? + 2 = 7? + 4 = ? + 1.
??????? ? ? 0 ???? F(ph) ?????????? ?????????? F?(ph) ????????????????? ?????? ????????? ????????? ???? F(ph), ???? ??????? ?i , i =
=1, 2, 3, ..., ph ? 1 ????????? ??? ????????? ???????? ???? F(ph). ?????????? ????? ??????????????? ??? ????????? log. ????? ?????????
?????????? ??????????? ???????????. ??????????, ????????, ??? 8
???????? ????? ? ? ??????????? ??????? ? ??????? ????????? ? ????
???????:
E
!
"
#
$
%
&
?
?+ ?+
?E
?
? + ? +
?? ??????? ?????, ??? ? ???????? ??????????. ??? ??????? ?????
???? ???????????? ??? ??????? ?????????? ??????????. ??? ????? ?
??????? ?????? ??????? ????????????? ???????? ????, ? ? ?????? ?
???????? ???????? ??????????? ????????, ??? ??????? ???????? ?????? ??????? ????:
O
1
2
?
? +1
? +2
2?
2? +1 2? +2
log ? O
1
2
7
5
6
8
4
3
?????????, ??? ?????????? ?????????? ?????????? ???????? ??????? ???????, ??? ? ?????? ???????????? (?????????? ?? ?????????).
??????? ?????????? ????? ?????????????? ??? ?????????? ????????? ? ??????? ????????? ????. ???????, ??? ???????? ??????????? ??
?????? ph ? 1, ? ?????? ??????? ?? ??????? 32 ? 1 = 8. ??? ???????:
26
log ((? + 2)(2? + 1))= log(? + 2) + log(2? + 1) = 7 + 3 = 10 ? 2 mod 8.
??? ????????????? ???????? ? + 1.
log ((? + 1)/( 2? + 2)) = 2 ? 6 = ? 4 ? 4 mod 8, ??? ?????????????
???????? 2.
????? ?????????, ??? ????? ???????? ? ??????????? ????? ???????? ???????? 2? + 1, ? + 2 ? 2?. ???? s = ph ? 1 ???? ??????????
????????????? ???????, ??????????????? ????????? ?s = 1, ?? ? ???????? ??????????. ??????? ????? ?????????? ????????? ???? ?????
?(ph?1), ??? ? ? ??????? ??????. ??? ?????? ??????? ? (8) = 4.
?????????? ??????????????? ??????. ????? ??????? ?????????
?????? A = (a1 a2 a3 ...ai ... an). ?????????? ????????? ????? ?????????, ????????? ?? h ?????????. ?????? ??????? ? ???, ????? ??? ???????? n ? h ????????? ?????? A ?????, ????? ??? ????? ?? h ?????????
???? ?? ??????? ????????. ??? ???????? ?????? ????????? ??? ??????? ?????: ai = hi?1, 1 ? i ? n. ????????,
A = (1 2 4 8 16 32 64), h = 2, n = 7;
A = (1 3 9 27 81 243 729 2187 6561), h = 3, n = 9.
????? ???????????, ??? ????? ???? ? ?????? ??????? ???????? ?
????? ?????? ?? ?????? ????? ????????.
????? ?????????? ???????? A ????????????? ???????? ?????? ?????????, ??? ??? ??? ???????? ??????????????.
????? n = p ? ??????? ?????. ????????, ??? ??? ???????? p ? ??????
h ? 2 ?????? ????? ????????? ????????? ?????? A = (a1 a2 a3 ...ai ... aP),
??????????????? ????????? ????????:
a) 1 ? ai ? ph?1, ??? 1 ? i ? p.
?) ???? xi ? yi ? ??????????????? ????? ?????, ?????, ??? (x1, x2, ...,
xp) ? (y1, y2, ..., yp), ?? ?xi = ?yi = h, ?????
? xiai ? ? yiai (*)
??? ?????????? ??????? A ????? ????? ai = logg(? + i?1), 1 ? i ? p,
??? ?? ?????? ????????????? ??????????; g ? ?????????? ?????? F?(ph).
??????????? ?????????? ????? ???? ????????? ??? n = ps , ??? p ?
???????; s ? ?????. ????? ????, ??????????? (*) ????? ???? ????????
?? ????? ???????: ?xiai ? ?yiai mod (ph?1).
??? ?????????? ????????????? ???????? ????? ?????? ???????? ??
p-????????? ??????, ? ?????? ?? ??????? ????? ????????? ?????????
h. ??? ???? ????? ?????????? ??? ???????, ?????????? ????? ????????27
??? ???? ????????? ?????????? ??????????????? ???????????? ?????? ????? p ???? h (??????? ????????, ??? ???????? ????????? ????? 0,
1, 2, ..., p ? 1)
?????? 1.
????? ????? ???? F(32) ? ? ?????? ????????? x2 = x +1.???????
?????????? g = 2 ? + 1. ????????? ????????? ????????? ?, ? + 1, ? + 2
???? ?????????????? 3, 6 ? 5, ?? ?????? A = (3 6 5). ???????? ??????
???? ??????? ??????????? 3 ? ?????? ?????????, ?????? 2. ???????
????? ??????? ????????? ??????: (2 0 0), (0 1 1), (0 2 0), (1 0 1). ?????????? ?????????? ???????? ???????:
? 2 0 0 1?
?
?
(3 6 5)? ? 0 1 2 0 ? = (6 3 4 8).
?0 1 0 1 ?
?
?
??? ? ????? ???????????.
????????, ??? ?? ?????????? ?????????? ?? ?????? ph ? 1. ? ?????? ?????? ?? ?????? 8. ????????? ?????????? ?????????:
(2? + 1)6 = ? + 1,
(2? + 1)3 = ?,
(2? + 1)4 = 2,
(2? + 1)8 = 1.
???? ? ?????????? ???????? ?????????? ????????? ?2 ? ? ? 1, ??????? ??????????????:
?2 , ?2 ? 1 = (? + 1)( ? + 2), 2 = (?2 ? ? + 1) = (? + 1)(? + 1); 1 = ?2 ?
?? = ? (? + 2). ?????? ???????? ???????? ????:
(2 0 0), ( 0 1 1), ( 0 2 0), ( 1 0 1).
???????? ?????? ???????? A, p, h. ????????? ???????? ????????
? ? g.
? ????????? ??????????? ????? ????????????? ????????????? ????? ???????????? ???????????? ????????????? ? ? ????? (???) d. ???
???????? ???????? ?????????????? ???????? ??? ?????????? ?????????? ?????????.
?????? 2.
??????? ???????? ???? F(64) = F(26). ????? p = 2, h = 6. ?????????
6
x ? x ? 1 ?????????? ??? ????? F(2), ??? ??? ?? 0, ?? 1 ?? ???????? ???
? 0. ??????, ??? p =2 ???????? + ? ? ???????????. ?????????????, ???
28
???????? ???? F(26) ????? ???? ???????????? ????? ?????? ? ????? ??????????. ????? ?????????, ??? 64 ???????? ???? F(26) ????? ???? ???????????? ? ????
6
?
i =1
xi?6?i, ??? xi ? {0, 1}.
???????? ???? ??? p = 2 ? h = 6 ?????????????? ??? ???????? ?????? ????? 6. ???, ?4 + ?2 + ? + 1 ?????????????? ???????: 0 1 0 1 1 1.
??????? ?????????? ???? g = ? ? ????? ????????????? ??????????.
????? ??????? ?????????? ????? ???? ???????????? ????????? ???????:
??????? ???????? ??????? ???????? ??????? ???????? ??????? ????????
000001
000010
000011
000100
000101
000110
000111
001000
001001
001010
001011
001100
001101
001110
001111
010000
63
1
6
2
12
7
26
3
32
13
35
8
48
27
18
4
010001
010010
010011
010100
010101
010110
010111
011000
011001
011010
011011
011100
011101
011110
011111
100000
24
33
16
14
52
36
54
9
45
49
38
28
41
19
56
5
100001
100010
100011
100100
100101
100110
100111
101000
101001
101010
101011
101100
101101
101110
101111
110000
62
25
11
34
31
17
47
15
23
53
51
37
44
55
40
10
110001
110010
110011
110100
110101
110110
110111
111000
111001
111010
111011
111100
111101
111110
111111
61
46
30
50
22
39
43
29
60
42
21
20
59
57
58
????????? log?? = 1 , ? log?(? + 1) = 6, ?? ?????? A = (1 6). ??????
??? ??? ? ???? ??????????????? ?????? ?? d = 60. ? ?????????? ??????? ???????? ?????? B = (61 3), ??? ??? ???????? bi ???????????
????????? ???????:
bi ? ai ? d mod (26 ? 1).
29
????????? ????????? ???????? ??????? (x, y), ? ??????? x + y = 6.
????????? ???????? ???? ???????????? B ? p = 2, h = 6, ?????????
??????? ????????? ??????:
?6 1 2 3 4 5 0?
( 61 3) ? ?
? = (51 13 8 3 61 56 18)
0
5
4
3
2
1
6
?
?
????????? ?????????? ???????? ?? ??????? ???????????? ????????? hd ?? ?????? 63 ? ???????? ????????? ????? ?????:
51 ? 6?60 ? 6 mod 63,
13 ? 360 ? 31 mod 63,
8 ? 360 ? 26 mod 63,
3 ? 360 ? 21 mod 63,
61 ? 360 ? 16 mod 63,
56 ? 360 ? 11 mod 63,
18 ? 360 ? 36 mod 63.
?? ??????? ?????????? ????????:
?6 = ? + 1 = ?6,
?31 = ?5 + ? + 1 = ? (? + 1)5,
?26 = ?2 + ? + 1 = ?2(? + 1)4,
(?)
?21 = ?5 + ?4 + ?3 + ? + 1 = ?3(?+ 1)3,
16
4
4
2
? = ? + ? + 1 = ? (? + 1) ,
?11 = ?5 + ? + 1 = ?5(? + 1),
?36 = ?4 + ?2 + ? = (? + 1)6.
??? ?????????? ???????? (?) ???????, ??? ?????? ????? ?????? ????
???????????? ? ????: ?k(? + 1)6?k, ??? k = 1, 2, 3, 4, 5, 6. ? ????? ?????
??????? ???????? ?x, ??? x = 6, 31, 26, 21, 16, 11, 36. ????? ???????, ???
?????????????? (?) ???????? ?????????: ?x = ?k(? + 1)6?k. ???? ?????????????????? ??? ?? ????????? ?, ?? ???????: x = k + (6?k)log? (? + 1).
?? ??????? ?????????? ?????????? ???????: log?(? + 1) = 6, ?????????????, x = 36 ? 5k, ?????? ???????? k = (36?x)/5. ?????????:
?6 (x = 6) = ?6,
?31(x =31) = ?(? + 1)5 ,
?26( x = 26) = ?2(? + 1)4 ? ?.?.
????? ????? ????? ?? ???????? ???????? ??????? ?????:
?6 1 2 3 4 5 0?
?
?
?0 5 4 3 2 1 6?
30
?????? 3.
?????????? ????? ????? ?????? ?????????? ? ??????????????
???????? ????? ?????. ????? p = 5, h = 2. ???? F(52) ???????? 25 ?????????. ????? ???????????, ??? ???????????? ????????? ? ???????
F(5) ????????? ???? ???????? ????????? X2 + 2, ??? ??? ??????? ?? 5
????????? (0, 1, 2, 3, 4) ?? ?? ?????????? ? 0. ????? ? ? ?????? ????????. ??? ??????????? ????? ??????????? ?????? ?2 = 3 (????????? ?2 ?
3 mod 5). ??????????? ????????? ???????? g = ? + 1, ??? ????? ???????????. ???????? ??????? ?????????? ??? ????????? ???? F?(52), ???
???????? ?????? ???????, ?????? 0. ??? ??? ??? ???????? ???? ?????
?????????????? ? ???? a1? + a2, ??? a1 ? a2 ? {0, 1, 2, 3, 4}, ?? ???????
?????????? ????? ????????? ????????? ???????:
???????
????????
???????
????????
???????
????????
00
01
02
03
04
10
11
12
13
14
24
18
6
12
3
1
8
4
17
20
21
22
23
24
30
31
32
33
34
21
22
19
11
2
9
14
23
7
10
40
41
42
43
44
15
5
16
20
13
???????? ?????? A ?? ???????: ??????? ai = logg(? + i ? 1), ??? i = 1, 2, 3, 4, 5.
????? ???????
a1 = logg(? + 0) = 3,
a2 = logg(? + 1) = 1,
a3 = logg(? + 2) = 8,
a4 = logg(? + 3) = 4,
a5 = logg(? + 4) =17.
?????? A = (3 1 8 4 17). ??????? ?????? ?????????????? ? ????????? ???????, ????????, ?? ?????? ??????? ???????????:
?a b c d e?
?= ?
? , ????? ??????? ?????? A? = ?A = (1 17 4 8 3).
?b e d c a?
31
?????? ??????? ???????????? ? ???? ?????? d = 20 (?? ?????? 52?
1 =24) ???? ????????? ??????? A?, ? ?????????? ??????? ???????? ?????? B:
B = ( 21 13 0 4 23).
????????? ????? ????????? ????????? ?????? ????? ????????,
????? ??????? ? ?????? ??????? ????? 2 (? ????? ?????? h). ???????
????????? ???????????? ?????????, ??????????????? ????? ???????,
? ?????????? ????????????:
?1 0 0 0 0 ?
?
?
?0 1 2 0 0 ?
(21 13 0 4 23)? ?1 0 0 0 2 ? = (21 12 2 8 0)
?
?
?0 0 0 2 0?
?0 1 0 0 0 ?
?
?
?? ?????? ????? ?????????? ????????????? ?????????: 21 12 2 8 0.
????? ????, ???????? ?????? ????? ???????? p = 5 ? h = 2. ????????? ??????????, ????? ????, ????? d, g ? ?. ??????? ?? ????? ?????????? ? ??????????????? ?????????. ?? ???????? ?? ?????????? ?????
??? hd ?? ?????? 24:
21 ? 2?20 ? 5 mod 24.
12 ? 2?20 ? 20 mod 24.
2 ? 2?20 ? 10 mod 24.
8 ? 2?20 ? 16 mod 24.
0 ? 2?20 ? 8 mod 24.
????? ????????? ?????????? ?? ??????? ?????????? ??????? ???????? gx = (? + 1)x, ??? x ? ???????, ?????????? ?????? ??????? ? ????????? ???????????. ????????? ? ??????????? ????????? ?2+ 2 ? ???????????? ????????? ?? ??? ?????????:
(? + 1)5 = 4? + 1 + ?2 + 2 = ?2+ 4? + 3 = (? + 1) (? + 3),
(? + 1)20= 4? + 3 + ?2 + 2 = ?2 + 4? = ?(? + 4),
(? + 1)10= 3? + 4 + ?2 + 2 = ?2 +3? + 1 = (? + 4)2,
(? + 1)16= 4? + 2+ ?2 + 2 = ?2 + 4? + 4 = (? + 2)2,
(? + 1)8 = ? + 2 + ?2 + 2 = ?2 + ? + 4 = (? + 3)2.
? ?????????? ???????? ?????????????? ?????????, ??????? ?????????? ?? ???????????? ?????? ????????????? ?:
32
?0
?
?1
?0
?
?1
?0
?
1 0 0 0?
?
0 0 0 0?
0 0 2 0?
?
0 0 0 2?
1 2 0 0 ?? .
????? ???????????? ???????? ???????? ?????????:
?1 0 0 0 0 ?
?
?
?0 1 2 0 0 ?
?1 0 0 0 2 ?
?
?
?0 0 0 2 0?
?0 1 0 0 0 ? .
?
?
????????? ???????????? ?????????? ??????? ?????
d (A ) =
p
5
= = 2,5.
log 2 max A 2
33
3. ????????????? RSA
3.1. ???? ?????????????
???????? ?????? ???????????????? ???????? ? ???????? ??????
???????? ????????????? RSA (Rivest, Shamir, Adleman). ???? ???????
??????? ? ???, ??? ????? ?????? ????????? ???????????? ???? ???????
????? ?? ???????????, ?. ?. ????? ??? ???????????. ???? ?? ???? ??????? RSA ????????????? ??????.
????? p ? q ? ??? ???????? ????????? ??????? ????? (?????? ???????? ?? 100 ?????????? ????????). ?????????:
n = pq ? ?(n) = (p ?1)(q ?1),
??? ? (n) ? ??????? ?????? ?? n.
???????? ?????????? ??????? ????? d >>1, ?????, ??? (d, ?(n)) = 1,
? ??????????? e, 1 < e < ?(n), ??????????????? ?????????:
ed ? 1 mod ?(n).
????? n, e ? d ?????????? ?????????????? ???????, ???????????
???????????? ? ??????????? ????????????? ??????????????.
????? n ? e ???????? ???????? ????, ? p, q, ?(n) ? d ?????????
???????. ??? ???? ????????? ??????? ???????? ? ???? ??????????????? ????????. ???, ???? ???????? p (?, ???????, n ? e), ?? ?????????
????? ??????? ??????????? ??????:
q = n/p; ?(n) = (p?1)(q?1);
d ????????? ?? ???????: ed ? 1 mod ?(n).
???????????? ?????????????? ??????????? ????????? ?????????
?????? S ? ??????? e ?? ?????? n.
????????????? ??????????? ??????????? ?????????? ???????????
???? ? ??????? d.
??? ???????????? ???????? Se ? C mod n. ????? C ? ????????????? ???????? ??????.
??? ????????????? Cd = Sed = S1+?(n)k = S?(n)k S ? S mod n. (?)
34
?????????????? (?) ????? ?????, ??? ??? ?? ????????? ed ? 1 mod ?(n)
???????, ??? ed = 1 + ?(n)k, ??? k ? ????????? ?????.
??????.
????? p = 11, q = 13. ????? n = 143, ?(n) = 120.
??????? d ?? ???????: ( d, ?(n)) = 1, ????????, d = 37, ????? ??
?????????: ed ? 1 mod ?(n) ??????? e = 13. ?????????????,
13?37 = 481 ? 1 mod 120.
??? ???????????? ??????? ???????? ??????, ??????? ???????????,
????????, ?????? S = 42.
4213 ? 3 mod 143, ?. ?. ???? ????????? C = 3.
??? ????????????? ???????? ????? 3 ? ??????? 37:
337 ? 42 mod 143.
????? ???????, ????????? ?????????? ????????? ???????? ????????? ???? ?????????.
3.2. ????????????? ??????
? ???????? ?????????????? ?????? ??? ??????????? ?????
?????????? ????????? ??????? ?????, ? ??????? ???????? ???????????? ????????? ??????????? ?? ????????? ??????.
1. ????? ????????? ????????? A, B, C, ???????????? ?? ?????? ???????????. ??? ????? ??????? ????????? ????? ??????? ????? p, ?????, ??? p ?1 ?????????????? ?? ??????? ??????????? ? ?????? ???????. ????? ???? N = p1 p2 p3?pk ?????????? ?????????? ??????. ?????? ?? ?????????? ???????? ??? ????? ??????? ? ??????? ??????? ?
p ?1 ???, ?????:
a1a2 ? b1b2 ? c1c2 ? 1 mod (p?1).
????? ??????? A ????? ???????? ????????? S ???????? B. ?? ???????? ???? ????????? ??????????? ? ??????? a1: Sa1 ? S1 mod p ? ???????? ??? B. ???, ? ???? ???????, ???????? ?????????? ????????? ??????????? ? ??????? b1 : S1b1 ? S2 mod p ? ?????????? ??? A. A ???????? ???
? ??????? a2 ? ???????? ??? B: S2a2 ? S3 mod p. B ???????? ??? ? ???????
b2 ? ?????? ?????????. ?????????????? ?????????? ??????? ?? ?????????: a1b1a2b2 ? 1 mod (p ? 1).
??????. ????? ???????? A, B ? C ??????? ????? p = 103. ??? ?????
???????, ?????? 103?1 = 102 ? ????????? ?????, ??? ??? ??????????????
? ???? ???????????? ??????? ????? ? ?????? ????????: 102 = 2?3?17.
?????? ?? ?????????? ???????? ???? ????????? ??????, ????????:
35
A: a1 = 25, a2 = 49,
B: b1 = 19, b2 = 43,
C: c1 = 35, c2 = 35.
????? ?????? A ???????? ? B ????????? S = 67. ?? ???????? ??? ?
??????? 25 ? ??????? ??????? ?? ?????? 103: 6725 ? 86 mod 103.
B ???????? ??? ? ??????? b2 = 19 ? ?????????? ????????? ? A:
8619 ? 96 mod 103.
A ???????? ?????????? ????????? ? ??????? 49 ? ???????? ??? B:
9649 ? 21 mod 103.
B, ??????? ?????????, ???????? ??? ? ??????? 43 ? ?????? ????????
?????: 2143 ? 67 mod 103. ????? ???????, S = 67.
???????? ?????? ? ???? ??????? ???????? ?????? p. ??????????? ????? ??????? ???????? ??????? ????? ??????? ?? ?????? ???????? ? ???????.
2. ????? ??????? ??????????? ???? ? ????????? ?????????? ?????
????? ????? ????? ?????????????. ???? ?? ?????? ?????? ??????? ???????? ???????? ????? g ? p ??????? ????????????, ?? ??? ?????
?????????? ????? ???? ????????? ???????. ????? ??????? A ???
???????? ???? k1, ? ??????? B ???? k2 (??? ?????????????? ?????????
????? ?????????). A ???????? ? B ????????? gk1 mod p, ? B ???????? ?
A ????????? gk2 mod p. B ???????? ?????????? ????????? ? ??????? k2,
? ? ? ??????? k1. ? ?????????? ??? ?????????? ?????????? ????? ????:
gk1k2 = gk2k1 ? K mod p, ????? ???? ???????? ????? ??????????? ?? ????????? ?????? ? ?????????????? ????? ???????????? (????????????) ?????????????.
36
4. ????????????????? ?????????
? ???????????? (????????????) ????????????????? ???????? ??????????????, ??? ??? ????, ??????? ???????????? ????????? ???????????, ????????? ???????? ???? ????? ? ???????? ???????? ???? ????????? ?? ??????? ??? (?????????????, ??????, ????????????????).
???????????? ? ???????? ?????? ??????????? ????????? ?????
?????, ???????? ? ??????? ????????????????? ???????. ? ?????????? ????????? ????????????? ? ????????????? , ???????????? ???????????? ??????? ??????????? ????? ???????????, ??????? ?? ??????
???????? ???? ?????, ? ???????? ?????????? ????? ??????????? ???????????. ?????????????????? ???????? ?????????? ?????? ???????????, ???????????? ????????????????? ?????? ??? ??????? ?????????????? ?????, ???????? ?????????????????? ???????????.
4.1. ????? ? ?????????
?????????? ??????, ? ??????? ????????? ????? v1, v2, ?vk ????????
??????????? ???????????? ?????????????? ????????? ????? B (???????). ??? ???? ????? ?????????????????? ?????? ??????????????
???????????? ?????????, ????? ?? ??????????? ????????? ?????? B
????? ???????????????? ?????? ????????? ? ????????? ?????? ???
????????????.
?????? B ???????? ????????? ????? N = PQ, ??? P ? Q ? ???????
??????? ?????. ?????? ?? ?????????? vi (i = 1, 2, 3, ?, k) ????? ???????? ???? ???????? ni = piqi, ?????? ??????????, ????? N > ni. ?????
??? ??????, ??? ? ????????? ??????? ???????? ? (N) ? ?????? ? ? (ni) ?
??? ?????????. ????? ???? ?????? ???????? ???? ???????? ????: S, ?
?????? ? si ? ????????? ?? ???????:
0 < S < ? (N) , ( S, ? (N) ) = 1 ? ?????? ?
0 < si < ? (ni), (si, ? (ni))= 1 ? ?????????.
????? ?????? ? ????????? ??????? ???? ????????? ????? T ? ti ?? ?????????:
ST ? 1 mod ? (N), 0 < T < ? (N) ? ??????,
37
st ? 1 mod ? (ni), 0 < t < ? (ni) ? ?????????.
????? ???? ???????? ??????? ??????????? ?????????? ????? ? ????????? ???????:
B: N, S
vi: ni, si.
????? ?????? ????????? ???????? vi ????? ???????? ????????????
m ??????? B. ?? ??????? ??? ??????? ????? ????????? ?????? (??????? m ? ??????? ti ?? mod ni, ? ????? ???????? ?????? ???????: m1 ? mti
mod ni, m2 ? m1S mod N. ????????? m2 ?????????? ?? ????????? ??????
?????. ??????, ??????? ????????? m2, ??????? ?????????????? ??? ????? ????????? ?????? T, ? ????? ???????? ?????? ????????? vi. ?
?????????? ????????:
m3 ? m2T mod N, m4 ? m3ti mod ni.
??? ???? m4 = m, ?. ?. ?????? B ?????????????? ?????????? ??? ????????????, ??? ???? ?????? ? ?????????????? (??????) ?????????. ???
?????? ?? ???????? ??????? ????????? ? ?????? ?????????? ???????????? ????????. ???? ???????? ?? ???????? ?????????? ????? ??????, ???
?????? ?????? ????? N < ni, ?? ??????? ??????? ????????, ??????? ???
?? ?????????, ???? ?????? ????? ??????? ??????? ???????????.
??????.
????? ?????? ?????? ??????? ????? P = 23, Q = 11; ???????? v: p = 13,
q = 7. ????? ???? ? ??????, ? ???????? ????????? ??????? ???????
??????: ?(23?11) = 220; ? (13?7) = 72, ????? ???????? ???????? ? ????????? ????????? ?????, ????????: S = 71, T = 31; s = 29, t = 5. ??????? ??????????? ?????: P?Q = 253, p?q = 91, S = 71, s = 29. ?????????
?????? ??????? ???????? ????? T = 31, ? ????????? ?????? ????????? t = 5.
????? ???????? ????? ???? ????????? ????????? ??????? ? ????
????? m = 41. ?? ??????? ??? ????? ????????? ?????? t, ? ????? ???????? ?????? ??????? S:
415 ? 6 mod 91, 671 ? 94 mod 253.
??? ????????? (????? 94) ?? ????????? ?????? ?????????? ???????.
?????? ?????????????? ????????? ??????? ????? ????????? ??????
T, ? ????? ???????? ?????? ????????? s:
94 31 ? 6 mod 253, 629 ? 41 mod 77.
?????? ????????? ???????? ????????? ? ???? ????? 41.
38
4.2. ??????????? ???????
?????????? ???????? ??????????? ????????, ??? ??????? ?????????????? ?????????? ????????????????? ?????????? (????????? ??????? ????????? ????). ????? ? ??????????? ???????? ????????? ???
???????: ????, ?????????????? ?????? ?? ????? ?????, ?????????? ??
???? ? ??????? ??????????? ????????, ??????????, ????????? ?? ????? ? ????? ????????? ????? ? ?????????? ?? ????????, ? ??? ????????
(??????? ??? ?????), ?????????? ??????????? ???????? ? ??????????
?? ? ???? ??? ???????? ? ?????????? ?? ???? ????.
????? ???????????? ??? ??????????: ?????? ?? ?????, ?????? ? ???????.
??? ???????? ???????????? ???????? ?????????? ??????????:
? ???????????? ?????, ? ???? ????????????? ????????? ???????
????? ??? ?? ?????? ????????? ???????, ??????????? ??????, ???????
????? ????????? ???????? ? ?????????? ????????,
? ????????????????? ?????????? ? ???? ????????????? ????????????? ???????? ???????, ??????? ???????????? ? ????, ? ??????????,
??????????? ??? ????????.
???, ?? ?????? ??????, ?????????????? ?????????? ??????????????
? ??????? ??? ?????????? "???????????" ??????? ? ???????????? ??
?????? RSA.
???? ???????? ??? ??????? ??????? ????? p ? q, ???????? ???? e
? ????????? ????????? ???? d ?? ???????: ed ? 1 mod ? (N = pq), ?????
??????? ????????? N, e ? ????????? ????????????? ??????? f : ZN ? ZN.
????????? ??????? ????? ??????? ? ?????????? ? ????????? m ??????? ????????????: s ? md mod N. ? ?????????? ???????? ???????????
??????? ?????? d ????????????? ???????? ???????????? ? 1 ????????
??????? (?????, ??? ??????, ?????? ? ?.?.). ??? ????????? ??????????
???????? ?????? ? ?????? ????????? ?????????? ?????? ??? ?????????? ? ????. ????? ??????? ???????? ???????????? ????????? ??????????? ???????? ????????????? ???????????.
??? ?????? ?? ????? ?????????? ???????? ????????? ????????? ????? n ? ZN ? ????????? f(n).?????????? ????? ???????? ?? ????? ??????? ?? ????????, ?. ?. f(n) d . ?????? ???? ?? ?????? ?????? ? ????
???????? f(n), ?? ????????? ??????? ?????????????????, ??? ??? ????,
?????? ?? ????? ?????????? ?????, ?????????? ?????????? ????????
(??????????? ??????) ????????. ??? ?????????? ????? ?????????? ???????? ????????? ????????? ????? r ? ZN., r ? 0, ????????? f(n)r e mod
39
N, ? ???????? ????????? ? ????. ???? ????????? ???????? f(n) dr mod N
? ?????????? ??? ??????????. ?????????? "???????" ??????????? ????????? r ? ???????? ??????????? ???????? ? ???? (n, f(n) d mod N).
???? ????????? ?? ????? ?????????????? ? ?????????.
? ?????????? ??????? ?????????? ???????? ???????? ???????????
???????? (n, f(n) d mod N), ??????? ??? ????? ????????? ??????????????, ???????? ?? n ???????? f(n), ? ????? ???????? ??????? f(n) ?
? (f(n) d) e mod N.
?????? ??? ????, ????? ????????? ?????? ????? ? ??? ?? ?????????
?????????? ???????, ???????? ?????????? ??????????? ???????? ? ????
??? ???????? ? ?????????? ?? ???? ????. ???? ?? ??????? ?????????, ??
???? ?? ????? ????????? ??? ???????? ? ????????? ???????? ????? ??
???? ????????.
??? ?????? ?? ????? ? ????? ???????? ????????? ???????? f(n)d r mod N,
??????? ??-?? ???????????? ????????? r ???????????? ????? ??????
????????? ?????.
??????.
????? ?????? ??????? ??????? ????? p = 17 ? q = 19. N = 323,
? (323) = 288. ???????? ???? e = 11, ????????? ???? d = 131 ? ????????????? ??????? f(x) = x2 mod 323.
??????? ??????????? N = 323, e = 11 ? ??? ??????? f.
??? ?????? ?? ????? ?????????? ???????? ????????? ????? n = 25,
????????? f(25) = 252 ? 302 mod 323 , ???????? ??????????? ????????? r = 20, ????????? f(n)r e mod N, ??????? ? ?????? ??????? ?????
?????: 302 ? 2011 mod 323 ? 74 mod 323 ? ???????? ? ???? ????? 74. ????
???????? ?????????? ????? ? ??????? d = 131 ? ????????: 74131 ? 63 mod 323.
?????????? ??????? ??????????? ????????? r = 20, ????? ?????????:
f(25)131?310 mod 323. ????? ???????, ??????????? ?????? ???????????
???????? ????? ???: (25, 310). ??? ???????? ???????????? ????????. ????
???????? ????? ?????????????? ????????? ??????????? ????????, ?? ??
????? ????????? F(25) ? 302 mod 323 ? ????? 31011 ? 302 mod 323. ?????????? ?????????? ???????? ??????????????? ? ??????????? ????????.
?????? ??? ???????? ????, ??? ??? ???????? ?? ?????????????? ? ??????
????????, ???????? ?????????? ?? ? ????, ??????? ?? ??????? ?????????, ??? ??? ??????? ???????????? ? ??????? ? ????????? ???? ???????? ??????? ?? ???? ????????.
40
4.3. ???????? ??????????? ?????????
???????????? ??????????
? ????????? ???????, ??????, ??????????? ?? ????, ?????? ????
?????????? ????????????, ????? ?? ???? ?? ????????? ?? ??? ?????????? ?? ????????? ??????????? ?????????. ??? ????? ?????????? ??????????? ?????, ?????????? ????????? ?????????. ? ????????, ????????, ????????????? ? ?????????? ???????, ????? ????????? ??????? ????????? ????????? ??????????? ????????? ? ????? ??????????????? ??? ????????? ????????? ????????. ???????? ????????? ?????????????? ???????? ????????. ?????????? ????????, ????????????
?????? ? ?????????? ?????????? ?????????????? (??????????????
????, ??? ????? ????????? ??????? ????????? ??????).
????? p ? q ? ??????? ?????, ?????? q ????? p ? 1. ????????, p = 23,
q = 11, ??? p = 59, q = 29. ????? ??????? g ?????, ??? gq ? 1 mod p. ???
??????? ??????? g = 2, ??? ??? 211 ? 1 mod 23, ??? ??????? ??????? g = 4,
??? ??? 429 ? 1 mod 59.
?????? ????????? ???????????, ??? ????? ??????????? ?????
????? ??????????, ????????, ?????? ? ?????. ????? ???????? ????????? ????????? ????? x ?? ????????? ?????: {0, 1, 2, ?q?1} ? ????????? ???? y = g?x mod p, ??????? ??????? ?????????.
????? ????? ???????? ????????? ????? k ?? ????????? {0, 1, 2, ?q?1},
????????? r = gk mod p ? r ?????????? ? ????.
??? ???????? ????????? ????????? ?????? e ?? ?????????
{0, 1, 2, ?2t?1},
??? t ? ????????? ????? ? ???????? e ? ?????.
????? ????????? s = k + xe mod q ? ???????? s ? ???? ?? ????????.
??? ????????? ???????????: r = gsye mod p ?, ???? ??? ???????????,
????????? ?????????????? ?????, ??? ??? ??????? ????????? ??????,
? ????????? ?????? ?????????????? ???????????.
??????.
????? p = 59, q = 29, ????? ????? ????? g = 4. ????????? ????? x,
?????????? ??????, x = 9, ????? y = 4?9? 17 mod 59. ????? 17 ????????
???????? ?????? ?????.
????? ????? ???????? k ????????, k = 12, ????????? r = 412 ? 35
mod 59 ? ????? r = 35 ?????????? ? ????. ????? ????????? ?????? ????
e = 10, ??????? ?? ???????? ? ?????. ????? ?????????: s = 12 + 9?10
mod 29 ? 15 mod 29. ????? s = 15 ?????????? ? ????.
41
??? ????????? ???????????:
4151710? 57 ? 12 ? 35 mod 59.
????????? r = 35, ?? ?????????????? ???????????.
4.4. ?????????? ???????
?????????? ??????, ????? ???????????? ????? ??? ?????-???? ?????? ??????????? ?? ????????? ???????? ????? ??????????? ? ????? ??????????????? ??? ????????????? ?????????? ?????. ?? ????? ????????? ???? ????????? ???? (???????? ??? ?????????? ?????????????????? ????????) ?? ????????? ????????? ? ??? ????????? ???????
?????????? ??????????? ???, ????? ??? ????? ????? ??????????? n
?????? ???? ??? ???? ??? ?????????, ???? ????????? ?????? ?? ?????
h ???????????.
???????? ?????? ???????????? ?????? ???????? ??? h = n, ?. ?. ?????
???? ????????? n ??????????? ? ????????? ??????? ???? n ??????????
?????, ????? ??????? ????????? ????????? ???? S. ??????? ????????? ??????? ????? p ? ????? ????????? ???? ?????????????? ? ????
?????? (s1, s2, s3, ?, sk) , ??? ??? si ???????? ?????????? ???? GF(p).
???????? ????????? ???? ?? n ?????????? ????????? ???????. ????? ???????????? ???????????? ????????? ?????: (a11, a12, a13, ?, a1k)
? ???????? ?????????? ????? 1-?? ??????????,
(a21, a22, a23, ?, a2k) ? ???????? ?????????? ????? 2-?? ??????????,
???????.
(an?11, an?12, an?13, ?, an?1k) ? ???????? ?????????? ????? n?1-?? ??????????.
? ?????????? n-?? ?????????? ???????? ???????? ??? ?????????
?????????? ????? ?? ?????????? ???????:
an1 = s1 ? a11 ? a21 ? a31 ? ? ? an1 mod p.
an2 = s2 ? a12 ? a22 ? a32 ? ? ? an2 mod p.
????????????????
ank = sk ? a1k ? a2k ? a3k ? ? ? ank mod p.
? ???? ?????? ?????? ??? ???????? ???? ?????????? ????? ?? ?????? p ??????? ?????? ????????? ????.
??????.
????? p = 29 ? ????????? ???? ????? ???: (26, 13, 21, 8, 0, 18). ????????? ????????? ??? ?? 5 ?????????? ??? ??????? 5 ???????????. ???
?????? ??????? ?? ??? ????????? ????????? ????? ?? ?????? 29 ?????
????????? ?????????:
42
(26, 0, 13, 11, 23, 25)
(2, 7, 15, 12, 27, 6)
(1, 3 , 24, 6, 0, 16)
(12, 2, 7, 0, 7, 0)
??? ??????????, ?????? ?????????? ??????????? ???????? ?????
???:
(14, 1, 20, 8, 1, 0).
????? ???????????, ??? ???????? ???? ?????????? (?????? ???????
???????????? ?? ?????? 29) ???? ?????? ????????? ???? (26, 13, 21, 8,
0, 18)
??????? ????????, ??? ????????? ??????? ?????????? ????? ? ????????????? ?????? ??????? ?????? ?? ???????? ?????? p ? ????? ????????? k ? ??????????? ?? ??????? ?? ?????????? ??????????? n.
?????????? ??????, ????? h < n. ??????? ????????? ????????? ??????? ????? ????????? ??????.???????? ????????, ????????? ? [2].
?? ??????? ?? ????????? ?????????? ? ????????? ??????? ?? ????????.
??????? n ?????????? A1, A2, A3, ?, An. ????? m i, i = 1, 2, ?n, ?????
?????, ??????? 1, ?????, ??? (mi, mj) = 1 ??? i ?j. ????????? ? ? ???????????? ???? ????? mi, ?. ?. ? = m1m2m3?, mi, ?mn.
????????? ????? Mi ? ???????????? ???? mj (j = 1, 2, ?, i?1, i+1, ?, n),
????? mi, ?. ?. Mi = M / mi. ???????? ???????? Ni ?? ???????: MiNi ?
?1 mod mi. ????????? (Mi, mi) = 1, ?? ??????? ?????? ?????????? ? ???
Ni ????? ???????.
???? ??????? n ????????? ????: x ? ai mod mi, i = 1, 2, ?, n, ai ?
?????, ?? ????? ??????? ???? ????????? ????? ???:
x=
n
? ai M i Ni .
i =1
????? ????, ??? ??????? ????????????, ?. ?. ????? ?????? ???????
y ????????????? ?????????: y ? x mod M.
????? ?????? h ????????????? ?????, 1 < h ? n. ????????? ?????
min(h) ? ?????????? ?? h ???????????? mi, ? max(h?1) ? ?????????? ??
h?1 ???????????? mi. ???? ????????? ???????:
min(h) ? max(h?1) ? 3 max(h?1) ( ? )
? max(h?1) < c < min(h) (??)
?? ????????? {a1, a2, ?, at}, ??? ai ? c mod mi, ???????? (h, n) ?????????
????? ??? ? [ 2 ]. ??? ????????, ??? ???? c ? ????????? ????????? ????,
43
? ai ? ????????? ?????, ????????? n ??????????, ?? ????? h ?? ?????????? ?????? ???????????? ???????? c ?? ??? ??????????, ? ?????
h?1 ?????????? ??????? ??? ?? ?????? (??? ???????? ?????????). ???
???? ??? ?????? ? (?) ????????, ??? ??????? h?1 ?????????? ????????? ????????? ???? ?? ????? ??????????.
??????.
????? n = 5 ? m1 = 97; m2 = 98, m3 = 99, m4 = 101, m5 = 103.
??????? h = 3 ? ???????? min(3) = (97 ? 98 ? 99) = 941094; max(2) =
=(101 ? 103) = 10403. ??????????? (?) ?????? ???:
941094 ? 10403 = 930691 > 3 ? 10403 = 31209.
????????? ????? ? ?????? ?????? ? ???????? (??). ????? ??? ???????? ?????????? ??????????, ???????????? ??????, ??????? ????????
???????? ai (i = 1, 2, ?, 5) ?? ??????? ai ? c mod mi ? ?????? ?????????
??????? ???? ??????????: a1 = 62, a2 = 4, a3 = 50, a4 = 50, a5 = 38.
????? ?????? ???? ?? ???? ??????????, ????????, A2, A3 ? A4 ???????? ???????????? ????????? ???? c ?? ????? ??????????. ?????????
?????? ???????? ????? ?????? ???? ???????? mi, ?? ??? ?????????:
M2? = m3? m4 = 9999; M3? = m2? m4 = 9898; M4? = m2? m3 = 9702,
? ????? ??????????????? ???????? Ni: N2 = 33, N3 = 49, N4 = 17. ?????
???? ??????? ???????? y = 4 ? 9999 ? 33 + 50 ? 9898 ? 49 + 50 ? 9702 ? 17 =
=33816668. ????????? ???? ??????????? ?? ?????????: c ? y mod (m2 ? m3 ? m4).
????? ???????,
c ? 33816668 mod (98 ? 99 ? 101) ? 500000 mod 979902.
???? ????? ????? ?????? ?????? ????????, ????????, A1, A4, A5, ??
??? ???????? ??? ?? ????????? ???? ? = 500000.
????? ?????? ???? ????????, ????????, A2 ? A5 ???????? ????? ????????? ???? ?. ??? ????????? ???????? y = 4 ? 103 ? 59 + 38 ? 98 ? 41 =
?176992 ? 5394 ? ? mod 10094. ??? ????????, ??? ???????? ?????????
???? ????????? ?? ???????: 5394 + i ? 10094, ?? ???????? i ?? ?????.
?????????? ???????? i ???????????? ??? ????? ????? ?????:
min ( h ) ? max ( h ? 1) ? 1
max ( h ? 1)
.
??? ???????????????? ??????? ????? ????? ????? ????? 89, ?. ?. ????
?????????? ??????????? ????????? 89 ????????? ?????. ? ???????? ???????? ?????????? ????????? ????? ???? ??????? ??????????? ???????.
44
?????????? ??? ???? ?????? ?????????? ?????????? ?????, ????????? ? [9].
????? ? ?????? ????????? ???????? n ???????????, ?? ??????? ??
??? ????? ????????? ?? ????? ?? ????? ??????. ????????? ????? ?????????????? ????? ???????????? ?? ????????????? ???????, ??????
???, ??? ?? ???? ????????? ?? ????? ??????? ?????? ?????????? ?????.
????????? ????? ???? ????????????, ???? ????????? h ??? ????? ??????????? (?. ?. h ??????????? ?????? ????? ?????? ????? ??????????), ??? ???? 1? h ? n. ? ?????????? ????? ????????? ?????? ?????
???????? ?? ????? ??????, ???? ? ????, ??? ???? ???? ???????? ??????
?????? ?????????? ?????.
????????? ?? ???????? ?????????? n ? h ?????????? ????? ??????
h ? ???? ??????? ????????????? ???? ?????? ????? ????????????.
??????? ?????????? ??????, ????? n ? ???????? ????? ? h = (n+1)/2.
1. ???????????? ???????
????????? 1. ????????, ??? n-?????????? ???????????? ??????
???? q ???????? ???????? n-????????? ??????????, ?????????? ????? q ?????? ? n ? q ?????. ?????? ??????????? ????? ????? n ???? q
????? ???????? ????? ???? ?????, ?????????? ?????? ????????, ?
?????????? R(n, q).
????????? 2. P( a, b ) ? ?????????? ?????????? ???????????? ?? a
???????? ??????? ???? ? b ???????? ???????, ??? ?????:
P ( a, b ) =
( a + b )!
= C(aa +b ) = C(ba +b ) .
(1)
a !b !
??? R(n, q) ????? ?????????? ????? P(n?q, q)
?????????? ???????????? ?????? ? ??????, ????? n ? ???????? ?????, ? ????? h = (n+1)/2.
??????? 1. ???? n ? ???????? ????? ? ????? h = (n+1)/2, ????? ?????????? ?????????? ????? k ????? ????? n ????????? ???????? ?????
???? h, ? ??????
n!
? n +1 n ?1 ?
k = P?
,
,
?=
2 ? (( n + 1) / 2 )!(( n ? 1) / 2 )!
? 2
(2)
? ??????? ????????????? ?????? ????? ???????????? ?????????????
???????? ??????? ???????????? ???? R(n, q).
?????????????? ????????????? ? ????????????? ????????? ????.
45
?????? 1.
????? n = 5 ? h = 3. ???????? ??????? ??????????? 5-?????????
????? ???? 3 , ?. ?. R (5, 3).
??????? 1
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
1
1
1
1
1
1
1
0
0
0
0
2
1
1
1
0
0
0
1
1
1
0
3
1
0
0
1
1
0
1
1
0
1
4
0
1
0
1
0
1
1
0
1
1
5
0
0
1
0
1
1
0
1
1
1
? ??????? ??????? 1, 2, 3, 4, 5 ?????????? ????? ???????? ???????, 1), 2), 3), ...?????????? ?????? ??????. ??????? ??? ??????? 3-?? ????? ???????. ?? ????? ????? ? ???????? 1), 4), 5), 7), 8),
10). ????? ?????? ?????? ???????? ??????? ????? ?????? ?????
?????? ? ????? ????????? ?????? ????????? ???? S. ??? ???? ??????? ???? ?????? ???????? ??????? ?? ????? ??????? ??????. ?????????? ?????? ? ?????? ??????? ????? 10. ??????? ? ???????????? ???? ????????????? ??????? ??????, ??????? ????? ??????
???? ???????.
2. ??????? ? ???????????? ???????
? ????????? ??????? ????? ????????? ????? ??????? ???????, ?????????? ?? ???????????? ?????? h. ??? ????? ???????????? ? ??????? ????????? ???????.
??????? 2.
???? ???????????? ????? ?????, ??????? ?????, ????? n (?????
??? n ? ????? ????? ????????????? ?????) ? ????????? ??????????
??????? ??? ?????? h, ?? ?????????? ?????????? ????? ????? ???????
?????????? ? R(n, n?h + 1), ?. ?.
n!
k = P ( h ? 1, n ? h + 1) =
.
(3)
( n ? 1)!( n ? h + 1)!
46
?????? 2.
????? n = 6, h = 2. ???????? ??????????? ???????? ??? R(6, 5)
??????? 2
1)
2)
3)
4)
5)
6)
1
1
1
1
1
1
0
2
1
1
1
1
0
1
3
1
1
1
0
1
1
4
1
1
0
1
1
1
5
1
0
1
1
1
1
6
0
1
1
1
1
1
?????????? ????? ???? ???????? ???? ???, ?????????? ??? ???????. ?????????????? ????????????? ? ????????????? ????????? ?????.
??????? 2 ???????? ?????????? ??????? 1. ?????????????, ????
???????? ? ??????? 2 ???????? h = (n +1)/2, ?? ???????
R(n, (n +1)/2).
??? ??????? ???????? ???????????????, ??? ??? ???? ??????? ????????????? ?????? ????? ??????? ??????????? ???????.
??????????????.
??????? i-? ??????? ?? R(n, q) ? ????????? ??? r (i). ??? ??? ?????
?????????? ??? ????? ?????? ? ???? ? ?????????? ?r(i)? ?????????
???????? ?????????? ???????? r (i) ? r (j) ? ???? ??????????????? ??????? ??? ?? ???????????, ??? ?????????? ???????? ???????? ?????
?????????? ??????????????? ??????????? ???????? r(i) ?
r(j).?????????? ?????? ???????? ?????????? «v» ??? s ?????????:
r(i1) v r(i2) v r(i3) v...v r(is).
??????? ?????? ??????? ????? ????? n ???? q, ??????? ?? ?????????? R(n, q). ?? ???? ??????? ??????? ???????????? ??????? ? ??????? i, ?. ?. r(i). ????????? ??? ???. ????? ??????, ??? ??? ????? i
r (i ) = P ( n ? q, q ? 1) = Cnq??q1 .
( 4)
??? ???? ?????????? ????? 2 ???????? ? ???????? i ? j ?????
r (i ) vr ( j ) = Cnq??11 + Cnq??21 .
??? ???? ?????????? ????? s ???????? ? ???????? i1, i 2, i 3, ...is
??? 1 < s < n?q+1 ?????
47
r (i1 ) vr (i2 ) vr (i3 ) v...vr (is ) = Cnq??11 + Cnq??21 + Cnq??31 + ... + Cnq??11.
(5)
???? s = n?q+1, ?? ????? ( 5 ) ????? ????? ?????????? ????? ?
R(n, q), ?. ?.
n!
Cnq =
.
q !( n ? q )
?????????????, ????????? ???? ? ( 5 ) ????? 1.
???? ????? ?????? s ???? ( 5 ) ?????? n?q+1, ?? ????? ( 5 ) ??????
???????? ( 1 ), ??? ?????????? ???????, ??? ??? ??????? ????? ???????, ???? ?? ??????, ??? n?q+1 ?? ????? ??????? ?????? ??????. ?
??????? ??????, ???? q = (n+1)/2, ?????, ??? ??? s = (n+1)/2 ? ???????????? ??????? ?????? ????? ?????? ??? ??????????? ?????????.
??????????? ???????? ????????????? ????????? ?????? (?????????? ?????? ?????????? ?????) ?????????? ????? ? ????????? ????? ????????????? ??????? ??? ????? ????????? n ? ????? h (1 ? h ? n ). ???
???????? ???????????? ???????????? ?????????. ???? ???????? ?????
???????????? ??????????, ???? ????? ???? ?????? ????????? ?? ????????? ???????: ??? ?????? ????????? ??????????? (???? ?? ?????
???? ? ?????? h), ??? ????? ?? ????? ????????? ???????? ??????????? ??????????. ????????, ???? ????? ???? ??????????? ????? 20????????? ?????????? ????? ? ??? ????????? ?? ????????? ?? 2 ???????, ?? ????? ????????? ????? 2 ??????????, ?? ?????????? ????? ????????? ???????? ???? ??????????? ????????, ?. ?. ????????? ????? 102
?????????.
??????????? ???????????? ????????? ????? ??????????? ???????,
???? ??????????? ????????? ??? ??, ??? ????????????? ????????? ?
?????? ??????? (??? h = n).
?????? 3.
????? ????????? ???? S (S1, S2, S3) ????? ??? S = (23, 8, 11), ?. ?.
???????????? ????? ???????????? ???? ?????????, ??? ?????? ???????
? ???????????? ????????????? ????? ??????? ?????????? ???????? ????? p.
?????? ?? ?????? ?????????? ??????? ? ??????? ?????????? ????????? ?????, ??? ???? ?????????? ?????????????, ????? ????????
?????????? ? ???????? 0 ? p ? 1. ????????,
1) ( 5, 32, 18)
48
2) (0, 19, 3)
3) (36, 7, 16)
4) (9, 11, 35)
5) (16, 1, 28)
6) (25, 39, 46)
7) (3, 0, 21)
8) (15, 14, 2)
9) (35, 20, 20)
? ??????? ???????? (a10, b10, c10) ??????? ?? ?????????? ???????:
a10 = S1 ? a1 ? a2 ? ? ? a9 mod p
b10 = S2 ? b1 ? b2 ? ? ? b9 mod p
c10 = S3 ? c1 ? c2 ? ? ? ?9 mod p
??? ???????????????? ??????? ????????:
10) (24, 10, 25)
???? ????????? ?????? ????? ??? ??? ?????? ???????????, ?? ????
S ????? ????????????????? ????????? ??????????????? ????????? ????
?????? ?????????? ?? ?????? 29. ???? ????????? ?????? ????? ????
???????????, ?? ?? ?????? ????? S ?? ??????????? ??????? ?? ??????,
??????? ????????? ?????? ?????? ??????????.
? ????? ?????? ??? ???????? n ? h ????? ?????????? ?????? ?????
P(h ? 1, n ? h + 1) = n!/((h ? 1)!(n ? h + 1)!)
??????????????? ????? ?? ??????? ?? ????? ???????????, ???? ??
?????? h, ? ???? ????? ??????????, ???? ????? ??????????? ????? ???
?????? h.
??????????? ????? ????????? ??????????? ?????????? ??????? ???
????????? ???????? ??????? ? ???????????. ???, ???? ???????????
?????? ???????? ??????-?? ???? ??????, ??? ?????????, ?? ?????
???????? ??? ??? ??? ???? ??? "?????" ?????. ?????, ??? ? ????? ????? ???????? ????? (?? ?? ?????, ??? ????? "????", ???????? ????????
??????????? ??????????). ???????????, ????? ??????????? ? ????? ????? ?????????????? ???????????.
49
5. ????????? ?????????????? ??????,
???????????? ???? ? ????????
?????????????? ??????
5.1. ???????? ?????? ?? ????????? ??????
???????????, ??? ????? ? ??? ??????? ????????? ? ????? ? ??????? ?????? ??????, ???? ??????????, ????????, ?? ????? ??????.
?????? ? ?????????????? ?????? ??? ????? ?????? ?? ????????
????? ???????? ??????, ??? ???? ??????????? ?????????? ????? ? ????,
????? ???? ???? ???????.
???????? ?????? ??????????? ??? ???? ????? ????????? ????????? ???????:
??? ????? ????? ??????? ?? ??? ??????: ?????? ? ????????. ?????
???????? ?????? ????????????? ????? ??????, ? ?????? ? ????. ???,
?????? 1, 3, 5, 7, 9,?????????????? ?????, ? ?????? 2, 4, 6, 8, 10,? ?
????. ????? ? ??? ?????????????? ?? ????????????? ????????? ????????????? ???????, ????????, ????????? ?????????? ? ????????? ???????: xk ? a mod p. ?????????? ??? ?????? ??????????? ???????? k ? p.
????? ????? ???????? ????????? ????? ????? x , ???????? ??? ? ??????? k ? ?????????? a ???????? ????. ???, ??????? a, ?? ?????, ????????????? ??? ??????? ????? ??? ??? ? ?????? ????????? ???????, ????????, ???????, ??? ????? ??????? ????? y, ??????? ???????? ?????.
????? ????? ???????? ???? ????? x, ??????? ??? ???????????? ??? ?????????? a. ??? ?????????? x ? y ?? mod 2, ???? x ? y mod 2, ?? ???
?????? ? ?????? ????????? ???, ???? ?? x ? y mod 2 , ?? ?????? ????????? ?????.
5.2. ??????????? ???????? ?????????
????? ?????? ???????? ????? ????? ??????????? ????????? ??
????????? ?????? ???, ??? ??? ???? ??????? ? ??????? 3 ????. 4.4.
"?????????? ???????".
50
???????????? ?????????? ???? ?????????? ? ?????? ????????? ????
????? ?????????? ???????. ???????????? ???????? ?????? ???????????? ????????? ? ???? ?? ????? ????? R, ?? ?????????? ?? ?? ?????? p,
??????? ????? ????????? ???? S, ??????????? ? ????????? ??????,
????????? ???. ???? ????? ?????? ?????????? ?????? R, ? ????? ?????????? ????? ??? ?????? h, ?? ??????? ????????. ???? ????? ????????? ?????????? ?????? R, ?? ????? ??????? ??????? ?????????, ???????? ??? ????????? ?????????????? ? ????????? ??????????? ? ?????? ???????????. ??? ??????? ?????, ??????? ?????? h, ?????? S ??
?????? ???? ??????.
5.3. ????????????? ????????????? ?? ??????? ???????
?????????? ????????, ????? ????????? ?????????? ? ???? ? ?????????? ???? ??????. ???? ?????? ???????? ? ?????-?? ??????? ??????, ??
??? ?? ?????????. ????? ?????, ???? ??? ????? ????????? ? ???? ????????? ???????, ???????? ??????????? ?????????? ???????????????? ???????. ????? ???? ????????? ????????????? ?? ?????? ???????? ??
??????????. ? ?? ?? ?????, ???????????? ?????? ???????? ???? ???????? ??????, ? ????????? ????????? ??? ??????. ????? ?? ?????????? ???? ????? ????? ???? ?????????: ?????? ???????? ???? ??????
? ???? ?????????? ?????, ????????, x. ??? ????????? ???????? xn ?
?s mod p ? ? ??????? ??????? ??????? ???????, ??? ?????????? ????????? ????????????? ???????? ???????? (??? ?? ???????? ??). ??? ????,
????? ????????? ?????????? ??????? ???? ???????, ???????, ????????,
????? ?????? ? ?????? ????????? ???????.
5.4. ??????????? ?????????????? ???????????
??????????? ?????????? ???? ????????? ???????? ??, ??? ??? ??????? ??????????????? ?????????? ??????? ????? ???????????????
?????? ???? ???. ? ????? ????????? ????? ??????????????? ??? ????????. ????????????? ??????? ???, ????? ?????? ??????? ?? ???????????
?? ????????? ?????? ? ???? ?? ??????????? ?????? ? ??? ?? ???? ??
?????? ????????. ????? ???????? ????? ???? ?????????? ?????????
???????. ?????? ???????????? ???????? ???? ????? ?????????? ?
????????????? (????????, ????????? ?????????? ? ???????), ????????? ??? ????? t ? d, ???????? ???? t ???????? ?? ??????????? ?????, ?
????????? d ????????? ? ????. ??? ????????? ??????? ?? ???????????
51
????? , ??? ?????????? ????????? ?????? x, ????????????? ????????
?????? t ????????????. ????????????, ??????? ???? ??????, ?????????????? ??? ????? ????????? ?????? d ? ???????? ??????????????
?????? ?? ??????????? ?????, ?? ???????? ??? ????? ??????, ??? ????????? ??????.
??????????
?????? ????? 50 ??? ?? ??????? ?????? ? ???? ????? ???????? ??????? ????????????? ????? ??????? [10], ??????????? ?????? ????? ?
????????????. ? ???? ??????? ??? ?????? ?????????????? ????????
????????? ???????????? ? ???? ?? ??????? ?.??????? ?? ????????
???? ????????????? ? ???????? ??????, ??? ?????? ?? ???????? ???????????? ? ???? ?????. ?? ??????? ??? ??????, ??????????????
?????????? ?????? ? ??????????? ? ??????? ? ??????????? ????????????, ? ??????? ????? ????????? ?????? ???????????? ? ????? ???????????? ?????????, ? ??????????? ????????? ? ?????? ????? ????
???????. ?????? ???????? ?????????? ?????????????? ?????????
?. ???????, ??? ??????????? ??????? ?????? ??????????????? ??????? ?????? ??????????. ???, ??????????? ??????? ? ???????????? ?
???????? ?. ??????? ?????? ???? ??????, ????? ?? ???????? ?????
????????????? ?? ????? ??? ????????????? ????? ??????????? ?????????????? ????????? ???????, ??? ?????, ?? ??????? ??????????
????????. ????? ???????, ??? 50 ??? ????? ?. ?????? ?????????, ???
??????? ?????? ?????????? ? ???????? ????? ????? ????????????
????? ??????? ???? ????? ? ????? ???? ??????? ?????: ????? ?? ???????????? ???????????? ? ??????????? ?? ???????? ???????????? ??????????, ??????? ?? ????? ? ???? ?? ???????? ? ???????????? ???????.
????????????????? ??????
1. ?????????? ?. ?. ?????? ?????? ?????. ?.: ?????, 1965. 172 ?.
2. Arto Saloma?.Public-Key Criptography:. Berlin, Heidelberg, New York,
London, Paris, Tokyo, Hong Kong, Barselona Springer-Verlag. 1990.(???. ?
????. ???? ???????. ???????????? ? ???????? ??????. ?.: ???, 1995.
364 ?.
3. ???? ?.?. ?????? ?????? ???????? ?????. ????. ??????? /
???????, 1998. 38 ?.
4. 1.Cramer R. at all. A Secure and Optimally Efficient Multi-Authority
Election Scheme. Proceedinds of EUROCRYPT?97. Vol.8, No. 5. SeptemberOctober 1997.
5. ?????? ?. ?. ???????? ????????????. ?????? ?????? ??????
??????????. ?.: ?????? ?????, 1999. 110 ?.
6. ???????? ?. ?., ???????? ?. ?., ??????? ?. ?. ????????????.
?????-?????????: ????. 2000. 218 ?.
7. ????????? ?.???????????? ?? ????????? ?? ???????????. ?.:
ABF., 1997. 334 ?.
8. ?????? ?. ?. ? ??. ???????? ? ????????????. ?.: ????? ?
????, 1999. 272 ?.
9. ???? ?. ?. ??????? ???????? ?????? ? ????????? ??????? //
?????????????? ??????? ? ????????? ? ?????????????? / ??? ???.
?. ? ?????. ???????. ???., 1999. ?. 114?117.
10. ?????? ?. ?????? ?? ?????? ?????????? ? ???????????. ?.:
??, 1963.
54
??????????
???????? ...................................................................................................
1. ???????? ???????????? ???????????? .............................................
1.1. ??????? ????????????????? ??????? ......................................
1.2. ??????????????? ??????? .......................................................
1.3. ???????? ????????????????? ?????? ....................................
1.4. ????????????????? ???????? DES ...........................................
2. ????????????? ? ???????? ?????????????? ?????? ...................
2.1. ????? ??????????? ? ??????? ? ????????
?????????????? ?????? ............................................................
2.2. ????????? ??????? ....................................................................
2.3. ?????? ????????????? ????????? ?????? ???
???????????? ? ???????? ?????????????? ?????? ..............
2.4. ??????? ??????? .........................................................................
3. ????????????? RSA ............................................................................
3.1. ???? ????????????? ..................................................................
3.2. ????????????? ?????? ? ???????? ??????????????
?????? ??? ??????????? ????? ..................................................
4. ????????????????? ????????? ..........................................................
4.1. ????? ? ????????? .......................................................................
4.2. ??????????? ??????? .................................................................
4.3. ???????? ??????????? ?????????
???????????? ?????????? ........................................................
4.4. ?????????? ??????? .....................................................................
5. ????????? ?????????????? ??????, ???????????? ???? ?
???????? ?????????????? ?????? .................................................
5.1. ???????? ?????? ?? ????????? ?????? ....................................
5.2. ??????????? ???????? ????????? ............................................
5.3. ????????????? ????????????? ?? ??????? ??????? ...............
5.4. ??????????? ?????????????? ??????????? .............................
?????????? ...............................................................................................
????????????????? ?????? .....................................................................
3
5
5
9
13
14
19
19
22
24
25
34
34
35
37
37
39
41
42
50
50
50
51
51
53
54
55
??????? ???????
???? ????? ???????
?????????? ??????????.
?????????????? ??????? ????????????
??????? ???????
???????? ?. ?. ?????
???????????? ??????? ??????? ?. ?., ?????????? ?. ?.
???????? ?? ?020341 ?? 07.05.97. ????? ? ????? 15.01.01 ????????? ? ?????? 28.04.01
?????? 60Ч84 1/16. ?????? ???. ?3. ?????? ????????. ???. ???. ?. 3,25. ???. ??.-???. 3,37.
??. -???. ?. 3,5. ????? 100 ???. ????? ? 172
???????????-???????????? ?????
?????? ???????????-???????????? ??????????
????? ??????????? ??????????
???????
190000, ?????-?????????, ??. ?. ???????, 67
56
?? ? ???? ?????? d = 20 (?? ?????? 52?
1 =24) ???? ????????? ??????? A?, ? ?????????? ??????? ???????? ?????? B:
B = ( 21 13 0 4 23).
????????? ????? ????????? ????????? ?????? ????? ????????,
????? ??????? ? ?????? ??????? ????? 2 (? ????? ?????? h). ???????
????????? ???????????? ?????????, ??????????????? ????? ???????,
? ?????????? ????????????:
?1 0 0 0 0 ?
?
?
?0 1 2 0 0 ?
(21 13 0 4 23)? ?1 0 0 0 2 ? = (21 12 2 8 0)
?
?
?0 0 0 2 0?
?0 1 0 0 0 ?
?
?
?? ?????? ????? ?????????? ????????????? ?????????: 21 12 2 8 0.
????? ????, ???????? ?????? ????? ???????? p = 5 ? h = 2. ????????? ??????????, ????? ????, ????? d, g ? ?. ??????? ?? ????? ?????????? ? ??????????????? ?????????. ?? ???????? ?? ?????????? ?????
??? hd ?? ?????? 24:
21 ? 2?20 ? 5 mod 24.
12 ? 2?20 ? 20 mod 24.
2 ? 2?20 ? 10 mod 24.
8 ? 2?20 ? 16 mod 24.
0 ? 2?20 ? 8 mod 24.
????? ????????? ?????????? ?? ??????? ?????????? ??????? ???????? gx = (? + 1)x, ??? x ? ???????, ?????????? ?????? ??????? ? ????????? ???????????. ????????? ? ??????????? ????????? ?2+ 2 ? ???????????? ????????? ?? ??? ?????????:
(? + 1)5 = 4? + 1 + ?2 + 2 = ?2+ 4? + 3 = (? + 1) (? + 3),
(? + 1)20= 4? + 3 + ?2 + 2 = ?2 + 4? = ?(? + 4),
(? + 1)10= 3? + 4 + ?2 + 2 = ?2 +3? + 1 = (? + 4)2,
(? + 1)16= 4? + 2+ ?2 + 2 = ?2 + 4? + 4 = (? + 2)2,
(? + 1)8 = ? + 2 + ?2 + 2 = ?2 + ? + 4 = (? + 3)2.
? ?????????? ???????? ?????????????? ?????????, ??????? ?????????? ?? ???????????? ?????? ????????????? ?:
32
?0
?
?1
?0
?
?1
?0
?
1 0 0 0?
?
0 0 0 0?
0 0 2 0?
?
0 0 0 2?
1 2 0 0 ?? .
????? ???????????? ???????? ???????? ?????????:
?1 0 0 0 0 ?
?
?
?0 1 2 0 0 ?
?1 0 0 0 2 ?
?
?
?0 0 0 2 0?
?0 1 0 0 0 ? .
?
?
????????? ???????????? ?????????? ??????? ?????
d (A ) =
p
5
= = 2,5.
log 2 max A 2
33
3. ????????????? RSA
3.1. ???? ?????????????
???????? ?????? ???????????????? ???????? ? ???????? ??????
???????? ????????????? RSA (Rivest, Shamir, Adleman). ???? ???????
??????? ? ???, ??? ????? ?????? ????????? ???????????? ???? ???????
????? ?? ???????????, ?. ?. ????? ??? ???????????. ???? ?? ???? ??????? RSA ????????????? ??????.
????? p ? q ? ??? ???????? ????????? ??????? ????? (?????? ???????? ?? 100 ?????????? ????????). ?????????:
n = pq ? ?(n) = (p ?1)(q ?1),
??? ? (n) ? ??????? ?????? ?? n.
???????? ?????????? ??????? ????? d >>1, ?????, ??? (d, ?(n)) = 1,
? ??????????? e, 1 < e < ?(n), ??????????????? ?????????:
ed ? 1 mod ?(n).
????? n, e ? d ?????????? ?????????????? ???????, ???????????
???????????? ? ??????????? ????????????? ??????????????.
????? n ? e ???????? ???????? ????, ? p, q, ?(n) ? d ?????????
???????. ??? ???? ????????? ??????? ???????? ? ???? ??????????????? ????????. ???, ???? ???????? p (?, ???????, n ? e), ?? ?????????
????? ??????? ??????????? ??????:
q = n/p; ?(n) = (p?1)(q?1);
d ????????? ?? ???????: ed ? 1 mod ?(n).
???????????? ?????????????? ??????????? ????????? ?????????
?????? S ? ??????? e ?? ?????? n.
????????????? ??????????? ??????????? ?????????? ???????????
???? ? ??????? d.
??? ???????????? ???????? Se ? C mod n. ????? C ? ????????????? ???????? ??????.
??? ????????????? Cd = Sed = S1+?(n)k = S?(n)k S ? S mod n. (?)
34
?????????????? (?) ????? ?????, ??? ??? ?? ????????? ed ? 1 mod ?(n)
???????, ??? ed = 1 + ?(n)k, ??? k ? ????????? ?????.
??????.
????? p = 11, q = 13. ????? n = 143, ?(n) = 120.
??????? d ?? ???????: ( d, ?(n)) = 1, ????????, d = 37, ????? ??
?????????: ed ? 1 mod ?(n) ??????? e = 13. ?????????????,
13?37 = 481 ? 1 mod 120.
??? ???????????? ??????? ???????? ??????, ??????? ???????????,
????????, ?????? S = 42.
4213 ? 3 mod 143, ?. ?. ???? ????????? C = 3.
??? ????????????? ???????? ????? 3 ? ??????? 37:
337 ? 42 mod 143.
????? ???????, ????????? ?????????? ????????? ???????? ????????? ???? ?????????.
3.2. ????????????? ??????
? ???????? ?????????????? ?????? ??? ??????????? ?????
?????????? ????????? ??????? ?????, ? ??????? ???????? ???????????? ????????? ??????????? ?? ????????? ??????.
1. ????? ????????? ????????? A, B, C, ???????????? ?? ?????? ???????????. ??? ????? ??????? ????????? ????? ??????? ????? p, ?????, ??? p ?1 ?????????????? ?? ??????? ??????????? ? ?????? ???????. ????? ???? N = p1 p2 p3?pk ?????????? ?????????? ??????. ?????? ?? ?????????? ???????? ??? ????? ??????? ? ??????? ??????? ?
p ?1 ???, ?????:
a1a2 ? b1b2 ? c1c2 ? 1 mod (p?1).
????? ??????? A ????? ???????? ????????? S ???????? B. ?? ???????? ???? ????????? ??????????? ? ??????? a1: Sa1 ? S1 mod p ? ???????? ??? B. ???, ? ???? ???????, ???????? ?????????? ????????? ??????????? ? ??????? b1 : S1b1 ? S2 mod p ? ?????????? ??? A. A ???????? ???
? ??????? a2 ? ???????? ??? B: S2a2 ? S3 mod p. B ???????? ??? ? ???????
b2 ? ?????? ?????????. ?????????????? ?????????? ??????? ?? ?????????: a1b1a2b2 ? 1 mod (p ? 1).
??????. ????? ???????? A, B ? C ??????? ????? p = 103. ??? ?????
???????, ?????? 103?1 = 102 ? ????????? ?????, ??? ??? ??????????????
? ???? ???????????? ??????? ????? ? ?????? ????????: 102 = 2?3?17.
?????? ?? ?????????? ???????? ???? ????????? ??????, ????????:
35
A: a1 = 25, a2 = 49,
B: b1 = 19, b2 = 43,
C: c1 = 35, c2 = 35.
????? ?????? A ???????? ? B ????????? S = 67. ?? ???????? ??? ?
??????? 25 ? ??????? ??????? ?? ?????? 103: 6725 ? 86 mod 103.
B ???????? ??? ? ??????? b2 = 19 ? ?????????? ????????? ? A:
8619 ? 96 mod 103.
A ???????? ?????????? ????????? ? ??????? 49 ? ???????? ??? B:
9649 ? 21 mod 103.
B, ??????? ?????????, ???????? ??? ? ??????? 43 ? ?????? ????????
?????: 2143 ? 67 mod 103. ????? ???????, S = 67.
???????? ?????? ? ???? ??????? ???????? ?????? p. ??????????? ????? ??????? ???????? ??????? ????? ??????? ?? ?????? ???????? ? ???????.
2. ????? ??????? ??????????? ???? ? ????????? ?????????? ?????
????? ????? ????? ?????????????. ???? ?? ?????? ?????? ??????? ???????? ???????? ????? g ? p ??????? ????????????, ?? ??? ?????
?????????? ????? ???? ????????? ???????. ????? ??????? A ???
???????? ???? k1, ? ??????? B ???? k2 (??? ?????????????? ?????????
????? ?????????). A ???????? ? B ????????? gk1 mod p, ? B ???????? ?
A ????????? gk2 mod p. B ???????? ?????????? ????????? ? ??????? k2,
? ? ? ??????? k1. ? ?????????? ??? ?????????? ?????????? ????? ????:
gk1k2 = gk2k1 ? K mod p, ????? ???? ???????? ????? ??????????? ?? ????????? ?????? ? ?????????????? ????? ???????????? (????????????) ?????????????.
36
4. ????????????????? ?????????
? ???????????? (????????????) ????????????????? ???????? ??????????????, ??? ??? ????, ??????? ???????????? ????????? ???????????, ????????? ???????? ???? ????? ? ???????? ???????? ???? ????????? ?? ??????? ??? (?????????????, ??????, ????????????????).
???????????? ? ???????? ?????? ??????????? ????????? ?????
?????, ???????? ? ??????? ????????????????? ???????. ? ?????????? ????????? ????????????? ? ????????????? , ???????????? ???????????? ??????? ??????????? ????? ???????????, ??????? ?? ??????
???????? ???? ?????, ? ???????? ?????????? ????? ??????????? ???????????. ?????????????????? ???????? ?????????? ?????? ???????????, ???????????? ????????????????? ?????? ??? ??????? ?????????????? ?????, ???????? ?????????????????? ???????????.
4.1. ????? ? ?????????
?????????? ??????, ? ??????? ????????? ????? v1, v2, ?vk ????????
??????????? ???????????? ?????????????? ????????? ????? B (???????). ??? ???? ????? ?????????????????? ?????? ??????????????
???????????? ?????????, ????? ?? ??????????? ????????? ?????? B
????? ???????????????? ?????? ????????? ? ????????? ?????? ???
????????????.
?????? B ???????? ????????? ????? N = PQ, ??? P ? Q ? ???????
??????? ?????. ?????? ?? ?????????? vi (i = 1, 2, 3, ?, k) ????? ???????? ???? ???????? ni = piqi, ?????? ??????????, ????? N > ni. ?????
??? ??????, ??? ? ????????? ??????? ???????? ? (N) ? ?????? ? ? (ni) ?
??? ?????????. ????? ???? ?????? ???????? ???? ???????? ????: S, ?
?????? ? si ? ????????? ?? ???????:
0 < S < ? (N) , ( S, ? (N) ) = 1 ? ?????? ?
0 < si < ? (ni), (si, ? (ni))= 1 ? ?????????.
????? ?????? ? ????????? ??????? ???? ????????? ????? T ? ti ?? ?????????:
ST ? 1 mod ? (N), 0 < T < ? (N) ? ??????,
37
st ? 1 mod ? (ni), 0 < t < ? (ni) ? ?????????.
????? ???? ???????? ??????? ??????????? ?????????? ????? ? ????????? ???????:
B: N, S
vi: ni, si.
????? ?????? ????????? ???????? vi ????? ???????? ????????????
m ??????? B. ?? ??????? ??? ??????? ????? ????????? ?????? (??????? m ? ??????? ti ?? mod ni, ? ????? ???????? ?????? ???????: m1 ? mti
mod ni, m2 ? m1S mod N. ????????? m2 ?????????? ?? ????????? ??????
?????. ??????, ??????? ????????? m2, ??????? ?????????????? ??? ????? ????????? ?????? T, ? ????? ???????? ?????? ????????? vi. ?
?????????? ????????:
m3 ? m2T mod N, m4 ? m3ti mod ni.
??? ???? m4 = m, ?. ?. ?????? B ?????????????? ?????????? ??? ????????????, ??? ???? ?????? ? ?????????????? (??????) ?????????. ???
?????? ?? ???????? ??????? ????????? ? ?????? ?????????? ???????????? ????????. ???? ???????? ?? ???????? ?????????? ????? ??????, ???
?????? ?????? ????? N < ni, ?? ??????? ??????? ????????, ??????? ???
?? ?????????, ???? ?????? ????? ??????? ??????? ???????????.
??????.
????? ?????? ?????? ??????? ????? P = 23, Q = 11; ???????? v: p = 13,
q = 7. ????? ???? ? ??????, ? ???????? ????????? ??????? ???????
??????: ?(23?11) = 220; ? (13?7) = 72, ????? ???????? ???????? ? ????????? ????????? ?????, ????????: S = 71, T = 31; s = 29, t = 5. ??????? ??????????? ?????: P?Q = 253, p?q = 91, S = 71, s = 29. ?????????
?????? ??????? ???????? ????? T = 31, ? ????????? ?????? ????????? t = 5.
????? ???????? ????? ???? ????????? ????????? ??????? ? ????
????? m = 41. ?? ??????? ??? ????? ????????? ?????? t, ? ????? ???????? ?????? ??????? S:
415 ? 6 mod 91, 671 ? 94 mod 253.
??? ????????? (????? 94) ?? ????????? ?????? ?????????? ???????.
?????? ?????????????? ????????? ??????? ????? ????????? ??????
T, ? ????? ???????? ?????? ????????? s:
94 31 ? 6 mod 253, 629 ? 41 mod 77.
?????? ????????? ???????? ????????? ? ???? ????? 41.
38
4.2. ??????????? ???????
?????????? ???????? ??????????? ????????, ??? ??????? ?????????????? ?????????? ????????????????? ?????????? (????????? ??????? ????????? ????). ????? ? ??????????? ???????? ????????? ???
???????: ????, ?????????????? ?????? ?? ????? ?????, ?????????? ??
???? ? ??????? ??????????? ????????, ??????????, ????????? ?? ????? ? ????? ????????? ????? ? ?????????? ?? ????????, ? ??? ????????
(??????? ??? ?????), ?????????? ??????????? ???????? ? ??????????
?? ? ???? ??? ???????? ? ?????????? ?? ???? ????.
????? ???????????? ??? ??????????: ?????? ?? ?????, ?????? ? ???????.
??? ???????? ???????????? ???????? ?????????? ??????????:
? ???????????? ?????, ? ???? ????????????? ????????? ???????
????? ??? ?? ?????? ????????? ???????, ??????????? ??????, ???????
????? ????????? ???????? ? ?????????? ????????,
? ????????????????? ?????????? ? ???? ????????????? ????????????? ???????? ???????, ??????? ???????????? ? ????, ? ??????????,
??????????? ??? ????????.
???, ?? ?????? ??????, ?????????????? ?????????? ??????????????
? ??????? ??? ?????????? "???????????" ??????? ? ???????????? ??
?????? RSA.
???? ???????? ??? ??????? ??????? ????? p ? q, ???????? ???? e
? ????????? ????????? ???? d ?? ???????: ed ? 1 mod ? (N = pq), ?????
??????? ????????? N, e ? ????????? ????????????? ??????? f : ZN ? ZN.
????????? ??????? ????? ??????? ? ?????????? ? ????????? m ??????? ????????????: s ? md mod N. ? ?????????? ???????? ???????????
??????? ?????? d ????????????? ???????? ???????????? ? 1 ????????
??????? (?????, ??? ??????, ?????? ? ?.?.). ??? ????????? ??????????
???????? ?????? ? ?????? ????????? ?????????? ?????? ??? ?????????? ? ????. ????? ??????? ???????? ???????????? ????????? ??????????? ???????? ????????????? ???????????.
??? ?????? ?? ????? ?????????? ???????? ????????? ????????? ????? n ? ZN ? ????????? f(n).?????????? ????? ???????? ?? ????? ??????? ?? ????????, ?. ?. f(n) d . ?????? ???? ?? ?????? ?????? ? ????
???????? f(n), ?? ????????? ??????? ?????????????????, ??? ??? ????,
?????? ?? ????? ?????????? ?????, ?????????? ?????????? ????????
(??????????? ??????) ????????. ??? ?????????? ????? ?????????? ???????? ????????? ????????? ????? r ? ZN., r ? 0, ????????? f(n)r e mod
39
N, ? ???????? ????????? ? ????. ???? ????????? ???????? f(n) dr mod N
? ?????????? ??? ??????????. ?????????? "???????" ??????????? ????????? r ? ???????? ??????????? ???????? ? ???? (n, f(n) d mod N).
???? ????????? ?? ????? ?????????????? ? ?????????.
? ?????????? ??????? ?????????? ???????? ???????? ???????????
???????? (n, f(n) d mod N), ??????? ??? ????? ????????? ??????????????, ???????? ?? n ???????? f(n), ? ????? ???????? ??????? f(n) ?
? (f(n) d) e mod N.
?????? ??? ????, ????? ????????? ?????? ????? ? ??? ?? ?????????
?????????? ???????, ???????? ?????????? ??????????? ???????? ? ????
??? ???????? ? ?????????? ?? ???? ????. ???? ?? ??????? ?????????, ??
???? ?? ????? ????????? ??? ???????? ? ????????? ???????? ????? ??
???? ????????.
??? ?????? ?? ????? ? ????? ???????? ????????? ???????? f(n)d r mod N,
??????? ??-?? ???????????? ????????? r ???????????? ????? ??????
????????? ?????.
??????.
????? ?????? ??????? ??????? ????? p = 17 ? q = 19. N = 323,
? (323) = 288. ???????? ???? e = 11, ????????? ???? d = 131 ? ????????????? ??????? f(x) = x2 mod 323.
??????? ??????????? N = 323, e = 11 ? ??? ??????? f.
??? ?????? ?? ????? ?????????? ???????? ????????? ????? n = 25,
????????? f(25) = 252 ? 302 mod 323 , ???????? ??????????? ????????? r = 20, ????????? f(n)r e mod N, ??????? ? ?????? ??????? ?????
?????: 302 ? 2011 mod 323 ? 74 mod 323 ? ???????? ? ???? ????? 74. ????
???????? ?????????? ????? ? ??????? d = 131 ? ????????: 74131 ? 63 mod 323.
?????????? ??????? ??????????? ????????? r = 20, ????? ?????????:
f(25)131?310 mod 323. ????? ???????, ??????????? ?????? ???????????
???????? ????? ???: (25, 310). ??? ???????? ???????????? ????????. ????
???????? ????? ?????????????? ????????? ??????????? ????????, ?? ??
????? ????????? F(25) ? 302 mod 323 ? ????? 31011 ? 302 mod 323. ?????????? ?????????? ???????? ??????????????? ? ??????????? ????????.
?????? ??? ???????? ????, ??? ??? ???????? ?? ?????????????? ? ??????
????????, ???????? ?????????? ?? ? ????, ??????? ?? ??????? ?????????, ??? ??? ??????? ???????????? ? ??????? ? ????????? ???? ???????? ??????? ?? ???? ????????.
40
4.3. ???????? ??????????? ?????????
???????????? ??????????
? ????????? ???????, ??????, ??????????? ?? ????, ?????? ????
?????????? ????????????, ????? ?? ???? ?? ????????? ?? ??? ?????????? ?? ????????? ??????????? ?????????. ??? ????? ?????????? ??????????? ?????, ?????????? ????????? ?????????. ? ????????, ????????, ????????????? ? ?????????? ???????, ????? ????????? ??????? ????????? ????????? ??????????? ????????? ? ????? ??????????????? ??? ????????? ????????? ????????. ???????? ????????? ?????????????? ???????? ????????. ?????????? ????????, ????????????
?????? ? ?????????? ?????????? ?????????????? (??????????????
????, ??? ????? ????????? ??????? ????????? ??????).
????? p ? q ? ??????? ?????, ?????? q ????? p ? 1. ????????, p = 23,
q = 11, ??? p = 59, q = 29. ????? ??????? g ?????, ??? gq ? 1 mod p. ???
??????? ??????? g = 2, ??? ??? 211 ? 1 mod 23, ??? ??????? ??????? g = 4,
??? ??? 429 ? 1 mod 59.
?????? ????????? ???????????, ??? ????? ??????????? ?????
????? ??????????, ????????, ?????? ? ?????. ????? ???????? ????????? ????????? ????? x ?? ????????? ?????: {0, 1, 2, ?q?1} ? ????????? ???? y = g?x mod p, ??????? ??????? ?????????.
????? ????? ???????? ????????? ????? k ?? ????????? {0, 1, 2, ?q?1},
????????? r = gk mod p ? r ?????????? ? ????.
??? ???????? ????????? ????????? ?????? e ?? ?????????
{0, 1, 2, ?2t?1},
??? t ? ????????? ????? ? ???????? e ? ?????.
????? ????????? s = k + xe mod q ? ???????? s ? ???? ?? ????????.
??? ????????? ???????????: r = gsye mod p ?, ???? ??? ???????????,
????????? ?????????????? ?????, ??? ??? ??????? ????????? ??????,
? ????????? ?????? ?????????????? ???????????.
??????.
????? p = 59, q = 29, ????? ????? ????? g = 4. ????????? ????? x,
?????????? ??????, x = 9, ????? y = 4?9? 17 mod 59. ????? 17 ????????
???????? ?????? ?????.
????? ????? ???????? k ????????, k = 12, ????????? r = 412 ? 35
mod 59 ? ????? r = 35 ?????????? ? ????. ????? ????????? ?????? ????
e = 10, ??????? ?? ???????? ? ?????. ????? ?????????: s = 12 + 9?10
mod 29 ? 15 mod 29. ????? s = 15 ?????????? ? ????.
41
??? ????????? ???????????:
4151710? 57 ? 12 ? 35 mod 59.
????????? r = 35, ?? ?????????????? ???????????.
4.4. ?????????? ???????
?????????? ??????, ????? ???????????? ????? ??? ?????-???? ?????? ??????????? ?? ????????? ???????? ????? ??????????? ? ????? ??????????????? ??? ????????????? ?????????? ?????. ?? ????? ????????? ???? ????????? ???? (???????? ??? ?????????? ?????????????????? ????????) ?? ????????? ????????? ? ??? ????????? ???????
?????????? ??????????? ???, ????? ??? ????? ????? ??????????? n
?????? ???? ??? ???? ??? ?????????, ???? ????????? ?????? ?? ?????
h ???????????.
???????? ?????? ???????????? ?????? ???????? ??? h = n, ?. ?. ?????
???? ????????? n ??????????? ? ????????? ??????? ???? n ??????????
?????, ????? ??????? ????????? ????????? ???? S. ??????? ????????? ??????? ????? p ? ????? ????????? ???? ?????????????? ? ????
?????? (s1, s2, s3, ?, sk) , ??? ??? si ???????? ?????????? ???? GF(p).
???????? ????????? ???? ?? n ?????????? ????????? ???????. ????? ???????????? ???????????? ????????? ?????: (a11, a12, a13, ?, a1k)
? ???????? ?????????? ????? 1-?? ??????????,
(a21, a22, a23, ?, a2k) ? ???????? ?????????? ????? 2-?? ??????????,
???????.
(an?11, an?12, an?13, ?, an?1k) ? ???????? ?????????? ????? n?1-?? ??????????.
? ?????????? n-?? ?????????? ???????? ???????? ??? ?????????
?????????? ????? ?? ?????????? ???????:
an1 = s1 ? a11 ? a21 ? a31 ? ? ? an1 mod p.
an2 = s2 ? a12 ? a22 ? a32 ? ? ? an2 mod p.
????????????????
ank = sk ? a1k ? a2k ? a3k ? ? ? ank mod p.
? ???? ?????? ?????? ??? ???????? ???? ?????????? ????? ?? ?????? p ??????? ?????? ????????? ????.
??????.
????? p = 29 ? ????????? ???? ????? ???: (26, 13, 21, 8, 0, 18). ????????? ????????? ??? ?? 5 ?????????? ??? ??????? 5 ???????????. ???
?????? ??????? ?? ??? ????????? ????????? ????? ?? ?????? 29 ?????
????????? ?????????:
42
(26, 0, 13, 11, 23, 25)
(2, 7, 15, 12, 27, 6)
(1, 3 , 24, 6, 0, 16)
(12, 2, 7, 0, 7, 0)
??? ??????????, ?????? ?????????? ??????????? ???????? ?????
???:
(14, 1, 20, 8, 1, 0).
????? ???????????, ??? ???????? ???? ?????????? (?????? ???????
???????????? ?? ?????? 29) ???? ?????? ????????? ???? (26, 13, 21, 8,
0, 18)
??????? ????????, ??? ????????? ??????? ?????????? ????? ? ????????????? ?????? ??????? ?????? ?? ???????? ?????? p ? ????? ????????? k ? ??????????? ?? ??????? ?? ?????????? ??????????? n.
?????????? ??????, ????? h < n. ??????? ????????? ????????? ??????? ????? ????????? ??????.???????? ????????, ????????? ? [2].
?? ??????? ?? ????????? ?????????? ? ????????? ??????? ?? ????????.
??????? n ?????????? A1, A2, A3, ?, An. ????? m i, i = 1, 2, ?n, ?????
?????, ??????? 1, ?????, ??? (mi, mj) = 1 ??? i ?j. ????????? ? ? ???????????? ???? ????? mi, ?. ?. ? = m1m2m3?, mi, ?mn.
????????? ????? Mi ? ???????????? ???? mj (j = 1, 2, ?, i?1, i+1, ?, n),
????? mi, ?. ?. Mi = M / mi. ???????? ???????? Ni ?? ???????: MiNi ?
?1 mod mi. ????????? (Mi, mi) = 1, ?? ??????? ?????? ?????????? ? ???
Ni ????? ???????.
???? ??????? n ????????? ????: x ? ai mod mi, i = 1, 2, ?, n, ai ?
?????, ?? ????? ??????? ???? ????????? ????? ???:
x=
n
? ai M i Ni .
i =1
????? ????, ??? ??????? ????????????, ?. ?. ????? ?????? ???????
y ????????????? ?????????: y ? x mod M.
????? ?????? h ????????????? ?????, 1 < h ? n. ????????? ?????
min(h) ? ?????????? ?? h ???????????? mi, ? max(h?1) ? ?????????? ??
h?1 ???????????? mi. ???? ????????? ???????:
min(h) ? max(h?1) ? 3 max(h?1) ( ? )
? max(h?1) < c < min(h) (??)
?? ????????? {a1, a2, ?, at}, ??? ai ? c mod mi, ???????? (h, n) ?????????
????? ??? ? [ 2 ]. ??? ????????, ??? ???? c ? ????????? ????????? ????,
43
? ai ? ????????? ?????, ????????? n ??????????, ?? ????? h ?? ?????????? ?????? ???????????? ???????? c ?? ??? ??????????, ? ?????
h?1 ?????????? ??????? ??? ?? ?????? (??? ???????? ?????????). ???
???? ??? ?????? ? (?) ????????, ??? ??????? h?1 ?????????? ????????? ????????? ???? ?? ????? ??????????.
??????.
????? n = 5 ? m1 = 97; m2 = 98, m3 = 99, m4 = 101, m5 = 103.
??????? h = 3 ? ???????? min(3) = (97 ? 98 ? 99) = 941094; max(2) =
=(101 ? 103) = 10403. ??????????? (?) ?????? ???:
941094 ? 10403 = 930691 > 3 ? 10403 = 31209.
????????? ????? ? ?????? ?????? ? ???????? (??). ????? ??? ???????? ?????????? ??????????, ???????????? ??????, ??????? ????????
???????? ai (i = 1, 2, ?, 5) ?? ??????? ai ? c mod mi ? ?????? ?????????
??????? ???? ??????????: a1 = 62, a2 = 4, a3 = 50, a4 = 50, a5 = 38.
????? ?????? ???? ?? ???? ??????????, ????????, A2, A3 ? A4 ???????? ???????????? ????????? ???? c ?? ????? ??????????. ?????????
?????? ???????? ????? ?????? ???? ???????? mi, ?? ??? ?????????:
M2? = m3? m4 = 9999; M3? = m2? m4 = 9898; M4? = m2? m3 = 9702,
? ????? ??????????????? ???????? Ni: N2 = 33, N3 = 49, N4 = 17. ?????
???? ??????? ???????? y = 4 ? 9999 ? 33 + 50 ? 9898 ? 49 + 50 ? 9702 ? 17 =
=33816668. ????????? ???? ??????????? ?? ?????????: c ? y mod (m2 ? m3 ? m4).
????? ???????,
c ? 33816668 mod (98 ? 99 ? 101) ? 500000 mod 979902.
???? ????? ????? ?????? ?????? ????????, ????????, A1, A4, A5, ??
??? ???????? ??? ?? ????????? ???? ? = 500000.
????? ?????? ???? ????????, ????????, A2 ? A5 ???????? ????? ????????? ???? ?. ??? ????????? ???????? y = 4 ? 103 ? 59 + 38 ? 98 ? 41 =
?176992 ? 5394 ? ? mod 10094. ??? ????????, ??? ???????? ?????????
???? ????????? ?? ???????: 5394 + i ? 10094, ?? ???????? i ?? ?????.
?????????? ???????? i ???????????? ??? ????? ????? ?????:
min ( h ) ? max ( h ? 1) ? 1
max ( h ? 1)
.
??? ???????????????? ??????? ????? ????? ????? ????? 89, ?. ?. ????
?????????? ??????????? ????????? 89 ????????? ?????. ? ???????? ???????? ?????????? ????????? ????? ???? ??????? ??????????? ???????.
44
?????????? ??? ???? ?????? ?????????? ?????????? ?????, ????????? ? [9].
????? ? ?????? ????????? ???????? n ???????????, ?? ??????? ??
??? ????? ????????? ?? ????? ?? ????? ??????. ????????? ????? ?????????????? ????? ???????????? ?? ????????????? ???????, ??????
???, ??? ?? ???? ????????? ?? ????? ??????? ?????? ?????????? ?????.
????????? ????? ???? ????????????, ???? ????????? h ??? ????? ??????????? (?. ?. h ??????????? ?????? ????? ?????? ????? ??????????), ??? ???? 1? h ? n. ? ?????????? ????? ????????? ?????? ?????
???????? ?? ????? ??????, ???? ? ????, ??? ???? ???? ???????? ??????
?????? ?????????? ?????.
????????? ?? ???????? ?????????? n ? h ?????????? ????? ??????
h ? ???? ??????? ????????????? ???? ?????? ????? ????????????.
??????? ?????????? ??????, ????? n ? ???????? ????? ? h = (n+1)/2.
1. ???????????? ???????
????????? 1. ????????, ??? n-?????????? ???????????? ??????
???? q ???????? ???????? n-????????? ??????????, ?????????? ????? q ?????? ? n ? q ?????. ?????? ??????????? ????? ????? n ???? q
????? ???????? ????? ???? ?????, ?????????? ?????? ????????, ?
?????????? R(n, q).
????????? 2. P( a, b ) ? ?????????? ?????????? ???????????? ?? a
???????? ??????? ???? ? b ???????? ???????, ??? ?????:
P ( a, b ) =
( a + b )!
= C(aa +b ) = C(ba +b ) .
(1)
a !b !
??? R(n, q) ????? ?????????? ????? P(n?q, q)
?????????? ???????????? ?????? ? ??????, ????? n ? ???????? ?????, ? ????? h = (n+1)/2.
??????? 1. ???? n ? ???????? ????? ? ????? h = (n+1)/2, ????? ?????????? ?????????? ????? k ????? ????? n ????????? ???????? ?????
???? h, ? ??????
n!
? n +1 n ?1 ?
k = P?
,
,
?=
2 ? (( n + 1) / 2 )!(( n ? 1) / 2 )!
? 2
(2)
? ??????? ????????????? ?????? ????? ???????????? ?????????????
???????? ??????? ???????????? ???? R(n, q).
?????????????? ????????????? ? ????????????? ????????? ????.
45
?????? 1.
????? n = 5 ? h = 3. ???????? ??????? ??????????? 5-?????????
????? ???? 3 , ?. ?. R (5, 3).
??????? 1
1)
2)
3)
4)
5)
6)
7)
8)
9)
10)
1
1
1
1
1
1
1
0
0
0
0
2
1
1
1
0
0
0
1
1
1
0
3
1
0
0
1
1
0
1
1
0
1
4
0
1
0
1
0
1
1
0
1
1
5
0
0
1
0
1
1
0
1
1
1
? ??????? ??????? 1, 2, 3, 4, 5 ?????????? ????? ???????? ???????, 1), 2), 3), ...?????????? ?????? ??????. ??????? ??? ??????? 3-?? ????? ???????. ?? ????? ????? ? ???????? 1), 4), 5), 7), 8),
10). ????? ?????? ?????? ???????? ??????? ????? ?????? ?????
?????? ? ????? ????????? ?????? ????????? ???? S. ??? ???? ??????? ???? ?????? ???????? ??????? ?? ????? ??????? ??????. ?????????? ?????? ? ?????? ??????? ????? 10. ??????? ? ???????????? ???? ????????????? ??????? ??????, ??????? ????? ??????
???? ???????.
2. ??????? ? ???????????? ???????
? ????????? ??????? ????? ????????? ????? ??????? ???????, ?????????? ?? ???????????? ?????? h. ??? ????? ???????????? ? ??????? ????????? ???????.
??????? 2.
???? ???????????? ????? ?????, ??????? ?????, ????? n (?????
??? n ? ????? ????? ????????????? ?????) ? ????????? ??????????
??????? ??? ?????? h, ?? ?????????? ?????????? ????? ????? ???????
?????????? ? R(n, n?h + 1), ?. ?.
n!
k = P ( h ? 1, n ? h + 1) =
.
(3)
( n ? 1)!( n ? h + 1)!
46
?????? 2.
????? n = 6, h = 2. ???????? ??????????? ???????? ??? R(6, 5)
??????? 2
1)
2)
3)
4)
5)
6)
1
1
1
1
1
1
0
2
1
1
1
1
0
1
3
1
1
1
0
1
1
4
1
1
0
1
1
1
5
1
0
1
1
1
1
6
0
1
1
1
1
1
?????????? ????? ???? ???????? ???? ???, ?????????? ??? ???????. ?????????????? ????????????? ? ????????????? ????????? ?????.
??????? 2 ???????? ?????????? ??????? 1. ?????????????, ????
???????? ? ??????? 2 ???????? h = (n +1)/2, ?? ???????
R(n, (n +1)/2).
??? ??????? ???????? ???????????????, ??? ??? ???? ??????? ????????????? ?????? ????? ??????? ??????????? ???????.
??????????????.
??????? i-? ??????? ?? R(n, q) ? ????????? ??? r (i). ??? ??? ?????
?????????? ??? ????? ?????? ? ???? ? ?????????? ?r(i)? ?????????
???????? ?????????? ???????? r (i) ? r (j) ? ???? ??????????????? ??????? ??? ?? ???????????, ??? ?????????? ???????? ???????? ?????
?????????? ??????????????? ??????????? ???????? r(i) ?
r(j).?????????? ?????? ???????? ?????????? «v» ??? s ?????????:
r(i1) v r(i2) v r(i3) v...v r(is).
??????? ?????? ??????? ????? ????? n ???? q, ??????? ?? ?????????? R(n, q). ?? ???? ??????? ??????? ???????????? ??????? ? ??????? i, ?. ?. r(i). ????????? ??? ???. ????? ??????, ??? ??? ????? i
r (i ) = P ( n ? q, q ? 1) = Cnq??q1 .
( 4)
??? ???? ?????????? ????? 2 ???????? ? ???????? i ? j ?????
r (i ) vr ( j ) = Cnq??11 + Cnq??21 .
??? ???? ?????????? ????? s ???????? ? ???????? i1, i 2, i 3, ...is
??? 1 < s < n?q+1 ?????
47
r (i1 ) vr (i2 ) vr (i3 ) v...vr (is ) = Cnq??11 + Cnq??21 + Cnq??31 + ... + Cnq??11.
(5)
???? s = n?q+1, ?? ????? ( 5 ) ????? ????? ?????????? ????? ?
R(n, q), ?. ?.
n!
Cnq =
.
q !( n ? q )
?????????????, ????????? ???? ? ( 5 ) ????? 1.
???? ????? ?????? s ???? ( 5 ) ?????? n?q+1, ?? ????? ( 5 ) ??????
???????? ( 1 ), ??? ?????????? ???????, ??? ??? ??????? ????? ???????, ???? ?? ??????, ??? n?q+1 ?? ????? ??????? ?????? ??????. ?
??????? ??????, ???? q = (n+1)/2, ?????, ??? ??? s = (n+1)/2 ? ???????????? ??????? ?????? ????? ?????? ??? ??????????? ?????????.
??????????? ???????? ????????????? ????????? ?????? (?????????? ?????? ?????????? ?????) ?????????? ????? ? ????????? ????? ????????????? ??????? ??? ????? ????????? n ? ????? h (1 ? h ? n ). ???
???????? ???????????? ???????????? ?????????. ???? ???????? ?????
???????????? ??????????, ???? ????? ???? ?????? ????????? ?? ????????? ???????: ??? ?????? ????????? ??????????? (???? ?? ?????
???? ? ?????? h), ??? ????? ?? ????? ????????? ???????? ??????????? ??????????. ????????, ???? ????? ???? ??????????? ????? 20????????? ?????????? ????? ? ??? ????????? ?? ????????? ?? 2 ???????, ?? ????? ????????? ????? 2 ??????????, ?? ?????????? ????? ????????? ???????? ???? ??????????? ????????, ?. ?. ????????? ????? 102
?????????.
??????????? ???????????? ????????? ????? ??????????? ???????,
???? ??????????? ????????? ??? ??, ??? ????????????? ????????? ?
?????? ??????? (??? h = n).
?????? 3.
????? ????????? ???? S (S1, S2, S3) ????? ??? S = (23, 8, 11), ?. ?.
???????????? ????? ???????????? ???? ?????????, ??? ?????? ???????
? ???????????? ????????????? ????? ??????? ?????????? ???????? ????? p.
?????? ?? ?????? ?????????? ??????? ? ??????? ?????????? ????????? ?????, ??? ???? ?????????? ?????????????, ????? ????????
?????????? ? ???????? 0 ? p ? 1. ????????,
1) ( 5, 32, 18)
48
2) (0, 19, 3)
3) (36, 7, 16)
4) (9, 11, 35)
5) (16, 1, 28)
6) (25, 39, 46)
7) (3, 0, 21)
8) (15, 14, 2)
9) (35, 20, 20)
? ??????? ???????? (a10, b10, c10) ??????? ?? ?????????? ???????:
a10 = S1 ? a1 ? a2 ? ? ? a9 mod p
b10 = S2 ? b1 ? b2 ? ? ? b9 mod p
c10 = S3 ? c1 ? c2 ? ? ? ?9 mod p
??? ???????????????? ??????? ????????:
10) (24, 10, 25)
???? ????????? ?????? ????? ??? ??? ?????? ???????????, ?? ????
S ????? ????????????????? ????????? ??????????????? ????????? ????
?????? ?????????? ?? ?????? 29. ???? ????????? ?????? ????? ????
???????????, ?? ?? ?????? ????? S ?? ??????????? ??????? ?? ??????,
??????? ????????? ?????? ?????? ??????????.
? ????? ?????? ??? ???????? n ? h ????? ?????????? ?????? ?????
P(h ? 1, n ? h + 1) = n!/((h ? 1)!(n ? h + 1)!)
??????????????? ????? ?? ??????? ?? ????? ???????????, ???? ??
?????? h, ? ???? ????? ??????????, ???? ????? ??????????? ????? ???
?????? h.
??????????? ????? ????????? ??????????? ?????????? ??????? ???
????????? ???????? ??????? ? ???????????. ???, ???? ???????????
?????? ???????? ??????-?? ???? ??????, ??? ?????????, ?? ?????
???????? ??? ??? ??? ???? ??? "?????" ?????. ?????, ??? ? ????? ????? ???????? ????? (?? ?? ?????, ??? ????? "????", ???????? ????????
??????????? ??????????). ???????????, ????? ??????????? ? ????? ????? ?????????????? ???????????.
49
5. ????????? ?????????????? ??????,
???????????? ???? ? ????????
?????????????? ??????
5.1. ???????? ?????? ?? ????????? ??????
???????????, ??? ????? ? ??? ??????? ????????? ? ????? ? ??????? ?????? ??????, ???? ??????????, ????????, ?? ????? ??????.
?????? ? ?????????????? ?????? ??? ????? ?????? ?? ????????
????? ???????? ??????, ??? ???? ??????????? ?????????? ????? ? ????,
????? ???? ???? ???????.
???????? ?????? ??????????? ??? ???? ????? ????????? ????????? ???????:
??? ????? ????? ??????? ?? ??? ??????: ?????? ? ????????. ?????
???????? ?????? ????????????? ????? ??????, ? ?????? ? ????. ???,
?????? 1, 3, 5, 7, 9,?????????????? ?????, ? ?????? 2, 4, 6, 8, 10,? ?
????. ????? ? ??? ?????????????? ?? ????????????? ????????? ????????????? ???????, ????????, ????????? ?????????? ? ????????? ???????: xk ? a mod p. ?????????? ??? ?????? ??????????? ???????? k ? p.
????? ????? ???????? ????????? ????? ????? x , ???????? ??? ? ??????? k ? ?????????? a ???????? ????. ???, ??????? a, ?? ?????, ????????????? ??? ??????? ????? ??? ??? ? ?????? ????????? ???????, ????????, ???????, ??? ????? ??????? ????? y, ??????? ???????? ?????.
????? ????? ???????? ???? ????? x, ??????? ??? ???????????? ??? ?????????? a. ??? ?????????? x ? y ?? mod 2, ???? x ? y mod 2, ?? ???
?????? ? ?????? ????????? ???, ???? ?? x ? y mod 2 , ?? ?????? ????????? ?????.
5.2. ??????????? ???????? ?????????
????? ?????? ???????? ????? ????? ??????????? ????????? ??
????????? ?????? ???, ??? ??? ???? ??????? ? ??????? 3 ????. 4.4.
"?????????? ???????".
50
???????????? ?????????? ???? ?????????? ? ?????? ????????? ????
????? ?????????? ???????. ???????????? ???????? ?????? ???????????? ????????? ? ???? ?? ????? ????? R, ?? ?????????? ?? ?? ?????? p,
??????? ????? ????????? ???? S, ??????????? ? ????????? ??????,
????????? ???. ???? ????? ?????? ?????????? ?????? R, ? ????? ?????????? ????? ??? ?????? h, ?? ??????? ????????. ???? ????? ????????? ?????????? ?????? R, ?? ????? ??????? ??????? ?????????, ???????? ??? ????????? ?????????????? ? ???
Документ
Категория
Без категории
Просмотров
0
Размер файла
355 Кб
Теги
0069, 2001
1/--страниц
Пожаловаться на содержимое документа