Home Manual Reference Source

Function

Static Public Summary
public

modN(r: *, N: *, x: *): *

public

modR(k: *, x: *): *

|x| >= k

Static Private Summary
private

_iadd(r: Number, N: Array, a: Array, b: Array): boolean

private

_isub(r: Number, N: Array, a: Array, b: Array): boolean

private

_montgomery(b: Number, N: Array): {"k": *, "M": *, "R": *, "R2": *, "R3": *}

N has no leading zeroes

private

_mul(r: *, N: *, M: *, a: *, b: *, c: *): *

abR mod N = REDC((aR mod N)(bR mod N))

private

_redc(b: *, k: *, N: *, Ni: *, Nj: *, M: *, Mi: *, Mj: *, T: *, Ti: *, Tj: *): boolean

Function REDC is

Static Public

public modN(r: *, N: *, x: *): * source

Params:

NameTypeAttributeDescription
r *
N *
x *

Return:

*

public modR(k: *, x: *): * source

|x| >= k

Params:

NameTypeAttributeDescription
k *
x *

Return:

*

Static Private

private _iadd(r: Number, N: Array, a: Array, b: Array): boolean source

Params:

NameTypeAttributeDescription
r Number

the radix

N Array

number array of length k.

a Array
b Array

(a+b)R mod N = aR mod N + bR mod N - ( 0/1 * N )

R = r^k N has no leading zeroes N has length k |N| = |a| >= |b| |a| = |b| if you want to avoid side channel attacks a < N b < N

t = a + b mod r^k if t < b or t >= N then return t - N mod r^k else return t // Can subtract dummy zero vector here in case we want // to avoid side channel attacks

Return:

boolean

private _isub(r: Number, N: Array, a: Array, b: Array): boolean source

Params:

NameTypeAttributeDescription
r Number

the radix

N Array

number array of length k.

a Array
b Array

(a+b)R mod N = aR mod N - bR mod N + ( 0/1 * N )

R = r^k N has no leading zeroes N has length k |N| = |a| >= |b| |a| = |b| if you want to avoid side channel attacks a < N b < N

t = a - b mod r^k if a < b then return t + N mod r^k else return t // Can add dummy zero vector here in case we want // to avoid side channel attacks

Return:

boolean

private _montgomery(b: Number, N: Array): {"k": *, "M": *, "R": *, "R2": *, "R3": *} source

N has no leading zeroes

Params:

NameTypeAttributeDescription
b Number

the radix

N Array

number array of length k.

Return:

{"k": *, "M": *, "R": *, "R2": *, "R3": *}

private _mul(r: *, N: *, M: *, a: *, b: *, c: *): * source

abR mod N = REDC((aR mod N)(bR mod N))

|N| >= |a| >= |b| |c| = 2*|N| + 1 c = 0000.0000 is zero initialized

Params:

NameTypeAttributeDescription
r *
N *
M *
a *
b *
c *

Return:

*

private _redc(b: *, k: *, N: *, Ni: *, Nj: *, M: *, Mi: *, Mj: *, T: *, Ti: *, Tj: *): boolean source

Function REDC is

input: Integers R = b^k > N with gcd(R, N) = 1, Integer M in [0, R − 1] such that NM ≡ −1 mod R, Integer T in the range [0, RN − 1]

    All numbers are given in base b (big endian order).

output: Integer S in the range [0, N − 1] such that S ≡ TR−1 mod N

m ← ((T mod R)M) mod R // Can be implemented by discarding limbs t ← (T + mN) / R // Can be implemented with a shift // /!\ T + mN is potentially RN - 1 + (R-1) N = 2RN - N - 1 so need one // extra limb for carry ? if t ≥ N then return t − N else return t // Can add dummy - zero vector here in case we want to avoid side // channel attacks end if end function

Params:

NameTypeAttributeDescription
b *
k *
N *
Ni *
Nj *
M *
Mi *
Mj *
T *
Ti *
Tj *

Return:

boolean