انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

stream cipher

الكلية كلية تكنولوجيا المعلومات     القسم قسم البرامجيات     المرحلة 4
أستاذ المادة بهيجة خضير شكر الغانمي       4/6/2011 9:30:02 AM
 

Stream Ciphers
? Generalization of one-time pad
? Trade provable security for practicality
? Stream cipher is initialized with short key
? Key is “stretched” into long keystream
? Keystream is used like a one-time pad
? XOR to encrypt or decrypt
? Stream cipher is a keystream generator
? Usually, keystream is bits, sometimes bytes

Stream Cipher
? We consider 3 real stream ciphers
? ORYX — weak cipher, uses shift registers,
generates 1 byte/step
? RC4 — strong cipher, widely used but used
poorly in WEP, generates 1 byte/step
? PKZIP — intermediate strength, unusual
mathematical design, generates 1 byte/step
? But first, we discuss shift registers

Shift Registers
? Traditionally, stream ciphers were based
on shift registers
o Today, a wider variety of designs
? Shift register includes
o A series of stages each holding one bit
o A feedback function
? A linear feedback shift register (LFSR)
has a linear feedback function

 

Berlekamp-Massey Algorithm
? Given (part of) a (periodic) sequence,
can find shortest LFSR that could
generate the sequence
? Berlekamp-Massey algorithm
o Order N2, where N is length of LFSR
o Iterative algorithm
o Only 2N consecutive bits required

Berlekamp-Massey Algorithm
? Binary sequence: s = (s0,s1,s2,…,sn-1)
? Linear complexity of s is the length of
shortest LFSR that can generate s
? Let L be linear complexity of s
? Then connection polynomial of s is of form
C(x) = c0 + c1x + c2x2 + … + cLxL
? Berlekamp-Massey finds L and C(x)
o Algorithm on next slide (where d is known as the
discrepancy)


Berlekamp-Massey Algorithm
? Berlekamp-Massey is efficient way to
determine minimal LFSR for sequence
? With known plaintext, keystream bits of
stream cipher are exposed
? With enough keystream bits, can use
Berlekamp-Massey to find entire keystream
o 2L bits is enough, where L is linear complexity of
the keystream

Stream Ciphers
? Generalization of one-time pad
? Trade provable security for practicality
? Stream cipher is initialized with short key
? Key is “stretched” into long keystream
? Keystream is used like a one-time pad
? XOR to encrypt or decrypt
? Stream cipher is a keystream generator
? Usually, keystream is bits, sometimes bytes

Stream Cipher
? We consider 3 real stream ciphers
? ORYX — weak cipher, uses shift registers,
generates 1 byte/step
? RC4 — strong cipher, widely used but used
poorly in WEP, generates 1 byte/step
? PKZIP — intermediate strength, unusual
mathematical design, generates 1 byte/step
? But first, we discuss shift registers

Shift Registers
? Traditionally, stream ciphers were based
on shift registers
o Today, a wider variety of designs
? Shift register includes
o A series of stages each holding one bit
o A feedback function
? A linear feedback shift register (LFSR)
has a linear feedback function

 

Berlekamp-Massey Algorithm
? Given (part of) a (periodic) sequence,
can find shortest LFSR that could
generate the sequence
? Berlekamp-Massey algorithm
o Order N2, where N is length of LFSR
o Iterative algorithm
o Only 2N consecutive bits required

Berlekamp-Massey Algorithm
? Binary sequence: s = (s0,s1,s2,…,sn-1)
? Linear complexity of s is the length of
shortest LFSR that can generate s
? Let L be linear complexity of s
? Then connection polynomial of s is of form
C(x) = c0 + c1x + c2x2 + … + cLxL
? Berlekamp-Massey finds L and C(x)
o Algorithm on next slide (where d is known as the
discrepancy)


Berlekamp-Massey Algorithm
? Berlekamp-Massey is efficient way to
determine minimal LFSR for sequence
? With known plaintext, keystream bits of
stream cipher are exposed
? With enough keystream bits, can use
Berlekamp-Massey to find entire keystream
o 2L bits is enough, where L is linear complexity of
the keystream

Stream Ciphers
? Generalization of one-time pad
? Trade provable security for practicality
? Stream cipher is initialized with short key
? Key is “stretched” into long keystream
? Keystream is used like a one-time pad
? XOR to encrypt or decrypt
? Stream cipher is a keystream generator
? Usually, keystream is bits, sometimes bytes

Stream Cipher
? We consider 3 real stream ciphers
? ORYX — weak cipher, uses shift registers,
generates 1 byte/step
? RC4 — strong cipher, widely used but used
poorly in WEP, generates 1 byte/step
? PKZIP — intermediate strength, unusual
mathematical design, generates 1 byte/step
? But first, we discuss shift registers

Shift Registers
? Traditionally, stream ciphers were based
on shift registers
o Today, a wider variety of designs
? Shift register includes
o A series of stages each holding one bit
o A feedback function
? A linear feedback shift register (LFSR)
has a linear feedback function

 

Berlekamp-Massey Algorithm
? Given (part of) a (periodic) sequence,
can find shortest LFSR that could
generate the sequence
? Berlekamp-Massey algorithm
o Order N2, where N is length of LFSR
o Iterative algorithm
o Only 2N consecutive bits required

Berlekamp-Massey Algorithm
? Binary sequence: s = (s0,s1,s2,…,sn-1)
? Linear complexity of s is the length of
shortest LFSR that can generate s
? Let L be linear complexity of s
? Then connection polynomial of s is of form
C(x) = c0 + c1x + c2x2 + … + cLxL
? Berlekamp-Massey finds L and C(x)
o Algorithm on next slide (where d is known as the
discrepancy)


Berlekamp-Massey Algorithm
? Berlekamp-Massey is efficient way to
determine minimal LFSR for sequence
? With known plaintext, keystream bits of
stream cipher are exposed
? With enough keystream bits, can use
Berlekamp-Massey to find entire keystream
o 2L bits is enough, where L is linear complexity of
the keystream

 


المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .