🔥

[Go] 多倍長整数を使ってRSA暗号を作る

2021/12/11に公開

この記事は法政大学　Advent Calendar 2021 11日目の記事です。GoでRSA暗号を実装し、Goでの大きな整数の扱い方を理解することを目的にします。

多倍長整数

多倍長整数は64ビットを超える巨大な整数を扱える整数型です。

固定長の整数はコンピュータ上で高速に計算することができます。しかし、固定長整数の精度では暗号などの大きな数値を扱うには不十分な場合があります。

多重長整数はビット長を動的に拡張することで、メモリに余裕がある限り大きな数値を扱うことができます。多重長整数は、各言語で以下のようにサポートされています。

Pythonは標準でサポート
JavaのBigInteger
C++のgmp
Goの"math/big"(今回利用する)

Goの整数

Goの整数は64ビット（int64,unit64）が上限です。

package main

const A = 1 << 63
const B = 1 << 64

func main() {
	var x uint64
	x = A // OK
	x = B // constant 18446744073709551616 overflows uint64
}

さらに定数は次のように256ビットで表現されなければなりません。

Represent integer constants with at least 256 bits.

https://go.dev/ref/spec#Constants

Goの多倍長整数

Goには標準ライブラリの"math/big"で多倍長整数を扱うことができます。64ビットを超える整数を扱うために必要です。

https://pkg.go.dev/math/big

"math/big"は大きく分けて3つの構造体が定義されています。

big.Int 任意の整数
big.Rat 任意の有理数
big.Float 任意の実数

この記事ではbig.Intを扱います。

https://pkg.go.dev/math/big#Int

bit.Intの基本

初期化は次のように行います。NewIntはポインタを返します。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var x *big.Int
	x = big.NewInt(64)
	fmt.Println(x) // 64
}

Stringerを実装しているので、fmt.Printlnの引数にできます。big.Intは全てのメソッドがポインタレシーバとなっているのでコピーは発生しません。

NewIntは引数が64ビットである必要があります。引数のビット長には制限がありますが、以下のように明らかに64ビット以上の計算をしてもオーバーフローしません。

package main

import (
	"fmt"
	"math"
	"math/big"
)

func main() {
	a := big.NewInt(math.MaxInt64)
	b := big.NewInt(math.MaxInt64)
	a.Mul(a, b)
	fmt.Println(a) // 85070591730234615847396907784232501249
}

四則演算と剰余演算

次のように書きます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var a *big.Int
	var b *big.Int

	a = big.NewInt(10)
	b = big.NewInt(2)

	a.Add(a, b)　　　　　　　　// 加算
	fmt.Println(a) // 12

	a.Sub(a, b)    // 減算
	fmt.Println(a) // 10

	a.Mul(a, b)    // 乗算
	fmt.Println(a) // 20

	a.Div(a, b)    // 除算（商のみ）
	fmt.Println(a) // 10

	a.Mod(a, b)    // 剰余
	fmt.Println(a) // 0
}

除算（商＋余り）

除算で商と余りが必要な場合、DivModを使用します。第三引数には*big.Int型の変数を指定します。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var a *big.Int
	var b *big.Int

	a = big.NewInt(10)
	b = big.NewInt(3)

	m := big.NewInt(0)
	a.DivMod(a, b, m)
	fmt.Println(a) // 3
	fmt.Println(m) // 1
}

aは商、mは余りになります。

冪乗

冪乗の場合、第三引数に結果をpで割った数にするかどうかを指定できます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var a *big.Int
	var b *big.Int
	var p *big.Int

	a = big.NewInt(5)
	b = big.NewInt(2)
	p = big.NewInt(7)

	a.Exp(a, b, nil)
	fmt.Println(a) // 25

	a = big.NewInt(5)
	b = big.NewInt(2)

	a.Exp(a, b, p)
	fmt.Println(a) // 4
}

第三引数の指定は暗号において重要になります。

乗法逆元

最後ですが、乗法逆元を計算できます。乗法逆元とは

A\times E \equiv 1 \mod p

