Tikhon03
commented
9 years ago For RSA n, where n is the number of bits , p and q are each n^1/2 bits . For numbers of this size, multiplication of big numbers needs to be implemented. In APL base conversions are time consuming, hence, our implementation must keep this to a minimum. So, if the implemation operates on binary arrays there are two options for a simple APL implementation.
1) FFT multiplication (xtimes already does this) 2) Toom-Cook mulitplication
Karatsuba is a specially case of Toom-Cook, but only applies directly to 2-bit numbers. Tests on numbers of this size reveal that it is about 10 times faster than xtimes. As such it may be worthwhile to implement Toom-Cook for eliptic curves, but for RSA there does not seem to be much incentive to do so.
Based on current cryptanalysis, the NSA recommends the following RSA strengths corresponding to symmetric keys (in bits):
Sym. Key : RSA 80 : 1024 112 : 2048 128 : 3072 192 : 7680 256 : 15360
Our implementation should allow for the maximum strength in this table, and hence the efficiency of our algorithms implementation needs to be tested for bit arrays up to 15360-bits. Currently, the only time requirement we will stipulate is that a full RSA 4096 computation should take no more than about 5 seconds. Given that xtimes takes only about 1/1000 of a second for numbers of this size, this requirement should be easy to satisfy.
Compute n = pq.
Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function.