This paper proposes a novel image encryption and decryption scheme, called Square Block Division-Fibonacci (SBD-Fibonacci), which dynamically partitions any input image into optimally sized square blocks to enable efficient encryption without resizing or distortion. The proposed encryption scheme can dynamically adapt to the image dimensions and ensure compatibility with images of varying and high resolutions, while it serves as a yardstick for any symmetric-key image encryption algorithm. An optimization model, combined with the Lagrange Four-Square theorem, minimizes trivial block sizes, strengthening the encryption structure. Encryption keys are generated using the direct sum of generalized Fibonacci matrices, ensuring key matrix invertibility and strong diffusion properties and security levels. Experimental results on widely-used benchmark images and a comparative analysis against State-of-the-Art encryption algorithms demonstrate that SBD-Fibonacci achieves high entropy, strong resistance to differential and statistical attacks, and efficient runtime performance—even for large images.