4 ms·
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 manipulat
by kbwt 11y ago
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.
- function_seven 11y agoNot 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). Thanks.
- e12e 11y agoI'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...
- ryan-c 11y agoThe 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).
- e12e 11y agoThank 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.
- tptacek 11y agopedantic: 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.
- ryan-c 11y agoRight, I was referring to what values are in the PEM serializations of the private and public key, since that was what e12e seemed to be confused by.
- e12e 11y agoIf 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? ;)
- ryan-c 11y agoIf 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.
- e12e 11y agoYes. 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"?
- tptacek 11y agoThe usual term here is indeed "parameter", as in "parameter validation flaw".