If the green comes off like a slime, it is the beginning of hair algae and it is not Coraline, Coraline is hard like the rocks themselves, and it won't scrape off with your fingernail. The red on the sand is Cyanobacteria. Coraline algae is desired, the other two mentioned are not.
Do a phosphate and nitrate test, the presence of these are what makes bad water quality and feeds nuisance algae. The answer is one good water change, don't overfeed, and use good RO water for your salt mix, no tap water. Ripping apart the tank to scrub the rock (in saltwater only) is not how to take care of the problem.