Abstract by anuja a sonalker on Asymmetric Key Distribution

2.8 Breaking the Algorithm 
In the following sections, we consider how an intelligent cryptanalyst would try to break 
the public key algorithm, i.e., try to get the secret decryption key from the publicly 
revealed encryption key. These attacks are common to any RSA based algorithm.
2.8.1 Factoring N 
One of the major concerns in key generation is generally the ability to factor N. While 
factoring large numbers is neither provably difficult nor impossible, stress lies on the fact 
that the time required to factorize a relatively large number (of the order of 200 digits) is 
not small in any way. This makes the attack too late to cause harm to the system. 
No doubt factoring N would definitely give a cryptanalyst the ability to crack our 
method, as it would any RSA based cryptographic scheme. The factors would enable 
computation of 
φ
(n) and hence d. It is however, asserted that the time required to factor N 
is very large and may be impractical with the technology available today. According to 
the RSA challenge ‘99 [20] [18], [19] the fastest factoring algorithm currently known to 
us is the classical Number Field Sieve (NFS) algorithm[19]; it factors a number N in 
approximately 
e
N
N
3
2
3
1
)))
(ln(ln(
))
(ln(
92
.
1
operations. It works in two stages. The first stage of 
the process is to search for equations that satisfy certain mathematical properties. This is 
followed by a large matrix calculation, which eventually produces the prime factors of 
the target number.
Table 2.1 shows the approximate amount of time required by the Number Field Sieve 
Algorithm to break different keys (expressed in number of operations), the size of the 
required factor base, amount of memory per machine to do sieving and the final matrix 
memory. 

---

16