プログラム

下のプログラムの encrypt(M) は文字列 $S$ を RSA 暗号化する. decrypt(C) は encrypt された結果を元の 文字列に戻す. 例を示そう.

[356] encrypt("OpenXM");
Block_size = 2
The input message = OpenXM
20336
25966
22605
0
 
[4113338,3276482,4062967,0]
[357] decrypt(@@);
Block_size = 2
The input message to decrypt 
= [4113338,3276482,4062967,0]
20336
25966
22605
0
 
[OpenXM,[79,112,101,110,88,77]]

    

文字列 ``OpenXM'' を encrypt で暗号化する. 結果は [4113338,3276482,4062967,0] である. これを入力として, decrypt を呼び出すと, 文字列 ``OpenXM'' を復元できる.

encrypt はあたえらた文字列をまず アスキーコードの列に 変換し, それをブロックに分割してから, 各ブロック $m$ の $m^e \ {\rm mod}\,n$ を計算して暗号化する. 20336, 25966, 22605 は各ブロックの $m$ の値である. なお下のプログラムの PP が $p$, QQ が $q$, EE が $e$, DD が $d$(秘密鍵) にそれぞれ対応する.

この実行例では, $p=1231$, $q=4567$, $e=65537$, $d=3988493$ を利用している.

以下の変数への値の設定プログラムと関数を集めたファイルが rsa.rr である.

PP=1231$
QQ=4567$
EE=65537$
DD=3988493$
/* 
    PP = 1231, QQ=4567, N=PP*QQ,  N'=(PP-1)*(QQ-1)
    EE = 65537, (gcd(EE, N') = 1),
    DD = 3988493, ( DD*EE = 1 mod N').
 (These values are taken from the exposition on RSA at
  http://www8.big.or.jp/%7E000/CyberSyndrome/rsa/index.html)
 (EE,N) is the public key.
  DD is the private key.  PP, QQ, N' should be confidential
*/

def naive_encode(S,P,N) {
  /* returns S^P mod N */
  R = 1;
  for (I=0; I<P; I++) {
    R = (R*S) % N;
  }
  return(R);
}

def encode(X,A,N) {
  R = 1; P = X;
  while (A != 0) {
    if (A % 2) {
      R = R*P % N;
    }
    P = P*P % N;
    A = idiv(A,2);
  }
  return(R);
}

def encrypt(M) {
   extern EE,PP,QQ;
   E =  EE; N= PP*QQ;
   Block_size = deval(log(N))/deval(log(256));
   Block_size = pari(floor,Block_size);
   
   print("Block_size = ",0); print(Block_size);
   print("The input message = ",0); print(M);
   M = strtoascii(M);
   L = length(M);
   /* Padding by 0 */
   M = append(M,
        vtol(newvect((idiv(L,Block_size)+1)*Block_size-L)));
   L = length(M);  

   C = [ ];  S=0;
   for (I=1; I<=L; I++) {
     S = S*256+M[I-1];
     if (I % Block_size == 0) {
       print(S);
       S = encode(S,E,N);
       C = append(C,[S]);
       S = 0;
     }
   }
   print(" ");
   return(C);
}

def decrypt(M) {
   extern DD, PP, QQ;
   D = DD; N = PP*QQ;
   Block_size = deval(log(N))/deval(log(256));
   Block_size = pari(floor,Block_size);
   
   print("Block_size = ",0); print(Block_size);
   print("The input message to decrypt = ",0); print(M);
   L = length(M);  

   C = [ ]; 
   for (I=0; I<L; I++) {
     S = encode(M[I],D,N);
     print(S);
     C1 = [ ];
     for (J=0; J<Block_size; J++) {
       S0 = S % 256;
       S = idiv(S,256);
       if (S0 != 0) {
         C1 = append(C1,[S0]);
       }
     }
     C = append(C,reverse(C1));
   }
   print(" ");
   return([asciitostr(C),C]);
}
end$

encode(X,A,N) は, ${\tt X}^{\tt A} \ {\rm mod}\,{\tt N}$ を計算する関数である. native_encode(X,A,N) は 定義どおりにこの計算をする関数である. この関数をためしてみればわかるように, 工夫してこの計算をしないと大変な時間がかかる. A を2進展開して計算しているのが, encode(X,A,N) である. 実行時間を比べてみてほしい.

A を2進展開し

$$\sum a_i 2^i ,\quad (a_i = 0\, \mbox{or}\, 1)$$

なる形にあらわすと,

$${\tt X}^{\tt A} = \prod_{i \,:\, a_i \not= 0} {\tt A}^{2^i}$$

