The Integers We Use In Programs Are Just So Small …

The Integers We Use In Programs Are Just So Small …

Our microprocessors started off with 4-bit registers (the mighty 4004 processor), and where we organised our memory in address with 8 bits in each. We then saw the development of 8-bit (8080), 16-bit (8086), 32-bit (80386) and 64-bit (Pentium) processors. Each of these processes could deal with larger integer values. Thus we end up with integers represented by 8-bit (byte), 16-bit (short), 32-bit (int) and 64-bit (long) values. These can be signed or unsigned.

Within cryptography, we often deal with integers which are greater than 64 bits. This means that we cannot use our normal integer values within programs. For this we normally use Big Integers to perform our calculations, and where we use a string value to represent the values (or as bytes) and then convert to a Big Integer. In this example, we will use the normal arithmetic operations for Big Integers, along with using the Mod operation with a prime number.

So let’s implement some Golang code for using Big Integers [here]:

package main

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

func isHexString(s string) bool {
	return strings.ContainsAny(s, "abc")
}

func toBigInt(s string) *big.Int {
	x, _ := new(big.Int).SetString("0", 16)

	if strings.HasPrefix(s, "0x") {
		s = strings.Replace(s, "0x", "", 1)
		x, _ = new(big.Int).SetString(s, 16)
	} else if strings.HasPrefix(s, "0") {
		x, _ = new(big.Int).SetString(s, 8)
	} else if isHexString(s) {
		x, _ = new(big.Int).SetString(s, 16)

	} else {
		x, _ = new(big.Int).SetString(s, 10)

	}
	return (x)
}

func main() {

	v1 := "2e63d239b3fc47433f19789843e30514b53dfd8773ebc915c0bc774e5368dbb6"
	v2 := "2e63d239b3fc47433f19789843e30514b53dfd8773ebc915c0bc774e5368dbb4"
	p1 := "127"
	argCount := len(os.Args[1:])

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

	x1 := toBigInt(v1)
	x2 := toBigInt(v2)
	prime := toBigInt(p1)
	fmt.Printf("Value 1 in hex: %x\n", v1)
	fmt.Printf("Value 1 in decimal: %s\n", v1)
	fmt.Printf("Value 2 in hex: %x\n", v1)
	fmt.Printf("Value 2 in decimal: %s\n", v1)

	fmt.Printf("v1+v2= %s\n", new(big.Int).Add(x1, x2).String())
	fmt.Printf("v1-v2= %s\n", new(big.Int).Sub(x1, x2).String())
	fmt.Printf("v1*v2= %s\n", new(big.Int).Mul(x1, x2).String())
	fmt.Printf("\n\n== Now using a prime number of 2^255-19 ===\n")
	fmt.Printf("p== %s\n", prime)
	p := new(big.Int).Exp(x1, x2, prime)
	fmt.Printf("v1^v2 (mod p)= %s\n", prime)

	p = new(big.Int).Mul(x1, x2)
	p = new(big.Int).Mod(p, prime)
	fmt.Printf("v1*v2 (mod p)= %s\n", p)

	p = new(big.Int).Add(x1, x2)
	p = new(big.Int).Mod(p, prime)
	fmt.Printf("v1+v2 (mod p)= %s\n", p)

	Invx2 := new(big.Int).ModInverse(x2, prime)
	p = new(big.Int).Mul(x1, Invx2)
	p = new(big.Int).Mod(p, prime)
	fmt.Printf("v1/v2 (mod p)= %s\n", p)

}

A sample run [here]:

Value 1 in hex: 36353637363534333232313539373836303539333231313235303736353933343831
Value 1 in decimal: 6567654322159786059321125076593481
Value 2 in hex: 36353637363534333232313539373836303539333231313235303736353933343831
Value 2 in decimal: 6567654322159786059321125076593481
v1+v2= 13135308644319572118642250153186961
v1-v2= 1
v1*v2= 43134083295384118890217002575136880587668454103193867717686255103880

== Now using a prime number of 2^255-19 ===
p== 162259276829213363391578010288127
v1^v2 (mod p)= 162259276829213363391578010288127
v1*v2 (mod p)= 124676263978455851507041051363013
v1+v2 (mod p)= 154566497982503047316009330136801
v1/v2 (mod p)= 62894471289770622511861081676001

Asecuritysite is provided free and without adverts. If you want to support its development and get access to this blog, subscribe here: