Signing data bigger than allowed RSA Block size?

Question

I've enountered a small problem while implementing a modified version of the Station-to-Station protocol (STS). Say we have two principals A and B, where both of them knows the other's public key:

1. A->B: Ta (DH public value)
2. B->A: Tb, SigB(Tb,Ta,A)
3. A->B: SigA(Ta,Tb,B)

For the second protocol message, I want to encrypt (using my private key) some data using public key encryption (e.g. RSA); and as STS is a key agreement protocol used for establishing a secret key, symmetric encryption such as AES or 3DES cannot be used.

Furthermore, I thought of just hashing the data to some fixed size (using e.g. SHA-1) and then signing it; however that will not work either, since the other party must be able to extract the different parts of the signed message for some later verification check.

In case I was unclear: SigB(Tb,Ta,A) where SigB means signing using private key B, and I must be able to retrieve Ta, Tb and A.

Is there some other way besides chopping up the data into blocks and then signing each such block (ECB, which is vulnerable to crypto analysis)?

Here's the code that generates the DHparamspec.

protected AlgorithmParameterSpec generateParameters() {
    DHParameterSpec spec = null;
    try {
        AlgorithmParameterGenerator apg = AlgorithmParameterGenerator
                .getInstance("DH");
        apg.init(1024);
        AlgorithmParameters algParam = apg.generateParameters();
        spec = (DHParameterSpec)algParam
                .getParameterSpec(DHParameterSpec.class);


    } catch (NoSuchAlgorithmException e) {
        e.printStackTrace();
    } catch (InvalidParameterSpecException e) {
        e.printStackTrace();
    }
    return spec; // something went wrong
}

And the code that generates the DH pair.

kf = KeyFactory.getInstance("DH");
            keyGen = KeyPairGenerator.getInstance("DH", "BC");
            keyGen.initialize(paramSpec);

            keyPair = keyGen.generateKeyPair();

            kAgreement = KeyAgreement.getInstance("DH");
            kAgreement.init(keyPair.getPrivate());

Answer 1

Woah. This is a bit of a mess. Let's go through this a small step at a time.

First off: You should not be designing or implementing your own crypto protocol. Please don't take this personally, but: you aren't qualified. And, even those who are qualified try hard to avoid doing this, because it is so easy to make subtle mistakes. Don't roll your own crypto.

Instead, you should be using TLS. Just use it; it is well-vetted, there are many implementations widely available, and it solves your problem. There's no good reason to implement something else, and every reason to avoid doing so. It has taken many years, and countless person-decades of expert time, to iron out the wrinkles and security problems in TLS. You simply cannot afford to do that for your own protocol and your own code. You shouldn't even try: you should re-use the effort that's already been put into TLS.

Use TLS. Problem solved. Now you can spend your time on something more useful!

---

(To answer the question you actually asked, if you want to sign a long message, the standard method is to hash it first with a collision-resistant hash and sign the hash. Indeed, this technique is already baked into every public-key signature scheme I've ever seen, so you don't actually need to do anything special: they already do the hashing. [I certainly hope you aren't trying to do raw RSA signature without any padding; that's horribly insecure.] I couldn't make any sense of your explanation you can't just use the standard digital signature algorithms; I suspect you may have confused yourself or gotten yourself twisted in knots or something. But in any case, this is all irrelevant: you should not be designing or implementing crypto at this level of abstraction. The best way to answer your question is to un-ask the question and point you in a different direction.)

Answer 2

Raw RSA is not a signature scheme. It is only a component of a signature scheme. Actual signature or encryption schemes based on RSA also include padding: instead of applying the raw RSA operation (m ↦ m^d mod n or m ↦ m^e mod n) to the message, it is applied to the concatenation of some padding text and the message. This padding has two main roles:

• It ensures that the RSA operation is not applied to a number that is too small. This prevents a number of mathematical relations from breaking the security of the use of RSA, the simplest being that if you compute m^e mod n with both m and e small, no modulo reduction actually takes place.
• It ensures that the RSA operation is never applied twice to the same message. For encryption, this prevents an attacker from breaking the message by brute force (trying every possible plaintext). For signatures, this prevents a number of mathematical relations from arising when related messages are signed.

For more in-depth information about the role of padding, see Is RSA of a random nonce with no padding safe? Does RSA padding have to be unpredictable if the payload is? Is RSA padding needed for single recipient, one-time, unique random message?

There are two common padding schemes for RSA signatures: RSA-PSS and RSA-PKCS1.5. Both are defined by the PKCS #1 document which defines RSA. I will not explain them here, read the PKCS #1 document for their definition. Both methods require that the message be first hashed with a cryptographic digest function such as SHA-256 or SHA-512 (or their predecessor SHA-1). Thus an actual RSA signature of an arbitrary¹ message looks like this:

RSA(key, message) = RSA_operation(key, padding ++ hash(message))

The hash compresses the relevant information about the message (namely, whether a purported message is equal to the genuine message) into a bounded size. When doing encryption, such compression is not possible. To encrypt arbitrary-sized data with RSA, the usual method is to generate a random secret key (often called a session key), encrypt the actual message with that key and send the secret key encrypted with RSA. See How can I use asymmetric encryption, such as RSA, to encrypt an arbitrary length of plaintext?

¹ _{Technically, there are limits, but you won't run into them in practice: SHA-1 and SHA-256 can run up to 2⁶¹-1 bytes, SHA-512 up to 2¹²⁵-1 bytes.}