rsa encryption

 choose two large  prime number p (prime 1) and q (prime 2)

 

n= p x q, where n is called the modulus for encryption and decryption

 

φ =(p - 1) x (q -1) is called Euler's totient function for n=pq

For a given positive integer n, Euler's totient function ϕ(n) is defined as the number of positive integers less than or equal to n that are coprime (i.e., share no common factors) with n.

$$$$ϕ(n)=n∏p∣n(1−1p)$$$$$$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

 $p\mid n$ means that $p$ divides $\mathrm{n\; ,\; and\; is\; a\; prime\; factor\; greater\; than\; 1 }$

$\mathrm{i }$$n$

 

 example , n=2*3=6 with factors f=1,2,3,4,5,6 factors

$\mathrm{Two\; numbers\; are\; coprime\; if\; their\; greatest\; common\; divisor\; (GCD)\; is\; 1}$

$\mathrm{here\; find\; gcd(f,n)=1 \; <br>}$

only 1 and 5 are coprime with 6 

φ=1*2 =2

 

choose e less  than φ , such that  e is co prime with φ , ie  e has no common factor with φ except 1

mathematically : gcd (e,φ) =1 and 1<e<φ 

first one is condition for existence of modulo inverse 

public key is <e, n>

plaintext message is m

ciphertext C

C = m^e mod n

m must be less than n. A larger message (>n) is treated as a concatenation of messages, each of which is encrypted separately.

  

Compute the private exponent D such that D×e ≡ 1 (mod ϕ)

its fancy way of saying   $\mathrm{<b>D</b>}$e/ϕ with  remainder  1.

 

notation 

$a\equiv c\; (\mathrm{mod}b)$

This is the congruence notation. It means that $a$ and $c$ have the same remainder when divided by $b$, i.e., they are congruent modulo $b$.

Extended Euclidean algorithm

a×x+b×y=gcd(a,b)

a,b are number whose gcd you want to find

x and y are called Bezout coefficients

gcd is expressed as linear combination of x and y 

 

euclidean algorithm

$\text{gcd}(a,b)=\text{gcd}(b,a\mathrm{mod}b)$

Repeat until the remainder is 0.

 

Apply the Euclidean algorithm as usual to find the gcd.

As we compute the remainders, we also track how to express each remainder as a linear combination of $a$ and $b$ .

When we reach the gcd (which is 1 if the numbers are coprime), the coefficients $x$ and $y$ represent the solution to the equation $a \times x + b \times y = \text{gcd}(a, b)$

 

i.e  De=kϕ+1

This means D is the modular  multiplicative inverse of e modulo ϕ(n)

 private key <D,n>

C = m^e mod n

m = C^d mod n

 

 

 

 

 openssl genpkey -algorithm RSA -out private_key.pem -pkeyopt rsa_keygen_bits:4096

