5 - RSA in more detail Flashcards
To send m to Bob it is encrypted as
c= m^e mod n
TO decrypt, Bob uses…
c^d mod n to get m
RSA - example with p =3 and q =11
n = pq = 33
r = (p-1)(q-1) = 20
e = 3 (random, no common divisor with 20 other than 1)
d = 7 (mult inverse of 3 in Z20)
Pub key = (e,n) = (3,33)
Private = (d,p,q) = (7,3,11)
Eg m=5 is c=5^3 mod 33 = 26
then m = c^7 mod 33
so 26^7 mod 33 = 5W
RSA -Why is it correct?
c^d mod n =
(m^e mod n)^d mod n =
m^(ed) mod n =
m
True or false: (m^e mod n)^d mod n = m^(ed) mod n
TRUE
If you have a 1024bit integer to add to another, is this possible outright?
No, processors generally cannot handle all in one.
Add in blocks of 32bit etc and carry over
How long do p and q need to be ( not in number of bits)
More than 150 decimal digits long.
Main method of RSA attacking
Integer Factorisation
Integer factorisation using n to get the decryption exponent d from a public key
p and q are prime numbers. Work them out from n and you already know e from the public key.
Follow how the key was made then you get the decryption exponent
Integer factorisation: would finding r or d directly be quicker?
No, it has been shown that it is roughly as ahrd as factorisation
Is factorisation NP-hard or complete?
We do not know. It may be possible to do in polynomial time
How to protect against RSA mathematical attacks?
- Choose p and q sufficiently large
- Currently recommended 1024bit key and 2048bit keys (where p and q are approximiately half the bits)
Side channel attacks
Attacks based on physical realisation of the implementation. Timing power, electromagnetic leaks etc
Eve utilises a side channel attack…
she observes how long/much power it takes to decrypt a ciphertext. The time taken by the square-and-multiply algorithm increases with the number of 1s in the binary rep of d
Protection against timing attacks
Modify the exponentiation algorithm to take constant/random time
