Пау функция и длинные инт вызывает проблемы

Question

Я пытаюсь реализовать схему шифрования RSA. Это выглядит примерно так:

encrypted data = ((message)^e) % n а также decrypted data = ((encrypted data)^d) % n

Я пытался реализовать это в с. Вот код:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    long int num = 3255859; 
    long int encrypt =(int)pow((double) num,3) % 33;
    printf("%ld\n",encrypt);

    return 0;

}

Я скомпилировал это используя gcc -Werror -g -o encrypt encrypt.c -lm

Это вывод, который я получаю = -2что, очевидно, неправильно. Когда я пробую этот код для меньших чисел, я получаю правильный результат. Например:

когда я установил num = 2Я получаю правильный результат, который 8

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

Не могли бы вы указать, где я иду не так.

Спасибо

РЕДАКТИРОВАТЬ:

Хорошо, согласно предложению от @Micael Oliver, вот модифицированный код:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){

    unsigned long long  num = 3255859; 

    long long encrypt =(long long)pow((double) num,3) % 33;

    printf("%llu\n",encrypt);

    long long decrypt =(long long)pow((double) encrypt,7) % 33;

    printf("%llu\n",decrypt);

    return 0;

}

Вот вывод этого кода:

Notra:Desktop Sukhvir$ gcc -Werror -g -o encrypt encrypt.c -lm
Notra:Desktop Sukhvir$ ./encrypt
18446744073709551608
18446744073709551614

что, очевидно, неправильно, так как 2-й выход должен был быть 3255859

Answer 1

В вашем коде есть немного не подписанных и подписанных чисел - вы должны стараться избегать этого, когда это возможно. Также вы пытаетесь использовать %llu на подписанный длинный длинный - вы должны использовать %lld в этом случае.

Но здесь есть более тонкая проблема. В этой строке:

long long encrypt =(long long)pow((double) num,3) % 33;

pow возвращает double, который не гарантирует всю точность, которую вы ищете. В результате вы потеряете несколько цифр long long, К сожалению, C не обеспечивает хорошую альтернативу для вычисления экспонент, поэтому вам нужно что-то реализовать самостоятельно или использовать библиотеку (некоторые другие ответы предлагают некоторые).

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

Они предоставляют некоторый псевдокод, который должен быть очевиден для кодирования на C.

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

Answer 2

Одним из предложений было использовать другой тип данных, например long long:

3255859^3 ==  34514116960466804779
ULLONG_MAX == 18446744073709551615  // this is the minimum guaranteed

Таким образом, unsigned long long может не работать. В целом изменение типов данных имеет свои ограничения. Другой более надежный подход, который вы можете рассмотреть, - это использование GMP-free. gmp manual -

Вы можете скачать gmp на этом сайте.

фрагмент кода:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <gmp.h>

int main()
{
    mpz_t rop, base, exp, mod;
    mpz_init2(rop,128); 
    mpz_init2(base,128); 
    mpz_init2(exp,128); 
    mpz_init2(mod,128);
    mpz_set_ui(base, 3255859);
    mpz_set_ui(exp, 3);
    mpz_set_ui(mod, 33);
    mpz_powm_sec (rop, base, exp, mod);
    gmp_printf ("result %Zd\n", rop);    
    return 0;
}

Answer 3

Пока ваши числа не превышают половины размера, с которым вы работаете, вы можете сделать что-то вроде этого:

(((num * num) % 33) * num) % 33

В общем, для чего-то практического в криптографических целях вам понадобятся гораздо большие значения и вычислительная среда для работы с 1024+ битными числами. Для этого вы можете использовать существующий код (я бы порекомендовал libtommath от libtomcrypt, безусловно, не GMP) или написать свой.