Big Integers and Some Crypto Homomorphic Magic

Big Integers and Some Crypto Homomorphic Magic

In software, we normally use integers that have 32-bit or 64-bit values. But in cryptography, we can be using 1,024, 2,048 and even 4,096-bit values. So, how do we do that? Well, we use Big Integers, and which can be of any size. In this article, we will implement a Paillier homomorphic method using Big Integers. A 2,048-bit value, for example, has this many digits:

32,317,006,071,311,007,300,714,876,688,669,951,960,444,102,669,715,
484,032,130,345,427,524,655,138,867,890,893,197,201,411,522,
913,463,688,717,960,921,898,019,494,119,559,150,490,921,095,088,152,386,448,283,120,630,877,367,300,996,091,750,197,750,389,652,
106,796,057,638,384,067,568,276,792,218,642,619,756,161,838,094,338,476,170,470,581,645,852,036,305,042,887,575,891,541,065,808,
607,552,399,123,930,385,521,914,333,389,668,342,420,684,974,786,564,569,494,856,176,035,326,322,058,077,805,659,331,026,192,708,
460,314,150,258,592,864,177,116,725,943,603,718,461,857,357,598,351,152,301,645,904,403,697,613,233,287,231,227,125,684,710,820,
209,725,157,101,726,931,323,469,678,542,580,656,697,935,045,997,268,352,998,638,215,525,166,389,437,335,543,602,135,433,229,604,
645,318,478,604,952,148,193,555,853,611,059,596,230,656

In Golang, we assign a value to a Big Integer in many ways, such as assigning an integer, byte values, or from an integer string. For integer casting, we can use the format of:

a:=big.NewInt(2)

Note that the value of a will be automatically assigned as a big.Int data type as we have used the assignment operation (:=). For string assignment:

pub.N, _ = new(big.Int).SetString("2220390286", 10)

To multiply two values (a and b) to give c:

c := new(big.Int).Mul(a, b)

To add two values (a and c) to give c:

c := new(big.Int).Add(a, b)

In order to perform a modulo operation of res=a.b (mod n), we have:

c := new(big.Int).Mul(a, b)
res:=new(big.Int).Mod(c, n)

Another typical operator is the inverse modulus of a value (z=v^{-1} (mod n)):

z := new(big.Int).ModInverse(v, n)

Paillier

Adding and scalar multiply

Subtract

Code

The basic data structures for the secret key, public key and ciphertext is:

type (
	PublicKey struct {
		N  *big.Int
		N2 *big.Int
	}

	SecretKey struct {
		PublicKey
		Lambda  *big.Int
		Totient *big.Int
		U       *big.Int
	}
	Ciphertext *big.Int
)

The adding of ciphertext values is achieved through a multiplication of our big integer ciphertext values c=a⋅b (mod n²):

func add(pk PublicKey, a Ciphertext, b Ciphertext) Ciphertext {

	c := new(big.Int).Mul(a, b)
	return (new(big.Int).Mod(c, pk.N2))

}

When we multiply two Paillier ciphertext’s, we actually use an exponential function, and where Mult(a,c)−>c.a (mod n)

func mul(a, c, m *big.Int) *big.Int {

	z := new(big.Int).Exp(c, a, m)
	return (z)
}

When we need to multiply two big integers we do it using a mod operator:

func Mul(x, y, m *big.Int) *big.Int {

	z := new(big.Int).Mul(x, y)

	return z.Mod(z, m)
}

The inverse mod is used in the subtraction operation, and is implemented as:

func Inv(x, m *big.Int) *big.Int {

	z := new(big.Int).ModInverse(x, m)
	return (z)
}

To encrypt the values, we create a random nonce (r) and implemented as:

func encrypt(pk PublicKey, msg *big.Int) *big.Int {

	r, _ := core.Rand(pk.N)

	a := new(big.Int).Add(pk.N, core.One)
	a.Exp(a, msg, pk.N2)
	b := new(big.Int).Exp(r, pk.N, pk.N2) // b = r^N (mod N^2)

	// ciphertext = a*b = (N+1)^m * r^N  (mod N^2)
	c := Mul(a, b, pk.N2)

	return c
}
func L(n, x *big.Int) *big.Int {
	// (x - 1) / n
	b := new(big.Int).Sub(x, big.NewInt(1))
	return b.Div(b, n)
}

To decrypt:

