代表的な公開鍵暗号であるRSA暗号ですが、
暗号化や復号化の手順自体はかなり簡単で、
プログラムの実装もそこまで苦労することなくできます。

ということで、Rで実際にRSA暗号のコードを書いて、
暗号化や復号化を動かしてみましょう。

Rのコード
実行例
準同型暗号としてのRSA
まとめ

Rのコード

RSA暗号では、まず公開鍵と秘密鍵のペアを生成し、
公開鍵を使ったメッセージの暗号化と、
秘密鍵を使ったメッセージの復号化を行います。

つまり、鍵生成、暗号化、復号化の主に三つの手順があり、
それぞれを実装すれば暗号で遊べることになります。

鍵の生成

どの公開鍵暗号でのそうですが、
鍵の生成は重要なポイントです。

公開鍵と秘密鍵は、特殊な関係になるようにデザインしておきます。

この特別なデザインのおかげで、
別々の鍵で暗号化、復号化を施すと元のメッセージに戻る
という公開鍵暗号の魔法が実現されます。

RSA暗号の場合は、割り算の余りの世界の関係を使って、
鍵のペアを生成します。

鍵の生成コードは下のようになります。

make.key = function(p=11,q=13){
  n = p*q
  phy = (p-1)*(q-1)
  
  e = phy
  while(gcd(phy,e)!=1){
    e = sample(2:phy,1)
  }
  tmp = eEuclideanAlgorithm(-phy,e)
  d = tmp$y
  if(d < 0){
    d = d %% phy
  }
  
  return(list(pub=list(n=n,e=e),sec=list(d=d)))
}

p,qは異なる2つの素数で、
鍵を作るために使われます。

公開鍵はnとeで、
nはp,qの積ですが、
eはほぼランダムに選ばれた数値です。

そして、eとある関係を持つように選ばれた
dが秘密鍵となります。
eとdの関係とは、nのオイラー関数の値phyを法として逆数である
というものです。
平たく言えば、eとdの積をphyで割った余りが1であるということですね。

この逆数を見つけるために拡張版ユークリッド互除法を用いています。

拡張ユークリッドの互除法

拡張ユークリッドの互除法では、
xm+yn = gcd(m,n) となるような
x,yを求めます。

下は拡張ユークリッドの互除法と、
最大公約数を求める通常のユークリッドの互除法のコードです。

eEuclideanAlgorithm = function(m,n){
  r = c(m,n)
  k = NULL
  
  ans = diag(1,2)
  
  while(n != 0){
    R = m %% n
    K = m %/% n
    
    m = n    
    n = R

    ans = ans %*% matrix(c(0,1,1,-K),ncol=2)
  }
  
  return(list(x=ans[1,1],y=ans[2,1]))
}

gcd = function(a, b){
  while(a %% b != 0){
    tmp = b
    b = a %% b
    a = tmp
  }
  return(b)
}

暗号化

鍵さえ作ってしまえば、
RSA暗号の暗号化は非常にシンプルです。

暗号化したいメッセージを数値化して、
公開鍵暗号のeで指定されている回数だけメッセージ同士の積をとって、
nで割った余りを求めます。

とは言え、積を繰り返すと途中で桁数が爆発的に増えてしまうので、
積を取るたびに余りを求めるようにしています。
どちらでも計算結果は変わりませんが、
途中で計算できない桁数になることがあるため、
後者で計算するのが安全でしょう。

RSA.encode = function(m,pub){
  ans = 1
  for(i in 1:pub$e){
    ans = (ans * m) %% pub$n
  }
  return(ans)
  # (m ^ pub$e) %% pub$n
}

復号化

復号化も暗号化とほぼ同様の操作になります。

違いは、積を取る回数が、
公開鍵のeか、秘密鍵のdかの違いだけになります。

RSA.decode = function(m,key){
  ans = 1
  for(i in 1:key$sec$d){
    ans = (ans*m) %% key$pub$n
  }
  return(ans)
  # (m ^ key$sec$d) %% key$pub$n
}

eとdが逆元の関係にあるので、
e回かけてd回かけると丁度1回かける、
つまり、何もしないのと同じ結果になります。

このおかげで、元のメッセージが得られます。

実行例

では、実際に上で実装したRSA暗号を使って、
暗号化、復号化を行ってみましょう。

ここでは、数値の3を暗号化して、
また元に戻すという操作を行ってみます。

  m = 3
  print(paste("original:",m))
  key = make.key()
  
  enc = RSA.encode(m,key$pub)
  print(paste("cryptogram:",enc))
  
  dec = RSA.decode(enc,key)
  print(paste("decoded",dec))

結果は、次のようになりました。
※鍵の生成に乱数を用いているので、
生成された鍵によって、暗号化された数値の値は異なります。

[1] "original: 3"
[1] "cryptogram: 126"
[1] "decoded 3"

元々3という数値が、暗号化されて「126」という数値に置き換えられています。

そのあと、復号化により、元の3が得られていますね。

準同型暗号としてのRSA

暗号には、準同型暗号と呼ばれる種類があり、
暗号文のまま計算できるという特徴を持つものがあります。

RSA暗号もこの準同型暗号の一つで、
暗号化されたメッセージ同士でかけ算を行うことができます。

せっかくなので、実際に試してみましょう。

  m1 = 2
  m2 = 3
  print(paste("originals:",m1,",",m2))
  key = make.key()
  
  e1 = RSA.encode(m1,key$pub)
  e2 = RSA.encode(m2,key$pub)
  print(paste("cryptograms:",e1,",",e2))
  
  mul = e1 * e2
  print(paste(e1,"x",e2,"=",mul))
  
  dec = RSA.decode(mul,key)
  print(paste("decode ",mul,"=",dec))

今回は二つの数値2と3を暗号化します。
そして、暗号化された数字同士をかけ合わせて、
ちゃんと、元の数字のかけ算ができることを確認します。

結果は下のようになりました。

[1] "originals: 2 , 3"
[1] "cryptograms: 128 , 42"
[1] "128 x 42 = 5376"
[1] "decode  5376 = 6"

2と3を暗号化することで、
128と42という暗号を得ました。

これらの暗号化された数字同士をかけ合わせると、
5376という数値をえます。

そして、この5376を復号すると、6が得られました。
これは、元々の数字、2,3のかけ算の結果と一致しています。

このようにRSA暗号では、暗号化された世界でかけ算をすることができて、
その結果は、復号化することで元の世界のかけ算結果に戻すことができます。

まとめ

Rを使って、RSA暗号で遊べるように、
コードを書いてみました。

意外とパッケージなどでの実装が見当たらなかったので、
暗号のコードに触れてみたいという人に使ってもらえれば幸いです。

クイックノート

ちょっとした発見・アイデアから知識の発掘を

【R】RSA暗号を使ってみる

Rのコード

鍵の生成

拡張ユークリッドの互除法

暗号化

復号化

実行例

準同型暗号としてのRSA

まとめ