Berlekamp Massy Algorithm As A Cryptanalysis Tool Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Nowadays many modern and reasonable secure communication systems like Personnel Computers, networks, SSL, mobile phone, Bluetooth etc. require a high speed binary encoding algorithms to encrypt messages that can be millions of bits long and impressive display structure. The most commonly used encryption in this case is stream cipher. A stream cipher encryption explains the process itself which is to encrypt binary plain text one bit at a time. Mostly and simplest stream cipher used for encrypting binary plaintext is where a time interval t of a pseudo random sequence zt is combined with module two of XOR with the plaintext bit mt, with cipher text bit represented by ct. following expression shows the simple stream cipher explanation:

ct = mt ' zt

where ' denotes XOR(Exclusive OR). The decryption process can be expressed as :

mt = ct ' zt

It should be noted from the equations that both encryption and decryption need to able to generate the same key stream sequence zt. The encryption key K is the initial seed to start the generator. Both the encryptor and decryptor have to address this key. The most common method of forming the streams is that zt be applied to non-linear boolean function f of the production of binary sequences by linear feedback shift register(LFSR's) which is characteristic primitive polynomial.


Cryptography or cryptology is a branch of computer science and mathematics dealing with information security and related issues mostly encryption and authentication and applications like access control. Cryptography as an interdisciplinary theme, based on several fields. Before the start of 20th century cryptography was primarily concerned linguistic patterns. Since then, the focus has been shifted and cryptography is widely using mathematics. Cryptography is also the branch of engineering but an unusual one, since it only deal of active, intelligent and malevolent opposition.

Cryptography is the main tool for information security and network such as access control and confidentiality. Cryptography has many applications affecting the daily life of the security like ATM cards, computer passwords, and electronic commerce, they all depend on cryptography.


In cryptography, a stream cipher is a symmetric encryption algorithm, where plaintext digits encrypted one at a time and successive digits varies during the process of encryption. Following figure show the encryption of each digit depends on the current state, typically one bit at a time.

Stream cipher represent a different approach to symmetric encryption as compared to block cipher. Block cipher working with large blocks of digits in the fixed unvarying transformation. This distinction is not always easy. Some operations use block cipher primitive effectively as compared to stream cipher. Stream cipher is normally conducted at higher speeds as compared to block cipher and have lower hardware complexity.

There are some well known stream ciphers

RC4, used in Netscape's Secure Socket Layer (SSL) protocol.

A5, in the global system for mobile communication(GSM).

Bluetooth stream cipher, standard for wireless short-range connectivity, specified by the blue tooth special interest group.

Word-oriented stream ciphers, suitable for software implementation (e.g. SNOW, SOBER, SCREAM).

Stream cipher modes of operation of block cipher (e.g. cipher feedback, output feedback mode of triple DES or AES).


Cryptanalysis is analysis or study the method to obtain the encrypted information, without access to secret information generally required to do so. This usually involves finding the secret key. Non-technically this is the practice of breaking the code or cracking the code but these sentences can also have a special technique report. Cryptanalysis is also used to refer to any attempt to circumvent the security of other types of cryptographic algorithms and protocols in general, not just encryption. However, cryptanalysis usually excludes the possibility that the attacks are not primarily target weaknesses actual cryptographic methods such as corruption, physical coercion, burglary, key logging and so on. Although the latter type of attack is important to affect the security of computers and more effective than traditional cryptanalysis.


The linear complexity of binary sequences of the length of the shortest LFSR that can be produced in the series. For a series it is also suitable to use an enciphering sequence in a stream cipher it is important that it has a sufficiently large linear complexity. There are two forms of linear complexity, global linear complexity infinite binary sequence in the same period, and the local linear complexity of binary sequence of finite length.

Any finite binary sequence of period p can be generated by linear recurrence of length p or less. The linear complexity of the shortest sequence of such a recurrence is to establish the series. This is equivalent to saying that the linear complexity is the length of the shortest LFSR that create the sequence. The berlekamp-massey algorithm is an effective procedure for searching the shortest length LFSR of a given finite sequence. If the linear complexity is m, the algorithm requires at least 2m bit series. If the encryption key has the small linear complexity, then it will be replicate to short LFSR. This is not desirable, therefore, the encryption key must has a large linear complexity.

The following is the berlekamp-massey algorithm that is expert in the typical binary finite fields F2 and GF(2). The elements 0 and 1 in the field operations + and - is the same and become the sole property exclusive OR operation(XOR). * the multiplication operator is a logical and operation. The division operator reduces to the identity operation i.e. the area defined in the for the dividing by 1 and x/1=1.

Let s0, s1,s3,.....Sn be the bits of stream.

Initialize two blocks b and c length n with zeros, except b01, c01.

Assign L ← 0, m ← -1.

for n = 0 step 1 while N<n.

Let d be Sn + c1Sn-1 + c2Sn-2 +.....cLSn-L.

If d = 0, then c is already a polynomial which destroy part of the flow N-NL to N.


let t be a copy of c

Set up to (where is the Exclusive or operator).

If , set , set , and let ; otherwise leave L, m and b alone.

At the end of algorithms=, L is the minimum length LFSR stream, and we have for all a.

This section describes the implementation of the berlekamp-massey algorithm to find the linear complexity of a given series. Two new methods for encrypting data stream are, an attack first known attack using the combination part of the assumption that the data are a major threat to the right answer. The second method, an attacker combines part of the discovery of unknown behaviour(truth table), the combination of the algorithm into two parts. Once we find the truth table of the combining part, we then find the initial values of the record keeping part or drawing a map combining some functions to help you reverse engineering algorithm for reconstruction and participate in the combines.


It can be concluded that as a consequence of applying the methods under study:

encryption stream is not recommended to use confidentiality because the stream cipher is vulnerable

to prevent a planned attack suggested that the number of LFSR is a part that must exceed the ability to perform the algorithm, which means the number of LFSR must be above 20 with nowadays computational capability.