: 60 48 01 04



quý

X
Phòng

ô


M

U........................................................................................................... 5
1: T NG QUAN V CÁC H M T MÃ ................................ 8

1.1. T ng quan v lý thuy t m t mã. ............................................................. 8
1.1.1. M t s khái ni

n........................................................................ 8

toán h c c a lý thuy t s . .......................................................... 10
1.2. M t mã truy n th ng . ........................................................................... 18
1.2.1. Mã chuy n d ch (shift cipher).............................................................. 18
1.2.2. Mã thay th (substitution cipher). ....................................................... 20
1.2.3. Mã apphin............................................................................................ 21
1.2.4. Mã Vigenere. ....................................................................................... 22
1.2.5. Mã Hill................................................................................................. 23
1.2.6. Mã hoán v ( chuy n v - Transposition )........................................... 24
i v i mã Vigenere ............................................................. 26

.................................................................................... 59
xu t thu t toán.................................................................................. 59
an toàn c a h m

xu t............................. 63

t ki m th ..................................................................................... 63
3.4.1 Gi i thi u thu t toán ............................................................................. 63
3.4.2 Gi i thi u thu t toán ............................................................................. 65
K T LU N ..................................................................................................... 82
TÀI LI U THAM KH O............................................................................... 82


mang

pháp. Thông tin

.

Steganography)
u khác

toàn.
Các

Steganography


Steganography



i nh

B n mã: Là k t qu

c

c..

c khi mã hóa b n rõ theo m t thu t toán mã

hóa
Gi i mã: Là quá trình x
b n rõ. Ví d

c, ti n hành gi i mã b

n có n

i lu t mã là t nh ti n

i v i mã ASCII c a m i kí t .

A

65, B

66, C

thu l i


m v i các bên r ng b n tin không b

i trên

ng truy n tin.
Ch ng ch i b : Có th xác nh n r ng tài li

nt

khi

h c g ng t ch i nó.
Tính xác th c: Cung c p hai d ch v :
Nh n d ng ngu n g c c a m

mb or

Ki

p h th ng, ti p t c ki m

th c.
nh danh c
mc ah
s d ng h p pháp.

ng h

g ng k t n i và gi

a, a là

b a

a
a và b, b

a cho b ta

q và r sao cho
a=b.q+r, 0
q

r

b.
a cho b

r

a cho b

a div b

a mod b.

3 và 25 mod 7 = 4, -25 div 7 = -4 và -25 mod 7 = 3.
d
d a và d b
d

m
b

a m và b m.

a và b
m

a,

a và b

a và b

m
a và b
lcm(a, b) . gcd(a, b) = a . b.

a và b

b.
a và b.

1. Trong khi còn b >
r
2.

a mod b , a

b,b

t

toán này

nguyên x, y, d sao cho: mx + ny = d
m
véc -

r

m, n là hai

n

(a1, a2, a3), (b1, b2, b3), (c1, c2, c3 )

sau:


c1. (a1, a2, a3

(1, 0, m ), (b1, b2, b3

b

(a1, a2, a3) là

q = [a3/ b3]; và (c1, c2, c3
a2, a


4864

3458

3458

1406

1

1406

1

1406

646

2

646

646

114

2

114



-2

3

-2

1

3

-1

114

5

-7

5

-2

-7

3

5

76


0

2

0

-91

128

-91

32

128

-45

x, y, r

x 3458 y

r

b
d
b

38, x

a

b theo modulo n

a

b (mod n

a, b chia cho n có cùng

n
a
Th

b (mod n)

: 11

Cho a, a1, b, b1, c Z
a

b mod n

a và b
a

a mod n
a

b mod n thì b


b mod n

modulo n

a
n

a theo modulo n
b
theo modulo (n).
d, Không gian Zn và Zn*.

a và b


Không gian Zn (các s nguyên theo modulo n)
n: Zn là
n

Zn

n

Zn

n.
Z10 ={0,1,2,3,.., 9}

Th


*

1}

Z2 = {0, 1} thì Z2* = {1} vì gcd(1, 2) = 1.

Th
e

.
Cho a Zn. Ngh

nh
x Zn sao cho a x
a

o c a a theo modulo n là s nguyên

1(mod n). N u x t n t

c g i là kh ngh ch. Ngh

duy nh t x Zn, và

o c a a ký hi u là a

1

i v i phép toán

1

g, Hàm

- Euler.

= 7 (mod 9) vì 4 7

1 (mod 9)

x


Cho n

1. (n

s t t c các s nguyên

trong kho ng t [1; n] nguyên t cùng nhau v i n và

c g i là hàm phi Euler.

Tính ch t:
p

(n) = p 1 .

Hàm phi Euler là hàm có tính nhân:
m, n) = 1 thì (m n) = (m) (n).


th nào, sau m t s h u h

c th c hi

ch

nh

c

m t k t qu (output) mong mu n.
a thu t toán

n, tính d

n, tính

ph d ng, tính kh thi.
Các th c mô t thu t toán: Ngôn ng t
Thu t toán t t
thu t toán t t

kh i, mã gi

nh (deterministic): V i hai b d li u vào gi ng nhau,

nh s thi hành các mã l nh gi ng nhau và cho k t qu gi ng

nhau.


bi n nh

th i gian th c hi n gi i thu t.
Phân tích th i gian th c hi n gi i thu t :
D li u càng l n
D li

th i gian s lý càng ch m.
cn

th i gian th c hi n T(n) là m

Th c hi n trên mô hình máy tính tr u

nh

ng.

c l p v i ph n c ng c th .

Th i gian th c hi n m t thu t toán ph thu c vào c (size) c a d li u vào:


N

:-

?



f(n) = O(n3)
f(n
f(n) = aknk + ak 1nk

k
1

n:

a1n + a0thìf(n) = O(nk)

:

n0.


O(1)
O(

logarit

)

O(n)
O(n

)

n


Z26
S = (P , C , K , E , D ),
P = C = K = Z26
K, x, y

E và D

Z26:

E(K, x) = x + K mod 26,
D(K, y) = y - K mod 26.
K, x, y Z26

dK(eK(x)) = (x +K ) - K mod 26 = x.

K=
và
hengapnhau

x = 7 4 13 6 0 15 13 7 0 20 21 0 14 2 7 8 4 20 19 7 20 1 0 24.
K
y= 20 17 0 19 13 2 0 20 13 7 8 13 1 15 20 21 17 7 6 20 7 14 13 11.

uratncaunhinbpuv rhguhonl.

dãy y
x



g

h

i

j

k

l

m

n

o

p

q

r

x

n

y


s

t

u

v m u

v w x

y

z

e

d

i

k

j

,
x = hengapnhauvaochieuthubay

y = ghsoxlsgxuexfygzhumgunxd.
Z26,
> 4.1026

o theo mod 26
1, 9, 21, 15, 3, 19, 7, 23, 11, 5, 17, 25.
" hengapnhauvaochieuthubay"
x = 7 4 13 6 0 15 13 7 0 20 21 0 14 2 7 8 4 20 19 7 20 1 0 24.
k
y = 15 0 19 10 6 3 19 15 6 2 7 6 24 16 15 20 0 2 23 15 2 11 6 22,
ng La tinh,
patkgdtpgchgyqpuacxpclgw.
Z26

a,


.N
1.2.4. Mã Vigenere.
Vigenere

16.
Vigenere không
m là

Vigenere
(P, C, K, E, D),

Vigenere
,P=C=K=

E và D

i:


mã:
y = 9 12 2 13 4 6 | 15 15 15 1 25 17 | 16 10 22 15 8 11 | 21 15 9 8 4 15


jmcnegpppbzrqkwpilvpjiep.

m

K
mã Vigenere

m

m
m

1.2.5. Mã Hill.
m

Vigenere

vành Z26

m
k Zm m

m
k


y2 = 8 1 + 7 2 mod 26.

hengapnhauvaochieuthubay,

x = 7 4 | 13 6 | 0 15 | 13 7 | 0 20 | 21 0 | 14 2 | 7 8 | 4 20 | 19 7 | 20 1 |

y = 11 6 |516 | 191 | 8 21 | 8 2 | 23 12 | 4 22 | 23 8 | 0 16 | 22 19 | 15 11 | 20 12.
T

:
lgfqtbivicxmewxiaqwtplum.

,

K-1

y
x
m

k có detk

m

1.2.6. Mã hoán v ( chuy n v - Transposition ).
m

Sm

2, ... ,