How can I share a number with an opponent?

Let's say I have a message (eg: Hello, world!) and I want to encrypt this message using symmetric encryption (AES-256). I am using a list of keys, where I randomly take one as a key (so that each message has a random key). My opponent also has this list of keys, but due to its size it will take too much time to brute-force.

I would like to somehow share either the key, or the index number of the key in the key-list with my opponent, but I have to do it at the same time I am sending the message.

Is there an algorithm or protocol which I can use to handle this scenario?

• Exactly how big do you intend this list of keys to be? You say it will be big enough to take too much time to brute-force, yet this list will always be smaller than the entire AES-256 keyspace, otherwise it would require a prohibitive amount of storage space, and so will be weaker than just using a random key each time that is agreed using an established key-agreement protocol. Rule number one of crypto: do not try to come up with your own crypto scheme. – Sean Burton Apr 5 '18 at 16:20
• Why are you sharing a number with your opponent? Did you intend to instead write that you wanted to share a number with someone else, in the presence of an opponent who has your list of keys? – Cort Ammon Apr 5 '18 at 16:56

Throw away the key lists and generate a fresh key every time you want to transmit a message. Use a key exchange algorithm like for example Diffie-Hellman.

If an enemy can steal your keys they are pretty much useless. You would have to notice the theft and replace all your keys with new ones. Asymmetric encryption like RSA won't help you here because as with symmetric keys the private key could be stolen. There's not much left you can do now, except for a key exchange algorithm. With that you create a new key every time you want to send a message to your friend. Beware that this won't help you against active attackers which can intercept and replace the communication between you two. It also needs direct responses from the other person to create a key, so you can't send him a new message when he's offline.

• It is possible, that someone is able to steal the list, so it is not a secure way of handling key exchange 😄 – Alexandr Romanov Apr 5 '18 at 12:46
• So the keys that you generate would be through a pseudo random generator (one with high entropy). So every time you send a message you create a new random key based on your generator. The other person receiving the message would also need to generate random keys. – Haris Nadeem Apr 6 '18 at 6:51
• For additive security you could add a signature scheme to the protocol. – Haris Nadeem Apr 6 '18 at 6:52
• @HarisNadeem: Sadly that won't work as the OP has said the keys on his computer could get stolen. A signature scheme would have the same problem. – Nova Apr 6 '18 at 9:57

I guess that you could simply use the RSA algorithm (asymmetric encryption).

Add the number of the key to your AES256-encrypted message, encrypt the whole message again with RSA-encryption and send the message.

As far as I know most of the encryptions work (kind of) this way. You exchange a symmetric key by using RSA-encryption (asymmetric) and all further messages will only be encrypted symmetrically to increase the speed of en- & decryption.

EDIT: This is only an example, and you shouldn't use your own (or my) invented ways of cryptography. There are plenty of public standards and very secure ways to manage your problem, so have a look at those too. ;)

• Thank you, Aleksander! I will try to find out how it works and come back later :) – Alexandr Romanov Apr 5 '18 at 11:54
• As long as you use a good padding scheme, it's enough to just encrypt the key number. – Nova Apr 5 '18 at 12:18
• You can (and should) of course then get rid of the list of precomputed keys completely, and just use a new random key for each session, with this key communicated using RSA (or DH as suggested by the other answer). – Sean Burton Apr 5 '18 at 16:17