cat private_key.pem
-----BEGIN PRIVATE KEY-----
MIIJQgIBADANBgkqhkiG9w0BAQEFAASCCSwwggkoAgEAAoICAQDkxD4DiyvePgGt
O8hNwfxRr6FOBlYVpq/WmLRbNcq0rRyN+rPkENnXAgtPJ3ny7NcF9O/mwojW2Ocr
VTQGe6DZGR/zABU9NobW8/7FAGtwEFuGWiG9C+it+gcTR8HYJMcA+yQqSWQr0yEW
Z934qrVgI+S/QOveNL/T3oxhz6CyJv0w2zqzcp8ANbxvppNzBfFMJMW1OlYsGKJR
ofvLuJE9rfxagcR/+Xb8PcuPgnVgCiqgvRU87iv20cXr07XRfH90MRAX1noeVezm
8qQL7KhzSLlYgzlbo8VyLEGI1gDyumApRWscV/0FzaZEyz6q/wC9BY6Zwq2vy5GD
uwy50ZbeYmi+O+Pc0CIx76Nd9OFOeNXdeFncR/xqEL7E61RiSBS038Oggu+7kKCx
K32F9YM3hbPm9j5fnenZw2NlS+5r9iNtkVQi1nmJqhmkgb2JPvlHV0TjIRjJlcoN
W6asXsqjnnVS+8gmceuyV5BhzouVK1gcfWxF6iKrXZPXOc3tzTie+caoTRBunPEI
Y+VaJktH8rfO2XHOmujE5B1Edg3ZC/JMKSoQk6L2eTkhf94L6B+uXr84toM8Bnfl
h4/ko1u3ULQ+vr2ZM4sOYt7ADtEzaSAUA9j2moyMSzoe0esMWo8icRbrhppEVYUh
wkWU1K54IowfFTo/nWHP1QumDhxMqQIDAQABAoICACmovPxLN0Fg/FAuL1NNrKO5
fn/lcn693I6RP2LOwGu3jJgkW+b/1JOtaR7QewosbBnHGXrl2SJ63FoNSYyWrdtr
EmDfln6Ps+1oAHCim24MZIZqWnOBPC2WdvxhWGECjYTVtyfGNqouZ/ubDZaPi7kG
wEy9x1YvN/GeuOTE+SgIJppjieSMznyszHRumrJbFi5+EcznYzLjh4ejHmXiZfyb
9vUKZZzCcpMLs8qeAL7tCwc7d6chXjszxz2jT5xm9hTULHCS26kzj5EdBZewUJqx
1yLRvru77qRUf9ip1AFfxEwvuoouUcLhSNKFSpO8HUfOv8GrbJKzWPvqr64VB0p+
4P7R3NGRDF5idiBntsKH/pPdHSXQWKlFpxTOhFZItv56PLne5S8AZhyonwuc3Teb
ddtCYm41w9QOJUL9h+3tjTF+grNQfTYz5FBb5jKGbaQoLZImJQ9Wfsj/gEqDd1j1
7dMJx13zky/CbM6SD/rbhCY1TmOei3SGjOsoZ6hzKG+9jnZSqBC2luoR56XSSeF0
jjvIy1uZN91LvHlFNNxdsV6x5V6DdiSsWSldDeU++R6g4KWLp9CwLPFQy7bBvbjo
4z8FKfjbOXvolff7Cct1042EwRj4muVsEy+JycJu1VBx33s1J/xaLkK6CTeDd31F
da6mcIodlXgSdX0ZRcYDAoIBAQD7Jx0MuYDjl/Oqc5yRzSNEHSgJixTpWgEwrgge
A2gtgqxpiQfDshzoUDvETiE1evy268UPaeafPJX4LyLDLfol2uy7zckFPgjjYlOv
34+kpAh5uc6Po3Wvya65Ot3LvXMBJ1EqSjgV8wVgEv84pIpy5DFlupst78Pxh6P2
R4gb7P8z4Cu1wKiAmv4hnDlTplpKVEZhXKalhw0ehsKglMLiHEqQbDRcY0eju4jZ
NDpEW971+3jd1tAORwlHZp1jKx6Trf5CvA9ZtkLvEZIg3oW98CrdbWFjCRoy+szE
tVtOZJNG91rY0tZIgHkAvE4o+9zDN2NACExamkcXpSsSLub3AoIBAQDpLoYVre0+
IMihDDcGR96nmM3kl3sti7DuYv1w1GsttX9IDXD0M1uiRghP3TkDwTf+cgPYL50J
vpGFGO3c9QJ8gYn3s63o3Aipk0jK8rgcrwDFM/EVpxqSLmnC1lRSroqgDhMopaGA
8C9RjEWToK+sn2z5zP8Rol6cdmLVd4OF988Mx2WauYF6DNvKXMhc2E6+ZJOtIx9j
L+ugROYfFof07GcjIKxqzS1/tAWtykGXnbkJWOgR9bifbR1hNHlsmnZBJRl9Tc4U
mRspHR+qMN+4fHL73vA6A+lhkAO52Na2ZDZFHsfNrq/INqw+/X5MZLchXJqKBJ/T
qhnPgM8/F2FfAoIBAHbEuGgcEWePpBsnMROB/vtnDlf0/Z6cgZOTuSL4WXusH/yI
YLOatzDlQF5E1E+GKZwXQslXO0hyTjlfkQDb7T+Zl/n4BugDvhBJn2m8PyGMsLVf
uN8UXcMTjRzrSZffr1MMVMW682rt0cztLuSKay6J2xJQfLHsgKzniBIfIa6TFNxj
VkhNI2It6Z/bUQDN2kTsNZw1RFli1EFrWP63WrGyz1Ac22YVTPuQ49ZTbHqHN5j7
otzFiP43eZvaWvNaoMsVrPfCF0BFgMGtfX0tvfFkceDkqPk8hLc3Az7CxLr9tOgK
cVu32L3Qg2hlpFCdSnjG6JiPVAxEiPoVkZi3tWECggEBALDUciRQoD/kFqFipPuj
Vusbys+WPHgeng85jF6bB6hDIgHfB5B4vf3CRB1kcw8w4KiZh+bSvLEeDjaz3/YW
60rF5X2tia2z5vHJ2oLlK8+8usXRjPrRnSnL/rIdXRbSfBfCdK73ZBFmk0uxJzY7
vd0XjUmmNqwFyN+4O10MY/YdJavYLmn2UYTf6XF9iQg3lQd3ODItF2lddr80YJqk
uHd5KwGNjpLzg5R7TW8smS9EEYVQIbU09UwZMBV9+LLuM81VOA45CZW/QcSc7F1g
8NdzsLLmrqAgRUSSNPEjyjfIqQsju3t0BKO9KkQecj+2hNXM5vjRZu7Z6PbeBMwg
i9sCggEAAqawR26qVZON8ext7j6/xQMVjYqurGNXrBuqMpavvSW+UIuqU3l3glN2
suhf8KlDGJugVggFOx6BpcxYQ3DFvpwVexJtUlwsJaEwiCTBcOmw8ouXyysp61lo
dSIvEkeQCZhgBszhERBbr63hKlTkhIhtMb5a5bSOTPiXNX1QQhY1HLXMWkO8acpR
9JEWjnylR17cU7o2f7GGQaxI1RJuEbwT7KzoOUHSFR9XZ4QU/ysoOqHccLc33159
tNByLzlQ66sNeML5KBOyJH59Uxh4yIBGtmJDK8D6BCZvjV6e7vK12E/GMzxdSDwr
SakeLymHKhiDGMfGii1SFAEgZVYf9Q==
-----END PRIVATE KEY-----

 openssl rsa -in private_key.pem -text -noout

