The invention relates to a method of storing data on a rewritable data storage medium, to a corresponding storage medium, to a corresponding recording apparatus and to a corresponding playback apparatus. Copy-protective measures require that on rewritable storage media some data must be stored which shall not be modifiable or erasable by consumer end products. A practical problem is the storage of large quantities of such data in a fixed data area. Typically the capacity is limited to a few bits. Meanwhile the amount of copy protection data that needs to be stored may well exceed the storage capacity available in the read-only fixed data area. The invention therefore proposes to write the copy protection data as system data in the recordable data area (4), e.g. as part of the formatting of the medium (1). A cryptographic summary is computed and also stored in the recordable data area (32) or in the fixed data area (2) such that a cryptographic relationship between the fixed data area (2) and the system data area (3) is provided. A playback or replay apparatus will only accept a storage medium with a valid combination of copy protection data and fixed data.