On a data recording medium which is divided into sectors and can be accessed on the sector unit basis, when encoded data is divided every predetermined length, a header is added, the data is packetized, a header is further added to the packet to thereby form the pack data, and the resultant data is recorded, if the stuffing is necessary, the stuffing data is inserted to the last of a data area of the packet. Thus, a length of pack header can be fixed. There is no need to provide a padding packet. A situation such that a PES header is encrypted is prevented and no problem occurs when encryption is performed.