公開鍵暗号の1つであるRSA暗号をGoで実装してみる

Kohei Kondo2020年7月30日4 min read

#Go #RSA #Crypt

注意: ところどころ簡素化してあるところはあります

公開鍵暗号とは

公開鍵暗号Public-key cryptography 暗号化復号暗号方式

流れ

2種類の素数p,qを準備する(p != q)
各素数の積 Nを計算 (p * q)
各素数から1を引いた値の最小公倍数Lを計算 lcm((p-1) * (q-1))
L未満でその値と互いに素な任意の値 Eを準備(公開鍵)
Lを法として公開鍵との積が1となる任意の値 Dを準備（秘密鍵）
EとNを使い暗号化
DとNを使い復号

2種類の素数p,qを準備する(p != q)

本来であれば、ある程度大きい素数を疑似乱数生成器で作る必要があるが、今回は学習も兼ねて、2つの値を自身で設定できるようにしてある。

※また、学習のためなので int 型としているが、本来はもっと大きな数値を扱える型としたほうが良い

var p, q 
int fmt.Println("enter two defferent primary numbers")
fmt.Println("like 17 19")
fmt.Scan(&p, &q)

各素数の積Nを計算 (p * q)

N = p*q

※このNは公開情報である

Nが大きい値の際に、素因数分解が現実的な時間で解読不可能なことを利用している。

(計算量的安全性)

Nの値としての推奨は 1024–4096ビット(Wikipediaより)

各素数から1を引いた値の最小公倍数Lを計算 lcm((p-1) * (q-1))

秘密鍵と公開鍵を作るためにLを準備する

ユークリッドの互除法を使い計算


L := culcLeastCommonMultiple(p-1, q-1)
func culcLeastCommonMultiple(a, b int) int {
  c := a * b
  if a < b {
    tmp := a  a = b  b = tmp
   }
   r := a % b
   for r != 0 {
     a = b
     b = r
     r = a % b
   }
   return c / b
}

L未満でその値と互いに素な任意の数Eを準備(公開鍵)

gcd(E,L) = 1

こちらは簡易的に、毎回乱数を取得して、それが互いに素か調べて当てはまった場合それを公開鍵とするようにしている。

E := makePublicKey(L)
func makePublicKey(l int)int64 {
  rand.Seed(time.Now().UnixNano())
  r := rand.Intn(l)
  for greatestCommonDivisor(r, l) != 1 {
    r = rand.Intn(l)
  }
  return int64(r)
}

最小公倍数をユークリッドの互除法で取得し、それが1となるまで実行


func greatestCommonDivisor(a, b int) int {
  if a < b {
    tmp := a
    a = b
    b = tmp
  }
  r := a % b
  for r != 0 {
    a = b
    b = r
    r = a % b
  }
  return b
}

Lを法として公開鍵との積が1となる任意の値Dを準備（秘密鍵）

// E*D mod L = 1 となるEを探す

こちらも簡易的に繰り上げ式で対象の値を取得

D := int64(makePrivateKey(E, int64(L)))
func makePrivateKey(e int64, l int64) int64 {
  i := int64(2)
  for i*e%l != 1 {
    i++
  }
  return i
}

Let’s 暗号化

//planText^E mod N

// planText^E mod N

cryptgram := new(big.Int).Exp(big.NewInt(planText), big.NewInt(E), big.NewInt(N))

Let’s 復号

// cryptgram^D mod N

res := new(big.Int).Exp(cryptgram, big.NewInt(D), big.NewInt(N))

全コード

終わりに

今回は小さい数値しか暗号化、復号できませんが。

大枠流れはつかめると思います。

普段何気なく使っているものを、自分で実装するというのは楽しいですね

参考: