Why is this Java RSA decryption not working?

Question

So this was part of an assignment I was working (though I already had to turn it in unsolved) based on this challenge at http://www.loyalty.org/~schoen/rsa/.

In summary, the challenge provides a list of files contain cipher and an associated public key. Using the fact that RSA public keys often repeat primes, we are expected to find as many of the private keys from the 100 as possible and decrypt the associated message. Although I think forming the private key was straightforward (and believe I am doing it correctly), but I get error "javax.crypto.BadPaddingException: Message is larger than modulus". Can someone tell me what I am doing wrong? I'm including my code along with 2 of the bin and cipher files as an example.

My Code:

package decryptrsa;

import com.sun.org.apache.xml.internal.security.utils.Base64;
import java.io.File;

import java.util.Scanner;
import java.security.spec.X509EncodedKeySpec;
import java.security.spec.RSAPrivateKeySpec;
import java.security.KeyFactory;
import java.security.interfaces.*;
import java.math.BigInteger;
import java.util.ArrayList;
import javax.crypto.Cipher;
import java.io.FileInputStream;
import java.io.FileOutputStream;


/**
 *
 * @author qscot
 */
public class DecryptRSA {

    static ArrayList<BigInteger> publicKeys = new ArrayList<BigInteger>();

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        // TODO code application logic here
        ReadPublicKeys();
        crackPrivateKeys();

    }

    static void ReadPublicKeys() throws Exception {
        String publicKey;

        for (int i = 1; i <= 100; i++) {
            publicKey = "";
            Scanner scanner = new Scanner(new File("C:\\Users\\qscot\\Downloads\\challenge\\" + i + ".pem"));
            scanner.nextLine();
            String lineString = scanner.nextLine();
            do {
                publicKey += lineString;
                lineString = scanner.nextLine();
            } while (lineString.contains("END PUBLIC KEY") == false);
            scanner.close();

            byte[] decoded = Base64.decode(publicKey.getBytes());
            X509EncodedKeySpec spec = new X509EncodedKeySpec(decoded);
            KeyFactory kf = KeyFactory.getInstance("RSA");

            RSAPublicKey pk = (RSAPublicKey) kf.generatePublic(spec);
            BigInteger modulus = pk.getModulus();

            publicKeys.add(modulus);
        }

    }

    static void crackPrivateKeys() throws Exception {

        BigInteger gcd;
        BigInteger q1;
        BigInteger q2;
        for (int i = 0; i < 100; i++) {
            for (int z = 0; z < 100; z++) {
                if (i != z) {
                    gcd = (gcd(publicKeys.get(i), publicKeys.get(z)));

                    if (!gcd.equals(BigInteger.ONE)) {
                        q1 = publicKeys.get(i).divide(gcd);
                        q2 = publicKeys.get(z).divide(gcd);
                        RSAPrivateKey key1 = getKey(gcd, q1);
                        RSAPrivateKey key2 = getKey(gcd, q2);


                        writeDecryptedFile(i, key1);
                        writeDecryptedFile(z, key2);

                    }
                }
            }
        }

    }

    static void writeDecryptedFile(int fileNo, RSAPrivateKey privKey) throws Exception {
        Cipher cipher = Cipher.getInstance("RSA/ECB/NoPadding");

        File file = new File("C:\\Users\\qscot\\Downloads\\challenge\\" + fileNo + ".bin");

        FileInputStream fis = new FileInputStream(file);
        byte[] fbytes = new byte[(int) file.length()];
        fis.read(fbytes);
        fis.close();
        cipher.init(Cipher.DECRYPT_MODE, privKey);
        byte[] oBytes = cipher.doFinal(fbytes);
        FileOutputStream fos = new FileOutputStream("C:\\Users\\qscot\\Downloads\\challenge\\" + fileNo + "-OUTPUT.txt");
        fos.write(oBytes);
        fos.flush();
        fos.close();

    }

    static BigInteger gcd(BigInteger num1, BigInteger num2) {

        while (!num1.equals(BigInteger.ONE) && !num1.equals(BigInteger.ZERO) && !num2.equals(BigInteger.ONE) && !num2.equals(BigInteger.ZERO)) {
            if (num1.compareTo(num2) == 1) {
                num1 = num1.mod(num2);

            } else {
                num2 = num2.mod(num1);

            }
        }

        if (num1.equals(BigInteger.ONE) || num2.equals(BigInteger.ONE)) {
            return BigInteger.valueOf(1);

        } else {
            if (num1.equals(BigInteger.ZERO)) {
                return num2;
            } else {
                return num1;
            }

        }
    }

    static RSAPrivateKey getKey(BigInteger p, BigInteger q) throws Exception {
        KeyFactory kf = KeyFactory.getInstance("RSA");
        BigInteger t, d, e;
        e = BigInteger.valueOf(65537);
        t = (p.subtract(BigInteger.ONE)).multiply((q.subtract(BigInteger.ONE)));
        d = e.modInverse(t);
        RSAPrivateKeySpec keyspec = new RSAPrivateKeySpec(d, e);
        return (RSAPrivateKey) kf.generatePrivate(keyspec);

    }

}