Private-Key: (4096 bit, 2 primes)
modulus:
    00:e4:c4:3e:03:8b:2b:de:3e:01:ad:3b:c8:4d:c1:
    fc:51:af:a1:4e:06:56:15:a6:af:d6:98:b4:5b:35:
    ca:b4:ad:1c:8d:fa:b3:e4:10:d9:d7:02:0b:4f:27:
    79:f2:ec:d7:05:f4:ef:e6:c2:88:d6:d8:e7:2b:55:
    34:06:7b:a0:d9:19:1f:f3:00:15:3d:36:86:d6:f3:
    fe:c5:00:6b:70:10:5b:86:5a:21:bd:0b:e8:ad:fa:
    07:13:47:c1:d8:24:c7:00:fb:24:2a:49:64:2b:d3:
    21:16:67:dd:f8:aa:b5:60:23:e4:bf:40:eb:de:34:
    bf:d3:de:8c:61:cf:a0:b2:26:fd:30:db:3a:b3:72:
    9f:00:35:bc:6f:a6:93:73:05:f1:4c:24:c5:b5:3a:
    56:2c:18:a2:51:a1:fb:cb:b8:91:3d:ad:fc:5a:81:
    c4:7f:f9:76:fc:3d:cb:8f:82:75:60:0a:2a:a0:bd:
    15:3c:ee:2b:f6:d1:c5:eb:d3:b5:d1:7c:7f:74:31:
    10:17:d6:7a:1e:55:ec:e6:f2:a4:0b:ec:a8:73:48:
    b9:58:83:39:5b:a3:c5:72:2c:41:88:d6:00:f2:ba:
    60:29:45:6b:1c:57:fd:05:cd:a6:44:cb:3e:aa:ff:
    00:bd:05:8e:99:c2:ad:af:cb:91:83:bb:0c:b9:d1:
    96:de:62:68:be:3b:e3:dc:d0:22:31:ef:a3:5d:f4:
    e1:4e:78:d5:dd:78:59:dc:47:fc:6a:10:be:c4:eb:
    54:62:48:14:b4:df:c3:a0:82:ef:bb:90:a0:b1:2b:
    7d:85:f5:83:37:85:b3:e6:f6:3e:5f:9d:e9:d9:c3:
    63:65:4b:ee:6b:f6:23:6d:91:54:22:d6:79:89:aa:
    19:a4:81:bd:89:3e:f9:47:57:44:e3:21:18:c9:95:
    ca:0d:5b:a6:ac:5e:ca:a3:9e:75:52:fb:c8:26:71:
    eb:b2:57:90:61:ce:8b:95:2b:58:1c:7d:6c:45:ea:
    22:ab:5d:93:d7:39:cd:ed:cd:38:9e:f9:c6:a8:4d:
    10:6e:9c:f1:08:63:e5:5a:26:4b:47:f2:b7:ce:d9:
    71:ce:9a:e8:c4:e4:1d:44:76:0d:d9:0b:f2:4c:29:
    2a:10:93:a2:f6:79:39:21:7f:de:0b:e8:1f:ae:5e:
    bf:38:b6:83:3c:06:77:e5:87:8f:e4:a3:5b:b7:50:
    b4:3e:be:bd:99:33:8b:0e:62:de:c0:0e:d1:33:69:
    20:14:03:d8:f6:9a:8c:8c:4b:3a:1e:d1:eb:0c:5a:
    8f:22:71:16:eb:86:9a:44:55:85:21:c2:45:94:d4:
    ae:78:22:8c:1f:15:3a:3f:9d:61:cf:d5:0b:a6:0e:
    1c:4c:a9
