RSA暗号のアルゴリズムと正当性の証明

鍵生成アルゴリズム

• 入力: $k$ (セキュリティパラメータ)
• 出力: $\mathrm{pk}$ (公開鍵)、 $\mathrm{sk}$ (秘密鍵)

1. $k$ ビットのランダムな素数 $p$ 、 $q$ を生成する
   • ここではランダムな整数を生成してミラーラビン法などで判定する)
2. $N=pq$ とする
   • $N$ はRSAモジュールと呼ばれる
3. $\mathrm{GCD(\varphi(N),e)}=1$ となるような $\varphi(N)$ 未満の $e$ を選ぶ
   • ここで $e$ は固定されていることがよくあり、暗号化指数と呼ばれる)
4. $ed=1 \bmod{\varphi(N)}$ となる $d$ を計算する
   • $d$ は復号指数と呼ばれる
   • 下のように変形すると、拡張ユークリッドの互除法を適用して $d$ を求めることができる

   \begin{eqnarray*}ed&=&1\bmod{\varphi(N)}\\
   ed&=&1+\varphi(N)m\\
   -\varphi(N)m+ed&=&1
   \end{eqnarray*}
   

5. $\mathrm{pk}=(N,e)$ 、 $\mathrm{sk}=d$ として出力する

暗号化アルゴリズム

• 入力: $m(0\leq m\lt N)$ (平文)、 $\mathrm{pk}$ (公開鍵)
• 出力: $c$ (暗号文)

1. $c=m^e\bmod N$ として出力する

復号アルゴリズム

• 入力: $c(0\leq m\lt N)$ (暗号文)、 $\mathrm{pk}$ (公開鍵)、 $\mathrm{sk}$ (秘密鍵)
• 出力: $m'$ (復号結果)

1. $m'=c^d\bmod N$ として出力する

正当性の証明

鍵生成アルゴリズムより、ある整数 $k$ に対し、

\begin{eqnarray*}
ed&=&1 \bmod{\varphi(N)}\\
ed&=&k\varphi(N)+1
\end{eqnarray*}

暗号化アルゴリズムと復号アルゴリズムより、

m'=c^d=(m^e)^d=m^{ed}=m^{k\varphi(N)+1}=m^{k\varphi(N)}\cdot m

1. $\mathrm{GCD}(m,N)=1$ のとき
   オイラーの定理より、

   m'=m^{k\varphi(N)}\cdot m = 1^k\cdot m=m\pmod{N}
   

2. $\mathrm{GCD}(m,N)\neq 1$ のとき
   $N=pq$ であるので、 $\mathrm{GCD}(m,N)$ は $p$ または $q$ である

   1. $\mathrm{GCD}(m,N)=p$ のとき

      $m'$ を法 $p$ 、 $q$ で考え、それぞれを $a$ 、 $b$ とする
      $\mathrm{GCD}(m,N)=p$ より、

      a:=m'=0\pmod p
      

      フェルマーの小定理より、

      b:=m'=m^{k\varphi(N)+1}=m^{k(p-1)(q-1)+1}=m(m^{q-1})^{k(p-1)}=m\cdot 1^{k(p-1)}=m\pmod q
      

      $px+qy=1$ となるような整数 $x$ 、 $y$ を考える
      中国剰余定理より、

      \begin{eqnarray*}
      m'&=&bpx+aqy\bmod pq\\
      &=&mpx+0qy\bmod N\\
      &=&mpx\bmod N\\
      &=&m(1-qy)\bmod N\\
      &=&m-mqy\bmod N\\
      &=&m\bmod N
      \end{eqnarray*}
      

      最後の行は $\mathrm{GCD}(m,N)=p$ より、 $m$ が $p$ の倍数であり、 $mqy$ が $N$ で割り切れるため

   2. $\mathrm{GCD}(m,N)=q$ のとき
      上と同様に正当性が示せる

証明終わり

おまけ

実装しました　GMPを使っています

安全素数の生成をしようとすると時間がかかりすぎてしまったので普通の素数を生成しています　もし高速な方法があれば教えてください
ゴードンの強素数生成アルゴリズムを使いました　素数判定も高速化しました

長いので折りたたんでいます

#include<random>
#include<vector>
#include<utility>
#include<iostream>
#include<gmpxx.h>

mpz_class randbits(int bits,std::random_device &rng){
    mpz_class to_ret=0;
    if(bits>=64){
        uint64_t tmp=rng();
        to_ret+=tmp;
    }
    while(bits>=64){
        to_ret<<=64;
        bits-=64;
        uint64_t tmp=rng();
        to_ret+=tmp;
    }
    to_ret<<=bits;
    uint64_t tmp=rng()%(1ll<<bits);
    to_ret+=tmp;
    return to_ret;
}

