The Symmetric RSA

A Symmetric Version of RSA

There are two ideas here:

A symmetric matched pair of RSA keys,
Concealment of both keys of a pair.

The public key RSA system, as far as I am aware, is always described asymmetrically:

The public key is not concealed whereas the private key is.
The public key can be derived from the private key.
The exponent of the public key is smaller and thus that key is faster to use.

It occurred to me just now that there is a symmetric version of RSA in which, as in normal RSA, two keys are produced where either is necessary and sufficient to decrypt what was encrypted by the other; but unlike normal RSA, the two keys are parallel in their structure.

I hasten to note that I know of no compelling problems to which this is a solution but merely note that symmetries seldom go unexploited! The symmetric RSA scheme has a disadvantage over normal practice in that both keys are expensive to use. In the normal scheme the public key is much quicker to use because of its small exponent.

To exploit symmetric applications, current protocols must be reexamined for concealment of the public key, as that was not a requirement when those protocols were designed.

The Math

Here are equations to fix names for the numbers we will discuss.

p and q are prime.
c = m^e (mod pq)
m = c^d (mod pq)
ed = 1 (mod (p−1)(q−1))
0 ≤ c, m < pq.

These equations work for both normal RSA and the symmetric version. p and q are large primes of about the same size. m is the plain text and c is the ciphertext.

Generation of Keys

First p and q are chosen. d is normally chosen as 2^2ⁿ+1 for some n∈{0, 1, 4, 8}. d must be relatively prime to both p−1 and q−1. Equation 3 is then solved for e. The private key is {e, p, q} and the public key is {d, pq}.

In the symmetric variation d is chosen to be unguessable. While the generation of the keys is asymmetric that fact is invisible outside the generator mechanism. When both keys are concealed they are on equal footing. This symmetry will simplify protocols and arguments about their correctness. Note that if d is chosen to be unguessable then pq may be revealed for that will not compromise the “public” key. I suspect that pq can be shared between several symmetric key pairs—a family parameter!

Applications for Symmetric RSA Key Pairs

In the most general case we generate a symmetric key pair, A and B. There are two populations each with its own collective interests. A is disseminated among the first population and B among the second. The relevant security properties are:

A message from one population can be so recognized by the other.
Only members of one population can decrypt messages from the other.

Dean’s Example

Assume multiple archivers who are responsible for physical custody of some data, and multiple sources that produce the data to be archived. A symmetric RSA key pair is produced and the first key is given to each of the archivers and the second key to each of the sources. The archivers are able to verify that the data they receive comes from authorized sources, while no one else, even the other sources, can decrypt the data.

To solve this problem with conventional RSA we try three cases:

equip the archivers (and only them) with a public key and the sources with the corresponding private key.
equip the archivers with the private key and the sources (and only them) with the public key.
Use two key pairs, one for secrecy and one for authorization.

In scheme 1 data from one source may be decrypted by the other sources since the public key can be derived from the private key. This may be unsuitable.
In scheme 2 the archivers can read data that is addressed to other archivers. This may be unsuitable.
In scheme 3 ...

It is not yet clear how to concoct a plausible set of requirements that requires the symmetric key.

Pessimistic Conjecture

The following may be the case. If so the scope of the above idea would be much better delimited.

Two conventional public RSA keys pairs serve all the functions of a symmetric RSA key pair.

In more detail, to get the function of a symmetric RSA key pair, generate two independent conventional RSA key pairs, A and B and then form two packets:

Private key from A with public key from B
Private key from B with public key from A

These packets may now be respectively disseminated to wherever the keys from the symmetric key pair would have been disseminated. Neither packet can be computed from the other. Note that the “public” keys above are disseminated only as prescribed!

To transmit a message with such a packet, first sign the message with the private key from the package, then encrypt the result with the public key from the packet.

To receive a message with a packet, decrypt the message with the private key from the packet and then verify the signature with the public key from the packet.

There are formalizations for arguments such as these that would raise issues more systematically.

There is only a meager advantage of the symmetric RSA cypher over two pair; This is because the public RSA keys have few bits in the exponent and are thus fast to use.

I think that the same tricks regarding bulk data apply equally to symmetric and asymmetric RSA.