I was reading a blog post, A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography, on Cloudflare’s blog. The section titled “A toy RSA algorithm” was of particular interest to me. I decided to try programming the RSA algorithm in Go. I also referenced the Wikipedia page on RSA Cryptography when I couldn’t fully understand something on the blog.

If you want to try this with your own prime numbers, you should read my post on Generate Randomness with OpenSSL to get started. Also, you’ll need to be familiar with the Go Package, Big.

Public/Private key encryption uses Modular exponentiation, which has a really neat property. You take the number you want to encrypt and use the public key as the exponent. If the sum of the exponent is greater than the λ(n), where n is p * q, you take the modulus and multiply the remainder by the number you’re encrypting. Then to decrypt the value, you do the same thing but you use the private key as the exponent.

For example, given b = 5, e = 3 and m = 13, the solution c = 8 is the remainder of dividing 53 = 125 by 13.

Code

Below is the Go code I wrote.

package main

import (
	"fmt"
	"math/big"
)

func main() {
	var plainText = "ACLOUD"

	// 1. Choose two distinct prime numbers, p and q
	// 4. Choose any number 1 < e < 780 that is coprime to 780.
	var p, q, e big.Int
	p.SetString("149167516042398723525996758773222137472281596223800479849551540351321034501792773631372499057699531070744472669665053159335520543433504855361286774214076723836802002410302647566892453660983455011781051513658262625786070114418438980094403935311556559954980492420486666809425360953717676668351593906539161639037", 10)
	q.SetString("144085140269927785077965383593233311382753811804186408035700201265790515428737655822413298633470907606520085298502109809391457262279140832852147401148057790649935817654787884130381388430766729931091479265582830015230104977199529156176249346200528785749827308279438469063610414582644920648362498649191416059531", 10)
	e.SetString("164980429110169948421905422637425619464250398994123121994248535750968988933737559448128821647637771319856056232350463890336363482800239649343244642618554310520539501215821564433169870438486644707957411182704673414335171493308674958494165428598801508076047085838657336277080545578857427910086984801408944113217", 10)

	// 2. Compute n = pq.
	// n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.
	// n is released as part of the public key.
	var n big.Int
	n = *n.Mul(&p, &q)

	// 3. Compute the Carmichael's totient function of the product as λ(n) = lcm(p − 1, q − 1) giving
	var lcm, lcmp, lcmq, i big.Int
	i.SetInt64(1)
	lcmp.Sub(&p, &i)
	lcmq.Sub(&q, &i)
	lcm.Mul(lcm.Div(&lcmp, lcm.GCD(nil, nil, &lcmp, &lcmq)), &lcmq)

	// 5. Compute d, the modular multiplicative inverse of e (mod λ(n)) yielding,
	var d big.Int
	d.ModInverse(&e, &lcm)

	fmt.Println("Input")
	fmt.Println("=====")
	fmt.Printf("%s\n\n", plainText)
	fmt.Println("Parameters")
	fmt.Println("==========")
	fmt.Printf("p:\t%s\n", p.String())
	fmt.Printf("q:\t%s\n", q.String())
	fmt.Printf("e:\t%s\n", e.String())
	fmt.Printf("n:\t%s\n", n.String())
	fmt.Printf("lcm:\t%s\n", lcm.String())
	fmt.Printf("inv:\t%s\n\n", d.String())

	// Encrypt
	fmt.Println("input\toutput")
	fmt.Println("-----\t------")
	var l, t big.Int
	var ciphertext []string
	for _, c := range plainText {
		l.SetInt64(int64(c))
		t.SetInt64(int64(c))
		t.Exp(&l, &e, &n)
		fmt.Printf("%s\t%s\n", l.String(), t.String())
		ciphertext = append(ciphertext, t.String())
	}
	fmt.Printf("\nCiphertext: %s\n\n", ciphertext)

	fmt.Println("input\toutput")
	fmt.Println("-----\t------")
	var decode []byte
	// Decrypt
	for _, k := range ciphertext {
		l.SetString(k, 10)
		t.Exp(&l, &d, &n)
		fmt.Printf("%s\t%s\n", l.String(), t.String())
		decode = append(decode, byte(t.Int64()))
	}
	fmt.Printf("\nDecrypted: %s\n", string(decode))
}

