1
$\begingroup$

we have a service who has a list of public keys got from clients (for example 1000 public keys. not too many)

service gets an encrypted message from one of clients. this message is encryped with a public key and defenitly service has that key.

can service find out which public key is used to encrype that data?

for more information (you can ignore it): service must broadcast data between all the clients (each one has a pair of RSA keys and service has their public keys). clients must send message to each other with no clue for tracking on service.

for example client A wants to send a message to client B. A encrypts the message with Bs public key and sends it to service. service broadcasts the message to all clients. but only one of the clients (it's B) can decrypt the message.

Improve this question
$\endgroup$
2
  • $\begingroup$ What is exact origin of this question? $\endgroup$
    – kelalaka
    Commented May 21, 2021 at 22:09
  • $\begingroup$ @kelalaka I'm trying to develop this service in one of my projects. $\endgroup$
    – reza
    Commented May 21, 2021 at 22:20

1 Answer 1

Reset to default
2
$\begingroup$

Maybe, but this approach depends on the distribution of the public key sizes.

Suppose that cm is the encrypted message, and ni is the modulus for customer i.

  • If cm >= ni, then customer i cannot be the recipient of this particular message.
  • if cm is significantly smaller then ni (16-32 bits or so, depending on how certain you want to be) then it is possible (but unlikely) to have been sent to customer i.

So if there is a variety of key sizes, this may allow you to narrow down the list of possible senders. For example, if customer X has a 4096-bit key and all the others have 3072-bit keys, identifying messages from customer X would be easy.

On the other hand, if everyone has a 3072-bit key, you may be able to narrow the list of senders down some, but you would still have a fairly large list remaining.

One possible countermeasure is to add random high-order padding bits to the message to make the padded message larger than any modulus. In other words, if the largest modulus is (decimal) 1000000, then 1234 might become 9351234, while 12345 might become 7412345. Each recipient can remove high-order bits until the message is smaller than their modulus, then try decrypting the message.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You could also add fixed bits to the RSA modulus if you have control over the generation. $\endgroup$
    – forest
    Commented May 22, 2021 at 0:34
  • $\begingroup$ @forest I am responsible to generate the keys for customers. they'll have same length. so as I understood, keys with equal length will solve this problem? $\endgroup$
    – reza
    Commented May 22, 2021 at 7:14
  • $\begingroup$ Keys with equal lengths won't solve the problem. See crypto.stackexchange.com/a/90035/54184 $\endgroup$
    – forest
    Commented May 22, 2021 at 7:27
  • $\begingroup$ @forest I think I should find another way to make message destinations untrackable by service. for example sending preiodic random fake messages by all clients to confuse the service $\endgroup$
    – reza
    Commented May 22, 2021 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.