I modified the package to provide/conflict with python-crypto, and that seems to work. I didn't test upgrade paths, though.
--- a/debian/control 2018-03-06 06:53:25.000000000 +0000 +++ b/debian/control 2018-03-26 00:40:04.081250416 +0000 @@ -13,6 +13,8 @@ Package: python-pycryptodome Architecture: any Depends: ${misc:Depends}, ${python:Depends}, ${shlibs:Depends} +Provides: python-crypto +Conflicts: python-crypto Description: cryptographic Python library (Python 2) PyCryptodome is a self-contained Python package of low-level cryptographic primitives. @@ -50,6 +52,8 @@ Package: python3-pycryptodome Architecture: any Depends: ${misc:Depends}, ${python3:Depends}, ${shlibs:Depends} +Conflicts: python3-crypto +Provides: python3-crypto Description: cryptographic Python library (Python 3) PyCryptodome is a self-contained Python package of low-level cryptographic primitives. --- a/debian/rules 2018-03-06 06:47:40.000000000 +0000 +++ b/debian/rules 2018-03-26 05:28:22.727479150 +0000 @@ -5,14 +5,14 @@ include /usr/share/dpkg/buildflags.mk export PYBUILD_NAME=pycryptodome -export PYBUILD_BEFORE_BUILD=touch .separate_namespace -export PYBUILD_AFTER_INSTALL=rm '{destdir}/{install_dir}/Cryptodome/SelfTest/PublicKey/test_vectors/ECC/gen_ecc_p256.sh' +#export PYBUILD_BEFORE_BUILD=touch .separate_namespace +export PYBUILD_AFTER_INSTALL=rm '{destdir}/{install_dir}/Crypto/SelfTest/PublicKey/test_vectors/ECC/gen_ecc_p256.sh' %: dh $@ --with python2,python3,sphinxdoc --buildsystem=pybuild override_dh_auto_test: PYBUILD_SYSTEM=custom \ - PYBUILD_TEST_ARGS="python{version} -m Cryptodome.SelfTest {build_dir}/" dh_auto_test + PYBUILD_TEST_ARGS="python{version} -m Crypto.SelfTest {build_dir}/" dh_auto_test override_dh_auto_build: export http_proxy=127.0.0.1:9 override_dh_auto_build: export https_proxy=127.0.0.1:9