This paper presents a medical image encryption algorithm using edge maps derived from a source image. The algorithm is composed by three parts: bit-plane decomposition, generator of random sequence, and permutation. It offers users the following flexibilities: (1) any type of images can be used as the source image; (2) different edge maps can be generated by various edge detectors and thresholds; (3) selection of appropriate bit-plane decomposition method is flexible; (4) many permutation methods can be cascaded with the proposed algorithm. A significantly large key space and strong key sensitive are possessed by the proposed algorithm to protect different types of medical images. Furthermore, it has a wider applicability than other methods for fuzzy edge maps. Experiments and security analysis further demonstrate that it has a strong resistance against various security attacks and outperforms other state-of-the-art methods.