Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have two questions about OAEP for RSA.

  1. How are the number of bits to pad with 0 chosen? For example, if I'm sending a 255 byte message with RSA-2048 I have 8 unused bits (1 byte). Should I split the remainder bits evenly so I pad with 4 zeroes and my $r$ is 4 random bits, or do I pick the number of bits to pad randomly?

  2. Does it matter if the hash functions $G$ and $H$ are the same (e.g. if both are SHA-256)?

Variables are in reference to the ones in the diagram found in the Wikipedia article “Optimal asymmetric encryption padding”.

Bonus question: What's the proper technique for expanding and shrinking data using hash functions? Could I use the hash as a seed for a secure PRNG and then generate $n$ random bits, or is that wrong?

share|improve this question

1 Answer 1

up vote 2 down vote accepted
  1. First off, the maximum size of a message you can use is determined by the desired length of the padding (in my case, I am using RSA-2048 so I wanted a final padded length of 256 bytes) and the hash function you are using.

    The formula is messageLength = desiredLength - 2 * hashOutputSize - 1 (in my case, I wanted to use SHA-256 so hashOutputSize would be 32 bytes).

    The number of zeroes padded is desiredLength - messageLength - 2 * hashOutputSize - 1. This can be 0 sometimes. There are not always padded zeroes…!

    After reading “PKCS #1: RSA Cryptography Specifications Version 2.0”, I realize that this question isn't important/doesn't make a lot of sense.

  2. Yes. The specification only calls for 1 hash function as a parameter, not two different ones.

  3. Bonus Question

    MGF1 is what I used for generating masks (i.e. "expanding and shrinking data using hash functions").

    And if anyone is reading this in the future and needs more resources to understand OAEP, I translated it to Java code (this is OAEP, not RSA-OAEP). Also, not strictly related to the forum, but if you can program this might make things easier to follow along:

    public class OAEP {
        public static void main(String[] args) throws Exception {
            byte[] myMessage = "I wonder if this will work".getBytes("UTF-8");
            byte[] padded = pad(myMessage, "SHA-256 MGF1", myMessage.length + 32 + 32 + 1);
            StringBuilder sb = new StringBuilder();
            for (byte b : padded) {
                sb.append(String.format("%02X", b));
            }
            System.out.println(sb.toString());
            byte[] unpadded = unpad(padded, "SHA-256 MGF1");
            System.out.println(new String(unpadded, "UTF-8"));
        }
        public static final SecureRandom random = new SecureRandom(); // Uhh you may want to replace this though
        public static byte[] SHA256(byte[] input) throws NoSuchAlgorithmException {
            MessageDigest digest = MessageDigest.getInstance("SHA-256");
            return digest.digest(input);
        }
        public static byte[] MGF1(byte[] seed, int seedOffset, int seedLength, int desiredLength) throws NoSuchAlgorithmException {
            int hLen = 32;
            int offset = 0;
            int i = 0;
            byte[] mask = new byte[desiredLength];
            byte[] temp = new byte[seedLength + 4];
            System.arraycopy(seed, seedOffset, temp, 4, seedLength);
            while (offset < desiredLength) {
                temp[0] = (byte) (i >>> 24);
                temp[1] = (byte) (i >>> 16);
                temp[2] = (byte) (i >>> 8);
                temp[3] = (byte) i;
                int remaining = desiredLength - offset;
                System.arraycopy(SHA256(temp), 0, mask, offset, remaining < hLen ? remaining : hLen);
                offset = offset + hLen;
                i = i + 1;
            }
            return mask;
        }
        public static byte[] unpad(byte[] message, String params) throws Exception {
            String[] tokens = params.split(" ");
            if (tokens.length != 2 || !tokens[0].equals("SHA-256") || !tokens[1].equals("MGF1")) {
                return null;
            }
            int mLen = message.length;
            int hLen = 32;
            if (mLen < (hLen << 1) + 1) {
                return null;
            }
            byte[] copy = new byte[mLen];
            System.arraycopy(message, 0, copy, 0, mLen);
            byte[] seedMask = MGF1(copy, hLen, mLen - hLen, hLen);
            for (int i = 0; i < hLen; i++) {
                copy[i] ^= seedMask[i];
            }
            byte[] paramsHash = SHA256(params.getBytes("UTF-8"));
            byte[] dataBlockMask = MGF1(copy, 0, hLen, mLen - hLen);
            int index = -1;
            for (int i = hLen; i < mLen; i++) {
                copy[i] ^= dataBlockMask[i - hLen];
                if (i < (hLen << 1)) {
                    if (copy[i] != paramsHash[i - hLen]) {
                        return null;
                    }
                } else if (index == -1) {
                    if (copy[i] == 1) {
                        index = i + 1;
                    }
                }
            }
            if (index == -1 || index == mLen) {
                return null;
            }
            byte[] unpadded = new byte[mLen - index];
            System.arraycopy(copy, index, unpadded, 0, mLen - index);
            return unpadded;
        }
        public static byte[] pad(byte[] message, String params, int length) throws Exception {
            String[] tokens = params.split(" ");
            if (tokens.length != 2 || !tokens[0].equals("SHA-256") || !tokens[1].equals("MGF1")) {
                return null;
            }
            int mLen = message.length;
            int hLen = 32;
            if (mLen > length - (hLen << 1) - 1) {
                return null;
            }
            int zeroPad = length - mLen - (hLen << 1) - 1;
            byte[] dataBlock = new byte[length - hLen];
            System.arraycopy(SHA256(params.getBytes("UTF-8")), 0, dataBlock, 0, hLen);
            System.arraycopy(message, 0, dataBlock, hLen + zeroPad + 1, mLen);
            dataBlock[hLen + zeroPad] = 1;
            byte[] seed = new byte[hLen];
            random.nextBytes(seed);
            byte[] dataBlockMask = MGF1(seed, 0, hLen, length - hLen);
            for (int i = 0; i < length - hLen; i++) {
                dataBlock[i] ^= dataBlockMask[i];
            }
            byte[] seedMask = MGF1(dataBlock, 0, length - hLen, hLen);
            for (int i = 0; i < hLen; i++) {
                seed[i] ^= seedMask[i];
            }
            byte[] padded = new byte[length];
            System.arraycopy(seed, 0, padded, 0, hLen);
            System.arraycopy(dataBlock, 0, padded, hLen, length - hLen);
            return padded;
        }
    }
    
share|improve this answer
    
Just as a note, you can use one hash function as two using domain separation. So, if h() is a good hash function You can use G(x)=h(0||x) and H(x)=h(1||x) as independent hashes –  figlesquidge Mar 4 at 15:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.