func decrypt(sk SecretKey, c *big.Int) *big.Int {

	// a ≡ c^{lambda(N)}		mod N^2
	a := new(big.Int).Exp(c, sk.Lambda, sk.N2)

	// l = L(ɑ, N)
	ell := L(sk.N, a)

	// m ≡ lu = L(ɑ)*u = L(c^{λ(N)})*u	mod N
	m := Mul(ell, sk.U, sk.N)

	return m
}

Coding

The code is [here]:

package main

import (
	"fmt"
	"math/big"
	"os"

	"github.com/coinbase/kryptology/pkg/core"
)

type (
	PublicKey struct {
		N  *big.Int
		N2 *big.Int
	}

	SecretKey struct {
		PublicKey
		Lambda  *big.Int
		Totient *big.Int
		U       *big.Int
	}
	Ciphertext *big.Int
)

func add(pk PublicKey, a Ciphertext, b Ciphertext) Ciphertext {

	c := new(big.Int).Mul(a, b)
	return (new(big.Int).Mod(c, pk.N2))

}
func encrypt(pk PublicKey, msg *big.Int) *big.Int {

	r, _ := core.Rand(pk.N)

	a := new(big.Int).Add(pk.N, core.One)
	a.Exp(a, msg, pk.N2)
	b := new(big.Int).Exp(r, pk.N, pk.N2) // b = r^N (mod N^2)

	// ciphertext = a*b = (N+1)^m * r^N  (mod N^2)
	c := Mul(a, b, pk.N2)

	return c
}
func L(n, x *big.Int) *big.Int {
	// (x - 1) / n
	b := new(big.Int).Sub(x, big.NewInt(1))
	return b.Div(b, n)
}

func decrypt(sk SecretKey, c *big.Int) *big.Int {

	// a ≡ c^{lambda(N)}		mod N^2
	a := new(big.Int).Exp(c, sk.Lambda, sk.N2)

	// l = L(ɑ, N)
	ell := L(sk.N, a)

	// m ≡ lu = L(ɑ)*u = L(c^{λ(N)})*u	mod N
	m := Mul(ell, sk.U, sk.N)

	return m
}

func Mul(x, y, m *big.Int) *big.Int {

	z := new(big.Int).Mul(x, y)

	return z.Mod(z, m)
}
func Inv(x, m *big.Int) *big.Int {

	z := new(big.Int).ModInverse(x, m)
	return (z)
}
func mul(a, c, m *big.Int) *big.Int {

	z := new(big.Int).Exp(c, a, m)
	return (z)
}
func setupKeys(sec *SecretKey, pub *PublicKey) {
	pub.N, _ = new(big.Int).SetString("22203902867524505059996239340306362808852805402888214954381553003002718752808306965243974655390219346481612755387890570991182385566928749760445875916800573782909761881261515602762049819293013811136510263722491329215251675663091154175860620927146517652389408089110716148633480085801107700968384078929774277970426932561081560231010426294975678729992804063220974701278229766883426991469078323539488917623430196595127834729964807458110080684240115196595760172158113810254192728271785178985307185853395355962836026777351498860874006114137632167254987479651229489157192247478252351962954320801263428208801271515398015887801", 10)
	pub.N2 = new(big.Int).Mul(pub.N, pub.N)

	sec.N = pub.N
	sec.N2 = pub.N2
	sec.Lambda, _ = new(big.Int).SetString("11101951433762252529998119670153181404426402701444107477190776501501359376404153482621987327695109673240806377693945285495591192783464374880222937958400286891454880940630757801381024909646506905568255131861245664607625837831545577087930310463573258826194704044555358074316740042900553850484192039464887138985064438949068643503538028104882092520753872226183177268421975002892541203962036580811698912148170624870917841537346985483337432253649017635885024033744586145456966646545432316660152135614842196027111652507352356170725302821683928442675667004336523805058723372589095589316741830468728743532156406225121890756346", 10)
	sec.Totient, _ = new(big.Int).SetString("22203902867524505059996239340306362808852805402888214954381553003002718752808306965243974655390219346481612755387890570991182385566928749760445875916800573782909761881261515602762049819293013811136510263722491329215251675663091154175860620927146517652389408089110716148633480085801107700968384078929774277970128877898137287007076056209764185041507744452366354536843950005785082407924073161623397824296341249741835683074693970966674864507298035271770048067489172290913933293090864633320304271229684392054223305014704712341450605643367856885351334008673047610117446745178191178633483660937457487064312812450243781512692", 10)
	sec.U, _ = new(big.Int).SetString("11108720355657041776647490476262423100273444107890028034525926371450220865341816894255404548947647952186614924131107824022774134150177636593890919577479093776330856863330832621779073688637362125712752218152358601679371477743308049274665882845748928958872854339383876978533793119837835146167726752137945969833510158025058440018805812646143848801020667307117190186323497007267362203459968413761903710129427082211518450427328378521338965975284389455704146581178957343955351641425309976491396722227064973929033480821132777267246266490713852090985090755453080857556125803448778856380844874040092451545474091429770838805", 10)

}
func main() {

	var sec SecretKey
	var pub PublicKey

	//	pub, sec, _ := paillier.NewKeys()
	setupKeys(&sec, &pub)

	v1 := "223"
	v2 := "224"
	argCount := len(os.Args[1:])

	if argCount > 0 {
		v1 = os.Args[1]
	}
	if argCount > 1 {
		v2 = os.Args[2]
	}

	val1, _ := new(big.Int).SetString(v1, 10)
	val2, _ := new(big.Int).SetString(v2, 10)

	cipher1 := encrypt(pub, val1)

	cipher2 := encrypt(pub, val2)

	// Adding
	cipher3 := add(pub, cipher1, cipher2)

	decrypted1 := decrypt(sec, cipher3)

	// Subtraction
	inv_cipher2 := Inv(cipher2, pub.N2)

	cipher4 := add(pub, cipher1, inv_cipher2)

	decrypted2 := decrypt(sec, cipher4)

	// Multiply
	cipher5 := mul(val1, cipher2, pub.N2)

	decrypted3 := decrypt(sec, cipher5)

	fmt.Printf("\na=%s, b=%s\n", val1, val2)

	fmt.Printf("\nEnc(a)=%v, Enc(b)=%v\n", cipher1, cipher2)

	fmt.Printf("\n%s + %s = %s\n", val1, val2, decrypted1)
	fmt.Printf("\n%s * %s = %s\n", val1, val2, decrypted3)

	if decrypted2.Cmp(new(big.Int).Div(pub.N, big.NewInt(2))) > 0 {
		// m = m - n
		fmt.Printf("%s - %s = %s\n", val1, val2, new(big.Int).Sub(decrypted2, pub.N))
	} else {
		fmt.Printf("%s - %s = %s\n", val1, val2, decrypted2)
	}

}

