5.11 PUBLIC KEY CRY PT ANALYSIS:
1. Mathematically: deduce d from n and e.
2. Guess (p -1) and (q-1)
3. Factoring n : having e ===> deduce d.
4. Chosen ciphertext attack: (Protocol attack): scenario:
eve wants Alice to sign m3; she generates ml and m2 Such that
m3 ml m2 (mod n)
m3d (m1d mod n) (m2d mod n)
moral: never use RSA to sign a random document presented by a stranger.
5. Common modulus: Known n,c1. c2., e1, and e2;
Select two random numbers r and s such that:
rel +,se2 1, assume r is negative:
( C1-1 )- r. c25 =m mod n
Moral: Don t share a common n among a group of users.
6. Genetic algorithm:
Choose a set of prime numbers such that the product of any two of them less than n use fitness function with the following characteistics:
- Neglect all even numbers, and those least significant digit = 0.
- Neglect numbers, which are divided by 3.
- Generated numbers by mating should be relatively prime to e.
7. Crypt analysis knowing n and e:
8. It is possible for cryptanalyst to try every possible d, until he fined the correct one. This is called brute-force attack. It is less efficient than other methods.
9. There is a common probabilistic algorithm for computing primesp and q.
10. Factoring n is the most obvious means of attack. Factoring a number means finding its prime factors. There are some factoring algorithm such as number field sieve (NFS), Quadratic sieve (QS), elliptic curve method (ECM), pollards Montecarlo algorithm, ..., etc. In March 1994, a 129-digit (428-bit) number was factored using the double prime variation of the multiple polynomial (QS) by a team of mathematician, led by Lenstra. Volunteers on the Internet carried out the computation; 600 people and 1600 machines over the course of eight months. The machines communicated via electronic mail sending their intermediate result to a central machine where the final steps of analysis took Lessons learned: