A Russian mathematician posed the following puzzle:

Once upon a time the Russian postal system was notoriously corrupt. Any letter, package or box which was open or easily openable would be opened in the sorting office, and anything inside would be removed whether or not it had any value. However, since the pickings were so rich the sorters never bothered to open anything that was locked, even if they suspected it contained valuables.

Now, Boris in Moscow had bought a beautiful gem for his girlfriend, Natasha who lived in St. Petersburg, and he wanted to get it to her as quickly as possible. Neither he nor Natasha could travel to the other's city, so what was he to do? He had a strongbox with a hasp to which a number of padlocks could be attached. If he bought a padlock and key he could put the gem in the box, lock the padlock and send the box through the postal system knowing that it would not be pried open and that it would be delivered to his beloved. But what good would that do? Natasha would not have a key to open the padlock. Boris couldn't send the key separately by letter as it would be opened and the key removed. However, Boris phoned Natasha and between them they hatched a clever scheme by which they could get the precious jewel from Moscow to St. Petersburg in safety despite the corrupt postal system.

How did they do it?