A sample run is [here]:

a=222, b=111

Enc(a)=480255181920800962319428195982635686810088385894694335732539232950598802361655578994299473947015823706085641632265918920177271050935899445772018657379409917340875585795573456622928011108763896998310685496049348635361148476665982292583742521662892246510134496910480985230953608457374596556061690681311372035369557473453948571498287540563940498719457037028423196712497593060402292462158152772365096268526544613966053669489002176306136618535389523393860906046429497082997574262450762786531668654114069457095304276136300381237935928488169886100022455673772985830484439920173220489954345908504730126607166660669616837735331132127595030555268828556190724381620586303349525363142824926041003132666363188063124075469384544768925327914082583686275806308821004655253016048332888033533857446684327464728753575758198032289396001937677420421304213675660776816637709884428865855227219223951888611467829806312828381700124791746116297756951418091223465584531827315766709832802225806892686198418948109322860207792492578901690557854559299736849385819889486069503912193322571436752435739403077721769655830857694261861731325926243758449255964430155072325622086559490250784450951299715352393589113643733050357885271539548238790965835016548892755681491217, Enc(b)=398205057005000805455412925833532994717615194020655376461633849479054914228469584412356182413073212222229225897995778310285802001620224215672510848280476816560246933598044438129822536195476471730535502177390452652250248208595245774868663210615963412562038409604119717517734532923327183494024965696228498538639558086901827119637452112502647978827481995866363495625837621647623546620410500086811780489366824575093690909960314240825269897595801111438023076383121529088191656996666295497574395828609506976835480393272407009883660101408839186236877371208967820363921744294119034984338166756418022949781351180172422781584254651807677632253283134440525408418041260953938375203226980802190306068235344987804712672397597944426532987481662630428128948672757884566423914969203583167323575075335034411157347418887682930435526342638719818198078786738032388166189020743344542420574023931557754426969505264962187883070184429059626960626546411313341199020568060067512561944206262699174908858448584688032887324374515251373912574173526824962194722293602736606882903604170107467326730803713106312324982828292317687693528819441737056014833346488071437353342607272253728630007825092500186949850603988095382717600780136544280866381494593592289423116839401

222 + 111 = 333

222 * 111 = 24642
222 - 111 = 111

Conclusions

And there you go … get into Big Integers … and create a world of numbers without any bounds. Here are some more Golang examples:

https://asecuritysite.com/golang