Discrete Log Group

The discrete logarithm problem is as follows: given a generator g of a finite group G and a random element h \in G, find the (unique) integer x such that g^x = h. In cryptography, we are interested in groups for which the discrete logarithm problem (Dlog for short) is assumed to be hard (or other discrete-log type assumptions like CDH and DDH). The two most common classes are a prime subgroup of the group Z_p^* for a large p, and some Elliptic curve groups.

We provide the implementation of the most important Dlog groups in cryptography (see diagram below):

  • Z_p^*
  • Elliptic curve over the field GF[2^m]
  • Elliptic curve over the field Z_p

Although Elliptic curves groups look very different, the discrete log problem over them can be described as follows. Given an elliptic curve E over a finite field F, a base point on that curve P (i.e., a generator of the group defined from the curve), and a random point Q on the curve, the problem is to find the integer n such that nP=Q.

We have currently incorporated the elliptic curves recommended by NIST.

Class Hierarchy:

The root of the family is a general Dlog Group that presents functionality that all Dlog Groups should implement.

At the second level we encounter three interfaces:

  1. PrimeOrderSubGroup: The order q of the group must be a prime.
  2. DlogZp: Dlog Group over the Z_p^* field.
  3. DlogEllipticCurve: Any elliptic curve.

At the third level we have:

  1. DlogZpSafePrime: The order q is not only a prime but also is such that prime p = 2*q + 1.
  2. DlogEcFp: Any elliptic curve over F_p.
  3. DlogEcF2m: Any elliptic curve over F_2[m].

All these are general interfaces. Specifically, we implement Dlog Groups that are of prime order; therefore all the concrete classes presented here implement this interface. Other implementations may choose to add Dlog Groups that are not of prime order, and they are at liberty of doing so. They just need not to declare that they implement the PrimeOrderSubGroup interface.

We also see in the diagram two other interfaces that are used by DlogGroup:

  1. GroupParams.
  2. GroupElement.

The DlogGroup Interface

Group Parameters

public GroupElement getGenerator()

The generator g of the group is an element of the group such that, when written multiplicatively, every element of the group is a power of g.

Returns:the generator of this Dlog group
public GroupElement createRandomGenerator()

Creates a random generator of this Dlog group

Returns:the random generator
public BigInteger getOrder()
Returns:the order of this Dlog group
public GroupParams getGroupParams()

GroupParams is a structure that holds the actual data that makes this group a specific Dlog group. For example, for a Dlog group over Zp* what defines the group is p.

Returns:the GroupParams of that Dlog group
public String getGroupType()

Each concrete class implementing this interface returns a string with a meaningful name for this type of Dlog group. For example: “elliptic curve over F2m” or “Zp*”

Returns:the name of the group type
public GroupElement getIdentity()
Returns:the identity of this Dlog group

Exponentiation

public GroupElement exponentiate(GroupElement base, BigInteger exponent)

Raises the base GroupElement to the exponent. The result is another GroupElement.

Parameters:
  • base
  • exponent
Throws:
Returns:

the result of the exponentiation

public GroupElement exponentiateWithPreComputedValues(GroupElement base, BigInteger exponent)

Computes the product of several exponentiations of the same base and distinct exponents. An optimization is used to compute it more quickly by keeping in memory the result of h1, h2, h4,h8,... and using it in the calculation.

Note that if we want a one-time exponentiation of h it is preferable to use the basic exponentiation function since there is no point to keep anything in memory if we have no intention to use it.

Parameters:
  • base
  • exponent
Returns:

the exponentiation result

public void endExponentiateWithPreComputedValues(GroupElement base)

This function cleans up any resources used by exponentiateWithPreComputedValues for the requested base. It is recommended to call it whenever an application does not need to continue calculating exponentiations for this specific base.

Parameters:
  • base
public GroupElement simultaneousMultipleExponentiations(GroupElement[] groupElements, BigInteger[] exponentiations)

Computes the product of several exponentiations with distinct bases and distinct exponents. Instead of computing each part separately, an optimization is used to compute it simultaneously.

Parameters:
  • groupElements
  • exponentiations
Returns:

the exponentiation result

Multiplication and Inverse

public GroupElement getInverse(GroupElement groupElement)

Calculates the inverse of the given GroupElement.

Parameters:
  • groupElement – to invert
Throws:
Returns:

the inverse element of the given GroupElement

public GroupElement multiplyGroupElements(GroupElement groupElement1, GroupElement groupElement2)

Multiplies two GroupElements

Parameters:
  • groupElement1
  • groupElement2
Throws:
Returns:

the multiplication result

Group Element Generation

public GroupElement createRandomElement()

Creates a random member of this Dlog group

Returns:the random element
public GroupElement generateElement(boolean bCheckMembership, BigInteger... values)

This function allows the generation of a group element by a protocol that holds a Dlog Group but does not know if it is a Zp Dlog Group or an Elliptic Curve Dlog Group. It receives the possible values of a group element and whether to check membership of the group element to the group or not.

