Generating public/private key pair with limitations on the form of valid keys

Question

I need a way to create public/private key pairs with a special pattern for valid pairs, like for example all valid pairs must start with 3, only much more sophisticated than this example. I'm doing this in order to make it hard for another party to generate valid pairs.

edit I'm trying to use anonymous authentication where users are able to self-generate public/private key pairs based on an initial key. the public key is also used as a pseudonym for the connection to a server. I'm working on a location privacy protocol where I have to authenticate users but they have to remain anonymous. here there is a problem that pseudonyms change often so I can't prevent a dos attack so I thought of this solution to prevent it

Answer 1

Most asymmetric key generation algorithms will go through many attempts to generate valid keys, often because certain keys are considered weak because they fail predefined tests. In your case, you would simply want an additional test to check if they match your special criteria before being considered valid keys.

Programmatically, if you are using a third-party key generation library, you would have to keep calling the generator until it gave you a pair that met your criteria. If you wrote the generator yourself, it would save some effort to be able to just stick in your criteria as part of the algorithm.

In any case, I agree with the other commentators that this may not be a great idea. If you are requiring a certain part of your key to match a predetermined pattern, you are sacrificing some of your security for something that could easily be uncovered and abused by an unfriendly party.

I'm curious how using a public key as a pseudonym offers anonymity. The key is still associated with a specific private key that is associated with a specific client. It sounds like you're trying to filter based on the key/pseudonym, but perhaps that isn't the best idea. Would encrypted signing help?