pyecsca.ec.scalar module

Provides functions for computing various scalar representations (like NAF, or different bases).

convert_base(i, base)[source]

Convert an integer to base.

Parameters:
  • i (int) – The scalar.

  • base (int) – The base.

Return type:

List[int]

Returns:

The resulting digit list (little-endian).

sliding_window_ltr(i, w)[source]

Compute the sliding-window left-to-right form.

From [BBG+17].

Parameters:
  • i (int) – The scalar.

  • w (int) – The width.

Return type:

List[int]

Returns:

The sliding-window LTR form.

sliding_window_rtl(i, w)[source]

Compute the sliding-window right-to-left form.

From [BBG+17].

Parameters:
  • i (int) – The scalar.

  • w (int) – The width.

Return type:

List[int]

Returns:

The sliding-window RTL form.

wnaf(k, w)[source]

Compute width w NAF (Non-Adjacent Form) of the scalar k.

Algorithm 9.35 from [GECC], Algorithm 9.20 from [HEHCC].

Note

According to HEHCC this is actually not unique

A left-to-right variant to compute an NAFw expansion of an integer can be found both in [AVA 2005a] and in [MUST 2005]. The result may differ from the expansion produced by Algorithm 9.20 but they have the same digit set and the same optimal weight.

According to GECC it is.

Parameters:
  • k (int) – The scalar.

  • w (int) – The width.

Return type:

List[int]

Returns:

The NAF.

naf(k)[source]

Compute the NAF (Non-Adjacent Form) of the scalar k.

Properties ([GECC] 3.29):
  1. k has a unique NAF denoted NAF(k).

  2. NAF(k) has the fewest non-zero digits of any signed digit representation of k.

  3. The length of NAF(k) is at most one more than the bit-length of k.

  4. If the length of NAF(k) is l, then $2^l / 3 < k < 2^(l+1) / 3$.

  5. The average density of non-zero digits among all NAFs of length l is approximately 1/3.

Parameters:

k (int) – The scalar.

Return type:

List[int]

Returns:

The NAF.

booth(k)[source]

Original Booth binary recoding, from [B51].

Parameters:

k (int) – The scalar to recode.

Return type:

List[int]

Returns:

The recoded list of digits (0, 1, -1), little-endian.

booth_word(digit, w)[source]

Modified Booth recoding, from [M61] and BoringSSL NIST impl.

Needs w+1 bits of scalar in digit, but the one bit is overlapping (window size is w).

Parameters:
  • digit (int)

  • w (int)

Return type:

int

Returns:

booth_window(k, w, blen)[source]

Recode a whole scalar using Booth recoding as in BoringSSL.

Parameters:
  • k (int) – The scalar.

  • w (int) – The window size.

  • blen (int) – The bit-length of the group.

Return type:

List[int]

Returns:

The big-endian recoding