So basically the idea with RSA is that all computations are done modulo N, where N is the product of two secret primes p and q.
What was done here is manipulating the high bits of N (yielding N'), and finding new prime q' slightly larger than N'/p. The high bits of N'' = p * q' are unaffected because the gap between N'/p and q' is small enough in practice.
Not sure why, but your explanation made it click for me in a way that the linked site couldn't. The primes, I suppose (punctuation, not the unfactorable numbers).
I'm going to have to read the article again, carefully -- and play some more with RSA. But I'm surprised so many... digits are shared between the secret key and the public cert. Or is that a typo in the article?
I've only done the toy mental gymnastics with RSA in base10 -- it's probably a good idea to play with in bitstrings as well...
The modulus - the part that has data embedded in it - isn't a secret part of the key. I think the part confusing you is that the modulus (N) is included in both the public and private key.
The private key contains: [p, q, N, e, d, d_p, d_q, q_inv]
The public key contains: [N, e]
If you do find a typo somewhere, please let me know (I have an email address listed in my HN profile).
pedantic: Conceptually, the public key is n, e and the private key is n, d. The other values you mention are secret, in that they can be used to derive d, but aren't the private key. OpenSSL keeps some intermediate values for performance, but they aren't strictly required for RSA to work.
If the n is public, it's not really part of the private key is it? (Or private key) Granted d is not sufficient as a key either - but n clearly isn't secret. Is there a term for that? "Commmon key", maybe? Key parameter? Keystone? ;)
If one wanted to be even more pedantic, N is the modulus, e is the public exponent and d is the private exponent. N is required for both public and private operations.
Yes. But is there a more general (or specific, depending on one's point of view) term that applies to (public key) cryptography? Eg "some random, public, non-repeated stuff" is a nonce, a key is a parameter to an encryption function etc. Ecc keys are over a certain [ed]curve - so you need parameters for that too, but modulus while entirely correct mathematically, doesn't really capture the essence of N from a cryptographic point of view. Maybe just "public parameter"?
Thank you. Yes, it was the header that confused me ("RSA SECRET KEY") - I've not played much with actual RSA - when doing the math with pen and paper it's easy to gloss over things like what's concatenated, and were/how things are stored/published.
What was done here is manipulating the high bits of N (yielding N'), and finding new prime q' slightly larger than N'/p. The high bits of N'' = p * q' are unaffected because the gap between N'/p and q' is small enough in practice.