RSA encryption and decryption produces some wrong characters

Question

This code here belongs to my security homework. I'm trying to encrypt a message with the RSAEncrypt function and decrypt a message with the RSADecrypt function character-wise. My alphabet array has 26 elements.

For example:

RSAEncryption(lorem) -> Ciphertext = ?????
RSADecryption(?????) -> Plaintext = lorem

Code is here:

static char alphabet[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 
    'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

public static String RSAEncrypt() {

    int[] keys;
    String message, cipherText = "";
    int p, q, n, x, e, d, index = 0;

    System.out.println("Enter two prime integers: ");
    p = sc.nextInt();
    q = sc.nextInt();

    n = p * q; //Modulus
    x = (p - 1) * (q - 1); //φ(n)

    if (n < 26) {
        System.out.print("Please enter two prime numbers that their multiplication "
                + "is bigger than 26(Alphabet Lenght)!");
    } else {
        System.out.println("Enter a message to encrypt: ");
        message = sc.next();

        keys = RSAKeyGeneration(x);
        e = keys[0]; //Public Key
        d = keys[1]; //Private Key

        for (int i = 0; i < message.length(); i++) {
            char character = message.charAt(i);
            for (int j = 0; j < alphabet.length; j++) {
                if (character == alphabet[j]) {
                    index = j;
                    break;
                }
            }

            double cipherTextDouble = (Math.pow(index, e) % n);
            cipherText += alphabet[(int) cipherTextDouble % 26];
        }

        System.out.print("Original Message = " + message + ", Modulus = " + n + ", Public Key = " + e
                + ", Private Key = " + d + ", Ciphertext = ");

        return cipherText;
    }
    return "";
}

public static String RSADecrypt() {

    String cipherText, plainText = "";
    int d, n;

    System.out.println("Enter the encrypted message: ");
    cipherText = sc.next();

    System.out.println("Enter the private key(d and n(modulus)): ");
    d = sc.nextInt();
    n = sc.nextInt();

    for (int i = 0; i < cipherText.length(); i++) {
        for (int j = 0; j < 26; j++) {
            if (cipherText.charAt(i) == alphabet[j]) {
                int temp = 1;
                for (int z = 0; z < d; z++) {
                    temp *= j;
                    temp = (temp % n);
                }
                plainText += alphabet[(temp % 26)];
            }
        }
    }
    return plainText;
}

public static int[] RSAKeyGeneration(int x) {
    int[] keys = new int[2];

    for (int i = x; i > 0; i--) {
        if (i % x != 0 && x % i != 0) {
            keys[0] = i; //Public Key
        }
    }

    keys[1] = findInverse(keys[0], x); //Private Key

    return keys;
}

The Problem is when I give the prime numbers 5 and 7 (Mod = 35, Totient = 24, e = 5, d = 5) It gives me wrong plaintext.

RSAEncryption(abcdefghijklmnopqrstuvwxyz) -> Ciphertext = abghjkghiefqrnoplmxyuvwste
RSADecryption(abghjkghiefqrnoplmxyuvwste) -> Plaintext = abghefghijklmnopqrstuvwxyj

Why 'c', 'd', 'z' characters are giving me wrong output. Also when I give prime numbers bigger the output is totally wrong. Where am I doing wrong?

score 1 · Accepted Answer · answered Dec 02 '15 at 17:05

1

RSA encryption is an exponentiation modulo n. Your n is 35, but the problem is that you then try to convert the ciphertext which is in the range from 0 to 34 to a ciphertext in the range from 0 to 25 with this line:

cipherText += alphabet[(int) cipherTextDouble % 26];

This means that ~25% ((35-26)/35) of your ciphertext characters will be incorrect. You need to increase your alphabet to 35 entries and use

cipherText += alphabet[(int) cipherTextDouble];

Also, you will probably run into the precision problem of representing integers in doubles pretty quick when you try to increase the prime numbers. You will have to switch to the BigInteger class.

answered Dec 02 '15 at 17:05

Artjom B.

61,146
24
125
222

But I need to use this alphabet array that's why I'm using modulo 26. Also I didn't use BigInteger class because values never reach long MAX_VALUE with "for" loop i wrote for taking pow. – Hmerac Dec 02 '15 at 17:32
You could use the two primes 2 and 13 and your code should work as it is now, but that's not how RSA should be used. RSA is sufficiently secure with a modulus of 3072 *bit* and up. What you do here is a toy example. One would never encrypt every single character on its own. Normally, you would use [hybrid encryption](https://en.wikipedia.org/wiki/Hybrid_cryptosystem). – Artjom B. Dec 02 '15 at 17:36
When you use larger primes, then you also probably want to encrypt larger messages, but a double cannot hold any integer without losing precision. Basically, when the result of `Math.pow(index, e)` is larger than `2^53` ([reference](http://stackoverflow.com/q/1848700/1816580)), then you won't be able to decrypt that, because that double cannot represent the integer. – Artjom B. Dec 02 '15 at 17:46
I'm converting Math.pow to manuel now. I'll give you feedback. – Hmerac Dec 02 '15 at 18:15
Oh, I converted it but still getting the same output. I think that's because I always pick my public key the smallest. Like 2, 3 or 5 so there is no problem at encryption pow method I guess. But my private key is the biggest and I thought I solved that problem by using for loop instead of pow method. – Hmerac Dec 02 '15 at 18:26
Have you tried the 2 and 13 as the two primes that multiply to 26? That should give you an idea why the second modulo operation (`%`) which I referenced in my answer is the problem. You're right, `Math.pow` is not a problem for such small numbers. – Artjom B. Dec 02 '15 at 20:27
So that means I can't use 26 length alphabet array for prime numbers bigger than 2 and 13 right ? – Hmerac Dec 02 '15 at 22:04
That's right. Your modulus must be smaller or equal to the alphabet size. – Artjom B. Dec 02 '15 at 22:43

RSA encryption and decryption produces some wrong characters

1 Answers1