In [9] Matsui introduced a new method of cryptanalysis, called Linear Cryptanalysis. This method was used to attack DES using 247 known plaintexts. In this paper we formalize this method and show that although in the details level this method is quite different from differential cryptanalysis, in the structural level they are very similar. For example, characteristics can be defined in linear cryptanalysis, but the concatenation rule has several important differences from the concatenation rule of differential cryptanalysis. We show that the attack of Davies on DES is closely related to linear cryptanalysis. We describe constraints on the size of S boxes caused by linear cryptanalysis. New results to Feal are also described.