RDES cryptosystem is an n-round DES in which an probabilistic swapping is added onto the right half of the input in each round. It is more effective than a simple increase of DES rounds for a countermeasure against differential attack. In this paper, we show that the RDES is also effective against linear cryptanalysis. We applied Matsui's search algorithm to find the best expression for RDES-1 and RDES-2. The results are as follows: (a) The 16-round RDES-1 is approximately as strong as a 22-round DES, and the 16-round RDES-2 is approximately as strong as a 29-round DES. (b) Linear cryptanalysis for a 16-round RDES-1 and a 16-round RDES-2 requires more than 264 known-plaintexts.