power(a,b) modn 계산하기

power(a,b) modn 계산하기

RSA 복호화에 사용할 모델을^b 계산하고자 합니다.내 코드(아래)가 오답을 반환합니다.무슨 문제가 있습니까?

unsigned long int decrypt2(int a,int b,int n)
{
    unsigned long int res = 1;

    for (int i = 0; i < (b / 2); i++)
    {
        res *= ((a * a) % n);
        res %= n;
    }

    if (b % n == 1)
        res *=a;

    res %=n;
    return res;
}

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

슈니어, 브루스 (1996)응용암호: C의 프로토콜, 알고리즘, 소스코드(Source Code), Second Edition.와일리.ISBN 978-0-471-11709-4.

---

result * base그리고.base * base이 단순화된 버전에서는 오버플로가 발생할 수 있습니다.모듈러스가 폭의 절반 이상인 경우T(즉, 최댓값의 제곱근 이상)T값), 그러면 적절한 모듈러 곱셈 알고리즘을 사용해야 합니다. 원시 유형으로 모듈러 곱셈을 수행하는 방법에 대한 답을 참조하십시오.

계산하기 위해서는pow(a,b) % n RSA 복호화에 사용할 수 있는 최고의 알고리즘은 다음과 같은 Primality Testing입니다¹⁾.

 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;
}

자세한 내용은 아래 참조.

---

¹⁾ IMT2000 3GPP - 비결정성 알고리즘 - 탑코더

보통은 이런 식입니다.

while (b)
{
    if (b % 2) { res = (res * a) % n; }

    a = (a * a) % n;
    b /= 2;
}

return res;

실제로 보이는 논리 오류는 다음 줄뿐입니다.

if (b % n == 1)

다음 중 어느 것이 되어야 합니까?

if (b % 2 == 1)

