RSA шифрование кириллицы

Исходная реализация алгоритма взята отсюда. Для простоты есть 2 класса сам алгоритм и Main (psvm):

import java.math.BigInteger;
import java.security.SecureRandom;
public class RSA {
    private final static BigInteger one = new BigInteger("1");
    private final static SecureRandom random = new SecureRandom();
    private BigInteger privateKey;
    private BigInteger publicKey;
    private BigInteger modulus;
    RSA(int N) {
        BigInteger p = BigInteger.probablePrime(N / 2, random);
        BigInteger q = BigInteger.probablePrime(N / 2, random);
        BigInteger phi = (p.subtract(one)).multiply(q.subtract(one));
        modulus = p.multiply(q);
        publicKey = new BigInteger("65537");     // common value in practice = 2^16 + 1
        privateKey = publicKey.modInverse(phi);
    }
    BigInteger encrypt(BigInteger message) {
        return message.modPow(publicKey, modulus);
    }
    BigInteger decrypt(BigInteger encrypted) {
        return encrypted.modPow(privateKey, modulus);
    }
}

и

import java.math.BigInteger;
public class Main {
    public static void main(String[] args) {
        int N = 1024; //количество бит для генерации RSA ключей
        RSA rsa = new RSA(N);
        //создаем сообщение в BigInteger формате
        BigInteger message = new BigInteger("Привет Мир! I love you!".getBytes());
        //далее, зашифровываем секретное сообщение
        BigInteger encryptMessage = rsa.encrypt(message);
        // Расшифровываем зашифрованное сообщение
        BigInteger decryptMessage = rsa.decrypt(encryptMessage);
        /* Выводим наш результат на экран */
        System.out.println(new String(decryptMessage.toByteArray()));
    }
}

Когда шифруются ASCII-символы, то все норм. Но если первая буква сообщения в байтовом представлении представляет собой отрицательное число (любая буква кириллицы, например), то и весь BigInteger, который представляет это секретное сообщение, будет отрицательным и результат будет неверным.

Я обошел это, добавляя один байт впереди при шифровании и не учитываю его в расшифрованном BigInteger-e. Но это похоже на костыль, мне не нравится, хочется чтобы красиво было.

Какие есть мысли?