Block ciphers based on key-dependent cipher structures have been investigated for years, however, their overall performance in terms of security and key-setup speed has not been sufficiently addressed. In this paper, we propose a 128-bit block cipher based on a novel SPN structure, which uses both S-box and P-boxes that are all key-dependent. With these two key-dependent transformations, the internal structure of this cipher algorithm is hided from the cryptanalyst, so as to resist the linear and differential cryptanalysis in a few round encryptions. We named this key-dependent structure the DSDP structure, and the cipher DSDP. A fast permutation algorithm is used to generate both the key-dependent S-box and key-dependent P-boxes. This greatly compensates the performance penalty of complex key schedule. The experimental results show that our algorithm has a very fast encryption/decryption speed and a reasonable fast key scheduling implementation.