Conclusion

Writing about a topic that I’m not entirely familiar with is difficult. It’s such an interesting topic and I’m going to keep learning more about it.

Sample Output

Input
=====
ACLOUD

Parameters
==========
p:	149167516042398723525996758773222137472281596223800479849551540351321034501792773631372499057699531070744472669665053159335520543433504855361286774214076723836802002410302647566892453660983455011781051513658262625786070114418438980094403935311556559954980492420486666809425360953717676668351593906539161639037
q:	144085140269927785077965383593233311382753811804186408035700201265790515428737655822413298633470907606520085298502109809391457262279140832852147401148057790649935817654787884130381388430766729931091479265582830015230104977199529156176249346200528785749827308279438469063610414582644920648362498649191416059531
e:	164980429110169948421905422637425619464250398994123121994248535750968988933737559448128821647637771319856056232350463890336363482800239649343244642618554310520539501215821564433169870438486644707957411182704673414335171493308674958494165428598801508076047085838657336277080545578857427910086984801408944113217
n:	21492822472685723225971092763481035152615803048791997443411526236367617001487022460390333335618159961118272929510348392382740589675703955103519625084601313401907426903049123212288872409721446124381358216098068941207675223554919782200115512689141254926303503483012507214839151375968970428813185986541920789711974041844739565401379879902900862059908032914634993913153534285307164462238549134872052677513405544827095433771902477753039759989145513465251878350547195970739793516344503470499194849033448960611889599856751314932679821732556837558344099008819799981626152243543474108806552380191760938572375175493737925511647
lcm:	10746411236342861612985546381740517576307901524395998721705763118183808500743511230195166667809079980559136464755174196191370294837851977551759812542300656700953713451524561606144436204860723062190679108049034470603837611777459891100057756344570627463151751741506253607419575687984485214406592993270960394855840394594213619446387958880267203305526498753303503512634141271845026456154009352709133439911117553074915437901867657392156391091716433888519222087592530728126527848139706469400960503470849387834508534538755111145831823320469434711036722863653857317960672221421774486466758302327699170627830541469003673906540
inv:	3607114346104970613977568286381383833256557028459714559751847616783719087493959723001472478702475974678691405023277745016553928376909658098945432336796411714239743722884815866922994142752121757477692092690133281937800739344619580715137574480057645065814468572291250188919216725057384190902049742115952044906941437564909236129430695609678701972331505122404097715822601289277795341273747887221876565863841158366141321290447294308570657031831517086212696246168639446731909085367452806597789276312108857019313809186032455750337243106821276067126330806726470366906825276775727328029075015896670207297594978053572388099993

