ÿþK o d o w a n i e i k r y p t o g r a f i a
B l o k o w e k o d y l i n i o w e
d r R o b e r t B o r o w i e c
P o l i t e c h n i k a W r o c Ba w s k a
I n s t y t u t T e l e k o m u n i k a c j i i A k u s t y k i
p o k ó j 9 0 8 , C - 5
t e l . 3 2 0 3 0 8 3
W y k Ba d I V
e - m a i l : r o b e r t . b o r o w i e c @ i t a . p w r . w r o c . p l
w w w : l s t w w w . i t a . p w r . w r o c . p l / ~ R B /
P l a n w y k Ba d u
D e f i n i c j a b l o k o w e g o k o d u l i n i o w e g o
P a r a m e t r y k o d u b l o k o w e g o
S p o s o b y k o d o w a n i a i n f o r m a c j i
T w o r z e n i e k o d u
K o d y d u a l n e
M e t r y k a p r z e s t r z e n i
Z d o l n o [ k o r e k c y j n a k o d u
P r z y k Ba d y w y b r a n y c h k o d ó w l i n i o w y c h
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 / 5 4
D e f i n i c j a b l o k o w e g o k o d u l i n i o w e g o
K o d o w a n i e b l o k o w e p o l e g a n a p r z e k s z t a Bc e n i u k - p o z y c y j n y c h
q - n a r n y c h c i g ó w i n f o r m a c y j n y c h h = ( h 1 , h 2 , . . , h k ) w n - p o z y c y j n e
q - n a r n e c i g i k o d o w e c = ( c 1 , c 2 , . . , c n )
K o d o w a n i e
h 1 , h 2 , . . . , h k c 1 , c 2 , . . . , c n
S Bo w o i n f o r m a c y j n e
S Bo w o k o d o w e
F o r m a l n i e p r o c e s k o d o w a n i a b l o k o w e g o m o |n a z a p i s a :
, p r z y c z y m
'" (" f : h i ’! c i f : h Ô! c
h i "{ h } c i "{ c }
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 / 5 4
P r o c e s k o d o w a n i a b l o k o w e g o
( - 1 ) - s z y t a k t
i
i - t y t a k t
( ) - s z y t a k t
i + 1
k o d o w a n i a k o d o w a n i a
k o d o w a n i a
k
-
h ( i ) h ( i + 1 )
h ( i 1 )
( i )
c ( i - 1 ) c c ( i + 1 )
n
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 / 5 4
P a r a m e t r y k o d u b l o k o w e g o
B l o k o w y k o d n a d m i a r o w y o z n a c z a m y s y m b o l e m ( n , k ) .
J e d n o z n a c z n e o k r e [l e n i e k o d u ( n , k ) w y m a g a p o d a n i a
z b i o r ó w { h } i { c } o r a z f u n k c j i f , a w i c
n , k a" h , c , f
( ) { } { }
( ) .
P a r a m e t r y k o d u b l o k o w e g o
N a d m i a r k o d o w y
S p r a w n o [
n - k k k
Ák = = 1 - ·k = = 1 - Ák
n n n
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 5 / 5 4
P o d z i a B k o d ó w
z e w z g l d u s p o s ó b t r a n s m i s j i b i t ó w i n f o r m a c y j n y c h
K o d s y s t e m a t y c z n y r o z d z i e l n y
h 1 h 2 h 3 . . . h k b 1 . . . b n - k
f
h 1 h 2 h 3 . . . h k
b 1 . . . b n - k h 1 h 2 h 3 . . . h k
K o d y s y s t e m a t y c z n y n i e r o z d z i e l n y
f
h 1 h 2 h 3 . . . h k b 1 h 1 h 2 . . . h 3 . . . b n - k h k
K o d n i e s y s t e m a t y c z n y
f
h 1 h 2 h 3 . . . h k c 1 c 2 c 3 c 4 c 5 c 5 . . . c n
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 6 / 5 4
B l o k o w e k o d y l i n i o w e
P o d e j [c i e o g ó l n e
{ h }
{ c }
f u n k c j a l i n i o w a f
n p o z y c y j n e
k p o z y c y j n e
q - n a r n e c i g i
q - n a r n e c i g i
{ z }
k o d o w e
i n f o r m a c y j n e
w s z y s t k i e m o |l i w e
q - n a r n e c i g i
n - p o z y c y j n e
F u n k c j a f j e s t l i n i o w a , j e |e l i
d l a d o w o l n y c h h i , h "{ h } i
j
( q )
d o w o l n y c h l i c z b
a 1 , a 2 " C G
f ( a 1 Å" h i + a 2 Å" h j ) = a 1 Å" f ( h i ) + a 2 Å" f ( h j )
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 7 / 5 4
B l o k o w e k o d y l i n i o w e
P o d e j [c i e s z c z e g ó l n e
c 1 c 2 . . . c i - 1 c i c i + 1 . . . c n
S t r u k t u r a s Bo w a k o d u
h i i = 1 , 2 , . . . , k
ñø
c i =
òøb i = k + 1 , k + 2 , . . . , n
óø i - k
h 1 h 2 h 3 . . . h k b 1 . . . b n - k
w s z y s t k i e ( n - k ) b i t ó w p a r z y s t o [c i s l i n i o w y m i s u m a m i b i t ó w
i n f o r m a c y j n y c h :
b i = p 1 , i Å" h 1 + p 2 , i Å" h 2 + . . . + p k , i Å" h k
g d z i e :
1 j e [l i b i z a l e |y o d h i
ñø
p i j =
òø
óø0 w p r z y p a d k u p r z e c i w n y m
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 8 / 5 4
B l o k o w e k o d y l i n i o w e
T w o r z e n i e k o d u - p o d e j [c i e s z c z e g ó l n e
Z a p i s z m y r ó w n a n i a w p o s t a c i m a c i e r z o w e j
h = [ h 1 , h 2 , . . . , h k ]
b = [ b 1 , b 2 , . . . , b n - k ] b = h P
p 1 1 p 1 2 . . . p 1 , n - k
îø ùø
ïø
c = [ c 1 , c 2 , . . . , c n ]
p 2 1 p 2 2 . . . p 2 , n - k úø
ïø úø
P a"
ïø . . . . . . . . . . . . úø
ïø úø
p k 1 p k 2 . . . p k , n - k ûø
ðø
P o n i e w a | w e k t o r c j e s t z Bo |e n i e m
w e k t o r a h o r a z b t o : c = [ h | b ]
1 0 . . . 0
îø ùø
ïø0 1 . . . 0 úø
ïø úø
I k a"
S t d : c = h [ I k | P ]
ïø úø
. . . . . . . . . . . .
G = [ P | I k ] ,
ïø úø
ðø0 0 . . . 1 ûø
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 9 / 5 4
B l o k o w e k o d y l i n i o w e
T w o r z e n i e k o d u - p o d e j [c i e s z c z e g ó l n e
I w e f e k c i e m o |e m y z a p i s a :
c = h G
g d z i e :
G = [ I k | P ]
M a c i e r z G j e s t n a z y w a n a m a c i e r z g e n e r u j c k o d l i n i o w y
( n , k )
g 1 1 g 1 2 . . . g 1 n
îø ùø
ïøg g 2 2 . . . g 2 n úø
2 1
ïø úø
G a"
ïø . . . . . . . . . . . . úø
ïøg g k . . . g k n úø
ðø k 1 2 ûø
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 0 / 5 4
P r z y k Ba d 2 . 0
D l a c z e g o z a s t o s o w a n i e k o d u
n a d m i a r o w e g o p o z w a l a w y k r y b Bd y ?
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 1 / 5 4
B l o k o w e k o d y l i n i o w e
P o d e j [c i e o g ó l n e
{ ±} = { ±1 , ±2 , . . . , ±k }
N i e c h z b i ó r k l i n i o w o n i e z a l e |n y c h w e k t o r ó w
s t a n o w i b a z p r z e s t r z e n i { h } , a z b i ó r n l i n i o w o n i e z a l e |n y c h
{ ²} = { ²1 , ²2 , . . . , ²n }
w e k t o r ó w s t a n o w i b a z p r z e s t r z e n i { z } .
n
f = a l , i ²i , l = 1 2 , . . . , k .
( ±l ) ,
"
i = 1
A ’! M A , B B ,
l u b m a c i e r z o w o f
a 1 1 a 1 2 . . . a 1 n
îø±1 îø ùø ²1
ùø îø ùø
ïøa a 2 2 . . . a 2 n úø
ïø± úø ïø² úø
2 , 2
ïø úø
ïø úø, M A B = 2 1 ïø úø
A = B =
f
ïø . . . . . . . . . . . . úø
ïø . úø ïø . úø
ïøa a k . . . a k n úø
ïø± úø ïø² úø
ðø k 1 2 ûø
ðø k ûø ðø n ûø
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 2 / 5 4
B l o k o w e k o d y l i n i o w e
P o d e j [c i e o g ó l n e
P r z e d s t a w m y c i g i n f o r m a c y j n y h j a k o l i n i o w k o m b i n a c j
w e k t o r ó w b a z y { ±}
n
k
f ( ±l ) = ²i
"a l , i
k k k n
i = 1
ëø öø
h = ±l
"b c = f ( h ) = f ±l = f =
)
l ìø ÷ø ( ±l l l , i
"b "b "b "a ²i =
l l
íø øø
l = 1 l = 1 l = 1 l = 1 i = 1
n k n
k
=
ìø ÷ø "b
l
"ëø"b a öø²i = "d ²i , d i = a l , i
l l , i i
íø øø l = 1
i = 1 l = 1 i = 1
T o s a m o w z a p i s i e m a c i e r z o w y m
A B
,
h = b A ’! b M B = d B = c ,
f
{ ±}
w k t ó r e j k - p o z y c y j n y w e k t o r b o k r e [l a l i n i o w k o m b i n a c j w e k t o r ó w ±l " ,
A B
,
²i " ²
{ }
a n - p o z y c y j n y d = b M w e k t o r - k o m b i n a c j l i n i o w w e k t o r ó w
f
o d p o w i a d a j c c i g o w i k o d o w e m u c .
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 3 / 5 4
B l o k o w e k o d y l i n i o w e
W y z n a c z e n i e c i g ó w k o d o w y c h - p o d e j [c i e o g ó l n e
P r z y z a d a n y c h b a z a c h A i B o r a z z n a n e j f u n k c j i f , c i g k o d o w y c
o d p o w i a d a j c y c i g o w i i n f o r m a c y j n e m u h w y z n a c z a m y
n a s t p u j c o :
h = b A
- z r ó w n a n i a o k r e [l a m y b = h A - 1 ,
A B
,
- o b l i c z a m y d = b M
f
- w y z n a c z a m y c i g k o d o w y c = d B .
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 4 / 5 4
P r z y k Ba d 2 . 1
W y z n a c z a n i e c i g ó w k o d o w y c h
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 5 / 5 4
B l o k o w e k o d y l i n i o w e
W y z n a c z e n i e c i g ó w k o d o w y c h - p o d e j [c i e o g ó l n e
J e |e l i z a d a n e b a z y A i B s b a z a m i j e d n o s t k o w y m i o z n a c z o n y m i
A 1 i B 1 , t o
1
h = b ’! h M A , B 1 = c ,
f
a w i c m a c i e r z k o d o w a n i a
1
G a" M A , B 1
f
c = h G
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 6 / 5 4
P r z y k Ba d 2 . 2
W y z n a c z a n i e c i g ó w k o d o w y c h w
b a z a c h j e d n o s t k o w y c h
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 7 / 5 4
B l o k o w e k o d y l i n i o w e
K o d y [c i [l e r ó w n o w a |n e
h h G ' h G ' '
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0
0 1 1 0 1
0 1 0 0 1 1 0 1
1 1 1 1 1
0 1 1 0 0 1 1 1
1 0 0 1 0
1 0 0 1 1 0 0 0
0 0 1 1 1
1 0 1 1 0 0 1 0
0 1 0 1 0
1 1 0 1 0 1 0 1
1 1 0 0 0
1 1 1 1 1 1 1 1
1 0 1 0 1
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 8 / 5 4
P r z y k Ba d 2 . 3 i 2 . 4
W y z n a c z a n i e k o d ó w [c i [l e
r ó w n o w a |n y c h
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 1 9 / 5 4
L i n i o w e k o d y d u a l n e
M a c i e r z k o n t r o l n a k o d u , S y n d r o m
W n - w y m i a r o w e j p r z e s t r z e n i l i n i o w e j { z } z Bo |o n e j z w s z y s t k i c h
m o |l i w y c h q - n a r n y c h c i g ó w n - p o z y c y j n y c h i s t n i e j e j e d n a i t y l k o
j e d n a p o d p r z e s t r z e D ( n - k ) - w y m i a r o w a { v } z w i z a n a z
p o d p r z e s t r z e n i k o d o w { c } w t e n s p o s ó b , |e d l a d o w o l n i e
{ } { }
w y b r a n y c h c " c i v " v z n i k a i l o c z y n s k a l a r n y
c Å" v = 0
K o d l i n i o w y ( n , k ) m o |n a o k r e [l i - z d o k Ba d n o [c i d o k o d u
[c i [l e r ó w n o w a |n e g o - p r z e z p o d a n i e m a c i e r z y H g e n e r u j c e j
k o d d u a l n y ( n , n - k ) .
T
p r z y c z y m r = n - k .
H = - P k , r I r ,
[ ]
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 0 / 5 4
L i n i o w e k o d y d u a l n e
M a c i e r z k o n t r o l n a k o d u , S y n d r o m
I l o c z y n m a c i e r z y g e n e r u j c e j G k o d u ( n , k ) i m a c i e r z y g e n e r u j c e j k o d
d u a l n y ( n , n - k ) z e r u j e s i
G H T = O k r
îø- P k r
ùø
G H T = [ I k P k r ] ïø úø = - I k P k r + P k r I r = - P k r + P k r = O k r
I r
ðø ûø
M a c i e r z H n a z y w a s i m a c i e r z k o n t r o l n k o d u ( n , k ) . D l a k o d ó w
b i n a r n y c h ( q = 2 ) w y r a |e n i e o p i s u j c e m a c i e r z k o n t r o l n , p r z y j m u j e p o s t a
T
H = P k , r I r .
[ ]
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 1 / 5 4
L i n i o w e k o d y d u a l n e
S y n d r o m
Z m a c i e r z k o n t r o l n k o d u w i |e s i p o j c i e s y n d r o m u
b Bd ó w , z w a n e g o k r ó t k o s y n d r o m e m . S y n d r o m n - p o z y c y j n e g o
c i g u a d e f i n i u j e m y n a s t p u j c o
S ( a ) a" a H T
S y n d r o m j e s t c i g i e m r = n - k
S y n d r o m d l a c i g u k o d o w e g o j e s t r ó w n y w e k t o r o w i z e r o w e m u
S ( c ) = c H T = h G H T = O r
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 2 / 5 4
L i n i o w e k o d y d u a l n e
D e k o d o w a n i e z s y n d r o m e m
O z n a c z m y c i g o d e b r a n y p r z e z y = ( y 1 , y 2 , . . . , y n )
y = c + e
g d z i e e j e s t w e k t o r e m b Bd u z d e f i n i o w a n y m n a s t p u j c o
1 g d y j e s t b Bd n a i - t e j p o z y c j i
ñø
e = ( e 1 , e 2 , . . . , e n ) e i =
òø0 w p r z e c i w n y m p r z y p a d k u
óø
s = S ( y ) = S ( c + e ) = ( c + e ) H T = c H T + e H T = e H T = S ( e )
S y n d r o m j e s t c i g i e m r = n - k - p o z y c y j n y m z a l e |n y m t y l k o
o d r o z k Ba d u b Bd ó w
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 3 / 5 4
P r z y k Ba d 2 . 6
S y n d r o m
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 4 / 5 4
M e t r y k a p r z e s t r z e n i k o d o w e j
A n a l i z w Ba [c i w o [c i k o d ó w n a d m i a r o w y c h u Ba t w i a
z d e f i n i o w a n i e m e t r y k i p r z e s t r z e n i { z } , t o j e s t m i a r y o d l e g Bo [c i
p o m i d z y d o w o l n y m i " p u n k t a m i " ( e l e m e n t a m i ) t e j p r z e s t r z e n i .
J e |e l i a , b , c " { z } , t o m i a r a o d l e g Bo [c i d ( a , b ) m u s i s p e Bn i a
n a s t p u j c e a k s j o m a t y :
( 1 ) d ( a , b ) e" 0 ; d ( a , b ) = 0 t y l k o d l a a = b ;
( 2 ) d ( a , b ) d" d ( a , c ) + d ( c , b ) ;
( 3 ) d ( a , b ) = d ( b , a ) .
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 5 / 5 4
M e t r y k a H a m m i n g a
W a g H a m m i n g a p o z y c j i a i c i g u a n a z y w a m y l i c z b
0 , j e |e l i a i = 0 ;
ñø
( 2 . 3 9 )
w H a i a"
( )
òø1 , j e |e l i a i `" 0 .
óø
W a g H a m m i n g a c i g u a n a z y w a m y s u m w a g j e g o p o z y c j i
n
w H ( a ) a" w H a i . ( 2 . 4 0 )
( )
"
i = 1
O d l e g Bo [c i H a m m i n g a m i d z y c i g a m i a , b n a z y w a m y l i c z b
d H ( a , b ) a" w H ( a - b ) .
( 2 . 4 1 )
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 6 / 5 4
P r z y k Ba d 2 . 8
M e t r y k a H a m m i n g a
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 7 / 5 4
M e t r y k a H a m m i n g a
I n t e r p r e t a c j a g r a f i c z n a
c 3
0 0 1
0 1 1
1 0 1 1 1 1
c 2
0 1 0
0 0 0
1 0 0
1 1 0
c 1
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 8 / 5 4
M e t r y k a L e e
W a g L e e p o z y c j i a i q - n a r n e g o c i g u a s t a n o w i l i c z b a
q
ñø
a i , j e |e l i 0 d" a i < ,
ôø
2
w L ( a i ) a"
òø
q ( 2 . 4 4 )
ôø - a i , j e |e l i d" a i d" q - 1 .
q
óø 2
W a g L e e n - p o z y c y j n e g o q - n a r n e g o c i g u a n a z y w a m y s u m
w a g j e g o p o z y c j i
n
( 2 . 4 5 )
w L ( a ) a" ( a i ) .
"w
L
i = 1
O d l e g Bo [ L e e d w ó c h n - p o z y c y j n y c h q - n a r n y c h c i g ó w a i b
d e f i n i u j e s i j a k o
d L ( a , b ) a" w L ( a - b ) .
( 2 . 4 6 )
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 2 9 / 5 4
P r z y k Ba d 2 . 1 0
M e t r y k a L e e
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 0 / 5 4
Z d o l n o [ d e t e k c y j n a k o d u n a d m i a r o w e g o
O d l e g Bo [ m i n i m a l n a k o d u n a d m i a r o w e g o
( 2 . 4 7 )
d m i n a" m i n d c i , c .
( )
j
i , j = 1 2 , . . . , q k
,
i `" j
Z d o l n o [ d e t e k c y j n a k o d u - n a j w i k s z a k r o t n o [ b Bd ó w
w y k r y w a n y c h p r z e z b l o k o w y k o d n a d m i a r o w y ( n , k ) o
o d l e g Bo [c i m i n i m a l n e j d m i n w y n o s i
³ = d m i n - 1 .
( 2 . 4 8 )
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 1 / 5 4
Z d o l n o [ k o r e k c y j n a k o d u n a d m i a r o w e g o
R e g u Ba d e c y z y j n a
O p t y m a l n r e g u B d e c y z y j n w p r z y p a d k u d e k o d o w a n i a
k o r e k c y j n e g o j e s t r e g u Ba m a k s y m a l i z u j c a
p r a w d o p o d o b i e Ds t w o a p o s t e r i o r i P ( c | y ) n a d a n i a c i g u c = c * ,
p r z y w a r u n k u |e z o s t a B o d e b r a n y c i g y .
c " = c l t a k i , |e d ( c l , y ) d" d ( c i , y ) ;
i = 1 , 2 , . . . q k ;
( 2 . 4 9 )
i `" l
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 2 / 5 4
Z d o l n o [ k o r e k c y j n a k o d u n a d m i a r o w e g o
R e p r e z e n t a c j a g r a f i c z n a
d m i n = 4
c 1 c 2
d m i n = 3
c 1 c 2
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 3 / 5 4
Z d o l n o [ k o r e k c y j n a k o d u n a d m i a r o w e g o
Z d o l n o [ k o r e k c y j n a k o d u o k r e [l a n a j w i k s z a k r o t n o [ b Bd ó w
k o r y g o w a n y c h p r z e z l i n i o w y k o d n a d m i a r o w y ( n , k ) o
o d l e g Bo [c i m i n i m a l n e j d m i n i w y n o s i
d m i n
ñø - 1 ( 2 . 5 0 )
üø
t = E ,
òø ýø
2
óø þø
p r z y c z y m E { x } o z n a c z a c z [ c a Bk o w i t l i c z b y x .
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 4 / 5 4
t
t
t
t
M e t o d y w y z n a c z a n i e d m i n
1 . K o r z y s t a j c z w Ba [c i w o [c i b l o k o w y c h k o d ó w l i n i o w y c h :
S u m a d w ó c h d o w o l n y c h w e k t o r ó w k o d o w y c h d a j e w
w y n i k u i n n y w e k t o r k o d o w y , a w i c :
d m i n = m i n ( w H ( c i ) ) i = 1 , 2 , . . . , q k p r z y c z y m c i `" 0
1 . K o r z y s t a j c z m a c i e r z y k o n t r o l n e j H T .
T
M i n i m a l n a l i c z b a w i e r s z y m a c i e r z y H s u m u j c y c h s i d o
w e k t o r a z e r o w e g o w y z n a c z a d m i n k o d u
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 5 / 5 4
D e k o d o w a n i e k o r e k c y j n e
T a b l i c a d e k o d o w a n i a q - n a r n e g o b l o k o w e g o k o d u l i n i o w e g o ( n , k )
¶1 = c 1 = O n c 2 & c l & c q
k
¶2 c 2 + ¶2 & c l + ¶2 & c q + ¶2
k
& & & & & &
¶m c 2 + ¶m & c l + ¶m & c q + ¶m
k
& & & & & &
¶q c 2 + ¶q & c l + ¶q & c q + ¶q
r r r k r
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 6 / 5 4
D e k o d o w a n i e k o r e k c y j n e
W Ba [c i w o [c i t a b l i c y d e k o d o w a n i a
T a b l i c a d e k o d o w a n i a c h a r a k t e r y z u j e s i n a s t p u j c y m i
w Ba [c i w o [c i a m i :
w t a b l i c y n i e w y s t p u j p o w t a r z a j c e s i e l e m e n t y ,
e l e m e n t y t e j s a m e j w a r s t w y m a j t e n s a m s y n d r o m ,
r ó |n i c a d w ó c h c i g ó w n a l e |c y c h d o t e j s a m e j w a r s t w y j e s t
c i g i e m k o d o w y m ,
r ó |n i c a d w ó c h c i g ó w n a l e |c y c h d o r ó |n y c h w a r s t w n i e j e s t
c i g i e m k o d o w y m ,
e l e m e n t y n a l e |c e d o r ó |n y c h w a r s t w m a j r ó |n e s y n d r o m y ,
w t e j s a m e j w a r s t w i e n i e m o |e w y s t p i w i c e j n i | j e d e n c i g o
w a d z e w i k s z e j n i | z d o l n o [ k o r e k c y j n a k o d u t ,
o z n a c z m y k o l u m n t a b l i c y d e k o d o w a n i a z a w i e r a j c c i g k o d o w y
c l p r z e z “l ; d l a i `" l n i e i s t n i e j e |a d e n t a k i c i g k o d o w y c i , k t ó r y
l e |a Bb y b l i |e j c i g ó w z n a l e |c y c h d o k o l u m n y “l n i | c i g k o d o w y
c l .
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 7 / 5 4
D e k o d o w a n i e k o r e k c y j n e
R e g u Ba k o r y g o w a n i a b Bd ó w
K o r y g o w a n i e b Bd ó w o p i e r a s i n a n a s t p u j c e j r e g u l e :
j e |e l i ( 2 . 5 5 )
y "“m , t o c * = c m .
D e k o d o w a n i e k o r e k c y j n e p r z e b i e g a w t r z e c h e t a p a c h :
" o b l i c z e n i e s y n d r o m u S ( y ) o d e b r a n e g o c i g u y ,
" o d s z u k a n i e , n a p o d s t a w i e S ( y ) , e l e m e n t u ¶ t w o r z c e g o
w a r s t w , w k t ó r e j l e |y c i g y ,
" s k o r y g o w a n i e b Bd ó w w e d Bu g z a l e |n o [c i
c * = y - ¶
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 8 / 5 4
P r z y k Ba d 2 . 1 1
P r z y k Ba d t w o r z e n i a k o d u o r a z j e g o
t a b l i c y d e k o d o w a n i a
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 3 9 / 5 4
W y b r a n e k o d y l i n i o w e
K o d z k o n t r o l p a r z y s t o [c i
K o d z m - k r o t n y m p o w t a r z a n i e m
K o d i t e r o w a n y m - k r o t n i e
K o d y H a m m i n g a
W y d Bu |o n y k o d l i n i o w y
K o d y r ó w n o l e g Be
K o d y M a c D o n a l d a
K o d y R e e d a - M u l l e r a
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 0 / 5 4
W y b r a n e k o d y l i n i o w e
K o d z k o n t r o l p a r z y s t o [c i
C i g k o d o w y t e g o k o d u p o w s t a j e w w y n i k u d o Bc z e n i a d o c i g u
i n f o r m a c y j n e g o j e d n e j p o z y c j i k o n t r o l n e j , t a k a b y i l o [ j e d y n e k w c i g u
b y Ba p a r z y s t a .
M a c i e r z g e n e r u j c a
h 1 h 2 h 3 . . . h n - 1 b 1
G = [ I n - 1 | 1 n - 1 ]
M a c i e r z k o n t r o l n a
P a r a m e t r y k o d u : ( n , n - 1 )
H = 1 n
[ ]
1
· = 1 -
S p r a w n o [:
R e g u Ba k o d o w a n i a
n
O d l e g Bo [ m i n i m a l n a : d m i n = 2
n
c i = 0
"
K o d w y k r y w a p o j e d y n c z e b Bd y
i = 1
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 1 / 5 4
W y b r a n e k o d y l i n i o w e
K o d z m - k r o t n y m p o w t ó r z e n i e m
C i g i k o d o w e t e g o k o d u p o w s t a j w w y n i k u m - k r o t n e g o p o w t ó r z e n i a
c i g u i n f o r m a c y j n e g o
h 1 h 2 . . . h k h 1 h 2 . . . h k . . . . . . h 1 h 2 . . . h k
1 2 . . . m
O z n a c z e n i e k o d u : ( m k , k ) M a c i e r z k o n t r o l n a M a c i e r z g e n e r u j c a
· = 1 m
S p r a w n o [: I k
îø ùø
ïøI úø
O d l e g Bo [ m i n i m a l n a : d m i n = m
k
ïø úø
ïø M I ( m - 1 ) , k úø
H =
G = I k I . . . I
[ ]
1 4 k 3
2 4 k
R e g u Ba k o d o w a n i a
ïøI úø
m r a z y
k
ïø úø
{
c = ( h , h , . . . , h )
ïøm - 1 úø
1 4 2 4
3
ðør a z y ûø
m r a z y
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 2 / 5 4
W y b r a n e k o d y l i n i o w e
K o d i t e r o w a n y m - k r o t n i e
C i g i k o d o w e t e g o k o d u p o w s t a j w w y n i k u m - k r o t n e g o k o d o w a n i a
i n f o r m a c j i m k o d a m i w e d Bu g n a s t p u j c y c h r e g u B:
1 . C i g i n f o r m a c y j n y h o d Bu g o [c i k = k 1 × k 2 × k 3 × · · · × k m p r z e d s t a w i a s i
w p o s t a c i m - w y m i a r o w e g o " p r o s t o p a d Bo [c i a n u " o w y m i a r a c h
k 1 × k 2 × k 3 × · · · × k m w u k Ba d z i e w s p ó Br z d n y c h x 1 , x 2 , x 3 , x 1 , . . . , x m .
2 . P o d c i g i i n f o r m a c y j n e o d Bu g o [c i k 1 , u m i e s z c z o n e r ó w n o l e g l e d o o s i
O x 1 , k o d u j e s i k o d e m ( n 1 , k 1 ) . W w y n i k u t e j o p e r a c j i p o w s t a j e
p r o s t o p a d Bo [c i a n o w y m i a r a c h n 1 × k 2 × k 3 × · · · × k m .
3 . P o d o b n i e , p o d c i g i i n f o r m a c y j n e o d Bu g o [c i k 2 , u m i e s z c z o n e
r ó w n o l e g l e d o o s i O x 2 , k o d u j e s i k o d e m ( n 2 , k 2 ) , o t r z y m u j c
p r o s t o p a d Bo [c i a n o w y m i a r a c h n 1 × n 2 × k 3 × · · · × k m .
4 . P o s t p u j c w t e n s p o s ó b z e w s z y s t k i m i p o d c i g a m i i n f o r m a c y j n y m i ,
t z n . k o d u j c j e k o d a m i . . . , ( n 3 , k 3 ) , ( n 4 , k 4 ) , . . . , ( n m , k m ) , o t r z y m u j e m y
c i g k o d o w y w p o s t a c i m - w y m i a r o w e g o p r o s t o p a d Bo [c i a n u o
w y m i a r a c h n 1 × n 2 × n 3 × · · · × n m
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 3 / 5 4
K o d i t e r o w a n y m - k r o t n i e
c d . .
O z n a c z e n i e k o d u : S p r a w n o [: O d l e g Bo [ m i n i m a l n a :
m m
m m
ëø öø
· = ·i . d m i n =
n i , k i
ìø ÷ø " "d ;
" " m i n i
íø øø
i = 1 i = 1
i = 1 i = 1
P r z y k Ba d
K o d d w u k r o t n i e i t e r o w a n y ( 4 0 , 1 6 ) m o |n a u z y s k a s t o s u j c n a s t p u j c e
d w a k o d y : k o d z p o w t a r z a n i e m ( 8 , 4 ) o r a z k o d z k o n t r o l p a r z y s t o [c i ( 5 , 4 )
h = 1 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 0 1
1 1 0 0 1 1 0 0
0 0 1 1 0 0 1 1
1 0 0 0 1 0 0 0
1 1 1 0 1 1 1 0
c = 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 4 / 5 4
W y b r a n e k o d y l i n i o w e
K o d H a m m i n g a
O b e c n i e j e s t t o k a |d y b l o k o w y k o d l i n i o w y ( n , k ) , s p e Bn i a j c y n a s t p u j c e
p a r a m e t r y : n = 2 m - 1 , k = 2 m - m - 1 , d m i n = 3 p r z y c z y m m j e s t l i c z b n a t u r a l n .
P r z y k Ba d e m k o d u H a m m i n g a m o |e b y k o d ( 7 , 4 ) g e n e r o w a n y p r z e z
m a c i e r z :
M a c i e r z k o n t r o l n a k o d u
1 1 1 0 0 0 0
îø ùø
ïø1 0 0 1 1 0 0 úø
îø ùø
0 0 0 1 1 1 1
ïø úø
G =
ïø úø
ïø úø
0 1 0 1 0 1 0
H = 1 1 0 0 1 1 úø
ïø0
ïø1 1 0 1 0 0 1 úø
ïø1 0 1 0 1 0 1 úø
ðø ûø
ðø ûø
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 5 / 5 4
W y b r a n e k o d y l i n i o w e
W y d Bu |o n y k o d l i n i o w y
W y d Bu |o n y k o d l i n i o w y p o w s t a j e z k o d u l i n i o w e g o ( n 1 , k ) o
n i e p a r z y s t e j o d l e g Bo [c i m i n i m a l n e j d ` m i n . P r o c e d u r a w y d Bu |a n i a p o l e g a n a
w p r o w a d z e n i u d o w y j [c i o w e g o c i g u k o d o w e g o d o d a t k o w e j p o z y c j i
k o n t r o l n e j , s p r a w d z a j c e j p a r z y s t o [ j e d y n e k w e d Bu g r e g u By
c i d l a i = 1 2 , . . . , n - 1 ;
,
ñø
ôø
n - 1
c i =
òø
c i d l a i = n .
"
ôø
óø i = 1
d m i n = d ' m i n + 1 .
W y d Bu |o n y k o d l i n i o w y m a p a r z y s t o d l e g Bo [ m i n i m a l n
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 6 / 5 4
W y b r a n e k o d y l i n i o w e
K o d r ó w n o o d l e g By
C i g k o d o w y t e g o k o d u z a w i e r a w s z y s t k i e k o m b i n a c j e
l i n i o w e p o z y c j i c i g u i n f o r m a c y j n e g o , t z n . :
k
ëø öø
h 1 , h 2 , . . . , h k ;
= k
ìø ÷ø p o z y c j i i n f o r m a c y j n y c h :
1
íø øø
k
ëø öø
ìø ÷ø
,
p o z y c j i k o n t r o l n y c h t y p u h i + h j ; i , j = 1 2 , . . . , k ; i `" j ;
2
íø øø
M
k
ëø öø
p o z y c j i k o n t r o l n y c h t y p u
ìø ÷ø
m
íø øø
h i + h j + . . . + h m ; i , j , m = 1 2 , . . . , k ; i `" j `". . . `" m ;
,
k
k
ëø öø
ìø ÷ø = 1 p o z y c j k o n t r o l n t y p u
"h .
i
k
íø øø
i = 1
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 7 / 5 4
W y b r a n e k o d y l i n i o w e
K o d r ó w n o o d l e g By c d . .
D Bu g o [ c i g u O z n a c z e n i e k o d u : O d l e g Bo [ m i n i m a l n a :
k
k
n = ìø ÷ø = 2 k - 1
( 2 k - 1 , k ) d m i n = 2 k - 1
"ëø öø
ìø ÷ø
i
i = 1
íø øø
P r z y k Ba d
D l a k = 4 o t r z y m u j e s i k o d r ó w n o o d l e g By ( 1 5 , 4 ) , k t ó r e g o
c i g i o p i s u j e z a l e |n o [:
c = h 1 , h 2 , h 3 , h 4 , ( h 1 + h 2 ) , ( h 1 + h 3 ) , ( h 1 + h 4 ) , ( h 2 + h 3 ) , ( h 2 + h 4 ) , ( h 3 + h 4 ) ,
( h 1 + h 2 + h 3 ) , ( h 1 + h 2 + h 4 ) , ( h 1 + h 3 + h 4 ) , ( h 2 + h 3 + h 4 ) , ( h 1 + h 2 + h 3 + h 4 ) .
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 8 / 5 4
W y b r a n e k o d y l i n i o w e
K o d M a c D o n a l d a
C i g k o d o w y z a w i e r a :
- p o z y c j e i n f o r m a c y j n e w l i c z b i e k , d l a k t ó r y c h z a c h o d z i
c i = h i , j = 1 , 2 , K , k ;
j
- p o z y c j e k o n t r o l n e w p o s t a c i c o n a j m n i e j d w u a r g u m e n t o w y c h
k o m b i n a c j i l i n i o w y c h p o z y c j i c i g u i n f o r m a c y j n e g o .
P r z y k Ba d
K o d M a c D o n a l d a ( 1 5 , 4 ) , k t ó r e g o c i g i o p i s u j e z a l e |n o [:
c = h 1 , h 2 , h 3 , h 4 , ( h 1 + h 2 + h 3 ) , ( h 1 + h 2 + h 4 ) , ( h 1 + h 3 + h 4 ) , ( h 2 + h 3 + h 4 ) , ( h 1 + h 2 + h 3 + h 4 )
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 4 9 / 5 4
W y b r a n e k o d y l i n i o w e
K o d R e e d a - M u l l e r a
P a r a m e t r y b i n a r n y c h k o d ó w R M s n a s t p u j c e :
»
m
ëø öø
n = 2 m ; k = ; d m i n = 2 m - » ;
ìø ÷ø
"
i
íø øø
i = 0
p r z y c z y m m , » - l i c z b y n a t u r a l n e ( m > ») ; » - r z d k o d u
K o n s t r u k c j a k o d ó w R M o p i e r a s i n a n - w y m i a r o w e j p r z e m i e n n e j
i Bc z n e j a l g e b r z e , j a k a p o w s t a j e w w y n i k u w p r o w a d z e n i a w n - w y m i a r o w e j
p r z e s t r z e n i l i n i o w e j o p e r a c j i m n o |e n i a w e k t o r o w e g o c i g ó w ,
z d e f i n i o w a n e j n a s t p u j c o :
a × b a" a 1 b 1 , a 2 b 2 , . . . , a n b n .
( )
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 5 0 / 5 4
K o d R e e d a - M u l l e r a c d . .
T w o r z e n i e b a z y
D l a z a d a n e j w a r t o [c i m k o n s t r u u j e s i a l g e b r , k t ó r e j b a z B m
s t a n o w i n a s t p u j c e n - p o z y c y j n e c i g i b i n a r n e :
- c i g u 0 z Bo |o n y z s a m y c h j e d y n e k ;
- m c i g ó w u i , i = 1 , 2 , . . , m , k t ó r e w y p i s a n e p o d s o b t w o r z
m a c i e r z o k o l u m n a c h b d c y c h m - p o z y c y j n y m i c i g a m i
b i n a r n y m i ;
m
ëø öø
u i j = u i × u d l a i , j = 1 , 2 , . . . , m , i `" j ;
- ìø ÷ø
c i g ó w t y p u j
2
íø øø
m
ëø öø
- c i g ó w t y p u a | d o c i g u t y p u :
ìø ÷ø
3
íø øø
u i j l = u i × u × u l d l a i , j , l = 1 , 2 , . . . , m , i `" j , l , j `" l i t d . ,
j
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 5 1 / 5 4
K o d R e e d a - M u l l e r a c d . .
P r z y k Ba d b a z y B 4
u
0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
u
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
1
u
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
2
u
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
3
u
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
4
u
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 2
u
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
1 3
u
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
1 4
u
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
2 3
u
0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1
2 4
u
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
3 4
u
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
1 2 3
u
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
1 2 4
u
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
1 3 4
u
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
2 3 4
u
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 2 3 4
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 5 2 / 5 4
W y b r a n e k o d y l i n i o w e
K o d R e e d a - M u l l e r a c d . .
M a c i e r z g e n e r u j c a i k o n t r o l n a k o d ó w R M j e s t z Bo |o n a
z n a s t p u j c y c h w e k t o r ó w b a z o w y c h b a z y B m :
u 0
îø ùø
u 0
îø ùø
ïø úø
u 1
ïø úø
ïø úø
u 1
ïø úø
H =
ïø M úø
ïø M úø
ïø úø
u m
ïøu úø
ïø úø
G =
ðø m ûø
ïø úø
u 1 2
ïø úø
u 1 3
ïø úø
ïø úø
M
u i i 2 . . . i l d l a l d" ».
W s z y s t k i e
1
ïø úø
ïøu i 1 i 2 K i l úø
ðø ûø
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 5 3 / 5 4
K O N I E C
D z i k u j z a u w a g
R o b e r t B o r o w i e c K o d o w a n i e i k r y p t o g r a f i a
W y k Ba d I V , s t r o n a 5 4 / 5 4
Wyszukiwarka
Podobne podstrony:
W14 Kodowanie i Kryptografia kody cykliczne?le 6gW15 Kodowanie i Kryptografia kody splotowe?leW6 Kodowanie i Kryptografia Kody klasyczne kryptoanaliza 1gW10 Kodowanie i Kryptografia Funkcje jednokierunkoweminutW8 Kodowanie i Kryptografia Algorytmy niesymetryczne 1gW12 Kodowanie i Kryptografia Rozdzielanie tajemnicy 1gW3 Kodowanie i Kryptografia Algebra 2 2gW1 Kodowanie i Kryptografia Systemy cyfrowe 1gW11 Kodowanie i Kryptografia Protokoy kryptograficzne 2gW2 Kodowanie i Kryptografia Algebra 1 2gW9 Kodowanie i Kryptografia Podpisy cyfrowe 1gW7 Kodowanie i Kryptografia Szyfry symetryczne 2gW4 Kodowanie i Kryptografia Wprowadzenie do kryptografii 2gW5 Kodowanie i Kryptografia Szyfry klasyczne 2gKody korekcyjne i kryptografiaNokia kody servisoweHeidenhain frezarka iTNC 530 G kody plKryptografia wykladwięcej podobnych podstron