# How to get dp and dq of CRT-RSA?

I am learning to utilize flush+reload method to get private key of CRT-RSA.

CRT-RSA calculates two parts separately: mp = c^dp mod p and mq = c^dq mod q

x = b^e mod m is calculated by the code below.

[![enter image description here][1]][1]

There is a loophole in this method, that is, the execution of Square-Reduce-Multiply-Reduce in the code can be detected, and the exponent can be inferred.

Square-Reduce-Multiply-Reduce indicate a set bit. Sequences of Square-Reduce which are not followed by Multiply indicate a clear bit.

According to the introduction of the paper, as long as the Square-Reduce-Multiply in the encryption process is detected, the private key can also be restored.

Hence, knowing dp (and, symmetrically, dq) is sufficient for factoring n and breaking the encryption

By reading the paper and source code, I found that he always checks whether the following three cache lines are used when decrypting.

For gnupg, flush+reload detects the execution of the following three lines of code.

    probe 0x080f7607 S #mpih-mul.c:270 (First cache line in mpih_sqr_n())
probe 0x080f6c45 r #mpih-div.c:329 (Loop in default case in mpihelp_divrem())
probe 0x080f6fa8 M #mpih-mul.c:121 (First cache line of mul_n())

1. I'm confused, does the execution of the above three lines of code restore dp or dq?

2. For Gnupg, I am able to export the private key by command gpg --output mike.secret.gpg --armor --export-secret-key [email protected], but how do I figure out what dp and dq are?

I've been trying for weeks and I still can't figure it out. Can anyone help? thank you very much!!!

• The hint seems to be in the "detection" part. Detecting if specific code is executed according to input values can lead to side channel attacks. Commented Nov 4, 2022 at 13:18
• Do you know how to get dp and dq based on the RSA private key? Thanks! Commented Nov 4, 2022 at 13:21
• $d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$ Commented Nov 4, 2022 at 14:55