であるようなEのことですが、今は何に使うのかわからなくても大丈夫です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var a *big.Int
	var p *big.Int
	var e *big.Int

	a = big.NewInt(5)
	p = big.NewInt(7)
	e = big.NewInt(0)

	e.ModInverse(a, p)
	fmt.Println(e) // 3

	a.Mul(a, e)
	a.Mod(a, p)
	fmt.Println(a) // 1
}

その他に最大公約数を計算できます。

RSA暗号

RSA暗号は公開鍵暗号のひとつです。アルゴリズムが非常に簡単でSSL/TLSや署名など多くの場面で利用されています。

RSA暗号は暗号や復号のときに非常に大きな数で冪乗を計算をすることになるため、多倍長整数が必須です。今回は部分的に多倍長整数を利用してRSA暗号を実装します。

アルゴリズム

実際にアルゴリズムを見てみましょう。アルゴリズムは次の３つから構成されます。

鍵生成フェーズ 公開鍵、秘密鍵やその他のパラメタを前準備する
暗号化フェーズ 公開鍵で暗号化する
復号フェーズ 秘密鍵で復号する

それでは、RSA暗号のアルゴリズムを記述します。なお、平文というのは暗号化されていない元の値のことです。簡単のため、安全性的に定義が厳密でない部分があります。

鍵生成フェーズ

アリスは素数 $p$ と $q$ を生成する。
アリスは $n=pq$ と $s=lcm(p-1,q-1)$ を計算する。
アリスは $s$ と互いに素でかつ $s$ より小さい数 $e$ を選ぶ。
アリスは $d=(\frac{1}{e}\ mod\ s)$ を計算する。 $\frac{1}{e}$ は $e$ の乗法逆元である。
アリスは秘密鍵を $d$ を公開鍵 $e,n$ として、 $e,n$ を公開する。

暗号化フェーズ

ボブはアリスに送りたいデータを平文 $m$ とする。 $c=m^e\ mod\ n$ を計算して、 $c$ をアリスに送る。

復号フェーズ

アリスは $m=c^d\ mod\ n$ を計算して、 $m$ を出力する。

秘密鍵はアリスしか知らず、ボブのcを復号できるのはアリスだけです。

実装

実装は次のようになります。ただし、簡単のために素数は固定しており、安全ではありません。

package main

import (
	"fmt"
	"math/big"
)

type PublicKey struct {
	N *big.Int
	E *big.Int
}

type PrivateKey struct {
	D *big.Int
	N *big.Int
}

func GCD(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return GCD(b, a%b)
}

func LCM(a, b int64) int64 {
	return (a * b) / GCD(a, b)
}

func getCoprime(x int64) int64 {
	var res int64
	for i := int64(2); i < x; i++ {
		if GCD(x, i) == 1 {
			res = i
			break
		}
	}
	return res
}

func GenKey(p, q int64) (*PublicKey, *PrivateKey) {
	N := big.NewInt(p * q)
	s := big.NewInt(LCM(p-1, q-1))         // p-1とq-1の最小公倍数s
	E := big.NewInt(getCoprime(s.Int64())) // sと互いに素な数e
	D := big.NewInt(0)
	D.ModInverse(E, s)                         // d = e^-1 mod s
	return &PublicKey{N, E}, &PrivateKey{D, N} // 公開鍵、秘密鍵
}

func Encrypt(pk *PublicKey, m *big.Int) *big.Int {
	c := big.NewInt(0)
	m.Mod(m, pk.N) // Nを超えないようにする
	return c.Exp(m, pk.E, pk.N) // c = m ^ e mod n
}

func Decrypt(sk *PrivateKey, c *big.Int) *big.Int {
	m := big.NewInt(0)
	c.Mod(c, sk.N) // Nを超えないようにする
	return m.Exp(c, sk.D, sk.N) // m = c ^ d mod n
}

func main() {
	p := int64(7727)
	q := int64(4463)
	pk, sk := GenKey(p, q)

	m := big.NewInt(75)
	cipherText := Encrypt(pk, m)
	result := Decrypt(sk, cipherText)
	fmt.Println(result) // 75
}

result==m　になっていれば復号成功です！

おわりに

big.Intを使ってRSA暗号を実装しました。標準ライブラリで多倍長整数が扱えるのは標準ライブラリが強力なGoならではだと思いました。

参考文献