6.pem file:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDn5BqEUDrlhvwXQ68MqZ001B74
fGD1w2Le++wILzEX7Ba8LeJVeuwpOxxdxDQ7280yc0SKPiChWpb3bE1/G/hV5e++
95qfhbe+SP7MRL39TxEotADaqyHY6SfloDk5A9NiIzgebWmtFriamBfhrxzx8G3K
6NWAAjDAIMx+xjLn6QIDAQAB
-----END PUBLIC KEY-----

6.bin File:

xƒâTD§¼çÄ   ؈ßPã…Ôä3x4b2Ð#•—æ¨
U«õ`Êzÿúw"Ü°™è0ÄÕ~³•—˜§FºqŠ„hÏŒÞõ&د³Ô<*pàbGÃGìMÿö¶3Ùù­¸²Z•a¯®éDNïæÝjn¢¯tå!WÐ

6-OUTPUT.txt:

8.pem File:

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC1fGe+mMJYZ+BDm76Ag25bXcBB
pABkGZpnQpnSTocEuCQyp5/lNNVFdF0QliNRULnxoK+pD8VEBqxR+zkYsYf9iGzU
PzOELWvbFgIJdUPixlaD3/1Y6+eSDffCOsCoJ1A/8DELMbjQdbFoxfqj9AVRU3cd
R0AauL4O9hPz0N9OVQIDAQAB
-----END PUBLIC KEY-----

8.bin File:

¤”»BÃ."
îÂT.<(bø×]¥”£Ó¯!›==±Ñ·;ª%7¿ðU@xÀÉ5ç£
‡*h\w¸¸@¦aܳj Ù~t´õêæSü®Î ŒQU¼L-â-äK}\-žù‹ý«>DÕ£ñ”Õe6Œ"
G®lI

Answer 1

The line RSAPrivateKeySpec keyspec = new RSAPrivateKeySpec(d, e); contains a bug. The arguments to RSAPrivateKeySpec should be, in order, the modulus and the decrypt exponent. According the documentation in the link you provided the padding used is PKCS1PADDING. Therefore you should obtain a Cipher instance using Cipher.getInstance("RSA/ECB/PKCS1PADDING");

There is also an off-by-1 bug in your writeDecryptedFile method. The files are named 1.bin ... 100.bin, but your keys are indexed from 0 through 99. Thus you need to be accessing (fileNo + 1) + ".bin" rather than fileNo + ".bin"

There is no reason to assume the encrypt exponent is always 65537 since this information is available in the RSAPublicKey. Also, do not use the Base64 codec you are using, instead use the one from java.util.Base64.

Your method of reading in the bytes from the cipher *.bin files is unreliable because it assumes a read always returns the number of bytes requested. It will probably work out that way with current implementations but that isn't guaranteed by the javadocs. You should investigate the very simple Files.readAllBytes() method and related methods for reading in small files. They greatly simplify your code.