RSA Steps 2 and 3 in Key Generation

[arcfide]

Compute n = pq.

n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.

Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), where φ is Euler's totient function.

[Tikhon03]

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.