One thing you're missing: cryptography is secured by say, the difficulty of factoring large numbers, but cryptocurrencies are secured by no one being able to take over more than 51% of the network's processing (in proof-of-work currencies, like Bitcoin). They're kind of the same technology, but cryptocurrencies are relying on a second-order effect.
Put another way: this "hardness" isn't a fundamental computational limit, but more of an enforced limitation because other parties want to verify your computation.
Also, one hole in your idea: the actual machine you compute on wouldn't matter to an AI, so it could easily jump from say, the Ethereum VM to an AWS instance that runs the same code (several orders of magnitude faster). The AI only needs to hit the point where it can buy that AWS instance, so I think you're only providing a temporary barrier.