input	output
-----	------
65	15548774780867264824353843603935252849744506377033844469756893098856931499779217669152218706433846407867724111120882896843618640141447097842219502712200075640041052519290495263499518762189842173959578540638627272366601090296239393220581590693028629711475316221546201715924981040492369416412996710066204148270729147306961689274921893751633212982381344411234962844923147414290348865622566732216425126233044348472891889770491137529410503828271602712039900034932232149019545933791839479942488689532039825104935808309619716081463126010838714275394044158876516221054023271308638477916628029917593913819714148151022935882396
67	2984959888243255019440213752543270102692024056976049720968396015677907415064404195476772854510750356491718960247121275847364533629744797269087848471768462847169145745194943467247955313963731433037755523004380319020430671350905725495176396109086341117596357894041715354448674027851122131599928046915734738159635788372584484492231072470449225814992948568511096438940404426453232157603624778045987855225929192665497347499285437641023036998286131698365502843294992544693561695234122807115624596084972145465677760574638365602239516282673594581843884355626145872426592189802973747049884698196258642226757252766425438312728
76	3710005346585339569488877576646935982402110325071540908015132249416443097772196789479077334924814900686204158662681195799590000031506002176290942669629790461469445030467103699096753446734777904513582842917617595868462987085551476425374236718326302275182712561765735018381933394425798318431135293242454041619657056492518373532709691246001338599323994097136182132823773029110166268581713051877523740853796314522187653796775707522009911921585150602023519815864729055561534582099160470846810799113361345164389255015669462007065242344318081781019832660539591827350305347503573932894513042739690656979086791340858254764946
79	19686313858940226280785941768930487546568003727925801268219206072802174835545812592244966962209794085494534639124519853801804987559182715728216555188415167933212400522450827311421640098030303394499357529392977647007028573318155352899234656774054319826600650911825607918614451121817678487877790299440699725345805366703459179963049961708513897489529323899224317170998691746302835633765693598989162362147063237656231132131297691446430015629265011716092366800389006435117757056910387983661854543425212479802386298485699568607505001774862056264276909860641694834408406845856242341711069367737498458965082196461652291854548
85	546454132356887277750998915940675421727043353468469737558202554708994818801095032499401863137351885039471194693389558435487549018463995769052055198501342496957876967764578293120552053591831641250342673471303294730243202225151056491814055949957933092192338732645330338834620394458336579854627009960519114398485269460836846677193368007770871372031778917078338190556710446964975505953080936394722068689243780285368988101074071796516124816560893551742425043291336890237920066031661609502842009070606477754898623674333092689114423273626818970995632235716332376436845623589676622319616879944545861115665522921391507598844
68	7774170115880796109308369705409797428121845385182103192310009446211170426299311083942694545246490530412409062666508550209207321559883140256769494466622528052893675373517562988137201132690117172586675162279042803623048156005765143476760591394348850334844663690563471160259796581677982784670421455976743895033208907133903802097949521295108377594574240617198227816649953378760259831898451969840196470362198758474496854875113586698117632572589684835202716252504672640042418023991273151670229965202309402718021470232651242681669522767231722973348936792201794452154087477554346908897528967727663287791684412102215819742811

Ciphertext: [15548774780867264824353843603935252849744506377033844469756893098856931499779217669152218706433846407867724111120882896843618640141447097842219502712200075640041052519290495263499518762189842173959578540638627272366601090296239393220581590693028629711475316221546201715924981040492369416412996710066204148270729147306961689274921893751633212982381344411234962844923147414290348865622566732216425126233044348472891889770491137529410503828271602712039900034932232149019545933791839479942488689532039825104935808309619716081463126010838714275394044158876516221054023271308638477916628029917593913819714148151022935882396 2984959888243255019440213752543270102692024056976049720968396015677907415064404195476772854510750356491718960247121275847364533629744797269087848471768462847169145745194943467247955313963731433037755523004380319020430671350905725495176396109086341117596357894041715354448674027851122131599928046915734738159635788372584484492231072470449225814992948568511096438940404426453232157603624778045987855225929192665497347499285437641023036998286131698365502843294992544693561695234122807115624596084972145465677760574638365602239516282673594581843884355626145872426592189802973747049884698196258642226757252766425438312728 3710005346585339569488877576646935982402110325071540908015132249416443097772196789479077334924814900686204158662681195799590000031506002176290942669629790461469445030467103699096753446734777904513582842917617595868462987085551476425374236718326302275182712561765735018381933394425798318431135293242454041619657056492518373532709691246001338599323994097136182132823773029110166268581713051877523740853796314522187653796775707522009911921585150602023519815864729055561534582099160470846810799113361345164389255015669462007065242344318081781019832660539591827350305347503573932894513042739690656979086791340858254764946 19686313858940226280785941768930487546568003727925801268219206072802174835545812592244966962209794085494534639124519853801804987559182715728216555188415167933212400522450827311421640098030303394499357529392977647007028573318155352899234656774054319826600650911825607918614451121817678487877790299440699725345805366703459179963049961708513897489529323899224317170998691746302835633765693598989162362147063237656231132131297691446430015629265011716092366800389006435117757056910387983661854543425212479802386298485699568607505001774862056264276909860641694834408406845856242341711069367737498458965082196461652291854548 546454132356887277750998915940675421727043353468469737558202554708994818801095032499401863137351885039471194693389558435487549018463995769052055198501342496957876967764578293120552053591831641250342673471303294730243202225151056491814055949957933092192338732645330338834620394458336579854627009960519114398485269460836846677193368007770871372031778917078338190556710446964975505953080936394722068689243780285368988101074071796516124816560893551742425043291336890237920066031661609502842009070606477754898623674333092689114423273626818970995632235716332376436845623589676622319616879944545861115665522921391507598844 7774170115880796109308369705409797428121845385182103192310009446211170426299311083942694545246490530412409062666508550209207321559883140256769494466622528052893675373517562988137201132690117172586675162279042803623048156005765143476760591394348850334844663690563471160259796581677982784670421455976743895033208907133903802097949521295108377594574240617198227816649953378760259831898451969840196470362198758474496854875113586698117632572589684835202716252504672640042418023991273151670229965202309402718021470232651242681669522767231722973348936792201794452154087477554346908897528967727663287791684412102215819742811]