publicExponent: 65537 (0x10001)
privateExponent:
    29:a8:bc:fc:4b:37:41:60:fc:50:2e:2f:53:4d:ac:
    a3:b9:7e:7f:e5:72:7e:bd:dc:8e:91:3f:62:ce:c0:
    6b:b7:8c:98:24:5b:e6:ff:d4:93:ad:69:1e:d0:7b:
    0a:2c:6c:19:c7:19:7a:e5:d9:22:7a:dc:5a:0d:49:
    8c:96:ad:db:6b:12:60:df:96:7e:8f:b3:ed:68:00:
    70:a2:9b:6e:0c:64:86:6a:5a:73:81:3c:2d:96:76:
    fc:61:58:61:02:8d:84:d5:b7:27:c6:36:aa:2e:67:
    fb:9b:0d:96:8f:8b:b9:06:c0:4c:bd:c7:56:2f:37:
    f1:9e:b8:e4:c4:f9:28:08:26:9a:63:89:e4:8c:ce:
    7c:ac:cc:74:6e:9a:b2:5b:16:2e:7e:11:cc:e7:63:
    32:e3:87:87:a3:1e:65:e2:65:fc:9b:f6:f5:0a:65:
    9c:c2:72:93:0b:b3:ca:9e:00:be:ed:0b:07:3b:77:
    a7:21:5e:3b:33:c7:3d:a3:4f:9c:66:f6:14:d4:2c:
    70:92:db:a9:33:8f:91:1d:05:97:b0:50:9a:b1:d7:
    22:d1:be:bb:bb:ee:a4:54:7f:d8:a9:d4:01:5f:c4:
    4c:2f:ba:8a:2e:51:c2:e1:48:d2:85:4a:93:bc:1d:
    47:ce:bf:c1:ab:6c:92:b3:58:fb:ea:af:ae:15:07:
    4a:7e:e0:fe:d1:dc:d1:91:0c:5e:62:76:20:67:b6:
    c2:87:fe:93:dd:1d:25:d0:58:a9:45:a7:14:ce:84:
    56:48:b6:fe:7a:3c:b9:de:e5:2f:00:66:1c:a8:9f:
    0b:9c:dd:37:9b:75:db:42:62:6e:35:c3:d4:0e:25:
    42:fd:87:ed:ed:8d:31:7e:82:b3:50:7d:36:33:e4:
    50:5b:e6:32:86:6d:a4:28:2d:92:26:25:0f:56:7e:
    c8:ff:80:4a:83:77:58:f5:ed:d3:09:c7:5d:f3:93:
    2f:c2:6c:ce:92:0f:fa:db:84:26:35:4e:63:9e:8b:
    74:86:8c:eb:28:67:a8:73:28:6f:bd:8e:76:52:a8:
    10:b6:96:ea:11:e7:a5:d2:49:e1:74:8e:3b:c8:cb:
    5b:99:37:dd:4b:bc:79:45:34:dc:5d:b1:5e:b1:e5:
    5e:83:76:24:ac:59:29:5d:0d:e5:3e:f9:1e:a0:e0:
    a5:8b:a7:d0:b0:2c:f1:50:cb:b6:c1:bd:b8:e8:e3:
    3f:05:29:f8:db:39:7b:e8:95:f7:fb:09:cb:75:d3:
    8d:84:c1:18:f8:9a:e5:6c:13:2f:89:c9:c2:6e:d5:
    50:71:df:7b:35:27:fc:5a:2e:42:ba:09:37:83:77:
    7d:45:75:ae:a6:70:8a:1d:95:78:12:75:7d:19:45:
    c6:03
