How to encrypt a string using public key cryptography

I am trying to implement my own RSA encryption engine. Given these RSA algorithm values:

p = 61. // A prime number.
q = 53. // Also a prime number.
n = 3233. // p * q.
totient = 3120. // (p - 1) * (q - 1)
e = 991. // Co-prime to the totient (co-prime to 3120).
d = 1231. // d * e = 1219921, which is equal to the relation where 1 + k * totient = 1219921 when k = 391.

I am trying to write a method to encrypt each byte in a string and return back an encrypted string:

public string Encrypt(string m, Encoding encoding)
{
    byte[] bytes = encoding.GetBytes(m);
    for (int i = 0; i < bytes.Length; i++)
    {
        bytes[i] = (byte)BigInteger.ModPow(bytes[i], e, n);
    }
    string encryptedString = encoding.GetString(bytes);
    Console.WriteLine("Encrypted {0} as {1}.", m, encryptedString);
    return encryptedString;
}

The obvious issue here is that BigInteger.ModPow(bytes[i], e, n) may be too large to fit into a byte-space; it could result in values over 8 bits in size. How do you get around this issue while still being able to decrypt an encrypted string of bytes back into a regular string?

Update: Even encrypting from byte[] to byte[], you reach a case where encrypting that byte using the RSA algorithm goes beyond the size limit of a byte:

public byte[] Encrypt(string m, Encoding encoding)
{
    byte[] bytes = encoding.GetBytes(m);
    for (int i = 0; i < bytes.Length; i++)
    {
        bytes[i] = (byte)BigInteger.ModPow(bytes[i], e, n);
    }
    return bytes;
}

Update: My issue is that encryption would cause a greater number of bytes than the initial input string had:

public byte[] Encrypt(string m, Encoding encoding)
{
    byte[] bytes = encoding.GetBytes(m);
    byte[] returnBytes = new byte[0];
    for (int i = 0; i < bytes.Length; i++)
    {
        byte[] result = BigInteger.ModPow(bytes[i], (BigInteger)e, n).ToByteArray();
        int preSize = returnBytes.Length;
        Array.Resize(ref returnBytes, returnBytes.Length + result.Length);
        result.CopyTo(returnBytes, preSize);
    }
    return returnBytes;
}

public string Decrypt(byte[] c, Encoding encoding)
{
    byte[] returnBytes = new byte[0];
    for (int i = 0; i < c.Length; i++)
    {
        byte[] result = BigInteger.ModPow(c[i], d, n).ToByteArray();
        int preSize = returnBytes.Length;
        Array.Resize(ref returnBytes, returnBytes.Length + result.Length);
        result.CopyTo(returnBytes, preSize);
    }
    string decryptedString = encoding.GetString(returnBytes);
    return decryptedString;
}

If you ran this code like this:

byte[] encryptedBytes = engine.Encrypt("Hello, world.", Encoding.UTF8);
Console.WriteLine(engine.Decrypt(encryptedBytes, Encoding.UTF8));

The output would be this:

?♥D
?♥→☻►♦→☻►♦oD♦8? ?♠oj?♠→☻►♦;♂?♠♂♠?♠

Obviously, the output is not the original string because I can't just try decrypting each byte at a time, since sometimes two or more bytes of the cypher-text represent the value of one integer that I need to decrypt back to one byte of the original string...so I want to know what the standard mechanism for handling this is.

Jon Skeet
people
quotationmark

Your basic code for encrypting and decrypting each byte - the call to ModPow - is working, but you're going about the "splitting the message up and encrypting each piece" inappropriately.

To show that the ModPow part - i.e. the maths - is fine, here's code based on yours, which encrypts a string to a BigInteger[] and back:

using System;
using System.Linq;
using System.Numerics;
using System.Text;

class Test
{
    const int p = 61;
    const int q = 53;
    const int n = 3233;
    const int totient = 3120;
    const int e = 991;
    const int d = 1231;

    static void Main()
    {
        var encrypted = Encrypt("Hello, world.", Encoding.UTF8);
        var decrypted = Decrypt(encrypted, Encoding.UTF8);
        Console.WriteLine(decrypted);
    }

    static BigInteger[] Encrypt(string text, Encoding encoding)
    {
        byte[] bytes = encoding.GetBytes(text);
        return bytes.Select(b => BigInteger.ModPow(b, (BigInteger)e, n))
                    .ToArray();
    }

    static string Decrypt(BigInteger[] encrypted, Encoding encoding)
    {
        byte[] bytes = encrypted.Select(bi => (byte) BigInteger.ModPow(bi, d, n))
                                .ToArray();
        return encoding.GetString(bytes);
    }
}

Next you need to read more about how a byte[] is encrypted into another byte[] using RSA, including all the different padding schemes etc. There's a lot more to it than just calling ModPow on each byte.

But to reiterate, you should not be doing this to end up with a production RSA implementation. The chances of you doing that without any security flaws are very slim indeed. It's fine to do this for academic interest, to learn more about the principles of cryptography, but leave the real implementations to experts. (I'm far from an expert in this field - there's no way I'd start implementing my own encryption...)

people

See more on this question at Stackoverflow