RSA decryption problem

I am working on the RSA algorithm and in general everything works out, but there is a problem with decryption. For some numbers, such as 9, 10, 13, the message is incorrectly decrypted. enter a description of the image here enter a description of the image here

Code

private void button_GetKey_Click(object sender, EventArgs e)
    {
        int n = p * q; // Модуль, который используется в открытом ключе
        int f = (p - 1) * (q - 1);  // Функция Эйлера

        List<int> simpleNumbers = generateSimpleNumbers(f);
        int exp = getExponent(simpleNumbers, f);
        // На данном этапе у нас есть открытый ключ {exp, n}
        //Далее необхожимо сформировафть личный ключ 
        int d = generatePrivateKey(exp, f); // личный ключ {d, n}

        // Теперь можем приступать к кодированию
        Random rnd = new Random();

        //Получить случайное число
        double x = rnd.Next(1, n);
        textBox5.Text = x.ToString();
        x = Math.Pow(x, exp);
        x = x % n;
        textBox3.Text = x.ToString();

        // После приступаем к дешифровке
        double y = Math.Pow(x, d);
        y = y % n;
        textBox4.Text = y.ToString();
    }

    private bool isSimpleNumber(int n)
    {
        int count = 0;

        for (int i = 2; i <= n; i++)
        {
            if (n % i == 0) count++;
        }

        if (count == 1)
            return true;
        else
            return false;
    }

    private List<int> generateSimpleNumbers(int n)
    {
        int count;
        List<int> numbers = new List<int>();

        for (int i = 2; i < n; i++)
        {
            count = 0;
            for (int j = 2; j <= i; j++)
            {
                if (i % j == 0) count++;
            }

            if (count == 1)
                numbers.Add(i);
        }

        return numbers;
    }

    // Находим экспоненту
    private int getExponent(List<int> numbers, int fi)
    {
        foreach (int el in numbers)
        {
            if (fi % el != 0)
                return el;
        }

        return 0;
    }

    // Находим личный ключ
    private int generatePrivateKey(int e, int fi)
    {
        int d = e;
        int test = 0;
        do
        {
            d += 1;
            test = (d * e) % fi;

        } while (!isSimpleNumber(d) || test != 1);

        return d;
    }

Why is the decryption broken at some points ? After all, the condition (x source

Author: return, 2020-12-04

1 answers

You have the wrong algorithm for finding the secret key.

long ComputPrivateKey(long e, long phi)
{
    var d = 1;

    while ((d * e - 1) % phi != 0) d++;

    return d;
}

My option is also not optimal, but simple. For complex options, go to here - I took all the information about RSA from there.


In general, you need to use large numbers in a good way (1024 bits, for example), otherwise you may have an overflow and all your data will go down the drain.

 2
Author: return, 2020-12-05 07:04:13