prime1:
    00:fb:27:1d:0c:b9:80:e3:97:f3:aa:73:9c:91:cd:
    23:44:1d:28:09:8b:14:e9:5a:01:30:ae:08:1e:03:
    68:2d:82:ac:69:89:07:c3:b2:1c:e8:50:3b:c4:4e:
    21:35:7a:fc:b6:eb:c5:0f:69:e6:9f:3c:95:f8:2f:
    22:c3:2d:fa:25:da:ec:bb:cd:c9:05:3e:08:e3:62:
    53:af:df:8f:a4:a4:08:79:b9:ce:8f:a3:75:af:c9:
    ae:b9:3a:dd:cb:bd:73:01:27:51:2a:4a:38:15:f3:
    05:60:12:ff:38:a4:8a:72:e4:31:65:ba:9b:2d:ef:
    c3:f1:87:a3:f6:47:88:1b:ec:ff:33:e0:2b:b5:c0:
    a8:80:9a:fe:21:9c:39:53:a6:5a:4a:54:46:61:5c:
    a6:a5:87:0d:1e:86:c2:a0:94:c2:e2:1c:4a:90:6c:
    34:5c:63:47:a3:bb:88:d9:34:3a:44:5b:de:f5:fb:
    78:dd:d6:d0:0e:47:09:47:66:9d:63:2b:1e:93:ad:
    fe:42:bc:0f:59:b6:42:ef:11:92:20:de:85:bd:f0:
    2a:dd:6d:61:63:09:1a:32:fa:cc:c4:b5:5b:4e:64:
    93:46:f7:5a:d8:d2:d6:48:80:79:00:bc:4e:28:fb:
    dc:c3:37:63:40:08:4c:5a:9a:47:17:a5:2b:12:2e:
    e6:f7
