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.
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
0
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