cascada.bitvector.secondaryop module

Provide additional (secondary) bit-vector operators.

BvMaj	The bit-wise majority function.
BvIf	The bit-wise conditional (If) function.
PopCount	Count the number of 1's in the bit-vector.
Reverse	Reverse the bit-vector.
PopCountSum2	Count the number of 1's of two bit-vectors.
PopCountSum3	Count the number of 1's of three bit-vectors.
PopCountDiff	Compute the difference of the hamming weight of two words.
LeadingZeros	Return a bit-vector with the leading zeros set to one and the rest to zero.
LutOperation	Base class for LUT-based operations.
MatrixOperation	Base class for matrix-vector products.

class cascada.bitvector.secondaryop.BvMaj(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

The bit-wise majority function.

The bit-wise majority function BvMaj(x, y, z) is defined for each bit i as the most common bit in [x[i], y[i], z[i]].

Since BvMaj is a SecondaryOperation, by default it is fully evaluated (i.e., Operation.eval is used) when all the inputs are constants (see also context.SecondaryOperationEvaluation). On the other hand, pre_eval is always called in the evaluation (even with symbolic inputs).

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import BvMaj
>>> BvMaj(Constant(0b000, 3), Constant(0b001, 3), Constant(0b011, 3))
0b001
>>> BvMaj(Variable("x", 4), Variable("y", 4), Variable("z", 4))
BvMaj(x, y, z)
>>> BvMaj(Variable("x", 4), Variable("x", 4), Variable("z", 4))
x
>>> BvMaj(Variable("x", 4), Variable("y", 4), Variable("z", 4)).doit()
(x & y) | (x & z) | (y & z)

classmethod condition(x, y, z)

Check if the operands verify the restrictions of the operator.

classmethod output_width(x, y, z)

Return the bit-width of the resulting bit-vector.

classmethod pre_eval(x, y, z)

Evaluate the operator before Operation.eval.

This is an internal method that assumes the list args has been parsed.

classmethod eval(x, y, z)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.BvIf(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

The bit-wise conditional (If) function.

The bit-wise conditional function BvIf(x, y, z) is defined for each bit i as y[i] if x[i]=1 otherwise z[i].

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import BvIf
>>> BvIf(Constant(0b01, 2), Constant(0b00, 2), Constant(0b11, 2))
0b10
>>> BvIf(Variable("x", 4), Variable("y", 4), Variable("z", 4))
BvIf(x, y, z)
>>> BvIf(0, Variable("y", 4), Variable("z", 4))
z
>>> BvIf(Variable("x", 4), Variable("y", 4), Variable("z", 4)).doit()
(x & y) | (~x & z)

classmethod condition(x, y, z)

Check if the operands verify the restrictions of the operator.

classmethod output_width(x, y, z)

Return the bit-width of the resulting bit-vector.

classmethod pre_eval(x, y, z)

Evaluate the operator before Operation.eval.

This is an internal method that assumes the list args has been parsed.

classmethod eval(x, y, z)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.PopCount(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Count the number of 1’s in the bit-vector.

This operation is also known as the hamming weight of a bit-vector.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import PopCount
>>> PopCount(Constant(0b1010, 4))
0b010
>>> PopCount(Constant(0b101, 3))
0b10
>>> PopCount(Variable("x", 4)).doit()
(((x - ((x >> 0x1) & 0x5)) & 0x3) + (((x - ((x >> 0x1) & 0x5)) >> 0x2) & 0x3))[2:]
>>> PopCount(Variable("x", 3)).doit()
(0b0 :: (x[0])) + (0b0 :: (x[1])) + (0b0 :: (x[2]))

classmethod output_width(x)

Return the bit-width of the resulting bit-vector.

classmethod eval(bv)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.Reverse(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Reverse the bit-vector.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import PopCount
>>> Reverse(Constant(0b1010, 4))
0x5
>>> Reverse(Constant(0b001, 3))
0b100
>>> Reverse(Variable("x", 4)).doit()  
(((((x & 0x5) << 0x1) | ((x >> 0x1) & 0x5)) & 0x3) << 0x2) |
(((((x & 0x5) << 0x1) | ((x >> 0x1) & 0x5)) >> 0x2) & 0x3)
>>> Reverse(Variable("x", 3)).doit()
(x[0]) :: (x[1]) :: (x[2])

classmethod output_width(x)

Return the bit-width of the resulting bit-vector.

classmethod eval(bv)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.PopCountSum2(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Count the number of 1’s of two bit-vectors.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import PopCountSum2
>>> PopCountSum2(Constant(0b000, 3), Constant(0b001, 3))
0b001
>>> PopCountSum2(~Constant(0, 15), ~Constant(0, 15))
0b11110
>>> PopCountSum2(Variable("x", 4), Variable("y", 4)).doit()  
((x - ((x >> 0x1) & 0x5)) & 0x3) + (((x - ((x >> 0x1) & 0x5)) >> 0x2) & 0x3) +
((y - ((y >> 0x1) & 0x5)) & 0x3) + (((y - ((y >> 0x1) & 0x5)) >> 0x2) & 0x3)
>>> PopCountSum2(Variable("x", 3), Variable("y", 3)).doit()  
(0b0 :: ((0b0 :: (x[0])) + (0b0 :: (x[1])) + (0b0 :: (x[2])))) +
(0b0 :: ((0b0 :: (y[0])) + (0b0 :: (y[1])) + (0b0 :: (y[2]))))

classmethod condition(x, y)

Check if the operands verify the restrictions of the operator.

classmethod output_width(x, y)

Return the bit-width of the resulting bit-vector.

classmethod eval(x, y)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.PopCountSum3(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Count the number of 1’s of three bit-vectors.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import PopCountSum3
>>> PopCountSum3(Constant(0b000, 3), Constant(0b001, 3), Constant(0b011, 3))
0x3
>>> PopCountSum3(Variable("x", 4), Variable("y", 4), Variable("z", 4)).doit()  
((x - ((x >> 0x1) & 0x5)) & 0x3) + (((x - ((x >> 0x1) & 0x5)) >> 0x2) & 0x3) +
((y - ((y >> 0x1) & 0x5)) & 0x3) + (((y - ((y >> 0x1) & 0x5)) >> 0x2) & 0x3) +
((z - ((z >> 0x1) & 0x5)) & 0x3) + (((z - ((z >> 0x1) & 0x5)) >> 0x2) & 0x3)
>>> PopCountSum3(Variable("x", 3), Variable("y", 3), Constant(0, 3)).doit()  
(0b00 :: ((0b0 :: (x[0])) + (0b0 :: (x[1])) + (0b0 :: (x[2])))) +
(0b00 :: ((0b0 :: (y[0])) + (0b0 :: (y[1])) + (0b0 :: (y[2]))))

classmethod condition(x, y, z)

Check if the operands verify the restrictions of the operator.

classmethod output_width(x, y, z)

Return the bit-width of the resulting bit-vector.

classmethod eval(x, y, z)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.PopCountDiff(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Compute the difference of the hamming weight of two words.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import PopCountDiff
>>> PopCountDiff(Constant(0b011, 3), Constant(0b100, 3))
0b01
>>> PopCountDiff(Variable("x", 4), Variable("y", 4)).doit()  
((((x - ((x >> 0x1) & 0x5)) & 0x3) + (((x - ((x >> 0x1) & 0x5)) >> 0x2) & 0x3) +
((~y - ((~y >> 0x1) & 0x5)) & 0x3) + (((~y - ((~y >> 0x1) & 0x5)) >> 0x2) & 0x3)) - 0x4)[2:]
>>> PopCountDiff(Variable("x", 3), Variable("y", 3)).doit()  
((0b0 :: (x[0])) + (0b0 :: (x[1])) + (0b0 :: (x[2]))) -
((0b0 :: (y[0])) + (0b0 :: (y[1])) + (0b0 :: (y[2])))

classmethod condition(x, y)

Check if the operands verify the restrictions of the operator.

classmethod output_width(x, y)

Return the bit-width of the resulting bit-vector.

classmethod eval(x, y)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.LeadingZeros(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Return a bit-vector with the leading zeros set to one and the rest to zero.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import PopCount
>>> LeadingZeros(Constant(0b11111, 5))
0b00000
>>> LeadingZeros(Constant(0b001, 3))
0b110
>>> LeadingZeros(Variable("x", 4)).doit()
~(x | (x >> 0x1) | ((x | (x >> 0x1)) >> 0x2))
>>> LeadingZeros(Variable("x", 3)).doit()
~(((0b0 :: x) | ((0b0 :: x) >> 0x1) | (((0b0 :: x) | ((0b0 :: x) >> 0x1)) >> 0x2))[2:])

classmethod output_width(x)

Return the bit-width of the resulting bit-vector.

classmethod eval(bv)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.LutOperation(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Base class for LUT-based operations.

Given a LUT (look-up table) T with Constant elements, the (bit-vector) LUT-based operation T(x) (with bit-vector input x) returns the bit-vector of T in the position given by the integer value of x.

Since LutOperation is a SecondaryOperation, it is only evaluated by default when the input is a constant value (see also context.SecondaryOperationEvaluation).

This class is not meant to be instantiated but to provide a base class for LUT-based operations. To define a LUT-based operation, subclass LutOperation and provide the class attribute lut.

lut

the table that defines the LUT-based operation given as a list of Constant objects.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import LutOperation
>>> class MyInvertibleLut(LutOperation): lut = [Constant(i, 2) for i in reversed(range(2**2))]
>>> MyInvertibleLut(Constant(0, 2))
0b11
>>> MyInvertibleLut(Variable("a", 2)).doit()
Ite(a == 0b00, 0b11, Ite(a == 0b01, 0b10, Ite(a == 0b10, 0b01, 0b00)))
>>> class MyNonInvLut(LutOperation): lut = [Constant(0, 8), ~Constant(0, 8)]
>>> MyNonInvLut(Variable("a", 1)).doit()
Ite(a == 0b0, 0x00, 0xff)

classmethod condition(x)

Check if the operands verify the restrictions of the operator.

classmethod output_width(x)

Return the bit-width of the resulting bit-vector.

classmethod eval(x)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).

class cascada.bitvector.secondaryop.MatrixOperation(**kwargs)

Bases: cascada.bitvector.operation.SecondaryOperation

Base class for matrix-vector products.

Given a binary matrix as a 2-dimensional list M with 1-bit Constant elements (M[i][j] is the j-th column element in the i-th row), the (bit-vector) matrix-vector product M(x) (with bit-vector input x) returns the bit-vector of y such the i-th bit of y is given by y[i] = (M[i][0] & x[0]) ^ (M[i][1] & x[1]) ^ ... ^ (M[i][n-1] & x[n-1]) where n is the number of columns and the width of x.

Since MatrixOperation is a SecondaryOperation, it is only evaluated by default when the input is a constant value (see also context.SecondaryOperationEvaluation).

This class is not meant to be instantiated but to provide a base class for matrix-vector products. To define a matrix-vector product, subclass MatrixOperation and provide the class attribute matrix.

Note

By default, a MatrixOperation subclass takes 1 input operand x, but arity can be changed to support multiple operands. In this case, the list of inputs (x_1, ..., x_n) are concatenated into x as x = x_n :: ... :: x_1 (x_1 denoting the least-significant part and x_n denoting the most-significant part).

In other words, a MatrixOperation subclass with arity == [n, 0] and input (x_1, ..., x_n) computes M(x_n :: ... :: x_1).

Alternatively, binary matrices can be implemented as a sequence of BvXor operations (e.g., https://eprint.iacr.org/2021/1400).

matrix

the binary matrix as a 2D list of 1-bit Constant objects.

>>> from cascada.bitvector.core import Constant, Variable
>>> from cascada.bitvector.secondaryop import MatrixOperation
>>> matrix = [[0, 1], [1, 0]]  # reverse
>>> matrix = [[core.Constant(x, 1) for x in row] for row in matrix]
>>> class MySquareMatrix(MatrixOperation): matrix = matrix
>>> MySquareMatrix(Constant(0, 2))
0b00
>>> MySquareMatrix(Variable("a", 2)).doit()
(a[0]) :: (a[1])
>>> matrix = [[1, 0], [0, 1], [1, 0], [0, 1]]  # 2 bit to 4 bit
>>> matrix = [[core.Constant(x, 1) for x in row] for row in matrix]
>>> class MyNonSqMatrix(MatrixOperation): arity, matrix = [2, 0], matrix
>>> MyNonSqMatrix(Variable("a0", 1), Variable("a1", 1)).doit()
a1 :: a0 :: a1 :: a0

classmethod condition(*args)

Check if the operands verify the restrictions of the operator.

classmethod output_width(*args)

Return the bit-width of the resulting bit-vector.

classmethod eval(*args)

Evaluate the operator with given operands.

This is an internal method that assumes the list args has been parsed. To evaluate a bit-vector operation, instantiate a new object with the operands as the object arguments (i.e., use the Python operator ()).