The major importance of medical imaging in modern healthcare systems requires the preservation of their integrity and authenticity properties as they have become increasingly vulnerable to manipulation and tampering, raising significant concerns regarding patient safety, diagnostic accuracy, and ethical standards. In this work, we propose a watermarking scheme for the preservation of authenticity of medical images utilizing a code-based frequency domain watermarking approach that is optimized in order to preserve the quality and the fidelity of the medical image considering the imperceptibility of the hidden information once watermarked, while it also exhibits high robustness regarding the extraction of the embedded information after an attack. The proposed method utilizes the 2D representation of a Self-inverting Permutation that corresponds to an integer in order to embed in the frequency domain of particular areas of a medical image multiple integers in terms of a code sequence that ensures the authenticity of the medical image while any mismatches during the extraction process indicate that the digital object under consideration is non-authentic, or it has been undergone modification. We conduct a series of evaluation experiments to attest the robustness of the proposed watermarking scheme against a wide attack vector considering various parameters over each category of attacks and attack types. The achieved experimental results are promising and attest the potentials of the proposed technique considering the preservation of high fidelity value on the watermarked medical images as well as high robustness considering the protection of authenticity of medical images against malicious attacks.