функция pow и long int вызывает проблемы

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

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

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

Благодаря

EDIT:

Ok согласно предложению от @Micael Оливер здесь модифицированный код:

#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 не является хорошей альтернативой для вычисления экспонентов, поэтому вам нужно что-то реализовать самостоятельно или использовать библиотеку (некоторые из других ответов предложили некоторые).

Если вы хотите реализовать его самостоятельно, большая статью о быстрой экспоненциации по квадратуре можно найти в Википедии здесь: Exponentiation by squaring

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

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

Answer 2

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

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

Так, неподписанные долго долго не может работать. В целом изменение типов данных имеет ограничения. Другим более надежным подходом, который вы можете рассмотреть, является использование GMP - бесплатно. 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) или написать свой собственный.