Additional information is embedded into elements that form digital data by adding or subtracting a value to or from the elements. An element is detected which has a value that exceeds a range that the element can assume after the addition or subtraction is performed, and actual embedding information is generated by combining the additional information and the information detected in the detection step. The actual embedding information generated in the generation step is embedded into the elements, which fall with the range an element can assume, as a digital watermark, while excluding the element that exceeds the range the element can assume after the addition or subtraction is performed.