[Security Discussion] Master Melab:
I remember that when I used to frequent these forums a year or two ago, there were often times when people would ask why we couldn't use the signing key to get bootloaders or devices to accept arbitrary code. Presumably, the more experienced here understand digital signatures, but maybe not the specific math behind them. This is intended to be a short informational guide on how these work.

Symmetric-key cryptography

The most ubiquitous form of encryption involves keys that are the same for encryption and decryption. This has existed since cryptography first became a thing. Historically, the plebeians of a given polity were illiterate. Only a small portion of society was capable of reading and writing. This is how the Roman Catholic Church held something of a monopoly on the Bible—which was written in Latin, by the way—until printing press lead to increased literacy.

All the people who know a particular key can encrypt and decrypt messages equally. This requires tedious amounts of work to keep the key secret (ergo, "secret key cryptography"). If secret keys are ever implemented on hardware, they must be stored in such a way that attempting to probe for it would simultaneously destroy it. The first iPhone, which lacked hardware-based verification of the bootloader, encrypted the first stage bootloader. If you didn't have the correct key, any code you placed there would decrypt to gibberish (it could presumably still run because it offered no authentication or integrity protection, but the chances of this happening were unlikely). Now, with a MAC algorithm, a tag could be attached for verification purposes, but this would still require having the key burned into the mask ROM.

Asymmetric-key cryptography

Asymmetric cryptography emerged in the 1970s with the Diffie-Hellman protocol—which admittedly wasn't a cryptosystem, but a key agreement protocol—and RSA. RSA is the most widely used public key cryptosystem, but there are others, most being variants on the difficulty of integer factorization or discrete logarithms (i.e., Paillier, Rabin, ElGamal, ECC, DSA, etc.), but there are more exotic ones based on lattices (NTRUEncrypt and NTRUSign), linear codes (McEliece), polynomials (HFE and multivariate cryptography), and hashes (Lamport signatures). There is a public key and private key (sometimes the which is key is which doesn't matter). Crypographic operations with the public key are one way. You can encrypt a message using my public key, but I'm the only who can decrypt it since I generated the key pair.

RSA, the most popular, operates on the fact that with a given exponent and a modulus of secret factorization. An example:

p=41 (prime number)

q=43 (prime number)

N=p*q=1763

e=11 (public exponent)​

To calculate the private exponent, I must find the number (d) that satisfies e*d mod ((p-1)*(q-1))=1. This number is called a modular multiplicative inverse and it is easy to determine when one knows the factors or N. In this case, d=611. Let's say you want to send me m=10. The ciphertext is c=m^e mod N=10^11 mod 1763=789. To get the message, I only need to calculate swap out my public exponent for my private exponent, giving m=c^d mod N=789^611 mod 1763=10.

These operations can also go the other way, allowing me to "sign" hashes of messages.

Digital signatures

Unlike encryption, signing a message goes the other way and involves using the private key to create a number that can be verified with the public key. With RSA, you just need to do what I did above in reverse. On devices with hardware-based or software-based verifications of code, all that is needed is the public key associated with the identity that is authorized to create runnable code. In a lot of cases, it is burned into the mask ROM of an SoC, allowing no way to change the change anything without some serious molecular rearrangement. If it's in the software, then all you have to do is edit the code that performs the signature check. Seeing as most companies are not stupid, however, this often impossible because that software is verified by a previous stage, with the verification going all the way down to the hardware level.

In the case of UEFI secure boot, the UEFI firmware (which can usually be changed), has a database of public keys that it uses to verify the "first stage" bootloader (in quotes because it's really not the first stage). I don't know if the UEFI firmware is also checked by a previous mechanism, but if it is, it's done in a way that's dissimilar to how ARM-based devices do it.

Questions, comments, concerns? I'm here all day.