input	output
-----	------
15548774780867264824353843603935252849744506377033844469756893098856931499779217669152218706433846407867724111120882896843618640141447097842219502712200075640041052519290495263499518762189842173959578540638627272366601090296239393220581590693028629711475316221546201715924981040492369416412996710066204148270729147306961689274921893751633212982381344411234962844923147414290348865622566732216425126233044348472891889770491137529410503828271602712039900034932232149019545933791839479942488689532039825104935808309619716081463126010838714275394044158876516221054023271308638477916628029917593913819714148151022935882396	65
2984959888243255019440213752543270102692024056976049720968396015677907415064404195476772854510750356491718960247121275847364533629744797269087848471768462847169145745194943467247955313963731433037755523004380319020430671350905725495176396109086341117596357894041715354448674027851122131599928046915734738159635788372584484492231072470449225814992948568511096438940404426453232157603624778045987855225929192665497347499285437641023036998286131698365502843294992544693561695234122807115624596084972145465677760574638365602239516282673594581843884355626145872426592189802973747049884698196258642226757252766425438312728	67
3710005346585339569488877576646935982402110325071540908015132249416443097772196789479077334924814900686204158662681195799590000031506002176290942669629790461469445030467103699096753446734777904513582842917617595868462987085551476425374236718326302275182712561765735018381933394425798318431135293242454041619657056492518373532709691246001338599323994097136182132823773029110166268581713051877523740853796314522187653796775707522009911921585150602023519815864729055561534582099160470846810799113361345164389255015669462007065242344318081781019832660539591827350305347503573932894513042739690656979086791340858254764946	76
19686313858940226280785941768930487546568003727925801268219206072802174835545812592244966962209794085494534639124519853801804987559182715728216555188415167933212400522450827311421640098030303394499357529392977647007028573318155352899234656774054319826600650911825607918614451121817678487877790299440699725345805366703459179963049961708513897489529323899224317170998691746302835633765693598989162362147063237656231132131297691446430015629265011716092366800389006435117757056910387983661854543425212479802386298485699568607505001774862056264276909860641694834408406845856242341711069367737498458965082196461652291854548	79
546454132356887277750998915940675421727043353468469737558202554708994818801095032499401863137351885039471194693389558435487549018463995769052055198501342496957876967764578293120552053591831641250342673471303294730243202225151056491814055949957933092192338732645330338834620394458336579854627009960519114398485269460836846677193368007770871372031778917078338190556710446964975505953080936394722068689243780285368988101074071796516124816560893551742425043291336890237920066031661609502842009070606477754898623674333092689114423273626818970995632235716332376436845623589676622319616879944545861115665522921391507598844	85
7774170115880796109308369705409797428121845385182103192310009446211170426299311083942694545246490530412409062666508550209207321559883140256769494466622528052893675373517562988137201132690117172586675162279042803623048156005765143476760591394348850334844663690563471160259796581677982784670421455976743895033208907133903802097949521295108377594574240617198227816649953378760259831898451969840196470362198758474496854875113586698117632572589684835202716252504672640042418023991273151670229965202309402718021470232651242681669522767231722973348936792201794452154087477554346908897528967727663287791684412102215819742811	68

Decrypted: ACLOUD