とかける. encode(X,A,N) では, ${\tt A}$, ${\tt A}^2$, ${\tt A}^{4}$, $\ldots$ を ${\tt N}$ でわった余りを 順番に計算して変数 P にいれている. あとは, 2進展開を利用して

$${\tt X}^{\tt A} \ {\rm mod}\,{\tt N} = \prod_{i \,:\, a_i \not= 0} {\tt A}^{2^i} \ {\rm mod}\,{\tt N}$$

を計算している.

encrypt では, あたえらた文字列をまずアスキーコードに変換して, 変数 M にいれている. Block_size を $b$ とするとき, まず,

$${\tt M[0]} 256^{b-1} + {\tt M[1]} 256^{b-2} + \cdots +{\tt M[b-1]} 256^0$$

を変数 S に代入し, この S に対して, ${\tt S}^{\tt E} \ {\rm mod}\,{\tt N}$ を計算する. この操作を各ブロック毎に繰り返す.

decrypt は encrypt とほぼ同様の操作なので 説明を省略する.

さて次の問題として, RSA 暗号化システムのための 公開鍵 $(n,e)$ および秘密鍵 $d$ を生成する問題がある. 次のプログラム rsa-keygen.rr は, これらの数を生成し, 変数 EE, DD などに設定する.

def rsa_keygen(Seed) {
  extern PP,QQ,EE,DD;
  random(Seed);
  do {  
    P = pari(nextprime,Seed); 
    Seed = Seed+P;
    Q = pari(nextprime,Seed);
    PP = P;
    QQ = Q;
    Phi = (P-1)*(Q-1);
    E = 65537;  
    Seed = Seed+(random()*Q % Seed);
  } while (igcd(E,Phi) != 1);
  EE = E;
  DD =inv(EE,Phi);
  print("Your public key (E,N) is ",0); print([EE,PP*QQ]);
  print("Your private key D is ",0); print(DD);
  return([PP,QQ,EE,DD]);
}
end$

次の例は, $2^{128} = 340282366920938463463374607431768211456$ 程度の 大きさの素数を $2$ 個生成して, RSA の公開鍵, 秘密鍵 を作る例である. なお, この程度の大きさの素数の積は最新の理論とシステムを用いると容易 に因数分解可能である.

[355] load("rsa.rr")$
[356] load("rsa-keygen.rr")$
[359] rsa_keygen(2^128);
Your public key (E,N) is [65537,
231584178474632390847141970017375815766769948276287236111932473531249232711409]
Your private key D is 
199618869130574460096524055544983401871048910913019363885753831841685099272061

[340282366920938463463374607431768211507,
680564733841876926926749214863536422987,
65537,
199618869130574460096524055544983401871048910913019363885753831841685099272061]
[360] encrypt("Risa/Asir");
Block_size = 32
The input message = Risa/Asir
37275968846550884446911143691807691583636835905440208377035441136500935229440
 
[146634940900113296504342777649966848592634201106623057430078652022991264082696]
[361] decrypt(@@);
Block_size = 32
The input message to decrypt = 
[146634940900113296504342777649966848592634201106623057430078652022991264082696]
37275968846550884446911143691807691583636835905440208377035441136500935229440
 
[Risa/Asir,[82,105,115,97,47,65,115,105,114]]

高速に安全な公開鍵 $(n,e)$ および秘密鍵 $d$ を生成する問題は, RSA 暗号ファミリを利用するうえでの一つの中心的問題である. たとえば, $p-1$, $q-1$ が小さい素数の積に分解する場合は, 比較的高速な $n$ の素因数分解法が知られている. つまりこのような $(p,q)$ から生成した 鍵はこの素因数分解法の攻撃に対して脆弱である. 上の関数 rsa_keygen はこのような攻撃に対する脆弱性がないかの チェックをしていない. その他, さまざまな攻撃法に対する, 脆弱性がないかのチェックが必要となる.

Risa/Asir は, 楕円曲線の定義する可換群をもちいる暗号系である, 楕円暗号系に関して, 安全なこれらのパラメータを生成する システムの基礎部分として実際に利用されている. Risa/Asir に組み込まれている, 大標数有限体の計算機能および 高速な 1 変数多項式の計算機能はこれらに必要な機能として開発された.

問題 16.2   上のプログラムでは, 文章をブロックに分けてから, RSA 暗号化している. 1 byte づつ暗号化すると比較的容易に暗号が解読できる. その方法を考察せよ.

問題 16.3   公開鍵 $(e,n)=(66649,2469135802587530864198947)$ を用いて, 関数 encrypt で, ある文字列を変換したら,
[534331413430079382527551,486218671433135535521840]
を得た. どのような文字列だったか?