Gaspare FERRARO
CyberSecNatLab
Matteo ROSSI
Politecnico di Torino
RSA
1 [Link]
License & Disclaimer
2
License Information Disclaimer
This presentation is licensed under the ➢ We disclaim any warranties or representations
Creative Commons BY-NC License as to the accuracy or completeness of this
material.
➢ Materials are provided “as is” without
warranty of any kind, either express or
implied, including without limitation,
warranties of merchantability, fitness for a
particular purpose, and non-infringement.
➢ Under no circumstances shall we be liable for
To view a copy of the license, visit: any loss, damage, liability or expense incurred
[Link] or suffered which is claimed to have resulted
from use of this material.
© CINI – 2021 Rel. 07.02.2021
Goal
3
➢ Give the definition of public-key encryption
➢ Present the RSA public-key cryptosystem
➢ Show how to choose the parameters
© CINI – 2021 Rel. 07.02.2021
Prerequisites
4
➢ Lectures:
➢ CR_0.1 - Number Theory and modular arithmetic
➢ CR_1.1 – Introduction to cryptography and classical ciphers
➢ CR_2.1 – Key Exchange & DH
© CINI – 2021 Rel. 07.02.2021
Outline
5
➢ Introduction to public-key cryptography
➢ RSA textbook scheme
➢ RSA-CRT
➢ Choose parameters
© CINI – 2021 Rel. 07.02.2021
Outline
6
➢ Introduction to public-key cryptography
➢ RSA textbook scheme
➢ RSA-CRT
➢ Choose parameters
© CINI – 2021 Rel. 07.02.2021
Recall: Cryptography
7
➢ Two main methods:
➢ Symmetric key - Single key
➢ Public key - Double key
© CINI – 2021 Rel. 07.02.2021
Recall: Cryptography
8
➢ Two main methods:
➢ Symmetric key - Single key
➢ Public key - Double key
Seen in:
• CR_1.2 – XOR cipher
• CR_1.3 – Block ciphers
• CR_1.4 – Stream ciphers
© CINI – 2021 Rel. 07.02.2021
Recall: Symmetric key cryptography
9
➢ Requires that both sender and recipient know the
same key
➢ An issue is how they do share it without meeting
𝑘𝑒𝑦
𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 𝑒𝑛𝑐𝑟𝑦𝑝𝑡𝑖𝑜𝑛 𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 𝑑𝑒𝑐𝑟𝑦𝑝𝑡𝑖𝑜𝑛 𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡
© CINI – 2021 Rel. 07.02.2021
Recall: Symmetric key cryptography
10
➢ Requires that both sender and recipient know the
same key
➢ An issue is how they do share it without meeting
𝑘𝑒𝑦
Seen in:
𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡 𝑒𝑛𝑐𝑟𝑦𝑝𝑡𝑖𝑜𝑛 • CR_2.1𝑑𝑒𝑐𝑟𝑦𝑝𝑡𝑖𝑜𝑛
𝑐𝑖𝑝ℎ𝑒𝑟𝑡𝑒𝑥𝑡 - Key Exchange𝑝𝑙𝑎𝑖𝑛𝑡𝑒𝑥𝑡
& DH
© CINI – 2021 Rel. 07.02.2021
Recall: public-key Encryption
11
➢ Require the use of two keys:
➢ a public key, which can be known by anyone and can be used to
encrypt messages and verify signatures
➢ a corresponding private key, known only to the recipient, used
to decrypt messages and to sign them
➢ Rely an asymmetric exchange: whoever encodes messages
or verifies signatures cannot decode messages or create
signatures
➢ Also called {double key, asymmetric} encryption
© CINI – 2021 Rel. 07.02.2021
Asymmetric Encryption
12
➢ Developed to address two important issues:
➢ key distribution: ensuring secure communications with a personal
key without depending on a key distribution center and without
trusting the behavior of others
➢ digital signatures: verify that a message comes intact from the
declared sender
➢ Complements rather than replaces symmetric encryption
➢ Is based on properties guaranteed by number theory rather
than on the use of permutations and substitutions
© CINI – 2021 Rel. 07.02.2021
Asymmetric vs symmetric encryption
13
➢ Symmetric encryption: same algorithm used to encrypt and decrypt with
the secret same key. Key and algorithm are shared by sender and receiver
➢ Almost impossible to decrypt a message if only the algorithm and the cipher text are
known
➢ Asymmetric encryption: same algorithm used to encrypt and decrypt, but
two keys are used: one to encrypt, the other to decrypt. Sender and
receiver must each have a key that pairs with the other (not the same)
➢ Almost impossible to decrypt a message if only the algorithm, the cipher text, and
one of the keys are known
© CINI – 2021 Rel. 07.02.2021
Principles of asymmetric cryptography
14
➢ A distinction is made between the keys of the subjects:
➢ public key: publicly disclosed by the subject
➢ private key: kept secret by the subject
➢ It must be computationally difficult to derive the decryption key
knowing the algorithm and the encryption key
➢ The two keys can be (complementarily) used for encryption/decryption
➢ Encryption with public key guarantees confidentiality
➢ Encryption with private key guarantees authentication
➢ With an appropriate mix we can also guarantee messages integrity
© CINI – 2021 Rel. 07.02.2021
Principles of asymmetric cryptography
15
➢ A distinction is made between the keys of the subjects:
➢ public key: publicly disclosed by the subject
➢ private key: kept secret by the subject
➢ It must be computationally difficult to derive the decryption key
knowing the algorithm and the encryption key
➢ The two keys can be (complementarily) used for encryption/decryption
➢ Encryption with public key
“trap-door guarantees
one-way confidentiality
functions”, seen in:
➢ • CR_0.1
Encryption with private key guarantees authentication
– Number theory and modular arithmetic
➢ With an appropriate mix we can also guarantee messages integrity
© CINI – 2021 Rel. 07.02.2021
Outline
16
➢ Introduction to public-key cryptography
➢ RSA textbook scheme
➢ RSA-CRT
➢ Choose parameters
© CINI – 2021 Rel. 07.02.2021
RSA
17
➢ The most famous asymmetric encryption algorithm is RSA,
from the authors Rivest, Shamir, Adleman, developed in 1977
and still used in practice today
➢ Based on exponentiation of integers modulo n. Very large integers are
used (typically 2048 bits)
➢ Encryption and decryption are single modular exponentiation
operation: exponentiation is easy (requires 𝑂((log 𝑛)3 ) operations)
➢ Security is guaranteed by the cost of factoring large numbers: factoring
is difficult (requires 𝑂 𝑒 log 𝑛 log log 𝑛 operations)
17
© CINI – 2021 Rel. 07.02.2021
RSA Key Generation
18
➢ A user generates a pair of public/private keys as follows:
➢ Randomly chooses two prime numbers: 𝑝, 𝑞
➢ Computes 𝑛 = 𝑝 × 𝑞 and 𝜙 𝑛 = 𝑝 − 1 × 𝑞 − 1 Euler’s totient
➢ Randomly chooses the public key 𝑒 such that:
➢ 1 < 𝑒 < 𝜙 𝑛 with 𝑒 and 𝜙(𝑛) coprime (gcd 𝑒, 𝜙 𝑛 = 1)
➢ Determines the private key d by solving the equation:
➢ 𝑒 × 𝑑 𝑚𝑜𝑑 𝜙 𝑛 = 1 with 0 ≤ 𝑑 ≤ 𝑛 (𝑑 = 𝑒 −1 𝑚𝑜𝑑 𝜙(𝑛))
➢ Share public key 𝑘𝑝𝑢𝑏 = {𝑒, 𝑛} and keeps private key 𝑘𝑝𝑟𝑖𝑣 = {𝑑, 𝑛}
18
© CINI – 2021 Rel. 07.02.2021
RSA encryption and decryption
19
➢ Public Key - 𝑘𝑝𝑢𝑏 = {𝑒, 𝑛} - Private Key - key 𝑘𝑝𝑟𝑖𝑣 = {𝑑, 𝑛}
➢ To encrypt a message 𝑀, the sender:
➢ Gets the recipient's public key 𝑘𝑝𝑢𝑏 = {𝑒, 𝑛}
➢ Computes 𝐶 = 𝑀𝑒 𝑚𝑜𝑑 𝑛, with 0 ≤ 𝑀 < 𝑛
➢ To decipher the ciphertext 𝐶, the recipient:
➢ Uses his private key 𝑘𝑝𝑟𝑖𝑣 = {𝑑, 𝑛}
➢ Computes 𝑀 = 𝐶 𝑑 𝑚𝑜𝑑 𝑛
➢ The "magic" is due to the fact that 𝑀𝑒 𝑑
𝑚𝑜𝑑 𝑛 = 𝑀
19
© CINI – 2021 Rel. 07.02.2021
Why RSA Works
20
➢ Euler’s theorem:
➢ 𝑎𝜙 𝑛
𝑚𝑜𝑑 𝑛 = 1 if gcd 𝑎, 𝑛 = 1
➢ In RSA we have:
➢ 𝑛 = 𝑝 × 𝑞 and 𝜙 𝑛 = 𝑝 − 1 × 𝑞 − 1
➢ The keys in the pair (𝑒, 𝑑) are inverses 𝑚𝑜𝑑 𝜙 𝑛
➢ 𝑒 × 𝑑 = 𝑘 × 𝜙 𝑛 + 1 for some integer value of 𝑘
20
© CINI – 2021 Rel. 07.02.2021
Why RSA Works
21
➢ Euler's theorem:
➢ 𝑎𝜙 𝑛 𝑚𝑜𝑑 𝑛 = 1 if gcd 𝑎, 𝑛 = 1
➢ Thus, working modulo 𝑛, 𝐶 𝑑 =
➢ = 𝑀𝑒×𝑑 (since 𝐶 = 𝑀𝑒 )
➢ = 𝑀𝑘×𝜙 𝑛 +1 since (𝑒, 𝑑) are inverses 𝑚𝑜𝑑 𝜙 𝑛
𝑘
➢ = 𝑀1 × 𝑀 𝜙 𝑛 with simple arithmetic
➢ = 𝑀1 × 1𝑘 for the Euler’s theorem
➢ = 𝑀1 = 𝑀
21
© CINI – 2021 Rel. 07.02.2021
An example in RSA - Key Setup
22
➢ Select two primes: 𝑝 = 17 and 𝑞 = 11
➢ Compute 𝑛 = 𝑝 × 𝑞 = 17 × 11 = 187
➢ Compute 𝜙(𝑛) = (𝑝– 1) × (𝑞 − 1) = 16 × 10 = 160
➢ Select 𝑒: 𝐺𝐶𝐷(𝑒, 160) = 1; 𝑒 = 7
➢ Determine 𝑑 < 160 such that (𝑑 × 𝑒) 𝑚𝑜𝑑 160 = 1
➢ We have 𝑑 = 23 as 23 × 7 = 161 = 160 + 1
➢ Publish public key 𝑘𝑝𝑢𝑏 = {𝑒 = 7, 𝑛 = 187}
➢ Keep private key secret 𝑘𝑝𝑟𝑖𝑣 = {𝑑 = 23, 𝑛 = 187}
22
© CINI – 2021 Rel. 07.02.2021
An example in RSA - En/Decryption
23
➢ Public key = {𝑒 = 7, 𝑛 = 187}
➢ Private key = {𝑑 = 23, 𝑛 = 187}
➢ Given 𝑀 = 88 (88 < 187)
➢ Cipher 𝑀:
➢ 𝐶 = 𝑀𝑒 𝑚𝑜𝑑 𝑛 = 887 𝑚𝑜𝑑 187 = 11
➢ Decipher 𝐶:
➢ 𝑀 = 𝐶 𝑑 𝑚𝑜𝑑 𝑛 = 1123 𝑚𝑜𝑑 187 = 88 23
© CINI – 2021 Rel. 07.02.2021
Outline
24
➢ Introduction to public-key cryptography
➢ RSA textbook scheme
➢ RSA-CRT
➢ Choose parameters
© CINI – 2021 Rel. 07.02.2021
RSA-CRT
25
➢ In practice, the public exponent 𝑒 is chosen to
optimize the (encryption) exponentiation operation
➢ The private exponent 𝑑 is unfortunately not as
convenient as the public one
➢ We can use the Chinese Remained Theorem (CRT) to
optimize also the decryption function
© CINI – 2021 Rel. 07.02.2021
RSA-CRT – Key generation
26
➢ Generate all the parameters from RSA textbook
schema as seen before (assuming 𝑝 > 𝑞)
➢ Precompute (just once) the following private values:
➢ 𝑑𝑝 = 𝑑 𝑚𝑜𝑑 𝑝 − 1
➢ 𝑑𝑞 = 𝑑 𝑚𝑜𝑑 𝑞 − 1
➢ 𝑞𝑖𝑛𝑣 = 𝑞 −1 (𝑚𝑜𝑑 𝑝)
© CINI – 2021 Rel. 07.02.2021
RSA-CRT – Decryption
27
➢ To decrypt a ciphertext c we have to execute:
➢ 𝑚1 = 𝑐 𝑑𝑝 𝑚𝑜𝑑 𝑝
➢ 𝑚2 = 𝑐 𝑑𝑞 𝑚𝑜𝑑 𝑝
➢ ℎ = 𝑞𝑖𝑛𝑣 × 𝑚1 − 𝑚2 𝑚𝑜𝑑 𝑝
➢ 𝑚 = 𝑚2 + ℎ × 𝑞 𝑚𝑜𝑑 𝑛
➢ In practice RSA-CRT is four time more efficiently than the standard
decryption operation 𝑚 = 𝑐 𝑑 (𝑚𝑜𝑑 𝑛)
➢ This thanks to the exponent used (𝑑𝑝 and 𝑑𝑞 ) which are smaller
than 𝑑
© CINI – 2021 Rel. 07.02.2021
Outline
28
➢ Introduction to public-key cryptography
➢ RSA textbook scheme
➢ RSA-CRT
➢ Choose parameters
© CINI – 2021 Rel. 07.02.2021
Choose parameters
29
➢ Choose the correct parameters is essential for the
security of RSA
➢ Some example recommendations for the primes:
➢ Primes p and q should be at least 1024 bits
➢ Same primes should not be reused for different keys
➢ Values of p and q should not be too close to each others
© CINI – 2021 Rel. 07.02.2021
Choose parameters
30
➢ The public exponent 𝑒 = 65537 is commonly choose
➢ This is mainly due to the exponentiation by squaring
algorithm used to evaluate 𝑐 = 𝑚𝑒 (𝑚𝑜𝑑 𝑛):
➢ Smaller public exponent (e.g., 𝑒 = 3) are vulnerable
© CINI – 2021 Rel. 07.02.2021
What can go wrong?
31
➢ In the next lecture we will present different
vulnerabilities, mainly due to some bad choice in the
parameters
➢ For example:
➢ How to factorize public modulo
➢ Standard attacks in vulnerable scenarios
➢ Attacks with RSA oracles
© CINI – 2021 Rel. 07.02.2021
Gaspare FERRARO
CyberSecNatLab
Matteo ROSSI
Politecnico di Torino
RSA
32 [Link]