Simple RSA Algorithm

rsa.go

package main

import (
	"fmt"
	"math/big"
	"time"
	mRand "math/rand"
	cRand "crypto/rand"
)

func randPrime() (*big.Int){
	bitLength:=31+mRand.Intn(2) //31 32
	p, _ := cRand.Prime(cRand.Reader, bitLength)	
	return p
}

func phyCal(p *big.Int,q *big.Int) (*big.Int){
	one := big.NewInt(1)
	pMinus1 := new(big.Int).Sub(p, one)
	qMinus1 := new(big.Int).Sub(q, one)
	phy := new(big.Int).Mul(pMinus1, qMinus1)
	return phy
}

func egcd(a *big.Int,b *big.Int) (*big.Int,*big.Int,*big.Int){
	x, y, u, v := big.NewInt(0),big.NewInt(1),big.NewInt(1),big.NewInt(0)
	for a.Cmp(big.NewInt(0))!=0 {
		q, r := new(big.Int).Div(b,a),new(big.Int).Mod(b,a)
		m, n := new(big.Int).Sub(x,new(big.Int).Mul(u,q)), new(big.Int).Sub(y,new(big.Int).Mul(v,q))
		b, a, x, y ,u ,v = a, r, u, v, m,n
	}
	gcd := b
	return gcd, x, y
}

func modInv(a,m *big.Int) (*big.Int){
	gcd, x, _:=egcd(a,m)
	if gcd.Cmp(big.NewInt(1))!=0{
		return big.NewInt(-1)
	}else{
		return new(big.Int).Mod(x,m)
	}
}

func RSAEncrypt(msg, e, n *big.Int) (*big.Int){
	return new(big.Int).Exp(msg,e,n)
}

func RSADecrypt(cipher, d, n *big.Int) (*big.Int){
	return new(big.Int).Exp(cipher,d,n)
}

func main() {
	mRand.Seed( time.Now().UTC().UnixNano())

	var p *big.Int
	var q *big.Int

	p = randPrime()
	q = randPrime()

	for !p.ProbablyPrime(128) {
		p = randPrime()
	}

	for !q.ProbablyPrime(128) {
		q = randPrime()
		for p.Cmp(q)==0{
			q = randPrime()
		}
	}

	fmt.Println("p\t",p)
	fmt.Println("q\t",q)

	n := new(big.Int).Mul(p, q)
	fmt.Println("n\t",n)

	phy:=phyCal(p,q)
	fmt.Println("phy(n)\t",phy)

	e:=big.NewInt(65537)
	fmt.Println("e\t",e)

	_, _, d := egcd(phy,e)

	if d.Cmp(big.NewInt(0))==-1{
		d.Add(d,phy)
	}
	fmt.Println("d\t",d)

	fmt.Println("Private key\t( n = ",n,",d =",d,")")
	fmt.Println("Public key\t( n = ",n,",e =",e,")")

	m := new(big.Int).Mul(big.NewInt(55010923),big.NewInt(55011222))
	fmt.Println("m\t",m)

	c := RSAEncrypt(m,e,n)
	fmt.Println("c\t",c)

	m_ := RSADecrypt(c,d,n)
	fmt.Println("m'\t",m_)
}