CM30173: Cryptography
eserved@d =[@let@token art V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Part V
Public-key cryptography
CM30173: CryptographyPart V
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Recall
Definition (A public-key cryptosystem)
A public-key cryptosystem is a cryptosystem
(P, C,K, E ,D) where
1 For every k ! K, ek is the inverse of dk
2 For every k ! K and for every x ! P or y ! C,
ek(x) and dk(y) are easy to compute
3 It is computationally infeasible (for almost all
k ! K) to derive dk from ek
4 For every k ! K it is feasible to compute ek and dk
from k
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
So, what do we really mean by secure?
Possible attack goals:
Total break
Partial break
Distinguishability of ciphertexts
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
So, what do we really mean by secure?
Possible attack goals:
Total break
Partial break
Distinguishability of ciphertexts
We have talked about unconditional security and
computational security.
Two other definitions of security:
Semantic security
Provable security
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
1 RSA security: all about factoring?
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
2 RSA in practice
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Basic RSA is not semantically secure
Imagine all messages are either “Buy” or “Sell”. Call
these x1 and x2.
Attacker sees a new message c being sent to Bob
Ltd. with public RSA key (n, b)
Attacker computes
c1 = x
b
1 (mod n)
and compares this with c. If they match he knows I
sent the message “Buy”.
The attacker can distinguish ciphertexts.
Basic RSA is not semantically secure because the
encryption function is deterministic.
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
1 RSA security: all about factoring?
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
2 RSA in practice
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Multiplicative properties
Let x1, x2 be two plaintext messages. Notice that
ek(x1x2) ⌘ (x1x2)b ⌘ xb1x
b
2 ⌘ ek(x1)ek(x2) (mod n)
The encryption of x = x1x2 is y = ek(x1)ek(x2).
RSA is malleable: known plaintext can be altered
without decryption.
We can use this to run an adaptive chosen
ciphertext attack.
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Multiplicative properties
Let x1, x2 be two plaintext messages. Notice that
ek(x1x2) ⌘ (x1x2)b ⌘ xb1x
b
2 ⌘ ek(x1)ek(x2) (mod n)
The encryption of x = x1x2 is y = ek(x1)ek(x2).
RSA is malleable: known plaintext can be altered
without decryption.
We can use this to run an adaptive chosen
ciphertext attack.
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Multiplicative properties
Let x1, x2 be two plaintext messages. Notice that
ek(x1x2) ⌘ (x1x2)b ⌘ xb1x
b
2 ⌘ ek(x1)ek(x2) (mod n)
The encryption of x = x1x2 is y = ek(x1)ek(x2).
RSA is malleable: known plaintext can be altered
without decryption.
We can use this to run an adaptive chosen
ciphertext attack.
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
1 RSA security: all about factoring?
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
2 RSA in practice
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus
Trusted authority produces RSA key pairs (n, b),
(n, a) for all users of a network.
Alice, Bob and Oscar are all legitimate users of the
network and so receive keys.
The TA fixes n = pq and provides each user i with
with unique bi and ai.
Alice encrypts x using Bob’s public key (n, b1) and
sends y on the insecure network.
What is the problem here?
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus
Trusted authority produces RSA key pairs (n, b),
(n, a) for all users of a network.
Alice, Bob and Oscar are all legitimate users of the
network and so receive keys.
The TA fixes n = pq and provides each user i with
with unique bi and ai.
Alice encrypts x using Bob’s public key (n, b1) and
sends y on the insecure network.
What is the problem here?
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus
Trusted authority produces RSA key pairs (n, b),
(n, a) for all users of a network.
Alice, Bob and Oscar are all legitimate users of the
network and so receive keys.
The TA fixes n = pq and provides each user i with
with unique bi and ai.
Alice encrypts x using Bob’s public key (n, b1) and
sends y on the insecure network.
What is the problem here?
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus
Trusted authority produces RSA key pairs (n, b),
(n, a) for all users of a network.
Alice, Bob and Oscar are all legitimate users of the
network and so receive keys.
The TA fixes n = pq and provides each user i with
with unique bi and ai.
Alice encrypts x using Bob’s public key (n, b1) and
sends y on the insecure network.
What is the problem here?
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus — take 2
Lets say Oscar doesn’t have a key on the network but is
some external attacker.
Alice wants to broadcast a message x:
y1 ⌘ xb1 (mod n)
y2 ⌘ xb2 (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus — take 2
Lets say Oscar doesn’t have a key on the network but is
some external attacker.
Alice wants to broadcast a message x:
y1 ⌘ xb1 (mod n)
y2 ⌘ xb2 (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus — take 2
Oscar uses the extended Euclidean algorithm to find s, t
such that
sb1 + tb2 = 1 if gcd(b1, b2) = 1
ys1y
t
2 ⌘ x
sb1xtb2 (mod n)
⌘ x1�tb2xtb2 ⌘ x1 ⌘ x (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Common modulus — take 2
Oscar uses the extended Euclidean algorithm to find s, t
such that
sb1 + tb2 = 1 if gcd(b1, b2) = 1
ys1y
t
2 ⌘ x
sb1xtb2 (mod n)
⌘ x1�tb2xtb2 ⌘ x1 ⌘ x (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Example
n = 11021, b1 = 5, b2 = 7, Alice encrypts the plaintext
50:
y1 ⌘ 50b1 ⌘ 10566 (mod n)
y2 ⌘ 50b2 ⌘ 8684 (mod n)
Extended Euclidean algorithm produces s = 3, t = �2:
3⇥ b1 + (�2)⇥ b2 = 1
ys1y
t
2 ⌘ 10566
3 ⇥ 8684�2 (mod n)
⌘ 112⇥ 8463 (mod n)
⌘ 50 (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Example
n = 11021, b1 = 5, b2 = 7, Alice encrypts the plaintext
50:
y1 ⌘ 50b1 ⌘ 10566 (mod n)
y2 ⌘ 50b2 ⌘ 8684 (mod n)
Extended Euclidean algorithm produces s = 3, t = �2:
3⇥ b1 + (�2)⇥ b2 = 1
ys1y
t
2 ⌘ 10566
3 ⇥ 8684�2 (mod n)
⌘ 112⇥ 8463 (mod n)
⌘ 50 (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Example
n = 11021, b1 = 5, b2 = 7, Alice encrypts the plaintext
50:
y1 ⌘ 50b1 ⌘ 10566 (mod n)
y2 ⌘ 50b2 ⌘ 8684 (mod n)
Extended Euclidean algorithm produces s = 3, t = �2:
3⇥ b1 + (�2)⇥ b2 = 1
ys1y
t
2 ⌘ 10566
3 ⇥ 8684�2 (mod n)
⌘ 112⇥ 8463 (mod n)
⌘ 50 (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Example
n = 11021, b1 = 5, b2 = 7, Alice encrypts the plaintext
50:
y1 ⌘ 50b1 ⌘ 10566 (mod n)
y2 ⌘ 50b2 ⌘ 8684 (mod n)
Extended Euclidean algorithm produces s = 3, t = �2:
3⇥ b1 + (�2)⇥ b2 = 1
ys1y
t
2 ⌘ 10566
3 ⇥ 8684�2 (mod n)
⌘ 112⇥ 8463 (mod n)
⌘ 50 (mod n)
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
1 RSA security: all about factoring?
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
2 RSA in practice
CM30173: CryptographyPart V
CM30173:
Cryptography
Part V
RSA security: all
about factoring?
Multiplicative
properties
Common modulus
Small private exponent
Small public exponent
RSA in practice
RSA security: all about factoring?
RSA in practice
Multiplicative properties
Common modulus
Small private exponent
Small public exponent
Small private exponent
To increase the speed of decryption perhaps we can use
a small private exponent a?
Wiener presented an attack that computes a from the
public key if
3a < n1/4 and q < p < 2q We won’t prove that that this is the case but if you are interested see Stinson 5.7.3. How else could we speed up decryption? We can use the Chinese remainder theorem. CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small private exponent To increase the speed of decryption perhaps we can use a small private exponent a? Wiener presented an attack that computes a from the public key if 3a < n1/4 and q < p < 2q We won’t prove that that this is the case but if you are interested see Stinson 5.7.3. How else could we speed up decryption? We can use the Chinese remainder theorem. CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small private exponent To increase the speed of decryption perhaps we can use a small private exponent a? Wiener presented an attack that computes a from the public key if 3a < n1/4 and q < p < 2q We won’t prove that that this is the case but if you are interested see Stinson 5.7.3. How else could we speed up decryption? We can use the Chinese remainder theorem. CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small private exponent To increase the speed of decryption perhaps we can use a small private exponent a? Wiener presented an attack that computes a from the public key if 3a < n1/4 and q < p < 2q We won’t prove that that this is the case but if you are interested see Stinson 5.7.3. How else could we speed up decryption? We can use the Chinese remainder theorem. CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent 1 RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent 2 RSA in practice CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small public exponent To reduce encryption time a small public exponent b is often used. However, very small exponents, such as b = 3, are not secure Alice wants to broadcast a message x: y1 ⌘ x3 (mod n1) y2 ⌘ x3 (mod n2) y3 ⌘ x3 (mod n3) CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small public exponent To reduce encryption time a small public exponent b is often used. However, very small exponents, such as b = 3, are not secure Alice wants to broadcast a message x: y1 ⌘ x3 (mod n1) y2 ⌘ x3 (mod n2) y3 ⌘ x3 (mod n3) CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small public exponent Attacker can use the Chinese remainder theorem to compute solution to Y ⌘ y1 (mod n1) Y ⌘ y2 (mod n2) Y ⌘ y3 (mod n3) Say the solution is Y (mod n1n2n3) But x3 < n1n2n3 so we must have Y = x 3 and hence x = Y 1/3 CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small public exponent Attacker can use the Chinese remainder theorem to compute solution to Y ⌘ y1 (mod n1) Y ⌘ y2 (mod n2) Y ⌘ y3 (mod n3) Say the solution is Y (mod n1n2n3) But x3 < n1n2n3 so we must have Y = x 3 and hence x = Y 1/3 CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Small public exponent Attacker can use the Chinese remainder theorem to compute solution to Y ⌘ y1 (mod n1) Y ⌘ y2 (mod n2) Y ⌘ y3 (mod n3) Say the solution is Y (mod n1n2n3) But x3 < n1n2n3 so we must have Y = x 3 and hence x = Y 1/3 CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Example: n1 = 319, n2 = 299, n3 = 323 Let b = 3, broadcasting x = 7 leads to y1 ⌘ 73 ⌘ 343 ⌘ 24 (mod 319) y2 ⌘ 73 ⌘ 343 ⌘ 44 (mod 299) y3 ⌘ 73 ⌘ 343 ⌘ 20 (mod 323) The CRT will give us: M = 30808063 299⇥ 323 = 96577, 96577�1 ⌘ 315 (mod 319) 319⇥ 323 = 103037, 103037�1 ⌘ 38 (mod 299) 319⇥ 299 = 95381, 95381�1 ⌘ 286 (mod 323) (24⇥ 96577⇥ 315 + 44⇥ 103037⇥ 38 + 20⇥ 95381⇥ 286) ⌘ 343 (mod 30808063) CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Example: n1 = 319, n2 = 299, n3 = 323 Let b = 3, broadcasting x = 7 leads to y1 ⌘ 73 ⌘ 343 ⌘ 24 (mod 319) y2 ⌘ 73 ⌘ 343 ⌘ 44 (mod 299) y3 ⌘ 73 ⌘ 343 ⌘ 20 (mod 323) The CRT will give us: M = 30808063 299⇥ 323 = 96577, 96577�1 ⌘ 315 (mod 319) 319⇥ 323 = 103037, 103037�1 ⌘ 38 (mod 299) 319⇥ 299 = 95381, 95381�1 ⌘ 286 (mod 323) (24⇥ 96577⇥ 315 + 44⇥ 103037⇥ 38 + 20⇥ 95381⇥ 286) ⌘ 343 (mod 30808063) CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Example: n1 = 319, n2 = 299, n3 = 323 Let b = 3, broadcasting x = 7 leads to y1 ⌘ 73 ⌘ 343 ⌘ 24 (mod 319) y2 ⌘ 73 ⌘ 343 ⌘ 44 (mod 299) y3 ⌘ 73 ⌘ 343 ⌘ 20 (mod 323) The CRT will give us: M = 30808063 299⇥ 323 = 96577, 96577�1 ⌘ 315 (mod 319) 319⇥ 323 = 103037, 103037�1 ⌘ 38 (mod 299) 319⇥ 299 = 95381, 95381�1 ⌘ 286 (mod 323) (24⇥ 96577⇥ 315 + 44⇥ 103037⇥ 38 + 20⇥ 95381⇥ 286) ⌘ 343 (mod 30808063) CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Multiplicative properties Common modulus Small private exponent Small public exponent Relation to padding Ways to avoid the attack: Use larger RSA exponents Increase the amount of padding Make padding depend on the message e.g. hash the message and append this Spread random padding throughout message (some methods can still be attacked) CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice 1 RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent 2 RSA in practice CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice RSA in practice What conclusions can we draw? What do we need? What do we want? CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Primitives and protocols We have a cryptographic primitive, that is, the “raw” or “basic” RSA. In practice we use protocols built of many primitives to achieve secure communication, perhaps with data integrity build in. The most important of these for RSA is Optimal Asymmetric Encryption Padding CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Primitives and protocols We have a cryptographic primitive, that is, the “raw” or “basic” RSA. In practice we use protocols built of many primitives to achieve secure communication, perhaps with data integrity build in. The most important of these for RSA is Optimal Asymmetric Encryption Padding CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Primitives and protocols We have a cryptographic primitive, that is, the “raw” or “basic” RSA. In practice we use protocols built of many primitives to achieve secure communication, perhaps with data integrity build in. The most important of these for RSA is Optimal Asymmetric Encryption Padding CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice RSA-OAEP OAEP is a padding scheme due to Bellare and Rogaway OAEP is used in Public Key Cryptography Standards (PKCS) and hence most Internet protocols There was some debate about the specific security status of RSA-OAEP but in 2001 Fujisaki, Okamoto, Pointcheval and Stern proved that: Assuming that the RSA problem of computing bth roots modulo n is computationally infeasible RSA-OAEP is semantically secure against adaptive chosen ciphertext attacks. CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice RSA-OAEP OAEP is a padding scheme due to Bellare and Rogaway OAEP is used in Public Key Cryptography Standards (PKCS) and hence most Internet protocols There was some debate about the specific security status of RSA-OAEP but in 2001 Fujisaki, Okamoto, Pointcheval and Stern proved that: Assuming that the RSA problem of computing bth roots modulo n is computationally infeasible RSA-OAEP is semantically secure against adaptive chosen ciphertext attacks. CM30173: CryptographyPart V CM30173: Cryptography Part V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice RSA security: all about factoring? RSA in practice Further reading D. Boneh. Twenty years of attacks on the RSA cryptosystem, Notices of the AMS, 46:203-231, 1999. Stinson: sections 5.7 and 5.9 HAC: sections 8.2.3 and notes on section 8.2 (pages 312–315) For those interested in the practicalities of RSA: PKCS #1 v2.1: RSA Cryptography Standard, http://www.rsa.com/rsalabs/node.asp?id=2125, 2002, and the many papers cited by it! For the even more practical, RSA within infrastructure (more on infrastructure later): http://www.ietf.org/rfc/rfc4055.txt CM30173: CryptographyPart V RSA security: all about factoring? Multiplicative properties Common modulus Small private exponent Small public exponent RSA in practice