A method of providing an encrypted data stream, includes obtaining a first data stream, partitioned into sections corresponding to key periods, each of a plurality of the key periods being associated with a respective value of a key, wherein each section corresponding to a key period associated with a value of the key includes at least one encrypted data unit decryptable using that associated key value, obtaining a sequence of key messages, at least some of which carry key information for obtaining at least one of the key values, obtaining a replacement data stream section, forming an encrypted output data stream, corresponding at least partially to the first data stream, by inserting the replacement data stream section so as to replace a corresponding part of the first data stream with a tail end of the replacement data stream section preceding at least part of a section of the first stream corresponding to a certain key period, and providing as output the encrypted output data stream in synchrony with an associated stream of key messages. A key message carrying key information for obtaining the key value associated with the certain key period is included in the stream of key messages so as to coincide with a point of the encrypted output data stream preceding the tail end of the replacement data stream section.