Also if you root your phone (not illegal for some devices) you can install any app from the store and the apk is just there… on your device, which you can then patch.
Yes that’s completely legal. It’s just illegal to download it from somewhere else. You don’t even need root to get the APK.