Безопасность шифрования RSA

Question

Я немного озадачен безопасностью RSA. Я искал алгоритмы rsa и нашел много, но их ключи кажутся маленькими цифрами все время.

Это самый простой алгоритм, который я нашел:

void RSAEncDec(BYTE* pBuff, int iLen)
{
    for (long i = 0; i < iLen; i++)
    {
        pBuff[i] = (long)pow(pBuff[i], key) % modl;
    }
}

С алгоритмом генерации ключа:

rsacrypto::rsacrypto()
{
    long p1,p2; //Prime numbers
    long n = 0; //Modulus
    long phi =0; //Totient value.

    long e = 0; //Public key exponent.
    long d = 0; //Private key exponent.

    p1 = genrndprimes(100,900);
    Sleep(1000);
    p1 = genrndprimes(100,900);

    n = p1*p2;
    phi = totient(n);

    e = genrndnum(2,(phi-1));

    while(gcd(e,phi)!=1)
    {
        e = genrndnum(2,(phi-1));
    }

    d = (1/e)%phi; //Modular Multiplicative Inverse.

    privatekey = e;
    publickey = d;
    modl = n;


}

Я обеспокоен "genrndprimes(100,900)", 100 между 900 - это небольшие числа, в то время как я узнал, что размеры ключей должны быть выше 512 битов, то есть выше 900. Я здесь что-то не так?

Большое спасибо.

Answer 1

Это совсем не безопасно и может быть довольно быстро взломано. Чтобы найти закрытый ключ из открытого ключа, потребуется не более 900 делений (при условии genrndprimes принимает фактические минимальные и максимальные значения вместо количества бит). Так что это займет меньше секунды.

Вам нужно либо написать свой собственный код с множественной точностью, либо просто использовать существующие, такие как GMP. Тогда вы могли бы представить большие целые числа. Сегодня хорошим начальным значением для n является 2048-битное целое число.

Кроме того, модульное мультипликативное обратное не является действительной операцией деления, потому что не может быть никаких дробей. Все должно быть сделано в модульной арифметике. Модульное мультипликативное обратное требует, например, использования расширенного евклидова алгоритма, чтобы найти его.

Но чтобы сделать RSA действительно пригодным для использования в реальных условиях, вам также потребуется реализовать схему заполнения, такую ​​как PKCS#1 v2.0 (OAEP).

Затем вам нужно взглянуть на гибридное шифрование, если вы хотите зашифровать данные, которые больше чем n (заполнение также должно учитываться). В этом случае вы должны сгенерировать случайный ключ AES, зашифровать свои данные с помощью AES, а затем зашифровать сгенерированный ключ AES с помощью RSA, поскольку ключи AES достаточно малы, чтобы их можно было зашифровать.

Сделав все это, вы обнаружите, что ваш код содержит ошибки и уязвим для различных атак по побочным каналам. Вы будете использовать свою любимую поисковую систему, чтобы найти существующую широко известную и протестированную библиотеку, которая сделает все это за вас, потому что никогда не раскручивайте свой собственный крипто.