dev-python/pycrypto-2.0.1-r6 is not enough for dev-python/paramiko-1.7.6: >>> import paramiko Traceback (most recent call last): File "<stdin>", line 1, in <module> File "/usr/lib/python2.6/site-packages/paramiko/__init__.py", line 69, in <module> from transport import randpool, SecurityOptions, Transport File "/usr/lib/python2.6/site-packages/paramiko/transport.py", line 32, in <module> from paramiko import util File "/usr/lib/python2.6/site-packages/paramiko/util.py", line 32, in <module> from paramiko.common import * File "/usr/lib/python2.6/site-packages/paramiko/common.py", line 98, in <module> from rng import StrongLockingRandomPool File "/usr/lib/python2.6/site-packages/paramiko/rng.py", line 23, in <module> from Crypto.Util.randpool import RandomPool as _RandomPool ImportError: No module named Crypto.Util.randpool Updating pycrypto to dev-python/pycrypto-2.1.0_beta1 fixes the issue (albeit with a warning): >>> import paramiko /usr/lib/python2.6/site-packages/Crypto/Util/randpool.py:40: RandomPool_DeprecationWarning: This application uses RandomPool, which is BROKEN in older releases. See http://www.pycrypto.org/randpool-broken RandomPool_DeprecationWarning)
dev-python/pycrypto-2.0.1* actually had Crypto.Util.randpool module. Your dev-python/pycrypto might had been installed for another version of Python. README of dev-python/paramiko-1.7.6 contains: Requirements ------------ - python 2.3 <http://www.python.org/> (python 2.2 is also supported, but not recommended) - pycrypto 1.9+ <http://www.amk.ca/python/code/crypto.html> (2.0 works too)