It may be not necessary to check membership if the source of values is a trusted source (it can be the group itself after some calculation). On the other hand, to work with a generated group element that is not really an element in the group is wrong. It is up to the caller of the function to decide if to check membership or not. If bCheckMembership is false always generate the element. Else, generate it only if the values are correct.

Parameters:
  • bCheckMembership
  • values
Throws:
Returns:

the generated GroupElement

Validation

public boolean isGenerator()

Checks if the element set as the generator is indeed the generator of this group.

Returns:true if the generator is valid, false otherwise.
public boolean isMember(GroupElement element)

Checks if the given element is a member of this Dlog group

Parameters:
  • element – possible group element for which to check that it is a member of this group
Throws:
Returns:

true if the given element is a member of this group, false otherwise.

public boolean validateGroup()

Checks parameters of this group to see if they conform to the type this group is supposed to be.

Returns:true if valid, false otherwise.

Group Classification

public boolean isOrderGreaterThan(int numBits)

Checks if the order of this group is greater than 2^numBits

Parameters:
  • numBits
Returns:

true if the order is greater than 2^numBits, false otherwise.

public boolean isPrimeOrder()

Checks if the order is a prime number

Returns:true if the order is a prime number, false otherwise.

Group Element Serialization

public GroupElement reconstructElement(boolean bCheckMembership, GroupElementSendableData data)

Reconstructs a GroupElement given the GroupElementSendableData data, which might have been received through a Channel open between the party holding this DlogGroup and some other party.

Parameters:
  • bCheckMembership – whether to check that the data provided can actually reconstruct an element of this DlogGroup. Since this action is expensive it should be used only if necessary.
  • data – the GroupElementSendableData from which we wish to “reconstruct” an element of this DlogGroup
Returns:

the reconstructed GroupElement

Byte Array Encoding

public GroupElement encodeByteArrayToGroupElement(byte[] binaryString)

This function takes any string of length up to k bytes and encodes it to a Group Element. k can be obtained by calling getMaxLengthOfByteArrayForEncoding() and it is calculated upon construction of this group; it depends on the length in bits of p.

The encoding-decoding functionality is not a bijection, that is, it is a 1-1 function but is not onto. Therefore, any string of length in bytes up to k can be encoded to a group element but not every group element can be decoded to a binary string in the group of binary strings of length up to 2^k.

Thus, the right way to use this functionality is first to encode a byte array and then to decode it, and not the opposite.

Parameters:
  • binaryString – the byte array to encode
Returns:

the encoded group Element or null if the string could not be encoded

public byte[] decodeGroupElementToByteArray(GroupElement groupElement)

This function decodes a group element to a byte array. This function is guaranteed to work properly ONLY if the group element was obtained as a result of encoding a binary string of length in bytes up to k.

This is because the encoding-decoding functionality is not a bijection, that is, it is a 1-1 function but is not onto. Therefore, any string of length in bytes up to k can be encoded to a group element but not any group element can be decoded to a binary sting in the group of binary strings of length up to 2^k.

Parameters:
  • groupElement – the element to decode
Returns:

the decoded byte array

public int getMaxLengthOfByteArrayForEncoding()

This function returns the value k which is the maximum length of a string to be encoded to a Group Element of this group. Any string of length k has a numeric value that is less than (p-1)/2. k is the maximum length a binary string is allowed to be in order to encode the said binary string to a group element and vice-versa. If a string exceeds the k length it cannot be encoded.

Returns:k the maximum length of a string to be encoded to a Group Element of this group. k can be zero if there is no maximum.
public byte[] mapAnyGroupElementToByteArray(GroupElement groupElement)

This function maps a group element of this dlog group to a byte array. This function does not have an inverse function, that is, it is not possible to re-construct the original group element from the resulting byte array.

Returns:a byte array representation of the given group element

The GroupElement Interface

public GroupElementSendableData generateSendableData()

This function is used when a group element needs to be sent via a edu.biu.scapi.comm.Channel or any other means of sending data (including serialization). It retrieves all the data needed to reconstruct this Group Element at a later time and/or in a different VM. It puts all the data in an instance of the relevant class that implements the GroupElementSendableData interface.

Returns:the GroupElementSendableData object
public boolean isIdentity()

checks if this element is the identity of the group.

Returns:true if this element is the identity of the group, false otherwise.

The GroupParams Interface

public BigInteger getQ()
Returns:the group order q

Basic Usage

// initiate a discrete log group (in this case the OpenSSL implementation of the elliptic curve group K-233)
DlogGroup dlog = new OpenSSLDlogECF2m("K-233");
SecureRandom random = new SecureRandom();

// get the group generator and order
GroupElement g = dlog.getGenerator();
BigInteger q = dlog.getOrder();
BigInteger qMinusOne = q.subtract(BigInteger.ONE);

// create a random exponent r
BigInteger r = BigIntegers.createRandomInRange(BigInteger.ZERO, qMinusOne, random);
// exponentiate g in r to receive a new group element
GroupElement g1 = dlog.exponentiate(g, r);
// create a random group element

GroupElement h = dlog.createRandomElement();
// multiply elements
GroupElement gMult = dlog.multiplyGroupElements(g1, h);