def _fromString_BLOB(Class, blob):
        """
        Return a public key object corresponding to this public key blob.
        The format of a RSA public key blob is::
            string 'ssh-rsa'
            integer e
            integer n

        The format of a DSA public key blob is::
            string 'ssh-dss'
            integer p
            integer q
            integer g
            integer y

        @type blob: C{str}
        @return: a C{Crypto.PublicKey.pubkey.pubkey} object
        @raises BadKeyError: if the key type (the first string) is unknown.
        """
        keyType, rest = common.getNS(blob)
        if keyType == 'ssh-rsa':
            e, n, rest = common.getMP(rest, 2)
            return Class(RSA.construct((n, e)))
        elif keyType == 'ssh-dss':
            p, q, g, y, rest = common.getMP(rest, 4)
            return Class(DSA.construct((y, g, p, q)))
        else:
            raise BadKeyError('unknown blob type: %s' % keyType)

    def verify(self, signature, data):
        """
        Returns true if the signature for data is valid for this Key.

        @type signature: C{str}
        @type data: C{str}
        @rtype: C{bool}
        """
        if len(signature) == 40:
            # DSA key with no padding
            signatureType, signature = 'ssh-dss', common.NS(signature)
        else:
            signatureType, signature = common.getNS(signature)
        if signatureType != self.sshType():
            return False
        if self.type() == 'RSA':
            numbers = common.getMP(signature)
            digest = pkcs1Digest(data, self.keyObject.size() / 8)
        elif self.type() == 'DSA':
            signature = common.getNS(signature)[0]
            numbers = [
                Util.number.bytes_to_long(n) for n in
                    (signature[:20], signature[20:])
                ]
            digest = sha1(data).digest()
        return self.keyObject.verify(digest, numbers)

    def _fromString_PRIVATE_LSH(Class, data):
        """
        Return a private key corresponding to this LSH private key string.
        The LSH private key string format is::
            <s-expression: ('private-key', (<key type>, (<name>, <value>)+))>

        The names for a RSA (key type 'rsa-pkcs1-sha1') key are: n, e, d, p, q.
        The names for a DSA (key type 'dsa') key are: y, g, p, q, x.

        @type data: C{str}
        @return: a {Crypto.PublicKey.pubkey.pubkey} object
        @raises BadKeyError: if the key type is unknown
        """
        sexp = sexpy.parse(data)
        assert sexp[0] == 'private-key'
        kd = {}
        for name, data in sexp[1][1:]:
            kd[name] = common.getMP(common.NS(data))[0]
        if sexp[1][0] == 'dsa':
            assert len(kd) == 5, len(kd)
            return Class(DSA.construct((kd['y'], kd['g'], kd['p'],
                kd['q'], kd['x'])))
        elif sexp[1][0] == 'rsa-pkcs1':
            assert len(kd) == 8, len(kd)
            if kd['p'] > kd['q']: # make p smaller than q
                kd['p'], kd['q'] = kd['q'], kd['p']
            return Class(RSA.construct((kd['n'], kd['e'], kd['d'],
                kd['p'], kd['q'])))
        else:
            raise BadKeyError('unknown lsh key type %s' % sexp[1][0])

    def _guessStringType(cls, data):
        """
        Guess the type of key in data.  The types map to _fromString_*
        methods.

        @type data: L{bytes}
        @param data: The key data.
        """
        if data.startswith(b'ssh-'):
            return 'public_openssh'
        elif data.startswith(b'-----BEGIN'):
            return 'private_openssh'
        elif data.startswith(b'{'):
            return 'public_lsh'
        elif data.startswith(b'('):
            return 'private_lsh'
        elif data.startswith(b'\x00\x00\x00\x07ssh-'):
            ignored, rest = common.getNS(data)
            count = 0
            while rest:
                count += 1
                ignored, rest = common.getMP(rest)
            if count > 4:
                return 'agentv3'
            else:
                return 'blob'

    def _fromString_PRIVATE_LSH(cls, data):
        """
        Return a private key corresponding to this LSH private key string.
        The LSH private key string format is::
            <s-expression: ('private-key', (<key type>, (<name>, <value>)+))>

        The names for a RSA (key type 'rsa-pkcs1-sha1') key are: n, e, d, p, q.
        The names for a DSA (key type 'dsa') key are: y, g, p, q, x.

        @type data: L{bytes}
        @param data: The key data.

        @return: A new key.
        @rtype: L{twisted.conch.ssh.keys.Key}
        @raises BadKeyError: if the key type is unknown
        """
        sexp = sexpy.parse(data)
        assert sexp[0] == b'private-key'
        kd = {}
        for name, data in sexp[1][1:]:
            kd[name] = common.getMP(common.NS(data))[0]
        if sexp[1][0] == b'dsa':
            assert len(kd) == 5, len(kd)
            return cls._fromDSAComponents(
                y=kd[b'y'], g=kd[b'g'], p=kd[b'p'], q=kd[b'q'], x=kd[b'x'])
        elif sexp[1][0] == b'rsa-pkcs1':
            assert len(kd) == 8, len(kd)
            if kd[b'p'] > kd[b'q']:  # Make p smaller than q
                kd[b'p'], kd[b'q'] = kd[b'q'], kd[b'p']
            return cls._fromRSAComponents(
                n=kd[b'n'], e=kd[b'e'], d=kd[b'd'], p=kd[b'p'], q=kd[b'q'])

        else:
            raise BadKeyError('unknown lsh key type %s' % (sexp[1][0],))

    def _fromString_PUBLIC_LSH(cls, data):
        """
        Return a public key corresponding to this LSH public key string.
        The LSH public key string format is::
            <s-expression: ('public-key', (<key type>, (<name, <value>)+))>

        The names for a RSA (key type 'rsa-pkcs1-sha1') key are: n, e.
        The names for a DSA (key type 'dsa') key are: y, g, p, q.

        @type data: L{bytes}
        @param data: The key data.

        @return: A new key.
        @rtype: L{twisted.conch.ssh.keys.Key}
        @raises BadKeyError: if the key type is unknown
        """
        sexp = sexpy.parse(base64.decodestring(data[1:-1]))
        assert sexp[0] == b'public-key'
        kd = {}
        for name, data in sexp[1][1:]:
            kd[name] = common.getMP(common.NS(data))[0]
        if sexp[1][0] == b'dsa':
            return cls._fromDSAComponents(
                y=kd[b'y'], g=kd[b'g'], p=kd[b'p'], q=kd[b'q'])

        elif sexp[1][0] == b'rsa-pkcs1-sha1':
            return cls._fromRSAComponents(n=kd[b'n'], e=kd[b'e'])
        else:
            raise BadKeyError('unknown lsh key type %s' % (sexp[1][0],))

    def ssh_KEX_DH_GEX_REQUEST_OLD(self, packet):
        """
        This represents two different key exchange methods that share the
        same integer value.

        KEXDH_INIT (for diffie-hellman-group1-sha1 exchanges) payload::

                integer e (the client's Diffie-Hellman public key)

            We send the KEXDH_REPLY with our host key and signature.

        KEX_DH_GEX_REQUEST_OLD (for diffie-hellman-group-exchange-sha1)
        payload::

                integer ideal (ideal size for the Diffie-Hellman prime)

            We send the KEX_DH_GEX_GROUP message with the group that is
            closest in size to ideal.

        If we were told to ignore the next key exchange packet by
        ssh_KEXINIT, drop it on the floor and return.
        """
        if self.ignoreNextPacket:
            self.ignoreNextPacket = 0
            return
        if self.kexAlg == 'diffie-hellman-group1-sha1':
            # this is really KEXDH_INIT
            clientDHpublicKey, foo = getMP(packet)
            y = Util.number.getRandomNumber(512, randbytes.secureRandom)
            serverDHpublicKey = _MPpow(DH_GENERATOR, y, DH_PRIME)
            sharedSecret = _MPpow(clientDHpublicKey, y, DH_PRIME)
            h = sha.new()
            h.update(NS(self.otherVersionString))
            h.update(NS(self.ourVersionString))
            h.update(NS(self.otherKexInitPayload))
            h.update(NS(self.ourKexInitPayload))
            h.update(NS(self.factory.publicKeys[self.keyAlg].blob()))
            h.update(MP(clientDHpublicKey))
            h.update(serverDHpublicKey)
            h.update(sharedSecret)
            exchangeHash = h.digest()
            self.sendPacket(
                MSG_KEXDH_REPLY,
                NS(self.factory.publicKeys[self.keyAlg].blob()) +
                serverDHpublicKey +
                NS(self.factory.privateKeys[self.keyAlg].sign(exchangeHash)))
            self._keySetup(sharedSecret, exchangeHash)
        elif self.kexAlg == 'diffie-hellman-group-exchange-sha1':
            self.dhGexRequest = packet
            ideal = struct.unpack('>L', packet)[0]
            self.g, self.p = self.factory.getDHPrime(ideal)
            self.sendPacket(MSG_KEX_DH_GEX_GROUP, MP(self.p) + MP(self.g))
        else:
            raise error.ConchError('bad kexalg: %s' % self.kexAlg)

    def _fromString_BLOB(cls, blob):
        """
        Return a public key object corresponding to this public key blob.
        The format of a RSA public key blob is::
            string 'ssh-rsa'
            integer e
            integer n

        The format of a DSA public key blob is::
            string 'ssh-dss'
            integer p
            integer q
            integer g
            integer y

        @type blob: L{bytes}
        @param blob: The key data.

        @return: A new key.
        @rtype: L{twisted.conch.ssh.keys.Key}
        @raises BadKeyError: if the key type (the first string) is unknown.
        """
        keyType, rest = common.getNS(blob)
        if keyType == b'ssh-rsa':
            e, n, rest = common.getMP(rest, 2)
            return cls(
                rsa.RSAPublicNumbers(e, n).public_key(default_backend()))
        elif keyType == b'ssh-dss':
            p, q, g, y, rest = common.getMP(rest, 4)
            return cls(
                dsa.DSAPublicNumbers(
                    y=y,
                    parameter_numbers=dsa.DSAParameterNumbers(
                        p=p,
                        q=q,
                        g=g
                    )
                ).public_key(default_backend())
            )
        else:
            raise BadKeyError('unknown blob type: %s' % (keyType,))

    def ssh_KEX_DH_GEX_GROUP(self, packet):
        """
        This handles two different message which share an integer value.
        If the key exchange is diffie-hellman-group1-sha1, this is
        MSG_KEXDH_REPLY.  Payload::
            string serverHostKey
            integer f (server Diffie-Hellman public key)
            string signature

        We verify the host key by calling verifyHostKey, then continue in
        _continueKEXDH_REPLY.

        If the key exchange is diffie-hellman-group-exchange-sha1, this is
        MSG_KEX_DH_GEX_GROUP.  Payload::
            string g (group generator)
            string p (group prime)

        We generate a Diffie-Hellman public key and send it in a
        MSG_KEX_DH_GEX_INIT message.
        """
        if self.kexAlg == 'diffie-hellman-group1-sha1':
            # actually MSG_KEXDH_REPLY
            pubKey, packet = getNS(packet)
            f, packet = getMP(packet)
            signature, packet = getNS(packet)
            fingerprint = ':'.join([ch.encode('hex') for ch in
                                    md5.new(pubKey).digest()])
            d = self.verifyHostKey(pubKey, fingerprint)
            d.addCallback(self._continueKEXDH_REPLY, pubKey, f, signature)
            d.addErrback(
                lambda unused: self.sendDisconnect(
                    DISCONNECT_HOST_KEY_NOT_VERIFIABLE, 'bad host key'))
            return d
        else:
            self.p, rest = getMP(packet)
            self.g, rest = getMP(rest)
            self.x = Util.number.getRandomNumber(320, randbytes.secureRandom)
            self.e = _MPpow(self.g, self.x, self.p)
            self.sendPacket(MSG_KEX_DH_GEX_INIT, self.e)

    def _fromString_PRIVATE_BLOB(cls, blob):
        """
        Return a private key object corresponding to this private key blob.
        The blob formats are as follows:

        RSA keys::
            string 'ssh-rsa'
            integer n
            integer e
            integer d
            integer u
            integer p
            integer q

        DSA keys::
            string 'ssh-dss'
            integer p
            integer q
            integer g
            integer y
            integer x

        @type blob: L{bytes}
        @param blob: The key data.

        @return: A new key.
        @rtype: L{twisted.conch.ssh.keys.Key}
        @raises BadKeyError: if the key type (the first string) is unknown.
        """
        keyType, rest = common.getNS(blob)

        if keyType == b'ssh-rsa':
            n, e, d, u, p, q, rest = common.getMP(rest, 6)
            return cls._fromRSAComponents(n=n, e=e, d=d, p=p, q=q)
        elif keyType == b'ssh-dss':
            p, q, g, y, x, rest = common.getMP(rest, 5)
            return cls._fromDSAComponents(y=y, g=g, p=p, q=q, x=x)
        else:
            raise BadKeyError('unknown blob type: %s' % (keyType,))

    def _fromString_PRIVATE_BLOB(Class, blob):
        """
        Return a private key object corresponding to this private key blob.
        The blob formats are as follows:

        RSA keys::
            string 'ssh-rsa'
            integer n
            integer e
            integer d
            integer u
            integer p
            integer q

        DSA keys::
            string 'ssh-dss'
            integer p
            integer q
            integer g
            integer y
            integer x

        @type blob: C{str}
        @return: a C{Crypto.PublicKey.pubkey.pubkey} object
        @raises BadKeyError: if the key type (the first string) is unknown.
        """
        keyType, rest = common.getNS(blob)

        if keyType == 'ssh-rsa':
            n, e, d, u, p, q, rest = common.getMP(rest, 6)
            rsakey = Class(RSA.construct((n, e, d, p, q, u)))
            return rsakey
        elif keyType == 'ssh-dss':
            p, q, g, y, x, rest = common.getMP(rest, 5)
            dsakey = Class(DSA.construct((y, g, p, q, x)))
            return dsakey
        else:
            raise BadKeyError('unknown blob type: %s' % keyType)

 def __init__(self, initialVector, blockSize):
     """
     @type initialVector: C{str}
     @param initialVector: A byte string representing the initial counter
                           value.
     @type blockSize: C{int}
     @param blockSize: The length of the output buffer, as well as the
     number of bytes at the beginning of C{initialVector} to consider.
     """
     initialVector = initialVector[:blockSize]
     self.count = getMP('\xff\xff\xff\xff' + initialVector)[0]
     self.blockSize = blockSize
     self.count = Util.number.long_to_bytes(self.count - 1)
     self.count = '\x00' * (self.blockSize - len(self.count)) + self.count
     self.count = array.array('c', self.count)
     self.len = len(self.count) - 1

    def ssh_KEX_DH_GEX_REPLY(self, packet):
        """
        Called when we receieve a MSG_KEX_DH_GEX_REPLY message.  Payload::
            string server host key
            integer f (server DH public key)

        We verify the host key by calling verifyHostKey, then continue in
        _continueGEX_REPLY.
        """
        pubKey, packet = getNS(packet)
        f, packet = getMP(packet)
        signature, packet = getNS(packet)
        fingerprint = ':'.join(map(lambda c: '%02x'%ord(c),
            md5.new(pubKey).digest()))
        d = self.verifyHostKey(pubKey, fingerprint)
        d.addCallback(self._continueGEX_REPLY, pubKey, f, signature)
        d.addErrback(
            lambda unused: self.sendDisconnect(
                DISCONNECT_HOST_KEY_NOT_VERIFIABLE, 'bad host key'))
        return d

    def ssh_KEX_DH_GEX_INIT(self, packet):
        """
        Called when we get a MSG_KEX_DH_GEX_INIT message.  Payload::
            integer e (client DH public key)

        We send the MSG_KEX_DH_GEX_REPLY message with our host key and
        signature.
        """
        clientDHpublicKey, foo = getMP(packet)
        # TODO: we should also look at the value they send to us and reject
        # insecure values of f (if g==2 and f has a single '1' bit while the
        # rest are '0's, then they must have used a small y also).

        # TODO: This could be computed when self.p is set up
        #  or do as openssh does and scan f for a single '1' bit instead

        pSize = Util.number.size(self.p)
        y = Util.number.getRandomNumber(pSize, randbytes.secureRandom)

        serverDHpublicKey = _MPpow(self.g, y, self.p)
        sharedSecret = _MPpow(clientDHpublicKey, y, self.p)
        h = sha.new()
        h.update(NS(self.otherVersionString))
        h.update(NS(self.ourVersionString))
        h.update(NS(self.otherKexInitPayload))
        h.update(NS(self.ourKexInitPayload))
        h.update(NS(self.factory.publicKeys[self.keyAlg].blob()))
        h.update(self.dhGexRequest)
        h.update(MP(self.p))
        h.update(MP(self.g))
        h.update(MP(clientDHpublicKey))
        h.update(serverDHpublicKey)
        h.update(sharedSecret)
        exchangeHash = h.digest()
        self.sendPacket(
            MSG_KEX_DH_GEX_REPLY,
            NS(self.factory.publicKeys[self.keyAlg].blob()) +
            serverDHpublicKey +
            NS(self.factory.privateKeys[self.keyAlg].sign(exchangeHash)))
        self._keySetup(sharedSecret, exchangeHash)

    def agentc_ADD_IDENTITY(self, data):
        """
        Adds a private key to the agent's collection of identities.  On
        subsequent interactions, the private key can be accessed using only the
        corresponding public key.
        """

        # need to pre-read the key data so we can get past it to the comment string
        keyType, rest = getNS(data)
        if keyType == 'ssh-rsa':
            nmp = 6
        elif keyType == 'ssh-dss':
            nmp = 5
        else:
            raise keys.BadKeyError('unknown blob type: %s' % keyType)

        rest = getMP(rest, nmp)[-1] # ignore the key data for now, we just want the comment
        comment, rest = getNS(rest) # the comment, tacked onto the end of the key blob

        k = keys.Key.fromString(data, type='private_blob') # not wrapped in NS here
        self.factory.keys[k.blob()] = (k, comment)
        self.sendResponse(AGENT_SUCCESS, '')

    def _fromString_PUBLIC_LSH(Class, data):
        """
        Return a public key corresponding to this LSH public key string.
        The LSH public key string format is::
            <s-expression: ('public-key', (<key type>, (<name, <value>)+))>

        The names for a RSA (key type 'rsa-pkcs1-sha1') key are: n, e.
        The names for a DSA (key type 'dsa') key are: y, g, p, q.

        @type data: C{str}
        @return: a C{Crypto.PublicKey.pubkey.pubkey} object
        @raises BadKeyError: if the key type is unknown
        """
        sexp = sexpy.parse(base64.decodestring(data[1:-1]))
        assert sexp[0] == 'public-key'
        kd = {}
        for name, data in sexp[1][1:]:
            kd[name] = common.getMP(common.NS(data))[0]
        if sexp[1][0] == 'dsa':
            return Class(DSA.construct((kd['y'], kd['g'], kd['p'], kd['q'])))
        elif sexp[1][0] == 'rsa-pkcs1-sha1':
            return Class(RSA.construct((kd['n'], kd['e'])))
        else:
            raise BadKeyError('unknown lsh key type %s' % sexp[1][0])

    def _fromString_AGENTV3(Class, data):
        """
        Return a private key object corresponsing to the Secure Shell Key
        Agent v3 format.

        The SSH Key Agent v3 format for a RSA key is::
            string 'ssh-rsa'
            integer e
            integer d
            integer n
            integer u
            integer p
            integer q

        The SSH Key Agent v3 format for a DSA key is::
            string 'ssh-dss'
            integer p
            integer q
            integer g
            integer y
            integer x

        @type data: C{str}
        @return: a C{Crypto.PublicKey.pubkey.pubkey} object
        @raises BadKeyError: if the key type (the first string) is unknown
        """
        keyType, data = common.getNS(data)
        if keyType == 'ssh-dss':
            p, data = common.getMP(data)
            q, data = common.getMP(data)
            g, data = common.getMP(data)
            y, data = common.getMP(data)
            x, data = common.getMP(data)
            return Class(DSA.construct((y,g,p,q,x)))
        elif keyType == 'ssh-rsa':
            e, data = common.getMP(data)
            d, data = common.getMP(data)
            n, data = common.getMP(data)
            u, data = common.getMP(data)
            p, data = common.getMP(data)
            q, data = common.getMP(data)
            return Class(RSA.construct((n,e,d,p,q,u)))
        else:
            raise BadKeyError("unknown key type %s" % keyType)

    def _fromString_AGENTV3(cls, data):
        """
        Return a private key object corresponsing to the Secure Shell Key
        Agent v3 format.

        The SSH Key Agent v3 format for a RSA key is::
            string 'ssh-rsa'
            integer e
            integer d
            integer n
            integer u
            integer p
            integer q

        The SSH Key Agent v3 format for a DSA key is::
            string 'ssh-dss'
            integer p
            integer q
            integer g
            integer y
            integer x

        @type data: L{bytes}
        @param data: The key data.

        @return: A new key.
        @rtype: L{twisted.conch.ssh.keys.Key}
        @raises BadKeyError: if the key type (the first string) is unknown
        """
        keyType, data = common.getNS(data)
        if keyType == b'ssh-dss':
            p, data = common.getMP(data)
            q, data = common.getMP(data)
            g, data = common.getMP(data)
            y, data = common.getMP(data)
            x, data = common.getMP(data)
            return cls._fromDSAComponents(y=y, g=g, p=p, q=q, x=x)
        elif keyType == b'ssh-rsa':
            e, data = common.getMP(data)
            d, data = common.getMP(data)
            n, data = common.getMP(data)
            u, data = common.getMP(data)
            p, data = common.getMP(data)
            q, data = common.getMP(data)
            return cls._fromRSAComponents(n=n, e=e, d=d, p=p, q=q, u=u)
        else:
            raise BadKeyError("unknown key type %s" % (keyType,))