Интересно, что ни один из ответов на этой странице не упоминает два крайних случая, надеюсь, никто не возражает, если я их добавлю:
Родовые словари в .NET не являются потокобезопасными, а иногда могут бросать NullReference
или даже (чаще) a KeyNotFoundException
при попытке получить доступ к ключу из двух параллельных потоков. Исключение в этом случае является довольно ошибочным.
Если код NullReferenceException
задан кодом unsafe
, вы можете посмотреть на переменные указателя , и проверьте их на IntPtr.Zero
или что-то в этом роде. Это одно и то же («исключение нулевого указателя»), но в небезопасном коде переменные часто переводятся в типы значений / массивы и т. Д., И вы ударяете головой о стену, задаваясь вопросом, как тип значения может исключение.
(Еще одна причина для небезопасного использования небезопасного кода, если вам это нужно)
Вы можете попробовать этот код на C ++. Я использовал его с 32 и 64-битными целыми числами. Я уверен, что получил это от SO.
template <typename T>
T modpow(T base, T exp, T modulus) {
base %= modulus;
T result = 1;
while (exp > 0) {
if (exp & 1) result = (result * base) % modulus;
base = (base * base) % modulus;
exp >>= 1;
}
return result;
}
Вы можете найти этот алгоритм и соответствующее обсуждение в литературе на с. 244 of
Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.
Выполнение операции сырой мощности очень дорого, поэтому вы можете применить следующую логику для упрощения дешифрования.
Из здесь ,
] Теперь скажем, что мы хотим зашифровать сообщение m = 7, c = m ^ e mod n = 7 ^ 3 mod 33 = 343 mod 33 = 13. Следовательно, зашифрованный текст c = 13.
Чтобы проверить расшифровку мы вычисляем m '= c ^ d mod n = 13 ^ 7 mod 33 = 7. Заметим, что нам не нужно вычислять полное значение 13 для мощности 7 здесь. Мы можем использовать тот факт, что a = bc mod n = (b mod n). (C mod n) mod n, поэтому мы можем разбить потенциально большое число на его компоненты и объединить результаты более простых, меньших вычислений для вычисления конечное значение.
Один из способов вычисления m 'заключается в следующем: - Обратите внимание, что любое число может быть выражено как сумма степеней 2. Итак, сначала вычислите значения 13 ^ 2, 13 ^ 4, 13 ^ 8, ... путем многократного возведения в квадрат последовательных значений по модулю 33. 13 ^ 2 = 169 ≡ 4, 13 ^ 4 = 4.4 = 16, 13 ^ 8 = 16.16 = 256 ≡ 25. Тогда, поскольку 7 = 4 + 2 + 1, мы имеем m '= 13 ^ 7 = 13 ^ (4 + 2 + 1) = 13 ^ 4.13 ^ 2.13 ^ 1 ≡ 16 x 4 x 13 = 832 ≡ 7 mod 33
blockquote>
Вычисление pow (a, b) mod n
blockquote>
- Ключевой проблемой с кодом OP является
a * a
. Этоint
переполнение (неопределенное поведение), когдаa
достаточно велико. Типres
не имеет значения при умноженииa * a
. Решение состоит в том, чтобы гарантировать: 1) умножение выполняется с использованием 2x широкой математики или 2) с модулемn
,n*n <= type_MAX + 1
- Нет причин возвращать более широкий тип, чем тип модуля , поскольку результат всегда представляет этот тип.
// unsigned long int decrypt2(int a,int b,int n) int decrypt2(int a,int b,int n)
- Использование математики unsigned , безусловно, более подходит для целей RSA в OP.
// (a^b)%n // n != 0 // Test if unsigned long long at least 2x values bits as unsigned #if ULLONG_MAX/UINT_MAX - 1 > UINT_MAX unsigned decrypt2(unsigned a, unsigned b, unsigned n) { unsigned long long result = 1u % n; // Insure result < n, even when n==1 while (b > 0) { if (b & 1) result = (result * a) % n; a = (1ULL * a * a) %n; b >>= 1; } return (unsigned) result; } #else unsigned decrypt2(unsigned a, unsigned b, unsigned n) { // Detect if UINT_MAX + 1 < n*n if (UINT_MAX/n < n-1) { return TBD_code_with_wider_math(a,b,n); } a %= n; unsigned result = 1u % n; while (b > 0) { if (b & 1) result = (result * a) % n; a = (a * a) % n; b >>= 1; } return result; } #endif
Я думаю, у вас две проблемы. Во-первых, вы проверяете нечетный показатель один раз в конце, а не каждый раз через цикл; два, ваш чек для нечетного экспонента ошибочен.
Вот рекурсивная версия, которая работает для нескольких примеров, которые я нашел в Интернете.
unsigned long int decrypt2(int a,int b,int n)
{
unsigned long int res;
if (b == 0) {
res = 1;
} else if (b % 2 == 1) {
res = a * decrypt2( a, b-1, n );
} else {
res = decrypt2( a, b/2, n );
res = (res*res)%n;
}
#include <cmath>
...
static_cast<int>(std::pow(a,b))%n
, но мой лучший выбор - вы переполняете int (IE: число два больших для int) на мощности у меня была та же проблема, создавая ту же самую функцию.
Я использую эту функцию:
int CalculateMod(int base, int exp ,int mod){
int result;
result = (int) pow(base,exp);
result = result % mod;
return result;
}
Я анализирую результат переменной, потому что pow возвращает вам двойной, и для использования мода вам нужны две переменные типа int, во всяком случае, в RSA расшифровка, вы должны просто использовать целые числа.
Обычно это что-то вроде этого:
while (b)
{
if (b % 2) { res = (res * a) % n; }
a = (a * a) % n;
b /= 2;
}
return res;
использовать быструю экспонентуцию, возможно, ..... дает такой же o (log n), что и этот шаблон выше
int power(int base, int exp,int mod)
{
if(exp == 0)
return 1;
int p=power(base, exp/2,mod);
p=(p*p)% mod;
return (exp%2 == 0)?p:(base * p)%mod;
}
Единственная фактическая логическая ошибка, которую я вижу, - это строка:
if (b % n == 1)
, которая должна быть такой:
if (b % 2 == 1)
Но ваш общий дизайн проблематичен: ваша функция выполняет O (b) операции умножения и модуля, но использование b / 2
и a * a
подразумевает, что вы пытаетесь выполнить операции O (log b) (как правило, это выполняется модульное возведение в степень).
Вы пытаетесь вычислить (a^b)%n
или a^(b%n)
?
Если вы хотите первый, то ваш код работает только тогда, когда b является четным числом из-за этого b / 2. «if b%n==1
» неверно, потому что здесь вас не интересует b%n
, а скорее b%2
.
Если вы хотите второй, тогда цикл ошибочен, потому что вы зацикливание b / 2 раза вместо (b% n) / 2 раза.
В любом случае ваша функция излишне сложна. Почему вы зацикливаете до b / 2 и пытаетесь умножить на 2 a каждый раз? Почему бы не просто петли до b и mulitply в один раз каждый раз. Это устранит много ненужной сложности и, таким образом, устранит потенциальные ошибки. Вы думаете, что быстрее сделаете программу быстрее, сократив количество циклов в два раза? Честно говоря, это плохая практика программирования: микро-оптимизация. Это не очень помогает: вы все еще умножаетесь на одно и то же количество раз, все, что вы делаете, сокращается на количество раз, проверяя цикл. Если b обычно мал (например, одна или две цифры), это не стоит проблем. Если b велико - если оно может быть в миллионах - тогда этого недостаточно, вам нужна гораздо более радикальная оптимизация.
Также, почему %n
каждый раз через цикл? Почему бы просто не сделать это один раз в конце?
Чтобы вычислить pow(a,b) % n
, который будет использоваться для дешифрования RSA, лучшим алгоритмом, с которым я столкнулся, является тестирование Primality 1), которое выглядит следующим образом:
int modulo(int a, int b, int n){
long long x=1, y=a;
while (b > 0) {
if (b%2 == 1) {
x = (x*y) % n; // multiplying with base
}
y = (y*y) % n; // squaring the base
b /= 2;
}
return x % n;
}
См. ниже ссылку для более подробной информации.
1) Испытание первичности: недетерминированные алгоритмы - topcoder
int
, как правило, недостаточно для RSA (если вы не имеете дело с небольшими упрощенными примерами)
вам нужен тип данных, который может хранить целые числа до 2256 (для 256-битных ключей RSA ) или 2512 для 512-битных ключей и т. д.