prime2:
    00:e9:2e:86:15:ad:ed:3e:20:c8:a1:0c:37:06:47:
    de:a7:98:cd:e4:97:7b:2d:8b:b0:ee:62:fd:70:d4:
    6b:2d:b5:7f:48:0d:70:f4:33:5b:a2:46:08:4f:dd:
    39:03:c1:37:fe:72:03:d8:2f:9d:09:be:91:85:18:
    ed:dc:f5:02:7c:81:89:f7:b3:ad:e8:dc:08:a9:93:
    48:ca:f2:b8:1c:af:00:c5:33:f1:15:a7:1a:92:2e:
    69:c2:d6:54:52:ae:8a:a0:0e:13:28:a5:a1:80:f0:
    2f:51:8c:45:93:a0:af:ac:9f:6c:f9:cc:ff:11:a2:
    5e:9c:76:62:d5:77:83:85:f7:cf:0c:c7:65:9a:b9:
    81:7a:0c:db:ca:5c:c8:5c:d8:4e:be:64:93:ad:23:
    1f:63:2f:eb:a0:44:e6:1f:16:87:f4:ec:67:23:20:
    ac:6a:cd:2d:7f:b4:05:ad:ca:41:97:9d:b9:09:58:
    e8:11:f5:b8:9f:6d:1d:61:34:79:6c:9a:76:41:25:
    19:7d:4d:ce:14:99:1b:29:1d:1f:aa:30:df:b8:7c:
    72:fb:de:f0:3a:03:e9:61:90:03:b9:d8:d6:b6:64:
    36:45:1e:c7:cd:ae:af:c8:36:ac:3e:fd:7e:4c:64:
    b7:21:5c:9a:8a:04:9f:d3:aa:19:cf:80:cf:3f:17:
    61:5f
exponent1:
    76:c4:b8:68:1c:11:67:8f:a4:1b:27:31:13:81:fe:
    fb:67:0e:57:f4:fd:9e:9c:81:93:93:b9:22:f8:59:
    7b:ac:1f:fc:88:60:b3:9a:b7:30:e5:40:5e:44:d4:
    4f:86:29:9c:17:42:c9:57:3b:48:72:4e:39:5f:91:
    00:db:ed:3f:99:97:f9:f8:06:e8:03:be:10:49:9f:
    69:bc:3f:21:8c:b0:b5:5f:b8:df:14:5d:c3:13:8d:
    1c:eb:49:97:df:af:53:0c:54:c5:ba:f3:6a:ed:d1:
    cc:ed:2e:e4:8a:6b:2e:89:db:12:50:7c:b1:ec:80:
    ac:e7:88:12:1f:21:ae:93:14:dc:63:56:48:4d:23:
    62:2d:e9:9f:db:51:00:cd:da:44:ec:35:9c:35:44:
    59:62:d4:41:6b:58:fe:b7:5a:b1:b2:cf:50:1c:db:
    66:15:4c:fb:90:e3:d6:53:6c:7a:87:37:98:fb:a2:
    dc:c5:88:fe:37:79:9b:da:5a:f3:5a:a0:cb:15:ac:
    f7:c2:17:40:45:80:c1:ad:7d:7d:2d:bd:f1:64:71:
    e0:e4:a8:f9:3c:84:b7:37:03:3e:c2:c4:ba:fd:b4:
    e8:0a:71:5b:b7:d8:bd:d0:83:68:65:a4:50:9d:4a:
    78:c6:e8:98:8f:54:0c:44:88:fa:15:91:98:b7:b5:
    61
