Both numbers have to be prime, both numbers have to be the length specified(128bits in this example) they must also both be related, and they both _should_ be random. There are quite a few algorithms for testing whether a number is prime or not, that don't require you to literally try every single number that is less than 1 of the number you're checking. If you can find the public key, which has to be known on the 3ds it has to be stored there or else it'd not be able to verify anything. if it's in hardware the decapping would probably reveal where it is hidden and help people know where to look for the thing. I seriously doubt nintendo paid for hardware that checks against tampering and then kills itself if someone tries to find the thing, and does all of the crypto in the black box, as this is a console and is meant to be very very cost effective and those boxes are unbelieveably expensive and are only really seen/used by CAs(people who make SSL certs).
Now then it could and likely is using lots of different keys, still though the public key is exposed with each signature so you can verify it, if nintendo made it so that the key's in hardware IE it cannot be updated, then they wouldn't have to include it in the signature, but it's much more likely it's stored on some eeprom that can be overwritten with a new key if peopel figure it out(like the ps3). So if we decap it, someone gets literal hardware access to the thing, sees how everything works/looks it's end of it all. If they're including the public key with each signature(not much security loss with doing this) then you'd just have to find the thing and bam you're done. They're also likely if they've got the ability to add new keys going to be transmitting it in the firmware. Now then I seriously doubt they're going to be a sony thing again, sony did their own thing and failed hard. Nintendo has RSA doing it, the company that literally made this thing. So they're likely using everythign as it should be. I'd even guess that they have a hardware chip to do the AES, Sha1/256/512, and the RSA verifications.
Edit: and to just reiterate the keys have to be there, even if they're hiding them. Using oracle attacks against them, you'll eventually learn what the key is. We already have dumps of roms, so you have the signature there. You know what you're trying for. Now you just need the public key to verify. It has to be on the system, it has to be in there. And also like the ps3, they can't just revoke the old key, once it's factored that's it. They can force _new_ games to use the new key, but people will resign the old games to make them work with the older software. This is assuming they've went full out on this thing.
Edit 2: Btw that's AES, you don't need AES to run signed code. That's symmetric encryption, that's to _decrypt_ games and such. But to make your homebrew looke legit, you will be using the RSA keypair. So whilst that's interesting that they've chosen so many different ways to encrypting/decrypting, the key still has to be stored in the games to decrypt them. If they're stored encrypted, then the 3ds might have its own private key to decrypt the roms, and nintendo encrypts them with a public key for each region. Doing this would cause more headaches/work as you'd need to factor more stuff. But still if you've got the hardware schematics before you, you'll find a flaw in the system.
This stuff wasn't written by perfect gods, it was written by men. Even RSA can get hacked, evne they can screw up, no one's perfect. There are flaws, there is holes in there, it's just with each generation they get harder and harder to find.
but will decapping help that somehow?
