// //------------------ DOK FILE -------------------------------------------------- +Header bignumLib =pkg bios =title Big numbers =short numbers for cryptography =desc Big numbers are mostly used for cryptography. // // //------------------ PROTO ----------------------------------------------------- BigNum +Proto BigNum =type BigNum =mode type =pkg bios =impl native =link =desc BigNum is the Minimacy type for very large integer numbers. There is currently a limit to 16384 bits. Big numbers are signed. You may use big numbers when the 64 bits integers are not enough for your computation, but the main usage is cryptography, and modulus computation. // // //------------------ PROTO ----------------------------------------------------- bigASL1 +Proto bigASL1 =type fun BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function performs an arithmetic shift left of the bits of p. It is like a multiplication by 2. // +arg p =type BigNum =desc A big number // +arg result =type BigNum =desc Another big number // // //------------------ PROTO ----------------------------------------------------- bigASR1 +Proto bigASR1 =type fun BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function performs an arithmetic shift right of the bits of p. It is like a euclidian division by 2, whatever the rest is. // +arg p =type BigNum =desc A big number // +arg result =type BigNum =desc Another big number // // //------------------ PROTO ----------------------------------------------------- bigASR +Proto bigASR =type fun BigNum Int -> BigNum =mode function =pkg bios =impl native =link =desc This function performs an arithmetic variable shift right of the bits of p. The shift value indicates how many bits are shifted to the right. // +arg p =type BigNum =desc A big number // +arg shift =type Int =desc An integer // +arg result =type BigNum =desc Another big number // // //------------------ PROTO ----------------------------------------------------- bigAbs +Proto bigAbs =type fun BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function 'abs'. // +arg p =type BigNum =desc A big number // +arg result =type BigNum =desc The absolute value // // //------------------ PROTO ----------------------------------------------------- bigAdd +Proto bigAdd =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function 'p + q'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc The sum // // //------------------ PROTO ----------------------------------------------------- bigAddMod +Proto bigAddMod =type fun BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p + q) mod M'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigBarrett +Proto bigBarrett =type fun BigNum -> BigNum =mode function =pkg bios =impl native =link =desc The Barrett reduction algorithm is a popular method to optimize modulus computation when you perform many operations with the same modulus value. Concerned operations are multiplication, division, exponential and even simple modulus. This function returns the precomputed factor, you may use with [[bigModBarrett]], [[bigMulModBarrett]], [[bigDivModBarrett]] and [[bigExpModBarrett]]. // +arg p =type BigNum =desc A big number // +arg result =type BigNum =desc The Barrett factor // // //------------------ PROTO ----------------------------------------------------- bigBit +Proto bigBit =type fun BigNum Int -> Int =mode function =pkg bios =impl native =link =desc This function returns the value of the bit at position in p. // +arg p =type BigNum =desc A big number // +arg position =type Int =desc A bit number // +arg result =type Int =desc 1 or 0 // // //------------------ PROTO ----------------------------------------------------- bigCmp +Proto bigCmp =type fun BigNum BigNum -> Int =mode function =pkg bios =impl native =link =desc This function compares two big numbers and returns 0 if equal, -1 if p lower than q, otherwise 1. > bigCmp (bigFromInt (1), bigFromInt (2)) >-> Int: -1 (0xFFFFFFFFFFFFFFFF) > bigCmp (bigFromInt (1), bigFromInt (0)) >-> Int: 1 (0x1) // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type Int =desc -1, 1 or 0 // // //------------------ PROTO ----------------------------------------------------- bigDiv +Proto bigDiv =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function 'p / q'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc The quotient p/q // // //------------------ PROTO ----------------------------------------------------- bigDivMod +Proto bigDivMod =type fun BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p / q) mod M'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigDivModBarrett +Proto bigDivModBarrett =type fun BigNum BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p / q) mod M', with the Barrett optimization. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg Barrett =type BigNum =desc The Barrett factor for M // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigDivRemainder +Proto bigDivRemainder =type fun BigNum BigNum -> [BigNum BigNum] =mode function =pkg bios =impl native =link =desc This is the mathematical Euclidian division 'p / q', returning the quotient and the remainder. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type [BigNum BigNum] =desc A tuple [quotient remainder] // // //------------------ PROTO ----------------------------------------------------- bigEquals +Proto bigEquals =type fun BigNum BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p = q. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigEuclid +Proto bigEuclid =type fun BigNum BigNum -> [BigNum BigNum BigNum] =mode function =pkg bios =impl native =link =desc This function implements the Euclidean algorithm, based on the following theorem: for any p and q, there is a and b so that pa+qb=gcd, where gcd is the greatest common divisor. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type [BigNum BigNum BigNum] =desc A tuple [a b gcd] // // //------------------ PROTO ----------------------------------------------------- bigExp +Proto bigExp =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function 'p exp q'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc The exponential // // //------------------ PROTO ----------------------------------------------------- bigExpChinese5 +Proto bigExpChinese5 =type fun BigNum BigNum BigNum BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function computes a^privateExponent mod M. Curiously this function doesn't need the value of M neither privateExponent. Instead we pass it p1 and p2, which are the prime factors of M: p1.p2 = M. We pass also: - e1=privateExponent mod (p1-1) - e2=privateExponent mod (p2-1) - coef=1/p2 mod p1 This algorithm relies on the Chinese remainder theorem. This is the most common way to optimize the modular exponentiation, as RSA keys are usually provided as a tuple (M, publicExponent, privateExponent, p1, p2, e1, e2, coef). This is an example of openssl use (we hide the numbers, we are only interested in the structure and how openssl names these numbers): >> openssl rsa -text -noout -in myRsa.key >Private-Key: (2048 bit) >modulus: >[..] >publicExponent: 65537 (0x10001) >privateExponent: >[..] >prime1: >[..] >prime2: >[..] >exponent1: >[..] >exponent2: >[..] >coefficient: >[..] // +arg a =type BigNum =desc A big number // +arg p1 =type BigNum =desc A big prime number // +arg p2 =type BigNum =desc A big prime number // +arg e1 =type BigNum =desc A big number // +arg e2 =type BigNum =desc A big number // +arg coef =type BigNum =desc A big number // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigExpChinese7 +Proto bigExpChinese7 =type fun BigNum BigNum BigNum BigNum BigNum BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function computes a^privateExponent mod M. Curiously this function doesn't need the value of M. Instead we pass it p and q, which are the prime factors of M: p.q = M We pass also: - u and v so that p.u + q.v = 1 mod M - pBarrett and qBarrett which are the Barrett factors of p and q This algorithm relies on the Chinese remainder theorem. From our tests this modular exponentiation is slightly faster (x 1.015) than [[bigExpChinese5]]. // +arg a =type BigNum =desc A big number // +arg privateExponent =type BigNum =desc A big number // +arg p =type BigNum =desc A big prime number // +arg q =type BigNum =desc A big prime number // +arg u =type BigNum =desc A big number // +arg v =type BigNum =desc A big number // +arg pBarrett =type BigNum =desc The Barrett factor for p // +arg qBarrett =type BigNum =desc The Barrett factor for q // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigExpChinese +Proto bigExpChinese =type fun BigNum BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function computes a^privateExponent mod M. Curiously this function doesn't need the value of M. Instead we pass it p and q, which are the prime factors of M: p.q = M This algorithm relies on the Chinese remainder theorem. // +arg a =type BigNum =desc A big number // +arg privateExponent =type BigNum =desc A big number // +arg p =type BigNum =desc A big prime number // +arg q =type BigNum =desc A big prime number // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigExpMod +Proto bigExpMod =type fun BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p exp q) mod M'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigExpModBarrett +Proto bigExpModBarrett =type fun BigNum BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p / q) mod M', with the Barrett optimization. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg Barrett =type BigNum =desc The Barrett factor for M // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigDeserializeBytes +Proto bigDeserializeBytes =type fun Bytes -> BigNum =mode function =pkg bios =impl native =link =desc This function decodes the big number encoded in the array of bytes. > bigDeserializeBytes (bytesFromStr (bigSerialize (bigFromInt (12345678), nil))) >-> BigNum: 00bc614e // +arg src =type Bytes =desc An array of bytes // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigDeserialize +Proto bigDeserialize =type fun Str -> BigNum =mode function =pkg bios =impl native =link =desc This function decodes the big number encoded by bigSerialize. // +arg src =type Str =desc A binary string // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigFromStr +Proto bigFromStr =type fun Str -> BigNum =mode function =pkg bios =impl native =link =desc This function creates a big number from a decimal representation. > bigFromStr ("123456789012345678901234567890") >-> BigNum: 00000001 8ee90ff6 c373e0ee 4e3f0ad2 // +arg src =type Str =desc A decimal representation of an integer // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigFromHex +Proto bigFromHex =type fun Str -> BigNum =mode function =pkg bios =impl native =link =desc This function creates a big number from an hexadecimal representation. > bigFromHex ("123456789012345678901234567890") >-> BigNum: 00123456 78901234 56789012 34567890 // +arg src =type Str =desc A hexadecimal representation of an integer // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigFromInt +Proto bigFromInt =type fun Int -> BigNum =mode function =pkg bios =impl native =link =desc This function creates a big number from an integer. > bigFromInt (12345678) >-> BigNum: 00bc614e // +arg p =type Int =desc An integer // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- signedBigDeserializeBytes +Proto signedBigDeserializeBytes =type fun Bytes -> BigNum =mode function =pkg bios =impl native =link =desc This function decodes a big number encoded by [[signedBigSerialize]]. > signedBigDeserializeBytes (bytesFromStr (signedBigSerialize (bigFromInt (-12345678)))) >-> BigNum: -00bc614e // +arg src =type Bytes =desc An array of bytes // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- signedBigDeserialize +Proto signedBigDeserialize =type fun Str -> BigNum =mode function =pkg bios =impl native =link =desc This function decodes the big number encoded by [[signedBigSerialize]]. // +arg src =type Str =desc A binary string // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigGreater +Proto bigGreater =type fun BigNum BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p > q. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigGreaterEquals +Proto bigGreaterEquals =type fun BigNum BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p >= q. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigInv +Proto bigInv =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function computes the modulus inverse. It returns q such as 'p.q=1 mod M' // +arg p =type BigNum =desc A big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigIsEven +Proto bigIsEven =type fun BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p is even. // +arg p =type BigNum =desc A big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigIsNull +Proto bigIsNull =type fun BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p is 0. // +arg p =type BigNum =desc A big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigIsOne +Proto bigIsOne =type fun BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p is 1. // +arg p =type BigNum =desc A big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigLower +Proto bigLower =type fun BigNum BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p < q. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigLowerEquals +Proto bigLowerEquals =type fun BigNum BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p <= q. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigLowestBit +Proto bigLowestBit =type fun BigNum -> Int =mode function =pkg bios =impl native =link =desc This function returns the position of the first non-zero bit of p. // +arg p =type BigNum =desc A big number // +arg result =type Int =desc An integer // // //------------------ PROTO ----------------------------------------------------- bigMod +Proto bigMod =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function computes the modulus. It returns q such as 0 BigNum =mode function =pkg bios =impl native =link =desc This function computes the modulus with the Barrett optimization. It returns q such as 0 BigNum =mode function =pkg bios =impl native =link =desc This function computes the modulus with a power of 2. It returns p mod 2^n // +arg p =type BigNum =desc A big number // +arg n =type Int =desc An integer // +arg result =type BigNum =desc A positive big number lower than 2^n // // //------------------ PROTO ----------------------------------------------------- bigMul +Proto bigMul =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function 'p * q'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc The product p*q // // //------------------ PROTO ----------------------------------------------------- bigMulMod +Proto bigMulMod =type fun BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p / q) mod M'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigMulModBarrett +Proto bigMulModBarrett =type fun BigNum BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p * q) mod M', with the Barrett optimization. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg Barrett =type BigNum =desc The Barrett factor for M // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigNbits +Proto bigNbits =type fun BigNum -> Int =mode function =pkg bios =impl native =link =desc This function returns the number of bits of p. > bigNbits (bigFromInt (1)) >-> Int: 1 (0x1) > bigNbits (bigFromInt (0)) >-> Int: 0 (0x0) > bigNbits (bigFromInt (280)) >-> Int: 9 (0x9) // +arg p =type BigNum =desc A big number // +arg result =type Int =desc The number of bits of p // // //------------------ PROTO ----------------------------------------------------- bigNeg +Proto bigNeg =type fun BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function returns minus p. // +arg p =type BigNum =desc A big number // +arg result =type BigNum =desc The opposite number // // //------------------ PROTO ----------------------------------------------------- bigNegMod +Proto bigNegMod =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function returns -p mod M. // +arg p =type BigNum =desc A big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigGcd +Proto bigGcd =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function returns the greatest common divisor of p an q. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc gcd(p,q) // // //------------------ PROTO ----------------------------------------------------- bigPositive +Proto bigPositive =type fun BigNum -> Bool =mode function =pkg bios =impl native =link =desc This function returns true if p is positive or null. // +arg p =type BigNum =desc A big number // +arg result =type Bool =desc A boolean // // //------------------ PROTO ----------------------------------------------------- bigPower2 +Proto bigPower2 =type fun Int -> BigNum =mode function =pkg bios =impl native =link =desc This function returns 2^n. // +arg n =type Int =desc An integer // +arg result =type BigNum =desc A big number // // //------------------ PROTO ----------------------------------------------------- bigRand +Proto bigRand =type fun Int Bool -> BigNum =mode function =pkg bios =impl native =link =desc This function generates a random number with at most nBits bits. If exact is true then the result has exactly nBits bits. // +arg nBits =type Int =desc An integer // +arg exact =type Bool =desc A boolean // +arg result =type BigNum =desc A random number with at most nBits bits // // //------------------ PROTO ----------------------------------------------------- bigSub +Proto bigSub =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function 'p - q'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc The difference // // //------------------ PROTO ----------------------------------------------------- bigSubMod +Proto bigSubMod =type fun BigNum BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This is the mathematical function '(p - q) mod M'. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg M =type BigNum =desc A big number // +arg result =type BigNum =desc A positive big number lower than M // // //------------------ PROTO ----------------------------------------------------- bigSerialize +Proto bigSerialize =type fun BigNum Int -> Str =mode function =pkg bios =impl native =link =desc This function encodes the positive big number p into a binary string. This encoding returns nil on negative values. The parameter nBytes forces the length of the result. When nil the function returns the shorter string. When nBytes is too small for the number, the results encodes only the lower bytes. It can be decoded by the [[bigDeserialize]] function. > bigSerialize (bigFromInt (0x8081), nil) >-> Str: "\\$80\\$81" > bigSerialize (bigFromInt (0x8081), 4) >-> Str: "\\z\\z\\$80\\$81" > bigSerialize (bigFromInt (0x80818283), 2) >-> Str: "\\$82\\$83" > bigSerialize (bigFromInt (-64), nil) >-> Str: nil // +arg p =type BigNum =desc A positive big number // +arg nBytes =type Int =desc An integer or nil // +arg result =type Str =desc A binary string // // //------------------ PROTO ----------------------------------------------------- strFromBig +Proto strFromBig =type fun BigNum -> Str =mode function =pkg bios =impl native =link =desc This function returns the decimal representation of p. > strFromBig (bigFromHex ("1000000000000000000000000")) >-> Str: "79228162514264337593543950336" // +arg p =type BigNum =desc A big number // +arg result =type Str =desc A string with only decimal digits // // //------------------ PROTO ----------------------------------------------------- hexFromBig +Proto hexFromBig =type fun BigNum -> Str =mode function =pkg bios =impl native =link =desc This function returns the hexadecimal representation of p. > hexFromBig (bigFromStr ("79228162514264337593543950336")) >-> Str: "01000000000000000000000000" // +arg p =type BigNum =desc A big number // +arg result =type Str =desc A string with only hexadecimal digits // // //------------------ PROTO ----------------------------------------------------- intFromBig +Proto intFromBig =type fun BigNum -> Int =mode function =pkg bios =impl native =link =desc This function returns the big number p as an integer. Due to the "small" size of integers (signed 64 bits), the result will always be an integer between -2^61 and 2^61. // +arg p =type BigNum =desc A big number // +arg result =type Int =desc An integer // // //------------------ PROTO ----------------------------------------------------- signedBigSerialize +Proto signedBigSerialize =type fun BigNum -> Str =mode function =pkg bios =impl native =link =desc This function encodes the big number p into a binary string. This encoding accepts negative values. It can be decoded by the signedBigDeserialize function. // +arg p =type BigNum =desc A big number // +arg result =type Str =desc A binary string // // //------------------ PROTO ----------------------------------------------------- bigXor +Proto bigXor =type fun BigNum BigNum -> BigNum =mode function =pkg bios =impl native =link =desc This function creates a new big number by applying a XOR operation between p and q, bit per bit. It also applies a XOR on the signs of p and q: the result is positive if p and q have the same sign. // +arg p =type BigNum =desc A big number // +arg q =type BigNum =desc Another big number // +arg result =type BigNum =desc A big number