Долго мучился с PyCrypto, в итоге получилась эта статья и полная реализация следующего протокола:

Этап отправки:

1. Алиса подписывает сообщение своей цифровой подписью и шифрует ее открытым ключом Боба (асимметричным алгоритмом).
2. Алиса генерирует случайный сеансовый ключ и шифрует этим ключом сообщение (с помощью симметричного алгоритма).
3. Сеансовый ключ шифруется открытым ключом Боба (асимметричным алгоритмом).
Алиса посылает Бобу зашифрованное сообщение, подпись и зашифрованный сеансовый ключ.

Этап приёма:

Боб получает зашифрованное сообщение Алисы, подпись и зашифрованный сеансовый ключ.
4. Боб расшифровывает сеансовый ключ своим закрытым ключом.
5. При помощи полученного, таким образом, сеансового ключа Боб расшифровывает зашифрованное сообщение Алисы.
6. Боб расшифровывает и проверяет подпись Алисы.