그러나 전체적인 설계는 문제가 있습니다. 함수는 O(b) 곱셈과 모듈러스 연산을 수행하지만 다음을 사용합니다.b / 2그리고.a * aO(log b) 연산을 수행하는 것을 목표로 하고 있음을 나타냅니다(일반적으로 모듈 지수화를 수행하는 방법은 일반적으로 모듈 지수화를 수행하는 것입니다.

원시 전력 연산을 수행하는 것은 매우 비용이 많이 들기 때문에 다음 논리를 적용하여 복호화를 단순화할 수 있습니다.

여기서부터.

이제 메시지 m = 7을 암호화하고 싶다고 합니다.
= mod n= 7^3 mod 33= 343 mod 33= 13.c= m^e mod n= 7^3 mod 33= 343 mod 33= 13.
따라서 암호문 c = 13.

암호 해독을 확인하기 위해 우리는 계산합니다.
mod n 13^7 mod 33 7.m' c^d mod n 13^7 mod 33 7.
여기서는 거듭제곱 7에 대한 13의 전체 값을 계산할 필요가 없습니다.우리는 그 사실을 이용할 수 있습니다.
mod n (b n). (c mod n) mod n a bc mod n (b mod n). (c modn) modn
따라서 잠재적으로 많은 수를 구성 요소로 분해하고 더 쉽고 작은 계산 결과를 결합하여 최종 값을 계산할 수 있습니다.

m'을 계산하는 한 가지 방법은 다음과 같습니다:-
임의의 숫자는 2의 거듭제곱의 합으로 표현될 수 있습니다.먼저 계산 값을 계산합니다.
연속된 값들을 반복적으로 제곱하여 모듈로 33. 13^2 = 169 ≡ 4, 13^4 = 4.4 = 16, 13^8 = 16.16 = 256 ≡ 25.
+ 이므로 m' 13^7 13^(4+2+1) 13^4.13^2.13^1 7 4 + 2 + 1 이므로 m' 13^7 13^(4+2+1) 13^4.13^2.13^1
x 4 x 7 mod 33 16 x 4 x 13 832 7 mod 33

당신은 계산을 하려는 건가요?(a^b)%n, 아니면a^(b%n)?

만약 당신이 첫번째 코드를 원한다면, 당신의 코드는 그 b/2 때문에 b가 짝수일 때만 작동합니다.더"if b%n==1" 당신이 신경쓰지 않기 때문에 틀렸습니다.b%n여기서, 그러나 그보다는b%2.

두 번째 루프를 원한다면, (b%n)/2회 대신에 b/2회 루프를 하는 것이기 때문에 루프가 잘못된 것입니다.

어느 쪽이든, 당신의 기능은 불필요하게 복잡합니다.왜 당신은 b/2까지 루프를 하고 매번 2 a를 곱하려고 합니까?매번 하나씩 b와 multiply in을 할 때까지 루프만 하는 것은 어떨까요?이를 통해 불필요한 복잡성을 제거하고 잠재적 오류를 제거할 수 있습니다.루프를 통과하는 횟수를 반으로 줄여 프로그램을 더 빠르게 만들 수 있을 것으로 생각하십니까?솔직히 그건 잘못된 프로그래밍 방식입니다. 마이크로 최적화입니다.별로 도움이 되지 않습니다. 여전히 같은 횟수만큼 곱하기만 하면 루프를 테스트하는 횟수가 줄어듭니다.일반적으로 b가 한 자리 또는 두 자리와 같이 작다면 수고할 가치가 없습니다.만약 b가 크다면, 만약 그것이 수백만 단위가 될 수 있다면, 이것은 불충분하고, 당신은 훨씬 더 급진적인 최적화가 필요합니다.

은 왜 야, .%n매번 루프를 통과할 때마다?마지막에 한 번만 하는 게 어때요?

power(a,b) modn 계산하기

1. OP 코드의 핵심 문제는 다음과 같습니다.a * a.이것은int오버플로(정의되지 않은 동작):a충분히 큽니다.형의 입니다.res의 곱셈에는 관계가 없습니다.a * a.

   해결책은 다음 중 하나를 보장하는 것입니다.

   • 곱셈은 2배 넓은 수학으로 이루어집니다.
   • 모듈러스로 n,n*n <= type_MAX + 1

2. 결과가 항상 해당 유형으로 표시되므로 모듈러스 유형보다 더 넓은 유형을 반환할 이유가 없습니다.

   // unsigned long int decrypt2(int a,int b,int n)
   int decrypt2(int a,int b,int n)
   

3. 부호 없는 수학을 사용하는 것이 OP의 RSA 목표에 더 적합합니다.

---

범위 제한이 없는 모듈형 지수화도 참조하십시오.

// (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

int의 것은 일반적으로 RSA에 충분하지 않습니다(소규모 단순화된 예를 다루지 않는 한).

최대 2개²⁵⁶(256비트 RSA 키의 경우) 또는 512비트 키의 경우 2개까지⁵¹² 정수를 저장할 수 있는 데이터 유형이 필요합니다.

다른 방법이 있습니다.우리가 발견했을 때 기억해요modulo multiplicative inversea현대하에m.그리고나서

a와 m은 반드시.coprime서로간에

사용할 수 있습니다.gcd extended계산을 위하여modulo multiplicative inverse.

모뎀을^b 계산할 때a그리고.b10자리⁵ 이상의 숫자를 가질 수 있으며 결과를 계산하는 것은 어렵습니다.

아래 코드는 컴퓨팅 부분을 수행합니다.

#include <iostream>
#include <string>
using namespace std;
/*
*   May this code live long.
*/
long pow(string,string,long long);
long pow(long long ,long long ,long long);
int main() {
    string _num,_pow;
    long long _mod;
    cin>>_num>>_pow>>_mod;
    //cout<<_num<<" "<<_pow<<" "<<_mod<<endl;
    cout<<pow(_num,_pow,_mod)<<endl;
   return 0;
}
long pow(string n,string p,long long mod){
    long long num=0,_pow=0;
    for(char c: n){
        num=(num*10+c-48)%mod;
    }
    for(char c: p){
        _pow=(_pow*10+c-48)%(mod-1);
    }
    return pow(num,_pow,mod);
}
long pow(long long a,long long p,long long mod){
    long res=1;
    if(a==0)return 0;
    while(p>0){
        if((p&1)==0){
            p/=2;
            a=(a*a)%mod;
        }
        else{
            p--;
            res=(res*a)%mod;
        }
    }
    return res;
}
 

이^b 코드는 modm을 ^{b mod m-1}(modm) modm으로 쓸 수 있기 때문에 작동합니다.

도움이 되었기를 바랍니다 { :)

빠른 지수화를 사용하면... 위의 템플릿과 동일한 o(로그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;
}

이것(암호화)은 프로그래밍 문제라기보다는 알고리즘 설계 문제에 더 가깝습니다.중요한 누락 부분은 현대 대수학에 대한 친숙함입니다.나는 당신이 군 이론과 수 이론에서 거대한 최적화를 찾는 것을 제안합니다. 만약n소수일 뿐입니다.pow(a,n-1)%n==1(assuming 무한 자릿수 정수).그래서 기본적으로 당신이 계산할 필요가 있습니다.pow(a,b%(n-1))%n; 집단 이론에 따르면, 당신은 다음을 찾을 수 있습니다.e모든 다른 수가 다음의 거듭제곱과 같도록e모듈로n. 따라서 범위는[1..n-1]의 힘에 대한 순열로 나타낼 수 있습니다.e. 찾을 알고리즘이 주어지면e위해서nda기초e, 계산을 상당히 단순화할 수 있습니다.암호학은 수학적 배경이 필요합니다. 저는 충분한 배경 없이 그 분야에서 벗어나길 원합니다.

php로 된 내 코드 a^k modn:

function pmod(a, k, n)
{
    if (n==1) return 0;
    power = 1;
    for(i=1; i<=k; $i++)
    {
        power = (power*a) % n;
    }
    return power;
}

#include <cmath>
...
static_cast<int>(std::pow(a,b))%n

하지만 저는 당신이 int를 넘치고 있다는 것을 가장 잘 장담합니다(즉, int의 경우 숫자가 2개 큽니다). 저는 똑같은 기능을 만드는 데 같은 문제가 있었습니다.

이 기능을 사용하고 있습니다.

int CalculateMod(int base, int exp ,int mod){
    int result;
    result = (int) pow(base,exp);
    result = result % mod;
    return result;
}

pow가 두 배를 돌려주기 때문에 변수 결과를 파싱합니다. mod를 사용하려면 int 타입의 두 변수가 필요합니다. 어쨌든 RSA 복호화에서는 정수만 사용해야 합니다.

언급URL : https://stackoverflow.com/questions/8496182/calculating-powa-b-mod-n