Quest for Minimalist Secure RSA Key Generation
Public key cryptography is a powerful mechanism for many purposes.
We examine here how a person might safely choose an RSA key pair while minimizing reliance on software and computer platforms.
It is not even required that the private key is remembered in a computer.
I propose an algorithm here to do this chore that is as simple as I can make it.
It is implemented in this Scheme code but I shall try to describe the algorithm in English as clearly as I can and without reference to the code, except for those who wish to understand the code.
Comments on the code appear between curly braces “{}” and should be unnecessary for understanding of the algorithm.
It is deterministic and ideally would be written in several languages whose outputs could be compared by anyone suspicious of the implementations.
To that end I go to extra lengths here to describe the algorithm:
- hoping to encourage other implementations and
- supporting analysis of the algorithm.
Part of the plan is to specify and publish a simple deterministic function F from a string of characters to a public-private RSA key pair.
With access to several implementations, some of which may be corrupt, it is possible to compare outputs from each version for the same string input and build trust in some of those versions by trying each of some suite of strings on each version.
Hopefully one of those versions will run on a machine and platform where the computation can be confined either by trust in the platform or discarding part of all of the hardware.
One must not give it a clue that it is computing the real case, lest it revert then to a choice of guessable primes.
That version is not in a position to know whether it is computing for the ultimate RSA pair, or computing for its results to be compared.
You are rather safe even if the version you use to compute your real key pair is corrupt!
Curiously this deterministic procedure is internally non-deterministic.
The internal source of nondeterminism is best different in different implementations, the better to gain confidence that the function is indeed deterministic; even implementations by your adversaries!
The algorithm takes a key length len {n} and a string of text {seed} to produce a public key with len significant bits together with its two prime factors that constitute the private key.
The text input to the algorithm serves directly as the key that initializes the RC4 crypto algorithm.
That produces an object called state {state} that produces a stream of eight bit bytes which we use as a deterministic stream depending only on the input text.
Together this stream and len, determine the key pair.
{In the program (RC4 seed) produces the state object.}
I use RC4(drop 768).
This means that after initialization by the string the first 768 characters of the stream are generated and discarded.
This seems to make the remaining stream less scrutable.
{(state ‘sb) is a function of 0 args that returns the next stream byte and also modifies the state of state.}
We define a function G {G} which takes two large integers x, y and returns a prime in the range [x, x+y].
All about G.
The private RSA key consists of two large primes p and q.
We choose p from the range [x, x+len−1] where x = ⅔(2len/2) rounded down to an integer.
We then choose q from the range [P, 2P] where P = 2len/(2p) rounded down.
Now 2len−1 < pq < 2len and we report pq, p and q in hexadecimal.
Good luck finding a way to use you new key pair as safely as this.
I have some preliminary ideas.
See this.
Previous similar idea.
RSA nexus