# On the Existence of Multiple RSA Private Keys

Authors: Chuan-Kun Wu; Bin Zhao
Journal: Security and Communication Networks
 (2022)

---

## Abstract

It is known that, given an RSA modulus,n=pq, the public key e and the corresponding private key d satisfy the modulo congruence ed≡1modϕn, where ϕn=p−1q−1. Usually, the private key d can be computed efficiently using the extended Euclidean algorithm, and it is common knowledge that the private key is unique in the sense of modular ϕn. This paper shows that there exist multiple private keys d; they all satisfy that d<ϕn. This paper also presents the exact relationship between an RSA public key and a corresponding private key.


---

## Body

## 1. Introduction

Since the proposal of the RSA public key cryptosystem [1], there have been thousands of papers discussing RSA related problems (see e.g., [2–4]). RSA encryption as well as RSA digital signature algorithms have been in wide commercial use, and research related to RSA public key cryptosystems continues [5–7].It is commonly known as a fact that an RSA public key corresponds to a unique private key in the sense when the public key and the private key take moduloϕn operation, where ϕn is the Euler’s totient function of the public modulus n.This paper reveals an interesting property: an RSA public key corresponds to multiple private keys. Equivalently, this can be understood as a private key that corresponds to multiple public keys because a public key and a private key can swap at the stage of their computation.The existence of multiple private keys corresponding to a public key has long been known as the following case: lete and d be the RSA public key and the private key, and the public modulus is n. Then, for any integer k, d′=d+kϕn is also a valid private key, i.e., any message encrypted using the public key e can be correctly decrypted using d′ as the private key. However, in the sense of modulo ϕn operation, d is the only one left since d′modϕn=d.To the contrary of common knowledge, this paper shows an interesting result: given an RSA modulusn and a public key e, even under the condition that the private key d takes over the operation of modulo ϕn, there can exist multiple private keys. Some implications about the problem have been mentioned (e.g. [8]), but no explicit explanation is given.With mathematical deduction, this paper shows that, given an RSA public keye, a sufficient and necessary condition for d to be a valid private key is edmodλn, and the number of such private keys under the restriction of modulo ϕn operation is given.


## 2. Traditional Computation of the RSA Private Key and Its Uniqueness

