【Go】RSA暗号を理解するためにサンプルコード書いてみた

概要

• 暗号技術入門 第3版に出てきたRSA暗号を理解するためにサンプルコード書いてみた
• パッケージなどは使わずに内部的な処理の理解を優先した最小限の実装

サンプルコード

package main

import "fmt"

// わかりやすくするため最小の素数を使う
const (
	p, q = 3, 5
)

// Nの生成
func generateN() int {
	n := p * q
	return n
}

// Lの生成
func generateL() int {
	l := (p - 1) * (q - 1)
	return l
}

// Eの生成
// 1 < E < L
// gcd(E, L) = 1
func generateE(l int) int {
	e := 2
	for e < l {
		if gcd(e, l) == 1 {
			break
		}
		e++
	}
	return e
}

// gcd(E, L) = 1を満たしているかをチェック
func gcd(e, l int) int {
	for l != 0 {
		e, l = l, e % l
	}
	return e
}

// Dの生成
// 1 < D < L
// E * D mod L = 1
func generateD(e, l int) int {
	d := 1
	for {
		if (e * d) % l == 1 {
			break
		}
		d++
	}
	return d
}

// 暗号化(復号化にも使用)
// m^e mod n
func modExp(m, e, n int) int {
	result := 1
	for e > 0 {
		if e % 2 == 1 {
			result = (result * m) % n
		}
		m = (m * m) % n
		e /= 2
	}
	return result
}

func main() {
	n := generateN() // 15
	l := generateL() // 8
	e := generateE(l) // 3
	d := generateD(e, l) // 3

	// 平文にはN未満の数値を指定
	target := 8 
	// 暗号化
	encrypted := modExp(target, e, n)
	// 復号化
	decrypted := modExp(encrypted, d, n)
	
	fmt.Println("平文:", target)
	fmt.Println("暗号化:", encrypted)
	fmt.Println("復号化:", decrypted)
}

// 出力
// 平文: 8
// 暗号化: 2
// 復号化: 8