And if we're talking megabytes, there's no excuse not to do proper crypto. MbedTLS, for example, gives you a basic TLS stack in 64kB ROM + 64kB RAM, and a pretty splurgy one in 200kB.
Of course this can be way too much for small embedded systems, but if you can afford to run Linux and use phrases like "individual megabytes matter", you can definitely do proper crypto.
Just because it runs “full blown Linux” doesn’t mean you get more than 16MB to play with.