Letn=pq be the public modulus of an RSA public key cryptosystem, where p and q are different primes. Let e be the public key and d be the private key. Then, the following modulo congruence holds:(1)ed≡1modϕn,where ϕn=p−1q−1 is the Euler’s totient function of n.The modulo congruence (1) means that e and d are inverses of each other in the sense of modulo ϕn operation. Given either e or d, the other one can efficiently be computed using the famous extended Euclidean algorithm [9, 10], which is described as follows.Lemma 1.
Given integersaandb, then it is efficient to compute integersuandvsuch thatd=au+bv=gcda,b.
Using a recursive algorithm, it is easy to write a simple programing code for the extended Euclidean algorithm. Alternatively, the algorithm can be implemented using a loop.
It is easy to see that the modulo congruence (1) can equivalently be written as(2)ed=1+kϕn,where k is an integer.
Given a messagem<n, the RSA encryption algorithm is as follows:(3)c=memodn.
The corresponding decryption algorithm can be written as(4)cdmodn=m.
The underline mathematics for the correct decryption is the Euler theorem for the case when the messagem is coprime to n, which is described as follows.Lemma 2.
Letnbe a positive integer,0<m<nbe an integer coprime ton. Then, the following congruent holds:(5)mϕnmodn=1.The Euler theorem (i.e., Lemma2) ensures that if a message m is coprime to n, then the private key will work correctly, i.e., for the ciphertext c=memodn, we have(6)cdmodn=memodndmodn,=medmodn,=m1+kϕnmodn,taking Eqn.2into it,=m.mϕnkmodn,=m.taking Eqn.5into it.Whenm is not coprime to n, using the Chinese remainder theorem [11], it can also be shown that the equality cdmodn=m still holds.Given an RSA public keye, and let d be a corresponding private key computed using the extended Euclidean algorithm (see Lemma 1). Then, it is obvious that for any integer t, d′=d+tϕn also works correctly as the decryption key. This comes from the observation that given c=memodn, we have(7)cd′modn=memodnd+tϕnmodn,=medmetϕnmodn,=m1+k+etϕnmodn,=m⋅mϕnk+etmodn,=m.If we only consider the positive values of private keys,t must not be negative. In this sense, there exist multiple private keys in an RSA public key cryptosystem for a given public key.However, ift>0, then d′>ϕn, which may not be preferable because the computation of cd′modn is equivalent to that of cd′modϕnmodn. This means that the values of the private keys are congruent to each other in the sense of modulo ϕn; hence, d′ is congruent to d modulo ϕn.It is assumed that when using the extended Euclidean algorithm to compute an RSA private key, the algorithm outputs a value in the range0<d<ϕn. Now, we propose a question: is there a chance for the extended Euclidean algorithm to produce a different private key d′≠d?Let the extended Euclidean algorithm produce two different private keysd and d′ in two executions, then we must have that both the congruences edmodϕn=1 and ed′modϕ(n=1 hold; hence, we have ed−d′modϕn=0, i.e., ϕn|ed−d′. Since e is required to be coprime to ϕn (otherwise, the private key would not exist), hence we have ϕn|d−d′. Since both d and d′ should be in the range between 0 and ϕn, this means that d′=d must hold. This shows the uniqueness of the RSA private key.


## 3. On the Existence of Multiple RSA Private Keys

Letn be a positive integer. Denote by Zn=0,1,…,n−1 the ring of residues modulo n, and let Zn∗ be the subset of Zn whose elements are coprime to n. Then, it is easy to verify that,Zn∗ together with the multiplication operation over Zn forms a multiplicative group. It is known that the order of Zn∗, i.e., the number of elements in Zn∗, is ϕn, which is the definition of ϕn.For an elementα∈Zn∗, define its order to be the smallest positive integer k such that the congruent αkmodn=1 holds, i.e.,(8)ordnα=mink,k>0αkmodn=1,and denote it as ordnα=k. It is a basic result in group theory that k|ϕn, i.e., k is a factor of ϕn. Define λn to be the maximum value of ordnα for all α∈Zn∗, i.e.,(9)λn=maxα∈Zn∗ordnα.Then, we haveLemma 3.
With the above definition and notation, letm∈Zn∗, we have thatordnm|λnandλn|ϕn.
The result of Lemma3 is a preliminary result in the theory of finite groups, which can be found in most relevant books such as [12].
Now we further explore the properties ofλn. Since Zn∗ exists only when n≥2, the definition of λn makes sense only when n≥2. We haveLemma 4.
([13]) The value of the functionλncan be computed as follows:(i)
λ2=1,λ4=2, andλ2k=2k−2fork≥3.(ii)
Ifpis an odd prime, thenλpk=pk−1p−1=ϕpkfor any positive integerk.(iii)
Ifn=n1n2…nk, whereniare pairwise coprime, then(10)λn=lcmλn1,λn2,…,λnk.
Note that for any positive integern, λn|ϕn. So, we also haveTheorem 1.
Given an RSA public keyn,e. Letd<ϕnbe a private key. Then, the equality(11)medmodn=m.
Holds for every messagem<n, if and only if the following congruence holds:(12)ed≡1modλn.Proof.
Sufficiency: suppose that (12) holds, which means that there exists some integer k such that ed=1+kλn. Then, the sufficiency is equivalent to prove that for any message m<n, medmodn=m must hold. The following cases are considered, respectively.(i)
Ifm is coprime to n, then m∈Zn∗. By Lemma 3, since ordnm|λn, we must have that mλnmodn=1 holds. This leads to that medmodn=m1+kλnmodn=m.mλnkmodn=m.(ii)
Ifm is a multiple of p, it must not be a multiple of q. Otherwise, m must be a multiple of n which is in contradiction with the assumption that m<n. In this case, it is easy to prove that m must be coprime to q. Since p|m, we have that med−mmodp=0. By Lemma 4 we know that λn=lcmp−1,q−1; hence, q−1|λn. Since q and m are coprime, by Fermat little theorem (i.e., a special case of Lemma 2), we have mq−1modq=1; hence, the congruent mλnmodq=1 and consequently med−mmodq=0 hold. This means that both p|med−m and q|med−m hold. Therefore, we have n|med−m or equivalently med−mmodn=0.(iii)
Ifm is a multiple of q, it must not be a multiple of p, and hence must be coprime to p. The proof for this case is similar to case (ii).
Necessity: assume that congruence (9) does not hold, i.e., r=edmodλn≠1. By the definition of λn, there exists m such that ordnm=λn. It can be shown that such a message m is coprime to n. Since d is a private key, hence we have medmodn=mrmodn=m, so we get mr−1modn=1. By the assumption that the order of m is λn, we get λn|r−1. This is possible only when r=1, which contradicts the assumption that congruence (9) does not hold. This means that the necessity of the theorem must be true.
Now, we have a new relationship between an RSA public key and its corresponding private key (congruence (9)). If λn=ϕn holds, then the new relationship makes no sense. By Lemma 4, it is known that for an RSA public modulus n=pq, λn=lcmp−1,q−1≤p−1q−1/2=ϕn/2. This guarantees that λn≠ϕn.
Notice that the congruence (1) is the traditional understanding of the relationship between an RSA public key and a private key. If we take λn as the input to the extended Euclidean algorithm to replace ϕn, then we can get multiple values of d satisfying that d<ϕn. Needless to say, many of those values do not meet congruence (1), but they meet congruence (9) and hence meet congruence (8) instead.


## 4. Counting the RSA Private Keys

The above analysis shows that under the condition that both the RSA public key and the private key are in the range between 0 andϕn, there exist multiple private keys for any given public key. It is interesting to know how many private keys there are corresponding to a public key. We have the following conclusion.Theorem 2.
Given an RSA public modulusn=pq, wherepandqare two different prime numbers. Given a public keyewhich is coprime toϕn, the number of valid private keysd<ϕnthat make the modulo congruencemedmodn=mhold for allm<nisgcdp−1,q−1.Proof.
Letd<λn be the smallest private key. Then, it is easy to verify that for any integer t, d′=d+tλn is also a valid private key, i.e., for any message m<n, the equality med′modn=m holds. This means that the number of choices of the value t is the number of valid private keys. Under the condition that d′<ϕn, it is easy to see that the number of valid private keys is(13)ϕnλn=p−1q−1lcmp−1,q−1,=gcdp−1,q−1.
Sincep−1 and q−1 are both even numbers, there exist at least two valid private keys. If p−1 and q−1 have a large common divisor, then the number of valid private keys can be large. This means that the number of valid private keys of the RSA cryptosystem varies in different cases. This is also a good indication to construct RSA cryptosystems with a large number of valid private keys when such private keys are useful.
It should be pointed out that even ifp−1 and q−1 have a fairly large common divisor that is sufficiently large for practical applications, e.g., the practical possible number of different holders of RSA private keys, the factorization of n=pq still remains hard as long as the common divisor of p−1 and q−1 is not too large. For example, if p and q are 512-bit (about 170 decimal digits) integers, and their common divisor is about a million, which is sufficient for most of the applications. This may reduce the difficulty of factorizing n=pq at most by a factor of 220, and it is still a hard problem that can be practically solved.Example 1.
(A small example)In order to show how it works, letp=7,q=11,e=59. Then,n=pq=77,ϕn=p−1q−1=60. Using the extended Euclidean algorithm, it is easy to compute the private keyd=e−1modϕn=59.
Note thatλ(n)=lcmp−1,q−1=30. Using the extended Euclidean algorithm, it is easy to compute d′=e−1modλn=29. Apparently, ed′modϕn=31≠1. However, it is trivial to verify that xed′modn=x holds for all x<n, which means that d′ is a valid private key.
According to Theorem2, the number of private keys is gcdp−1,q−1=gcd6,10=2; hence, d=59 and d′=29 are the only valid private keys not exceeding ϕn=60.


## 5. How to Choose a Private Key as Small as Possible

Theoretically, the public keye is chosen at random. However, sometimes it requires e to be as small as possible to minimize the computational cost of the encryption process (e.g., siangature verification via a smart card). This would also reduce the computational cost of public key management. In this case, the public key e is normally chosen as a small number. When the public key is fixed, the user has to choose a private key. If the private key is also reasonably small, then encryption or signature creation needs a relatively small amount of computation. When the relation edmodϕn=1 is used to compute a private key d, d may be well close to ϕn. The best case is when e is a factor of ϕn+1. If the relation edmodλn=1 is used instead, d may be much smaller when e is fixed. Following is an example to show that private keys can be smaller than the ones satisfying the equality edmodϕn=1.Example 2.
Let the public modulus ben=pq, where(14)p=3603109844542291969,q=319546020820551643220672513,
are the two largest known prime factors of the Fermat numberF13=28192+1 so far. Then, we have(15)ϕn=1151359413402845823696126917735180482815983616,λn=2196043803029719970123533091993676152832.
Now, lete=123454321. If d is chosen such that edmodϕn=1, then(16)d=346082282519637733667478927540911949872799121,
is the only solution. Ifd′ is chosen such that ed′modλn=1, then(17)d′=1151468775074415800976974352543919545745.
Note thatd is 300557 times larger than d′; hence, the use of d′ is more efficient. The binary representation of d has 148 bits with 75 of 1’s; hence, the computation of mdmodn requires 221 modulo multiplications. The binary representation of d′ has 130 bits with 61 of 1’s. Hence, the computation of md′modn requires 189 modulo multiplications, with 32 less modulo multiplications than the computation of mdmodn.
By Theorem 2, there aregcdp−1,q−1=524288valid private keys, andd′is the smallest one.


## 6. An Application in Many-To-One Privacy-Preserving Encryption

The above statement shows the existence of multiple RSA private keys, which is the one-to-many feature between an RSA public key and private keys. To make use of the multiple private keys, we give an application here.Consider the following scenario: in medical practices, abnormal cases (e.g., when an abnormal symptom is diagnosed) are to be reported to an authorityAUT. This problem has become practically important due to the finding of the COVID-19 pandemic and other new diseases. Usually, before the reported message is processed and verified by the authority, the message should be kept secret to the public, avoiding unnecessary panic among the civilians. Hence, sending the message in ciphertext form would meet the requirement. If symmetric key encryption is used, then the key management is an overhead burden, and the privacy of the message reporter cannot be protected. If public key encryption is used, then it is difficult to reveal the identity of the message sender, which increases the chances of deliberate hoaxes. It is ideal to keep the privacy of message reporters in normal cases, and in some special cases, the identity of the message sender can be revealed by the help of other technical support, e.g., the system management center.With the property of multiple RSA private keys, a privacy-preserving scheme can be established, where the above disadvantages can be overcome.


### 6.1. System Setup

Assume that a management center establishes an RSA cryptosystem withn=pq as the modulus, where the public key e corresponds to multiple private keys d1,d1,…,dk. The management enters, sends e,n to the authority AUT, and sends n,di to the user Ui. Such messages are sent in a secure manner (e.g., offline).In order to assist the userUi to execute the following message encryption scheme, the management center should find some prime factors of di and send the factors to Ui as well. If di do not have odd prime factors or it is difficult to find such factors, then dispose di and choose a different private key as di. Ideally, the odd prime factors of di should be larger than gcdp−1,q−1.It is noted that the system is no longer a public key cryptosystem but a many-to-one encryption scheme.


### 6.2. Message Encryption

When a userUi wants to send a message m to AUT, he does the following:(1)
Find an odd factor ofdi, say t. t does not have to be a prime number, it can be the multiplication of some of the factors of di known to the user;(2)
Computec=mdi/tmodn;(3)
Sendt,c to the authority AUT.When the authorityAUT receives the message t,c, he computes m′=ctemodn. Then, m′=m is the original message.The following theorem confirms the correctness of the decryption.Theorem 3.
For any messagem<n, the computation made byAUTcan recover the original messagem.Proof.
Through the process of message encryption,c=mdi/tmodn. Then, the AUT can get(18)m′=ctemodn,=mdi/ttemodn,=mdiemodn.
Sincee,di is a valid pair of a public key and a private key. By Theorem 1, for any message m<n, the equality medimodn=m must hold.


### 6.3. Properties of the Proposed Scheme

It is easy to verify that the above scheme has the following properties.


#### 6.3.1. Privacy Preserving of the Message Sender

Although the authorityAUT can recover the original message that was encrypted using di/t, from the message t,c, the authority AUT does not know who sent the message. The correct recovery of the message m only tells us that the message sender is one of the key holders. This preserves the privacy of the message sender.However, when the same user sends more messages than the number of prime factors ofdi that Ui knows and when two messages are associated with the same t, with a high probability, it may indicate that the two messages are sent by the same user. This can be treated as a privacy problem; however, it is still too far from getting the real identity of the message sender.


#### 6.3.2. Revealing the Identity of the Message Sender

In case when the identity of the message sender needs to be revealed, the management center needs to do some verification. By checking which user created the message, the identity of the message sender can be revealed. This verification can be done by the management center by simply checking which keydi has the factor t.If there exists another keydj that also has t as a factor, then the management center is unable to tell which key was used to create the message, hence unable to identify the message sender. However, if t is relatively large, particularly when t>gcdp−1,q−1, then the following theorem tells us that the user key di having t as a factor is unique.Theorem 4.
Letn=pqbe the public modulus of an RSA cryptosystem and letd1andd2be valid private keys corresponding to the public keye. Iftis a prime factor ofd1andt>gcdp−1,q−1, thentmust not be a factor ofd2.Proof.
By the proof of Theorem2, it is known that d1−d2=kλn holds for some integer k<gcdp−1,q−1. Assume that t is a common factor of both d1 and d2, then t|d1−d2 must hold, i.e., t|kλn. Since t>gcdp−1,q−1>k, we have that t|λn. Since d1 is a private key corresponding to e, there must exist some integer k1 such that d1e=k1λn+1 holds; hence, we get that t|(d1e−k1λn), which means that t|1, which is a contradiction. This contradiction means that t must not be a factor of d2.
Theorem4 shows that when t>gcdp−1,q−1, it is not possible for two valid private keys to have a common factor t. Although the condition in Theorem 4 is that t>gcdp−1,q−1, from the proof it can be seen that as long as t|k, the conclusion of the theorem still holds.
Letd1 be the smallest private key corresponding to the public key e. By Theorem 2, the other valid private keys corresponding to the same public key e can be represented by di=d1+kiλn, where 1≤ki<gcdp−1,q−1. Combining with the proof of Theorem 4, we get the following conclusion.Corollary 1.
Letn=pq be the public modulus of an RSA cryptosystem, and let the public key be e. If kk≤gcdp−1,q−1 different private keys corresponding to e are used, then no two private keys have a common prime factor larger than k.
The proof of Corollary1 can be similar to that of Theorem 4, except that the k private keys are chosen to be the smallest ones. The condition of Corollary 1 is weaker than that of Theorem 4 because k<gcdp−1,q−1. This means that when a small number of different private keys are used than the total number of private keys, the condition for no two private keys to have a common prime factor is weaker. The cases for small common factors in general are complicated, which are left as an open problem.
The result of Theorem4 means that the identity-revealing process of the proposed protocol works effectively.
What if a userUi chooses t such that it is not a factor of di? If the user Ui can compute mdi/tmodn, then by receiving the message together with t sent to AUT, AUT can decrypt the message m correctly but cannot find who sent the message. However, in the proposed scheme, λn is only known to the management center. This means that it is difficult for the user Ui to compute t−1modλn; hence, it is difficult for the user to create a message in the form mdi/tmodn while the user also knows t.


## 6.1. System Setup

Assume that a management center establishes an RSA cryptosystem withn=pq as the modulus, where the public key e corresponds to multiple private keys d1,d1,…,dk. The management enters, sends e,n to the authority AUT, and sends n,di to the user Ui. Such messages are sent in a secure manner (e.g., offline).In order to assist the userUi to execute the following message encryption scheme, the management center should find some prime factors of di and send the factors to Ui as well. If di do not have odd prime factors or it is difficult to find such factors, then dispose di and choose a different private key as di. Ideally, the odd prime factors of di should be larger than gcdp−1,q−1.It is noted that the system is no longer a public key cryptosystem but a many-to-one encryption scheme.


## 6.2. Message Encryption

When a userUi wants to send a message m to AUT, he does the following:(1)
Find an odd factor ofdi, say t. t does not have to be a prime number, it can be the multiplication of some of the factors of di known to the user;(2)
Computec=mdi/tmodn;(3)
Sendt,c to the authority AUT.When the authorityAUT receives the message t,c, he computes m′=ctemodn. Then, m′=m is the original message.The following theorem confirms the correctness of the decryption.Theorem 3.
For any messagem<n, the computation made byAUTcan recover the original messagem.Proof.
Through the process of message encryption,c=mdi/tmodn. Then, the AUT can get(18)m′=ctemodn,=mdi/ttemodn,=mdiemodn.
Sincee,di is a valid pair of a public key and a private key. By Theorem 1, for any message m<n, the equality medimodn=m must hold.


## 6.3. Properties of the Proposed Scheme

It is easy to verify that the above scheme has the following properties.


### 6.3.1. Privacy Preserving of the Message Sender

Although the authorityAUT can recover the original message that was encrypted using di/t, from the message t,c, the authority AUT does not know who sent the message. The correct recovery of the message m only tells us that the message sender is one of the key holders. This preserves the privacy of the message sender.However, when the same user sends more messages than the number of prime factors ofdi that Ui knows and when two messages are associated with the same t, with a high probability, it may indicate that the two messages are sent by the same user. This can be treated as a privacy problem; however, it is still too far from getting the real identity of the message sender.


### 6.3.2. Revealing the Identity of the Message Sender

In case when the identity of the message sender needs to be revealed, the management center needs to do some verification. By checking which user created the message, the identity of the message sender can be revealed. This verification can be done by the management center by simply checking which keydi has the factor t.If there exists another keydj that also has t as a factor, then the management center is unable to tell which key was used to create the message, hence unable to identify the message sender. However, if t is relatively large, particularly when t>gcdp−1,q−1, then the following theorem tells us that the user key di having t as a factor is unique.Theorem 4.
Letn=pqbe the public modulus of an RSA cryptosystem and letd1andd2be valid private keys corresponding to the public keye. Iftis a prime factor ofd1andt>gcdp−1,q−1, thentmust not be a factor ofd2.Proof.
By the proof of Theorem2, it is known that d1−d2=kλn holds for some integer k<gcdp−1,q−1. Assume that t is a common factor of both d1 and d2, then t|d1−d2 must hold, i.e., t|kλn. Since t>gcdp−1,q−1>k, we have that t|λn. Since d1 is a private key corresponding to e, there must exist some integer k1 such that d1e=k1λn+1 holds; hence, we get that t|(d1e−k1λn), which means that t|1, which is a contradiction. This contradiction means that t must not be a factor of d2.
Theorem4 shows that when t>gcdp−1,q−1, it is not possible for two valid private keys to have a common factor t. Although the condition in Theorem 4 is that t>gcdp−1,q−1, from the proof it can be seen that as long as t|k, the conclusion of the theorem still holds.
Letd1 be the smallest private key corresponding to the public key e. By Theorem 2, the other valid private keys corresponding to the same public key e can be represented by di=d1+kiλn, where 1≤ki<gcdp−1,q−1. Combining with the proof of Theorem 4, we get the following conclusion.Corollary 1.
Letn=pq be the public modulus of an RSA cryptosystem, and let the public key be e. If kk≤gcdp−1,q−1 different private keys corresponding to e are used, then no two private keys have a common prime factor larger than k.
The proof of Corollary1 can be similar to that of Theorem 4, except that the k private keys are chosen to be the smallest ones. The condition of Corollary 1 is weaker than that of Theorem 4 because k<gcdp−1,q−1. This means that when a small number of different private keys are used than the total number of private keys, the condition for no two private keys to have a common prime factor is weaker. The cases for small common factors in general are complicated, which are left as an open problem.
The result of Theorem4 means that the identity-revealing process of the proposed protocol works effectively.
What if a userUi chooses t such that it is not a factor of di? If the user Ui can compute mdi/tmodn, then by receiving the message together with t sent to AUT, AUT can decrypt the message m correctly but cannot find who sent the message. However, in the proposed scheme, λn is only known to the management center. This means that it is difficult for the user Ui to compute t−1modλn; hence, it is difficult for the user to create a message in the form mdi/tmodn while the user also knows t.


## 6.3.1. Privacy Preserving of the Message Sender

Although the authorityAUT can recover the original message that was encrypted using di/t, from the message t,c, the authority AUT does not know who sent the message. The correct recovery of the message m only tells us that the message sender is one of the key holders. This preserves the privacy of the message sender.However, when the same user sends more messages than the number of prime factors ofdi that Ui knows and when two messages are associated with the same t, with a high probability, it may indicate that the two messages are sent by the same user. This can be treated as a privacy problem; however, it is still too far from getting the real identity of the message sender.


## 6.3.2. Revealing the Identity of the Message Sender

In case when the identity of the message sender needs to be revealed, the management center needs to do some verification. By checking which user created the message, the identity of the message sender can be revealed. This verification can be done by the management center by simply checking which keydi has the factor t.If there exists another keydj that also has t as a factor, then the management center is unable to tell which key was used to create the message, hence unable to identify the message sender. However, if t is relatively large, particularly when t>gcdp−1,q−1, then the following theorem tells us that the user key di having t as a factor is unique.Theorem 4.
Letn=pqbe the public modulus of an RSA cryptosystem and letd1andd2be valid private keys corresponding to the public keye. Iftis a prime factor ofd1andt>gcdp−1,q−1, thentmust not be a factor ofd2.Proof.
By the proof of Theorem2, it is known that d1−d2=kλn holds for some integer k<gcdp−1,q−1. Assume that t is a common factor of both d1 and d2, then t|d1−d2 must hold, i.e., t|kλn. Since t>gcdp−1,q−1>k, we have that t|λn. Since d1 is a private key corresponding to e, there must exist some integer k1 such that d1e=k1λn+1 holds; hence, we get that t|(d1e−k1λn), which means that t|1, which is a contradiction. This contradiction means that t must not be a factor of d2.
Theorem4 shows that when t>gcdp−1,q−1, it is not possible for two valid private keys to have a common factor t. Although the condition in Theorem 4 is that t>gcdp−1,q−1, from the proof it can be seen that as long as t|k, the conclusion of the theorem still holds.
Letd1 be the smallest private key corresponding to the public key e. By Theorem 2, the other valid private keys corresponding to the same public key e can be represented by di=d1+kiλn, where 1≤ki<gcdp−1,q−1. Combining with the proof of Theorem 4, we get the following conclusion.Corollary 1.
Letn=pq be the public modulus of an RSA cryptosystem, and let the public key be e. If kk≤gcdp−1,q−1 different private keys corresponding to e are used, then no two private keys have a common prime factor larger than k.
The proof of Corollary1 can be similar to that of Theorem 4, except that the k private keys are chosen to be the smallest ones. The condition of Corollary 1 is weaker than that of Theorem 4 because k<gcdp−1,q−1. This means that when a small number of different private keys are used than the total number of private keys, the condition for no two private keys to have a common prime factor is weaker. The cases for small common factors in general are complicated, which are left as an open problem.
The result of Theorem4 means that the identity-revealing process of the proposed protocol works effectively.
What if a userUi chooses t such that it is not a factor of di? If the user Ui can compute mdi/tmodn, then by receiving the message together with t sent to AUT, AUT can decrypt the message m correctly but cannot find who sent the message. However, in the proposed scheme, λn is only known to the management center. This means that it is difficult for the user Ui to compute t−1modλn; hence, it is difficult for the user to create a message in the form mdi/tmodn while the user also knows t.


## 7. Concluding Remarks

This paper reveals that an RSA public key corresponds to multiple private keys that are all smaller thanϕn, the Euler’s totient function of the modulus n. The exact relation between an RSA public key and a valid private key that is smaller than ϕn is given. Theorem 1 shows that apart from the revealed possible private keys, no other values can work as private keys.As a specific application of the multiple RSA private keys, this paper presents a simple privacy-preserving encryption scheme, enabling many-to-one encryption, which provides properties such as privacy-preserving in encryption and identity-revealing in the case when it is necessary. This application actually turns the RSA system into a privacy-preserving encryption scheme, where no key is made public. Other applications on the property of multiple RSA private keys need to be further studied.In applications where a certain number of private keys are needed corresponding to the same public key, the two prime numbersp and q can be chosen in such a way that gcdp−1,q−1 is large enough to meet the application requirement but not unnecessarily large. On the other hand, if the number of valid private keys should be kept small, then p and q should be chosen in such a way that gcdp−1,q−1 is as small as possible. The best case is that gcdp−1,q−1=2, which means that there are only 2 valid private keys, and one of them is the usual private key computed using ϕn.Nevertheless, the existence of multiple RSA private keys and the relationship between an RSA public key and a private key should be kept in mind when designing RSA-based cryptosystems or schemes.



---

*Source: 4997392-2022-09-14.xml*