int calc_bit_len(mpz_class num){
    int now_width=2048;
    int ret=0;
    while(now_width){
        mpz_class mask=((mpz_class(1)<<now_width)-1)<<now_width;
        mpz_class tmp;
        mpz_and(tmp.get_mpz_t(),num.get_mpz_t(),mask.get_mpz_t());
        if(tmp!=0){
            ret+=now_width;
            num>>=now_width;
        }
        now_width>>=1;
    }
    return ret;
}

std::pair<mpz_class,mpz_class> extgcd(mpz_class m,mpz_class n){
    bool swapped=false;
    if(m<n){
        swapped=true;
        swap(m,n);
    }
    mpz_class r_prev=m,r_now=n,u_prev=1,u_now=0,v_prev=0,v_now=1,q_prev=-1,q_now=-1;
    while(true){
        q_prev=q_now;
        q_now=r_prev/r_now;

        mpz_class tmp_r=r_now;
        r_now=r_prev-q_now*r_now;
        r_prev=tmp_r;

        if(r_now==0){
            if(swapped){
                return {v_now,u_now};
            }else{
                return {u_now,v_now};
            }
        }

        mpz_class tmp_u=u_now;
        u_now=u_prev-q_now*u_now;
        u_prev=tmp_u;
        
        mpz_class tmp_v=v_now;
        v_now=v_prev-q_now*v_now;
        v_prev=tmp_v;
    }
}

mpz_class modpow(mpz_class x,mpz_class n,mpz_class mod){
    mpz_class ans=1;
    while(n){
        if(n%2==1){
            ans*=x;
            ans%=mod;
        }
        x*=x;
        x%=mod;
        n>>=1;
    }
    return ans;
}

bool miller_rabin(mpz_class n){
    if(n<=1){
        return false;
    }
    int k=0;
    mpz_class m=n-1;
    while(m%2==0){
        k+=1;
        m>>=1;
    }
    std::random_device rng;
    for(int rep=0;rep<10;rep++){
        mpz_class a=randbits(2064,rng)%(n-2)+2;
        mpz_class b=modpow(a,m,n);
        
        bool flag=false;
        if(b==1){
            flag=true;
        }else{
            for(int rep2=0;rep2<k;rep2++){
                if(b==n-1){
                    flag=true;
                    break;
                }
                b=b*b%n;
            }
        }
        if(!flag)return false;
    }
    return true;
}

bool fermat_test(mpz_class n){
    std::random_device rng;
    for(int rep=0;rep<10;rep++){
        mpz_class a=randbits(2064,rng)%(n-1)+1;
        if(modpow(a,n-1,n)!=1)return false;
    }
    return true;
}

const mpz_class big_compos("1152783981972759212376551073665878035");

bool is_prime(mpz_class num){
    if(num%2==0)return false;
    if(gcd(big_compos,num)!=1)return false;
    if(fermat_test(num) && miller_rabin(num)){
        return true;
    }
    return false;
}

mpz_class gen_prime(int bits){
    std::random_device rng;
    while(true){
        mpz_class num=randbits(bits,rng);
        if(is_prime(num)){
            return num;
        }
    }
}

mpz_class gen_strong_prime(int bits){
    mpz_class q=gen_prime(bits/5*2);
    std::random_device rng;
    mpz_class a=randbits(bits/10,rng);
    mpz_class r=2*a*q+1;
    while(!is_prime(r)){
        r+=2*q;
    }
    mpz_class s=gen_prime(bits/5*2);
    auto [tmp,inv_r]=extgcd(s,r);
    while(true){
        mpz_class b=randbits(bits/10,rng);
        mpz_class p=1+2*(b*s-inv_r)*r;
        while(calc_bit_len(p)<bits){
            b<<=1;
            p=1+2*(b*s-inv_r)*r;
        }
        if(is_prime(p)){
            return p;
        }
    }
}

struct public_key{
    mpz_class n,e;
};
struct secret_key{
    mpz_class d;
};

std::pair<public_key,secret_key> key_gen(int k){
    mpz_class p = gen_strong_prime(k/2),q = gen_strong_prime(k/2);
    mpz_class n=p*q;
    mpz_class phi_n=(p-1)*(q-1);
    mpz_class e=65537;
    auto [tmp,d]=extgcd(phi_n,e);
    if(d<0){
        d+=phi_n;
    }
    return {{n,e},{d}};
}

mpz_class enc(mpz_class m,public_key pk){
    return modpow(m,pk.e,pk.n);
}

mpz_class dec(mpz_class c,public_key pk,secret_key sk){
    return modpow(c,sk.d,pk.n);
}

int main(){
    auto [pk,sk]=key_gen(2048);
    std::cout<<"N = "<<pk.n<<"\ne = "<<pk.e<<"\nd = "<<sk.d<<std::endl;
    mpz_class m("314159265358979323846264338327950288419716939937510");
    mpz_class c=enc(m,pk);
    std::cout<<"c = "<<c<<std::endl;
    mpz_class m_dash=dec(c,pk,sk);
    std::cout<<"m' = "<<m_dash<<std::endl;
}

参考

IPUSIRON．暗号技術のすべて．翔泳社，2017．