You probably saw this:
% openssl genrsa -out keypair.pem 512
% openssl rsa -noout -text -in keypair.pem
RSA Private-Key: (512 bit, 2 primes)
modulus:
00:fd:1a:2f:5a:b9:01:4f:85:f7:72:a4:c2:6f:58:
43:c8:6a:4c:dc:2b:3f:96:08:8e:e9:ed:4e:c2:92:
e4:3c:02:c8:2e:09:63:23:ad:45:6b:92:fa:a7:88:
3a:0c:4b:08:cf:aa:fd:b5:64:cd:28:5e:3a:6a:53:
20:7c:e9:35:d7
publicExponent: 65537 (0x10001)
privateExponent:
49:b5:ac:80:d1:4c:2e:6a:a7:6b:bd:cb:da:3d:6c:
50:1b:95:12:b1:8d:ad:16:04:f8:df:61:86:8c:dc:
e7:14:9c:0f:e0:89:d9:20:fe:9c:6d:9a:be:0c:aa:
a3:90:d1:88:7d:85:38:08:19:3d:f0:d0:3f:f0:6a:
88:8f:f8:71
prime1:
00:ff:df:13:bd:0e:17:9f:05:41:92:8a:86:53:91:
34:fc:51:f2:c2:59:a7:ec:9b:f5:37:74:95:f0:eb:
c6:17:55
prime2:
00:fd:3a:c0:67:27:b5:25:ab:72:10:a3:77:8c:b7:
d3:cd:00:db:89:e9:25:82:11:24:ec:bc:e9:a8:29:
cc:00:7b
exponent1:
00:8d:e4:30:36:fb:f4:9f:6b:b3:c4:46:eb:5c:b6:
3e:92:da:02:ec:41:f9:bc:5d:74:2b:af:8c:62:d0:
ec:c6:0d
exponent2:
00:f4:2d:24:bd:d3:42:0f:32:c4:68:5a:d7:ba:2e:
bf:e2:9b:83:15:f6:64:9e:88:9d:8c:51:95:14:fc:
48:a3:e5
coefficient:
7b:be:00:7a:51:cd:5c:b0:ac:f7:be:67:2d:0c:ce:
a1:34:cc:ab:7e:06:d4:88:cf:97:b0:b4:43:d9:96:
bd:9c
What is with all these parameters? When all crypto textbooks says that p/q/exponent are the core of RSA? Let's see.
There is another connection between CRT (Chinese Remainder Theorem) and RSA. (One more: low-exponent attack).
RSA decryption phase is: \( m = c^d \pmod {pq} \), where m=message, c=ciphertext, d=decryption exponent, pq=modulus. (For short RSA intro, you may read in my book.) So, for decryption you need to know d/p/q.
But exponentiation is slow, when d has 512 bits, or, nowadays, when 4096 is not uncommon. This is the reason why RSA is slow. Some clever math trickery can speed this process up.
In short, CRT allows to calculate this step in two parts.
Precompute for your private RSA key:
Now, at the step of decryption, when you received 'c', calculate this:
In fact, the following equations hold:
Why is this? A digression here. For example, we need to calculate \( c^d \pmod p \), but 'd' is very big, much larger than 'p', Since \( c^d \) is 'cut' by 'p', the result must be lower than 'p' and much lower than 'd'. Euler's theorem allow us save some computation power. It says that:
\[ c^d \pmod p = c^{d \pmod {\varphi(p)}} \pmod p = c^{d \pmod{p-1}} \pmod p \]Hence, to calculate \( c^d \pmod p \), just calculate \( c^{d \pmod{p-1}} \pmod p \), exponentiation to \( d \pmod{p-1} \) would be must faster than to 'd'. Now let's rewrite our system of equations, by expanding dp and dq and see that equations holds, thanks to Euler's theorem:
And since we already calculated \( c^{dp} \) and \( c^{dq} \), and we know p/q (we are at decryption side), and p and q are coprime to each other, so we can use CRT to recover the 'm' (which is modulo pq, of course).
Now the real example. PEM file, PEM file dumped, version 2. A SageMath notebook, where I use crt() built-in function to decrypt message, alongside with a more 'usual' method from textbooks.
So why using that esoteric math? For 512-bit RSA key, pq is 512-bit, p and q are 256-bit each other. Two exponentaion operations by 256 bits are much faster than one exponentiation by 512 bit number. Speed up may be as large as fourfold. Many texts about CRT says that you can process a number by processing its parts separately, thanks to CRT.
And this is why you see all these parameters in PEM files. They are precomputed for your private key. dp=exponent1, dq=exponent2. This is why when I factored RSA-512, I used an additional script that will precompute these paremeters for newly created PEM file.
So far so good, but how can be get rid of crt() function? This is a pure Python notebook, where I used Gauss algorithm for CRT, copypasted from somewhere. There is also a short algorithm I copied from SSH 1.x, which is fast and used everywhere. But cryptic, due to optimization. It uses modulo inverse of 'q', and this is why this precomputed value is also present in PEM files, named 'coefficient' or 'q_inv'.
What RFC 2437 says about it all, by the way?
dP p's exponent, a positive integer such that:
e(dP)\equiv 1 (mod(p-1))
dQ q's exponent, a positive integer such that:
e(dQ)\equiv 1 (mod(q-1))
...
qInv CRT coefficient, a positive integer less
than p such: q(qInv)\equiv 1 (mod p)
...
11.1.2 Private-key syntax
An RSA private key should be represented with ASN.1 type
RSAPrivateKey:
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER -- (inverse of q) mod p }
Version ::= INTEGER
The fields of type RSAPrivateKey have the following meanings:
-version is the version number, for compatibility with future
revisions of this document. It shall be 0 for this version of the
document.
-modulus is the modulus n.
-publicExponent is the public exponent e.
-privateExponent is the private exponent d.
-prime1 is the prime factor p of n.
-prime2 is the prime factor q of n.
-exponent1 is d mod (p-1).
-exponent2 is d mod (q-1).
-coefficient is the Chinese Remainder Theorem coefficient q-1 mod p.
Summary: a highly-popular CRT method used in RSA decryption step is cryptic, but fast and optimized. Python and SageMath Jupyter notebooks used.
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.