exponent2:
    00:b0:d4:72:24:50:a0:3f:e4:16:a1:62:a4:fb:a3:
    56:eb:1b:ca:cf:96:3c:78:1e:9e:0f:39:8c:5e:9b:
    07:a8:43:22:01:df:07:90:78:bd:fd:c2:44:1d:64:
    73:0f:30:e0:a8:99:87:e6:d2:bc:b1:1e:0e:36:b3:
    df:f6:16:eb:4a:c5:e5:7d:ad:89:ad:b3:e6:f1:c9:
    da:82:e5:2b:cf:bc:ba:c5:d1:8c:fa:d1:9d:29:cb:
    fe:b2:1d:5d:16:d2:7c:17:c2:74:ae:f7:64:11:66:
    93:4b:b1:27:36:3b:bd:dd:17:8d:49:a6:36:ac:05:
    c8:df:b8:3b:5d:0c:63:f6:1d:25:ab:d8:2e:69:f6:
    51:84:df:e9:71:7d:89:08:37:95:07:77:38:32:2d:
    17:69:5d:76:bf:34:60:9a:a4:b8:77:79:2b:01:8d:
    8e:92:f3:83:94:7b:4d:6f:2c:99:2f:44:11:85:50:
    21:b5:34:f5:4c:19:30:15:7d:f8:b2:ee:33:cd:55:
    38:0e:39:09:95:bf:41:c4:9c:ec:5d:60:f0:d7:73:
    b0:b2:e6:ae:a0:20:45:44:92:34:f1:23:ca:37:c8:
    a9:0b:23:bb:7b:74:04:a3:bd:2a:44:1e:72:3f:b6:
    84:d5:cc:e6:f8:d1:66:ee:d9:e8:f6:de:04:cc:20:
    8b:db
coefficient:
    02:a6:b0:47:6e:aa:55:93:8d:f1:ec:6d:ee:3e:bf:
    c5:03:15:8d:8a:ae:ac:63:57:ac:1b:aa:32:96:af:
    bd:25:be:50:8b:aa:53:79:77:82:53:76:b2:e8:5f:
    f0:a9:43:18:9b:a0:56:08:05:3b:1e:81:a5:cc:58:
    43:70:c5:be:9c:15:7b:12:6d:52:5c:2c:25:a1:30:
    88:24:c1:70:e9:b0:f2:8b:97:cb:2b:29:eb:59:68:
    75:22:2f:12:47:90:09:98:60:06:cc:e1:11:10:5b:
    af:ad:e1:2a:54:e4:84:88:6d:31:be:5a:e5:b4:8e:
    4c:f8:97:35:7d:50:42:16:35:1c:b5:cc:5a:43:bc:
    69:ca:51:f4:91:16:8e:7c:a5:47:5e:dc:53:ba:36:
    7f:b1:86:41:ac:48:d5:12:6e:11:bc:13:ec:ac:e8:
    39:41:d2:15:1f:57:67:84:14:ff:2b:28:3a:a1:dc:
    70:b7:37:df:5e:7d:b4:d0:72:2f:39:50:eb:ab:0d:
    78:c2:f9:28:13:b2:24:7e:7d:53:18:78:c8:80:46:
    b6:62:43:2b:c0:fa:04:26:6f:8d:5e:9e:ee:f2:b5:
    d8:4f:c6:33:3c:5d:48:3c:2b:49:a9:1e:2f:29:87:
    2a:18:83:18:c7:c6:8a:2d:52:14:01:20:65:56:1f:
    f5

 

 

optimization

Chinese Remainder Theorem (CRT)

 

Exponent 1 is often referred to as dP. It is the private exponent modulo (p - 1).

dP=d mod (p−1) 

used for the decryption calculation modulo p, which is faster than directly using the full modulus n.

dQ=d mod (q−1) 

It is used for the decryption calculation modulo q.

 

coefficient is often referred to as qInv. It is the modular inverse of q modulo p.

qInv=q−1 modp

  This is used to combine the results of the two separate decryption calculations modulo p and q. It helps in reconstructing the final decrypted message after the separate calculations modulo p and q.